摘要本论文主要研究基于反向轮盘赌机制的人工蜂群算法在旅行商问题上的应用，采用Matlab 软件编程仿真实现，并对算法的有效性及正确性进行了验证。本文首先阐述了群体智能优化算法的基本特点，列举了常见的群智能优化算法，介绍了论文的主要研究内容和研究意义。然后深入研究了基本人工蜂群算法的主要步骤、控制参数的设定及算法的流程。紧接着针对基本ABC 算法“早熟”的缺陷，在大量实验测试的基础上，采用反向轮盘赌机制对算法进行改进并仿真实现。通过对仿真结果的分析，应用这一机制选取待更新的食物源能有效克服过早陷入局部最优这一缺点，收敛速度也有显著提升，确保了种群的多样性。论文最后总结了人工蜂群算法目前的发展状况，并对算法的研究方向和应用领域进行了展望。 20865
关键词 反向轮盘赌 人工蜂群 群体智能 组合优化 评估适应度值
Title Artificial Bee Colony (ABC) Algorithms on TSP
Abstract
In this thesis, artificial bee colony algorithm based on reverse roulette
mechanism was applied in the traveling salesman problem. The improved
algorithm used Matlab for simulation, testing the validity and accuracy
of the algorithm. The paper described the basic features of the swarm
intelligence optimization algorithm concisely, also cited several common
examples of the swarm intelligence optimization algorithm, which
introduced the main contents and significance of this thesis. After
carefully studying the major steps, control parameters setting, and the
process of the algorithm, anti-roulette mechanism was applied into the ABC
algorithm to make improvements, aimed at the "premature" of the ABC
algorithm. After analyzing the results of the simulation, this mechanism
does not add any time complexity and space complexity, which can
effectively overcome the shortcomings named “premature” and
significantly improved convergence rate, with less times of fitness
evaluation than the hybrid ABC algorithm. Finally, the paper concluded the
overview of the current developments of the ABC algorithm, and had a
creative outlook of the research direction and the application of the
algorithm.
Keywords Reverse roulette mechanism Artificial bee colony algorithm Swarm intelligence Combination optimal Fitness evaluation
目 次
1绪论 1
1.1 研究背景 1
1.2 群体智能优化算法 1
1.3 常见的群智能优化算法 3
1.4 研究现状 3
1.5 研究内容和研究意义 4
1.6 论文的组织结构 5
2人工蜂群算法简介 6
2.1 模拟蜜蜂繁殖机理 6
2.2 模拟蜜蜂觅食机理 6
2.3 人工蜂群算法的基本原理 7
2.4 算法控制参数的选择 9
2.5 人工蜂群算法框架 . 10
2.6 本章小结 . 11
3人工蜂群算法在TSP 问题中的应用 . 12
3.1 TSP 问题概述 12
3.2 算法改进与实现 . 13
3.3 仿真验证 . 14
3.4 本章小结 . 18
4总结与展望 . 19
致 谢 20
参 考 文 献 21
1 绪论
1.1 研究背景
达尔文在其1859 年出版的著作The Origin of Species 中指出，大自然根据“物竞 人工蜂群算法在旅行商问题中的应用研究 :http://www.751com.cn/zidonghua/lunwen_12807.html