当前位置：文档之家 › 第三章 经典进化计算——遗传算法_2

第三章 经典进化计算——遗传算法_2

  • 格式：ppt
  • 大小：1.33 MB
  • 文档页数：44

下载文档原格式

  / 44

合集下载

遗传算法遗传算法

遗传算法遗传算法
11
（5）遗传算法在解空间进行高效启发式搜索，而非盲 目地穷举或完全随机搜索；
（6）遗传算法对于待寻优的函数基本无限制，它既不 要求函数连续，也不要求函数可微，既可以是数学解 析式所表示的显函数，又可以是映射矩阵甚至是神经 网络的隐函数，因而应用范围较广；
（7）遗传算法具有并行计算的特点，因而可通过大规 模并行计算来提高计算速度，适合大规模复杂问题的 优化。
26
（4）基本遗传算法的运行参数 有下述4个运行参数需要提前设定：
M：群体大小，即群体中所含个体的数量，一般取为 20~100； G：遗传算法的终止进化代数，一般取为100~500； Pc：交叉概率，一般取为0.4~0.99；
Pm：变异概率，一般取为0.0001~0.1。
27
10.4.2 遗传算法的应用步骤
遗传算法简称GA（Genetic Algorithms）是1962年 由美国Michigan大学的Holland教授提出的模拟自然 界遗传机制和生物进化论而成的一种并行随机搜索最 优化方法。
遗传算法是以达尔文的自然选择学说为基础发展起 来的。自然选择学说包括以下三个方面：
1
（1）遗传：这是生物的普遍特征，亲代把生物信息交 给子代，子代总是和亲代具有相同或相似的性状。生 物有了这个特征，物种才能稳定存在。
18
（3）生产调度问题 在很多情况下，采用建立数学模型的方法难以对生
产调度问题进行精确求解。在现实生产中多采用一些 经验进行调度。遗传算法是解决复杂调度问题的有效 工具，在单件生产车间调度、流水线生产车间调度、 生产规划、任务分配等方面遗传算法都得到了有效的 应用。
19
（4）自动控制。 在自动控制领域中有很多与优化相关的问题需要求
10

遗传算法

遗传算法

1.3 遗传算法与传统方法的比较
传统算法 起始于单个点 遗传算法 起始于群体
改善 （问题特有的）
否
改善 （独立于问题的） 否
终止？
终止？ 是 结束
是
结束
1.3.1遗传算法与启发式算法的比较
启发式算法是通过寻求一种能产生可行解的启发式规则，找到问 题的一个最优解或近似最优解。该方法求解问题的效率较高，但是具有 唯一性，不具有通用性，对每个所求问题必须找出其规则。但遗传算法 采用的是不是确定性规则，而是强调利用概率转换规则来引导搜索过程。
1.2 遗传算法的特点
遗传算法是一种借鉴生物界自然选择和自然遗传机制 的随机搜索法。它与传统的算法不同，大多数古典的优化算 法是基于一个单一的度量函数的梯度或较高次统计，以产生 一个确定性的试验解序列；遗传算法不依赖于梯度信息，而 是通过模拟自然进化过程来搜索最优解，它利用某种编码技 术，作用于称为染色体的数字串，模拟由这些串组成的群体 的进化过程。
1.2.2 遗传算法的缺点
（1）编码不规范及编码存在表示的不准确性。 （2）单一的遗传算法编码不能全面地将优化问题的约束表示 出来。考虑约束的一个方法就是对不可行解采用阈值，这样， 计算的时间必然增加。 （3）遗传算法通常的效率比其他传统的优化方法低。 （4）遗传算法容易出现过早收敛。 （5）遗传算法对算法的精度、可信度、计算复杂性等方面， 还没有有效的定量分析方法。
上述遗传算法的计算过程可用下图表示。
遗传算法流程图
目前，遗传算法的终止条件的主要判据有 以下几种：
• 1） 判别遗传算法进化代数是否达到预定的最大代数； • 2） 判别遗传搜索是否已找到某个较优的染色体； • 3） 判别各染色体的适应度函数值是否已趋于稳定、再上升 否等。

遗传算法

遗传算法

1 遗传算法1.1 遗传算法的定义遗传算法(GeneticAlgorithm，GA)是近多年来发展起来的一种全新的全局优化算法，它是基于了生物遗传学的观点，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

它通过自然选择、遗传、复制、变异等作用机制，实现各个个体的适应性的提高，从而达到全局优化。

遗传算法151解决一个实际问题通常都是从一个种群开始，而这个种群通常都是含有问题的一个集合。

