学位论文 > 优秀研究生学位论文题录展示

佳点集遗传算法的理论和应用

作　者: 赵春英
导　师: 张铃
学　校: 安徽大学
专　业: 计算机应用技术
关键词: 遗传算法数论方法佳点集遗传算法组合优化背包问题 TSP问题测试集 NP完全问题
分类号: TP18
类　型: 硕士论文
年　份: 2001年
下　载: 231次
引　用: 1次
阅　读: 论文下载

内容摘要

遗传算法是用计算机模拟生物进化思想的优化算法，首先由美国Michigan大学的John Holland教授于1975年提出。它在固定的种群规模下，仅利用个体适应度来引导搜索，通过按照一定概率进行选择、杂交和变异遗传操作完成群体的更新，因此遗传算法实际是一种“盲目的概率启发搜索策略”。由于它使用简单，鲁棒性强，易于并行化，在各个领域得到广泛应用。本文介绍了数论在统计中的应用，并利用数论中的佳点集理论和方法，对遗传算法中的交叉操作进行了重新设计，给出了一个新的GA算法，称为佳点集遗传算法。我们将佳点集遗传算法应用于求解几类典型的组合优化问题（如背包问题和TSP问题），并与传统遗传算法进行比较，可以看出该算法不仅提高了求解的效率和精度，还有效地避免了“早熟”现象。本文还讨论了对于任给一类NPC问题，如何给出一组测试样本集，利用这个测试集，能比较合理地估计出求解这类NPC问题的算法的计算能力和复杂性，从而可以用此测试集来分析各种算法的优劣。我们利用数论中的佳点集理论给出构造算法测试集的方法，最后以TSP问题和背包问题为例给其对应的算法测试集。本论文共分五章：第一章扼要介绍了遗传算法的原理、特点和发展进程；第二章探讨了数论方法在统计中的应用，给出了生成C~s上数论网格的有效方法——佳点集方法；第三章阐述了佳点集的基本定义和性质，对交叉操作进行改进，给出了佳点集遗传算法；第四章分析了佳点集遗传算法应用于背包问题和TSP问题的算法实现和实验结果；第五章提出了用佳点集理论构造算法测试集的方法，并给出实例。

佳点集遗传算法的理论和应用

内容摘要

全文目录

相似论文