遗传算法原理与应用实例pdf

遗传算法原理与应用

遗传算法原理与应用唐 慧 丰

2006 年 5 月

遗传算法原理与应用

报告提纲一、遗传算法概述

二、遗传算法原理 三、遗传算法的应用

遗传算法原理与应用

一、遗传算法概述1、智能优化算法 2、基本遗传算法 3、遗传算法的特点

遗传算法原理与应用

1、智能优化算法智能优化算法又称为现代启发式算 法，是一种具有全局优化性能、通用性 强、且适合于并行处理的算法。这种算 法一般具有严密的理论依据，而不是单 纯凭借专家经验，理论上可以在一定的 时间内找到最优解或近似最优解。

遗传算法原理与应用

常用的智能优化算法(1)遗传算法 (Genetic Algorithm, 简称GA)

(2)模拟退火算法(Simulated Annealing, 简称SA)

(3)禁忌搜索算法(Tabu Search, 简称TS)

……

遗传算法原理与应用

智能优化算法的特点它们的共同特点：都是从任一解出发， 按照某种机制，以一定的概率在整个求解 空间中探索最优解。由于它们可以把搜索 空间扩展到整个问题空间，因而具有全局 优化性能。

遗传算法原理与应用

遗传算法起源遗传算法是由美国的J. Holland教授于 1975年在他的专著《自然界和人工系统的 适应性》中首先提出的，它是一类借鉴生

遗传算法的程序实例

f(x)=10*sin(5x)+7*cos(4x) x∈[0,10] 一、初始化(编码)

initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)，

长度大小取决于变量的二进制编码的长度(在本例中取10位)。 代码:

%Name: initpop.m %初始化

function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength));

% rand随机产生每个单元为 {0,1} 行数为popsize，列数为chromlength的矩阵， % roud对矩阵的每个单元进行圆整。这样产生的初始种群。 二、计算目标函数值

1、将二进制数转化为十进制数(1) 代码:

%Name: decodebinary.m

%产生 [2^n 2^(n-1) ... 1] 的行向量，然后求和，将二进制转化为十进制 function pop2=decodebinary(pop)

[px,py]=size(pop);

挺好

遗传算法原理及其应用王正山 wzs@

挺好

第三章 遗传算法的基本实现技术 掌握编码方法 掌握适应度函数的设计方法 掌握选择、交叉、变异算子的设计方法 了解遗传算法的运行参数设置 掌握约束条件处理方法 掌握Matlab遗传算法工具箱

挺好

3.1 编码方法 编码– 在遗传算法中如何描述问题的可行解，即把一个问题的可行解从 其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编 码。设计一个完美的编码方案是遗传算法的应用难点之一。 设计一个完美的编码方案是遗传算法的应用难点之一。 设计一个完美的编码方案是遗传算法的应用难点之一

编码规则– 有意义的积木块编码原则：应使用能易于产生与所求问题相关的 有意义的积木块编码原则 且具有低阶、短定义长度模式的编码方案。 – 最小字符集编码原则 最小字符集编码原则：应使用能使问题得到自然表示或描述的具 有最小编码字符集的编码方案。

编码分类– 二进制编码方法 – 浮点编码方法 – 符号编码方法

挺好

3.1.1 二进制编码方法 二进制编码方法– 二进制编码方法使用的编码符号集是由二进制符号0和1所组成 的二值符号集{0,1},它构成的个体基因型是一个二进制编码的 符号串。 – 二进制

最新发布的MATLAB Release 14已经包含了一个专门设计的遗传算法与直接搜索工具箱（Genetic Algorithm and Direct Search Toolbox，GADS）。使用遗传算法与直接搜索工具箱，可以扩展MATLAB及其优化工具箱在处理优化问题方面的能力，可以处理传统的优化技术难以解决的问题，包括那些难以定义或不便于数学建模的问题，可以解决目标函数较复杂的问题，比如目标函数不连续、或具有高度非线性、随机性以及目标函数没有导数的情况。

本章节首先介绍这个遗传算法与直接搜索工具箱，其余各节分别介绍该工具箱中的遗传算法工具及其使用方法。

遗传算法与直接搜索工具箱概述

本节介绍MATLAB的GADS（遗传算法与直接搜索）工具箱的特点、图形用户界面及运行要求，解释如何编写待优化函数的M文件，且通过举例加以阐明。

8.1.1 工具箱的特点

GADS工具箱是一系列函数的集合，它们扩展了优化工具箱和MATLAB数值计算环境的性能。遗传算法与直接搜索工具箱包含了要使用遗传算法和直接搜索算法来求解优化问题的一些例程。这些算法使我们能够求解那些标准优化工具箱范围之外的各种优化问题。所有工具箱函数都是MATLAB的M文件，这些文件由实现特定优化算

第八章 使用MATLAB遗传算法工具

最新发布的MATLAB 7.0 Release 14已经包含了一个专门设计的遗传算法与直接搜索工具箱（Genetic Algorithm and Direct Search Toolbox，GADS）。使用遗传算法与直接搜索工具箱，可以扩展MATLAB及其优化工具箱在处理优化问题方面的能力，可以处理传统的优化技术难以解决的问题，包括那些难以定义或不便于数学建模的问题，可以解决目标函数较复杂的问题，比如目标函数不连续、或具有高度非线性、随机性以及目标函数没有导数的情况。

本章8.1节首先介绍这个遗传算法与直接搜索工具箱，其余各节分别介绍该工具箱中的遗传算法工具及其使用方法。

8.1 遗传算法与直接搜索工具箱概述

