一种求解TSP问题的均匀设计抽样混合遗传算法

旅行商问题是经典的NP-hard组合优化问题,在许多领域有着重要应用。近年来,传统遗传算法等各种智能优化方法被引入到该问题的求解中来,但效果不理想。基于理想浓度模型的机理分析,利用均匀设计抽样的理论和方法,对遗传算法中的交叉操作进行了重新设计,并在旅行商问题特点的基础上,结合2-opt局部搜索策略,给出了一个解决旅行商问题的新的遗传算法。通过将该算法与简单遗传算法和佳点集遗传算法进行实例仿真比较,可以看出新算法在求解旅行商问题上提高了求解的质量、速度和精度,而且避免了其它方法常有的早期收敛现象。     

面向多旅行商问题的多目标模拟退火算法研究

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

求解多起点多旅行商问题的-K-means聚类信息传播算法

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

用启发式贪心法求解旅行商问题

旅行商问题是ＮＰ完全的组合优化问题，分析了邻域启发式算法的基本操作，提出了一种简单的启发式贪心法，仅利用城市间的距离信息求解旅行商问题，理论分析与实验结果表明该方法是确定性的多项式时间算法，对５个不同规模的典型的旅行商问题进行优化，均达到或优于文献中的结果。     

基于蚁群算法的TSP问题研究

蚁群算法是一种新型的优化算法,于20世纪90年代提出,最早成功应用于解决旅行商问题。研究表明,蚁群算法有着极强的鲁棒性发现较好解的能力。本文介绍了蚁群算法原理和TSP问题,通过Scilab编程实现了用蚁群算法解决旅行商问题。     

一种优化的量子蚁群算法在旅行商问题上的应用

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

用随机神经网络优化求解C-TSP

基于动态随机神经网络(DRNN:Dynamical Random Neural Network)求解典型旅行商优化问题TSP(Traveling Salesman Problem),通过简化方程参数的改进算法,针对解决大规模TSP的求解效果在时间以及路径寻优上所存在的问题,提出一种新的分区方案来解决中国31城市的旅行商问题.所获得的最优路径结果与目前公开文献中已有的其他神经网络所解的结果相比较,显示出采用随机神经网络解决多于10个变量TSP问题的优越性.实验结果表明,采用该方法解决31个城市TSP的优化,所得出的最短距离(15 112.7km)比已有5种算法的结果都要少.     

改进的蚁群禁忌搜索混合算法

蚁群算法作为一种全局搜索的方法,具有正反馈性、并行性、分布性、自组织性等特点,在求解复杂组合优化问题上具有强大的优势.但是,蚁群算法也存在一些不足之处:例如,算法需要较长的搜索时间、容易出现早熟停滞现象.为了更优地解决旅行商问题,改进单纯用蚁群算法求解旅行商问题的结果,通过蚁群算法、免疫算法和禁忌搜索算法自身的特点,分别对三者的优势和不足进行分析,提出一种将三者混合使用的求解旅行商问题的算法.     

遗传算法在车辆优化调度中的应用

旅行商问题是车辆优化调度中的NP难题,对旅行商问题进行描述,并建立了数学模型。介绍了遗传算法的基本思想,给出用遗传算法求解旅行商问题的过程,仿真实验证明该算法是有效的。     

基于蜂群的改进混合算法求解旅行商问题

旅行商作为组合优化问题,在求解中存在收敛慢、易于陷入局部最优问题,模拟蜜蜂觅食行为并利用蜂群算法求旅行商问题的最优解,觅食过程中根据收益比因子动态转变角色,加速算法收敛。结合改进2-opt算法,有效改善蜂群算法在全局搜索中局部搜索能力较弱的缺陷,降低问题规模。对不同基准问题的测试结果进行了对比分析,分析结果表明:改进混合算法比标准蜂群算法能在短时间内求得最优解。     

粒子群与遗传算法的混合算法

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

一种改进的自适应蚁群算法及其应用研究

蚁群算法作为一种新型的模拟进化算法,具有分布计算和信息正反馈等优点,但蚁群算法与其他进化算法一样存在收敛速度慢,易陷于局部最优等缺陷。针对这一问题,提出一种改进的蚁群算法,结合遗传算法和图论中的最邻近算法,并自适应地初始化信息素和限定信息素的大小范围。将该算法应用于旅行商问题（traveling salesman problem,TSP）求解,与基本蚁群算法比较,数值实验结果表明,这种改进算法能有效抑制算法陷入局部最优的缺陷,从而提高了解的全局搜索能力和解的质量。     

