Improved ant colony optimization algorithm for the traveling salesman problems

Ant colony optimization (ACO) is a new heuristic algorithm which has been proven a successful technique and applied to a number of combinatorial optimization problems.The traveling salesman problem (TSP) is among the most important combinatorial problems.An ACO algorithm based on scout characteristic is proposed for solving the stagnation behavior and premature convergence problem of the basic ACO algorithm on TSP.The main idea is to partition artificial ants into two groups: scout ants and common ants.The common ants work according to the search manner of basic ant colony algorithm,but scout ants have some differences from common ants,they calculate each route's mutation probability of the current optimal solution using path evaluation model and search around the optimal solution according to the mutation probability.Simulation on TSP shows that the improved algorithm has high efficiency and robustness.     

求解TSP的改进人工鱼群算法

利用遗传算法的交叉算子,并引入去交叉策略,对人工鱼群算法进行了改进,提出了一种改进型人工鱼群算法,并将该算法用于求解旅行商问题(traveling salesman problem,TSP)这一经典的NP难问题。通过实验仿真与目前TSP已知最优解进行对比分析,结果表明,改进后的人工鱼群算法在种群规模较小,迭代次数较少的情况下也可以收敛到已知最优解。     

一种求解TSP的生物信息启发式遗传算法

遗传算法是解决旅行商问题（traveling salesman problem，TSP）的通用路径优化算法之一。为解决传统遗传算法收敛速度慢且解不稳定的问题，提出一种生物信息启发式遗传算法（bioinformation heuristic genetic algorithm，BHGA）。通过优化适应度函数和初始种群，引入生物信息学中的基因序列对比手法进行交叉重组排序，采用基因逆转操作进行变异，对遗传算法进行改进，使算法能够加快收敛速度，得到更优路径解。利用BHGA对TSPLIB数据库中算例进行求解，实验仿真结果表明：该算法在中小型规模的TSP中求解效果好且结果稳定。     

一种基于能量熵的快速遗传算法研究

在分析标准遗传算法的优越性与存在不足的基础上,提出了对遗传算法的改进方法.将能量熵的选择加入到遗传算法的退火选择中,以充分地探索解空间,保持种群的多样性.将伪梯度搜索应用于对个体的邻域搜索,利用当前种群的有效信息及系统信息,提高寻优速度.对典型的TSP问题及一实际电力网络故障恢复的仿真研究表明,改进算法全局优化性能优于启发式遗传算法及标准、退火遗传算法,同时使收敛速度有了较大的提高.     

模拟退火算法的一种参数设定方法研究

模拟退火算法在有限计算量条件下的收敛性能对自身参数有很大的依赖性,这使得参数设定问题成了算法应用过程中的一个关键环节。考虑到模拟退火算法本身的随机性,将其参数设定问题描述为随机优化问题,提出一种系统可靠地解决该问题的混合优化算法,即基于序的巢分区算法,该算法继承了序优化算法的快速收敛性及巢分区算法的全局搜索特性,能够有效解决复杂的随机组合优化问题。以典型旅行商问题为算例的仿真结果检验了方法的高效性与可靠性。     

基于蚁群优化算法的0-1背包问题求解

蚁群优化算法在求解旅行商问题、指派问题、Job-shop调度问题和网络路由问题等获得了极大的成功．将蚁群优化算法应用于0—1背包问题，首先将0—1背包问题表示成相应的构造图，并针对该图设计了两个状态转移公式，蚂蚁根据这两个状态转移公式在带权图中移动直到死亡．此时，蚂蚁所走过的路径即构成背包问题的一个可行解．仿真实验对该算法的参数进行了讨论，再与遗传算法进行比较，结果显示该算法具有较高的性能．     

小规模TSP边集裁剪策略研究

由于旅行商问题的计算复杂性,随着问题规模的扩大,精确算法逐渐不能在较短的时间内得到或不能得到问题的全局最优解.通过对该类问题的高质量优化解与全局最优解之间关系的分析,基于概率统计原理建立了问题的简化初始边集,并在分支裁减法中应用了合理的动态上界调整,新建立的混合分支裁减法实现了对小规模旅行商问题的快速精确求解.     

圆排列问题的蚁群模拟退火算法

首先把圆排列问题转化为旅行商问题,然后利用模拟退火算法是求解此问题.针对模拟退火算法对选择试验解比较敏感这一问题,文章提出六种找领域解算法.算法的分析和测试表明,利用了城市间距离大小的信息的蚁群模拟退火算法 是一种简单有效的算法.     

对一类带聚类特征TSP问题的蚁群算法求解

蚁群算法是近几年提出的一种新型的模拟进化算法,初步的研究表明该算法具有极强的鲁棒性和发现较好解的能力,但同时也存在收敛速度慢的缺点。针对带聚类特征的TSP问题,提出了一种新型的蚁群算法。该算法利用TSP问题本身所具有的聚类特征,从数据域上将其分解成多个子问题,对每个子问题分别采用蚁群算法并行求解,最后将所有子问题的解按一定规则合并成问题的解。对带聚类特征TSP问题的仿真实验表明该算法的收敛速度得到了极大的提高。     

Global Convergence Analysis of Non-Crossover Genetic Algorithm and Its Application to Optimization

Selection, crossover, and mutation are three main operators of the canonical genetic algorithm (CGA). This paper presents a new approach to the genetic algorithm. This new approach applies only to mutation and selection operators. The paper proves that the search process of the non-crossover genetic algorithm (NCGA) is an ergodic homogeneous Markov chain. The proof of its convergence to global optimum is presented. Some nonlinear multi-modal optimization problems are applied to test the efficacy of the NCGA. NP-hard traveling salesman problem (TSP) is cited here as the benchmark problem to test the efficiency of the algorithm. The simulation result shows that NCGA achieves much faster convergence speed than CGA in terms of CPU time. The convergence speed per epoch of NCGA is also faster than that of CGA.     

