《毕业论文遗传算法在函数优化中的应用》由会员分享，可在线阅读，更多相关《毕业论文遗传算法在函数优化中的应用（23页珍藏版）》请在金锄头文库上搜索。
1、潍坊学院本科毕业论文遗传算法在函数优化中的应用目录1.绪论11.1概述11.2遗传算法的发展历史与研究进展22.遗传算法流程与应用举例42.1遗传算法中各重要因素分析42.2重要参数设置62.3简单的遗传算法运算示例63.遗传算法在函数优化应用中的性能研究103.1遗传算法在实际应用中的性能影响因素103.2函数优化问题的描述123.3求解函数优化问题的最优交叉、变异率组合的研究143.4一种求解函数优化问题的自适应遗传算法173.5小结19结束语19参考文献20致谢21211.绪论1.1概述遗传算法(genetic algorithms简称GA)由美国密歇根大学的John HHolland教
2、授等创立的一类仿生型的优化算法。它是以达尔文的生物进化论和孟德尔的遗传变异理论为基础、模拟生物进化过程、自适应启发式全局优化的搜索算法。由于遗传算法无需过多地考虑问题的动力学信息，如连续、可微等，该算法结构简单，并且具有全局搜索能力、信息处理的隐并行性、鲁棒性和可规模化等优点，它在思路上突破原有的最优化方法的框架，尤其适用于处理传统搜索方法难以解决的复杂和非线性问题，现己被广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，并且在经济和决策方面也有很好的应用，是21世纪有关智能计算中的关键技术之一。遗传算法的处理对象不是参数本身，而是对参数进行了编码的个体，因此不仅可以对传统的目
3、标函数优化求解，而且可以处理诸如矩阵、树和图等结构形式的对象，用适应度函数同时对搜索空间的多个解进行评估，它将每个可能的问题表示为“染色体”，然后按遗传学规律进行选择、交叉和变异操作，直到满足终止条件为止。隐含并行性和全局搜索性是遗传算法的两大特点，前者可使遗传算法只需检测少量的结构就能反映搜索空间的大量区域，后者则使遗传算法具有良好的稳健性。在遗传算法的诸多应用中，函数优化是最显而易见的应用，也是经典的应用。函数优化问题是许多领域中普遍存在的问题，也一直是人们探索的若干重要问题之一。很多复杂的问题，如神经网络的训练、系统模型参数的辨识等，可以转化为函数优化问题来求解。函数优化的本质就是从所有
4、可能的方案中选择出最合理、达到最优目标的方案。它通常可归结为求最小值问题，对于最大值问题可以通过对函数取反，将其转化为最小值问题。对于函数优化问题，传统的求解方法有最速下降法、牛顿法、拉格朗日乘数法、罚函数法等等。对于这些确定的搜索优化方法来说，函数可微通常是求解问题的前提，而且随着函数维数的增长，求解的难度大幅度增长。因此传统的优化方法并不适合于求解不可微函数以及高维函数的优化问题。一种模仿生物自然进化过程的、被称作为演化算法的随机优化技术在解这类优化难题中显示出了优于传统优化算法的性能。自70年代Holland正式提出遗传算法以来，非经典的随机搜索优化方法如演化策略、演化规划、基因表达式程
5、序设计等层出不穷。遗传算法就是其中一种具有代表性的随机算法，与传统的优化算法相比，遗传算法不是从单个点，而是从点的群体开始搜索，对初始点集的要求不高；遗传算法不是直接在参变量集上实施，而是利用参变量集的某种编码；遗传算法利用适应值信息，无需导数或其他辅助信息，这就使得它在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的、非规则的或有噪声的情况下，它也能以较大的概率找到整体最优解。1遗传算法优化求解过程与梯度信息无关，只需要目标函数是可计算的，对于复杂的优化问题只需选择、杂交、变异三种遗传运算就能得到优化解，基于这些显著的优点，GA已引起人们的广泛应用和研究。1.2遗传算法的发展
6、历史与研究进展1.2.1遗传算法的发展历史遗传算法的发展历史始于二十世纪60年代。JHHolland教授认识到生物的遗传和自然进化现象与人工自适应系统的相似关系，提出在研究和设计人工自适应系统时，可以借鉴生物的遗传机制，以群体的方式进行自适应搜索。1967年，Holland的学生Bagley在他的博士论文中首次提出了“遗传算法”这一术语，提出选择、交叉和变异，与目前遗传算法中相应的算法十分接近，引入适应度定标(Scaling)的概念。同时，他也首次提出了遗传算法自我调整的概念。第一个把遗传算法用于函数优化的是Hollstien，1971年他在论文计算机控制系统中的人工遗传自适应方法(Artif
7、icial Genetic Adaptation in Computer ControlSystems)中阐述了遗传算法用于数学反馈控制的方法，主要讨论了二变量函数的优化问题。1975年，Holland出版了第一部著名的专著自然系统和人工系统的适配(Adaptation in Natural and Artificial Systems)，该书系统地阐述遗传算法的基本理论和方法，并提出了遗传算法的基本定理模式定理(Schema Theorem)，奠定了遗传算法的理论基础。同年，美国De Jong博士在其论文遗传自适应系统的行为分析中结合模式定理进行了大量的纯数值函数优化计算实验，建立了遗传算法
8、的工作框架，将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟(generationgap)等新的遗传操作技术，建立了著名的De Jong五函数测试平台。80年代，Holland教授实现了第一个基于遗传算法的机器学习系统分类系统(Classifier System)，开创了基于遗传算法的机器学习的新概念，为分类器在构造上提出了一个完整的框架。1987年，Davis出版了Genetic Algorithm and SimulatedAnnealing一书，以论文集形式用大量的实例介绍了遗传算法的应用技术。1989年，Goldberg出版了专著遗传算法在搜索优化和机器学习中的应用(Ge
9、netic Algorithms in Search，Optimization and Machine Learning)，该书系统总结了遗传算法的主要成果，对GA的基本原理及应用做了比较详细、全面的论述，奠定了现代遗传算法的科学基础。该书至今仍是遗传算法研究中广泛适用的经典之作。此后，许多学者对原来的遗传算法(或称基本遗传算法)进行了大量改进和发展，提出了许多成功的遗传算法模型，从而使遗传算法应用于更广泛的领域。进入90年代后，遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为迅速，在各种不同领域如机器学习、模式识别、神经网络、控制系统优化及社会科学等中得到广泛应用，引起了许多学者的关
10、注。1991年，Lawrence Davis出版了遗传算法手册(Handbook ofGeneticAlgorithm)一书，对有效地应用遗传算法具有重要的指导意义。国外出现了一些著名学者，如Holland，Goldberg，Davis等，其经典著作也鲜为人知，国内也有一些有关的书籍相继出版，一系列以遗传算法为主题的国际会议变得十分活跃。从1985年开始，国际遗传算法会议，即ICGA(InternationalConference on Genetic Algorithm)每两年举行一次；在欧洲，从1990年开始也每隔一年举办一次类似的会议，即PPSN(Parallel Problem Sal
11、ving from Nature)会议；目前与GA有关的学术会议有：世界计算智能大会，它是IEEE主办的综合性学术大会，有ICNN、FUZZY IEEE和ICEC三个学术会议联合组成，每四年召开一次；此外，还有ANN&GA、EP、GP、EP、SEAL等和Internet上专门的遗传算法站点更是推动着遗传算法实质性的进展。进入21世纪，以不确定性、非线性、时间不可逆为内涵的复杂性科学已成为一个研究热点。遗传算法因能有效地求解NP难问题以及非线性、多峰函数优化和多目标优化问题，得到了众多学科的高度重视，同时也极大地推动了遗传算法理论研究和实际应用的不断深入与发展，目前已在世界范围内掀起关于GA的研
12、究与应用热潮，可以预测随着进化论、遗传学、分子生物学、计算机科学的进展，GA也将在理论与应用中得到发展和完善。1.2.2遗传算法的常见应用(1)函数优化函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。对于解变量是实数型的优化问题，为提高GA的搜索效率，可采用动态编码和实数编码。对于带约束的优化问题，引入罚函数，把约束条件结合到且标函数定义中。樊重俊用特定的杂交、变异算子在一定程度上解决了线性等式优化问题；对于多峰函数优化问题，1987年Goldberg和Richardson用共享和限制交配机制结合的方法成功实现了多峰的搜索；袁丽华等利用小生境技术，成功实现多峰的搜索；2
13、000年刘洪杰等M利用多种算子混合的方法来搜索多极值点，该算法对等高等距、不等高等距和不等高不等距情况都有好的结果。对于多目标函数的优化问题，多数情况下，最优解是不存在的，一般找到其Pareto最优解或非劣解，这仍是个值得研究的新课题，也是当前管理科学、决策理论、系统工程、运筹学等学科研究中十分重要的内容。(2)组合优化组合优化问题，通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全问题，很难求出最优解。实践表明遗传算法求解组合优化问题非常有效。如GA在求解巡回旅行商问题、装箱问题、背包问题、图形划分问题等方面得到成功地应用；唐立新、张毅、曾三友等学
14、者在各自的研究领域已取得一定的成果。(3)遗传编程与学习Koza成功地把他提出的遗传编程的方法应用于人工智能、机器学习、符号处理等方面。Kinnear提出了基于遗传算法的移动机器人路径的新方法；基于GA的机器学习特别是分类器系统已被用于学习模糊控制规则、人工神经网络的连接权和结构优化等领域，也是目前遗传算法研究中一个十分活跃的领域。(4) 自动控制遗传算法已在自动控制领域得到了初步应用，并取得良好的效果。如基于GA的模糊控制器的优化设计，用GA进行航空控制系统的优化；20世纪80年代，Goldberg用GA学会控制天然气输气管道系统；机器人控制等等唧。此外，遗传算法也在生产调度问题、图像与信号
15、处理、设计、人工生命等方面获得了广泛的运用。这里就不一一赘述了。总之，随着研究的深入，算法不断地被改进，遗传算法的应用领域将会越来越广，效果也越来越好。2.遗传算法流程与应用举例2.1遗传算法中各重要因素分析2.1.1编码理论遗传算法需要采用某种编码方式将解空间映射到编码空间（可以是位串、实数、有序串）。类似于生物染色体结构，这样容易用生物遗传理论解释，各种遗传操作也易于实现。编码理论是遗传算法效率的重要决定因素之一。二进制编码是最常用的编码方式，算子处理的模式较多也较易于实现。但是，在具体问题中，根据问题的不同，采用适合解空间的形式的方式进行编码，可以有效地直接在解的表现型上进行遗传操作，从
16、而更易于引入相关启发式信息，往往可以取得比二进制编码更高的效率。2.1.2 染色体每个编码串对应问题的一个具体的解，称为染色体或个体。一个染色体可以通过选用的编码理论与问题的一个具体的解相对应，一组固定数量的染色体则构成一代群体。群体中染色体可重复。2.1.3 随机初始化随机或者有规律（如从一个已知离解较近的单点，或者等间隔分布地生成可行解）生成第一代群体。一次遗传算法中有目的采用多次初始化群体会使算法拥有更强的搜索全局最有解的能力。2.1.4适应度一个染色体的适应度是对一个染色体生存能力的评价，它决定了该染色体在抽取操作中被抽取到的概率。估价函数是评价染色体适应度的标准，常见的估价函数有：直接以解的权值（如01背包问题以该方案装进背包物品的价值作为其适应度），累计二进制串中1/0
