A COMPARATIVE STUDY ON PARTICLE SWARM OPTIMIZATION AND GENETIC ALGORITHMS FOR TRAVELING SALESMAN PROBLEMS

This article deals with a performance evaluation of particle swarm optimization (PSO) and genetic algorithms (GA) for traveling salesman problem (TSP). This problem is known to be NP-hard, and consists of the solution containing N! permutations. The objective of the study is to compare the ability to solve the large-scale and other benchmark problems for both algorithms. All simulation has been performed using a software program developed in the Delphi environment. As yet, overall results show that genetic algorithms generally can find better solutions compared to the PSO algorithm, but in terms of average generation it is not good enough.     

一种基于相似性排挤的多种群混合遗传算法

在遗传算法优化的研究中,针对简单遗传算法存在的局部搜索能力差和早熟收敛的问题,提出一种相似性排挤的多种群混合遗传算法.新算法主要在宏观上设置多个子种群与一个最优保存种群的进化架构,并在子种群中引入模拟退火算法,构成合理的混合结构,用于提高算法的局部搜索能力.在微观方面,个体在子种群间交流时采取相似性评判标准,进而实施排挤替换操作,维护种群多样性,用于改善算法的早熟收敛问题.最后,通过对TSP问题的求解,验证算法的有效性与实用性.     

一种求解TSP问题的多种群并行遗传算法

遗传算法是一种基于自然群体遗传机制的有效搜索算法,由于它在搜索空间中同时考虑许多点.减少了收敛于局部极值的可能,也增加了处理的并行性.因此可以利用并行遗传算法研究典型的TSP问题的求解.提出一种有效的多种群并行算法求解旅行商(TSP)问题,应用多种群遗传并行进化的思想,并在种群之间进行遗传信息交流,以解决经典遗传的收敛到局部最优值问题.仿真实验结果表明,方法在解的精度上以及解的质量上优于经典的遗传算法.     

旅行商问题(TSP)的一种改进遗传算法

传统的序号编码遗传算法(GA)使用PMX、CX和OX等特殊的交叉算子，这些算子实施起来很麻烦。针对TSP问题的求解，提出了一种新的改进遗传算法：单亲进化遗传算法(PEGA)，PEGA是利用父体所提供的有效边的信息，使用保留最小边的方法进行个体的进化。与传统的遗传算法相比，PEGA算法弥补了它们的不足之处，简化了遗传算法。给出了PEGA算法的数值算例，仿真实验表明了该算法对于对称的TSP和非对称的TSP问题，都具有收敛速度快的特点，证明了该算法的有效性。     

Approximation Algorithms for Multi-Criteria Traveling Salesman Problems

We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with γ-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of and a randomized approximation algorithm that achieves a ratio of . In particular, we obtain a 2+ε approximation for multi-criteria metric STSP. Then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximation algorithms for STSP with γ-triangle inequality (ratio ), asymmetric TSP (ATSP) with γ-triangle inequality (ratio ), STSP with weights one and two (ratio 4/3) and ATSP with weights one and two (ratio 3/2). A preliminary version of this work has been presented at the 4th Workshop on Approximation and Online Algorithms (WAOA 2006) (Lecture Notes in Computer Science, vol. 4368, pp. 302–315, 2007). B. Manthey is supported by the Postdoc-Program of the German Academic Exchange Service (DAAD). He is on leave from Saarland University and has done part of the work at the Institute for Theoretical Computer Science of the University of Lübeck supported by DFG research grant RE 672/3 and at the Department of Computer Science at Saarland University.     

Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem

Let G=(V,E) be a complete undirected graph with vertex set V , edge set E , and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V ₁ , . . ., V _k . The clustered traveling salesman problem is to compute a shortest Hamiltonian cycle (tour) that visits all the vertices, and in which the vertices of each cluster are visited consecutively. Since this problem is a generalization of the traveling salesman problem, it is NP-hard. In this paper we consider several variants of this basic problem and provide polynomial time approximation algorithms for them. Received February 13, 1998; revised July 8, 1998.     

基于智能Agent的个性化生物信息检索系统的设计

设计了一个基于智能Agent的面向生物信息领域的信息检索服务系统,介绍了该系统的体系结构和各组成部分的设计思想,重点讨论了如何应用遗传算法对用户感兴趣的信息进行学习并推荐给用户.     

人工神经网络求解TSP问题新方法

本文在分析Hopfield/Tank方法的基础上提出一种新的人工神经网络方法,采用优化约束条件的能量函数,具有收敛速度快、不易陷入无效解、易获得亚优解等优点。     

Approximation algorithms for time-dependent orienteering

The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in general dependent on the starting time.For any ε>0, we provide a (2+ε)-approximation algorithm for the time-dependent orienteering problem which runs in polynomial time if the ratio between the maximum and minimum traveling time between any two sites is constant. No prior upper approximation bounds were known for this time-dependent problem.     

The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem

Traveling salesman problem (TSP) is proven to be NP-complete in most cases. The genetic algorithm (GA) is improved with two local optimization strategies for it. The first local optimization strategy is the four vertices and three lines inequality, which is applied to the local Hamiltonian paths to generate the shorter Hamiltonian circuits (HC). After the HCs are adjusted with the inequality, the second local optimization strategy is executed to reverse the local Hamiltonian paths with more than 2 vertices, which also generates the shorter HCs. It is necessary that the two optimization strategies coordinate with each other in the optimization process. The two optimization strategies are operated in two structural programs. The time complexity of the first and second local optimization strategies are O(n) and O(n³), respectively. The two optimization strategies are merged into the traditional GA. The computation results show that the hybrid genetic algorithm (HGA) can find the better approximate solutions than the GA does within an acceptable computation time.     

引入基因簇求解TSP的遗传算法

在用遗传算法求解TSP时,极易破坏已经发现的较短线路片段,从而使遗传算法的收敛变慢.为了保护较短的线路片段,遗传操作以基因和基因簇为单位进行,优良基因簇可完整地遗传到下一代.在获得第一个近似最优解后,粉碎已发现的基因簇并继续寻优,以期能够获得全局最优解.使用CHN144及TSPLIB中的数据进行试验,找到了CHN144问题的当前最优路径.通过对TSP225的实验获得了最短路径3859,优于目前已经公布的最短路径3916.实验表明,基于基因簇的算法具备3000个城市左右的寻优能力.     

An asynchronous recurrent linear threshold network approach to solving the traveling salesman problem

In this paper, an approach to solving the classical Traveling Salesman Problem (TSP) using a recurrent network of linear threshold (LT) neurons is proposed. It maps the classical TSP onto a single-layered recurrent neural network by embedding the constraints of the problem directly into the dynamics of the network. The proposed method differs from the classical Hopfield network in the update of state dynamics as well as the use of network activation function. Furthermore, parameter settings for the proposed network are obtained using a genetic algorithm, which ensure a stable convergence of the network for different problems. Simulation results illustrate that the proposed network performs better than the classical Hopfield network for optimization.     

智能教学系统中的知识树增长模型

智能教学系统（intelligent tutoring system,ITS),作为人工智能学科的重要研究应用领域,是21世纪人类社会数字化教育的必然发展方向,迄今研究逾30年。现有一些ITS系统由于知识表示以及推理方法的领域相关特性,系统构建与系统运用、系统模块之间动态有机联系不强,进而导致学生模型弱化等问题,限制了系统在进行个别化教学过程中的智能性和推广运用。在此从系统的知识表示入手,基于SC文法的知识表示体系和知识树映射方法,提出了一个动态、实时、自适应、交互式知识树增长模型（augment knowledge-tree model,AKTM)。模型包括基于SC文法的知识点表示方法、知识树结构以及知识树映射、知识树学生模型、知识点学习循环等内容,贯穿于ITS系统4大传统模块之中,并在内容和功能上与之完全集成。通过知识点层次多维属性标注和索引,实现了知识存储、处理、调用和维护动态、一体化过程。通过知识点学习循环,实现个别化、动态、自适应智能教／学过程。同时通过模型在多媒体ITS系统中的实例化设计和运用,实现了动态教／学、领域无关、人机交互、自适应、个别化等智能特点。     

AnO(logk)-approximation algorithm for thek minimum spanning tree problem in the plane

Givenn points in the Euclidean plane, we consider the problem of finding the minimum tree spanning anyk points. The problem isNP-hard and we give anO(logk)-approximation algorithm.     

基于混合行为的自适应蚁群算法

针对传统蚁群算法求解能力的不足,提出了一种基于混合行为的自适应蚁群算法(HBACA).通过引入具有多行为的混合蚂蚁来扩大解搜索空间,避免早熟和停滞现象;另外在每次迭代过程中具有不同行为的蚂蚁数目可以视具体情况而动态地进行调整,以便在加速收敛和防止早熟、停滞现象之间取得一个较好的平衡.实验表明,相比ACS、MMAS算法,改进算法求解TSP问题的性能得到了加强.     

Positive role of glassy dynamics in finite-time optimization by threshold algorithms

The optimization mechanism of threshold algorithms is investigated in the solving process of a random Euclidean traveling salesman problem. A series of computer experiments previously designed for simulated annealing is conducted with algorithms such as generalized simulated annealing. The results show that if the threshold function decays fast enough, a previous positive view of slow relaxation dynamics in finite-time optimization by simulated annealing is still applicable regardless of the algorithm. These dynamics work effectively as an optimizer at around an intermediate temperature, which can be identified by using the Deborah number.     

基于混合杂交的遗传算法求解旅行商问题

通过混合使用多种杂交算子,提出了一种求解旅行商问题的新型遗传算法,并给出了实验验证。通过实验用该算法求解了城市数为50到100不等的旅行商问题,获得了比其它算法更精确或更接近最优的解,表明了算法的有效性。