检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

针对模糊需求的VRP的两种2-opt算法

电子学报 2001年第8期29卷 1035-1037页

作者：祝崇隽刘民吴澄吴晓冰清华大学自动化系北京100084 中兴通讯有限公司上海二所上海200233

本文研究了一类客户需求不确定的VRP(车辆路径问题 ) .在算法中 ,引入了伪出发点和新的聚类判定规则 ,将聚类和排序有机的结合起来 ,有效地处理了全局采样和局部搜索之间的矛盾 .给出了基于可能性分布的 2 opt算法和基于需求上界的 2 ... 详细信息

本文研究了一类客户需求不确定的VRP(车辆路径问题 ) .在算法中 ,引入了伪出发点和新的聚类判定规则 ,将聚类和排序有机的结合起来 ,有效地处理了全局采样和局部搜索之间的矛盾 .给出了基于可能性分布的 2 opt算法和基于需求上界的 2 opt算法 ,并用模糊模拟技术进行了实验 .大量的实验结果表明 ,这两种方法明显优于这个领域现有的算法。

关键词： VRP问题可能性分布 2-opt算法

在线全文

学校读者我要写书评

暂无评论

保存基因的2-opt一般反向差分演化算法

小型微型计算机系统 2012年第4期33卷 789-794页

作者：刘罡李元香郑昊武汉大学软件工程国家重点实验室武汉430072 中国地质大学计算机学院武汉430074

为了进一步提高差分演化算法的性能,提出一种采用保存基因的2-opt一般反向差分演化算法,并把它应用于函数优化问题中.新算法具有以下特征:(1)采用保存被选择个体基因的方式组成参加演化的新个体.保存基因的方法可以很好的保持种群多样性... 详细信息

为了进一步提高差分演化算法的性能,提出一种采用保存基因的2-opt一般反向差分演化算法,并把它应用于函数优化问题中.新算法具有以下特征:(1)采用保存被选择个体基因的方式组成参加演化的新个体.保存基因的方法可以很好的保持种群多样性;(2)采用一般反向学习(GOBL)机制进行初始化,提高了初始化效率;(3)采用2-opt算法加速差分演化算法的收敛速度,提高搜索效率.通过测试函数的实验,并与其他差分演化算法进行比较.实验结果证实了新算法的高效性,通用性和稳健性.

关键词：差分演化一般反向学习 2-opt算法保存基因函数优化

A Hybrid Method Based on Christofides and 2-opt Algorithm for Solving Travelling Salesman Problem

在线全文

学校读者我要写书评

暂无评论

A Hybrid Method Based on Christofides and 2-Opt Algorithm fo...

作者： MD SALAH UDDIN BHUIYAN 华南理工大学

学位级别：硕士

旅行商问题(TSP)是计算机科学中的经典优化问题,在物流、交通等诸多领域都有应用。在本研究中,我们比较了解决TSP的三种算法的性能:Christofides算法、最近邻算法以及Christofides和2-opt算法相结合的混合方法。在本研究中,将这两种算... 详细信息

旅行商问题(TSP)是计算机科学中的经典优化问题,在物流、交通等诸多领域都有应用。在本研究中,我们比较了解决TSP的三种算法的性能:Christofides算法、最近邻算法以及Christofides和2-opt算法相结合的混合方法。在本研究中,将这两种算法的性能与结合了Christofides和2-opt算法的混合方法进行了比较。2-opt算法是一种局部搜索启发式算法,它通过交换相互交叉的边对来迭代改进解决方案。结果表明,混合方法优于其他两种算法,平均错误率为6.47%,明显优于最近邻算法的24.77%和Christofides算法的12.39%错误率。混合方法通过使用Christofides算法构建初始解,然后使用2-opt算法进一步细化解来实现此目的。我们还发现,混合方法在不同的TSP实例特征(例如规模、复杂性和城市之间的距离分布)上表现良好。此外,我们证明,通过调整参数和测试Christofides和2-opt算法的不同组合来微调混合方法可以进一步提高解决方案质量和计算效率。这些发现表明,所提出的混合方法可能是解决TSP的更有效方法,特别是对于问题的大型实例。该研究还强调了结合不同算法和技术以在优化问题中获得更好性能的潜在好处。我们的研究强调了探索不同算法方法来解决TSP并微调其参数以获得最佳性能的重要性。基于Christofides和2-opt算法的混合方法为TSP提供了一种有前途的解决方案,并且未来通过添加机器学习技术可以进一步提高其性能。

关键词：组合优化混合方法旅行商问题 TSP Christofides算法 2-opt算法最近邻算法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

