遺傳算法的生物學(xué)基礎(chǔ)第一頁(yè)，共二十七頁(yè)，編輯于2023年，星期三

?構(gòu)成生物的基本結(jié)構(gòu)和功能的單位是細(xì)胞(Ce11)。

?

細(xì)胞中含有的一種微小的絲狀化合物稱為染色體(Chromosome)，生物的所有遺傳信息都包含在這個(gè)復(fù)雜而又微小的染色體中。

?

基因經(jīng)過(guò)生物學(xué)家的研究，控制并決定生物遺傳性狀的染色體主要是由一種叫做脫氧核糖核酸(deoxyribonucleicacid簡(jiǎn)稱DNA)的物質(zhì)所構(gòu)成。DNA在染色體中有規(guī)則地排列著，它是個(gè)大分子的有機(jī)聚合物，其基本結(jié)構(gòu)單位是核苷酸，許多核苷酸通過(guò)磷酸二酯鍵相結(jié)合形成一個(gè)長(zhǎng)長(zhǎng)的鏈狀結(jié)構(gòu)，兩個(gè)鏈狀結(jié)構(gòu)再通過(guò)堿基間的氫鍵有規(guī)律地扭合在一起，相互卷曲起來(lái)形成一種雙螺旋結(jié)構(gòu)。基因就是DNA長(zhǎng)鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位。

?

遺傳信息是由基因(Gene)組成的，生物的各種性狀由其相應(yīng)的基因所控制。

?

基因是遺傳的基本單位。細(xì)胞通過(guò)分裂具有自我復(fù)制的能力，在細(xì)胞分裂的過(guò)程中，其遺傳基因也同時(shí)被復(fù)制到下一代，從而其性狀也被下一代所繼承。

第二頁(yè)，共二十七頁(yè)，編輯于2023年，星期三?遺傳基因在染色體中所占據(jù)的位置稱為基因座(Locus)；?同一基因座可能有的全部基因稱為等位基因(Allele)；?某種生物所特有的基因及其構(gòu)成形式稱為該生物的基因型(Genotype)；?而該生物在環(huán)境中呈現(xiàn)出的相應(yīng)的性狀稱為該生物的表現(xiàn)型(Phenotype)；?一個(gè)細(xì)胞核中所有染色體所攜帶的遺傳信息的全體稱為一個(gè)基因組(Genome)。第三頁(yè)，共二十七頁(yè)，編輯于2023年，星期三生物的遺傳方式：

1.復(fù)制生物的主耍遺傳方式是復(fù)制。遺傳過(guò)程中，父代的遺傳物質(zhì)DNA被復(fù)制到子代。即細(xì)胞在分裂時(shí)，遺傳物質(zhì)DNA通過(guò)復(fù)制(Reproduction)而轉(zhuǎn)移到新生的細(xì)胞中，新細(xì)胞就繼承了舊細(xì)胞的基因。

2.交叉有性生殖生物在繁殖下一代時(shí)，兩個(gè)同源染色體之間通過(guò)交叉(Crossover)而重組，亦即在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交義組合而形成兩個(gè)新的染色體。

3.變異在進(jìn)行細(xì)胞復(fù)制時(shí)，雖然概率很小，僅僅有可能產(chǎn)生某些復(fù)制差錯(cuò)，從而使

DNA發(fā)生某種變異(Mutation)，產(chǎn)生出新的染色體。這些新的染色體表現(xiàn)出新的性狀。

如此這般，遺傳基因或染色體在遺傳的過(guò)程中由于各種各樣的原因而發(fā)生變化。第四頁(yè)，共二十七頁(yè)，編輯于2023年，星期三

1.1.2進(jìn)化地球上的生物，都是經(jīng)過(guò)長(zhǎng)期進(jìn)化而形成的。根據(jù)達(dá)爾文的自然選擇學(xué)說(shuō)，地球上的生物具有很強(qiáng)的繁殖能力。在繁殖過(guò)程中，大多數(shù)生物通過(guò)遺傳，使物種保持相似的后代；部分生物由于變異，后代具有明顯差別，甚至形成新物種。正是由于生物的不斷繁殖后代，生物數(shù)目大量增加，而自然界中生物賴以生存的資源卻是有限的。因此，為了生存，生物就需要競(jìng)爭(zhēng)。生物在生存競(jìng)爭(zhēng)中，根據(jù)對(duì)環(huán)境的適應(yīng)能力，適者生存，不適者消亡。自然界中的生物，就是根據(jù)這種優(yōu)勝劣汰的原則，不斷地進(jìn)行進(jìn)化。

?

生物的進(jìn)化是以集團(tuán)的形式共同進(jìn)行的，這樣的一個(gè)團(tuán)體稱為群體(Population)，或稱為種群。

?組成群體的單個(gè)生物稱為個(gè)體(Individual)，

?每一個(gè)個(gè)體對(duì)其生存環(huán)境都有不同的適應(yīng)能力，這種適應(yīng)能力稱為個(gè)體的適應(yīng)度(Fitness)。第五頁(yè)，共二十七頁(yè)，編輯于2023年，星期三1.1.3遺傳與進(jìn)化的系統(tǒng)觀雖然人們還未完全揭開遺傳與進(jìn)化的奧秘，即沒有完全掌握其機(jī)制、也不完全清楚染色體編碼和譯碼過(guò)程的細(xì)節(jié)，更不完全了解其控制方式，但遺傳與進(jìn)化的以下幾個(gè)特點(diǎn)卻為人們所共識(shí)：

(1)生物的所有遺傳信息都包含在其染色體中，染色體決定了生物的性狀；

(2)染色體是由基因及其有規(guī)律的排列所構(gòu)成的，遺傳和進(jìn)化過(guò)程發(fā)生在染色體上；

(3)生物的繁殖過(guò)程是由其基因的復(fù)制過(guò)程來(lái)完成的；

(4)通過(guò)同源染色體之間的交叉或染色體的變異會(huì)產(chǎn)生新的物種，使生物呈現(xiàn)新的性狀。

(5)對(duì)環(huán)境適應(yīng)性好的基因或染色體經(jīng)常比適應(yīng)性差的基因或染色體有更多的機(jī)會(huì)遺傳到下一代。第六頁(yè)，共二十七頁(yè)，編輯于2023年，星期三1.2遺傳算法簡(jiǎn)介

遺傳算法是模擬生物在自然環(huán)境下的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索方法。

它最早由美國(guó)密西根大學(xué)的H.Holland教授提出，起源于60年代對(duì)自然和人工自適應(yīng)系統(tǒng)的研究；

1967年，Bagley發(fā)表了關(guān)于遺傳算法應(yīng)用的論文，在其論文中首次使用“遺傳算法（GeneticAlgorithm）”一詞。

70年代

DeJong基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)。

在一系列研究工作的基礎(chǔ)上，80年代由Goldberg進(jìn)行歸納總結(jié)，形成了遺傳算法的基本框架。

第七頁(yè)，共二十七頁(yè)，編輯于2023年，星期三1.2.1遺傳算法概要對(duì)于一個(gè)求函數(shù)最大值的優(yōu)化問(wèn)題（求最小值也類同），一般可描述為下述數(shù)學(xué)規(guī)劃模型：

maxf(X)(1-1)s.t.XR(1-2)RU(1-3)

其中：

X＝[x1,x2,…,xn]T為決策變量，

f(X)為目標(biāo)函數(shù)，式(1-2)、(1-3)為約束條件，

U是基本空間，

R是U的一個(gè)子集。滿足約束條件的解X稱為可行解；集合R表示由所有滿足約束條件的解所組成的一個(gè)集合，叫做可行解集合。它們之間的關(guān)系如圖所示。第八頁(yè)，共二十七頁(yè)，編輯于2023年，星期三對(duì)于上述最優(yōu)化問(wèn)題，目標(biāo)函數(shù)和約束條件種類繁多，有的是線性的，有的是非線性的；有的是連續(xù)的，有的是離散的；有的是單峰值的，有的是多峰值的。隨著研究的深入，人們逐漸認(rèn)識(shí)到在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解既不可能，也不現(xiàn)實(shí)，因而求出其近似最優(yōu)解或滿意解是人們的主要著眼點(diǎn)之一。

總的來(lái)說(shuō)，求最優(yōu)解或近似最優(yōu)解的方法主要有三種：枚舉法、啟發(fā)式算法和搜索算法。隨著問(wèn)題種類的不同，以及問(wèn)題規(guī)模的擴(kuò)大，要尋求到一種能以有限的代價(jià)來(lái)解決上述最優(yōu)化問(wèn)題的通用方法仍是個(gè)難題。而遺傳算法卻為我們解決這類問(wèn)題提供了一個(gè)有效的途徑和通用框架，開創(chuàng)了一種新的全局優(yōu)化搜索算法。第九頁(yè)，共二十七頁(yè)，編輯于2023年，星期三遺傳算法中：

將n維決策向量X＝[x1,x2,…,xn]T用n個(gè)記號(hào)Xi(i=1,2,…,n))所組成的符號(hào)串X來(lái)去示：

X＝xlx2…xn

X＝[x1，x2，…,xn]T

?把每一個(gè)xi看作一個(gè)遺傳基因，這樣，X就可看做是由n個(gè)遺傳基因所組成的一個(gè)染色體。

?

這里的等位基因可以是一組整數(shù)。也可以是某一范圍內(nèi)的實(shí)數(shù)值，或者是純粹的一個(gè)記號(hào)。最簡(jiǎn)單的等位基因是由0和1這兩個(gè)整數(shù)組成的，相應(yīng)的染色體就可表示為一個(gè)二進(jìn)制符號(hào)串。

?這種編碼所形成的排列形式X是個(gè)體的基因型，與它對(duì)應(yīng)的X值是個(gè)體的表現(xiàn)型。

?對(duì)于每一個(gè)個(gè)體X，要按照一定的規(guī)則確定出其適應(yīng)度，個(gè)體的適應(yīng)度與其對(duì)應(yīng)的個(gè)體表現(xiàn)型X的目標(biāo)函數(shù)值相關(guān)聯(lián)，X越接近于目標(biāo)函數(shù)的最優(yōu)點(diǎn)，其適應(yīng)度越大；反之，其適應(yīng)度越小。遺傳算法中，決策變量X組成了問(wèn)題的解空間。對(duì)問(wèn)題最優(yōu)解的搜索是通過(guò)對(duì)染色體X的搜索過(guò)程來(lái)進(jìn)行的。從而所有的染色體X就組成了問(wèn)題的搜索空間。第十頁(yè)，共二十七頁(yè)，編輯于2023年，星期三生物的進(jìn)化是以集團(tuán)為主體的。與此相對(duì)應(yīng)，遺傳算法的運(yùn)算對(duì)象是由M個(gè)個(gè)體所組成的集合，稱為群體（或稱種群）。與生物一代一代的自然進(jìn)化過(guò)程相類似，遺傳算法的運(yùn)算過(guò)程也是一個(gè)反復(fù)迭代過(guò)程：第t代群體記做P(t)，經(jīng)過(guò)一代遺傳和進(jìn)化后，得到t+1代群體，記做P(t+1),

這個(gè)群體不斷地經(jīng)過(guò)遺傳和進(jìn)化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個(gè)體更多地遺傳到下一代，這樣最終在群體中將會(huì)得到一個(gè)優(yōu)良的個(gè)體

X，它所對(duì)應(yīng)的表現(xiàn)型X將達(dá)到或接近于問(wèn)題的最優(yōu)解X*。第十一頁(yè)，共二十七頁(yè)，編輯于2023年，星期三1.2.2遺傳策法的運(yùn)算過(guò)程選擇(復(fù)制)：根據(jù)各個(gè)個(gè)體的適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體P(t)

