共查询到18条相似文献,搜索用时 375 毫秒
1.
2.
陆添超 《电脑编程技巧与维护》2010,(10):29-30
遗传算法模拟自然界动物的繁衍来解决全局寻优问题,。旅行商问题是典型的组合优化问题,而且非常适于演示遗传算法的基本思想。对于遗传算法的优化,国内外许多专家结合旅行商问题提出了很多算子,结合其中的一些经典算子实现应用遗传算法解决旅行商问题的演示程序。 相似文献
3.
鉴于旅行商问题是一个NP难问题,而猴群算法是一种新的群体智能优化算法,因此,利用猴群算法给出旅行商问题的求解。在分析了旅行商问题的特点后,采用整数编码的方式来表示猴群的位置,这样就解决了猴群算法在求解含有离散变量的组合优化问题时,算法中的爬过程失效的问题,有效地利用猴群算法求解旅行商问题。为了提高猴群算法的性能,在猴群算法的爬过程中,引入好动策略,给出改进算法,并将其应用到求解旅行商问题。在仿真实验中,与其他算法进行比较,结果表明利用改进猴群算法能够有效地求解旅行商问题。 相似文献
4.
5.
旅行商问题是算法应用中的基本问题,遗传算法具有通用性、智能性、鲁棒性、全局性和并行性的特点,正好适合于该问题的求解。但基本遗传算法在解决旅行商问题时效率不高,并且容易陷于局部最优解。为了解决这一问题,提出了一种改进的遗传算法。文章首先对旅行商问题进行了描述,对遗传算法进行了介绍,对其中的个体选择、交叉算法等重要因素做了一定地改进。最后,用一个简单的实例对基本遗传算法和改进的遗传算法进行了比较,发现改进的遗传算法在解决旅行商问题上的效率问题上有了一定的提高。 相似文献
6.
牟廉明 《计算机应用与软件》2011,28(11)
扩展旅行商问题是根据实际需要对传统旅行商问题的一种延伸和拓展,在实际问题中有许多有趣的应用。提出一种新的扩展旅行商问题(子旅行商问题),传统旅行商问题仅仅是子旅行商问题的一种特例。然后根据子旅行商问题的定义对蚁群系统算法进行改造,设计了一种有效的求解子旅行商问题的蚁群算法,并根据子旅行商问题的特点设计了一种高效的邻域局部搜索技术来提高解的质量。最后在10个TSPLIB范例上进行比较实验。结果表明:改进的蚁群算法能够有效求解提出的子旅行商问题,设计的邻域局部搜索技术是有效的。 相似文献
7.
为解决多起点均衡多旅行商问题,分析问题的特点,从优化旅行商的起点、最小化所有旅行商总路程和维持各旅行商路径均衡的角度出发,提出一种基于改进交叉、变异操作的遗传算法。根据均衡多旅行商问题的优化目标,构建新型评价函数,设计双染色体编码方式。在此基础上,引入改进的三交换启发式交叉操作并设计双变异策略。在经典旅行商问题的测试集TSPLIB上,与其它求解多旅行商问题的进化算法进行对比,验证算法的有效性。 相似文献
8.
9.
10.
11.
给出了球面随机旅行商问题最优值的一个上界以及最优值期望的一个下界.猜想球面旅行商问题常数存在且与平面旅行商问题常数相等.所做两组数值实验支持该猜想,且显示球面比平面正方形更适宜作为二维旅行商问题常数的测试床. 相似文献
12.
虽然遗传算法相较于其他算法能够更好地求解旅行商问题,但这种算法在使用的过程中容易陷入局部最优的问题,进而导致问题求解遭遇困境。文章在简要介绍旅行商问题的基础上,介绍了遗传算法求解旅行商问题的思路和方法,并明确算法应用中存在的不足。在此基础上提出基于指针网络改进遗传算法求解旅行商问题的新思路,为弥补遗传算法的缺陷提供相应的原理支持。 相似文献
13.
14.
A strategy for solving the traveling salesman problem is adapted to the problem of finding a biconnected subgraph of a weighted graph whose cost function satisfies the triangle inequality. An approximation algorithm similar to Christofides' algorithm [5] for the traveling salesman problem is shown to possess the same worst-case bound of when applied to the biconnectivity augmentation problem. A tight inequality is derived relating the cost of an optimal traveling salesman tour to the cost of an optimal biconnection. 相似文献
15.
根据三值光计算机具有的巨并行性特点,对给定城市数的旅行商问题进行研究.首先将旅行商问题进行预处理,并转换为改进的符号数(modified signed-digit,MSD)表示形式;然后根据三值光学计算机的位数众多和MSD加法的无进位过程,建立了相应的计算方法,用自主开发的三值逻辑光处理器系统进行求解.结果表明,在数据... 相似文献
16.
旅行商问题作为组合优化研究中最具挑战的问题之一, 自被提出以来就引起了学术界的广泛关注并提出了大量的方法来解决它. 蚁群算法是求解复杂组合优化问题的一种启发式仿生进化算法, 是求解旅行商问题的有效手段. 本文分别介绍蚁群算法中几个有代表性的算法, 综述了蚁群算法的改进、融合和应用的文献研究进展, 以评价近年来不同版本的蚁群算法为解决旅行商问题的发展和研究成果, 并针对改进蚁群算法结构框架、算法参数的设置及优化、信息素优化和混合算法等方面, 对现被提出的改进算法进行了分类综述. 对蚁群算法在未来对旅行商问题及其他不同领域的研究内容和研究热点的进一步发展提供了展望和依据. 相似文献
17.
旅行商问题是求仅一次遍访指定城市并返回出发城市的最短旅行路线的问题,它是图论中一个经典的NP完全问题,用电子计算机需要指数级的时间才能得到解决,该文基于分子生物技术并利用Adleman-Lipton模型给出旅行商问题的DNA算法,这个DNA算法理论上能在多项式的时间内解决这个NP完全问题。具体地对n个城市的旅行商问题,首先将它视为一个具有顶点和边的图,并将顶点、边分别用DNA链编码表示,边的方向通过顶点的编码获得;再将这些DNA链投放在试管中进行生物化学反应,利用DNA计算的高效并行性,通过基本的生物实验操作最后得到旅行商问题的解,其过程的复杂度为O(n)。该算法的创新之处在于表示城市和路径的DNA链长度的设计,能使我们在合理小的范围内寻找旅行商问题的解,较大地简化了问题的复杂度。 相似文献
18.
王继强 《计算机工程与科学》2014,36(5):947-950
旅行商问题是图论中一类经典的最优化问题,其研究对于其他图优化问题的解决具有重要的理论意义和实际价值。针对旅行商问题建模中的困难之处--如何避免“分割”现象,提供了三种不同的解决方法,并给出了基于当今最流行的优化计算软件LINGO的实证分析。 相似文献