这个种群是由一定数目的个体所构成的，利用生物遗传的知识我们可以知道这些个体正好组成了我们知道的染色体，也就是说染色体是由一个个有特征的个体组成的。

另外我们还知道，遗传算法是由染色体组成，而染色体是由基因组成，可以这么说，基因就决定了个体的特性，所以对于遗传算法的最开始的工作就需要进行编码工作。

然后形成初始的种群，最后进行选择、交叉和变异的操作。

1.2遗传算法的重要应用在现实应用中，遗传算法在很多领域得到很好的应用，特别是在解决多维并且相当困难的优化问题中时表现出了很大的优势。

在遗传算法的优化问题的应用中，其中最为经典的应用就是我们所熟悉的函数优化问题，它也是对遗传算法的性能进行评价的最普遍的一种算法;另外的一个最重要的应用，也就是我们本文所研究的应用—组合优化问题，一般的算法很难解决组合优化问题的搜索空间不断扩大的局面，而组合优化问题正好是解决这种问题的最有效的方法之一，在本文的研究中，比如求解TSP问题、VRP问题等方面都得到了很好的应用;另外遗传算法在航空控制系统中的应用、在图像处理和模式识别的应用、在生产调度方面的应用以及在工人智能、人工生命和机器学习方面都得到了很好的应用。

其实在当今的社会中，有关于优化方面的问题应用于各行各业中，因此有关于优化问题已经变得非常重要，它对于整个社会的发展来说都是一个不可改变的发展方向，也是社会发展的一个非常重要的需要。

1.3 遗传算法的特点遗传算法不同于传统的搜索与优化方法，它是随着问题种类的不同以及问题规模的扩大，能以有限的代价来很好的解决搜索和优化的方法。

遗传算法-2-2

遗传算法-2-2

确定式选择
按照确定的方式进行选择。其具体操作过程是： （1）计算群体中每个个体在下一代群体中的期望生存数目 N i： N
N i N Fi
F ,
j j 1
i 1, 2, , N
（2）用 N i 的整数部分[ N i ]确定各个对应个体在下一代群 体中的生存数目； （3）按照 N i 的小数部分对个体进行降序排序，顺序取前
2.4.1
单点交叉
单点交叉（One-point Crossover）又称为简 单交叉，它是指在个体码串中只随机设置一个交 叉点，然后两个配对染色体分别在该点处断开， 并交换断开后部的染色体。具体过程是：
（1）群体中的个体进行随机成双配对； （2）对每一对配对的个体随机的设置某一个 基因座的位置为交叉点 （3）对每一对配对的个体依设定的交叉概率 pc 在其交叉点处相互交换两个个体的部分染色体， 从而产生出两个新的个体。依概率 pc 的含义是 当机器产生的随机数 p pc 时交换，p p c 时不 交换。
N [ N j ]个个体加入到下一代群体中，至此可完全确定出下
j 1 N
一代群体中的 N 个个体。 这种方法可保证适应度较大的一些个体一定能够被保留 在下一代群体中。
2.4 交叉算子
遗传算法中的交叉运算是指对两个染色体按 某种方式相互交换其部分基因，从而产生两个新 的基因，即产生两个新的个体。交叉运算是产生 新个体的主要方法。
如
交叉点1 交叉点2
A : x xxx xx 双点交叉 B : y yyy yy
A : x yyy xx B : y xxx y y
将单点交叉和双点交叉的概念加以推广，可以得到 多点交叉的概念。 A : x xx xxx x 三 点交叉 A : x yy xxx y B : y yy yyy y B : y xx yyy x

遗传算法

遗传算法

1.1引言
生命科学--与工程科学的相互交叉、相互渗透和相互促进是近代科学技术发展的一个显著特点，而遗传算法的蓬勃发展正体现了科学发展的这一特征和趋势。
遗传算法(Genetic Algorithm-GA)，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1 975年首先提出的[1]。J.Holland教授和他的研究小组围绕遗传算法进行研究的宗旨有两个，一是抽取和解释自然系统的自适应过程，二是设计具有自然系统机理的人工系统。毫无疑问，Holland教授的研究，无论对白然系统还是对人工系统都是十分有意义的。
生物的各项生命活动都有它的物质基础，生物的遗传与变异也是这样。根据现代细胞学和遗传学的研究得知，遗传物质的主要载体是染色体(chromsome)，染色体主要是由DNA(脱氧核糖核酸)和蛋白质组成，其中DNA又是最主要的遗传物质。现代分子水平的遗传学的研究又进一步证明，基因(gene)是有遗传效应的片段，它储存着遗传信息，可以准确地复制，也能够发生突变，并可通过控制蛋白质的合成而控制生物的性状。生物体自身通过对基因的复制(reproduction)和交叉(crossover)，即基因分离、基因自由组合和基因连锁互换的操作使其性状的遗传得到选择和控制。同时，通过基因重组、基因变异和染色体在结构和数目上的变异产生丰富多采的变异现象。需要指出的是，根据达尔文进化论，多种多样的生物之所以能够适应环境而得以生存进化，是和上述的遗传和变异生命现象分不开的。生物的遗传特性，使生物界的物种能够保持相对的稳定;生物的变异特性，使生物个体产生新的性状，以至于形成了新的物种，推动了生物的进化和发展。
1100|0 -> 11001
表1.2

