Solving traveling salesman problems using generalized chromosome genetic algorithm

Generalized chromosome genetic algorithm （GCGA） was proposed for solving generalized traveling salesman problems （GTSP） as reported in the authors＇ earlier work. Theoretically, the GCGA could also be used to solve the classical traveling salesman problem （CTSP）, which has not been reported by others. In this paper, the generalized chromosome characteristics are analyzed and the feasibility for consistently solving the GTSP and CTSP is verified. Numerical experiments show the advantages of the GCGA for solving a largescale CTSP.     

遗传算法求解TSP问题的MATLAB实现

以遗传算法求解旅行商问题（TSP）为例,提出一种改进的交叉和变异算子,深入讨论了各个遗传算子的程序实现,并给出其算子的MATLAB程序编码,最后用5个城市的非对称TSP进行仿真分析.结果表明,改进的算法比传统算法收敛速度更快,适应值更优,说明改进算法是有效的,证实TSP问题是遗传算法得以成功应用的典型例子.     

一种改进的蚁群求解算法

为了提高蚁群算法的求解性能,对基本蚁群算法进行了改进.采用上三角的信息素存储形式、改禁忌表为可选表、遗传算法中的交叉及变异、全局更新信息素等做法对基本蚁群算法进行改进,并介绍了在Matlab环境下编程实现的方法及步骤,仿真实验求解了16个城市的TSP问题,得到最短距离为73.988,结果表明了编程思路的正确性及算法的高效性.此改进算法改善了随着求解空间的增加而导致的求解效率低下及因迭代次数的增加而造成的信息素量堆积导致的不成熟收敛,提高了搜索能力及速度,拓展了搜索空间.     

一种改进的遗传算法求解旅行商问题

针对在解决旅行商问题时标准遗传算法效率不高,很容易陷入局部最优解的问题,提出了一种改进的遗传算法. 根据种群个体的多样性和分布情况,提出了判定遗传算法截止代数的方法. 研究结果表明,通过加入了初始化信息,改进交差算子,可提高遗传算法的精确性和收敛性.      

蚂蚁算法在概念设计方案求解中的应用

通过分析概念设计方案求解问题与旅行商问题的相似性，将方案求解问题转化为组合优化的最优路径问题，建立了基于动态规划的解空间模型和基于最长路径的优化模型，利用蚁群系统内在的正反馈寻优机制，将求解旅行商问题的基本蚂蚁算法应用于方案求解的组合优化过程，结合遗传算法的交叉变异操作，提出一种基于改进蚂蚁算法的求解方法，从而快速有效地获得了最优方案解，最后，以压力机的概念设计为例验证了该方法，研究表明，该方法是合理可行的，它可以使方案求解的人工寻优过程实现算法化，并具有较好的可操作性，从而为解决方案优化的组合爆炸问题提供了一种新的思路。     

解TSP问题的蚁群算法及其收敛性分析

研究和证明求解旅行商问题(TSP)的蚁群算法收敛性.针对蚁群算法搜索时间长、收敛速度慢、易陷入局部最优等缺陷,改进Dorigo提出的基本蚁群算法.最后,用典型的旅行商问题CHN144进行仿真实验,结果表明,改进蚁群算法在收敛速度及求解能力上都有较大改善.     

基于人工蜂群算法的TSP仿真

针对标准蚁群算法求解的旅行商问题(TSP)存在收敛速度慢,易陷入局部最优等缺陷,将求解组合优化问题的过程转化为蜜蜂群寻找优良蜜源的过程,并分析了人工蜂群算法及3种基本算法模型,3种引领因子更新策略,讨论了转移因子动态更新公式及状态转移公式,研究了利用该算法求解TSP问题的具体步骤,通过典型的TSP实例进行了仿真实验,结果表明该算法能够克服早熟现象,迭代次数少,收敛速度快,通用性强,比标准蚁群算法具有一定优势.     

蚁群算法的改进及其在TSP问题中的应用

为了克服标准蚁群算法容易陷入局部最优化从而导致算法过早停滞的缺陷,论文引入了城市选择策略的变参数和局部最优搜索策略,同时对信息激素的更新方式提出了相应的改进策略,并应用于对TSP问题的仿真实验.结果表明:改进算法能够加快收敛速度,节省搜索时间,而且能够克服停滞行为的过早出现.     

混沌优化在TSP问题中的应用研究

分析了混沌的基本概念、研究现状、相应的参数选取方法、Lyapunov指数的计算方法等内容,并提出了一种改进的混沌神经网络模型用于解决旅行商问题(TSP),仿真结果较好。     

热轧调度并行处理策略的多旅行商模型

研究了钢铁企业热轧工序的生产调度问题·对于热轧调度,传统的研究和开发方法是采用串行策略:一个班次内的轧制单元计划是依次制定的·这种串行策略实质是一个贪婪程序,所以可能导致局部最优·与这个串行策略相反,从全局最优观点提出了一个并行策略:能够同时产生一个班次中的Ｍ个轧制单元计划·使用并行策略,基于实际生产约束的热轧调度问题可以作为一个多旅行商模型·为了求解这个问题,多旅行商模型变换为单旅行商模型·     

一种基于粒子群算法和Hopfield网络求解TSP问题的方法

