第六章 最近发展起来的新算法

1智能优化方法AI-BasedOptimizationMethodsByProfessorDingweiWangNortheasternUniversityChina20042第六章最近发展起来的新算法一.蚁群优化ACO二.粒子群优化三.其它新方法四.我们的工作：群落选址算法31.蚁群优化的产生蚁群优化AntColonyOptimization在1995-1996年，Dorigo(Italy)提出ACO2.基本思想模拟蚂蚁选择路线的能力。即：蚂蚁以信息素的强度为概率来决定路线选择。一.蚁群优化（1）4ACO整体往往大于部分的“简单和”蚂蚁的低智能——蚁群的高智慧蚂蚁的简单行为——蚁群的智能突现实际蚁群的觅食1、主体（agent)：蚂蚁2、简单的规则（rules）：分工、通讯3、相互作用（interaction）：蚂蚁==触角放电==蚂蚁蚂蚁==气味积累==环境5ACO观察实际蚁群的觅食1：6ACO观察实际蚁群的觅食2：用障碍物切断原来的通路7ACO观察实际蚁群的觅食3：搜索新路8ACO观察实际蚁群的觅食4：最佳路径形成93.ACO的基本计算公式ACO最早用来解决TSP问题一.蚁群优化（2）其它选择概率公式：城市间的距离为个城市的,0Aj,,kAlilijijijkijijttPdTSPn蚂蚁标号迭代次数信息素的影响10一.蚁群优化（3）只考虑信息素、贪婪启发式，、重要程度节信息素和距离的是指数型权重，用来调，走过的城市表示蚂蚁没走过的城市表示蚂蚁，距离的影响0110,\1kttabukAttabuNAdkkkkijij114.举例说明一.蚁群优化（4）1534215d12d13d3,210510511AkTabuk没有走过的城市蚂蚁，已走过蚂蚁1313121213131313131212121212pp蚂蚁的选择概率为：125.信息素强度的计算一.蚁群优化（5）其它，的巡回上在，边0kij1kkijMkkijijijijijLQtnt蚂蚁k的巡回长度常量所有蚂蚁留下的信息信息素增量遗忘因子136.ACO的基本算法步骤①初始化②令S=1,(S是tabu表的指标，即走过的城市数)将所有的初始城市记入一.蚁群优化（6）个城市中。个蚂蚁分散到。将）令，对所有的边（巡回次数，令nmctjiNCtijij0,,)(00ttabuk14③重复以下步骤，直到tabu表填满（所有城市走过）。令S=S+1,对k=1到m个城市，以选择城市j移动，将j加入。④对（计算信息素，理解为每个蚂蚁在路径(i,j)上留下的总气味）一.蚁群优化（7）tPkijstabuk。计算历史最优解）对边更新最短巡回（即下，计算到ijkijkjiLMk,,,115⑤对⑥若NC大于停止，否则转②，并清空tabu表一.蚁群优化（8）1,,ijNCNCnttnt令所有边计算maxNC16粒子群优化（ParticleSwarmOptimization）1.PSO的产生1995年，Kennedy&Eberhart提出PSOPSO已经成为当今的热门2003年，《控制与决策》第二期刊登国内第一篇PSO论文——综述文章二.粒子群优化（1）172.PSO的基本思想模仿鸟群的飞行，觅食行为特征（用Swarm仿真软件仿真）①保持惯性②按自身的最优修正方向③按群体的最优修正方向二.粒子群优化（2）183.PSO的特点公式简单，待定系数少，可用来解实优化二.粒子群优化（3）194.PSO的基本公式二.粒子群优化（4）idkidkididgdididkidkidiDidiiiVXXccXPcXPcVVVVVVVi121212211121,,1,0,,,,,,是常数，其速度每一代，对于粒子过去的方向个体最优方向，第d个分量群体最优方向20其中：二.粒子群优化（5）是群体的历史最好解个分量的第是的历史最优解是粒子giidipdppip216.PSO的计算步骤①初始化粒子群，给予随机的位置和速度②评估每个粒子的适应值（目标函数值）③对每个粒子，更新历史最优位置④对群体更新历史最好解二.粒子群优化（6）mi,,2,1iivx,mixFxfi,,2,1,其中ipgp22⑤对所有粒子计算⑥若达到最大迭代数停止，否则转②以上就是PSO最早最初始的经典算法，以后有多种改进。二.粒子群优化（7）iivx,231.文化算法（CultureAlgorithm）文化算法的基本思想：借鉴不同文化的相互排斥的特性，用到进化算法中。三.其它新方法（1）242.掠夺搜索策略（PSS）掠夺搜索策略的基本思想：模仿猛兽的捕食策略（广域与邻域有效结合起来）。三.其它新方法（2）253.人工生命算法人工生命算法的基本思想：模仿生态环境中多种种群的相互作用。三.其它新方法（3）26ALA食物链：（来自生物学的解释）生产者所固有的能量和物质，通过一系列取食和被食的关系在生态系统中传递，各种生物按其食物关系排列的链状顺序称为食物链（foodchain)。简单的生物链（下图所示）27食物链模式的人工生命算法思想定义食物链:Resource：Artificialorganism说明：1、定义了四种资源：ResourceB,W,R和G；2、定义四种生物：Blue,white，Red和Green；3、定义它们之间的取食关系：White生物吃蓝色资源，白色废物；White白色废物，成为红色生物的资源。其他，依次类推。Resource(B)Resource(G)Resource(R)Resource(W)WhiteRedGreenBlueWhite生物吃蓝色资源，产生白色废物White白色废物，成为红色生物的资源28ALA算法描述：Step1:初始化（initalization）产生四种相等数量的人工生物，并随机的布置在人工环境之中；每种人工生物的初始能量是Ie；产生四种相等数量的资源随机的布置在人工环境之中；设定最大代数。Step2:寻找资源（searchresource)人工生物在它们的邻域内，从当前位置寻找离它最近的资源29ALAStep3：移动时使用优值保留策略（elitereservationstrategy）：首先，如果它们发现它们想吃的最近的资源在它们的邻域内，它们就移向它；其次，如果不是这样，它们就随机的在它们的邻域内移动；当随机移动时，采用优值保留策略即：如果人工生物有高的适值，那么它们移动最小的距离，以便仅轻微的改变适值，并甚至得到能量Ee。因此具有更高适值的生物有更多的机会生存。30ALAStep4:新陈代谢（Metabolism）：如果人工生物发现最近的资源正是它们想要的吃的（Metabolism），它们就吃了它，并得到能量Ge，并随机的产生废物在邻域内。Step5:年龄增长（aging）在这个过程中，每个生物的年龄增加1。Step6：复制（reproduction）如果生物年龄达到了Ra，并且能量=Re，它将和最近的同种的同样满足上述条件的生物交配。规则如下：例如：A，B都满足年龄达到了Ra，并且能量=Re，它们依据概率Rp来决定是复制它们自己(clone)还是交配(mate)。31ALAStep7:减少能量（ReduceEnergy）：所有的生物将减少能量Le。如果某个人工生物的能量少有Ld，则它将死掉，同时从人工环境中移走。Step8:增长代数（Increasinggenernation）：代数增加1；如果代数小于结束的代数，返回Step2；否则结束计算。32ALA韩国学者Bo-SukYang等人在《Optimumdesignofshortjournalbearingsbyartificiallifealgorithm》一文中，应用该算法进行短经向轴承的优化设计。33四.我们的工作：群落选址算法ColonyLocationAlgorithm(CLA)基本思想模拟植物群落形成机制－•－土地含有的适于植物生长营养成分；•不同物种间对生存资源的竞争；人工干预手段——施肥策略。34CLA养分函数Nij(t):在t时刻，土地j对群落i的养分。加上时间t，是因为施肥可以改变肥力。对于指派问题，A为工作时间，（极小化）Nij(t)＝1／aij,即可。对于TSP，Nij(t)＝1／dij,即可。对于QAP，怎么设？35CLA生长率与衰亡率生长率：r是平均生长率，是所有土地对i的平均肥力。（行均值）36衰亡率：是土地j对所有群落的肥力的均值。（列均值）CLA37CLA群落比例与归一化设xij(t)是群落i在土地j上的比例；生长过程带来比例的和不是1。行、列归一化，反复进行。38生长过程CLA39CLA解的构成与评估xij(t)不是解。以xij(t)为概率，在每块土地上产生一个群落，问题是要保证一个群落不能同时在两块土地上—解的合法性。其实很简单，按随机顺序，在剩余群落中选。40CLA施肥过程若S(k*)是最好解；或者41CLA解的信息熵的计算解的信息熵：42CLA停止判据停止准则的计算：43指派问题的计算结果444546CLATSP的计算结果全国33城市的TSP计算结果好于文献的结果，但TSP.Lab测试题的计算结果不好。工作还需要继续进行。47CLAQAP的计算结果自己编的题目计算结果不错但对大规模问题计算效果不好，还需要做很多工作。包括养分函数的设置方法都还是问题。48欢迎提问，批评。谢谢大家！49课程全部结束谢谢！