共查询到20条相似文献,搜索用时 9 毫秒
1.
基于差分进化算法的多旅行商问题优化 总被引:4,自引:1,他引:3
针对所有旅行商路径最大值最小的多旅行商问题,提出改进的差分进化算法优化.在该优化方法中,编码采用实数编码;改进的差分进化算法采用轮盘赌选择;根据旅行商问题的特点,在差分进化算法中增加邻域搜索算子.该方法适于距离对称和非对称的多旅行商问题求解.以距离非对称的多旅行商问题的实例进行了仿真和比较,可以看出所提出的改进差分用来解决多旅行商这类离散组合优化问题是有效的. 相似文献
2.
多目标旅行商问题(MOTSP)是经典旅行商问题的扩展,其优化目标包含了距离、成本、收益及风险等多个相互冲突的指标.本文提出了一种基于偏好的Pareto演化算法p-PEA用于建模并求解此NP-hard问题.该优化算法建立在MOTSP的智能体仿真模型之上,从而解决了数学建模不能真实再现实际MOTSP中众多影响因素的问题.通过仿真的方法,算法能够得到MOTSP可行解的各项评价指标值.在此基础士,通过设计演化算法搜索问题的Pareto优化解集.其中,将决策者的决策偏好信息引入到Pareto优化解集的求解过程中,所得结果将更合理.最后,以一个130个城市的旅行商问题为例验证了算法的有效性. 相似文献
3.
4.
5.
遗传算法求解旅行商问题时的基因片段保序 总被引:15,自引:0,他引:15
针对基于遗传算法的 TSP问题求解 ,尝试了多种遗传操作 ,分析了这些操作在遗传算法中的作用 ,讨论了基因片段保序在利用遗传算法求解 TSP问题中的重要性 . 相似文献
6.
为优化生物反恐条件下的应急物资配送过程,将该环境下的应急物资配送问题构造为一多旅行商问题(MTSP),并从理论上分析了该旅行商回路为最短Hamilton路径。以此问题为背景,针对应用传统遗传算法求解多旅行商问题时存在收敛速度缓慢等问题,提出并设计了一类新的混合遗传算法。该类新遗传算法与传统遗传算法的最主要区别在于,针对多旅行商问题专门设计了一种新的染色体编码规则、排序算子和交叉算子。仿真结果表明,该算法能够快速收敛到问题的近似最优解,并能很好地维持种群的多样性。 相似文献
7.
解旅行商问题的混沌蚁群算法 总被引:19,自引:0,他引:19
高尚 《系统工程理论与实践》2005,25(9):100-104
利用混沌运动的遍历性、随机性和规律性等特点,提出了一种求解旅行商问题的混沌蚁群(CACO)算法.该算法的思想是采用混沌初始化进行改善个体质量和利用混沌扰动避免搜索过程陷入局部极值.与模拟退火算法、标准遗传算法进行比较,仿真结果表明该方法是一种简单有效的算法. 相似文献
8.
提出了一种自调节种群的演化算法(SaPEA)求解旅行商问题,算法根据当前最优适应度改进的情况提出一种更精细调节种群规模的模式,并根据演化的进程选择强化操作或者分化操作.这样不仅有利于保持种群的多样性开发新的解,还可以加快收敛速度探索到更好的解.同时,还对现有的启发式交叉算子和3-opt局部搜索算法进行了改进.通过对TSPLIB中实例进行测试,表明了SaPEA算法的优越性. 相似文献
9.
基于仿真的遗传算法求解动态旅行商问题 总被引:1,自引:0,他引:1
以标准旅行商问题的扩展问题--动态旅行商问题为对象,分析了动态旅行商问题中由于道路流量实时变化所引起的标准旅行商问题的数学建模与优化求解的问题复杂性.通过建立其计算机仿真模型再现动态旅行商问题中众多复杂的非平稳、随机因子.进而提出了基于计算机仿真模型的遗传算法,即根据计算机仿真的结果,应用改造后的遗传算法搜索原问题的优化解.最后,在多智能体仿真平台上实现该优化算法,并以此求解20个城市的动态旅行商问题,计算结果验证了算法的有效性. 相似文献
10.
11.
基于Hopfield网络学习的多城市旅行商问题的解法 总被引:1,自引:0,他引:1
针对Hopfield神经网络(HNN) 学习算法难以求解大规模组合优化问题的不足,提出了基于HNN学习的多城市旅行商问题的示解算法。它是把HNN学习算法作基本算子,对城市群体按一定的规则进行有效的分割、计算攻连接,来寻找巡回路径的最优解或满意解。并以100城市的旅行商问题为例进行了仿真实验,骓证了算法的有效性。该算法不受求解问题的规模限制;还可通过并列运算实现高速化;同时因自满法简明,易于硬件实现。 相似文献
12.
刘永红 《系统工程与电子技术》2002,24(11):123-126
最优聚丛原理是解决算法集和演算集极小化问题、NP完全问题的一个基本的计算复杂性原理 ,引入了稠密、有洞算法概念。以此为基础 ,提出了GED聚丛法 ,它是几何算法G、生态算法E和判定问题D的近似演算等三方面合力求解旅行商问题 (TSP)的方法。给出了求解TSP流程及实例 ,计算结果验证了该原理和方法的正确性和精巧性。 相似文献
13.
针对最小化单个旅行商路程的多旅行商问题,提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点,采用一种递阶编码方案,此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题不需设计专门的遗传算子,操作简单,并且解码方法适于求解距离对称和距离非对称的多旅行商问题。计算结果表明,递阶遗传算法是有效的,能适用于优化多旅行商问题。 相似文献
14.
15.
旅行商问题的遗传算法 总被引:9,自引:0,他引:9
旅行商问题属于NP问题,现在还没有找到有效的解法。本文应用遗传算法对解决此类问题的有效性作了探讨。文中对遗传算子的应用,编码,参数选择及其对收敛的影响等问题作了分析与探讨。 相似文献
16.
旅行商问题(Traveling Salesman Problem,简称TSP)是一个典型的组合优化问题,而且是一个NP完全问题。遗传算法(Genetic Algorithm,简称GA)是求解组合优化问题的行之有效的算法。但遗传算法并不是一个完美无缺的算法,它最突出的问题是早熟现象。在解决像旅行商这类组合优化中的NP完全问题。是极易陷入早熟收敛,城市规模越大越难求得最优解。如何缓和旅行商问题中的早熟现象。使问题的解尽可能接近最优解.这是本文研究的主要内容。本文在分形法的基础上提出.了一种分形法与范例库推理相结合的改进方法用以求解TSP问题。首先建立范例库,选取其中优良的个体来指导城市规模大的旅行商问题进行合理的区域分割,由于优良个体与最优值的结构大体相同,相似度大,故可以有效地实施“分而治之”的策略。在寻优进化过程中,还要对范例库进行更新与维护。通过对TSPLIB测试库中的eil51、eil101、ch130和ch150问题的求解,说明该方法在求解TSP问题上是行之有效的。 相似文献
17.
解旅行商问题的一个新的遗传算法 总被引:2,自引:1,他引:2
对旅行商(TSP)问题设计了一个新的遗传算法.首先,对n个城市的旅行商问题设计了一个新的编码方法,并且对这种编码方法,给出了简便的解码方法.其次,针对编码的特点,设计了一种新的、有效的杂交算子和变异算子,这些算子均能直接产生可行的后代.为提高杂交算子的搜索能力,结合了一个局部搜索技术来改进杂交算子.在此基础上,提出了求解TSP的一个新的遗传算法,并证明了其全局收敛性.为了验证算法的有效性,对10个国际标准算例(城市规模从14到1000)进行了计算机仿真,结果表明算法是有效的. 相似文献
18.
一种求解旅行商问题的交叉禁忌搜索 总被引:2,自引:1,他引:2
提出一种改进的禁忌搜索(TS)一交又禁忌搜索(CTS),并用于混合优化问题旅行商问题(TSP)的求解。CTS主要包括集中策略和分散策略,采用选择规律的改变促进移动的混合,集中策略增强了算法的局部搜索能力;分散策略是用于开辟新的搜索空间,在CTS中,采用遗传算法中的交叉算子作为分散策略,优解选择法作为集中策略。CTS、标准TS、带集中裳略的TS和蚁群算法用于求解相同的TSP例子,所用例子都是来自TSPLIB例子库和Fogel路径。求解结果显示了CTS的性能优于其它算法。 相似文献
19.
20.
求解连续函数优化问题的改进蚁群算法及仿真 总被引:3,自引:0,他引:3
蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智能进化算法,该算法采用分布式并行计算和正反馈机制,易于与其它方法结合,目前虽然已经在离散空间优化领域中得到了广泛应用,但是在求解连续空间优化问题方面的研究相对较少.在介绍基本蚁群算法机制原理和数学模型的基础上,对信息素更新方式进行了改进,采用动态局部信息素更新方式和自适应调节信息素挥发的全局信息素更新方式相结合,并将各条寻优路径上可能的残留信息素数量限制在一个最大最小区间,以提高改进后蚁群算法的全局收敛性能.仿真实验表明,提出的改进蚁群算法能更快地找到连续空间优化问题更优良的全局解,从而为蚁群算法求解这类问题提供了一条可行有效的新途径. 相似文献