中選擇出一些優(yōu)良的個(gè)體遺傳到下一代群體P(t+1)中；交叉：將群體P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對(duì)，對(duì)每一對(duì)個(gè)體，以某個(gè)概率

(稱為交叉概率）交換它們之間的部分染色體；變異：對(duì)群體P(t)中的每一個(gè)個(gè)體，以某一概率(稱為變異概率)改變某一個(gè)或某一些基因座上的基因值為其他基因值。實(shí)際問(wèn)題參數(shù)集編碼群體t計(jì)算適值運(yùn)算：復(fù)制交叉變異群體t+1滿足要求？解碼改善或解決實(shí)際問(wèn)題群體t+1群體tYN第十二頁(yè)，共二十七頁(yè)，編輯于2023年，星期三1.2.3遺傳算法的手工模擬計(jì)算示例為更好地理解遺傳算法的運(yùn)算過(guò)程，下面用手工計(jì)算來(lái)簡(jiǎn)單地模擬遺傳算法的各個(gè)主要執(zhí)行步驟。

例：求下述二元函數(shù)的最大值：

maxf(x1,x2)=x12+x22s.t.x1

{1,2,3,4,5,6,7}x2

{1,2,3,4,5,6,7}

(1)個(gè)體編碼遺傳算法的運(yùn)算對(duì)象是表示個(gè)體的符號(hào)串，所以必須把變量x1,x2編碼為一種符號(hào)串。本題中，用無(wú)符號(hào)二進(jìn)制整數(shù)來(lái)表示。因x1,x2為0~7之間的整數(shù)，所以分別用3位無(wú)符號(hào)二進(jìn)制整數(shù)來(lái)表示，將它們連接在一起所組成的6位無(wú)符號(hào)二進(jìn)制數(shù)就形成了個(gè)體的基因型，表示一個(gè)可行解。

例如，基因型X＝101110所對(duì)應(yīng)的表現(xiàn)型是：x＝[5，6]。個(gè)體的表現(xiàn)型x和基因型X之間可通過(guò)編碼和解碼程序相互轉(zhuǎn)換。第十三頁(yè)，共二十七頁(yè)，編輯于2023年，星期三

(2)初始群體的產(chǎn)生遺傳算法是對(duì)群體進(jìn)行的進(jìn)化操作，需要給其淮備一些表示起始搜索點(diǎn)的初始群體數(shù)據(jù)。本例中，群體規(guī)模的大小取為4，即群體由4個(gè)個(gè)體組成，每個(gè)個(gè)體可通過(guò)隨機(jī)方法產(chǎn)生。如：011101，101011，011100，111001

(3)適應(yīng)度汁算遺傳算法中以個(gè)體適應(yīng)度的大小來(lái)評(píng)定各個(gè)個(gè)體的優(yōu)劣程度，從而決定其遺傳機(jī)會(huì)的大小。本例中，目標(biāo)函數(shù)總?cè)》秦?fù)值，并且是以求函數(shù)最大值為優(yōu)化目標(biāo)，故可直接利用目標(biāo)函數(shù)值作為個(gè)體的適應(yīng)度。

(4)選擇運(yùn)算選擇運(yùn)算(或稱為復(fù)制運(yùn)算)把當(dāng)前群體中適應(yīng)度較高的個(gè)體按某種規(guī)則或模型遺傳到下一代群體中。一般要求適應(yīng)度較高的個(gè)體將有更多的機(jī)會(huì)遺傳到下一代群體中。第十四頁(yè)，共二十七頁(yè)，編輯于2023年，星期三本例中，我們采用與適應(yīng)度成正比的概率來(lái)確定各個(gè)個(gè)體復(fù)制到下一代群體中的數(shù)量。其具體操作過(guò)程是：

?先計(jì)算出群體中所有個(gè)體的適應(yīng)度的總和fi

(i=1.2,…,M);

?其次計(jì)算出每個(gè)個(gè)體的相對(duì)適應(yīng)度的大小fi/fi

，它即為每個(gè)個(gè)體被遺傳到下一代群體中的概率，

?

