混合蚁群算法求解TSP问题

被引:0
作者
翁武熙
机构
[1] 广西大学
关键词
蚁群算法; 蛙跳算法; 模拟退火算法; 旅行商问题; 高斯变异; 柯西变异;
D O I
暂无
年度学位
2012
学位类型
硕士
导师
摘要
蚁群算法是一种广泛用于求解组合优化问题的启发式智能算法,在解决复杂离散优化问题方面展现出其优异的性能及潜力。但其仍存在一些不足,例如搜索时间长,易陷入早熟和停滞等现象。蚁群算法本身也具有易于和其他算法融合的特点,同时很多新型的仿生算法在解决组合优化问题方面有着很好的表现,在算法机理和算法实现上有着和蚁群优势互补的特点。 蛙跳算法是一种结合了具有遗传学特征的Memetic算法和粒子群算法特点的新兴的群智能优化算法,具有较强的全局搜索能力。 模拟退火算法源于固体物质退火原理,能够有效的解决大规模组合优化问题,是近年来相关领域的研究热点。 因此,基于以上背景,本文的主要研究内容如下: 首先,结合TSP问题对蚁群算法、蛙跳算法以及模拟退火算法的基础理论研究进行综述,包括各个算法的研究现状和发展情况,算法的机理,算法的模型和算法的实现等。 其次,针对蚁群算法的一些缺点提出改进的策略,包括状态转移和信息素更新策略,进一步提高了算法的计算能力。 第三,分别将蛙跳算法和模拟退火算法与蚁群算法进行结合。对蛙跳算法和模拟退火提出几种算法改进策略和与蚁群算法进行混合的策略,包括蛙跳-蚁群算法的信息素初始化策略,动态融合策略,高斯变异及柯西变异策略,以及模拟退火-蚁群算法的信息素初始化策略,动态融合策略,针对混合算法的降温公式的优化策略。 最后,对改进的各个算法进行了求解TSP问题的实验验证,其结果表明了改进算法和改进策略的有效性。
引用
收藏
页数:48
共 23 条
[1]
一种新型的智能优化方法-人工鱼群算法 [D]. 
李晓磊 .
浙江大学,
2003
[2]
基于混合进化的SFL算法及其应用 [D]. 
李鑫 .
河北大学,
2010
[3]
基于模拟退火的粒子群优化算法在拆卸序列规划中的应用 [D]. 
杨德军 .
合肥工业大学,
2010
[4]
基于离散粒子群与模拟退火融合算法的自动小车存取系统货位优化 [D]. 
钟寿桂 .
厦门大学,
2009
[5]
Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization..Bullnheimer B; Hartl RF; Strauss C;.Kluwer Academics.1998,
[6]
Particle swarm optimization..Kennedy J; Eberhart RC;.Proceedings of the IEEE International Joint Conference on Neural Networks.1995,
[7]
On Evolution;Search;Optimization;Genetic Algorithms and Martial Arts:Towards Memetic Algorithms..Moscato P;..1989,
[8]
Comparison among five evolutionary-based optimization algorithms [J].
Elbeltagi, E ;
Hegazy, T ;
Grierson, D .
ADVANCED ENGINEERING INFORMATICS, 2005, 19 (01) :43-53
[9]
基于二次退火机制的改进多态蚁群算法 [J].
杜振鑫 ;
王兆青 ;
王枝楠 ;
秦伟 ;
段云涛 .
中南大学学报(自然科学版), 2011, 42 (10) :3112-3117
[10]
基于蚁群算法和免疫算法融合的TSP问题求解 [J].
吴建辉 ;
章兢 ;
刘朝华 .
湖南大学学报(自然科学版), 2009, 36 (10) :81-87