首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 78 毫秒
1.
针对旅行商问题(TSP)的特点提出了一种新的解码方式,结合了进化计算(EA)和微粒群算法(PSO)的思想,构造了独特的混合量子算法(HQA).为进一步提高算法的性能,构造了改进混合量子算法(IHQA).IHQA在更新个体时能够指导惯性权重进行动态变化,决定个体在下一代被吸引或扩散.经测试证明,两种混合算法均表现出强大的寻优能力,IHQA效率更高.  相似文献   

2.
混合量子算法在生产调度中的应用   总被引:2,自引:1,他引:1  
针对生产调度领域中的置换Flow Shop调度问题,在量子进化算法思想的基础上,进行了解码、最佳模式设计,并融入了优化方法,形成了混合量子算法(HQA).经过对多个算例的测试,证明HQA在生产调度领域能够提供良好的决策方案和依据.  相似文献   

3.
提出了一种基于K-means聚类算法的多出发点多旅行商问题求解的新方法.算法定义了节点的吸引度,通过节点吸引度矩阵进行子环游节点集的归类,并对各子环游应用单旅行商启发式算法进行求解.实例表明,此规划算法能很好地求解多出发点多旅行商问题.  相似文献   

4.
多旅行商问题是经典旅行商问题的一种演化,考虑一些约束,可以转换为一些较现实的问题,具有较高的理论研究和应用价值.在多旅行商问题中,一个任务由多位旅行商共同完成,问题的求解难度较经典旅行商问题更大.现有的研究中指定旅行商个数,将问题转换为固定数量的多旅行商问题.本文构建了求解pareto解的多目标多旅行商问题模型,针对一定规模的城市数量和约束的问题,获得多旅行商问题中旅行商的合适数量.本文将旅行商的个数和多旅行商的最长访问路径作为优化目标,采用改进的多目标模拟退火(IMOSA)算法和传统的多目标遗传算法对问题进行了求解.采用30个城市的旅行商问题对两种算法进行了测试,发现改进的多目标模拟退火算法相较于多目标遗传算法计算复杂度低,且能发现较好的pareto解,算法性能更优.  相似文献   

5.
求解旅行商问题的几种算法的比较研究   总被引:12,自引:1,他引:11       下载免费PDF全文
旅行商问题具有重要的理论和实际研究价值,在工程实践中应用广泛.采用遗传算法、蚁群算法和模拟退火算法对旅行商问题进行求解,并选取中国旅行商问题进行仿真,比较了3种算法的优劣,得出了它们各自不同的适用范围:蚁群算法适用于缓慢地较精确的求解场合;模拟退火算法适用于快速精确的求解;遗传算法适用于快速求解,但结果准备度要求不高的情况.  相似文献   

6.
粒子群优化算法求解旅行商问题   总被引:90,自引:2,他引:90  
首先介绍粒子群优化的搜索策略与基本算法, 然后通过引入交换子和交换序的概念, 构造一种特殊的粒子群优化算法, 并用于求解旅行商问题. 实验表明了在求解组合优化问题中的有效性.  相似文献   

7.
基于粘贴和删除系统求解旅行商问题的DNA算法   总被引:1,自引:1,他引:0  
旅行商问题(Traveling Salesman Problem,TSP)是一个典型的NP完全问题.粘贴和删除模型是DNA计算的两个基本计算模型.结合上述两个模型的优点,构造粘贴-删除模型,并利用该模型给出求解旅行商问题一种新的DNA算法.  相似文献   

8.
针对粒子群算法直接用于求解离散旅行商优化问题会存在诸多困难,通过分析粒子群算法、遗传算法各自优缺点,将粒子群算法、遗传算法有效结合组成混合算法用于求解离散旅行商问题.混合的目的在于保持两种算法各自的优点,并有效地避免各算法原有的不足.对3个不同规模的巡回旅行商问题进行实验,结果表明:混合算法提升了算法的局部搜索能力.  相似文献   

9.
叙述了NP完全问题的复杂性及分支限界法求解问题最优解的策略,分析了利用分支限界法求解旅行商问题过程中影响算法求解效率的主要原因。针对欧氏空间的旅行商问题求解,提出了通过化简初始边集的策略,改善算法的求解效率,通过实验说明了该策略的有效性。该策略可应用到求解旅行商问题的其他算法中。  相似文献   

