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

智能优化方法AI-BasedOptimizationMethods,ByProfessorDingweiWangNortheasternUniversityChina2004,第六章最近发展起来的新算法,一.蚁群优化ACO二.粒子群优化三.其它新方法四.我们的工作：群落选址算法,蚁群优化的产生蚁群优化AntColonyOptimization在1995-1996年，Dorigo(Italy)提出ACO基本思想模拟蚂蚁选择路线的能力。即：蚂蚁以信息素的强度为概率来决定路线选择。,一.蚁群优化（1）,ACO,整体往往大于部分的“简单和”蚂蚁的低智能蚁群的高智慧蚂蚁的简单行为蚁群的智能突现实际蚁群的觅食1、主体（agent)：蚂蚁2、简单的规则（rules）：分工、通讯3、相互作用（interaction）：蚂蚁蚂蚁蚂蚁环境,ACO,观察实际蚁群的觅食1：,ACO,观察实际蚁群的觅食2：用障碍物切断原来的通路,ACO,观察实际蚁群的觅食3：搜索新路,ACO,观察实际蚁群的觅食4：最佳路径形成,ACO的基本计算公式ACO最早用来解决TSP问题,一.蚁群优化（2）,蚂蚁标号,迭代次数,信息素的影响,一.蚁群优化（3）,举例说明,一.蚁群优化（4）,信息素强度的计算,一.蚁群优化（5）,蚂蚁k的巡回长度,常量,所有蚂蚁留下的信息,信息素增量,遗忘因子,ACO的基本算法步骤初始化令S=1,(S是tabu表的指标，即走过的城市数)将所有的初始城市记入,一.蚁群优化（6）,重复以下步骤，直到tabu表填满（所有城市走过）。令S=S+1,对k=1到m个城市，以选择城市j移动，将j加入。对（计算信息素，理解为每个蚂蚁在路径(i,j)上留下的总气味）,一.蚁群优化（7）,对若NC大于停止，否则转，并清空tabu表,一.蚁群优化（8）,粒子群优化（ParticleSwarmOptimization）PSO的产生1995年，Kennedy&Eberhart提出PSOPSO已经成为当今的热门2003年，控制与决策第二期刊登国内第一篇PSO论文综述文章,二.粒子群优化（1）,PSO的基本思想模仿鸟群的飞行，觅食行为特征（用Swarm仿真软件仿真）保持惯性按自身的最优修正方向按群体的最优修正方向,二.粒子群优化（2）,PSO的特点公式简单，待定系数少，可用来解实优化,二.粒子群优化（3）,PSO的基本公式,二.粒子群优化（4）,过去的方向,个体最优方向，第d个分量,群体最优方向,其中：,二.粒子群优化（5）,PSO的计算步骤初始化粒子群，给予随机的位置和速度评估每个粒子的适应值（目标函数值）对每个粒子，更新历史最优位置对群体更新历史最好解,二.粒子群优化（6）,对所有粒子计算若达到最大迭代数停止，否则转以上就是PSO最早最初始的经典算法，以后有多种改进。,二.粒子群优化（7）,文化算法（CultureAlgorithm）文化算法的基本思想：借鉴不同文化的相互排斥的特性，用到进化算法中。,三.其它新方法（1）,掠夺搜索策略（PSS）掠夺搜索策略的基本思想：模仿猛兽的捕食策略（广域与邻域有效结合起来）。,三.其它新方法（2）,人工生命算法人工生命算法的基本思想：模仿生态环境中多种种群的相互作用。,三.其它新方法（3）,ALA,食物链：（来自生物学的解释）生产者所固有的能量和物质，通过一系列取食和被食的关系在生态系统中传递，各种生物按其食物关系排列的链状顺序称为食物链（foodchain)。简单的生物链（下图所示）,食物链模式的人工生命算法思想定义食物链,:Resource,：Artificialorganism,说明：1、定义了四种资源：ResourceB,W,R和G；2、定义四种生物：Blue,white，Red和Green；3、定义它们之间的取食关系：White生物吃蓝色资源，白色废物；White白色废物，成为红色生物的资源。其他，依次类推。,ALA,算法描述：Step1:初始化（initalization）产生四种相等数量的人工生物，并随机的布置在人工环境之中；每种人工生物的初始能量是Ie；产生四种相等数量的资源随机的布置在人工环境之中；设定最大代数。Step2:寻找资源（searchresource)人工生物在它们的邻域内，从当前位置寻找离它最近的资源,ALA,Step3：移动时使用优值保留策略（elitereservationstrategy）：首先，如果它们发现它们想吃的最近的资源在它们的邻域内，它们就移向它；其次，如果不是这样，它们就随机的在它们的邻域内移动；当随机移动时，采用优值保留策略即：如果人工生物有高的适值，那么它们移动最小的距离，以便仅轻微的改变适值，并甚至得到能量Ee。因此具有更高适值的生物有更多的机会生存。,ALA,Step4:新陈代谢（Metabolism）：如果人工生物发现最近的资源正是它们想要的吃的（Metabolism），它们就吃了它，并得到能量Ge，并随机的产生废物在邻域内。Step5:年龄增长（aging）在这个过程中，每个生物的年龄增加1。Step6：复制（reproduction）如果生物年龄达到了Ra，并且能量=Re，它将和最近的同种的同样满足上述条件的生物交配。规则如下：例如：A，B都满足年龄达到了Ra，并且能量=Re，它们依据概率Rp来决定是复制它们自己(clone)还是交配(mate)。,ALA,Step7:减少能量（ReduceEnergy）：所有的生物将减少能量Le。如果某个人工生物的能量少有Ld，则它将死掉，同时从人工环境中移走。Step8:增长代数（Increasinggenernation）：代数增加1；如果代数小于结束的代数，返回Step2；否则结束计算。,ALA,韩国学者Bo-SukYang等人在Optimumdesignofshortjournalbearingsbyartificiallifealgorithm一文中，应用该算法进行短经向轴承的优化设计。,四.我们的工作：群落选址算法ColonyLocationAlgorithm(CLA),基本思想模拟植物群落形成机制土地含有的适于植物生长营养成分；不同物种间对生存资源的竞争；人工干预手段施肥策略。,CLA,养分函数Nij(t):在t时刻，土地j对群落i的养分。加上时间t，是因为施肥可以改变肥力。对于指派问题，A为工作时间，（极小化）Nij(t)1aij,即可。对于TSP，Nij(t)1dij,即可。对于QAP，怎么设？,CLA,生长率与衰亡率生长率：r是平均生长率，是所有土地对i的平均肥力。（行均值）,衰亡率：是土地j对所有群落的肥力的均值。（列均值）,CLA,CLA,群落比例与归一化设xij(t)是群落i在土地j上的比例；生长过程带来比例的和不是1。行、列归一化，反复进行。,生长过程,CLA,CLA,解的构成与评估xij(t)不是解。以xij(t)为概率，在每块土地上产生一个群落，问题是要保证一个群落不能同时在两块土地上解的合法性。其实很简单，按随机顺序，在剩余群落中选。,CLA,施肥过程若S(k*)是最好解；,或者,CLA,解的信息熵的计算解的信息熵：,CLA,停止判据停止准则的计算：,指派问题的计算