求解多旅行商问题的改进分组遗传算法

电子与信息学报 2017年第1期39卷 198-205页

作者：王勇臻陈燕于莹莹大连海事大学交通运输管理学院大连116026

该文针对总路径长度最小的多旅行商问题,提出一种改进分组遗传算法。在该算法中,设计了一种有序分组编码,采用新编码方式的个体与多旅行商问题有效解之间具有一一对应的关系。为了减少算法的运行时间,根据编码的特点构造了一种快速交叉... 详细信息

该文针对总路径长度最小的多旅行商问题,提出一种改进分组遗传算法。在该算法中,设计了一种有序分组编码,采用新编码方式的个体与多旅行商问题有效解之间具有一一对应的关系。为了减少算法的运行时间,根据编码的特点构造了一种快速交叉算子。同时,结合贪婪算法和2-opt算法设计了一种新的局部搜索算子,以提高算法的收敛精度。实验结果分析表明,所提算法能够有效地解决多旅行商问题,具有可靠的全局收敛性,较高的计算效率。

关键词：分组遗传算法多旅行商问题编码 2-opt算法

在线全文

学校读者我要写书评

暂无评论

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

系统仿真学报 2008年第24期20卷 6858-6861,6870页

作者：刘昌军苏琴卫军胡陶维丽西安交通大学系统工程研究所机械制造系统工程国家重点实验室西安710049

嵌套分割算法是近年来提出的一种求解大规模优化问题的新型全局优化方法。介绍了嵌套分割算法(NPM)的基本思想,将其应用于求解旅行商问题。首先对嵌套分割算法各个算子的策略进行了分析和比较,在局部搜索中引入2-opt算法,并对初始最可... 详细信息

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

关键词：嵌套分割算法旅行商问题 2-opt算法并行算法

在线全文

学校读者我要写书评

暂无评论

基于干扰管理的车辆故障救援模型

系统工程 2010年第6期28卷 111-116页

作者：蒋丽丁斌臧晓宁中国科学技术大学管理学院安徽合肥230026

针对物流配送过程中的车辆故障问题,制定救援车辆要到故障车辆处装货的邻近救援策略。以总配送距离最短、受扰车辆数最少和总配送延迟最小为目标,构建车辆故障邻近救援模型。设计遗传算法和2-opt算法结合的混合遗传算法求解模型,得出车... 详细信息

针对物流配送过程中的车辆故障问题,制定救援车辆要到故障车辆处装货的邻近救援策略。以总配送距离最短、受扰车辆数最少和总配送延迟最小为目标,构建车辆故障邻近救援模型。设计遗传算法和2-opt算法结合的混合遗传算法求解模型,得出车辆发生故障以后对系统负作用最小的调整方案。最后,通过仿真算例对比分析该邻近救援策略和车辆增派策略。

关键词：干扰管理车辆故障车辆路径问题遗传算法 2-opt算法

在线全文

学校读者我要写书评

暂无评论

车辆路径问题的一种启发式解法

上海交通大学学报 2002年第Z1期36卷 96-98页

作者：吕新军韩兵上海交通大学自动化研究所上海200030

研究了带有容量约束的车辆路径问题(VRP),在预先不确定车辆数目的情况下,提出将聚类方法、禁忌搜索方法和2-opt方法集合对VRP求解.分析和实验结果表明,该方法对VRP,尤其是大规模的VRP是有效的.

关键词：车辆路径问题聚类算法禁忌搜索 2-opt算法

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

双种群混合遗传算法的研究及应用

双种群混合遗传算法的研究及应用

作者：何昌武广西大学

学位级别：硕士

GA是一种自适应全局搜索算法,它以个体为基本搜索单位,模拟物种进化过程进行搜索。它通过编码技术将问题空间转换为个体编码,将适应度函数取代目标函数作为个体优劣的衡量标准,把对问题的求解过程转换成对最优适应度个体的搜索过程。算... 详细信息

