AAI-5 1自然计算及群体智能

1、高级人工智能第一章 人工智能概述第二章 归结推理方法第三章 不确定性推理第四章 知识表达方法第五章 自然计算及群体智能蚁群算法第六章 自然计算及群体智能遗传算法1自然计算与群体智能赵林亮计算机应用技术研究所zhaoll2创新：向大自然学习生物体、自然生态系统通过自身演化解决优化问题模拟自然生态系统求解复杂优化问题仿生优化算法遗传算法蚁群算法微粒群算法人工免疫算法人工鱼群算法混合蛙跳算法3遗传算法(GA)物竞天择，设计染色体编码，交配 突变与适应函数的萃取，优化求解神经网络(ANN)模彷生物神经元，透过神经元的讯息传递、训练学习、回溯，优化求解模拟退火演算法(SA)模彷金属退火过程基因表达式编程

2、4基因 DNA56神经网络78昆虫蚁，蜂910蚁群算法Ant Colony Optimization (ACO)11鸟群算法Particle Swarm Optimization有个 带头鸟12设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值(fitness value)

3、，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索 PSO 初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest. 另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 13鱼群算法Fish Swarm Optimization14蜂群算法 Marriage in Honey Bees Optimization (MBO)15禁忌

4、搜索（tabu search）模拟退火（simulated annealing）遗传算法（genetic algorithms）神经网络（neural networks）蚁群算法（群体（群集）智能，Swarm Intelligence） 拉格朗日松弛算法（lagrangean）蜜蜂算法飞姿传信，圈轴方向：蜜向，飞行圈数：距离16被模拟对象的智能层次昆虫（低智能）蜜蜂、蚂蚁蜂群算法，蚁群算法脊椎动物门 （较低智能）鱼群、鸟群鱼群算法，鸟群算法，PSO遗传算法家族（模拟 生物界 基本性质，中智能） GA, GP GEP 基因表达式编程 GEP 变异和杂交 = PSO17AI上这一特殊分支的发展历史

5、Genetic AlgorithmTabu Search195319911975Ants SystemParticle Swarm Optimization1995Swarm Intelligence19891969Expert System1953 Simulated Annealing模拟退火18Genetic AlgorithmTabu Search195319911975Ants SystemParticle Swarm Optimization1995Swarm Intelligence198919691969 Expert System专家系统AI上这一特殊分支的发展历史19Tab

6、u Search195319911975Ants SystemParticle Swarm Optimization1995Swarm Intelligence19891969Expert System1975 遗传算法Genetic AlgorithmAI上这一特殊分支的发展历史20Genetic AlgorithmTabu Search195319911975Ants SystemParticle Swarm Optimization199519891969Expert System1989 Swarm Intelligence群体智能 Tabu SearchAI上这一特殊分支的发展历史2

7、1Genetic AlgorithmTabu Search195319911975Ants SystemParticle Swarm Optimization199519891969Expert System1991 Swarm Intelligence蚁群算法 Ants SystemAI上这一特殊分支的发展历史22Genetic AlgorithmTabu Search195319911975Ants System199519891969Expert System1995 Particle Swarm Optimization粒子群优化算法AI上这一特殊分支的发展历史23出版社：人民邮电出版

8、社作者：美James Kennedy/ Russell C.Eberhart/ Yuhui Shi/ 2009年2月第1版第1次印刷24几本相关的中文书25蚁群优化算法Ant Colony Algorithm(ACA)26参考文献APPEARED IN PROCEEDINGS OF ECAL91-EUROPEAN CONFERENCE ON ARTIFICIAL LIFE, PARIS, FRANCE,ELSEVIER PUBLISHING,134142.Distributed Optimization by Ant ColoniesAlberto Colorni, Marco Dorigo,

9、 Vittorio ManiezzoDipartimento di Elettronica, Politecnico di MilanoPiazza Leonardo da Vinci 32, 20133 Milano, ItalyIEEE Transactions on Systems, Man, And Cybernetics-Part B: Cybernetics,Vol.26, No.1, Feb 1996. 29-41Ant System: Optimization by a Colony of Cooperating AgentsMarco Dorigo, Member, IEEE

10、, Vittorio Maniezzo, and Alberto Colornihttp:/iridia.ulb.ac.be/mdorigo/HomePageDorigo/27对蚂蚁的观察单只蚂蚁智能不高; 没有集中的指挥 无所作为蚁群，复杂的社会行为：协同工作筑巢、觅食、迁徙、清扫蚁巢、抚养后代依靠群体能力发挥出超出个体的智能28蚁群算法特点模拟蚂蚁群体智能行为的仿生优化算法较强的鲁棒性优良的分布式计算机制易于与其它方法结合29蚂蚁的生物学特征别称：玄驹、蚍蜉、状元子属节肢动物门，昆虫纲，膜翅目，蚁科 在昆虫界种类最多，生存量最大约260属，16000多种，已命名的9000多种拖动1400自

11、重的食物举起自重400倍的物体起源于1亿年前的恐龙时代30蚂蚁的社会形态蚁后、雄蚁、工蚁、兵蚁信息交流方式：化学通信分泌化学刺激物：信息素 (pheromone)彼此平等，利他主义个体协作，协调一致共和国31蚂蚁的群体行为蚂蚁个体简单群体：高度机构化的社会组织远超蚂蚁个体能力行为1：觅食食物随机散布找到一条蚁巢到食物源的最佳路径适应环境变化：出现障碍方法：蚁过留素（雁过留声），闻素而跟信息正反馈32良性循环 ： 路好（有食且近）蚁多信息素多蚁多.（随时 会蒸发掉一部分），开始： 信息素浓度 路短 素浓。33良性循环如何进行？符号和假定：路径上的信息素浓度记为 X蚂蚁均匀释放信息素，dx/dt

