AAI51自然计算及群体智能汇总课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,AAI51自然计算及群体智能,AAI51自然计算及群体智能,创新：向大自然学习,生物体、自然生态系统,通过自身演化解决优化问题,模拟自然生态系统求解复杂优化问题,仿生优化算法,遗传算法,蚁群算法,微粒群算法,人工免疫算法,人工鱼群算法,混合蛙跳算法,创新：向大自然学习生物体、自然生态系统,遗传算法(GA),物竞天择，设计染色体编码，交配 突变与适应函数的萃取，优化求解,神经网络(ANN),模彷生物神经元，透过神经元的讯息传递、训练学习、回溯，优化求解,模拟退火演算法(SA),模彷金属退火过程,基因表达式编程,遗传算法(GA),基因 DNA,基因 DNA,AAI51自然计算及群体智能汇总课件,神经网络,神经网络,AAI51自然计算及群体智能汇总课件,昆虫,蚁，蜂,昆虫,AAI51自然计算及群体智能汇总课件,蚁群算法,Ant Colony Optimization (ACO,),蚁群算法,鸟群算法,Particle Swarm Optimization,有个 带头鸟,鸟群算法,鱼群算法,Fish,Swarm Optimization,鱼群算法,蜂群算法,Marriage in Honey Bees Optimization (MBO,),蜂群算法 Marriage in Honey Bees Op,禁忌搜索（tabu search）,模拟退火（simulated annealing）,遗传算法（genetic algorithms）,神经网络（neural networks）,蚁群算法（群体（群集）智能，Swarm Intelligence）,拉格朗日松弛算法（lagrangean）,蜜蜂算法,飞姿传信，圈轴方向：蜜向，飞行圈数：距离,禁忌搜索（tabu search）,被模拟对象的智能层次,昆虫,（低智能）,蜜蜂、蚂蚁,蜂群算法，蚁群算法,脊椎动物门,（较低智能）,鱼群、鸟群,鱼群算法，鸟群算法，PSO,遗传算法家族,（模拟 生物界 基本性质，,中智能）,GA, GP,GEP 基因表达式编程,GEP 变异和杂交 = PSO,被模拟对象的智能层次昆虫（低智能）,AI上这一特殊分支的发展历史,Genetic Algorithm,Tabu Search,1953,1991,1975,Ants System,Particle Swarm Optimization,1995,Swarm Intelligence,1989,1969,Expert System,1953,Simulated Annealing,模拟退火,AI上这一特殊分支的发展历史Genetic Algorith,Genetic Algorithm,Tabu Search,1953,1991,1975,Ants System,Particle Swarm Optimization,1995,Swarm Intelligence,1989,1969,1969,Expert System,专家系统,AI上这一特殊分支的发展历史,Genetic AlgorithmTabu Search19,Tabu Search,1953,1991,1975,Ants System,Particle Swarm Optimization,1995,Swarm Intelligence,1989,1969,Expert System,1975,遗传算法,Genetic Algorithm,AI上这一特殊分支的发展历史,Tabu Search195319911975Ants Sy,Genetic Algorithm,Tabu Search,1953,1991,1975,Ants System,Particle Swarm Optimization,1995,1989,1969,Expert System,1989,Swarm Intelligence,群体智能,Tabu Search,AI上这一特殊分支的发展历史,Genetic AlgorithmTabu Search19,Genetic Algorithm,Tabu Search,1953,1991,1975,Ants System,Particle Swarm Optimization,1995,1989,1969,Expert System,1991,Swarm Intelligence,蚁群算法,Ants System,AI上这一特殊分支的发展历史,Genetic AlgorithmTabu Search19,Genetic Algorithm,Tabu Search,1953,1991,1975,Ants System,1995,1989,1969,Expert System,1995,Particle Swarm Optimization,粒子群优化算法,AI上这一特殊分支的发展历史,Genetic AlgorithmTabu Search19,出版社：人民邮电出版社,作者：美James Kennedy/ Russell C.Eberhart/ Yuhui Shi/,2009年2月第1版第1次印刷,出版社：人民邮电出版社,几本相关的中文书,几本相关的中文书,蚁群优化算法,Ant Colony Algorithm,(ACA),AAI51自然计算及群体智能汇总课件,参考文献,APPEARED IN PROCEEDINGS OF ECAL91-EUROPEAN CONFERENCE ON ARTIFICIAL LIFE, PARIS, FRANCE,ELSEVIER PUBLISHING,134142.,Distributed Optimization by Ant Colonies,Alberto Colorni, Marco Dorigo, Vittorio Maniezzo,Dipartimento di Elettronica, Politecnico di Milano,Piazza Leonardo da Vinci 32, 20133 Milano, Italy,IEEE Transactions on Systems, Man, And Cybernetics-,Part B: Cybernetics,Vol.26, No.1, Feb 1996. 29-41,Ant System: Optimization by a Colony of Cooperating Agents,Marco Dorigo, Member, IEEE, Vittorio Maniezzo, and Alberto Colorni,http:/iridia.ulb.ac.be/mdorigo/HomePageDorigo/,参考文献APPEARED IN PROCEEDINGS OF,对蚂蚁的观察,单只蚂蚁智能不高; 没有集中的指挥,无所作为,蚁群，复杂的社会行为：,协同工作,筑巢、觅食、迁徙、清扫蚁巢、抚养后代,依靠群体能力发挥出超出个体的智能,对蚂蚁的观察单只蚂蚁智能不高; 没有集中的指挥,蚁群算法特点,模拟蚂蚁群体智能行为的仿生优化算法,较强的鲁棒性,优良的分布式计算机制,易于与其它方法结合,蚁群算法特点模拟蚂蚁群体智能行为的仿生优化算法,蚂蚁的生物学特征,别称：玄驹、蚍蜉、状元子,属,节肢动物门,，,昆虫纲,，,膜翅目,，,蚁科,在昆虫界种类最多，生存量最大,约260属，16000多种，已命名的9000多种,拖动1400自重的食物,举起自重400倍的物体,起源于1亿年前的恐龙时代,蚂蚁的生物学特征别称：玄驹、蚍蜉、状元子,蚂蚁的社会形态,蚁后、雄蚁、工蚁、兵蚁,信息交流方式：化学通信,分泌化学刺激物：信息素 (pheromone),彼此平等，利他主义,个体协作，协调一致,共和国,蚂蚁的社会形态蚁后、雄蚁、工蚁、兵蚁,蚂蚁的群体行为,蚂蚁个体简单,群体：高度机构化的社会组织,远超蚂蚁个体能力,行为1：觅食,食物随机散布,找到一条蚁巢到食物源的最佳路径,适应环境变化：出现障碍,方法：蚁过留素（雁过留声），闻素而跟,信息正反馈,蚂蚁的群体行为蚂蚁个体简单,良性循环,：,路好（有食且近）,蚁多,信息素多,蚁多.,（随时 会蒸发掉一部分），,开始,： 信息素浓度 路短 素浓。,良性循环 ：,良性循环如何进行？,符号和假定：,路径上的信息素浓度记为 X,蚂蚁均匀释放信息素，dx/dt =常数,蚁穴A，食物源C，,路径1：A,C，,路径2：A,BC,等边三角形ABC,找到食物，沿原路返回,B,A,C,良性循环如何进行？符号和假定：路径上的信息素浓度记为 XBA,良性循环如何进行？,蚂蚁M1：A,C，蚂蚁,M2：A,BC,找到食物（分布、并行），沿原路返回,AC 比ABC短， M1回到A点时， M2 才到C点。,AC上蚁气 ：两次信息素叠加（去-回）,AB路只有去一次信息素,X(AC)X(ABC)，下一只蚂蚁：选择路径AC,AC上信息素越来越多，进入良性循环,B,A,C,良性循环如何进行？蚂蚁M1：AC，蚂蚁M2：ABC B,Fig. 1. An example with real ants,a) Ants follow a path between points A and E.,b) An obstacle is interposed; ants can choose to go around it following one of the two different paths with equal probability.,c) On the shorter path more pheromone is laid down.,Fig. 1. An example with real a,Fig. 2. An example with artificial ants,a) The initial graph with distances.,b) At time t=0 there is no trail on the graph edges; therefore, ants choose whether to turn right or left with equal probability.,c) At time t=1 trail is stronger on shorter edges, which are therefore, in the average, preferred by ants.,Fig. 2. An example with artifi,要点,蚂蚁群居群动，很少有独行侠，,选择,信息素浓的路径,， 喜欢热闹，,追求蚁气（人气）,人也类似。,两家饭店，一家热热火火，一家门可罗雀，选哪家？,选登山旅游线，一般人选人气多的（信息素浓的）,信息素启发性知识：人气高的，自有其优点,饭店请名人写诗歌作画、写对联，留下信息素,商业 ”托” , 假造信息素,优势： 并行+分布+信息素,70%选红火的，,不一定每人是这样,称为按概率.0.7选红火的,要点蚂蚁群居群动，很少有独行侠，70%选红火的，,双桥实验(Goss S, 1989),Naturwissenschaften 76, 579-581 (1989),Self-organized Shortcuts in the Argentine Ant,S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels,Unit of Behavioural Ecology, C.P. 231, Universit6 Libre de Bruxelles,B- 1050 Bruxelles,双桥实验(Goss S, 1989)Naturwissens,Fig. 1. A colony of,I humilis,selecting the short branches on both modules of the bridge,a) one module of the bridge,b) and c): photos taken 4 and 8 min after placement of the bridge,Fig. 1. A colony of I humilis,双桥实验数学模型,假设条件：,1、非对称桥上的信息量与过去一个时间段内经过该桥的蚂蚁数目成正比；,2、某一时刻蚂蚁按照桥上残留的信息量多少来选择其中某座桥,3、经过该桥的蚂蚁数目越多则桥上的残留信息量就越大,设短桥为A，长桥为B，m,A,和m,B,分别表示经过桥A和桥B的蚂蚁数目,m,A,+ m,B,= m,当所有m只蚂蚁都经过两座桥之后，第m+1只蚂蚁选择桥A的概率为：,而选择桥B的概率为：,双桥实验数学模型假设条件：设短桥为A，长桥为B，mA和mB分,参数h 和 k用以匹配真实实验数据,第m+1只蚂蚁首先计算,然后生成一个在区间0,1上均匀分布的随机数,若 ，则选择桥A，否则选择桥B,参数h 和 k用以匹配真实实验数据,发展,意大利学者M Dorigo，Vmaniezzo和A Colorni,20世纪90年代 ：蚂蚁系统（ant system，AS）,求解旅行商问题（Traveling Salesman Problem，简称TSP）,90年代中期，用于广泛领域，取得成果,M Dorigo 发展为优化技术-蚁群优化,（Ant Colony Optimization，简称ACO）,W J Gutjahr ：ACO的收敛性,用于合优化，函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由,发展意大利学者M Dorigo，Vmaniezzo和A Co,ACO国际研讨会,ACO国际研讨会,1998、2000年、2002年、2004年，2006年，比利时布鲁塞尔大学,ACO国际研讨会ACO国际研讨会,基本蚁群算法的数学模型,基本蚁群算法的数学模型,P、NP、NP-C、NP-hard问题,P类问题,所有可用DTM (Deterministic one-tape Turing Machine) 在多项式时间内求解的判定问题的集合。简记为O(p(n),即 P=L: 存在一个多项式时间DTM程序M，是的L=L,M, , 其中L,M,表示程序M所识别的语言。,若存在一个多项式时间DTM程序，它在编码策略e之下求解判定问题，即L, eP,则称该判定问题属于P类问题。,P、NP、NP-C、NP-hard问题P类问题,P、NP、NP-C、NP-hard问题,NP类问题,(Non-deterministic Polynomial),若存在一个多项式函数 g(x) 和一个验证算法H, 对一类判定问题A的任何一个“是”回答，满足其输入长度d(s)不超过g(d(I), 其中d(I)为I的输入长度，且验证算法中S为I的“是”回答的计算时间不超过g(d(I), 则称判定问题A为非多项式确定问题。,NP类问题是所有可用NDTM (Non-Deterministic one-tape Turing Machine)在多项式时间内求解的判定问题的集合,P、NP、NP-C、NP-hard问题NP类问题 (Non-,P、NP、NP-C、NP-hard问题,NP-C类问题,(NP-Complete),是NP类中最困难的一类问题。,有重要实际意义和工程背景,TSP (Traveling Salesman Problem),Symmetric; Asymmetric,NP-hard类问题,NP-C NP-hard,NP,P,NP-hard,NP-C,P、NP、NP-C、NP-hard问题NP-C类问题 (NP,基本蚁群算法模型,基本假设,蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对周围的局部环境产生影响；,蚂蚁对环境的反应由其内部模式决定。即蚂蚁是反应型适应性主体,在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。,基本蚁群算法模型基本假设,TSP (Traveling Salesman Problem),有向图,有向图D的三元组为 (V, E, f)，其中V是一个非空集合，其元素称为有向图的结点；E是一个集合，其元素称为有向图的弧段（边）；f是从E到VxV上的一个映射（函数）。,E中的元素总是和V中的序偶对有对应关系，可用V中的序偶代替E中的元素。,一个有向图可简记为(V, E).,TSP (Traveling Salesman Proble,TSP (Traveling Salesman Problem),TSP,设C=c1, c2, , cn 是n个城市的集合，,L=l,ij,|c,i, c,j,C是集合C中的元素（城市）两两连接的集合，,d,ij,(i, j=1,1,n)是l,ij,的Euclidean距离，即,G=(C, L)是一个有向图，TSP的目的是从有向图G中寻出长度最短的Hamilton圈，,即一条对C=c1, c2, , cn中n个元素（城市）访问且只访问一次的最短封闭曲线,TSP (Traveling Salesman Proble,TSP (Traveling Salesman Problem),TSP简单形象描述,给定n个城市，一个旅行商从某一城市出发，访问各城市一次且仅有一次后再回到原出发城市，要求找出一条最短的巡回路径,可分为对称TSP (Symmetric Traveling Salesman Problem) 和非对称TSP (Asymmetric Traveling Salesman Problem),TSP是NP-C问题,n城市规模的TSP，存在(n-1)!/2条不同闭合路径。,TSP (Traveling Salesman Proble,蚁群算法,时间,：20世纪90年代,地点,：,意大利,人物,： 意大利 MDorigo，VManiezzo，AColorni,目的,： 模拟自然界蚂蚁搜索路径的行为，,结果,： 群体智能理论,应用,： 求解NP问题 （TSP问题、分配问题、,job-shop调度问题），,解复杂优化问题（离散优化问题）有优势,蚁群算法时间：20世纪90年代,应用领域,解决大多数优化问题,或转化为优化求解的问题。,分类、聚类、模式识别、,多目标优化、,QoS,、,流程规划,信号处理,机器人控制、,决策支持,应用领域解决大多数优化问题,背景,群体智能理论包括：,微粒群算法，,Particle Swarm Optimization, PSO,鱼群 鸟群 追尾,蚁群算法(Ant Colony Optimization, ACO),简单社会系统的模拟,背景 群体智能理论包括：,蚁群优化算法研究背景,与传统进化算法-梯度算法的差异,：，,概率搜索,1,并行+分布 ，,无中控，,个别蚂蚁死亡 无关大局,2 因而程序,坚固,。,3 非直接,信息交流,，（广播）,4 可处理,离散,对象,5,实现简单,蚁群优化算法研究背景与传统进化算法-梯度算法的差异：，,实现简单,算法中仅涉及各种基本的数学操作，,对CPU和内存的要求不高。,只输出：目标函数值，,无需梯度信息。（导数，微分）,实现简单,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力,