蚁群算法与函数优化课件.ppt
蚁群算法与函数优化,主讲人：王同伟,1蚁群算法原理,蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素或者信息素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。,2,2简化的蚂蚁寻食过程,3,蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。,4,本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。,假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。,5,3 蚂蚁的觅食策略,6,1、等长二元桥实验 蚁穴通过双支桥与食物相连，而桥的两个分支长度相等，而且两个分支上最初没有信息素。然后，将蚂蚁置于可以自由地在蚁穴和食物源之间移动的状态，观察选择两个分支的蚂蚁的比例。结果如图(b)显示，经过最初的一个短暂的震荡阶段，蚂蚁向着一条相同的路径前进。,7,图 1 等长双桥实验,S.Goss 8 等人给出了上述实验的概率模型。首先，假定桥上残留的外激素量与过去一段时间经过该桥的蚂蚁数成正比（这意味着不考虑外激素蒸发的情况）；其次，某一时刻蚂蚁按桥上外激素量的多少来选择某座桥，即蚂蚁选择某座桥的概率与经过该桥的蚂蚁数成正比。当所有 m 只蚂蚁都经过两座桥以后，设 Am、Bm分别为经过 A 桥和 B 桥的蚂蚁数（Am+Bm=m），则第 m+1 只蚂蚁选择 A 桥的概率为：,9,公式表明：往A走的蚂蚁越多，选择分支A的概率就越高“n”决定选择公式的非线性程度。（n越大，信息素多一点的分支选择概率越高）“k”表示对未标记的分支的吸引程度。（k越大，越多的信息素使选择非随机化）,2、不等长双桥实验：图2(a)为蚂蚁经过不等长双桥开始觅食；图2(b)显示绝大多数蚂蚁选择较短的桥；图2(c)显示最终有80%一100%的蚂蚁选择较短的桥。,10,11,图 2 不等长双桥实验,在非对称双桥实验中，由于初始波动的扩大，蚂蚁常常会选择最短的路径;先回蚁巢的蚂蚁在最短分支上走了两次(从蚁穴到食物源，再回到蚁穴)。所以这些蚂蚁回来后不久，在短分支上有更多的信息素，从而诱使巢中同伴选择短分支。实验表明，通过初始波动的扩大，最终选择短分支的几率随着两个分支的长度比的增加而增长。由此可见，在非对称双桥实验中，初始波动对胜出分支桥(即较多蚂蚁选择的桥)的影响减小，而占主导作用的是随机信息素的引导行为。,12,基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。,13,4蚁群现象,蚂蚁正常行进，没有遇到任何障碍，一路畅通。,蚂蚁正常行进，突然环境变换，增加了障碍物,蚁群以同等概率选择各条路径，紧接着，随着时间的增加较短路径信息浓度高，选择该路径的蚂蚁逐渐增多。,蚂蚁最终绕过障碍物，找到最优路径。,5蚂蚁简单规则两方面,1多样性：蚂蚁在觅食的时候路线不一，随机性的向着某个方向方向走，打破常规，进行创新。2正反馈：优化的路线不断被保存并加大自身概率，保证了相对优良的信息能够被保存下来。多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。,6.蚁群算法求最优,目标函数：=cos(2*pi.*x).*cos(2.*pi.*y).*exp(-(x.2+y.2)/10)其中x,y-1,1 根据原理，各数值首先随机分布在坐标上如图7，经过多次搜索最终得到最优解如图8所得极大值为0.9997 如图9，并得出最优函数值的变化趋势图。,数值随机分布图,蚂蚁的最终分布位置图,最优函数值变化趋势图,谢谢观赏,