本节介绍MATLAB的GADS（遗传算法与直接搜索）工具箱的特点、图形用户界面及运行要求，解释如何编写待优化函数的M文件，且通过举例加以阐明。

8.1.1 工具箱的特点

GADS工具箱是一系列函数的集合，它们扩展了优化工具箱和MATLAB数值计算环境的性能。遗传算法与直接搜索工具箱包含了要使用遗传算法和直接搜索算法来求解优化问题的一些例程。这些算法使我们能够求解那些标准优化工具箱范围之外的各种优化

关于遗传算法的介绍和简单应用。

遗传算法

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。

基本概念

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。 对于一个求函数最大值的优化问题(求函

数最小值也类

遗传算法的泛函极值求解与应用

维普资讯 http://www.77cn.com.cn

Vo . 2. 1 3 No. 2 1

火力与指挥控制Fie CO lr 1a d Co r r O n mma d Co t o t n nr1

De e e 2 0 c mb r, 0 7

第 3 2卷第 l期 2 2 0年 1月 07 2

文章编号：0 20 4 (0 7 1—020 1 0—6 0 2 0 )20 5—3

,n\ 1 I

遗传算法的泛函极值求解与应用*

肖兆银，德云周(西北工业大学，西陕西安 70 7 ) 1 0 2

摘

要：径规划可以描述为泛函极值模型。针对传统的变分法、大值原理等求解泛函目标函数类型有限的局限性，路最考

虑遗传算法在解空间中进行随机优化搜索的特点，入遗传算法对泛函极值问题进行求解，出了求解过程。该方法具有广引给泛适应性，值仿真结果表明了该算法的有效性和合理性。最后得到了飞行器飞行的最优控制规律和最优路径。数 关键词：函极值，传算法，优控制，径规划泛遗最路中图分类号： 4 01 7 V2, 7文献标识码： A

S l i n a p lc to f Fu to lM i m i a i n o uto nd A p i a

遗传算法的泛函极值求解与应用

维普资讯 http://www.77cn.com.cn

Vo . 2. 1 3 No. 2 1

火力与指挥控制Fie CO lr 1a d Co r r O n mma d Co t o t n nr1

De e e 2 0 c mb r, 0 7

第 3 2卷第 l期 2 2 0年 1月 07 2

文章编号：0 20 4 (0 7 1—020 1 0—6 0 2 0 )20 5—3

,n\ 1 I

遗传算法的泛函极值求解与应用*

肖兆银，德云周(西北工业大学，西陕西安 70 7 ) 1 0 2

摘

要：径规划可以描述为泛函极值模型。针对传统的变分法、大值原理等求解泛函目标函数类型有限的局限性，路最考

虑遗传算法在解空间中进行随机优化搜索的特点，入遗传算法对泛函极值问题进行求解，出了求解过程。该方法具有广引给泛适应性，值仿真结果表明了该算法的有效性和合理性。最后得到了飞行器飞行的最优控制规律和最优路径。数 关键词：函极值，传算法，优控制，径规划泛遗最路中图分类号： 4 01 7 V2, 7文献标识码： A

S l i n a p lc to f Fu to lM i m i a i n o uto nd A p i a

1 遗传算法的原理

1.1 遗传算法的基本思想

遗传算法（genetic algorithms，GA）是一种基于自然选择和基因遗传学原理，借鉴了生物进化优胜劣汰的自然选择机理和生物界繁衍进化的基因重组、突变的遗传机制的全局自适应概率搜索算法。

遗传算法是从一组随机产生的初始解（种群）开始，这个种群由经过基因编码的一定数量的个体组成，每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，其内部表现（即基因型）是某种基因组合，它决定了个体的外部表现。因此，从一开始就需要实现从表现型到基因型的映射，即编码工作。初始种群产生后，按照优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。

计算开始时，将实际问题的变量进行编码形成染色体，随机产生一定数目的个体，即种群，并计算每个个体的适应度值，然后通过终止条件判断该初始解是否是最优解，若是则停止计算输出结果，若不是则通过遗传算子操作产生新的一代种群，回到计算群体

遗传算法属于人工智能的算法,但是其经过改进可以用来进行数据的挖掘

维普资讯

遗传算法在数据挖掘中的应用李康顺 1,李元香， 2 3滕冲王玲玲 (武汉大学软件工程国家重点实验室，武汉 4 0 7 ) 30 2 (西理工大学信息工程学院，江江西 3 10 ) 4 0 0

(武汉大学计算机学院，武汉 4 0 7 ) 3 0 2摘要论文介绍一种利用遗传算法的演化计算机编程的方法来自动建立一种动态非线性数学模型进行数据挖掘，并进行社会经济趋势预测和回归曲线拟舍，变过去那种只使用拟舍粗糙、测结果准确度差的传统预测模型进行曲线拟改预合和趋势预测的分析方法。数据实验中，用遗传算法演化计算机编程的方法自动生成的演化模型对一些真实的历史在使

资料进行了曲线拟合和发展趋势预测以及对前馈、馈误差进行了深入分析。结果表明，用该方法建立的演化模型要后使比传统的线性回归、指数回归、抛物线回归三种固定传统数学模型所预测的数据准确度高很多，而且拟合曲线的前馈标准差和预测后馈标准差也明显要小。

关键词遗传算法数据挖掘演化建模

误差分析

文章编号 10— 3 1 (0 5 0— 2 9 0 文献标识码 A中图分类号 T 3 1 0 2 8 3 - 20 )9 0 1 - 5 P l

Th