文档介绍：目录
摘要 1
关键词 1
引言 1
1 遗传算法概论 1
1
遗传算法的基本原理 3
遗传算法基本概念 3
遗传算法基本原理 3
遗传算法的特点 3
2 普通遗传算法 4
普通遗传遗传算法思想 4
普通遗传算法的遗传操作 4
选择(selection)操作 4
交叉(crossover)操作 4
变异(mutation)操作 5
4 遗传算法在TSP问题上的应用 8
TSP问题概述 8
8
8
9
9
10
10
15
停止准则 15
5 TSP问题的实验结果及分析 15
普通遗传算法与佳点集遗传算法的比较与分析 15
15
17
算法运行时间分析 18
总结 18
致谢 18
参考文献 19
ABSTRACT 19
KEY WORDS 19
遗传算法在TSP问题上的应用
摘要:遗传算法(GA)模拟自然进化机制,在搜索优化问题全局或全局附近的最优解上具有较好的鲁棒性、内在的并行性和较优越的稳定性,因而在诸如组合优化、图像处理等方面有着广泛的应用。但是传统的遗传算法性能很大程度上依赖于相关参数的取值与算子的作用方式,佳点集遗传算法利用数论中的佳点集理论和方法,来改进普通遗传算法中的各相关算子,以期克服普通遗传算法收敛速度慢,易陷入局部最优的弱点。本文在分析普通遗传算法和佳点集遗传算法机理上,利用JAVA语言实现了佳点集算法演示系统,通过选取不同的遗传算子来对标准TSP的数据集中的大量数据进行了对比分析和验证。我们的实验结果表明对于较大规模的TSP组合问题佳点集的优势是非常明显的。
关键词: Tsp问题;普通遗传算法;佳点集遗传算法;单切点交叉算子;双切点交叉算子;
循环交叉算子;佳点集交叉算子;
引言
ic Algorithm(GA)是由美国密歇根大学的John H. Holland教授及其学生于20世纪60年代末到70年代初提出的。它是以达尔文的自然进化论“适者生存、优胜劣汰”和孟德尔遗传变异理论为基础,模拟生物进化过程。它具有大范围快速全局搜索能力,能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求的最优解。正是遗传算法的诸多特点,使得它在求解组合优化、机器学习、并行处理等问题上得到了广泛的应用。普通遗传算法是通过模拟染色体群的选择、交叉和变异等操作,不断迭代,最终收敛到高适应度值的染色体,从而求得问题的最优解。但是随着问题规模的扩大,组合优化问题的搜索空间急剧扩大,普通遗传算法的收敛速度慢、易陷入局部最优的缺点就暴露了。而佳点集遗传算法正是通过佳点集的方法改进交叉算子,加快算法收敛到全局最优解的速度,降低发生早熟的概率,提高整个算法的计算效率。
1 遗传算法概论
早在1967年Bagley和Rosenberg就提出了生物遗传算法(GA)的初步思想,1975年由美国Michigan大学的John Holland 的出色工作奠定了遗传学算法的理论基础,遗传变异和优胜劣汰现象的优化搜索算法付诸了实际应用,这也标志着遗传算法的诞生。
到了80年代初期,Holland 的一些学生的毕业论文中对遗传算法的应用以及在应用中遇到的问题进行了研究,其中有Delong(1975)对GA的各种策略的性能和机理进行了大量的细致分析与实验。与此同时Holland还给出了一个自适应的规则学习系统,并于1980年成功地实现了这一学习系统,Holland 及其学生的研究成果使得人们开始看到了GA的应用价值。1981年Betake的博士论文中提出了用Walsh函数来研究遗传算法的方法,Alberta大学的Brindle 在其博士论文中开始对选择策略进行了研究,这一时期的研究回答了GA算法的到底有何意义,有何价值。也正是他们的研究使得更多的人把目光投向了遗传算法,1985年召开了第一届GA国际会议,至此以后每两年召开一次。
80年代中期,遗传算法广泛的应用于许多的应用领域,如TSP问题、调度问题、机器学习、模式分类问题,囚徒困境问题以及多关节机械手轨迹规划问题。
. Goldberg总结了遗传算法的主要成果,全面论述了遗传学的基本原理极其应用,奠定了现代GA的科学基础。
进入90年代,遗传算法迎来了兴盛发展时期,无论是理