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

智能优化方法

AI-BasedOptimizationMethodsByProfessorDingweiWangNortheasternUniversityChina20041智能优化方法

AI-BasedOptimizationM第六章最近发展起来的新算法一.蚁群优化ACO二.粒子群优化三.其它新方法四.我们的工作：群落选址算法2第六章最近发展起来的新算法一.蚁群优化ACO2蚁群优化的产生 蚁群优化AntColonyOptimization在1995-1996年，Dorigo(Italy)提出ACO基本思想 模拟蚂蚁选择路线的能力。即：蚂蚁以信息素的强度为概率来决定路线选择。一.蚁群优化（1）3蚁群优化的产生一.蚁群优化（1）3ACO整体往往大于部分的“简单和”蚂蚁的低智能——蚁群的高智慧蚂蚁的简单行为——蚁群的智能突现实际蚁群的觅食1、主体（agent)：蚂蚁2、简单的规则（rules）：分工、通讯3、相互作用（interaction）： 蚂蚁<==触角放电==>蚂蚁蚂蚁<==气味积累==>环境4ACO整体往往大于部分的“简单和”4ACO观察实际蚁群的觅食1：5ACO观察实际蚁群的觅食1：5ACO观察实际蚁群的觅食2：

用障碍物切断原来的通路6ACO观察实际蚁群的觅食2：用障碍物切断原来的通路6ACO观察实际蚁群的觅食3：

搜索新路7ACO观察实际蚁群的觅食3：搜索新路7ACO观察实际蚁群的觅食4：最佳路径形成8ACO观察实际蚁群的觅食4：最佳路径形成8ACO的基本计算公式 ACO最早用来解决TSP问题一.蚁群优化（2）蚂蚁标号迭代次数信息素的影响9ACO的基本计算公式一.蚁群优化（2）蚂蚁标号迭代次数信息素一.蚁群优化（3）10一.蚁群优化（3）10举例说明一.蚁群优化（4）1534211举例说明一.蚁群优化（4）1534211信息素强度的计算一.蚁群优化（5）蚂蚁k的巡回长度常量所有蚂蚁留下的信息信息素增量遗忘因子12信息素强度的计算一.蚁群优化（5）蚂蚁k的巡回长度常量所有蚂ACO的基本算法步骤初始化令S=1,(S是tabu表的指标，即走过的城市数)将所有的初始城市记入一.蚁群优化（6）13ACO的基本算法步骤一.蚁群优化（6）13重复以下步骤，直到tabu表填满（所有城市 走过）。令S=S+1,对k=1到m个城市，以选择城市j移动，将j加入。对

（计算信息素，理解为每个蚂蚁在路径(i,j)上留下的总气味）一.蚁群优化（7）14重复以下步骤，直到tabu表填满（所有城市一.蚁群优化（7）对若NC大于 停止，否则转②，并清空tabu表一.蚁群优化（8）15对一.蚁群优化（8）15粒子群优化（ParticleSwarmOptimization）PSO的产生1995年，Kennedy&Eberhart提出PSOPSO已经成为当今的热门2003年，《控制与决策》第二期刊登国内第一篇PSO论文——综述文章二.粒子群优化（1）16粒子群优化（ParticleSwarmOptimizatPSO的基本思想 模仿鸟群的飞行，觅食行为特征（用Swarm仿真软件仿真）保持惯性按自身的最优修正方向按群体的最优修正方向二.粒子群优化（2）17PSO的基本思想二.粒子群优化（2）17PSO的特点 公式简单，待定系数少，可用来解实优化二.粒子群优化（3）18PSO的特点二.粒子群优化（3）18PSO的基本公式二.粒子群优化（4）过去的方向个体最优方向，第d个分量群体最优方向19PSO的基本公式二.粒子群优化（4）过去的方向个体最优方向其中：二.粒子群优化（5）20其中：二.粒子群优化（5）20PSO的计算步骤初始化粒子群，给予随机的位置和速度评估每个粒子的适应值 （目标函数值）对每个粒子，更新历史最优位置对群体更新历史最好解二.粒子群优化（6）21PSO的计算步骤二.粒子群优化（6）21对所有粒子计算若达到最大迭代数停止，否则转② 以上就是PSO最早最初始的经典算法，以后有多种改进。二.粒子群优化（7）22对所有粒子计算二.粒子群优化（7）22文化算法（CultureAlgorithm）文化算法的基本思想： 借鉴不同文化的相互排斥的特性，用到进化算法中。三.其它新方法（1）23文化算法（CultureAlgorithm）三.其它新方掠夺搜索策略（PSS）掠夺搜索策略的基本思想： 模仿猛兽的捕食策略（广域与邻域有效结合起来）。三.其它新方法（2）24掠夺搜索策略（PSS）三.其它新方法（2）24人工生命算法人工生命算法的基本思想： 模仿生态环境中多种种群的相互作用。三.其它新方法（3）25人工生命算法三.其它新方法（3）25ALA食物链：（来自生物学的解释）生产者所固有的能量和物质，通过一系列取食和被食的关系在生态系统中传递，各种生物按其食物关系排列的链状顺序称为食物链（foodchain)。简单的生物链（下图所示）26ALA食物链：（来自生物学的解释）26食物链模式的人工生命算法思想定义食物链:Resource：Artificialorganism说明：1、定义了四种资源：ResourceB,W,R和G；2、定义四种生物：Blue,white，Red和Green；3、定义它们之间的取食关系：White生物吃蓝色资源，白色废物；White白色废物，成为红色生物的资源。其他，依次类推。Resource(B)Resource(G)Resource(R)Resource(W)WhiteRedGreenBlue

