英语原文共 9 页
摘要
在解决对称和非对称类型的中小型旅行商问题（TSP）时，传统的蚁群优化（ACO）算法可以很好地工作，提供高精度和令人满意的效率。 然而，当TSP的规模增加时，启发式算法ACO在准确性和效率方面受到很大挑战。 因此提出了一种新的信息素跟踪更新策略，该策略适度地减少了实际优化问题求解所需的迭代时间。 与几个实验中ACO的传统策略相比，所提出的策略显示了性能方面的优势。 因此，这种信息素跟踪更新策略被认为是一种有效的能够减少时间复杂度并提高其效率的解决方法，同时减少实际优化应用中的迭代时间。 此外，该策略特别适用于解决基于ACO的中等大规模TSP。
Key Words: ant colony optimization (ACO); travelling salesman problem (TSP); time-complexity of algorithm; pheromone-trail up- dating.
DOI: 10.1109/JSEE.2015.00142
第1章 简介
蚁群优化（ACO）算法，即抽象的蚂蚁觅食行为，体现了群体行为的分布式计算和自组织特征。由于Dorigo首先使用ACO算法来解决旅行商问题（TSP），因此有许多专家尝试将ACO应用于不同的组合优化问题，例如作业车间调度问题，二次分配问题，路径规划，网络路由优化和控制参数优化[1-6]。近年来，一些学者将ACO扩展到连续功能优化，并取得了比较满意的结果[7]。
大规模TSP是典型的NP-C问题[8,9]。目前，解决TSP的算法可以分为两类：精度算法和启发式算法[9]。通常，结构算法用于通过找到最优解来解决小TSP;而采用启发式算法来解决中型和大型TSP。用于解决TSP的几种启发式算法来自自然启发的群体智能，例如ACO模型，PSO模型和进化计算模型[9-11]。启发式算法模型通常遵循简单的控制规则，试图通过多次迭代和随机游走策略获得满意的解决方案。为了加快算法的收敛速度和准确性，不少学者使用混合算法来改进当前的启发式计算模式[12-14]。一般而言，在TSP中，具有100-1000个节点的对象被定义为中等规模的TSP（MTSP），而具有超过1000个节点的对象属于大规模TSP（LTSP）。到目前为止，最大的LTSP记录是大规模超大规模集成（VLSI）焊点路径优化，具有85 900个节点。当前的单一启发式算法具有缓慢收敛和解决LTSP的准确性差的缺点。因此，在处理LTSP时，目前可用的单一启发式算法需要进一步混合和改进[15-17]。
总体而言，有许多关于ACO和其他启发式算法的应用的研究工作，但关于效率和减少ACO算法的时间复杂性的文献相对较少。穆罕默德比较了觅食算法和进化算法的性能，但是这个测试的基准只是连续函数的集合，并且比较没有考虑组合或离散优化领域[18]。 Zhou讨论了基于约束模型最大最小蚂蚁算法（MMAA）的ACO的运行时间，并认为在受限情况下可以观察和测量ACO的效率[19]。
从目前的文献中可以看出，ACO在解决小规模TSP方面具有一定的优势，但随着TSP节点数量的增加，算法的准确性和效率迅速下降。因此，基本的ACO必须与其他算法结合才能解决实际的应用问题[20]。事实上，许多与基本ACO有关的问题仍然是秘密，是ACO的时间复杂性，并找到了一个有效的策略在真正的离散优化过程中减少基本ACO的运行时间。
第2章 解决大规模TSP的基本ACO算法
基本的ACO算法在解决小规模问题时具有快速收敛和高精度的优点。 然而，当TSP的节点数达到或超过100时，基本的ACO算法大多数时间只能找到局部优化解，并且随着节点数量的增加，其收敛速度会降低，这使得它很难满足 组合优化的要求。
2.1蚁群算法基本的概念和步骤
ACO算法的基本概念计算步骤如下[1,2]所述。
定义1 ：TSP：假设C = c1，c2，...，cn是一组N个节点，L = lij ci，cj C是集合C中每两个节点之间的连接集，而dij（i，j = 1,2，...，n）是lij的欧几里德距离 ， 然后dij（i，j = 1,2，...，n）是lij的欧几里德距离
G =（C，L）是有向图。 这个问题的TSP是找到最短的哈密顿环，即最短的闭环，仅在C中遍历N个元素一旦。 TSP可以分为对称和非对称类型，根据是否有距离任何两个节点是否相同。 在这里，我们只研究对称TSP。假设fi（t）是节点i处的蚂蚁数在时刻t，tau;ij是路径（i，j）处的信息素值时刻t，n是TSP的节点尺度，m是总和蚂蚁的数量
时刻t的节点的路径残差信息为由下列公式给出：
在搜索过程中，ant k（k = 1,2，...，m）根据信息计算转移概率每条路径的数量及其启发式功能信息，如图所示
在（4）中，allowedk = {C-tabuk}表示城市节点设置ant k可以为下一步选择元素，alpha;是信息素信息因子或权重，代表信息素在路径中的相对重要性，beta;是期望因子，代表影响两个节点之间的距离由ant决定ķ。启发式函数的一般形式如下所示：
避免路径中残留信息的影响这将完全压倒启发式功能在每个迭代过程中，都需要更新残差当所有蚂蚁完成遍历所有节点时的信息素踪迹。信息素更新策略指的是一个特征人类的记忆，随着时间的流逝，旧记忆消失或甚至被遗忘。 因此，信息素蒸发速率rho;加入ACO和信息素更新规则由（6）和（7）给出。
Dorigo和其他学者提出了三种不同的模型通过他们不同的信息素更新来识别
策略：蚂蚁周期模型，蚂蚁数量模型和蚂蚁密度模型，分别给出了更新公式
通过
在大多数关于ACO算法及其研究的研究中在应用程序中，选择蚂蚁循环模型作为最多有利的信息素追踪更新策略[2,21,22]。因此，我们也选择了蚂蚁循环模型作为对象对照实验。
2.2 ACO算法的时间复杂度分析
经常提到算法的复杂性在文献中，这个术语实际上包括两个时间复杂性和空间复杂性。 时间复杂度分析旨在确定计算时间尺度，即通常用来解释程序执行的次数步骤，从而估计算法的效率。假设n是TSP的节点规模，错误的数字蚂蚁，最大迭代是Imax。 然后，时间解决方案的ACO算法的复杂性分析TSP的结果如表1所示。
表一：蚁群算法的复杂度分析
|
步骤 描述 运行的复杂度 |
|
1 初始化参数 O(n2 m) 2 重置禁忌表 O(n) 3 每只蚂蚁构建其解决方案空间独立 O(n2m) 4 评估本地解决方案并计算信息素 O(n2m) 5 更新路径上的信息素 O(n2) 6 如果t lt; Imax返回步骤二 O(nm) 7 输出结果 O (1) |
从表1中的算法步骤可以看出在Imax代之后，标准的时间复杂性ACO算法可以通过估算
在类似的估计方法下，空间复杂性ACO算法似乎更简单，如图所示
从（11）和（12），在真正的优化应用中，如果我们选择更合适迭代和蚂蚁数，空间复杂性和时间算法的复杂性可以部分降低。虽然时间不对复杂性和空间复杂性可能只会略微降低，但在解决LTSP问题中仍具有实用价值。例如，在处理时超大规模焊接路径优化问题VLSI中有10 000个焊点，如果迭代可以在某些情况下减少，算法的真正运行时间也会随之减少。减少ACO运行时间的方法包括发现适当的迭代时间并确定最小值蚁群的种群大小。对于基本的ACO，Dorigo提出了三种信息素踪迹更新模型。在实际应用中，大多数学者选择了反周期Dorigo推荐的模型，因为它是反周期模型具有比较好的性能另外两个更新策略[1,2]。我们问了以下问题问题：更好的信息素追踪更新策略是否可以发现了什么？更好的信息素更新模型意味着在相同的环境下，ACO的收敛速度可以增加，而算法精度仍然存在不变或精度损失可以忽略不计。这个更新战略似乎对小到没什么意义中等规模的TSP问题。但是，在解决问题上大规模组合优化问题的时候了可以减少运行算法的迭代次数从1 000到500，准确度几乎不变，在a感觉，算法的时间复杂度实际上有减少了50％。虽然文献比较了三种传统信息素更新模型（ant-cycle，ant-quantity和蚂蚁密度是有限的，在经验上，它似乎是有可能加快ACO的收敛速度贪婪的哲学，经典的全球信息素更新模型，被添加到蚂蚁循环模型中;准确性可能也很满意。因此，全球化的新战略提出了信息素更新，命名为ant-cycle-quantity由（13）给出，这是一种混合模型梳理全球和本地更新信息素追踪方法在ACO。
在（13）中，Q具有与传统相同的含义信息素更新策略，代表一个常数总信息素。 Lk代表传球第k蚂蚁的长度。 dij是两者之间的距离第i点和第j点。 lambda;是常数或随机的功能大于1.在传统的antcycle中模型，信息素踪迹均匀更新Kth（t）路径，不考虑本地路径信息，而蚂蚁数量模型只考虑当地路径权重，取决于贪心算法而不是全路径信息。 基于全路径信息，蚂蚁循环量模型考虑到本地路径，在基本的ACO算法的信息素路径更新计算步骤中加入这一考虑。
第3章 控制实验解决蚂蚁循环量模型的TSP问题
3.1实验设计
首先，我们从TSPLIB95选择了（pr1002，d1291，fl1400）作为LTSP的测试地图集。同时，要观察效率可能的波动我们从小规模到大规模的时候选择（bays29，ctsp31，ch130）作为解决方案的测试集中小规模的TSP。 模拟实验的软件是Matlab 7.0和硬件是LENOVA笔记本电脑（CPU：M460,2.53 MHZ，内存：4 GB）和TOSHIBA笔记本电脑（CPU：M370,2.40 MHZ，内存：2 GB）。 为基本ACO选择的参数算法如表2所示。
表二：实验数据
|
参数 描述 默认值 |
|
alpha; 信息素重要程度 1 beta; 启发因子重要程度 5 m 蚂蚁数量 35 P 信息素蒸发因子 0.1 Q 信息素浓度 1 lambda; 全路径调整因素 30 （经验值） runs 在新策略下每个TSP的循环次数 ＞30 |
蚂蚁循环量模型的迭代次数是典型的蚂蚁循环模型的一半。 在小中等规模的TSP解决方案实验，迭代次数将蚂蚁循环模型设定为100，并进行迭代蚂蚁循环量模型的数量为50.要解决在LTSP中，ant-cycle的迭代次数设置为200，并且蚂蚁循环量的迭代次数是相等的用模型实验的结果蚂蚁循环量如图1 - 图12所示。
图1最短长度与路径平均长度（Bays29，iteration =50，蚂蚁循环量模型）
图2基于蚂蚁循环量的Bays29的路径规划（迭代=50）
图3最短路径与路径平均长度（Ctsp31，迭代=50，蚂蚁循环量模型）
图4基于蚂蚁循环量的Ctsp31的路径规划（迭代=50）
图5最短长度与路径平均长度（ch130，迭代=50，蚂蚁循环量模型）
图6基于蚂蚁循环量的ch130路径规划（迭代=50）
图7最短长度与路径平均长度（fr1400，迭代=100，蚂蚁循环量模型）
图8基于蚂蚁循环量的fr1400的路径规划（迭代=100）
图9最短长度与路径平均长度（d1291，迭代=100，蚂蚁循环量模型）
图10基于蚂蚁循环量的d1291的路径规划（迭代=100）
图11最短长度与路径平均长度（pr1002，迭代100，蚂蚁循环量模型）
图12基于蚂蚁循环量的pr1002路径规划（迭代=100）
3.2对两个模型的对比试验分析
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
