?? 3_2 遺傳算法.htm
字號(hào):
<!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">上一頁(yè)</A>
<A href="http://www.jgchina.com/ednns/ednnsbk/6.3.htm">下一頁(yè)</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>生物的進(jìn)化是一個(gè)奇妙的優(yōu)化過(guò)程，它通過(guò)選擇淘汰，突然變異，基因遺傳等規(guī)律產(chǎn)生適應(yīng)環(huán)境變化的優(yōu)良物種。遺傳算法是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。
</P>
<P>遺傳算法的概念最早是由Bagley
J.D在1967年提出的；而開(kāi)始遺傳算法的理論和方法的系統(tǒng)性研究的是1975年，這一開(kāi)創(chuàng)性工作是由Michigan大學(xué)的J.H.Holland所實(shí)行。當(dāng)時(shí)，其主要目的是說(shuō)明自然和人工系統(tǒng)的自適應(yīng)過(guò)程。</P>
<P>遺傳算法簡(jiǎn)稱GA(Genetic
Algorithm)，在本質(zhì)上是一種不依賴具體問(wèn)題的直接搜索方法。遺傳算法在模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、圖像處理、機(jī)器學(xué)習(xí)、工業(yè)優(yōu)化控制、自適應(yīng)控制、生物科學(xué)、社會(huì)科學(xué)等方面都得到應(yīng)用。在人工智能研究中，現(xiàn)在人們認(rèn)為“遺傳算法、自適應(yīng)系統(tǒng)、細(xì)胞自動(dòng)機(jī)、混沌理論與人工智能一樣，都是對(duì)今后十年的計(jì)算技術(shù)有重大影響的關(guān)鍵技術(shù)”。</P>
<P>3．2．1 遺傳算法的基本概念</P>
<P>遺傳算法的基本思想是基于Darwin進(jìn)化論和Mendel的遺傳學(xué)說(shuō)的。</P>
<P>Darwin進(jìn)化論最重要的是適者生存原理。它認(rèn)為每一物種在發(fā)展中越來(lái)越適應(yīng)環(huán)境。物種每個(gè)個(gè)體的基本特征由后代所繼承，但后代又會(huì)產(chǎn)生一些異于父代的新變化。在環(huán)境變化時(shí)，只有那些熊適應(yīng)環(huán)境的個(gè)體特征方能保留下來(lái)。</P>
<P>Mendel遺傳學(xué)說(shuō)最重要的是基因遺傳原理。它認(rèn)為遺傳以密碼方式存在細(xì)胞中，并以基因形式包含在染色體內(nèi)。每個(gè)基因有特殊的位置并控制某種特殊性質(zhì)；所以，每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境具有某種適應(yīng)性。基因突變和基因雜交可產(chǎn)生更適應(yīng)于環(huán)境的后代。經(jīng)過(guò)存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來(lái)。</P>
<P>由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法；故而在這個(gè)算法中要用到各種進(jìn)化和遺傳學(xué)的概念。這些概念如下：</P>
<P>一、串(String)</P>
<P>它是個(gè)體(Individual)的形式，在算法中為二進(jìn)制串，并且對(duì)應(yīng)于遺傳學(xué)中的染色體(Chromosome)。</P>
<P>二、群體(Population)</P>
<P>個(gè)體的集合稱為群體，串是群體的元素</P>
<P>三、群體大小(Population Size)</P>
<P>在群體中個(gè)體的數(shù)量稱為群體的大小。</P>
<P>四、基因(Gene)</P>
<P>基因是串中的元素，基因用于表示個(gè)體的特征。例如有一個(gè)串S＝1011，則其中的1，0，1，1這4個(gè)元素分別稱為基因。它們的值稱為等位基因(Alletes)。</P>
<P>五 、基因位置(Gene Position)</P>
<P>一個(gè)基因在串中的位置稱為基因位置，有時(shí)也簡(jiǎn)稱基因位。基因位置由串的左向右計(jì)算，例如在串S＝1101中，0的基因位置是3。基因位置對(duì)應(yīng)于遺傳學(xué)中的地點(diǎn)(Locus)。</P>
<P>六、基因特征值(Gene Feature)</P>
<P>在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。</P>
<P>七、串結(jié)構(gòu)空間S<SUP>S</SUP></P>
<P>在串中，基因任意組合所構(gòu)成的串的集合。基因操作是在結(jié)構(gòu)空間中進(jìn)行的。串結(jié)構(gòu)空間對(duì)應(yīng)于遺傳學(xué)中的基因型(Genotype)的集合。</P>
<P>八、參數(shù)空間S<SUP>P</SUP></P>
<P>這是串空間在物理系統(tǒng)中的映射，它對(duì)應(yīng)于遺傳學(xué)中的表現(xiàn)型(Phenotype)的集合。</P>
<P>九、非線性</P>
<P>它對(duì)應(yīng)遺傳學(xué)中的異位顯性(Epistasis)</P>
<P>十、適應(yīng)度(Fitness)</P>
<P>表示某一個(gè)體對(duì)于環(huán)境的適應(yīng)程度。</P>
<P>遺傳算法還有一些其它的概念，這些概念在介紹遺傳算法的原理和執(zhí)行過(guò)程時(shí)，再進(jìn)行說(shuō)明。</P>
<P>3．2．2遺傳算法的原理</P>
<P>遺傳算法GA把問(wèn)題的解表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解。然后，把這些假設(shè)解置于問(wèn)題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過(guò)交叉，變異過(guò)程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，它就是問(wèn)題的最優(yōu)解。</P>
<P>一、遺傳算法的目的</P>
<P>典型的遺傳算法CGA(Canonical Genetic Algorithm)通常用于解決下面這一類的靜態(tài)最優(yōu)化問(wèn)題：</P>
<P>考慮對(duì)于一群長(zhǎng)度為L(zhǎng)的二進(jìn)制編碼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>給定目標(biāo)函數(shù)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>同時(shí)<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>很明顯，遺傳算法是一種最優(yōu)化方法，它通過(guò)進(jìn)化和遺傳機(jī)理，從給出的原始解群中，不斷進(jìn)化產(chǎn)生新的解，最后收斂到一個(gè)特定的串b<SUB>i</SUB>處，即求出最優(yōu)解。</P>
<P>二、遺傳算法的基本原理</P>
<P>長(zhǎng)度為L(zhǎng)的n個(gè)二進(jìn)制串bi(i＝1，2，…，n)組成了遺傳算法的初解群，也稱為初始群體。在每個(gè)串中，每個(gè)二進(jìn)制位就是個(gè)體染色體的基因。根據(jù)進(jìn)化術(shù)語(yǔ)，對(duì)群體執(zhí)行的操作有三種：</P>
<P>1．選擇(Selection)</P>
<P>這是從群體中選擇出較適應(yīng)環(huán)境的個(gè)體。這些選中的個(gè)體用于繁殖下一代。故有時(shí)也稱這一操作為再生(Reproduction)。由于在選擇用于繁殖下一代的個(gè)體時(shí)，是根據(jù)個(gè)體對(duì)環(huán)境的適應(yīng)度而決定其繁殖量的，故而有時(shí)也稱為非均勻再生(differential
reproduction)。</P>
<P>2．交叉(Crossover)</P>
<P>這是在選中用于繁殖下一代的個(gè)體中，對(duì)兩個(gè)不同的個(gè)體的相同位置的基因進(jìn)行交換，從而產(chǎn)生新的個(gè)體。</P>
<P>3．變異(Mutation)</P>
<P>這是在選中的個(gè)體中，對(duì)個(gè)體中的某些基因執(zhí)行異向轉(zhuǎn)化。在串bi中，如果某位基因?yàn)?，產(chǎn)生變異時(shí)就是把它變成0；反亦反之。</P>
<P>遺傳算法的原理可以簡(jiǎn)要給出如下：</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>這里所指的某種結(jié)束準(zhǔn)則一般是指?jìng)€(gè)體的適應(yīng)度達(dá)到給定的閥值；或者個(gè)體的適應(yīng)度的變化率為零。</P>
<P>三、遺傳算法的步驟和意義</P>
<P>1．初始化</P>
<P>選擇一個(gè)群體，即選擇一個(gè)串或個(gè)體的集合b<SUB>i</SUB>，i=1，2，...n。這個(gè)初始的群體也就是問(wèn)題假設(shè)解的集合。一般取n＝30-160。</P>
<P>通常以隨機(jī)方法產(chǎn)生串或個(gè)體的集合b<SUB>i</SUB>,i＝1，2，...n。問(wèn)題的最優(yōu)解將通過(guò)這些初始假設(shè)解進(jìn)化而求出。</P>
<P>2．選擇</P>
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -