内容发布更新时间 : 2024/11/14 13:02:51星期一 下面是文章的全部内容请认真阅读。

智能优化计算及应用课考核论文 第 1 页

遗传算法在求解最短路径问题中的研究应用

摘 要

TSP 问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种常用方法。本文针对解决TSP 问题,在MATLAB中用遗传算法施行对TSP问题进行了求解，进行了选择、交叉和变异算子进行了算法设计，最后在JAVA软件上进行编程实现。最后探讨了遗传算法解决旅行商问题自身具备的特点[1]。

关键词：遗传算法；TSP问题；JAVA软件

智能优化计算及应用课考核论文 第 2 页

SOLVING TSP (Travelling Salesman Problem ) BASED ON GENETIC

ALGORITHM

Author : Zong Man-yi

Tutor : Qiao Li-hong

Abstract

TSP( Traveling Salesman Problem) is a typical NP complete problem ,genetic algorithm is the perfect method for solving NP complete problem. This paper use genetic algorithm in the MATLAB software to solve the a typical TSP problem . It probes into the realization of genetic operator program through TSP solving by genetic algorithm , design the each function of each genetic operator(select, intercross, mutate). Finally ,We programm in Matlab language and discuss the characteristic of genetic algorithm in solving TSP

Key words : genetic algorithm; TSP JAVA ;

智能优化计算及应用课考核论文 第 3 页

目录

引言 .................................................................... 4

1 GA概述 .......................................................... 4 2 旅行商问题(TSP) .................................................. 4 3 用遗传算法解决旅行商问题 ......................................... 4 4 论文的主要构成 .................................................... 5 遗传算法的设计 .......................................................... 5

1问题分析 ........................................................... 5 2 总体设计 .......................................................... 6 3 详细设计 .......................................................... 8

3.1 编码与随机和初始群体生成 .....................................................................................................................................8 3.2 城市位置及距离矩阵和适应度函数 .........................................................................................................................8 3.4 选择 ............................................................................................................................................................................8 3.4 交叉 ............................................................................................................................................................................9 3.5 变异 ............................................................................................................................................................................9 3.6 群体的跟新和终止条件........................................................................................................................................... 10

MATLAB编程验证 ........................................................ 11

1MATLAB计算 ........................................................ 11 2算法分析优化 ...................................................... 13 结论 ................................................................... 15 参考文献 ............................................................... 16