📄 3_2 遗传算法.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0044)http://www.jgchina.com/ednns/ednnsbk/6.2.htm -->
<HTML><HEAD><TITLE>3.2 遗传算法</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2900.3243" name=GENERATOR>
<META content=FrontPage.Editor.Document name=ProgId><LINK
href="3_2 遗传算法-Dateien/style.css" type=text/css rel=stylesheet></HEAD>
<BODY bgColor=#ffffff leftMargin=0 topMargin=0>
<TABLE height=1418 cellSpacing=0 cellPadding=0 width=778 border=0>
<TBODY>
<TR>
<TD width="100%" height=17>
<P><A
href="http://www.jgchina.com/ednns/ednnsbk/director.htm">回目录</A>
<A
href="http://www.jgchina.com/ednns/ednnsbk/6.htm">上一页</A>
<A href="http://www.jgchina.com/ednns/ednnsbk/6.3.htm">下一页</A></P></TD></TR>
<TR>
<TD width="100%" height=8>
<P align=center>3.2 遗传算法</P></TD></TR>
<TR>
<TD width="100%" height=1471>
<P>生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。
</P>
<P>遗传算法的概念最早是由Bagley
J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。</P>
<P>遗传算法简称GA(Genetic
Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。</P>
<P>3．2．1 遗传算法的基本概念</P>
<P>遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。</P>
<P>Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。</P>
<P>Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。</P>
<P>由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：</P>
<P>一、串(String)</P>
<P>它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。</P>
<P>二、群体(Population)</P>
<P>个体的集合称为群体，串是群体的元素</P>
<P>三、群体大小(Population Size)</P>
<P>在群体中个体的数量称为群体的大小。</P>
<P>四、基因(Gene)</P>
<P>基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。</P>
<P>五 、基因位置(Gene Position)</P>
<P>一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。</P>
<P>六、基因特征值(Gene Feature)</P>
<P>在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。</P>
<P>七、串结构空间S<SUP>S</SUP></P>
<P>在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。</P>
<P>八、参数空间S<SUP>P</SUP></P>
<P>这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。</P>
<P>九、非线性</P>
<P>它对应遗传学中的异位显性(Epistasis)</P>
<P>十、适应度(Fitness)</P>
<P>表示某一个体对于环境的适应程度。</P>
<P>遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。</P>
<P>3．2．2遗传算法的原理</P>
<P>遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。</P>
<P>一、遗传算法的目的</P>
<P>典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：</P>
<P>考虑对于一群长度为L的二进制编码b<SUB>i</SUB>，i＝1，2，…，n；有</P>
<P>b<SUB>i</SUB><SPAN
style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 10.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">∈</SPAN>{0,1}<SUP>L</SUP>
(3-84)</P>
<P>给定目标函数f，有f(b<SUB>i</SUB>)，并且</P>
<P>0<f(b<SUB>i</SUB>)<<SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.0pt; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">∞</SPAN></P>
<P>同时<BR>f(b<SUB>i</SUB>)<SPAN
style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 10.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">≠</SPAN>f(b<SUB>i+1</SUB>)</P>
<P>求满足下式</P>
<P>max{f(b<SUB>i</SUB>)|b<SUB>i</SUB><SPAN
style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 10.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">∈</SPAN>{0,1}<SUP>L</SUP>}
(3-85)</P>
<P>的b<SUB>i</SUB>。</P>
<P>很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串b<SUB>i</SUB>处，即求出最优解。</P>
<P>二、遗传算法的基本原理</P>
<P>长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：</P>
<P>1．选择(Selection)</P>
<P>这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential
reproduction)。</P>
<P>2．交叉(Crossover)</P>
<P>这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。</P>
<P>3．变异(Mutation)</P>
<P>这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。</P>
<P>遗传算法的原理可以简要给出如下：</P>
<P>choose an intial population</P>
<P>determine the fitness of each individual</P>
<P>perform selection</P>
<P>repeat</P>
<P> perform crossover</P>
<P> perform mutation</P>
<P> determine the fitness of each individual</P>
<P> perform selection</P>
<P>until some stopping criterion applies</P>
<P>这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。</P>
<P>三、遗传算法的步骤和意义</P>
<P>1．初始化</P>
<P>选择一个群体，即选择一个串或个体的集合b<SUB>i</SUB>，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。</P>
<P>通常以随机方法产生串或个体的集合b<SUB>i</SUB>,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。</P>
<P>2．选择</P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -