基于多顶点替换策略的迭代局部搜索算法解决覆盖推销员问题

覆盖推销员问题(Covering Salesman Problem,CSP)是著名的旅行商问题的一个变体,是NP难问题。给定一组顶点和每个顶点相关联的预定覆盖半径,CSP的目标是在顶点子集上找到一个最短长度的哈密顿回路,使每个顶点被访问或者在被访问顶点的覆盖范围内。为提升搜索候选顶点集的质量,提出一种基于多顶点替换的搜索策略,并将该策略引入到迭代局部搜索算法解决CSP。所提CSP算法通过扰动过程和改进过程的迭代探索邻域最优解,其中扰动过程将搜索发散到未探索的区域,改进过程提升解的质量。实验结果表明,多顶点替换方法相比“移出-重新插入”过程可以获得更高质量的候选顶点集。所提CSP算法在寻优的正确率上取得了不错的成效,尽管运行速度与其他启发式算法相比有差距,但可以在合理的运行时间内解决CSP。

关于旅行推销员问题的一个算法

通过圈上结点下标自足方法 ,给出了一个关于旅行推销员问题的算法 .尽管该算法实质上无法改变问题的 NP-完全性的难度 ,但较分支定界法的执行速度快 。

旅行推销员问题凸包方法的性能比分析

在欧几里德平面上证明了旅行推销员问题的凸包方法的性能比上界为n/2,同时给出了凸包随意插入算法的性能比可以接近n/2的例子。另外,对凸包增量最小插入法、凸包最近插入法及凸包最近加入法给出了性能比不超过3的证明。

基因多效性人口增量学习算法及其在旅行推销员问题中的应用(英文)

本文扩展了基于人口的增量学习算法使其每个基因可呈现多个品质值 ,这反映了自然演化系统中基因型和表现型的多向性和多源性 ,提出了用熵来判断进化过程的可进化性 .用该方法求解典型的组合优化问题———旅行推销员问题 。

协同神经网络求解流动推销员问题方法--确保单回路的神经网络方法

神经网络方法求解流动推销员问题(Travel Salesman Problem,简称TSP问题)时,往往产生不满足TSP的单回路约束的不可行解。基于协同神经网络的方法解决TSP,并设计了一个回路合并算法,确保得到满足TSP的单回路约束的解。通过算例进行数值模拟,并且比较了新算法、标准遗传算法和标准模拟退火算法的求解结果。实验结果表明,说明该方法在求解TSP问题上是行之有效的。

旅行推销员问题的凸包收缩法

本文提出一种用凸包收缩来解决旅行推销员问题。首先形成一个凸包初始环路。然后 ,逐个考察凸包内的点 ,按照增加值从小到大的顺序依次插入 ,直至考察完所有的点。从而得到一个包含所有点的环路 ,即旅行推销员问题的一个满意解。

旅行推销员问题的算法综述

本文综述了旅行推销员问题 (TSP)近几十年来的算法研究进展 。

遗传算法求解旅行推销员问题时算子的设计与选择

主要讨论了在用遗传算法求解ＴＳＰ时，在算子的设计和选择方面应该注意的一些问题，并且给出了一些算子的分析和设计实例。

用改进的噪声混沌神经网络模型求解组合优化问题

混沌模拟退火方法 (CSA)在解决组合优化问题时有很强的搜索能力 .其中系数α代表能量函数对动态性的影响 ,α太大 ,能量函数影响太强 ,以至于无法得到暂态混沌现象 ,α太小 ,能量函数的影响太弱 ,从而无法收敛到最优解 .提出了一种自适应参数动态调整方法 ,随着能量函数的逐渐减小 ,通过加大 α,保持能量函数在整个搜索过程中对搜索动态性保持一定的影响 ,从而加快搜索速度 ,同时保持搜索的精度 .计算机仿真结果表明 ,在保持和增强搜索能力的同时 ,文中动态参数算法所用时间与现有的算法相比可以减少 2 0 %～ 5 0 % .

货郎问题填数破圈法的计算机实现

货郎问题填数破圈法的计算机实现张乃书一、货郎问题及其数学模型运筹学中有一个著名的问题叫货郎问题（Ｔｒａｖｅｌｉｎｇ－ｓａｌｅｓｍａｎＰｒｏｂｌｅｍ）：假设有一个货郎从ｎ个城市中的某个城市出发，遍访其余ｎ一１个城市，每个城市去一次，并且仅去一次，然后回...