遗传算法(GeneticAlgorithm)..

遗传算法(GeneticAlgorithm)..
问题的一个解 解的编码 编码的元素
被选定的一组解 根据适应函数选择的一组解 以一定的方式由双亲产生后代的过程 编码的某些分量发生变化的过程
遗传算法的基本操作
➢选择(selection):
根据各个个体的适应值，按照一定的规则或方法，从 第t代群体P(t)中选择出一些优良的个体遗传到下一代 群体P(t+1)中。
等到达一定程度时，值0会从整个群体中那个位上消失，然而全局最 优解可能在染色体中那个位上为0。如果搜索范围缩小到实际包含全局 最优解的那部分搜索空间，在那个位上的值0就可能正好是到达全局最 优解所需要的。
2023/10/31
适应函数(Fitness Function)
➢ GA在搜索中不依靠外部信息，仅以适应函数为依据，利 用群体中每个染色体(个体)的适应值来进行搜索。以染 色体适应值的大小来确定该染色体被遗传到下一代群体 中的概率。染色体适应值越大，该染色体被遗传到下一 代的概率也越大；反之，染色体的适应值越小，该染色 体被遗传到下一代的概率也越小。因此适应函数的选取 至关重要，直接影响到GA的收敛速度以及能否找到最优 解。
2023/10/31
如何设计遗传算法
➢如何进行编码？ ➢如何产生初始种群？ ➢如何定义适应函数？ ➢如何进行遗传操作(复制、交叉、变异)？ ➢如何产生下一代种群？ ➢如何定义停止准则？
2023/10/31
编码(Coding)
表现型空间
基因型空间 = {0,1}L
编码(Coding)
10010001
父代
111111111111
000000000000
交叉点位置
子代
2023/10/31
111100000000 000011111111

03第三章 遗传算法

03第三章 遗传算法

第三章遗传算法习题与答案1.填空题（1）遗传算法的缩写是，它模拟了自然界中过程而提出，可以解决问题。

在遗传算法中，主要的步骤是、、。

（2）遗传算法的三个算子是、、。

解释：本题考查遗传算法的基础知识。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：（1）GA，生物进化，全局优化，编码，计算适应度函数，遗传算子（2）选择，交叉，变异2.对于编码长度为7的二进制编码，判断以下编码的合法性。

（1）[1020110]（2）[1011001]（3）[0110010]（4）[0000000]（5）[2134576]解释：本题考查遗传算法的二进制编码的合法性。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：（1）[1020110]不合法，不能出现“2”（2）[1011001]合法（3）[0110010]合法（4）[0000000]合法（5）[2134576]不合法，不能出现0、1以外的数字3.下图能够基本反映生物学遗传与优胜劣汰的过程。

理解该图，联想计算类问题求解，回答下列问题。

（1）下列说法正确的是_____。

（多选）A）任何一个生物个体的性状是由其染色体确定的，染色体是由基因及其有规律的排列所构成的，因此生物个体可由染色体来代表。

B）生物的繁殖过程是通过将父代染色体的基因复制到子代染色体中完成的，在复制过程中会发生基因重组或基因突变。

基因重组是指同源的两个染色体之间基因的交叉组合，简称为“杂交/交配”。

基因突变是指复制过程中基因信息的变异，简称“突变”。

C）不同染色体会产生不同生物个体的性状，其适应环境的能力也不同。

D）自然界体现的是“优胜劣汰，适者生存”的丛林法则。

不适应环境的生物个体将被淘汰，自然界生物的生存能力会越来越强。

解释：本题考核对生物遗传观点以及所给图片的理解。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：A、B、C、D关于生物遗传进化的基本观点如下：（1）生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状。

遗传算法--种群进化（经典算法连载二）

遗传算法--种群进化（经典算法连载二）

遗传算法--种群进化（经典算法连载⼆）遗传算法核⼼---杂交，物竞天择
物竞天择－－适应性评分与及选择函数。

