1、蚁群算法与函数优化 主讲人：王同伟 1蚁群算法原理 蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素或者信息素 (pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 2 2简化的蚂蚁寻食过程 3 蚂蚁从 A点出发，速度相同，食物在 D点，可能随机选择路线ABD或 ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过 9个时间单位时的情形：走 ABD的蚂蚁到达终点，而走 ACD的蚂蚁刚好走到 C
2、点，为一半路程。 4 本图为从开始算起，经过 18个时间单位时的情形：走 ABD的蚂蚁到达终点后得到食物又返回了起点 A，而走 ACD的蚂蚁刚好走到 D点。 假设蚂蚁每经过一处所留下的信息素为一个单位，则经过 36个时间单位后所有开始一起出发的蚂蚁都经过不同路径从 D点取得了食物，此时 ABD的路线往返了 2趟，每一处的信息素为 4个单位，而 ACD的路线往返了一趟，每一处的信息素为 2个单位，其比值为 2： 1。 若按以上规则继续，蚁群在 ABD路线上再增派一只蚂蚁（共 3只），而 ACD路线上仍然为一只蚂蚁。再经过 36个时间单位后，两条线路上的信息素单位积累为 24和 6，比值为 4：1
3、。 若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃 ACD路线，而都选择 ABD路线。这也就是前面所提到的正反馈效应。 5 3 蚂蚁的觅食策略 6 1、等长二元桥实验 蚁穴通过双支桥与食物相连，而桥的两个分支长度相等，而且两个分支上最初没有信息素。然后，将蚂蚁置于可以自由地在蚁穴和食物源之间移动的状态，观察选择两个分支的蚂蚁的比例。结果如图 (b)显示，经过最初的一个短暂的震荡阶段，蚂蚁向着一条相同的路径前进。 7 图 1 等长双桥实验 S. Goss 8 等人给出了上述实验的概率模型。首先，假定桥上残留的外激素量与过去一段时间经过该桥的蚂蚁数成正比（这意味着不考虑外激素蒸发的情况）；其次
4、，某一时刻蚂蚁按桥上外激素量的多少来选择某座桥，即蚂蚁选择某座桥的概率与经过该桥的蚂蚁数成正比。当所有 m 只蚂蚁都经过两座桥以后，设 Am、 Bm分别为经过 A 桥和 B 桥的蚂蚁数（ Am + Bm = m），则第 m+1 只蚂蚁选择 A 桥的概率为： 9 公式表明：往 A走的蚂蚁越多，选择分支 A的概率就越高 “ n”决定选择公式的非线性程度。（ n越大，信息素多一点的分支选择概率越高） “ k”表示对未标记的分支的吸引程度。（ k越大，越多的信息素使选择非随机化） ()1( ) ( )niAB nniikAPPk A k B 2、不等长双桥实验： 图 2 (a)为蚂蚁经过不等长双桥开始觅食； 图 2 (b)显示绝大多数蚂蚁选择较短的桥； 图 2 (c)显示最终有 80%一 100%的蚂蚁选 择较短的桥。 10
