【作者】 刘道军；

【导师】 覃俊；

【作者基本信息】 中南民族大学 ， 计算机应用技术， 2008， 硕士

【摘要】 本文首先对遗传算法的原理、技术、理论做了介绍,然后描述了TSP问题,并给出其数学模型.在提出改进的遗传算法之前,先对求解TSP问题常用的遗传算法技术进行介绍,充分分析了矩阵编码的缺点之后,提出了一种新的编码技术——向量编码,并利用基于向量编码的遗传算法求解了TSP问题。作者编写了基于向量编码遗传算法的Matlab程序,试验表明,向量编码遗传算法对求解TSP问题效果较为理想。在改进的遗传算法编码方案中,提出了Hamilton矩阵的概念;根据向量编码的形式,提出一种比较好的不可行解修正技术,这种技术的优点是尽最大程度不破坏染色体的结构,尽力保持父代和子代个体相似度,以便染色体结构遗传到下一代,使得优良模式生存下去;为了使读者能够更加深刻地理解本文提出向量编码方案的动机,也为了让读者不至于混淆向量编码和矩阵编码,在提出向量编码遗传算法和相关的技术之后,将向量编码遗传算法和矩阵编码遗传算法在理论上作了比较,并对矩阵编码遗传算法的缺点和向量编码的优点进行了分析。最后,本文采用改进的遗传算法对TSP问题的求解过程进行了算法设计和实现,通过试验,得出了一个较理想的结果,验证了本文提出的遗传编码方案的正确性和可行性。更多还原

【Abstract】 The principle and the technology and the theory of genetic algorithm were firstly introduced in this paper, then the travel salesman problem was depicted and its mathematical model was presented. Popular and general algorithm technology was introduced before the improved algorithm was putted, after completely analyzing the disadvantage of the matrix coding, I putted a new coding technique named vector coding, and the algorithm technology based on the vector coding was used for the solution of the TSP. The author presented the MATLAB program based vector coding algorithm for the solution of TSP, the experimentation indicated that the vector coding genetic algorithm take good effect in the solution of the TSP.Hamilton matrix was produced as a new concept in the vector coding technique, according to the vector coding form, a better illegal revising technique was putted forward. The excellence of the technique is to make great efforts not to destroy chromosome’s structure and maintain the similarity of parents and children, which makes chromosome’s structure get inherited in next generation, so the excellent model will be survived. For the sake of the reader being able to understand the motion and the aim of the vector coding technique putted in this paper profoundly, and not making reader confused about vector coding and matrix coding, after putting forward the vector coding genetic algorithm and related technique, the paper narrates the comparison of the vector coding genetic algorithm and the matrix coding genetic algorithm on theory and their essence difference and the analysis on the advantage of the matrix coding technique and the disadvantage of the vector coding technique for the TSP solution.At last, I used the improved genetic algorithm according to the resolving process of the TSP to design and implement, by experiment I gained a perfect result, which verified the correctness and feasibility of the genetic coding project putted in the paper.更多还原