1.物竞――适应度函数（fitness function）
你产⽣的个体，对你预设的环境有多⼤的适应度
2.天择――选择函数（selection）
3.变异，进化的源泉。

//1.评估每条染⾊体所对应个体的适应度。

//2.遵照适应度越⾼，选择概率越⼤的原则，从种群中选择两个个体作为⽗⽅和母⽅。

//3.抽取⽗母双⽅的染⾊体，进⾏交叉，产⽣⼦代。

//4.对⼦代的染⾊体进⾏变异。

//5.重复2，3，4步骤，直到新种群的产⽣。

//结束循环。

void calAdaptive(个体unit);//计算个体适应度
void outUnit(种群units) ;
void getSon();//获取⼦孙后代
void variation();//变异
int test()
{
//种群初始化
init(uints);
do{
foreach uint in uints
calAdaptive(uint);
select good mother and father to create a son
getSon(mother,father);//获取⼦孙后代
variation();//变异
}(looptime==>)//终⽌条件可以使迭代次数也可以是种群对环境适应度⽔平等
}。

遗传算法2

遗传算法2

I. Basic Concepts of Multiple Objective Optimization
- Multiple Objective Optimization Problem with q objective functions and m nonlinear constraints can be represented: mo-OP:
I. Basic Concepts of Multiple Objective Optimization
2. Pareto (or Nondominated) Optimal Solutions
- In the single objective case, one attempts to obtain the best solution, which is absolutely superior to all other alternatives. - In the multiple objective case, there does not necessarily exist a solution that is best with respect to all objectives because of incommensurability and conflict among objectives. -There usually exist a set of solutions; nondominated or Pareto optimal solutions, for the multiple objective case which cannot simply be compared with each other. - For a given nondominated point in the criterion space Z, its image point in the decision space S is called efficient or noninferior. A point in S is efficient if and only if its image in Z is nondominated.

Geatpy进化算法遗传算法

Geatpy进化算法遗传算法
第二次是常被称为“重插入”或“环境选择”的选择，它是指在个体经过交叉、变 异等进化操作所形成的子代（或称“育种个体”）后用某种方法来保留到下一代从而形 成新一代种群的过程。这个选择过程对应的是生物学中的” 自然选择”。它可以是显性地 根据适应度（再次注意：适应度并不等价于目标函数值）来进行选择的，也可以是隐性 地根据适应度（即不刻意去计算个体适应度）来选择。例如在多目标优化的 NSGA-II 算 法 [1] 中，父代与子代合并后，处于帕累托分层中第一层级的个体以及处于临界层中的 且拥挤距离最大的若干个个体被保留到下一代。这个过程就没有显性地去计算每个个体 的适应度。
算如下：
i−1 F itnessi = 2 − SP + 2 (SP − 1) N ind − 1
线性排序中选择压力SP 的值必须在 [1.0,2.0] 之间。
文献 [1] 中有这种线性排序的详细分析。其选择强度、多样性损失、选择方差 (这些
概念详见下一节) 的计算如下：
选择强度：
SelInt (SP ) = SP√− 1 π
进化算法
序言 进化算法 (Evolutionary Algorithm, EA) 是一类通过模拟自然界生物自然选择和自然
进化的随机搜索算法。与传统搜索算法如二分法、斐波那契法、牛顿法、抛物线法等相 比，进化算法有着高鲁棒性和求解高度复杂的非线性问题 (如 NP 完全问题) 的能力。
在过去的 40 年中，进化算法得到了不同的发展，现主要有三类： 1) 主要由美国 J. H. Holland 提出的的遗传算法 (Genetic Algorithm, GA)； 2) 主要由德国 I. Rechenberg 提出的进化策略 (Evolution strategies, ES)； 3) 主要由美国的 L. J. Fogel 提出的进化规划 (Evolutionary Programming, EP)。 三种进化算法都是受相同的自然进化原则的启发下创立的，文献 [1] 以及国内的诸 多资料也有详细的介绍。除此之外，进化算法还有差分进化 (Differential Evolution)、基 因表达式编程 (Gene Expression Programming) 等众多分支。本文档只介绍经典的遗传算 法、差分进化算法和多目标进化优化算法，不对众多改进的进化算法以及其他分支作详 细介绍，如有需要进行相关研究的可以参考相关的专业和权威的文献。 文档第一章是有关遗传算法的概述和基本框架；第二章介绍了编码；第三章是关于 适应度的计算；第四章讲述了选择算法；在第五章中，介绍了不同的重组算法；第六章 解释了如何变异；第七章详细讲解了与多目标优化有关的概念。 最后值得一提的是，虽然进化算法在近 20 年来已经得到了快速的发展，在当今已 经比较成熟，在金融、工程、信息学、数学等领域已经有广泛的应用，但是，众多新兴 的进化算法 (如差分进化算法等) 以及不断改进和完善的拥有高维、多目标问题求解能 力的进化优化算法等等，正给进化算法注入源源不断的新活力。与此同时，深度神经网 络的蓬勃发展让进化算法有了一个更加前沿和广阔的前景——神经进化。量子计算机的 出现，也使得拥有高度并行能力的进化算法有着更大的潜能。