每個(gè)概率值組成一個(gè)區(qū)域，全部概率值之和為1；

?最后再產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)，依據(jù)該隨機(jī)數(shù)出現(xiàn)在上述哪一個(gè)概率區(qū)域內(nèi)來(lái)確定各個(gè)個(gè)體被選中的次數(shù)。0124%24%17%35%1#2#3#4#個(gè)體編號(hào)初始群體p(0)適值占總數(shù)的百分比總和1234011101101011011100111001343425500.240.240.170.351431選擇次數(shù)選擇結(jié)果1102011101111001101011111001

x1x2

35533471第十五頁(yè)，共二十七頁(yè)，編輯于2023年，星期三(5)交叉運(yùn)算交叉運(yùn)算是遺傳算法中產(chǎn)生新個(gè)體的主要操作過(guò)程，它以某一概率相互交換某兩個(gè)個(gè)體之間的部分染色體。本例采用單點(diǎn)交叉的方法，其具體操作過(guò)程是：

?先對(duì)群體進(jìn)行隨機(jī)配對(duì)；

?其次隨機(jī)設(shè)置交叉點(diǎn)位置；

?最后再相互交換配對(duì)染色體之間的部分基因。選擇結(jié)果011101111001101011111001配對(duì)情況交叉點(diǎn)位置個(gè)體編號(hào)12341-23-41-2：23-4：4交叉結(jié)果011001111101101001111011可以看出，其中新產(chǎn)生的個(gè)體“111101”、“111011”的適應(yīng)度較原來(lái)兩個(gè)個(gè)體的適應(yīng)度都要高。第十六頁(yè)，共二十七頁(yè)，編輯于2023年，星期三(6)變異運(yùn)算變異運(yùn)算是對(duì)個(gè)體的某一個(gè)或某一些基因座上的基因值按某一較小的概率進(jìn)行改變，它也是產(chǎn)生新個(gè)體的一種操作方法。本例中，我們采用基本位變異的方法來(lái)進(jìn)行變異運(yùn)算，其具體操作過(guò)程是：

?首先確定出各個(gè)個(gè)體的基因變異位置，下表所示為隨機(jī)產(chǎn)生的變異點(diǎn)位置，其中的數(shù)字表示變異點(diǎn)設(shè)置在該基因座處；

?然后依照某一概率將變異點(diǎn)的原有基因值取反。對(duì)群體P(t)進(jìn)行一輪選擇、交叉、變異運(yùn)算之后可得到新一代的群體p(t+1)。個(gè)體編號(hào)1234交叉結(jié)果011001111101101001111011變異結(jié)果變異點(diǎn)4526011101111111111001111010子代群體p(1)011101111111111001111010第十七頁(yè)，共二十七頁(yè)，編輯于2023年，星期三從上表中可以看出，群體經(jīng)過(guò)一代進(jìn)化之后，其適應(yīng)度的最大值、平均值都得到了明顯的改進(jìn)。事實(shí)上，這里已經(jīng)找到了最佳個(gè)體“111111”。

[注意]

需要說(shuō)明的是，表中有些欄的數(shù)據(jù)是隨機(jī)產(chǎn)生的。這里為了更好地說(shuō)明問(wèn)題，我們特意選擇了一些較好的數(shù)值以便能夠得到較好的結(jié)果，而在實(shí)際運(yùn)算過(guò)程中有可能需要一定的循環(huán)次數(shù)才能達(dá)到這個(gè)最優(yōu)結(jié)果。個(gè)體編號(hào)子群體p(1)適值占總數(shù)的百分比總和1234011101111111111001111010349850530.140.420.210.232351

x1x2

35777172第十八頁(yè)，共二十七頁(yè)，編輯于2023年，星期三個(gè)體編號(hào)初始群體p(0)適值fi(x1,x2)占總數(shù)的百分比f(wàn)i/f1234011101101011011100111001343425500.240.240.170.35

x1x2

