智能控制系统五自然计算及群体智能

智能控制系统五自然计算及群体智能1第1页，共52页，2023年，2月20日，星期五创新：向大自然学习生物体、自然生态系统通过自身演化解决优化问题模拟自然生态系统求解复杂优化问题仿生优化算法遗传算法蚁群算法微粒群算法人工免疫算法人工鱼群算法混合蛙跳算法2第2页，共52页，2023年，2月20日，星期五遗传算法(GA)物竞天择，设计染色体编码，交配突变与适应函数的萃取，优化求解神经网络(ANN)模彷生物神经元，透过神经元的讯息传递、训练学习、回溯，优化求解模拟退火演算法(SA)模彷金属退火过程基因表达式编程3第3页，共52页，2023年，2月20日，星期五基因DNA4第4页，共52页，2023年，2月20日，星期五5第5页，共52页，2023年，2月20日，星期五神经网络6第6页，共52页，2023年，2月20日，星期五7第7页，共52页，2023年，2月20日，星期五昆虫蚁，蜂8第8页，共52页，2023年，2月20日，星期五9第9页，共52页，2023年，2月20日，星期五蚁群算法AntColonyOptimization(ACO)10第10页，共52页，2023年，2月20日，星期五鸟群算法ParticleSwarmOptimization有个带头鸟11第11页，共52页，2023年，2月20日，星期五鱼群算法FishSwarmOptimization12第12页，共52页，2023年，2月20日，星期五蜂群算法

MarriageinHoneyBeesOptimization(MBO)13第13页，共52页，2023年，2月20日，星期五禁忌搜索（tabusearch）模拟退火（simulatedannealing）遗传算法（geneticalgorithms）神经网络（neuralnetworks）蚁群算法（群体（群集）智能，SwarmIntelligence）拉格朗日松弛算法（lagrangean）蜜蜂算法飞姿传信，圈轴方向：蜜向，飞行圈数：距离14第14页，共52页，2023年，2月20日，星期五被模拟对象的智能层次昆虫（低智能）蜜蜂、蚂蚁——蜂群算法，蚁群算法脊椎动物门（较低智能）鱼群、鸟群——鱼群算法，鸟群算法，PSO遗传算法家族（模拟生物界基本性质，中智能）

GA,GP

GEP基因表达式编程

GEP–变异和杂交=PSO15第15页，共52页，2023年，2月20日，星期五AI上这一特殊分支的发展历史GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence19891969ExpertSystem1953SimulatedAnnealing模拟退火16第16页，共52页，2023年，2月20日，星期五GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence198919691969ExpertSystem专家系统AI上这一特殊分支的发展历史17第17页，共52页，2023年，2月20日，星期五TabuSearch195319911975AntsSystemParticleSwarmOptimization1995SwarmIntelligence19891969ExpertSystem1975

遗传算法GeneticAlgorithmAI上这一特殊分支的发展历史18第18页，共52页，2023年，2月20日，星期五GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization199519891969ExpertSystem1989SwarmIntelligence群体智能TabuSearchAI上这一特殊分支的发展历史19第19页，共52页，2023年，2月20日，星期五GeneticAlgorithmTabuSearch195319911975AntsSystemParticleSwarmOptimization199519891969ExpertSystem1991SwarmIntelligence蚁群算法AntsSystemAI上这一特殊分支的发展历史20第20页，共52页，2023年，2月20日，星期五GeneticAlgorithmTabuSearch195319911975AntsSystem199519891969ExpertSystem1995ParticleSwarmOptimization粒子群优化算法AI上这一特殊分支的发展历史21第21页，共52页，2023年，2月20日，星期五出版社：人民邮电出版社作者：[美]JamesKennedy/RussellC.Eberhart/YuhuiShi/2009年2月第1版第1次印刷22第22页，共52页，2023年，2月20日，星期五几本相关的中文书23第23页，共52页，2023年，2月20日，星期五蚁群优化算法AntColonyAlgorithm(ACA)24第24页，共52页，2023年，2月20日，星期五参考文献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,andAlbertoColornihttp://iridia.ulb.ac.be/~mdorigo/HomePageDorigo/25第25页，共52页，2023年，2月20日，星期五对蚂蚁的观察单只蚂蚁智能不高;没有集中的指挥无所作为蚁群，复杂的社会行为：协同工作筑巢、觅食、迁徙、清扫蚁巢、抚养后代依靠群体能力发挥出超出个体的智能26第26页，共52页，2023年，2月20日，星期五蚁群算法特点模拟蚂蚁群体智能行为的仿生优化算法较强的鲁棒性优良的分布式计算机制易于与其它方法结合27第27页，共52页，2023年，2月20日，星期五蚂蚁的生物学特征别称：玄驹、蚍蜉、状元子属节肢动物门，昆虫纲，膜翅目，蚁科

