近发展起来的新算法

《近发展起来的新算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、智能优化方法AI-BasedOptimizationMethodsByProfessorDingweiWangNortheasternUniversityChina20041第六章最近发展起来的新算法一.蚁群优化ACO二.粒子群优化三.其它新方法四.我们的工作：群落选址算法2蚁群优化的产生蚁群优化AntColonyOptimization在1995-1996年，Dorigo(Italy)提出ACO基本思想模拟蚂蚁选择路线的能力。即：蚂蚁以信息素的强度为概率来决定路线选择。一.蚁群优化（1）3ACO整体往往大于部分的“简单和”蚂蚁的低智能——蚁群的高智慧蚂蚁的简单行为——蚁群的智能突现实际蚁群

2、的觅食1、主体（agent)：蚂蚁2、简单的规则（rules）：分工、通讯3、相互作用（interaction）：蚂蚁<==触角放电==>蚂蚁蚂蚁<==气味积累==>环境4ACO观察实际蚁群的觅食1：5ACO观察实际蚁群的觅食2：用障碍物切断原来的通路6ACO观察实际蚁群的觅食3：搜索新路7ACO观察实际蚁群的觅食4：最佳路径形成8ACO的基本计算公式ACO最早用来解决TSP问题一.蚁群优化（2）蚂蚁标号迭代次数信息素的影响9一.蚁群优化（3）10举例说明一.蚁群优化（4）1534211信息素强度的计算一.蚁群优化（5）蚂蚁k的巡回长度常量所有蚂蚁留下的信息信息素增量遗忘因子12ACO的基本

3、算法步骤初始化令S=1,(S是tabu表的指标，即走过的城市数)将所有的初始城市记入一.蚁群优化（6）13重复以下步骤，直到tabu表填满（所有城市走过）。令S=S+1,对k=1到m个城市，以选择城市j移动，将j加入。对（计算信息素，理解为每个蚂蚁在路径(i,j)上留下的总气味）一.蚁群优化（7）14对若NC大于停止，否则转②，并清空tabu表一.蚁群优化（8）15粒子群优化（ParticleSwarmOptimization）PSO的产生1995年，Kennedy&Eberhart提出PSOPSO已经成为当今的热门2003年，《控制与决策》第二期刊登国内第一篇PSO论文——综述文章二.粒子

4、群优化（1）16PSO的基本思想模仿鸟群的飞行，觅食行为特征（用Swarm仿真软件仿真）保持惯性按自身的最优修正方向按群体的最优修正方向二.粒子群优化（2）17PSO的特点公式简单，待定系数少，可用来解实优化二.粒子群优化（3）18PSO的基本公式二.粒子群优化（4）过去的方向个体最优方向，第d个分量群体最优方向19其中：二.粒子群优化（5）20PSO的计算步骤初始化粒子群，给予随机的位置和速度评估每个粒子的适应值（目标函数值）对每个粒子，更新历史最优位置对群体更新历史最好解二.粒子群优化（6）21对所有粒子计算若达到最大迭代数停止，否则转②以上就是PSO最早最初始的经典算法，以后有多种改进

5、。二.粒子群优化（7）22文化算法（CultureAlgorithm）文化算法的基本思想：借鉴不同文化的相互排斥的特性，用到进化算法中。三.其它新方法（1）23掠夺搜索策略（PSS）掠夺搜索策略的基本思想：模仿猛兽的捕食策略（广域与邻域有效结合起来）。三.其它新方法（2）24人工生命算法人工生命算法的基本思想：模仿生态环境中多种种群的相互作用。三.其它新方法（3）25ALA食物链：（来自生物学的解释）生产者所固有的能量和物质，通过一系列取食和被食的关系在生态系统中传递，各种生物按其食物关系排列的链状顺序称为食物链（foodchain)。简单的生物链（下图所示）26食物链模式的人工生命算法思想

6、定义食物链: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白色废物，成为红色生物的资源27ALA算法描述：Step1:初始化（initalization）产生四种相等数量的人工生物，

7、并随机的布置在人工环境之中；每种人工生物的初始能量是Ie；产生四种相等数量的资源随机的布置在人工环境之中；设定最大代数。Step2:寻找资源（searchresource)人工生物在它们的邻域内，从当前位置寻找离它最近的资源28ALAStep3：移动时使用优值保留策略（elitereservationstrategy）：首先，如果它们发现它们想吃的最近的资源在它们的邻域内，它们就移向它；其次，如果不是这样，它