遗传算法

遗传算法

遗传算法直接以目标函数作为搜索信息。 （3）遗传算法直接以目标函数作为搜索信息。传统的优化算法不仅 需要利用目标函数值， 需要利用目标函数值，而且需要目标函数的导数值等辅助信息才 能确定搜索方向。 能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应 度函数值，就可以确定进一步的搜索方向和搜索范围， 度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标 函数的导数值等其他一些辅助信息。 遗传算法可应用于目标函 函数的导数值等其他一些辅助信息。 数无法求导数或导数不存在的函数的优化问题， 数无法求导数或导数不存在的函数的优化问题，以及组合优化问 题等。 题等。 遗传算法使用概率搜索技术。遗传算法的选择、交叉、 （4）遗传算法使用概率搜索技术。遗传算法的选择、交叉、变异等 运算都是以一种概率的方式来进行的， 运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程 具有很好的灵活性。随着进化过程的进行， 具有很好的灵活性。随着进化过程的进行，遗传算法新的群体会 更多地产生出许多新的优良的个体。 更多地产生出许多新的优良的个体。
• 1.2 遗传算法的概述
• 遗传算法的基本思想： 遗传算法的基本思想： 在问题的求解过程中，把搜索空间视为遗传空间，把问题的 在问题的求解过程中，把搜索空间视为遗传空间， 每一个可能解看做一个染色体，染色体里面有基因，所有染色体 每一个可能解看做一个染色体，染色体里面有基因， 组成一个群体。首先随机选择部分染色体组成初始种群，依据某 组成一个群体。首先随机选择部分染色体组成初始种群， 种评价标准，也就是寻优准则（这里叫适应度函数），对种群每 种评价标准，也就是寻优准则（这里叫适应度函数），对种群每 ）， 一个染色体进行评价，计算其适应度，淘汰适应度值小的，保留 一个染色体进行评价，计算其适应度，淘汰适应度值小的， 适应度值大的，并借助于自然遗传学的遗传算子进行选择、交叉 适应度值大的，并借助于自然遗传学的遗传算子进行选择、 和变异，产生出代表新的解集的种群。 和变异，产生出代表新的解集的种群。

《遗传算法》课件

《遗传算法》课件
总结词
达到预设迭代次数
详细描述
当遗传算法达到预设的最大迭代次数时，算法终止。此时 需要根据适应度值或其他指标判断是否找到了满意解或近 似最优解。
总结词
达到预设精度
详细描述
当遗传算法的解的精度达到预设值时，算法终止。此时可 以认为找到了近似最优解。
总结词
满足收敛条件
详细描述
当遗传算法的解满足收敛条件时，算法终止。常见的收敛 条件包括个体的适应度值不再发生变化、最优解连续多代 保持不变等。
多目标优化
传统的遗传算法主要用于单目标优化问题。然而 ，实际应用中经常需要解决多目标优化问题。因 此，发展能够处理多目标优化问题的遗传算法也 是未来的一个重要研究方向。
适应性遗传算法
适应性遗传算法是指根据问题的特性自适应地调 整遗传算法的参数和操作，以提高搜索效率和精 度。例如，可以根据问题的复杂度和解的质量动 态调整交叉概率、变异概率等参数。
自适应调整是指根据个体的适应度值动态调整 适应度函数，以更好地引导遗传算法向更优解 的方向进化。
选择操作
总结词
基于适应度选择
详细描述
选择操作是根据个体的适应 度值进行选择，通常采用轮 盘赌、锦标赛等选择策略， 以保留适应度较高的个体。
总结词
多样性保护
详细描述
为了保持种群的多样性，选择操作可以采 用一些多样性保护策略，如精英保留策略 、小生境技术等。
梯度下降法是一种基于函数梯度的优化算法，与遗传算法结合使用可以加快搜索速度， 提高解的质量。
遗传算法的基本思想
初始化
随机生成一组解作为初始种群。
适应度评估
根据问题的目标函数计算每个解 的适应度值。
选择操作
根据适应度值的大小，选择适应 度较高的解进行遗传操作。