基于遗传算法的约束性多TSP问题及其应用

针对一类具有约束条件的汽车调度问题 ,提出了约束性的多重 TSP(CMTSP)问题及其模型 ,给出了一种遗传算法解法。对比实验结果表明 :遗传算法具有比启发式算法更好的结果。

TSP问题的一种新解法及其神经网络实现

本文给出一种解TSP问题的新方法,在保证路径有效的前提下,所求出的准最优解优于或至少近似于用以前各种方法所求出的解.特别是避免了用Hopfield模型时常常存在的许多不足.文中同时给出这一算法的神经网络实现与仿真结果.

货郎担问题的对角线生成和2-最优改进回路解法

第Ⅰ部分以十个城市的货郎担题为例,提出了一个快速求得较好的初始可行解的启发式方法——对角线生成法。该方法可以与解货郎担题的任何一种改进回路的方法结合使用。从而求得货郎担题的最优或接近最优的解。第Ⅱ部分将以上的方法与2-最优改进回路的方法相结合,计算了十个文献中报导的货郎担题,其规模从十个城市到318个城市。计算结果表明该方法相对于别的方法而言,其主要优点是:它的计算时间随着城市个数的增加而增加的速度较慢,因而适用于解几百个城市的大规模的货郎担题。结论本文所介绍的方法是一种解货郎担题,尤其是大规模货郎担题的快速而有效的计算机算法。

向蜜蜂学习或许可解决堵车问题

英国一项研究表明,在花丛中飞来飞去的小蜜蜂显示出了轻易破解"旅行商问题"的能力,而这是一个吸引全世界数学家研究多年的大问题,如能理解蜜蜂的解决方式,将有助于人们改善交通规划和物流等领域的工作。"旅行商问题"常被称为"旅行推销员问题",是指一名推销员要拜访多个地点时,如何找到在拜访每个地点一次后再回到起点的最短路径。

混沌神经网络模型中的模拟退火策略

混沌模拟退火法 ( CSA)是一种能有效解决局部极值问题的全局最优化算法 ,其神经元的自反馈连接权值 zi 的演变函数称为退火函数 ,它影响暂态混沌神经网络 ( TCNN)优化方法的准确性和计算速度 .文中通过比较单细胞 TCNN模型 CSA中两种最常用的退火函数 (线性退火和指数退火函数 ) ,给出了一种新的分段指数退火函数 ,使得算法的收敛速度加快 ,搜索精度增加 .并利用推销员问题 ( TSP)

CPN原理及其在人工智能中的应用

1 引言 Petri网理论是由联邦德国的Carl Adam Petri于1962年在其博士论文中提出的一种建模方法.最初的网理论称为条件/事件网(CE-nets).在随后的几年中,人们对新的网模型、网的基本概念及分析方法等进行了大量的研究.其中最有影响的是位置/变迁网(PT-nets),PT-nets后来命名为Petri网(Petri Net).这些早期的网模型在理论上都归结为基本网(EN-nets).研究者通过对PT-nets进行了扩展,在网中增加了变迁的优先级、时间延迟、全程变量等一些概念以满足解决实际应用建模的具体要求.

具有能量奖励策略的微正则退火算法

为提高微正则退火算法求解旅行推销员问题的最终解质量,提出一种对妖的能量进行奖励的策略,在拒绝状态时增大妖所携带的能量,用以提高脱离局部极值的能力.按照能量奖励后是否做限界检查,给出了无上界约束和有上界约束两种实施方式.仿真显示无上界约束的能量奖励策略能够提高最终解的质量,而有上界约束不能提高算法性能.为加快应用该策略后的收敛速度,设计了一种容忍机制,降低了搜索到最优解时的平均目标评价次数.

TSP邻近算法在Euclid平面上的性能比分析

旅行推销员问题(TSP)邻近算法的性能比已经被证明有一个关于点数的对数函数上界,本文就该方法在欧几里得平面上给出了性能比的一个对数下界。

在TSP算法中确定初始可行解的一种新方法

在用启发式算法解决旅行推销员问题时要用到初始可行解。本文首次用聚类分析法研究出了一种确定初始可行解的新方法。用该方法确定的初始可行解可以看作为局部最优解,从而使搜索时间缩短;提高运算速度。