自然计算及群体智能

自然计算及群体智能2自然计算与群体智能赵林亮计算机应用技术研究所[e-mail]3创新：向大自然学习•生物体、自然生态系统•通过自身演化解决优化问题•模拟自然生态系统求解复杂优化问题•仿生优化算法–遗传算法–蚁群算法–微粒群算法–人工免疫算法–人工鱼群算法–混合蛙跳算法4•遗传算法(GA)–物竞天择，设计染色体编码，交配突变与适应函数的萃取，优化求解•神经网络(ANN)–模彷生物神经元，透过神经元的讯息传递、训练学习、回溯，优化求解•模拟退火演算法(SA)–模彷金属退火过程•基因表达式编程5•基因DNA67神经网络89昆虫•蚁，蜂1011•蚁群算法•AntColonyOptimization(ACO)12鸟群算法•ParticleSwarmOptimization•有个带头鸟13•设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。•PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索•PSO初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest.另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。14•鱼群算法•FishSwarmOptimization15•蜂群算法MarriageinHoneyBeesOptimization(MBO)16•禁忌搜索（tabusearch）•模拟退火（simulatedannealing）•遗传算法（geneticalgorithms）•神经网络（neuralnetworks）•蚁群算法（群体（群集）智能，SwarmIntelligence）•拉格朗日松弛算法（lagrangean）•蜜蜂算法–飞姿传信，圈轴方向：蜜向，飞行圈数：距离17被模拟对象的智能层次•昆虫（低智能）–蜜蜂、蚂蚁——蜂群算法，蚁群算法•脊椎动物门（较低智能）–鱼群、鸟群——鱼群算法，鸟群算法，PSO•遗传算法家族（模拟生物界基本性质，中智能）•GA,GP••GEP基因表达式编程•GEP–变异和杂交=PSO18AI上这一特殊分支的发展历史GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence19891969ExpertSystem1953SimulatedAnnealing模拟退火19GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence198919691969ExpertSystem专家系统AI上这一特殊分支的发展历史20TabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence19891969ExpertSystem1975遗传算法GeneticAlgorithmAI上这一特殊分支的发展历史21GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization199519891969ExpertSystem1989SwarmIntelligence•群体智能TabuSearchAI上这一特殊分支的发展历史22GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization199519891969ExpertSystem1991SwarmIntelligence•蚁群算法AntsSystemAI上这一特殊分支的发展历史23GeneticAlgorithmTabuSearch195319911975AntsSystem199519891969ExpertSystem1995ParticleSwarmOptimization粒子群优化算法AI上这一特殊分支的发展历史24•出版社：人民邮电出版社•作者：[美]JamesKennedy/RussellC.Eberhart/YuhuiShi/•2009年2月第1版第1次印刷25几本相关的中文书26蚁群优化算法AntColonyAlgorithm(ACA)27参考文献APPEAREDINPROCEEDINGSOFECAL91-EUROPEANCONFERENCEONARTIFICIALLIFE,PARIS,FRANCE,ELSEVIERPUBLISHING,134–142.DistributedOptimizationbyAntColoniesAlbertoColorni,MarcoDorigo,VittorioManiezzoDipartimentodiElettronica,PolitecnicodiMilanoPiazzaLeonardodaVinci32,20133Milano,ItalyIEEETransactionsonSystems,Man,AndCybernetics-PartB:Cybernetics,Vol.26,No.1,Feb1996.29-41AntSystem:OptimizationbyaColonyofCooperatingAgentsMarcoDorigo,Member,IEEE,VittorioManiezzo,andAlbertoColorni~mdorigo/HomePageDorigo/28对蚂蚁的观察•单只蚂蚁智能不高;没有集中的指挥•无所作为•蚁群，复杂的社会行为：–协同工作–筑巢、觅食、迁徙、清扫蚁巢、抚养后代–依靠群体能力发挥出超出个体的智能29蚁群算法特点•模拟蚂蚁群体智能行为的仿生优化算法•较强的鲁棒性•优良的分布式计算机制•易于与其它方法结合30蚂蚁的生物学特征•别称：玄驹、蚍蜉、状元子•属节肢动物门，昆虫纲，膜翅目，蚁科•在昆虫界种类最多，生存量最大•约260属，16000多种，已命名的9000多种•拖动1400自重的食物•举起自重400倍的物体•起源于1亿年前的恐龙时代31蚂蚁的社会形态•蚁后、雄蚁、工蚁、兵蚁•信息交流方式：化学通信•分泌化学刺激物：信息素(pheromone)•彼此平等，利他主义•个体协作，协调一致•共和国32蚂蚁的群体行为•蚂蚁个体简单•群体：高度机构化的社会组织•远超蚂蚁个体能力•行为1：觅食–食物随机散布–找到一条蚁巢到食物源的最佳路径–适应环境变化：出现障碍–方法：蚁过留素（雁过留声），闻素而跟–信息正反馈33良性循环：路好（有食且近）蚁多信息素多蚁多…..（随时会蒸发掉一部分），开始：信息素浓度路短素浓。34良性循环如何进行？符号和假定：路径上的信息素浓度记为X蚂蚁均匀释放信息素，dx/dt=常数蚁穴A，食物源C，路径1：AC，路径2：ABC等边三角形ABC找到食物，沿原路返回BAC35良性循环如何进行？蚂蚁M1：AC，蚂蚁M2：ABC找到食物（分布、并行），沿原路返回AC比ABC短，M1回到A点时，M2才到C点。AC上蚁气：两次信息素叠加（去-回）AB路只有去一次信息素X(AC)X(ABC)，下一只蚂蚁：选择路径ACAC上信息素越来越多，进入良性循环BAC36Fig.1.Anexamplewithrealantsa)AntsfollowapathbetweenpointsAandE.b)Anobstacleisinterposed;antscanchoosetogoarounditfollowingoneofthetwodifferentpathswithequalprobability.c)Ontheshorterpathmorepheromoneislaiddown.37Fig.2.Anexamplewithartificialantsa)Theinitialgraphwithdistances.b)Attimet=0thereisnotrailonthegraphedges;therefore,antschoosewhethertoturnrightorleftwithequalprobability.c)Attimet=1trailisstrongeronshorteredges,whicharetherefore,intheaverage,preferredbyants.38要点•蚂蚁群居群动，很少有独行侠，•选择信息素浓的路径，喜欢热闹，•追求蚁气（人气）•人也类似。•两家饭店，一家热热火火，一家门可罗雀，选哪家？•选登山旅游线，一般人选人气多的（信息素浓的）•信息素启发性知识：人气高的，自有其优点•饭店请名人写诗歌作画、写对联，留下信息素•商业”托”,假造信息素•优势：并行+分布+信息素•70%选红火的，•不一定每人是这样•称为按概率.0.7选红火的39双桥实验(GossS,1989)Naturwissenschaften76,579-581(1989)Self-organizedShortcutsintheArgentineAntS.Goss,S.Aron,J.L.Deneubourg,andJ.M.PasteelsUnitofBehaviouralEcology,C.P.231,Universit6LibredeBruxelles,B-1050Bruxelles40Fig.1.AcolonyofIhumilisselectingtheshortbranchesonbothmodulesofthebridgea)onemoduleofthebridgeb)andc):photostaken4and8minafterplacementofthebridge41双桥实验数学模型()()()()hAAhhABmkPmmkmk假设条件：1、非对称桥上的信息量与过去一个时间段内经过该桥的蚂蚁数目成正比；2、某一时刻蚂蚁按照桥上残留的信息量多少来选择其中某座桥3、经过该桥的蚂蚁数目越多则桥上的残留信息量就越大设短桥为A，长桥为B，mA和mB分别表示经过桥A和桥B的蚂蚁数目mA+mB=m当所有m只蚂蚁都经过两座桥之后，第m+1只蚂蚁选择桥A的概率为：而选择桥B的概率为：()1()BAPmPm42•参数h和k用以匹配真实实验数据•第m+1只蚂蚁首先计算•然后生成一个在区间[0,1]上均匀分布的随机数•若，则选择桥A，否则选择桥B()APm()APm()APm43发展•意大利学者MDorigo，Vmaniezzo和AColorni•20世纪90年代：蚂蚁系统（antsystem，AS）•求解旅行商问题（TravelingSalesmanProblem，简称TSP）•90年代中期，用于广泛领域，取得成果•MDorigo发展为优化技术-蚁群优化•（AntColonyOptimization，简称ACO）•WJGutjahr：ACO的收敛性•用于合优化，函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由44ACO国际研讨会•ACO国际研讨会•1998、2000年、2002年、2004年，2006年，比利时布鲁塞尔大学45基本蚁群算法的数学模型46P、NP