文档介绍：1蚁群算法及其应用2启发式算法_分类现代优化算法: 80年代初兴起?禁忌搜索(tabu search)?模拟退火(simulated annealing)?神经网络(works)?遗传算法(ic algorithms)?蚂蚁算法(Ant Algorithm,群体智能,Swarm Intelligence)3遗传算法?遗传算法(icAlgorithm,GA)是1962年密切根大学Holland教授首次提出的一种全局优化算法,它借用了生物遗传学的观点,通过自然选择、遗传、变异等作用机制,实现各个体的适应性的提高,并迅速推广到优化、搜索、机器学****等方面。4遗传算法的过程编码和初始群体生成个体适应度的评测(适值函数)选择交叉变异5蚁群算法1 原理2 在TSP中的应用及改进3 在QoS多播路由中的应用61 蚁群算法原理?20 世纪90 年代初,意大利学者Dorigo 等受蚂蚁觅食行为的启发,提出了蚁群算法,是一种仿生算法。?蚂蚁在觅食过程中可以找出巢穴到食物源的最短路径,为什么?(1)信息素(pheromone)(2)正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。7简化的蚂蚁寻食过程蚂蚁从A点出发,速度相同,食物在D点,可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁,每个时间单位行走一步,本图为经过9个时间单位时的情形:走ABD的蚂蚁到达终点,而走ACD的蚂蚁刚好走到C点,为一半路程。8简化的蚂蚁寻食过程经过18个时间单位时的情形:走ABD的蚂蚁到达终点后得到食物又返回了起点A,而走ACD的蚂蚁刚好走到D点。9自然蚁群与人工蚁群相似之处在于:都是优先选择信息素浓度大的路径。两者的区别:(1)在于人工蚁群有一定的记忆能力,能够记忆已经访问过的节点。(2)人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如,在TSP问题中,可以预先知道当前城市到下一个目的地的距离。10应用一:TSP问题?旅行商问题(TSP,traveling salesman problem)1960年首先提出。?问题描述:一商人去n个城市销货,所有城市走一遍再回到起点,使所走路程最短。?TSP在许多工程领域具有广泛的应用价值例如电路板布线、VLSI芯片设计、机器人控制、交通路由等。?TSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长。