《山东理工大学信科专业毕业论文》由会员分享，可在线阅读，更多相关《山东理工大学信科专业毕业论文（45页珍藏版）》请在金锄头文库上搜索。
1、 SHANDONG毕业论文遗传算法用于优化计算问题的研究学 院： 理学院 专 业： 信科0801 学生姓名： 学 号： 指导教师： 20 12 年 6 月2 摘 要摘要遗传算法是基于“适者生存”的一种高度并行、随机和自适应的全局搜索优化算法，它将问题的求解表示成个体的适者生存过程，通过种群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。遗传算法被成功地用于各种不同领域，如组合优化，图像处理，模式识别，智能控制，机器学习，数据挖掘等多个领域，而优化计算问题是对遗传算法进行性能评价的常用算例。本文将系统地论述了遗传算法在优化计算问题中的应
2、用，采用基于遗传算法的函数优化问题的通用框架，用遗传算法求解函数优化问题为研究对象，通过对连续函数以及0-1背包、TSP等离散问题的实例分析及计算，得出较为理想的结果。关键词：遗传算法 ，优化计算 ，0-1背包问题 ， TSP问题I Abstract Genetic Algorithm (GA) is a highly parallel, random and adaptive optimization search algorithm based on the mechanics of survival of fittest.It makes problem solving as indiv
3、idual survival of the fittest process, evolving populations from generation to generation, including selection, crossover and mutation operations, and eventually converge to the best adapted to the environment individuals, in order to obtain the optimal solution of the problemor satisfactory solutio
4、n.The genetic algorithm was successfully used in various fields, such as combinatorial optimization, image processing, pattern recognition, intelligent control, machine learning, data mining, and other fields.,but function optimization is a common example of genetic algorithm.The paper systematicall
5、y discuss the research work of applying genetic algorithm to solve mathematical function optimization problems.General framework and procedures to solve function optimization problem using genetic algorithm is proposed.through extensive analysis and calculation examples,such as continuous function,t
6、he Knapsack Problem and the Traveling Salesman Problem,effective results have been obtained. Key Words: Genetic Algorithm , Optimization, Knapsack Problem ,Traveling Salesman ProblemII 摘 要IAbstractII第一章 引言11.1概述11.2遗传算法的发展历史及研究进展21.3本课题研究的目的和意义4第二章 遗传算法的基本理论52.1数学基础52.1.1 模式定理52.1.2隐含并行性62.2遗传算法的运算流
7、程62.3遗传操作82.3.1编码82.3.2适应度函数82.3.3遗传算子9第三章 优化计算123.1连续函数优化123.1.1编码和产生初始化种群133.1.2解码133.1.3计算适应度143.1.4优化计算结果173.1.5 MATLAB遗传算法工具箱183.2离散问题优化213.2 .1 0-1背包问题213.2.2 遗传算法求解TSP问题23结 论30参考文献32致 谢33 第一章 引言1.1概述 遗传算法是基于“适者生存”的一种高度并行、随机和自适应的全局搜索优化算法，它将问题的求解表示成个体的适者生存过程，通过种群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应
8、环境”的个体，从而求得问题的最优解或满意解。因为遗传算法不需要过多地考虑问题具体的信息，如是否可导、是否连续等，且遗传算法框架结构比较简单，能够应用于许多问题的全局优化，具有隐含并行性、鲁棒性和大规模计算等优点。遗传算法突破了以往的全局优化方法的基本框架，在处理传统的优化搜索方法难以解决的复杂的组合优化问题，如背包问题、TSP问题等，能够取得比较好的结果。 遗传算法不以参数本身为处理对象，而对参数进行编码，然后对编码后的个体进行优化搜索。遗传算法不仅能够对连续函数进行优化计算，而且能够对离散问题，如0-1背包、TSP问题等，进行优化计算。每个编码后的个体代表问题域的一个可行解，遗传算法根据适应
9、度函数对问题域的每个可行解进行评价，然后根据遗传算法的基本框架进行选择、交叉和变异操作，当满足最优化条件时，输出问题的最优解。 优化计算问题是存在于众多研究领域，吸引了来自各行各业的研究人员采用不同的方法来解决它。对于许多复杂的问题，如神经网络的训练、系统模型参数的辨识等，可以转化为优化计算问题来求解。优化计算的本质上是从问题域的所有可行解中选择出能够达到最优目标的解，一般可以分为最大值问题和最小值问题。对于优化计算问题，使用传统的求解方法，如枚举法、启发式算法、搜索算法等，随着问题的种类的不同和问题规模的扩大，传统的求解方法将很难得到最优解，而遗传算法为我们提供了一种求解优化问题的通用框架，
10、通过对种群施加的迭代进化过程，不断地将当前代种群中适应度较高的个体遗传到下一代群体中，并且不断地淘汰适应度较低的个体，从而能够找出适应度最大的个体。这个适应度最大的个体经解码处理之后所对应的个体表现型就是这个实际应用问题的最优解或近似最优解。1.2遗传算法的发展历史及研究进展 20世纪60年代末70年代初，美国Michigan大学的John Holland及其同事、学生们形成了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。1967 年，Holland的学生Bagley在他的博士论文中首次提出了“遗传算法”这一术语，提出选择、交叉和变
11、异，与目前遗传算法中相应的算法十分接近，引入适应度定标(Scaling)的概念。同时，他也首次提出了遗传算法自我调整的概念。 Hollstien首次将遗传算法用于函数优化计算，1971 年在他的论文“ Artificial Genetic Adaptation in Computer Control Systems”中系统的阐述了将遗传算法用于数学反馈控制的方法，主要讨论了二变量函数的优化问题。 1975 年，Holland 出版了开创性著作“Adaptation in Natural and Artificial Systems”，以后Holland等人将该算法加以推广，应用到优化和机器学习
12、等问题中并正式定名为遗传算法。该书系统地阐述了遗传算法的基本理论和方法，并提出了遗传算法的基本定理模式定理(Schema Theorem)，奠定了遗传算法的理论基础。同年，美国 De Jong 博士在其论文遗传自适应系统的行为分析中结合模式定理进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟(generationgap)等新的遗传操作技术，建立了著名的 De Jong 五函数测试平台。 对遗传算法影响力最大的专著，要属于1989年美国伊利诺大学的Goldberg所著的“Genetic Algorithm in Sear
13、ch，Optimsization，and Machine Learning”。这本书对于遗传算法的理论及其多领域的应用展开了较为全面的分析和例证。1992年，Michalewicz出版了另一部很有影响力的著作“Genetic Algorithm+Data Structure=Evolution Programs”对遗传算法应用于最优化问题起到了推波助澜的作用。 以遗传算法、进化计算为主题的多个国际会议在世界各地定期的召开。1985年，在美国卡内基梅隆大学召开了第一届国际遗传算法ICGA85，以后该会议每隔一年举行一次。1997年夏季在美国密西根大学召开了ICGA97。现在与之平行的国际会议很多
14、，其中International Conference on Evolutionary Programming和IEEE Conference on Evolutionary Computation每隔2年和4年召开一次。在欧洲，从1990年开始每隔一年举办一次Parallel Problem Solving from Nature 学术会议，其中遗传算法是会议主要内容之一。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。 在国内，有关遗传算法的研究，自本世纪以来一直处于不断上升的时期，特别近年来，遗传算法的应用在许多领域取得了令人瞩目的成果，该类研究获得不同渠道的经费资助比例也在逐年上升。其中较突出的研究成果有：2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题；2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法 Parallel GA，
