【作者】 张挺；

【导师】 李艳萍；

【作者基本信息】 太原理工大学 ， 通信与信息系统， 2008， 硕士

【摘要】 自然界的生物进化是一个不断循环的过程,在这一个过程中,生物群体也就不断的完善和发展。可见,生物进化过程本质上是一种优化过程,在计算科学上具有直接的借鉴意义。人们模仿生物的遗传和进化机制,提出了遗传算法。由于遗传算法的普适性和鲁棒性,遗传算法在机器人路径规划,公路路径设计等许多工程领域都发挥了重要的作用。由于TSP(Traveling Salesman Problem)与众多网络优化问题在形式上有一定的相似性,所以研究遗传算法在TSP问题中的应用对后续问题的展开有一定的指导意义。随着程控交换机的大量运用,中国七号信令网在我国的应用已经全面铺开。因此NO.7信令网的规划就显的日益重要。其中,A/B平面划分是一个用传统方法难以解决的NPC(Nondeterministic Polynomial complete)问题,它和图的划分问题有类似的地方,但也有其自身的特点。本文所做的主要工作概括如下:1.建立了TSP问题的数学模型,在介绍传统遗传算法和贪婪算法的基本原理的基础上,研究了用传统的遗传算法和贪婪算法解决问题的方法,并且对国际通行的TSPLIB中两个不同规模的问题进行了仿真。2.本文提出了一种新型的遗传变异算子,该算子针对遗传算法在求解TSP问题后期遇到收敛瓶颈的缺点,有目地的加大了种群的搜索空间,使得种群最优值能够迅速的向函数最优值靠拢。仿真试验表明,改进后的遗传算法在性能上有了显著的改进。3.比较传统遗传算法、贪婪算法,改进遗传算法在解决TSP问题时的性能,指出了三种算法在寻优性能上的差距,解释了改进后算法性能改变的原因。4.建立了七号信令网A/B平面划分的数学模型,并且用传统的遗传算法和本文提出的遗传算法对数学模型进行仿真,比较了两种算法在网络优化问题上的性能差异。最后就新旧算法耗时和网络的规模关系进行了仿真。更多还原

【Abstract】 The evolutionary of nature is a cycle process. In this process,the biotic population continuously develop and improve themselves, It is obviously that the evolutionary process is alike an optimization process. we can directly learn it in compute science. People simulate the biological evolution and inheritance system, then they give a new optimization algorithm--GA (genetic algorithm). Because of the common adaptation and the robustness, GA is extensively used in many aspects of engineering. For example in the route planning of robot and the design of road. So the research of the GA is meaningful.Because the TSP problem (Traveling Salesman Problem) is often used to test the performance of algorithm and it has some degree likeness of many network route optimization questions, the application of GA in TSP can give some guides to solve the net route optimization question.With the use of SPC exchange,NO.7 signal network has become a supporting network of telephone network, so the planning of NO.7 network become more important than past. In this problem, The division of A/B plane is a NPC problem for a traditional algorithm, it have some degree likeness with other figure division questions, but it also have some unique characteristics.The major work of this paper can be summarized as follows:1. This paper establishes the model of TSP problem. Based on the traditional genetic algorithm and greedy genetic algorithm, the method of solving TSP problem based on two algorithms are introduced. Then, this paper get the simulation figures of two examples of TSPLIB.2. In order to overcome the difficulty of slow convergence of GA, This paper give a new mutation operator to solve this problem. The operator purposefully enlarge the searching space and make the best value of population converge to the best value of function. The simulation shows the improve algorithm can make the algorithm performance become better.3. To compare the performances of three algorithms, it points out the difference of three alogirithms in searching the best value respect and explains the cause of the change of the algorithm performance.4.This paper establishes A/B devision model, devised the traditional genetic algorithm and improving algorithm to simulate the problem. It also compare the performance difference of two algorithms. Lastly,the paper also simulated the relation of cost time and net-scale.更多还原