在昆虫界种类最多，生存量最大约260属，16000多种，已命名的9000多种拖动1400自重的食物举起自重400倍的物体起源于1亿年前的恐龙时代28第28页，共52页，2023年，2月20日，星期五蚂蚁的社会形态蚁后、雄蚁、工蚁、兵蚁信息交流方式：化学通信分泌化学刺激物：信息素(pheromone)彼此平等，利他主义个体协作，协调一致共和国29第29页，共52页，2023年，2月20日，星期五蚂蚁的群体行为蚂蚁个体简单群体：高度机构化的社会组织远超蚂蚁个体能力行为1：觅食食物随机散布找到一条蚁巢到食物源的最佳路径适应环境变化：出现障碍方法：蚁过留素（雁过留声），闻素而跟信息正反馈30第30页，共52页，2023年，2月20日，星期五良性循环：路好（有食且近）蚁多信息素多蚁多…..（随时会蒸发掉一部分），开始：信息素浓度路短素浓。31第31页，共52页，2023年，2月20日，星期五良性循环如何进行？符号和假定：路径上的信息素浓度记为X蚂蚁均匀释放信息素，dx/dt=常数蚁穴A，食物源C，路径1：AC，路径2：ABC等边三角形ABC找到食物，沿原路返回BAC32第32页，共52页，2023年，2月20日，星期五良性循环如何进行？蚂蚁M1：AC，蚂蚁M2：ABC

找到食物（分布、并行），沿原路返回AC比ABC短，M1回到A点时，M2才到C点。AC上蚁气：两次信息素叠加（去-回）AB路只有去一次信息素X(AC)>X(ABC)，下一只蚂蚁：选择路径ACAC上信息素越来越多，进入良性循环BAC33第33页，共52页，2023年，2月20日，星期五Fig.1.Anexamplewithrealantsa)AntsfollowapathbetweenpointsAandE.b)Anobstacleisinterposed;antscanchoosetogoarounditfollowingoneofthetwodifferentpathswithequalprobability.c)Ontheshorterpathmorepheromoneislaiddown.34第34页，共52页，2023年，2月20日，星期五Fig.2.Anexamplewithartificialantsa)Theinitialgraphwithdistances.b)Attimet=0thereisnotrailonthegraphedges;therefore,antschoosewhethertoturnrightorleftwithequalprobability.c)Attimet=1trailisstrongeronshorteredges,whicharetherefore,intheaverage,preferredbyants.35第35页，共52页，2023年，2月20日，星期五要点蚂蚁群居群动，很少有独行侠，选择信息素浓的路径，喜欢热闹，追求蚁气（人气）人也类似。