GA是一种自适应全局搜索算法,它以个体为基本搜索单位,模拟物种进化过程进行搜索。它通过编码技术将问题空间转换为个体编码,将适应度函数取代目标函数作为个体优劣的衡量标准,把对问题的求解过程转换成对最优适应度个体的搜索过程。算法不依赖于问题本身的特性,通过选择操作,种群一直朝着最优解的方向不断进化,体现出较高的自适应性,这就使得遗传算法在很多领域有着广泛的应用。遗传算法以种群为单位进行搜索,个体进化具有很高的独立性,每个个体进化过程就是对问题解的一个独立搜索过程,可以说,遗传算法是一种以种群规模大小为并行规模的隐藏式并行算法,使得遗传算法具有较强的全局搜索能力,然而,缺乏局部搜索能力的遗传算法,在对实际问题进行求解时缺乏收敛力度,往往在进化很多代之后,也无法精确收敛于最优解。造成这种现象的另一个原因是种群在进化到中后期时,种群间的相似度会不断提高,种群进化当中出现大量的近亲繁殖现象,种群多样性被破坏,从而使得算法收敛于局部最优解或最优解附近。本文根据遗传算法本身存在的缺陷,提出了双种群混合遗传算法DPHGA,通过构造双种群并行进化,保证种群多样性,避免种群近亲繁殖,提高算法效率。将局部优化算法加入遗传算法当中,构造混合遗传算法,在保证遗传算法全局搜索能力的同时,增强局部搜索能力。DPHGA算法是以遗传算法为框架的混合式算法,算法能够通过不同编码方式,应用于对不同的实际问题的求解,本文研究内容包括两个部分：1.无约束函数优化部分,为研究便利,本章选择双决策变量多模态的无约束函数优化问题作为研究对象。采用扩展性和可操作性非常强的二进制编码方式进行编码,通过随机匹配复制原则构造双种群,并采用改进的随机联赛选择算子,保证种群多样性的同时,能有效提高交叉操作的效率,交叉操作和变异操作均根据问题特性进行设计,加入模拟退火算法以提高DPHGA算法的局部搜索能力。最后,对3个国际算例的测试结果与文献对比,证实了DPHGA算法具有较强的收敛能力与精确度。2. VRPTW部分,针对带时间窗车辆路径问题,先对约束进行处理,对载重约束,在解码部分通过贪婪算法进行处理,而对时间窗约束,则通过惩罚函数法进行处理,优化处理仍采用DPHGA算法。首先对所有客户进行编号,采用自然数编码方式对配送的所有客户进行编码,并针对编码的不同,设计出不同的交叉变异算子,在变异算子中加入2-opt算法思想,取代模拟退火算法作为局部搜索算法,增强算法的局部搜索能力。最后,为进一步保证种群的多样性,算法加入重生策略,将种群中相同个体进行重生操作。算法通过对2个VRPTW常用算例进行测试,测试结果优于文献中算法。

关键词：遗传算法无约束函数优化模拟退火算法 VRPTW 贪婪算法惩罚函数 2-opt算法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于多目标方法的旅行商问题复杂度研究

基于多目标方法的旅行商问题复杂度研究

作者：孙文成大连理工大学

学位级别：硕士

NP-hard组合优化问题一直都是备受关注的问题,越来越多的启发式算法被提出来解决这些问题,针对某一类组合优化问题,这里有很多种启发式算法可以选择,因此算法选择问题成为现在研究的热点。本文旨在研究在解决旅行商问题时是否选择2-opt... 详细信息

NP-hard组合优化问题一直都是备受关注的问题,越来越多的启发式算法被提出来解决这些问题,针对某一类组合优化问题,这里有很多种启发式算法可以选择,因此算法选择问题成为现在研究的热点。本文旨在研究在解决旅行商问题时是否选择2-opt算法,给定一个旅行商问题实例,只需要借助它的特征,就能预测其对于2-opt算法的复杂度,如果对于2-opt算法的复杂度较低,那么可以选择2-opt算法来解决它,相反就需要选择其它算法来解决它。在现有的文献中,主要有两种评价旅行商问题实例对于2-opt算法复杂度的方法。一种是根据2-opt算法解决旅行商问题实例的效率,该方法认为2-opt算法在处理简单旅行商问题实例时效率较高,相反在困难实例上效率较低,另-种是根据2-opt算法解决旅行商问题实例时得到的解的质量,该方法提出2-opt解决简单旅行商问题实例时得到的解的质量是较好的,而在解决困难实例时得到的解的质量较差。现有的方法都是利用遗传算法演化生成困难和简单的旅行商问题实例,然后通过比较这两类实例特征的差异,去分析特征与实例复杂度之间的关系,然而本文实验表明这两种评价旅行商问题实例对于2-opt算法复杂度的方法是有冲突的。为了解决这个冲突,本文综合考虑了这两个目标,并采用NSGA-Ⅱ算法以及MOEA/D算法多目标去演化得到简单和困难的旅行商问题实例,然后提取特征去分析实例特征与实例复杂度的关系。实验结果表明多目标方法能够发现不同于单目标发现的特征与实例复杂度之间的关系,并且利用多目标方法发现的特征与复杂度之间的规律能够更好地预测实例在多目标空间的分布。

关键词：旅行商问题 2-opt算法多目标优化算法