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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

面向算法的遗传算法类库设计

遗传算法个体数据结构复杂,随机性是其基本特性。建立一个标准的、开放的遗传算法类库有利于遗传算法的直接应用和在此基础上进一步扩充。本文提出用面向算法的模式将多种数据结构的遗传算法(二进制编码、实型编码、有序编码、变长串编码、遗传程序设计编码等五种算法)统一建模,实现了数据和算法分离,静态数据和动态数据分离,群体和个体分离。这样的类库设计结构更加清晰,实现了易用性、可扩充性与易调试性的统一,可用于对线性规划、旅行推销员问题、数据回归等问题的求解。

神经网络的原理与应用、现状与发展

1984年,美国物理学家Hopfield用模拟电子技术设计出了类似于人脑神经网络的电路结构,这种神经网络电路只需要很短的时间便可以成功地解决传统串行计算机需要几天乃至几年都无法解决的旅行推销员问题,从而触发了一场世界性的神经网络热潮.

一种求解TSP的改进的遗传算法

在应用遗传算法求解TSP问题构造交叉算子时,将贪心算法与边重组结合起来,使得交叉操作能够既继承父代个体中边的设计,又能保留父代的优秀基因,使收敛速度明显加快,且具有较强的全局搜索能力。

车辆运用计划编制方法研究

编制车辆运用计划的目的是在满足车辆使用的制约条件的前提下,为列车运行图上的列车分配车辆,制定更高效的车辆使用顺序。本文主要讨论车辆运用计划的定义、编制计划的算法理论和自动生成运用计划的计算机辅助系统的开发现状。

神经网络最小二乘估计器

Hopfield和Tank证明几种最优化问题能用Hopfield网络快速求解,而Hopfield网络是简单的类似神经元模拟处理机的递推网络。使用Hopfield网络时,目标函数的自变量收敛于超立方体的顶点。因此,它们的应用严格地限于决策最优化问题。在本文中,我们将研究目标函数自变量是实数的问题。基于Hopfield网络的概念,推导了求解最小二乘估计问题的神经网络。用这个网络,目标函数可能收敛于超立方体内的任何点,给出一个具有极大速度的实值解。由于所选择的能量函数的凸状性质,不会出现收敛到局部最小值的问题。我们还介绍了空间迭代搜索方法,以便找到可能存在于空间内任意点的最优解。最后,给出了求解线性系统和参数估计问题的模拟结果。

同步、互斥原理在物流拣选系统中的应用

运用图论中旅行推销员问题的启发式算法解决了物流拣选系统中拣选路径的优化问题,运用操作系统中同步、互斥原理和任务优先级的概念讨论了在访问同一储区产生冲突问题时的解决方法。

飞机着陆调度问题的MPS优化算法研究

以深度优先搜索的隐枚举算法为基础 ,结合 MPS约束、位置冻结限制、优化深度限制 ,使用复杂的软件编码实现了特定于飞机着陆调度问题的优化排序算法 .该算法能满足现实复杂空管条件下的各种限制约束 ,以及多种目标成本函数 ,可应用于静态和动态的实时 ATC自动化系统 ,能有效地减小交通延误和提高着陆容量 .

下世纪的超超级计算机

英特尔公司和Sandia国家实验室的一项最新研究成果把他们的Tflops超级计算机的运算速度提高到令人难以置信的程度,达到了每秒钟1.3万亿次。但他们还没来得及为此加以庆贺,其竞争对手柯瑞研究开发公司就宣布该公司超级计算机的运算速度又将前者提高了一倍。