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

智能优化方法

AI-BasedOptimizationMethodsByProfessorDingweiWangNortheasternUniversityChina20041第六章最近开展起来的新算法一.蚁群优化ACO二.粒子群优化三.其它新方法四.我们的任务：群落选址算法2蚁群优化的产生 蚁群优化AntColonyOptimization在1995-1996年，Dorigo(Italy)提出ACO根本思想 模拟蚂蚁选择道路的才干。即：蚂蚁以信息素的强度为概率来决议道路选择。一.蚁群优化〔1〕3ACO整体往往大于部分的“简单和〞蚂蚁的低智能——蚁群的高智慧蚂蚁的简单行为——蚁群的智能突现实践蚁群的寻食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的根本算法步骤初始化令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论文——综述文章二.粒子群优化〔1〕16PSO的根本思想 模拟鸟群的飞行，寻食行为特征〔用Swarm仿真软件仿真〕坚持惯性按本身的最优修正方向按群体的最优修正方向二.粒子群优化〔2〕17PSO的特点 公式简单，待定系数少，可用来解实优化二.粒子群优化〔3〕18PSO的根本公式二.粒子群优化〔4〕过去的方向个体最优方向，第d个分量群体最优方向19其中：二.粒子群优化〔5〕20PSO的计算步骤初始化粒子群，给予随机的位置和速度评价每个粒子的顺应值 〔目的函数值〕对每个粒子，更新历史最优位置对群体更新历史最好解二.粒子群优化〔6〕21对一切粒子计算假设到达最大迭代数停顿，否那么转② 以上就是PSO最早最初始的经典算法，以后有多种改良。二.粒子群优化〔7〕22文化算法〔CultureAlgorithm〕文化算法的根本思想： 自创不同文化的相互排斥的特性，用到进化算法中。三.其它新方法〔1〕23掠夺搜索战略〔PSS〕掠夺搜索战略的根本思想： 模拟猛兽的捕食战略〔广域与邻域有效结合起来〕。三.其它新方法〔2〕24人工生命算法人工生命算法的根本思想： 模拟生态环境中多种种群的相互作用。三.其它新方法〔3〕25ALA食物链：〔来自生物学的解释〕消费者所固有的能量和物质，经过一系列取食和被食的关系在生态系统中传送，各种生物按其食物关系陈列的链状顺序称为食物链〔foodchain)。简单的生物链〔以下图所示〕26食物链方式的人工生命算法思想定义食物链: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〕产生四种相等数量的人工生物，并随机的布置在人工环境之中；每种人工生物的初始能量是Ie；产生四种相等数量的资源随机的布置在人工环境之中；设定最大代数。Step2:寻觅资源〔searchresource)人工生物在它们的邻域内，从当前位置寻觅离它最近的资源28ALAStep3：挪动时运用优值保管战略〔elitereservationstrategy〕：首先，假设它们发现它们想吃的最近的资源在它们的邻域内，它们就移向它；其次，假设不是这样，它们就随机的在它们的邻域内挪动；当随机挪动时，采用优值保管战略即：假设人工生物有高的适值，那么它们挪动最小的间隔，以便仅细微的改动适值，并甚至得到能量Ee。因此具有更高适值的生物有更多的时机生存。29ALAStep4:新陈代谢〔Metabolism〕：假设人工生物发现最近的资源正是它们想要的吃的〔Metabolism〕，它们就吃了它，并得到能量Ge，并随机的产生废物在邻域内。Step5:年龄增长〔aging〕在这个过程中，每个生物的年龄添加1。Step6：复制〔reproduction〕假设生物年龄到达了Ra，并且能量>=Re，它将和最近的同种的同样满足上述条件的生物交配。规那么如下：例如：A，B都满足年龄到达了Ra，并且能量>=Re，它们根据概率Rp来决议是复制它们本人(clone)还是交配(mate)。30ALAStep7:减少能量〔ReduceEnergy〕：一切的生物将减少能量Le。假设某个人工生物的能量少有Ld，那么它将死掉，同时从人工环境中移走。Step8:增长代数〔Increasinggenernation〕：代数添加1；假设代数小于终了的代数，前往Step2；否那么终了计算。31ALA韩国学者Bo-SukYang等人在<Optimumdesignofshortjournalbearingsbyartificiallifealgorithm>一文中，运用该算法进展短经向轴承的优化设计。32四.我们的任务：群落选址算法

ColonyLocationAlgorithm(CLA)根本思想模拟植物群落构成机制－－土地含有的适于植物生长营养成分；不同物种间对生存资源的竞争；人工干涉手段——施肥战略。33CLA营养函数Nij(t):在t时辰，土地j对群落i的营养。加上时间t，是由于施肥可以改动肥力。对于指派问题，A为任务时间，〔极小化〕Nij(t)＝1／aij,即可。对于TSP，Nij(t)＝1／dij,即可。对于QAP，怎样设？34CLA生长率与衰亡率生长率：r是平均生长率，是一切土地对i的平均肥力。〔行均值〕35衰亡率：是土地j对一切群落的肥力的均值。〔列均值〕CLA36CLA群落比例与归一化设xij(t)是群落i在土地j上的比例；生长过程带来比例的和不是1。行、列归一化，反复进展。37生长过程CLA38CLA解的构成与评价xij(t)不是解。以xij(t)为概率，在每块土地上产生一个群落，问题是要保证一个群落不能同时在两块土地上—解的合法性。其实很简单，按随机顺序，在剩余群落中选。39CLA施肥过程假设S(k*)是最好解；或者40CLA解的信息熵的计算解的信息熵：41CLA停顿判据停顿准那么的计算：42