35533471fi=143fmax=50f=35.75選擇結(jié)果011101111001101011111001配對(duì)情況交叉點(diǎn)位置1-23-41-2：23-4：4交叉結(jié)果011001111101101001111011選擇次數(shù)1102變異結(jié)果變異點(diǎn)4526011101111111111001111010子代群體p(1)適值fi(x1,x2)占總數(shù)的百分比f(wàn)i/f011101111111111001111010349850530.140.420.210.23

x1x2

35777172fi=253fmax=98f=58.75第十九頁(yè)，共二十七頁(yè)，編輯于2023年，星期三1.3遺傳算法的發(fā)展進(jìn)化算法與其他科學(xué)技術(shù)一樣，都經(jīng)歷一段成長(zhǎng)過(guò)程，逐漸發(fā)展壯大。此過(guò)程可大致分為三個(gè)時(shí)期：萌芽期、成長(zhǎng)期和發(fā)展期。

(1)萌芽期(50年代后期至70年代初期)

?50年代后期，一些生物學(xué)家著手采用電子計(jì)算機(jī)模擬生物的遺傳系統(tǒng)，盡管這些工作純粹是研究生物現(xiàn)象，但其中已使用現(xiàn)代遺傳算法的一些標(biāo)識(shí)方式。

?1965年，德國(guó)的L.Rechenberg等人正式提出進(jìn)化策略的方法，當(dāng)時(shí)的進(jìn)化策略只有一個(gè)個(gè)體，而且進(jìn)化操作也只有變異一種。

?1965年，美國(guó)的L.j.Fogel正式提出進(jìn)化規(guī)劃，在計(jì)算中采用多個(gè)個(gè)體組成的群體，而且只運(yùn)用變異操作。

?60年代期間，美國(guó)J.H.Holland在研究自適應(yīng)系統(tǒng)時(shí)，提出系統(tǒng)本身與外部環(huán)境相互協(xié)調(diào)的遺傳算法。1968年，J.H.Holland教授又提出模式理論，它成為遺傳算法的主要理論基礎(chǔ)。

?1967年，Bagley發(fā)表了關(guān)于遺傳算法應(yīng)用的論文，在其論文中首次使用“遺傳算法（GeneticAlgorithm）”一詞。第二十頁(yè)，共二十七頁(yè)，編輯于2023年，星期三

(2)成長(zhǎng)期(70年代中期至80年代末期)

?1975年，J.H.Holland教授的專著《自然界和人工系統(tǒng)的適應(yīng)性(AdaptationinNaturalandArtificialSystem)》正式出版，全面地介紹了遺傳算法，人們常常把這一事件視作遺傳算法問(wèn)世的標(biāo)志，Holland也被視作遺傳算法的創(chuàng)始人。

?1975年，De.Jong在其博士論文中結(jié)合模式定理進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)，樹立了遺傳算法的工作框架，得到了一些重要且具有指導(dǎo)意義的結(jié)論。

?1987年，美國(guó)D.Lawrence總結(jié)人們長(zhǎng)期從事遺傳算法的經(jīng)驗(yàn)，公開出版《遺傳算法和模擬退火(GeneticAlgorithmandSimulatedAnnealing)》一書，以論文集形式用大量實(shí)例介紹遺傳算法。

?1985年，作為Holland的學(xué)生，D.E.Goldberg博士出版專著《遺傳算法——搜索、優(yōu)化及機(jī)器學(xué)習(xí)(GeneticAlgorithms——inSearch，OptimizationandMachineLearning)》，全面、系統(tǒng)地介紹遺傳算法，使這一技術(shù)得到普及與推廣。該書被人們視為遺傳算法的教科書。

