|
第一章 基本遗传算法 1.1 遗传算法的产生及发展 copyright paper51.com 最早美国Ｍichigan(密执安大学)的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代De Jong基于遗传算法的思想在计算机上进行了大量纯数值函数优化计算实验。在一系列研究工作的基础上80年代Goldberg进行总结归纳，形成了遗传算的基本框架。 http://www.paper51.com 主要以一些关键人物所做出的主要贡献见证了遗传算法的发展进程: copyright paper51.com 1 J.H.Holland copyright paper51.com 60年代提出在研究和设计人工自适应系统时,可以借鉴生物遗传的机制； copyright paper51.com
70年代初提出了遗传算法的基本定理－模式定理(Schema Theorem)，从而奠定了遗传算法的理论基础； 内容来自www.paper51.com 80年代实现了第一个基于遗传算法的机器学系统－分类器系统(Classifier Systems),开创了基于遗传算法的机器学习的新概念。 paper51.com 2 J.D.Bagley 内容来自www.paper51.com
1967年在其博士论文中首次提出了：“遗传算法”一词，发展了复制、交叉、变异、显性、倒位等遗传算子，创立了自适应遗传算法的概念。 copyright paper51.com 3 K.A.De Jong copyright paper51.com
1975年在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，定义了评价遗传算法性能的在线指标和离线指标。 内容来自论文无忧网 www.paper51.com 4 D.J.Golgberg http://www.paper51.com 1989年出版了专著《搜索、优化和机器学习中的遗传算法(Genetic Algorithms in Search，Optimizationand Machine Learning)》，系统总结了遗传算法的主要研究成果，全面而完整的论述了遗传算法的基本原理及其应用。 内容来自论文无忧网 www.paper51.com 5 L.Davis 内容来自论文无忧网 www.paper51.com 1991年编辑出版了《遗传算法手册 (Handbook of Genetic Algorithms)》书中包括遗传算法在科学计算、工程技术和社会经济中的大量应用实例。 http://www.paper51.com
6 J.R.Koza 内容来自www.paper51.com
1992年将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程(Genetic Programming) 的概念，并成功的将其提出的遗传编程应用于人工智能、机器学习符号处理等方面。 内容来自论文无忧网 www.paper51.com 1.2 基本原理 copyright paper51.com 遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法，由美国J.Holland教授提出，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是一种全局化搜索算法，尤其适用于传统搜索算法难于解决的复杂和非线性问题。 paper51.com
选择(selection)算子、交叉(crossover)算子和变异(mutation)算子是遗传算法的3个主要操作算子。遗传算法中包含了如下5个基本要素: copyright paper51.com (1) 对参数进行编码； 内容来自www.paper51.com
(2) 设定初始种群大小； http://www.paper51.com (3) 适应度函数的设计； copyright paper51.com (4) 遗传操作设计； 内容来自www.paper51.com (5) 控制参数设定(包括种群大小、最大进化代数、交叉率、变异率等)。 内容来自www.paper51.com 1.3 遗传算法的特点 http://www.paper51.com (1) 遗传算法对优化问题没有太多的数学要求，而且只要知道目标函数的信息即可； 内容来自www.paper51.com (2) 遗传算法采用的是启发性的知识智能搜索算法，在搜索高度空间复杂问题上比以往有更好的效果； 内容来自www.paper51.com (3) 遗传算法是对问题参数或者变量编码群进行优化，而不是参数或变量本身； 内容来自论文无忧网 www.paper51.com (4) 遗传算法使用的选择、交叉、变异算子都是随机的； paper51.com 1.4 基本遗传算法描述 paper51.com
基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子来模仿不同环境下生物遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个特点，Goldberg总结出了一种统一的最基本的遗传算法——基本遗传算法（SimpleGenetic Algorithms，简称SGA）。基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。 内容来自www.paper51.com 基本遗传算法描述： paper51.com 基本遗传算法只使用选择算子 ( Selection Operator)、交叉算子(Crossover Operator)、变异算子(Mutation Operator)这三种算子。 paper51.com
基本遗传算法可以形式化定义为一个八元组：SGA=(C,E,Po,M,φ,τ,ψ,T) copyright paper51.com
C ——个体的编码方法； 内容来自论文无忧网 www.paper51.com E ——个体适应度评价函数； http://www.paper51.com Po——初始群体； 内容来自论文无忧网 www.paper51.com M ——群体大小； paper51.com φ ——选择算子； paper51.com τ ——交叉算子； http://www.paper51.com ψ ——变异算子； 内容来自www.paper51.com T ——遗传运算终止条件。 内容来自www.paper51.com
遗传算法的应用步骤： paper51.com 第一步： 确定决策变量及其各种约束条件，即确定出个体的表现型X和问题的解空间。 copyright paper51.com
第二步： 建立优化模型，即确定出目标函数的类型(是求目标函数的最大值还是求目标函数的最小值？)及其数学描述形式或量化方法。 http://www.paper51.com 第三步：确定表示可行解的染色体编码方法，也即确定出个体的基因型X及遗传算法的搜索空间。 http://www.paper51.com 第四步：确定解码方法，即确定出个体基因型X到个体表现型X的对应关系转换方法。 内容来自www.paper51.com
第五步：确定个体适应度的量化评价方法，即确定出由目标函数值f(X)到个体适应度F(X)的转换规则。 http://www.paper51.com 第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。 copyright paper51.com
第七步：确定遗传算法的有关运行参数，即确定出遗传算法的M、T、Pc、Pm等参数。 http://www.paper51.com |