配送中心补货作业问题的蚂蚁算法

补货是配送中心运作中一项重要的作业,对其有效管理能够显著减少配送中心的运作时间,带来可观的经济效益. 根据配送中心的具体配置,补货作业呈现不同的模式,本文探讨配送中心分拣区采取指定储存策略情形下,补货设备从储存区补充物品到拣货区的补货作业问题,运用蚂蚁寻找最优路径算法原理设计出解决该问题的算法步骤与流程,并仿真测试算法性能,计算结果显示效果良好.     

蚂蚁算法在概念设计方案求解中的应用

通过分析概念设计方案求解问题与旅行商问题的相似性，将方案求解问题转化为组合优化的最优路径问题，建立了基于动态规划的解空间模型和基于最长路径的优化模型，利用蚁群系统内在的正反馈寻优机制，将求解旅行商问题的基本蚂蚁算法应用于方案求解的组合优化过程，结合遗传算法的交叉变异操作，提出一种基于改进蚂蚁算法的求解方法，从而快速有效地获得了最优方案解，最后，以压力机的概念设计为例验证了该方法，研究表明，该方法是合理可行的，它可以使方案求解的人工寻优过程实现算法化，并具有较好的可操作性，从而为解决方案优化的组合爆炸问题提供了一种新的思路。     

TSP及其扩展问题的混合型启发式算法

就经典的旅行商问题（ＴＳＰ）及其扩展形式;瓶颈问题、多目标问题等给出一种混合型启发式算法,并知微机上予以实现,为困难的扩展型ＴＳＰ提供了新的求解手段。     

一种解决TSP问题的自适应协同演化计算方法

针对遗传算法和蚁群算法存在运行时都会出现停滞、早熟等现象,且容易陷入局部最小的特点,提出了一种将两者结合协同演化运行的方法,通过建立对这两种算法状态的评估函数来动态判断其运行状态是否正常,进而动态调整运行的算法,从而最大程度地避免了这两种算法运行时的缺点.对TSP问题进行了实验测试,结果表明：此方法在收敛速度、寻优结果上都较上述两种算法单独运行有着明显的优势.     

货郎问题求解算法分析

介绍了求解货郎问题的4个算法：贪心算法、MST近似算法、MM近似算法和回溯搜索算法。分别使用各个算法对一个货郎问题的具体实例进行求解，并对各个算法的性能进行了分析比较。贪心算法的运行速度较快，但在大多数情况下该算法找到的是次优解而非最优解。MST和MM近似算法用以求解满足三角不等式的货郎问题，其近似性能比（即精确度）分别为：RMST（I）＜2，RMM（I）＜3／2。回溯搜索算法可以求出货郎问题的最优解，随着城市数目的增加，其搜索效率会下降。     

基于MATLAB的改进型基本蚁群算法

蚁群算法是一种新型的模拟进化算法。是继GA、SA、TS等算法之后求解组合优化问题的一种新思路。人工蚁群算法通过模拟蚁群搜索食物的行为,采用正反馈结构、分布式计算与某种启发式算子相结合的方法,能够很快地发现较好解。本文给出一种基于MATLAB的改进型基本蚁群算法,有效地降低了算法的复杂度,缩短了搜索时间,具有较强发现最好解的能力。     

基于演化算法的TSP求解

TSP即旅行商问题或者货郎担问题是一个易于描述但难于解决的NP问题,也是一个具有广泛的应用背景和重要理论价值的组合优化问题。简要介绍了求解TSP的若干方法,同时讨论了基于演化算法的TSP求解方法,并对TSP的求解进行了展望。     

基于Prüfer数的离散粒子群优化算法在TSP问题中的应用

通过引入Prüfer数编码、归一化运算、粒子的位置矩阵进行模糊化等操作,将连续型粒子群优化算法改造为离散化PSO.并通过构造旅行商问题的度约束最小生成树,利用DCMST的模糊离散粒子群算法求出最优解.采用TSP的测试实例进行仿真实验,证明算法的有效性与实用性.