12、=常数蚁穴A，食物源C，路径1：AC，路径2：ABC等边三角形ABC找到食物，沿原路返回BAC34良性循环如何进行？蚂蚁M1：AC，蚂蚁M2：ABC 找到食物（分布、并行），沿原路返回AC 比ABC短， M1回到A点时， M2 才到C点。AC上蚁气 ：两次信息素叠加（去-回）AB路只有去一次信息素X(AC)X(ABC)，下一只蚂蚁：选择路径ACAC上信息素越来越多，进入良性循环BAC35Fig. 1. An example with real antsa) Ants follow a path between points A and E.b) An obstacle is interpose

13、d; 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.36Fig. 2. An example with artificial antsa) The initial graph with distances.b) At time t=0 there is no trail on the graph edges; therefore, ants choo

14、se 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.37要点蚂蚁群居群动，很少有独行侠，选择信息素浓的路径 ， 喜欢热闹，追求蚁气（人气）人也类似。 两家饭店，一家热热火火，一家门可罗雀，选哪家？选登山旅游线，一般人选人气多的（信息素浓的）信息素启发性知识：人气高的，自有其优点饭店请名人写诗歌作画、写对联，留下信息素商业 ”托

15、” , 假造信息素优势： 并行+分布+信息素70%选红火的，不一定每人是这样称为按概率.0.7选红火的38双桥实验(Goss S, 1989)Naturwissenschaften 76, 579-581 (1989) Self-organized Shortcuts in the Argentine AntS. Goss, S. Aron, J. L. Deneubourg, and J. M. PasteelsUnit of Behavioural Ecology, C.P. 231, Universit6 Libre de Bruxelles,B- 1050 Bruxelles39Fig

16、. 1. A colony of I humilis selecting the short branches on both modules of the bridgea) one module of the bridgeb) and c): photos taken 4 and 8 min after placement of the bridge40双桥实验数学模型假设条件：1、非对称桥上的信息量与过去一个时间段内经过该桥的蚂蚁数目成正比；2、某一时刻蚂蚁按照桥上残留的信息量多少来选择其中某座桥3、经过该桥的蚂蚁数目越多则桥上的残留信息量就越大设短桥为A，长桥为B，mA和mB分别表示经过

17、桥A和桥B的蚂蚁数目mA + mB = m当所有m只蚂蚁都经过两座桥之后，第m+1只蚂蚁选择桥A的概率为：而选择桥B的概率为：41参数h 和 k用以匹配真实实验数据第m+1只蚂蚁首先计算 然后生成一个在区间0,1上均匀分布的随机数若 ，则选择桥A，否则选择桥B42发展意大利学者M Dorigo，Vmaniezzo和A Colorni20世纪90年代 ：蚂蚁系统（ant system，AS）求解旅行商问题（Traveling Salesman Problem，简称TSP）90年代中期，用于广泛领域，取得成果M Dorigo 发展为优化技术-蚁群优化（Ant Colony Optimization

18、，简称ACO）W J Gutjahr ：ACO的收敛性用于合优化，函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由43ACO国际研讨会ACO国际研讨会 1998、2000年、2002年、2004年，2006年，比利时布鲁塞尔大学 44基本蚁群算法的数学模型45P、NP、NP-C、NP-hard问题P类问题所有可用DTM (Deterministic one-tape Turing Machine) 在多项式时间内求解的判定问题的集合。简记为O(p(n)即 P=L: 存在一个多项式时间DTM程序M，是的L=LM , 其中LM表示程序M所识别的语言。若存在一个多项式时间DTM程序，它在编码策

19、略e之下求解判定问题，即L, eP,则称该判定问题属于P类问题。46P、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)在多项式时间内求解的判定问题的集合47P、NP、

20、NP-C、NP-hard问题NP-C类问题 (NP-Complete)是NP类中最困难的一类问题。有重要实际意义和工程背景TSP (Traveling Salesman Problem)Symmetric; AsymmetricNP-hard类问题NP-C NP-hardNPPNP-hardNP-C48基本蚁群算法模型基本假设蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对周围的局部环境产生影响；蚂蚁对环境的反应由其内部模式决定。即蚂蚁是反应型适应性主体在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成

21、高度有序的群体行为。49TSP (Traveling Salesman Problem)有向图有向图D的三元组为 (V, E, f)，其中V是一个非空集合，其元素称为有向图的结点；E是一个集合，其元素称为有向图的弧段（边）；f是从E到VxV上的一个映射（函数）。E中的元素总是和V中的序偶对有对应关系，可用V中的序偶代替E中的元素。一个有向图可简记为(V, E).50TSP (Traveling Salesman Problem)TSP设C=c1, c2, , cn 是n个城市的集合，L=lij|ci, cj C是集合C中的元素（城市）两两连接的集合，dij(i, j=1,1,n)是lij的Euclidean距离，即G=(C, L)是一个有向图，TSP的目的是从有向图G中寻出长度最短的Hamilton圈，即一条对C=c1, c2, , cn中n个元素（城市）访问且只访问一次的最短封闭曲线51T