White生物吃蓝色资源，产生白色废物

White白色废物，成为红色生物的资源27食物链模式的人工生命算法思想:Resource：ArtifiALA算法描述：Step1:初始化（initalization）产生四种相等数量的人工生物，并随机的布置在人工环境之中；每种人工生物的初始能量是Ie；产生四种相等数量的资源随机的布置在人工环境之中；设定最大代数。Step2:寻找资源（searchresource)人工生物在它们的邻域内，从当前位置寻找离它最近的资源28ALA算法描述：28ALAStep3：移动时使用优值保留策略（elitereservationstrategy）：首先，如果它们发现它们想吃的最近的资源在它们的邻域内，它们就移向它；其次，如果不是这样，它们就随机的在它们的邻域内移动；当随机移动时，采用优值保留策略即：如果人工生物有高的适值，那么它们移动最小的距离，以便仅轻微的改变适值，并甚至得到能量Ee。因此具有更高适值的生物有更多的机会生存。29ALAStep3：移动时使用优值保留策略（eliteresALAStep4:新陈代谢（Metabolism）：如果人工生物发现最近的资源正是它们想要的吃的（Metabolism），它们就吃了它，并得到能量Ge，并随机的产生废物在邻域内。Step5:年龄增长（aging）在这个过程中，每个生物的年龄增加1。Step6：复制（reproduction）如果生物年龄达到了Ra，并且能量>=Re，它将和最近的同种的同样满足上述条件的生物交配。规则如下：例如：A，B都满足年龄达到了Ra，并且能量>=Re，它们依据概率Rp来决定是复制它们自己(clone)还是交配(mate)。30ALAStep4:新陈代谢（Metabolism）：30ALAStep7:减少能量（ReduceEnergy）：所有的生物将减少能量Le。如果某个人工生物的能量少有Ld，则它将死掉，同时从人工环境中移走。Step8:增长代数（Increasinggenernation）：代数增加1；如果代数小于结束的代数，返回Step2；否则结束计算。31ALAStep7:减少能量（ReduceEnergy）ALA韩国学者Bo-SukYang等人在《Optimumdesignofshortjournalbearingsbyartificiallifealgorithm》一文中，应用该算法进行短经向轴承的优化设计。32ALA韩国学者Bo-SukYang等人在《Optimum四.我们的工作：群落选址算法

ColonyLocationAlgorithm(CLA)基本思想模拟植物群落形成机制－－土地含有的适于植物生长营养成分；不同物种间对生存资源的竞争；人工干预手段——施肥策略。33四.我们的工作：群落选址算法

ColonyLocationCLA养分函数Nij(t):在t时刻，土地j对群落i的养分。加上时间t，是因为施肥可以改变肥力。对于指派问题，A为工作时间，（极小化）Nij(t)＝1／aij,即可。对于TSP，Nij(t)＝1／dij,即可。对于QAP，怎么设？34CLA养分函数34CLA生长率与衰亡率生长率：r是平均生长率，是所有土地对i的平均肥力。（行均值）35CLA生长率与衰亡率35衰亡率：是土地j对所有群落的肥力的均值。（列均值）CLA36衰亡率：CLA36CLA群落比例与归一化设xij(t)是群落i在土地j上的比例；生长过程带来比例的和不是1。行、列归一化，反复进行。37CLA群落比例与归一化37生长过程CLA38生长过程CLA38CLA解的构成与评估xij(t)不是解。以xij(t)为概率，在每块土地上产生一个群落，问题是要保证一个群落不能同时在两块土地上—解的合法性。其实很简单，按随机顺序，在剩余群落中选。39CLA解的构成与评估39CLA施肥过程若S(k*)是最好解；或者40CLA施肥过程或者40CLA解的信息熵的计算解的信息熵：41CLA解的信息熵的计算41CLA停止判据停止准则的计算：42CLA停止判据42指派问题的计算结果43指派问题的计算结果4344444545CLATSP的计算结果全国33城市的TSP计算结果好于文献的结果，但TSP.Lab测试题的计算结果不好。工作还需要继续进行。46CLATSP的计算结果46CLAQAP的计算结果自己编的题目计算结果不错但对大规模问题计算效果不好，还需要做很多工作。包括养分函数的设置方法都还是问题。47CLAQAP的计算结果47欢迎提问，批评。谢谢大家！48欢迎提问，批评。谢谢大家！48课程全部结束