生物进化算法

生物进化算法
生物进化算法
信实101 薛子朦 丁明 洪莹
引言
• 遗传算法作为一门新兴学科，在信息 学竞赛中还未普及，但由于遗传算法对许 多用传统数学难以解决或明显失效的复杂 问题，特别是优化问题，提供了一个行之 有效的新途径，且能够较好地解决信息学 竞赛中的NP难题，因此值得我们进行深入 的讨论。
关键词
• • • • • • • • • • 遗传算法（Genetic Algorithm） GA通常为简单遗传算法（SGA） 遗传（Genetic） 基因(Gene) 染色体(Chromosome) 选择（option） 交叉（cross） 变异（metamorphossis） 种群（population） 个体（individual）
• • • • • •
变异
• 变异运算用来模拟生物在自然界的遗传环境中由于各 种偶然因素引起的基因突变，它以很小概率随机地改变遗 传基因（表示染色体的符号串的某一位）的值。在染色体 以二进制编码的系统中，它随机地将染色体的某一个基因 由1变成0，或由0变成1。若只有选择和交换，而没有变异 操作，则无法在初始基因组合以外的空间进行搜索，使进 化过程在早期就陷入局部解而终止进化过程，从而使解的 质量受到很大限制。通过变异操作，可确保群体中遗传基 因类型的多样性，以使搜索能在尽可能大的空间中进行， 避免丢失在搜索中有用的遗传信息而陷入局部解，获得质 量较高的优化解答。
• 上述各种算子的实现是多种多样的，而且许多新 的算子正在不断地提出，以改进GA的某些性能。 系统参数(个体数n,基因链长度l,交叉概率Pc,变异 概率Pm等)对算法的收敛速度及结果有很大的影响， 应视具体问题选取不同的值。 • GA的程序设计应考虑到通用性，而且要有较强的 适应新的算子的能力。OOP中的类的继承为我们 提供了这一可能。

第三章 经典进化计算——遗传算法_3

第三章 经典进化计算——遗传算法_3
• 在研究自然界生物的遗传和进化现象时，生物学家使用适应度这个术 语来度量某个物种对于其生存环境的适应程度。 • 与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个 体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。 度量个体适应度的函数称为适应度函数。 2.1 目标函数与适应度函数 遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一 步的有关搜索信息。 最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为 求目标函数的全局最小值。对于这两类优化问题，第二章中已经介绍过由解 空间中某一点的目标函数值 f(x) 到搜索空间中对应个体的适应度函数值F(x) 的转换方法： • 对于求最大值的问题，作下述转换：
F(X) =
f(X)+Cmin if f(X)+Cmin> 0 0 if f(X)+Cmin ≤ 0
• 对于求最小值问题，变换如下：
F(X) =
Cmax - f(X) if f(X) Cmax 0 if f(X) Cmax
2.2 适应度尺度变换 (1) 适应度尺度变换的原因 在遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体的 适应度来确定的，应用实践表明，仅使用以上两式来计算个体适应度时， 有些遗传算法会收敛得很快，也有些遗传算法会收敛得很慢。 • 在遗传算法运行的初期阶段 群体中可能会有少数几个个体的适应度相对其他个体来说非常高。若 按照常用的比例选择算子来确定个体的遗传数量时，则这几个相对较好的 个体将在下一代群体中占有很高的比例，在极端情况下或当群体现模较小 时，新的群体甚 至完全由这样的少数几个个体所组成。这时产生新个体作 用较大的交叉算子就起不了什么作用，因为相同的两个个体不论在何处进 行交叉操作都永远不会产生出新的个体，如下所示：

遗传算法

遗传算法

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

遗传算法模仿了生物的遗传、进化原理, 并引用了随机统计理论。

在求解过程中, 遗传算法从一个初始变量群体开始, 一代一代地寻找问题的最优解, 直至满足收敛判据或预先设定的迭代次数为止。

它是一种迭代式算法。

2、遗传算法的基本原理遗传算法是一种基于自然选择和群体遗传机理的搜索算法, 它模拟了自然选择和自然遗传过程中发生的繁殖、杂交和突变现象。

在利用遗传算法求解问题时, 问题的每个可能的解都被编码成一个“染色体”,即个体, 若干个个体构成了群体( 所有可能解) 。

在遗传算法开始时, 总是随机地产生一些个体( 即初始解) , 根据预定的目标函数对每个个体进行评价, 给出了一个适应度值。

基于此适应度值, 选择个体用来繁殖下一代。

选择操作体现了“适者生存”原理, “好”的个体被选择用来繁殖, 而“坏”的个体则被淘汰。

