基于蚁群算法的TSP研究
Abstract（摘要）
本文利用改进的蚁群算法解决了TSP（旅行商问题）问题，讨论了蚁群算法的几个关键参数对算法性能的影响。 同时利用MATLAB对大量数据进行计算机仿真，通过对大量数据的实验，对设定参数进行调整。 实验表明，蚁群算法对于解决实际问题具有理论和实践指导意义。
关键词：蚁群算法，TSP，组合优化，模型，信息素
I.介绍
为了提高人工智能（Artificial Intelligence，AI）优化技术和智能计算的发展水平，近年来有许多研究，特别是在学者的生物学方面，通过大量的生物本性生活现象以及大量研究和研究的规律，提出了大量的群体智能算法[1,2,3]。
蚁群算法是群体智能算法的一个重要分支。 在一些如蜜蜂的昆虫中，观察到了蚂蚁和大量的研究，生物学家在徘徊时发现了小虫子如蚂蚁，通过群体的力量，经过反复探索发现，终于找到了最短路径从巢到食物来源。 为了进一步研究，蚂蚁生物学家在路径上寻找食物，设置了一些障碍物来影响蚂蚁的搜索路径，经过一段时间的搜索，蚂蚁仍然找到从巢到食物源的最短路径[4] 。 经过各种实验，生物学家进一步的研究表明，蚂蚁在探索过程中寻找食物，化学物质可以在这种特定物质的路径上释放一种叫做信息素（信息素）的挥发物。 信息素可以随着时间逐渐沉积在路径上。 [5,6]当蚂蚁选择路径时，往往会沿着气味浓厚的信息素路径向前移动。 所以费洛蒙可以引导蚂蚁更快，更可能找到离巢穴最近的食物。 实验结果表明，它是特殊的材料，可以使蚂蚁找到从巢到食物的最短路径。 也可以这样说，由于蚂蚁巢穴和食物之间有许多路径，所以可以在整个群体的每只蚂蚁的信息素中搜索踪迹，找到巢穴和食物之间的最短路径[7,8,9]。
II.基本蚁群算法实现步骤
步骤1：nc = 0（NC是迭代次数或搜索次数）; 每一边的Tj（0）= c（常数）和delta Tj = 0; 把蚂蚁放在N个城市。
步骤2：每个蚂蚁的初始起点位于当前解集TABUk中; 根据到下一个城市j的概率Pij（t），每个蚂蚁k（k = 1，lt;，m） 将城市j放入TABUk。
第三步：第n次以后，蚂蚁可以完成所有的城市，完成一个循环。 计算每只蚂蚁的总路径长度Lk，更新找到的最短路径。
步骤4：更新每个边上的信息量Tij（t n)
步骤5：对于每个集合Delta;Tij= 0; nc = nc 1
步骤6：如果nc lt;预定的迭代次数Ncmax，则转到步骤2; 否则，打印出最短路径来终止整个程序。
III.基本参数设置
代码如下所示：
%% initialization parameters m= 50; % 蚂蚁的数量
Alpha = 1; %信息素重要因子
Beta = 5; % 启发式函数重要因子
Rho = 0.1; % 信息素蒸发因子
Q = 1; % 常数系数
Eta = 1. /D;%启发式函数
Tau = ones (n, n); %信息素矩阵
Table = zeros (m, n); % 踪迹表
iter = 1; %迭代初始值
iter_max = 200; % 最大迭代次数
Route_best =零（iter_max，n）; ％每一代的最佳路径
Length_best =零（iter_max，1）; 最佳路径长度：
Length_ave =零（iter_max，1）; 每一代路径的平均长度
这是程序初始化设置中的一些参数，其中参数的值可以修改，影响下面各个蚁群算法关键参数的性能。 在接下来的研究中，我们将介绍分析研究的几个关键参数。
IV.基本蚁群算法仿真结果
以基本蚁群算法为例，设置了启发因子alpha;，期望启发因子beta;，蚂蚁数m，挥发系数rho;，蚂蚁信息素强度信息Q，默认值为程序中的原始值，对全局搜索能力和算法收敛速度表现出较好的性能，并且算法也获得了最优路径[11,12,13]
图1显示了34个城市的连接图，说明了基本的蚁群算法可以解决TSP问题（NP完全问题），同时也反映了蚁群算法具有正反馈，自组织等优点。
图2红线（线）是每次迭代平均路径长度，每次迭代的最短路径（即最优值）为蓝线（线）。 平均路径比最短路径图要高得多，这是因为一些蚂蚁的路径走得很好，距离相应变短; 而且有些蚂蚁路径很不好，路径会经历很长的变化，说明了基本蚁群算法存在局部过早收敛的问题。 从蓝线（直线）可以看出，直到迭代次数超过120次才收敛算法结束，而蚁群算法也存在收敛速度慢的情况，那么参数设置就显得尤为重要[14， 15,16]。
图1城市旅游路线图
图2每次迭代的平均路径长度和最短路径图
V.关键参数的设置和优化
蚁群算法中的alpha;，beta;，rho;，m等关键参数对算法的性能影响很大，参数alpha;，beta;，rho;，m的最优配置进一步优化了算法的性能和蚁群算法这在实际问题中非常重要。 要对每个关键参数进行适当的设置，必须针对具体的问题，条件和要求，并将这两个指标整合到全局搜索能力和收敛速度中[17,18]。
通过计算机仿真实验，影响蚁群算法分析和验证的关键参数对算法性能的影响，终点条件实验在全局最优化100个循环后依然没有改善，用改变参数方法，固定其他参数，以探索参数设置对算法效率的影响[19]。 蚂蚁总数临时设置为城市总数，每个城市是蚂蚁的初始放置位置; 默认参数设置为alpha;= 0.1，beta;= 2，rho;= 0.2。 在每个备选路线的概率条件下，采用随机选择蚂蚁到达下一个城市的方法，每次测试10次并进行平均比较，用于Eli51城市问题的TSP数据的测试问题。
信息启发因子alpha;反映了蚂蚁在信息素运动过程中的积累（即信息素残差tau;ij（T））在指导蚁群搜索中的相对重要程度。 它的大小反映了蚁群路径搜索强度的随机因素：alpha;值越大，蚂蚁通过前面选择的路段的可能性越大，搜索的随机性越弱，但是当alpha;值过高时会使蚁群过早搜索到局部最优; 而当alpha;= 0时蚁群算法是传统的贪心算法。
期望的启发式因子beta;反映了运动过程中的蚂蚁启发式信息（期望值eta;ij）指导蚁群搜索的相对重要程度。 它的大小反映了路径搜索前的蚁群的确定性因子强度：beta;值越大，蚂蚁从它附近节点中选取的可能性越大，局部点局部最短路径选择的可能性也越大，虽然蚁群的搜索过程的收敛速度会加快，但是最优路径的随机性会减弱，算法很容易陷入局部最优; 当beta;= 0时，蚁群算法是一种纯粹的正反馈启发式算法。
蚁群算法的全局优化性能要求，蚁群搜索过程必须具有较强的随机性; 而用于快速收敛的蚁群算法和蚁群搜索过程必须定义更高的收敛速度。 因此alpha;，beta;对蚁群算法性能的影响是密切相关的。
蚁群算法的全局优化性能要求，蚁群搜索过程必须具有较强的随机性; 而用于快速收敛的蚁群算法和蚁群的搜索过程必须定义更高的收敛速度。alpha;和beta;对算法性能的影响实验结果如表1所示，它与其他参数保持不变，alpha;，beta;组合为不同的值。
表格1alpha;和beta;不同组合对算法的影响
|
alpha; |
beta; |
Length of optimal path |
Times of search loop |
|
0.1 |
0.5 |
455.7 |
162 |
|
0.1 |
1.0 |
442.4 |
97 |
|
0.2 |
2.0 |
431.4 |
79 |
|
0.3 |
3.0 |
443.3 |
66 |
|
1.0 |
4.0 |
452.6 |
52 |
|
5.0 |
8.0 |
458.0 |
22 |
|
10.0 |
10.0 |
470.0 |
16 |
图三alpha;和beta;不同组合对算法的影响
从图3可以看出，蚁群算法的alpha;和beta;的选择性，对算法的性能有很大的影响。
当alpha;和beta;太高时：对于较大的值，相当于赋予信息素tau;ij（T）在蚂蚁搜索过程中的重要性给予充分的重视，蚂蚁完全依靠信息素tau;ij（T）来引导搜索，如果希望的信息是ij，启发式因子beta;也是比较大的，这将导致局部最优路径信息是强正反馈过程，算法会出现早熟收敛（停滞）现象，当问题规模很大，在这种情况下搜索通常是一个局部最优解决方案。
当alpha;和beta;为小时：对于alpha;值较小的情况，蚂蚁在蚂蚁搜索过程中tau;ij（T）重要性路径上信息素的等价性没有给予足够的重视，完全依赖于期望信息eta;ij来搜索，如果预期的启发式因子beta;信息eta;ij相对较小，则会导致蚁群进入无尽的随机搜索在这种纯粹的（即不停滞的）情况，这种情况下，搜索一般很难找到最佳解决方案。
alpha;和beta;合适的选择范围中，在此时如果参数组合不同（如本文中的Eli51问题从0.2到0.5，alpha;，beta;2左右），蚁群算法可以获得更好的搜索结果，循环次数算法可能会更少（即收敛速度快），并且性能非常接近。
在蚁群算法中，人造蚂蚁是人类的记忆函数，随着时间的推移，离开之前信息会消失。 在具有参数1-rho;的算法模型中，信息消失度（也称为信息素挥发度），rho;是信息素残差水平。 遗传算法和蚁群算法模拟进化算法收敛速度慢，容易陷入局部最优缺陷，p级信息素残差直接关系到蚁群算法全局搜索能力的大小及其收敛性。
信息素余量rho;存在，当问题规模较大时，可以使信息素在从未搜索到的路径（解）上缓慢降低到0，从而降低算法的全局搜索能力; 而当p较大时，正反馈信息为较强的可能性，之前由蚂蚁搜索到的路径选择也较大，随机搜索较为虚弱。 相反，如果rho;较小，虽然随机搜索会更强，但可以提高算法的全局搜索能力。
关于rho;信息素残留量对算法性能及其选择的影响，还可以通过计算机模拟实验来分析和确定描述：根据上述实验，与其他参数保持不变，信息素残留水平rho;lt;{0.1,0.2,0.3,0.5,0.7,0.9}的变化，与图4和表2中的实验结果相关。 以下是实验参数的数据，包括最佳路径的长度和迭代次数，可以严格地显示实际情况。
表2rho;对算法性能的影响
|
rho; |
的长度 最佳路径 |
的时代 迭代 |
|
0.1 |
446.8 |
573 |
|
0.2 |
434.9 |
273 |
|
0.3 |
435.7 |
147 |
|
0.5 |
436.0 |
112 |
|
0.7 |
463.7 |
72 |
|
0.9 |
455.3 |
33 |
图4rho;对算法性能的影响
从上述实验结果可以看出，当其他参数在相同收敛性条件下时，对蚁群算法1-rho;大小的信息素挥发影响很大：当1-rho;小时（即P较大） ，由于主导信息路径残差，信息正性反馈较强，搜索弱随机性，收敛速度快，但算法容易陷入局部最优; 而在1-rho;较大（即P很小）时，由于信息反馈效应占优势。
因此，在蚁群算法中选择度rho;信息素必须是残差，具体应用条件
全文共7515字，剩余内容已隐藏，支付完成后下载完整资料
毕业设计英文翻译（译文）
|
学 院 |
计算机科学与技术 |
|
专 业 |
计算机科学与技术 |
|
班 级 |
计算机zy1401 |
|
姓 名 |
李文君 |
|
指导教师 |
彭德巍 |
|
2018 |
年 |
2 |
月 |
4 |
日 |
基于蚁群算法的TSP研究
Abstract（摘要）
本文利用改进的蚁群算法解决了TSP（旅行商问题）问题，讨论了蚁群算法的几个关键参数对算法性能的影响。 同时利用MATLAB对大量数据进行计算机仿真，通过对大量数据的实验，对设定参数进行调整。 实验表明，蚁群算法对于解决实际问题具有理论和实践指导意义。
关键词：蚁群算法，TSP，组合优化，模型，信息素
I.介绍
为了提高人工智能（Artificial Intelligence，AI）优化技术和智能计算的发展水平，近年来有许多研究，特别是在学者的生物学方面，通过大量的生物本性生活现象以及大量研究和研究的规律，提出了大量的群体智能算法[1,2,3]。
蚁群算法是群体智能算法的一个重要分支。 在一些如蜜蜂的昆虫中，观察到了蚂蚁和大量的研究，生物学家在徘徊时发现了小虫子如蚂蚁，通过群体的力量，经过反复探索发现，终于找到了最短路径从巢到食物来源。 为了进一步研究，蚂蚁生物学家在路径上寻找食物，设置了一些障碍物来影响蚂蚁的搜索路径，经过一段时间的搜索，蚂蚁仍然找到从巢到食物源的最短路径[4] 。 经过各种实验，生物学家进一步的研究表明，蚂蚁在探索过程中寻找食物，化学物质可以在这种特定物质的路径上释放一种叫做信息素（信息素）的挥发物。 信息素可以随着时间逐渐沉积在路径上。 [5,6]当蚂蚁选择路径时，往往会沿着气味浓厚的信息素路径向前移动。 所以费洛蒙可以引导蚂蚁更快，更可能找到离巢穴最近的食物。 实验结果表明，它是特殊的材料，可以使蚂蚁找到从巢到食物的最短路径。 也可以这样说，由于蚂蚁巢穴和食物之间有许多路径，所以可以在整个群体的每只蚂蚁的信息素中搜索踪迹，找到巢穴和食物之间的最短路径[7,8,9]。
II.基本蚁群算法实现步骤
步骤1：nc = 0（NC是迭代次数或搜索次数）; 每一边的Tj（0）= c（常数）和delta Tj = 0; 把蚂蚁放在N个城市。
步骤2：每个蚂蚁的初始起点位于当前解集TABUk中; 根据到下一个城市j的概率Pij（t），每个蚂蚁k（k = 1，lt;，m） 将城市j放入TABUk。
第三步：第n次以后，蚂蚁可以完成所有的城市，完成一个循环。 计算每只蚂蚁的总路径长度Lk，更新找到的最短路径。
步骤4：更新每个边上的信息量Tij（t n)
步骤5：对于每个集合Delta;Tij= 0; nc = nc 1
步骤6：如果nc lt;预定的迭代次数Ncmax，则转到步骤2; 否则，打印出最短路径来终止整个程序。
III.基本参数设置
代码如下所示：
%% initialization parameters m= 50; % 蚂蚁的数量
Alpha = 1; %信息素重要因子
Beta = 5; % 启发式函数重要因子
Rho = 0.1; % 信息素蒸发因子
Q = 1; % 常数系数
Eta = 1. /D;%启发式函数
Tau = ones (n, n); %信息素矩阵
Table = zeros (m, n); % 踪迹表
iter = 1; %迭代初始值
iter_max = 200; % 最大迭代次数
Route_best =零（iter_max，n）; ％每一代的最佳路径
Length_best =零（iter_max，1）; 最佳路径长度：
Length_ave =零（iter_max，1）; 每一代路径的平均长度
这是程序初始化设置中的一些参数，其中参数的值可以修改，影响下面各个蚁群算法关键参数的性能。 在接下来的研究中，我们将介绍分析研究的几个关键参数。
IV.基本蚁群算法仿真结果
以基本蚁群算法为例，设置了启发因子alpha;，期望启发因子beta;，蚂蚁数m，挥发系数rho;，蚂蚁信息素强度信息Q，默认值为程序中的原始值，对全局搜索能力和算法收敛速度表现出较好的性能，并且算法也获得了最优路径[11,12,13]
图1显示了34个城市的连接图，说明了基本的蚁群算法可以解决TSP问题（NP完全问题），同时也反映了蚁群算法具有正反馈，自组织等优点。
图2红线（线）是每次迭代平均路径长度，每次迭代的最短路径（即最优值）为蓝线（线）。 平均路径比最短路径图要高得多，这是因为一些蚂蚁的路径走得很好，距离相应变短; 而且有些蚂蚁路径很不好，路径会经历很长的变化，说明了基本蚁群算法存在局部过早收敛的问题。 从蓝线（直线）可以看出，直到迭代次数超过120次才收敛算法结束，而蚁群算法也存在收敛速度慢的情况，那么参数设置就显得尤为重要[14， 15,16]。
图1城市旅游路线图
图2每次迭代的平均路径长度和最短路径图
V.关键参数的设置和优化
蚁群算法中的alpha;，beta;，rho;，m等关键参数对算法的性能影响很大，参数alpha;，beta;，rho;，m的最优配置进一步优化了算法的性能和蚁群算法这在实际问题中非常重要。 要对每个关键参数进行适当的设置，必须针对具体的问题，条件和要求，并将这两个指标整合到全局搜索能力和收敛速度中[17,18]。
通过计算机仿真实验，影响蚁群算法分析和验证的关键参数对算法性能的影响，终点条件实验在全局最优化100个循环后依然没有改善，用改变参数方法，固定其他参数，以探索参数设置对算法效率的影响[19]。 蚂蚁总数临时设置为城市总数，每个城市是蚂蚁的初始放置位置; 默认参数设置为alpha;= 0.1，beta;= 2，rho;= 0.2。 在每个备选路线的概率条件下，采用随机选择蚂蚁到达下一个城市的方法，每次测试10次并进行平均比较，用于Eli51城市问题的TSP数据的测试问题。
信息启发因子alpha;反映了蚂蚁在信息素运动过程中的积累（即信息素残差tau;ij（T））在指导蚁群搜索中的相对重要程度。 它的大小反映了蚁群路径搜索强度的随机因素：alpha;值越大，蚂蚁通过前面选择的路段的可能性越大，搜索的随机性越弱，但是当alpha;值过高时会使蚁群过早搜索到局部最优; 而当alpha;= 0时蚁群算法是传统的贪心算法。
期望的启发式因子beta;反映了运动过程中的蚂蚁启发式信息（期望值eta;ij）指导蚁群搜索的相对重要程度。 它的大小反映了路径搜索前的蚁群的确定性因子强度：beta;值越大，蚂蚁从它附近节点中选取的可能性越大，局部点局部最短路径选择的可能性也越大，虽然蚁群的搜索过程的收敛速度会加快，但是最优路径的随机性会减弱，算法很容易陷入局部最优; 当beta;= 0时，蚁群算法是一种纯粹的正反馈启发式算法。
蚁群算法的全局优化性能要求，蚁群搜索过程必须具有较强的随机性; 而用于快速收敛的蚁群算法和蚁群搜索过程必须定义更高的收敛速度。 因此alpha;，beta;对蚁群算法性能的影响是密切相关的。
蚁群算法的全局优化性能要求，蚁群搜索过程必须具有较强的随机性; 而用于快速收敛的蚁群算法和蚁群的搜索过程必须定义更高的收敛速度。alpha;和beta;对算法性能的影响实验结果如表1所示，它与其他参数保持不变，alpha;，beta;组合为不同的值。
表格1alpha;和beta;不同组合对算法的影响
|
alpha; |
beta; |
Length of optimal path |
Times of search loop |
|
0.1 |
0.5 |
455.7 |
162 |
|
0.1 |
1.0 |
442.4 |
97 |
|
0.2 |
2.0 |
431.4 |
79 |
|
0.3 |
3.0 |
443.3 |
66 |
|
1.0 |
4.0 |
452.6 |
52 |
|
5.0 |
8.0 |
458.0 |
22 |
|
10.0 |
10.0 |
470.0 |
16 |
图三alpha;和beta;不同组合对算法的影响
从图3可以看出，蚁群算法的alpha;和beta;的选择性，对算法的性能有很大的影响。
当alpha;和beta;太高时：对于较大的值，相当于赋予信息素tau;ij（T）在蚂蚁搜索过程中的重要性给予充分的重视，蚂蚁完全依靠信息素tau;ij（T）来引导搜索，如果希望的信息是ij，启发式因子beta;也是比较大的，这将导致局部最优路径信息是强正反馈过程，算法会出现早熟收敛（停滞）现象，当问题规模很大，在这种情况下搜索通常是一个局部最优解决方案。
当alpha;和beta;为小时：对于alpha;值较小的情况，蚂蚁在蚂蚁搜索过程中tau;ij（T）重要性路径上信息素的等价性没有给予足够的重视，完全依赖于期望信息eta;ij来搜索，如果预期的启发式因子beta;信息eta;ij相对较小，则会导致蚁群进入无尽的随机搜索在这种纯粹的（即不停滞的）情况，这种情况下，搜索一般很难找到最佳解决方案。
alpha;和beta;合适的选择范围中，在此时如果参数组合不同（如本文中的Eli51问题从0.2到0.5，alpha;，beta;2左右），蚁群算法可以获得更好的搜索结果，循环次数算法可能会更少（即收敛速度快），并且性能非常接近。
在蚁群算法中，人造蚂蚁是人类的记忆函数，随着时间的推移，离开之前信息会消失。 在具有参数1-rho;的算法模型中，信息消失度（也称为信息素挥发度），rho;是信息素残差水平。 遗传算法和蚁群算法模拟进化算法收敛速度慢，容易陷入局部最优缺陷，p级信息素残差直接关系到蚁群算法全局搜索能力的大小及其收敛性。
信息素余量rho;存在，当问题规模较大时，可以使信息素在从未搜索到的路径（解）上缓慢降低到0，从而降低算法的全局搜索能力; 而当p较大时，正反馈信息为较强的可能性，之前由蚂蚁搜索到的路径选择也较大，随机搜索较为虚弱。 相反，如果rho;较小，虽然随机搜索会更强，但可以提高算法的全局搜索能力。
关于rho;信息素残留量对算法性能及其选择的影响，还可以通过计算机模拟实验来分析和确定描述：根据上述实验，与其他参数保持不变，信息素残留水平rho;lt;{0.1,0.2,0.3,0.5,0.7,0.9}的变化，与图4和表2中的实验结果相关。 以下是实验参数的数据，包括最佳路径的长度和迭代次数，可以严格地显示实际情况。
表2rho;对算法性能的影响
|
rho; |
的长度 最佳路径 |
的时代 迭代 |
|
0.1 |
446.8 |
573 |
|
0.2 |
434.9 |
273 |
|
0.3 |
435.7 |
147 |
|
0.5 |
436.0 |
112 |
|
0.7 |
463.7 |
72 |
|
0.9 |
455.3 |
33 |
图4rho;对算法性能的影响
从上述实验结果可以看出，当其他参数在相同收敛性条件下时，对蚁群算法1-rho;大小的信息素挥发影响很大：当1-rho;小时（即P较大） ，由于主导信息路径残差，信息正性反馈较强，搜索弱随机性，收敛速度快，但算法容易陷入局部最优; 而在1-rho;较大（即P很小）时，由于信息反馈效应占优势。
因此，在蚁群算法中选择度rho;信息素必须是残差，具体应用条件
全文共7515字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11727]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
