求解配送＼收集旅行商问题的模拟退火算法

配送＼收集旅行商问题(TSPD)是一类重要的组合优化问题,与车辆路径问题等有着密切的联系.但与传统的旅行商问题(TSP)相比,人们对该问题的研究有限,而且大多假定必须在完成所有的配送需求后,才服务收集需求.文中放松这一约束条件,在扩展Metropolis接受准则的基础上,运用模拟退火算法求得该问题较好的结果.     

基于差分进化算法的多旅行商问题优化

针对所有旅行商路径最大值最小的多旅行商问题,提出改进的差分进化算法优化.在该优化方法中,编码采用实数编码;改进的差分进化算法采用轮盘赌选择;根据旅行商问题的特点,在差分进化算法中增加邻域搜索算子.该方法适于距离对称和非对称的多旅行商问题求解.以距离非对称的多旅行商问题的实例进行了仿真和比较,可以看出所提出的改进差分用来解决多旅行商这类离散组合优化问题是有效的.     

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

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

基因重组算法设计及多目标旅行商问题求解

遗传算法等启发式算法在求解旅行商问题时,存在收敛速度较慢、容易出现过早收敛及算法计算效率较低的问题。在模式理论基础上,提出一种新的基因重组算法。根据优良基因模式,设计模式重组算子,运用重构及进化规划的思想设计算法的个体重构算子和个体选择算子。建立一个多目标旅行商问题模型,分析每一轮计算旅行路线适应度值的差异性,采用熵值法确定路程和费用权重。系列实验表明,基因重组算法在求解多目标旅行商问题时,计算效率远高于比较的算法,收敛速度和求解精度也较一般启发式算法有明显改善。     

自调节种群的演化算法求解旅行商问题

提出了一种自调节种群的演化算法(SaPEA)求解旅行商问题,算法根据当前最优适应度改进的情况提出一种更精细调节种群规模的模式,并根据演化的进程选择强化操作或者分化操作.这样不仅有利于保持种群的多样性开发新的解,还可以加快收敛速度探索到更好的解.同时,还对现有的启发式交叉算子和3-opt局部搜索算法进行了改进.通过对TSPLIB中实例进行测试,表明了SaPEA算法的优越性.     

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

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

一类多旅行商问题的计算及仿真分析

旅行售货商问题(TSP)是组合优化领域的经典问题之一,而考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展.多旅行商问题的特点使其符合许多实际问题,并且通过对多旅行商问题加入约束条件可以使其转化为车辆选择问题(VRPs).针对一类特殊的MTSP问题采用Lin-Kernighan算法进行求解分析,并在此基础之上针对访问城市数目均衡的多旅行商问题采用两阶段方法进行求解,计算仿真结果是令人满意的.     

基于偏好信息的多目标旅行商问题Pareto优化求解

多目标旅行商问题(MOTSP)是经典旅行商问题的扩展,其优化目标包含了距离、成本、收益及风险等多个相互冲突的指标.本文提出了一种基于偏好的Pareto演化算法p-PEA用于建模并求解此NP-hard问题.该优化算法建立在MOTSP的智能体仿真模型之上,从而解决了数学建模不能真实再现实际MOTSP中众多影响因素的问题.通过仿真的方法,算法能够得到MOTSP可行解的各项评价指标值.在此基础士,通过设计演化算法搜索问题的Pareto优化解集.其中,将决策者的决策偏好信息引入到Pareto优化解集的求解过程中,所得结果将更合理.最后,以一个130个城市的旅行商问题为例验证了算法的有效性.     

遗传算法求解旅行商问题时的基因片段保序

针对基于遗传算法的 TSP问题求解 ,尝试了多种遗传操作 ,分析了这些操作在遗传算法中的作用 ,讨论了基因片段保序在利用遗传算法求解 TSP问题中的重要性 .     

分形法与范例库推理相结合进化求解旅行商问题

旅行商问题（Traveling Salesman Problem，简称TSP）是一个典型的组合优化问题，而且是一个NP完全问题。遗传算法（Genetic Algorithm，简称GA）是求解组合优化问题的行之有效的算法。但遗传算法并不是一个完美无缺的算法，它最突出的问题是早熟现象。在解决像旅行商这类组合优化中的NP完全问题。是极易陷入早熟收敛，城市规模越大越难求得最优解。如何缓和旅行商问题中的早熟现象。使问题的解尽可能接近最优解．这是本文研究的主要内容。本文在分形法的基础上提出．了一种分形法与范例库推理相结合的改进方法用以求解TSP问题。首先建立范例库，选取其中优良的个体来指导城市规模大的旅行商问题进行合理的区域分割，由于优良个体与最优值的结构大体相同，相似度大，故可以有效地实施“分而治之”的策略。在寻优进化过程中，还要对范例库进行更新与维护。通过对TSPLIB测试库中的eil51、eil101、ch130和ch150问题的求解，说明该方法在求解TSP问题上是行之有效的。     

嵌套分割算法在旅行商问题上的应用

嵌套分割算法是近年来提出的一种求解大规模优化问题的新型全局优化方法。介绍了嵌套分割算法(NPM)的基本思想,将其应用于求解旅行商问题。首先对嵌套分割算法各个算子的策略进行了分析和比较,在局部搜索中引入2-opt算法,并对初始最可能域加以改良,最后提出算法的并行化实现方法。实验证明嵌套分割算法在解决TSP问题时可以获得高质量的解,并且具有良好的时间性能。