谢谢！49课程全部结束

谢谢！49演讲完毕，谢谢观看！演讲完毕，谢谢观看！智能优化方法

AI-BasedOptimizationMethodsByProfessorDingweiWangNortheasternUniversityChina200451智能优化方法

AI-BasedOptimizationM第六章最近发展起来的新算法一.蚁群优化ACO二.粒子群优化三.其它新方法四.我们的工作：群落选址算法52第六章最近发展起来的新算法一.蚁群优化ACO2蚁群优化的产生 蚁群优化AntColonyOptimization在1995-1996年，Dorigo(Italy)提出ACO基本思想 模拟蚂蚁选择路线的能力。即：蚂蚁以信息素的强度为概率来决定路线选择。一.蚁群优化（1）53蚁群优化的产生一.蚁群优化（1）3ACO整体往往大于部分的“简单和”蚂蚁的低智能——蚁群的高智慧蚂蚁的简单行为——蚁群的智能突现实际蚁群的觅食1、主体（agent)：蚂蚁2、简单的规则（rules）：分工、通讯3、相互作用（interaction）： 蚂蚁<==触角放电==>蚂蚁蚂蚁<==气味积累==>环境54ACO整体往往大于部分的“简单和”4ACO观察实际蚁群的觅食1：55ACO观察实际蚁群的觅食1：5ACO观察实际蚁群的觅食2：

用障碍物切断原来的通路56ACO观察实际蚁群的觅食2：用障碍物切断原来的通路6ACO观察实际蚁群的觅食3：

搜索新路57ACO观察实际蚁群的觅食3：搜索新路7ACO观察实际蚁群的觅食4：最佳路径形成58ACO观察实际蚁群的觅食4：最佳路径形成8ACO的基本计算公式 ACO最早用来解决TSP问题一.蚁群优化（2）蚂蚁标号迭代次数信息素的影响59ACO的基本计算公式一.蚁群优化（2）蚂蚁标号迭代次数信息素一.蚁群优化（3）60一.蚁群优化（3）10举例说明一.蚁群优化（4）1534261举例说明一.蚁群优化（4）1534211信息素强度的计算一.蚁群优化（5）蚂蚁k的巡回长度常量所有蚂蚁留下的信息信息素增量遗忘因子62信息素强度的计算一.蚁群优化（5）蚂蚁k的巡回长度常量所有蚂ACO的基本算法步骤初始化令S=1,(S是tabu表的指标，即走过的城市数)将所有的初始城市记入一.蚁群优化（6）63ACO的基本算法步骤一.蚁群优化（6）13重复以下步骤，直到tabu表填满（所有城市 走过）。令S=S+1,对k=1到m个城市，以选择城市j移动，将j加入。对

