蚁群算法及其应用.ppt

《蚁群算法及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、蚁群算法及其应用1启发式算法_分类现代优化算法：80年代初兴起禁忌搜索（tabusearch）模拟退火（simulatedannealing）神经网络（neuralnetworks）遗传算法（geneticalgorithms）蚂蚁算法（AntAlgorithm，群体智能，SwarmIntelligence）2遗传算法遗传算法(Genetic Algorithm, GA)是1962年密切根大学Holland教授首次提出的一种全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个体的适应性的提高，并迅速推广到优化、搜索、

2、机器学习等方面。3遗传算法的过程编码和初始群体生成个体适应度的评测(适值函数)选择交叉变异4蚁群算法1原理2在TSP中的应用及改进3在QoS多播路由中的应用51蚁群算法原理20世纪90年代初，意大利学者Dorigo等受蚂蚁觅食行为的启发，提出了蚁群算法，是一种仿生算法。蚂蚁在觅食过程中可以找出巢穴到食物源的最短路径，为什么？（1）信息素(pheromone)（2）正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。6简化的蚂蚁寻食过程蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂

3、蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。7简化的蚂蚁寻食过程经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。8自然蚁群与人工蚁群相似之处在于：都是优先选择信息素浓度大的路径。两者的区别：（1）在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。（2）人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如，在TSP问题中，可以预先知道当前城市到下一个目的地的距离。9应用一：TSP问题旅行商问

4、题（TSP,travelingsalesmanproblem）1960年首先提出。问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。TSP在许多工程领域具有广泛的应用价值例如电路板布线、VLSI芯片设计、机器人控制、交通路由等。TSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长。10TSP问题的数学描述TSP问题表示为一个N个城市的有向图G=（N，A），其中城市之间距离目标函数为其中，，为城市1,2，…n的一个排列，。11蚂蚁算法求解TSP下面以TSP为例说明基本蚁群算法模型。首先将m只蚂蚁随机放置

5、在n个城市，位于城市i的第k只蚂蚁选择下一个城市j的概率为:12蚂蚁算法求解TSP其中：表示边（i，j）上的信息素浓度；是启发信息，d是城市i和j之间的距离；α和β反映了信息素与启发信息的相对重要性；表示蚂蚁k已经访问过的城市列表。当所有蚂蚁完成周游后，按以下公式进行信息素更新。13蚂蚁算法求解TSP其中：ρ为小于1的常数，表示信息的持久性。其中：Q为常数；lk表示第k只蚂蚁在本次迭代中走过的路径，Lk为路径长度。14求解TSP算法步骤⑴初始化　随机放置蚂蚁，为每只蚂蚁建立禁忌表tabuk，将初始节点置入禁忌表中;⑵迭代过程k=1whilek=

6、tCountdo(执行迭代)fori=1tomdo(对m只蚂蚁循环)forj=1ton-1do(对n个城市循环)根据式(1)，采用轮盘赌方法在窗口外选择下一个城市j;将j置入禁忌表,蚂蚁转移到j;endforendfor计算每只蚂蚁的路径长度;根据式(2)更新所有蚂蚁路径上的信息量;k=k+1;endwhile⑶输出结果,结束算法.15蚁群的规模和停止规则一、蚁群大小一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。二、终止条件1给定一个外循环的最大数目；2当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续。1

7、6蚂蚁算法的缺点蚂蚁算法的缺点：1）收敛速度慢2）易于陷入局部最优改进：1）采用局部优化，设计了三种优化算子。2）采用蚁群优化算法。3）其它优化算法17改进一：局部优化（算子1）18对Kroa100，算子1优化前后的路径如图所示。优化前（28596），算子1优化后（26439）19改进一：局部优化（算子2）20对Kroa100，算子2优化前后的路径如图所示。算子1（26439），算子2优化后（23012）21TSP具有邻域特征，设置候选窗口，窗口大小应取一个合理值。蚂蚁总是优先选择候选窗口中的城市。搜索结束后，根据候选窗口对路径进行优化，如果将候选

8、窗口内的节点交换到当前节点附近后距离更短，则进行变异。改进一：局部优化（算子3）22对Kroa100，算子3优化前后的路径