10.
【目的】量子蚁群算法是一种常见的智能仿生算法,广泛的应用在数学优化、工程技术等领域。该算法在求解旅行商问题时也表现出良好的效果,但当城市规模变大时求解该问题就会出现算法收敛速度慢、早熟、全局寻优能力较弱等问题,为了解决这方面的问题,提出了一种优化的量子蚁群算法。【方法】将部分量子蚁群算法中信息素更新机制与量子旋转角更新机制结合,改进量子选择策略,并将轮盘赌法应用在状态转移规则模型中。【结果】分别使用标准库中的样本和自定义样本,利用Python平台进行实验仿真,通过与其他算法进行比较,并在给出了详细的对比过程。在求解旅行商问题时,提出的算法在最优值差别不大的情况下,减少了早熟,大幅度提高了算法的收敛速度。【结论】提出的算法是有效的,具有一定的实践意义。  相似文献   

11.
李婷  张楠  吕志民  邹蕾 《科学技术与工程》2020,20(33):13735-13739
作为一种新兴的群智能启发式算法,蝙蝠算法近年来被广泛用于求解离散、连续、及组合优化问题。针对典型组合优化问题中的旅行商问题,本文提出一种基于偏序对改进的蝙蝠算法用于求解离散型旅行商问题。通过对蝙蝠速度、位置的更新,使算法具有更强的适用性。本文对16个标准TSP问题进行测试与对比分析以验证算法有效性。实验结果表明,本文提出的偏序对蝙蝠算法在大多数实例中均优于其他算法。  相似文献   

12.
多旅行商问题在实际生活中有着较为广泛的应用价值,该问题的求解受到越来越多学者的关注。信息传播算法是一类求解组合优化问题最为有效的方法,基于K-means聚类技术,给出了求解多起点多旅行商问题(Multiple depots Multiple Traveling Salesman Problem, MMTSP)的信息传播算法,该算法采用k-means聚类算法将旅行商问题进行聚类,从而形成若干类,对每一个类采用信息传播算法进行旅行商搜索,将每一个类的搜索结果进行综合,得到MMTSP问题的解。通过对旅行商标准测试数据集中的多种实例进行测试,并与其它同类算法进行试验对比分析,结果表明:该算法优于同类算法。  相似文献   

13.
以著名的旅行商问题为研究对象,研究了基于线路重连(PR)算法的自适应蚁群算法(ACO)的应用。根据蚁群算法构解过程中的选择策略与信息素更新机制,提出了自适应的蚁群优化方法,即通过阈值接收算法(TA)中的阈值控制参数改变蚁群的确定选择与随机选择机会,从而控制了搜索方向。采用这种自适应的蚁群优化算法,避免蚁群算法陷入局部最优,使对解空间的更好地进行搜索。同时,在蚁群优化算法(ACO)中,嵌入路径重连算法(PR)来改进解的质量。实验结果证明了基于线路重连算法(PR)的自适应蚁群算法(ACO)在求解该问题时的有效性。  相似文献   

14.
求解旅行商问题的一个有效算法   总被引:1,自引:0,他引:1  
采用统计方法,以中国旅行商问题为例给出了一个求解旅行商问题的有效算法.首先对每个点到其他各点的距离进行求和,然后对每点的距离之和排序,取距离之和最长的3个点连成一回路,再按距离之和的大小顺序选取其余节点,插入到回路的最佳位置上,使得新回路增加的长度越来越短,最后得到旅行商问题的回路.算法实现容易、运行速度快,生成的结果接近其最优解.  相似文献   

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

16.
遗传算法是基于生物进化原理的普适性全局优化算法,针对一类NP完全的组合优化问题—旅行商问题,文章阐述了用遗传算法求解旅行商问题的算法步骤,并给出相应的程序设计.将此算法应用到6个旅行商问题中所得到的结果与弹性网络得到的结果进行比较,得出用遗传算法得到的结果与最优解较为接近的结论.  相似文献   

17.
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.  相似文献   

18.
用蚁群算法求解旅行商问题   总被引:1,自引:1,他引:0  
介绍了一种用于解决复杂优化问题的新的启发式算法--蚁群算法.阐述了该算法的基本原理、算法模型和在旅行商问题中的具体应用过程.研究表明该算法具有并行性,鲁棒性等优良性质.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号