（计算信息素，理解为每个蚂蚁在路径(i,j)上留下的总气味）一.蚁群优化（7）64重复以下步骤，直到tabu表填满（所有城市一.蚁群优化（7）对若NC大于 停止，否则转②，并清空tabu表一.蚁群优化（8）65对一.蚁群优化（8）15粒子群优化（ParticleSwarmOptimization）PSO的产生1995年，Kennedy&Eberhart提出PSOPSO已经成为当今的热门2003年，《控制与决策》第二期刊登国内第一篇PSO论文——综述文章二.粒子群优化（1）66粒子群优化（ParticleSwarmOptimizatPSO的基本思想 模仿鸟群的飞行，觅食行为特征（用Swarm仿真软件仿真）保持惯性按自身的最优修正方向按群体的最优修正方向二.粒子群优化（2）67PSO的基本思想二.粒子群优化（2）17PSO的特点 公式简单，待定系数少，可用来解实优化二.粒子群优化（3）68PSO的特点二.粒子群优化（3）18PSO的基本公式二.粒子群优化（4）过去的方向个体最优方向，第d个分量群体最优方向69PSO的基本公式二.粒子群优化（4）过去的方向个体最优方向其中：二.粒子群优化（5）70其中：二.粒子群优化（5）20PSO的计算步骤初始化粒子群，给予随机的位置和速度评估每个粒子的适应值 （目标函数值）对每个粒子，更新历史最优位置对群体更新历史最好解二.粒子群优化（6）71PSO的计算步骤二.粒子群优化（6）21对所有粒子计算若达到最大迭代数停止，否则转② 以上就是PSO最早最初始的经典算法，以后有多种改进。二.粒子群优化（7）72对所有粒子计算二.粒子群优化（7）22文化算法（CultureAlgorithm）文化算法的基本思想： 借鉴不同文化的相互排斥的特性，用到进化算法中。三.其它新方法（1）73文化算法（CultureAlgorithm）三.其它新方掠夺搜索策略（PSS）掠夺搜索策略的基本思想： 模仿猛兽的捕食策略（广域与邻域有效结合起来）。三.其它新方法（2）74掠夺搜索策略（PSS）三.其它新方法（2）24人工生命算法人工生命算法的基本思想： 模仿生态环境中多种种群的相互作用。三.其它新方法（3）75人工生命算法三.其它新方法（3）25ALA食物链：（来自生物学的解释）生产者所固有的能量和物质，通过一系列取食和被食的关系在生态系统中传递，各种生物按其食物关系排列的链状顺序称为食物链（foodchain)。简单的生物链（下图所示）76ALA食物链：（来自生物学的解释）26食物链模式的人工生命算法思想定义食物链:Resource：Artificialorganism说明：1、定义了四种资源：ResourceB,W,R和G；2、定义四种生物：Blue,white，Red和Green；3、定义它们之间的取食关系：White生物吃蓝色资源，白色废物；White白色废物，成为红色生物的资源。其他，依次类推。Resource(B)Resource(G)Resource(R)Resource(W)WhiteRedGreenBlue

White生物吃蓝色资源，产生白色废物

White白色废物，成为红色生物的资源77食物链模式的人工生命算法思想:Resource：ArtifiALA算法描述：Step1:初始化（initalization）产生四种相等数量的人工生物，并随机的布置在人工环境之中；每种人工生物的初始能量是Ie；产生四种相等数量的资源随机的布置在人工环境之中；设定最大代数。Step2:寻找资源（searchresource)人工生物在它们的邻域内，从当前位置寻找离它最近的资源78ALA算法描述：28ALAStep3：移动时使用优值保留策略（elitereservationstrategy）：首先，如果它们发现它们想吃的最近的资源在它们的邻域内，它们就移向它；其次，如果不是这样，它们就随机的在它们的邻域内移动；当随机移动时，采用优值保留策略即：如果人工生物有高的适值，那么它们移动最小的距离，以便仅轻微的改变适值，并甚至得到能量Ee。因此具有更高适值的生物有更多的机会生存。79ALAStep3：移动时使用优值保留策略（eliteresALAStep4:新陈代谢（Metabolism）：如果人工生物发现最近的资源正是它们想要的吃的（Metabolism），它们就吃了它，并得到能量Ge，并随机的产生废物在邻域内。Step5:年龄增长（aging）在这个过程中，每个生物的年龄增加1。Step6：复制（reproduction）如果生物年龄达到了Ra，并且能量>=Re，它将和最近的同种的同样满足上述条件的生物交配。规则如下：例如：A，B都满足年龄达到了Ra，并且能量>=Re，它们依据概率Rp来决定是复制它们自己(clone)还是交配(mate)。80ALAStep4:新陈代谢（Metabolism）：30ALAStep7:减少能量（ReduceEnergy）：所有的生物将减少能量Le。如果某个人工生物的能量少有Ld，则它将死掉，同时从人工环境中移走。Step8:增长代数（Increasinggenernation）：代数增加1；如果代数小于结束的代数，返回Step2；否则结束计算。81ALAStep7:减少能量（ReduceEnergy）ALA韩国学者Bo-SukYang等人在《Optimumdesignofshortjournalbearingsbyartificiallifealgorithm》一文中，应用该算法进行短经向轴承的优化设计。82ALA韩国学者Bo-SukYang等人在《Optimum四.我们的工作：群落选址算法

ColonyLocationAlgorithm(CLA)基本思想模拟植物群落形成机制－－土地含有的适于植物生长营养成分；不同物种间对生存资源的竞争；人工干预手段——施肥策略。83四.我们的工作：群落选址算法

ColonyLoc