?1985年，在美國(guó)舉行第一屆遺傳算法國(guó)際學(xué)術(shù)會(huì)議(InternationalConferenceonGeneticAlgorithms，簡(jiǎn)稱ICGA），與會(huì)者交流運(yùn)用遺傳算法的經(jīng)驗(yàn)。隨后，

1987，1989，1991，1993，l995及l(fā)997年，每2年左右都舉行一次這種會(huì)議。第二十一頁(yè)，共二十七頁(yè)，編輯于2023年，星期三(3)發(fā)展期(90年代以后)90年代，遺傳算法不斷地向廣度和深度發(fā)展。

?1991年，D.Lawrence出版《遺傳算法手冊(cè)(HandbookofGeneticAlgorithms)一書，詳盡地介紹遺傳算法的工作細(xì)節(jié)。

?1996年Z.Michalewicz的專著《遺傳算法+數(shù)據(jù)結(jié)構(gòu)=進(jìn)化程序》深入討論了遺傳算法的各種專門問(wèn)題。同年，T.Back的專著《進(jìn)化算法的理論與實(shí)踐：進(jìn)化策略、進(jìn)化規(guī)劃、遺傳算法》

深入闡明進(jìn)化算法的許多理論問(wèn)題。

?1992年，Koza出版專著《遺傳規(guī)劃——應(yīng)用自然選擇法則的計(jì)算機(jī)程序設(shè)計(jì)(GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection)》，該書全面介紹了遺傳規(guī)劃的原理及應(yīng)用實(shí)例，標(biāo)明遺傳規(guī)劃己成為進(jìn)化算法的一個(gè)重要分支。Koza本人也被視作遺傳規(guī)劃的奠基人。

?1994年，Koza又出版第二部專著《遺傳規(guī)劃Ⅱ：可再用程序的自動(dòng)發(fā)現(xiàn)(GeneticProgrammingⅡ:AutomaticDiscoveryofReusablePrograms)》，提出自動(dòng)定義函數(shù)的新概念，在遺傳規(guī)劃中引入子程序的新技術(shù)。同年，K.E.Kinnear主編《遺傳規(guī)劃進(jìn)展(AdvancesinGeneticProgramming)》，匯集許多研究工作者有關(guān)應(yīng)用遺傳規(guī)劃的經(jīng)驗(yàn)和技術(shù)。第二十二頁(yè)，共二十七頁(yè)，編輯于2023年，星期三

?90年代期間，有關(guān)遺傳算法的國(guó)際會(huì)議也比較活躍，見下表。

?我國(guó)開展遺傳算法研究，主要在90年代。目前，已成為繼專家系統(tǒng)、人工神經(jīng)網(wǎng)絡(luò)之后有關(guān)人工智能方面的第三個(gè)熱點(diǎn)課題。第二十三頁(yè)，共二十七頁(yè)，編輯于2023年，星期三1.4遺傳算法的應(yīng)用遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化間題的通用框架，它不依賴于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域：

(1)函數(shù)優(yōu)化函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問(wèn)題，用其他優(yōu)化方法較難求解，用遺傳算法可以方便地得到較好的結(jié)果。

(2)組合優(yōu)化隨著問(wèn)題規(guī)模的增大，組合優(yōu)化問(wèn)題的搜索空間也急劇擴(kuò)大，有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對(duì)這類復(fù)雜問(wèn)題，人們己意識(shí)到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的NP完全問(wèn)題非常有效。例如，遺傳算法已經(jīng)在求解旅行商問(wèn)題、背包問(wèn)題、裝箱問(wèn)題、圖形劃分問(wèn)題等方面得到成功的應(yīng)用。第二十四頁(yè)，共二十七頁(yè)，編輯于2023年，星期三

(3)生產(chǎn)調(diào)度問(wèn)題生產(chǎn)調(diào)度問(wèn)題在很多情況下所建立起來(lái)的數(shù)學(xué)模型難以精確求解，即使經(jīng)過(guò)一些簡(jiǎn)化之后可以進(jìn)行求解，也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。而目前在現(xiàn)實(shí)生產(chǎn)中也主要是靠一些經(jīng)驗(yàn)來(lái)進(jìn)行調(diào)度。現(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問(wèn)題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。

(4)自動(dòng)控制在自動(dòng)控制領(lǐng)域中很多與優(yōu)化相關(guān)的問(wèn)題需要求解，遺傳算法已在其中得到了初步的應(yīng)用，并顯示出了良好的效果。例如用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計(jì)