一种求解旅行商问题的交叉禁忌搜索

提出一种改进的禁忌搜索（TS）一交又禁忌搜索（CTS），并用于混合优化问题旅行商问题（TSP）的求解。CTS主要包括集中策略和分散策略，采用选择规律的改变促进移动的混合，集中策略增强了算法的局部搜索能力；分散策略是用于开辟新的搜索空间，在CTS中，采用遗传算法中的交叉算子作为分散策略，优解选择法作为集中策略。CTS、标准TS、带集中裳略的TS和蚁群算法用于求解相同的TSP例子，所用例子都是来自TSPLIB例子库和Fogel路径。求解结果显示了CTS的性能优于其它算法。     

解旅行商问题的一个新的遗传算法

对旅行商(TSP)问题设计了一个新的遗传算法.首先,对n个城市的旅行商问题设计了一个新的编码方法,并且对这种编码方法,给出了简便的解码方法.其次,针对编码的特点,设计了一种新的、有效的杂交算子和变异算子,这些算子均能直接产生可行的后代.为提高杂交算子的搜索能力,结合了一个局部搜索技术来改进杂交算子.在此基础上,提出了求解TSP的一个新的遗传算法,并证明了其全局收敛性.为了验证算法的有效性,对10个国际标准算例(城市规模从14到1000)进行了计算机仿真,结果表明算法是有效的.     

自适应并行机制的改进蚁群算法

针对蚁群算法存在停滞现象的缺点,以及如何有效提高蚂蚁代理的搜索能力问题,提出了一种具有自适应并行机制的选择和搜索策略。该策略通过将蚁群划分为若干个子群,不同子群的蚂蚁释放不同类型的信息素,引入了吸引因子和排斥因子,实现了一种多蚁群并行选择策略,以加强其全局搜索能力。以对称旅行商问题(traveling salesman problem, TSP)测试集为对象,将改进算法与现有蚁群优化算法进行了测试比较。实验结果表明,改进后的算法具有优良的全局优化能力,有效防止了停滞现象。     

求解TSP问题的最近邻域与插入混合算法

研究了求解旅行商问题(TSP)的构建型启发式算法中的最近邻域算法和插入算法的特点, 集最近邻域算法求解速度快、插入算法求解质量高的优点, 提出了一种最近邻域与插入混合算法. 分析了混合算法的合理性、复杂度及参数取值, 并分别采用以上三种算法求解了TSPLIB标准库中多个算例, 结果表明混合算法的求解速度接近最近邻域算法, 对城市数量小于1000的小规模TSP问题的求解质量与插入算法相当, 而对大规模TSP问题的求解质量明显优于插入算法.     

对称型TSP下界的快速估算法

在数学推导和证明的基础上,给出了一个求解对称型TSP问题下界的快速算法,利用该算法求解了TSP标准问题库中部分对称型问题,给出了计算结果并与标准问题库中公布的最好解进行了比较,获得了令人满意的效果.     

基于递阶遗传算法的一类多旅行商问题优化

针对最小化单个旅行商路程的多旅行商问题,提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点,采用一种递阶编码方案,此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题不需设计专门的遗传算子,操作简单,并且解码方法适于求解距离对称和距离非对称的多旅行商问题。计算结果表明,递阶遗传算法是有效的,能适用于优化多旅行商问题。     

解旅行商问题的混沌蚁群算法

利用混沌运动的遍历性、随机性和规律性等特点,提出了一种求解旅行商问题的混沌蚁群(CACO)算法.该算法的思想是采用混沌初始化进行改善个体质量和利用混沌扰动避免搜索过程陷入局部极值.与模拟退火算法、标准遗传算法进行比较,仿真结果表明该方法是一种简单有效的算法.     

基于仿真的遗传算法求解动态旅行商问题

以标准旅行商问题的扩展问题--动态旅行商问题为对象,分析了动态旅行商问题中由于道路流量实时变化所引起的标准旅行商问题的数学建模与优化求解的问题复杂性.通过建立其计算机仿真模型再现动态旅行商问题中众多复杂的非平稳、随机因子.进而提出了基于计算机仿真模型的遗传算法,即根据计算机仿真的结果,应用改造后的遗传算法搜索原问题的优化解.最后,在多智能体仿真平台上实现该优化算法,并以此求解20个城市的动态旅行商问题,计算结果验证了算法的有效性.     

基于改进型能量函数和瞬态混沌神经网络的TSP问题研究

针对传统神经网络在搜索NP类问题的解时易陷于局部最优点的不足,提出了一种基于改进型能量函数(IEF)和瞬态混沌神经网络(TCNN)的优化模型,将此应用于旅行商问题(TSP)的求解,并和传统神经网络优化方法进行了比较。仿真研究结果表明,该论文所提出的方法在解的可行性以及全局最优解的获取能力方面都有很大优势,收敛速度和准确度也令人满意。     

基于蚁群并行算法的电气接线路径优化及仿真

继电控制系统中元件的连接关系可以使用网络拓扑图描述，元件间的接线路径优化类似于旅行商(TSP)问题，属于NP完备的组合优化问题。本文将ACS蚁群算法引入接线路径优化，建立了适用于继电系统接线路径优化的计算模型，并在MPI(消息传递界面)的基础上实现了算法的并行化。通过对算法初始参数进行仿真分析，确定了各参数的最佳取值范围，实验结果证明，在参数选择适当的情况下，ACS蚁群算法具有很好的全局搜索能力和较快的收敛速度。