两家饭店，一家热热火火，一家门可罗雀，选哪家？选登山旅游线，一般人选人气多的（信息素浓的）信息素启发性知识：人气高的，自有其优点饭店请名人写诗歌作画、写对联，留下信息素商业”托”,假造信息素优势：并行+分布+信息素70%选红火的，不一定每人是这样称为按概率.0.7选红火的36第36页，共52页，2023年，2月20日，星期五双桥实验(GossS,1989)Naturwissenschaften76,579-581(1989)Self-organizedShortcutsintheArgentineAntS.Goss,S.Aron,J.L.Deneubourg,andJ.M.PasteelsUnitofBehaviouralEcology,C.P.231,Universit6LibredeBruxelles,B-1050Bruxelles37第37页，共52页，2023年，2月20日，星期五Fig.1.AcolonyofIhumilisselectingtheshortbranchesonbothmodulesofthebridgea)onemoduleofthebridgeb)andc):photostaken4and8minafterplacementofthebridge38第38页，共52页，2023年，2月20日，星期五双桥实验数学模型假设条件：1、非对称桥上的信息量与过去一个时间段内经过该桥的蚂蚁数目成正比；2、某一时刻蚂蚁按照桥上残留的信息量多少来选择其中某座桥3、经过该桥的蚂蚁数目越多则桥上的残留信息量就越大设短桥为A，长桥为B，mA和mB分别表示经过桥A和桥B的蚂蚁数目

mA+mB=m当所有m只蚂蚁都经过两座桥之后，第m+1只蚂蚁选择桥A的概率为：而选择桥B的概率为：39第39页，共52页，2023年，2月20日，星期五参数h和k用以匹配真实实验数据第m+1只蚂蚁首先计算然后生成一个在区间[0,1]上均匀分布的随机数若，则选择桥A，否则选择桥B40第40页，共52页，2023年，2月20日，星期五发展意大利学者MDorigo，Vmaniezzo和AColorni20世纪90年代：蚂蚁系统（antsystem，AS）求解旅行商问题（TravelingSalesmanProblem，简称TSP）90年代中期，用于广泛领域，取得成果MDorigo发展为优化技术-蚁群优化（AntColonyOptimization，简称ACO）WJGutjahr：ACO的收敛性用于合优化，函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由41第41页，共52页，2023年，2月20日，星期五ACO国际研讨会ACO国际研讨会

1998、2000年、2002年、2004年，2006年，比利时布鲁塞尔大学42第42页，共52页，2023年，2月20日，星期五基本蚁群算法的数学模型43第43页，共52页，2023年，2月20日，星期五P、NP、NP-C、NP-hard问题P类问题所有可用DTM(Deterministicone-tapeTuringMachine)在多项式时间内求解的判定问题Π的集合。简记为O(p(n))即P={L:存在一个多项式时间DTM程序M，是的L=LM},其中LM表示程序M所识别的语言。若存在一个多项式时间DTM程序，它在编码策略e之下求解判定问题Π，即L[Π,e]∈P,则称该判定问题属于P类问题。44第44页，共52页，2023年，2月20日，星期五P、NP、NP-C、NP-hard问题NP类问题(Non-deterministicPolynomial)若存在一个多项式函数g(x)和一个验证算法H,对一类判定问题A的任何一个“是”回答，满足其输入长度d(s)不超过g(d(I)),其中d(I)为I的输入长度，且验证算法中S为I的“是”回答的计算时间不超过g(d(I)),则称判定问题A为非多项式确定问题。NP类问题是所有可用NDTM(Non-Deterministicone-tapeTuringMachine)在多项式时间内求解的判定问题Π的集合45第45页，共52页，2023年，2月20日，星期五P、NP、NP-C、NP-hard问题NP-C类问题(NP-Complete)是NP类中最困难的一类问题。有重要实际意义和工程背景TSP(TravelingSalesmanProblem)Symmetric;AsymmetricNP-hard类问题NP-CNP-hardNPPNP-hardNP-C46第46页，共52页，2023年，2月20日，星期五基本蚁群算法模型基本假设蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对周围的局部环境产生影响；蚂蚁对环境的反应由其内部模式决定。即蚂蚁是反应型适应性主体在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。47第47页，共52页，2023年，2月20日，星期五TSP(TravelingSalesmanProblem)有向图有向图D的三元组为(V,E,f)，其中V是一个非空集合，其元素称为有向图的结点；E是一个集合，其元素称为有向图的弧段（边）；f是从E到VxV上的一个映射（函数）。E中的元素总是和V中的序偶对有对应关系，可用V中的序偶代替E中的元素。一个有向图Ｄ可简记为(V,E).48第48页，共52页，2023年，2月20日，星期五TSP(TravelingSalesmanProblem)TSP设C={c