然后选择出来的个体经过交叉和变异算子进行再组合生成新的一代。

这一群新个体由于继承了上一代的一些优良性状,因而在性能上要优于上一代, 这样逐步朝着更优解的方向进化。

因此, 遗传算法可以看作是一个由可行解组成的群体逐代进化的过程。

3、遗传算法的一般算法（1）创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。

（2）评估适应度对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

解 (1) 设定种群规模 , 编码染色体，产生初始 种群。 将种群规模设定为 4 ；用 5 位二进制数编码 染色体；取下列个体组成初始种群S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011)
(2) 定义适应度函数,
取适应度函数：f (x)=x2
s3=11000
81
576
0.04
0.32
0.48
0.80
0
1
s4=10011
361
0.20
1.00
1
设这一轮的选择-复制结果为：
s1’=11100（28）, s2’=11100（28）
s3’=11000（24）, s4’=10011（19） 做交叉运算，让s1’与s4’，s2’与s3’ 分别交换 后两位基因，得 s1’’=11111（31）, s2’’=11100（28） s3’’=11000（24）, s4’’=10000（16） 这一轮仍然不会发生变异。
3.3—遗传算法的模式理论
指导遗传算法的基本理论，是J.H.Holland教授创 立的模式理论。该理论揭示遗传算法的基本机理。
一、基本概念 二、模式定理 三、建筑块假说 四、隐含并行性
一、基本概念
1.1 问题的引出
例： 求 max f(x)=x2 x {0,31}
[分析] • 当编码的最左边字符为“1”时，其个体适应度较大，如2号个体和4号个体， 我们将其记为 “ 1**** ”； 其中2号个体适应度最大，其编码的左边两位都是1，我们记为 “ 11*** ”； • 当编码的最左边字符为“0”时，其个体适应度较小，如1号和3号个体， 我们记为 “ 0**** ”。
——遗传算法总是在寻找优解, 而不像图搜 索那样并非总是要求优解, 而一般是设法尽快 找到解, 所以遗传算法又是一种优化搜索算法。
——遗传算法的搜索过程是从空间的一个点 集(种群)到另一个点集(种群)的搜索,而不像图 搜索那样一般是从空间的一个点到另一个点地 搜索。 因而它实际是一种并行搜索, 适合大规 模并行计算,而且这种种群到种群的搜索有能力 跳出局部最优解。
j 1
选择-复制
设从区间［0, 1］中产生4个随机数如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503
染色体 适应度 选择概率 积累概率 选中次数
s1=01101
s2=11000 s3=01000
169
576 64
0.14
0.49 0.06
——遗传算法的适应性强 , 除需知适应度 函数外, 几乎不需要其他的先验知识。 ——遗传算法长于全局搜索 , 它不受搜索 空间的限制性假设的约束,不要求连续性, 能以 很大的概率从离散的、多极值的、 含有噪声的 高维问题中找到全局最优解。
◆遗传算法的应用
函数优化
是遗传算法的经典应用领域; 组合优化 实践证明，遗传算法对于组合优化中的NP完全问题 非常有效; 自动控制 如基于遗传算法的模糊控制器优化设计、基于遗传算 法的参数辨识、利用遗传算法进行人工神经网络的结构 优化设计和权值学习等; 机器人智能控制 遗传算法已经在移动机器人路径规划、关节机器人运 动轨迹规划、机器人逆运动学求解、细胞机器人的结构 优化和行动协调等;
于是，得第四代种群S4：
s1=11111（31）, s2=11100（28）
s3=11000（24）, s4=10000（16）
显然，在这一代种群中已经出现了适应度 最高的染色体s1=11111。于是，遗传操作终止， 将染色体“11111”作为最终结果输出。 然后，将染色体“11111”解码为表现型，即 得所求的最优解：31。 将31代入函数y=x2中，即得原问题的解，即 函数y=x2的最大值为961。
0.14
0.63 0.69
1
2 0
s4=10011
361
0.31
1.00
1
于是，经复制得群体：
s1’ =11000（24）, s2’ =01101（13）
s3’ =11000（24）, s4’ =10011（19）
交叉
设交叉率 pc=100% ，即 S1 中的全体染色体都 参加交叉运算。
设s1’与s2’配对，s3’与s4’配对。分别交换后 两位基因，得新染色体： s1’’=11001（25）, s2’’=01100（12）
第二代种群S2中各染色体的情况 染色体 s1=11001 s2=01100 s3=11011 s4=10000 适应度 625 144 729 256 选择概率 0.36 0.08 0.41 0.15 积累概率 0.36 0.44 0.85 1.00 估计的 选中次数 1 0 2 1
假设这一轮选择-复制操作中，种群S2中的
• 阶次越低，模式的概括性越强，所代表的编码串个体数也越多，反之亦然； • 当模式阶次为零时，它没有明确含义的字符，其概括性最强。
模式的定义长度( Schema Defining Length) ——指模式中第一个和最后一个具有明确含意的字符之间的距离，记作 (s)。 例如，模式( 011*l** ) 的第一个字符为0，最后一个字符为l，中间有3个 字符，其定义长度为4，记作 ( 011*l** ) = 4 ；模式 ( 0****** ) 的长度是0，记 作 ( 0****** ) = 0 ；
4个染色体都被选中，则得到群体：
s1’=11001（25）, s2’= 01100（12）
s3’=11011（27）, s4’= 10000（16）
做交叉运算，让s1’与s2’，s3’与s4’ 分别交换 后三位基因，得 s1’’ =11100（28）, s2’’ = 01001（9）
s3’’ =11000（24）, s4’’ = 10011（19）
这一轮仍然不会发生变异。
于是，得第三代种群S3：
s1=11100（28）, s2=01001（9）
s3=11000（24）, s4=10011（19）
第三代种群S3中各染色体的情况 染色体 s1=11100 适应度 784 选择概率 0.44 积累概率 0.44 估计的 选中次数 2
s2=01001
• 一般地，有式子 (s)＝b – a 式中 b—模式s 中最后一个明确字符的位置; a—模式s 中最前一个明确字符的位置。 • 模式的长度代表该模式在今后遗传操作(交叉、变异)中被破坏的可能性： 模式长度越短，被破坏的可能性越小，长度为0的模式最难被破坏。
1.3 编码字符串的模式数目
(1) 模式总数
• 二进制字符串 假设字符的长度为，字符串中每一个字符可取( 0, 1, * ) 三个符号中任意 一个，可能组成的模式数目最多为： 3 3 3 … 3 = (2+1) • 一般情况下， 假设字符串长度为，字符的取值为 k 种，字符串组成的模式数目 n1 最多 为： n1=(k+1)
s3’’=11011（27）, s4’’=10000（16）
变异
设变异率pm=0.001。
这样，群体S1中共有
5×4×0.001=0.02
位基因可以变异。 0.02位显然不足 1位，所以本轮遗传操作不 做变异。
于是，得到第二代种群S2：
s1=11001（25）, s2=01100（12）
s3=11011（27）, s4=10000（16）
(3) 计算各代种群中的各个体的适应度 , 并
对其染色体进行遗传操作,直到适应度最高的个
体(即31（11111）)出现为止。
首先计算种群S1中各个体 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011) 的适应度f (si) 。 容易求得 f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 361
[结论] 从这个例子可以看比，我们在分析编码字符串时，常常只关心某一位或某几位 字符，而对其他字符不关心。换句话讲．我们只关心字符的某些特定形式，如 1****，11***，0****。这种特定的形式就叫模式。
Hale Waihona Puke 1.2 模式、模式阶及模式定义长度
模式(Schema)——指编码的字符串中具有类似特征的子集。 以五位二进制字符串为例，模式 *111* 可代表4个个体： 01110，01111， 11110，11111；模式 *0000 则代表2个个体：10000，00000 。
Y
Y
y=x2
y =x2
8 Y
13
19 24
X Y
12 16
25 27
X
第一代种群及其适应度
第二代种群及其适应度
y=x 2
y=x2
9
19 24 28
X
16
24 28 31 X
第三代种群及其适应度
第四代种群及其适应度
二、遗传算法的特点与优势
◆遗传算法的主要特点 ——遗传算法一般是直接在解空间搜索 , 而不像图搜索那样一般是在问题空间搜索 , 最 后才找到解。 ——遗传算法的搜索随机地始于搜索空间 的一个点集 , 而不像图搜索那样固定地始于搜 索空间的初始节点或终止节点 , 所以遗传算法 是一种随机搜索算法。
• 个体是由二值字符集 V={0, 1} 中的元素所组成的一个编码串; • 而模式却是由三值字符集 V={0, 1,* } 中的元素所组成的一个编码串，其中 “ * ” 表示通配符，它既可被当作 “1” 也可被当作 “0”。 模式阶 (Schema Order) ——指模式中已有明确含意(二进制字符时指0或1)的字符个数， 记做 o(s)，式中 s 代表模式。 例如，模式 ( 011*1** ) 含有4个明确含意的字符，其阶次是4， 记作 o( 011*1** ) =4; 模式 ( 0****** ) 的阶次是1，记作 o( 0****** ) =1。