针对Hopfield网络求解TSP问题经常出现局部最优解,将粒子群算法(PSO)与Hopfield神经网络结合,提出一种基于粒子群的Hopfield神经网络方法. 实验证实这种方法能够以更大概率收敛到全局最优.     

利用改进匈牙利算法求解旅行商问题

针对传统的匈牙利算法在求解旅行商问题(Travelling Salesman Problem,TSP)时会导致多回路闭合的问题,提出了破环机制,设计了破环匈牙利算法。通过采用分配问题的描述方法对旅行商问题进行建模,并建立二者之间的转换关系,论证了TSP可行解的充分必要条件是对应分配问题的可行解与辅助边结合后仅包含一个环路,对6个标准旅行商进行测试和对比分析,验证算法的有效性。实验结果表明:在不同的数据集中,改进匈牙利算法能有效求出TSP问题的解。     

基于受限制候选表的反应蚁群算法求解TSP问题

针对蚁群算法求解大规模旅行商问题(TSP)时会出现计算时间长等问题,将反应贪婪随机适应搜索机制引入蚁群算法中,提出了一种基于受限制候选表(RCL)的反应蚁群算法,其中的候选表大小可以随机选取.将蚂蚁要选择的下一点的范围控制在RCL中,避开了许多局部极小点,克服了最近邻居候选表的不足,提高了搜索效率.对大规模TSP问题进行仿真实验的结果表明该算法具有良好的性能.     

用基于蚂蚁算法的混合方法求解不确定TSP问题

首次提出不确定旅行商问题模型, 此模型将路径长度看作动态可变的, 并考虑了交通运行中的不确定因素, 比经典旅行商(TSP)问题更具有灵活性及实用价值, 利用此模型得到的结果更适于指导车辆对运行路线的选择. 同时使用一种基于蚂蚁算法的混合方法求解不确定旅行商问题, 即引入3-opt方法对问题求解进行局部优化. 实验结果显示, 该方法能够加速蚂蚁算法的收敛性.     

A Multi-Agent Approach for Solving Traveling Salesman Problem

The traveling salesman problem （TSP） is a classical optimization problem and it is one of a class of NP- Problem. This paper presents a new method named multiagent approach based genetic algorithm and ant colony system to solve the TSP. Three kinds of agents with different function were designed in the multi-agent architecture proposed by this paper. The first kind of agent is ant colony optimization agent and its function is generating the new solution continuously. The second kind of agent is selection agent, crossover agent and mutation agent, their function is optimizing the current solutions group. The third kind of agent is fast local searching agent and its function is optimizing the best solution from the beginning of the trial. At the end of this paper, the experimental results have shown that the proposed hybrid ap proach has good performance with respect to the quality of solution and the speed of computation.     

新型混沌粒子群算法在TSP中的应用

针对旅行商问题,提出一种结合混沌优化和粒子群算法的新型混沌离散粒子群方法(CIPSO)。新算法根据此类组合优化问题解的固有地形特征,利用混沌运动的遍历性、随机性等特点进行求解,其基本思想是在求解过程中对粒子进行混沌扰动避免陷入局部最优,并引入群体间粒子的交叉作用来提高寻优效率。通过与遗传算法、蚁群算法和模拟退火算法等比较以及不同TSP问题的仿真实验发现,该方法是一种能进行有效优化的新方法。     

一种求解TSP初始化种群问题的邻域法

针对遗传算法求解TsP问题时存在初始化种群敏感的问题,提出一种初始化种群的邻域法,在该方法中,从某个城市出发其下一站不是其最近城市,而在比最近城市稍远的邻域范围进行随机选取.邻域法既能提取局部优化路径特征信息,又具有多样性.用4个通用的TSPI.IB标准实例进行实验验证.邻域法初始化种群相比随机法,4个实例的最优解平均改进值达到了46.3%,最优解的质量有较大改善.仿真实验结果验证了邻域法初始化种群的有效性.     

遗传算法进化中积木块的识别和利用研究

提出了一种基于积木块识别的遗传算法，该算法通过对进化过程中的候选积木块进行识别与利用来加速搜索，从而避免遗传算法随机搜索的盲目性．利用经典的对称旅行商问题求解过程来测试各种识别方法，再利用积木块的识别结果改进原有遗传算法，包括改进积木块的识别率以及基于积木块的交叉、变异算子．与基本遗传算法的计算结果对比分析表明，所提算法可显著提高遗传算法的搜索效率，减小遗传算法随机搜索的波动性．     

不一致连续Hopfield网络及其应用

针对一致连续Hopfield网络容易陷入局部最小和不合理解的现象,给出了不一致连续Hopfield网络的能量分析,得到了使网络能量函数上升、下降和不变的条件.在此基础上,通过衰减自反馈,提出了求解旅行商问题(Traveling Salesman Problem,TSP)的新网络.通过仿真证实,该网络可有效地求解TSP问题.     

一个求解旅行商问题的松弛算法

在旅行商问题（TSP）的传统模型中，子回路消除约束的数量随着问题规模的增大具有指数增长的特性，极大地限制了TSP的求解效率。基于TSP的松弛问题，本文提出一种有效生成子回路消除约束的方法。该方法通过求解一系列线性整数规划，来实现TSP的精确快速求解。数值结果表明，本方法相比于采用Cplex直接求解，能够更快地找到TSP的最优解。