遺傳算法的生物學基礎第一頁，共二十七頁，編輯于2023年，星期三

?構成生物的基本結構和功能的單位是細胞(Ce11)。

?

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

?

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

?

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

?

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

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

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

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

3.變異在進行細胞復制時，雖然概率很小，僅僅有可能產生某些復制差錯，從而使

DNA發生某種變異(Mutation)，產生出新的染色體。這些新的染色體表現出新的性狀。

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

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

?

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

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

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

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

(2)染色體是由基因及其有規律的排列所構成的，遺傳和進化過程發生在染色體上；

(3)生物的繁殖過程是由其基因的復制過程來完成的；

(4)通過同源染色體之間的交叉或染色體的變異會產生新的物種，使生物呈現新的性狀。

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

遺傳算法是模擬生物在自然環境下的遺傳和進化過程而形成的一種自適應全局優化概率搜索方法。

它最早由美國密西根大學的H.Holland教授提出，起源于60年代對自然和人工自適應系統的研究；

1967年，Bagley發表了關于遺傳算法應用的論文，在其論文中首次使用“遺傳算法（GeneticAlgorithm）”一詞。

70年代

DeJong基于遺傳算法的思想在計算機上進行了大量的純數值函數優化計算實驗。

在一系列研究工作的基礎上，80年代由Goldberg進行歸納總結，形成了遺傳算法的基本框架。

第七頁，共二十七頁，編輯于2023年，星期三1.2.1遺傳算法概要對于一個求函數最大值的優化問題（求最小值也類同），一般可描述為下述數學規劃模型：

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

其中：

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

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

U是基本空間，

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

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

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

X＝xlx2…xn

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

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

?

這里的等位基因可以是一組整數。也可以是某一范圍內的實數值，或者是純粹的一個記號。最簡單的等位基因是由0和1這兩個整數組成的，相應的染色體就可表示為一個二進制符號串。

?這種編碼所形成的排列形式X是個體的基因型，與它對應的X值是個體的表現型。

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

這個群體不斷地經過遺傳和進化操作，并且每次都按照優勝劣汰的規則將適應度較高的個體更多地遺傳到下一代，這樣最終在群體中將會得到一個優良的個體

X，它所對應的表現型X將達到或接近于問題的最優解X*。第十一頁，共二十七頁，編輯于2023年，星期三1.2.2遺傳策法的運算過程選擇(復制)：根據各個個體的適應度，按照一定的規則或方法，從第t代群體P(t)

中選擇出一些優良的個體遺傳到下一代群體P(t+1)中；交叉：將群體P(t)內的各個個體隨機搭配成對，對每一對個體，以某個概率

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

例：求下述二元函數的最大值：

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

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

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

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

例如，基因型X＝101110所對應的表現型是：x＝[5，6]。個體的表現型x和基因型X之間可通過編碼和解碼程序相互轉換。第十三頁，共二十七頁，編輯于2023年，星期三

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

(3)適應度汁算遺傳算法中以個體適應度的大小來評定各個個體的優劣程度，從而決定其遺傳機會的大小。本例中，目標函數總取非負值，并且是以求函數最大值為優化目標，故可直接利用目標函數值作為個體的適應度。

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

?先計算出群體中所有個體的適應度的總和fi

(i=1.2,…,M);

?其次計算出每個個體的相對適應度的大小fi/fi

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

?

每個概率值組成一個區域，全部概率值之和為1；

?最后再產生一個0到1之間的隨機數，依據該隨機數出現在上述哪一個概率區域內來確定各個個體被選中的次數。0124%24%17%35%1#2#3#4#個體編號初始群體p(0)適值占總數的百分比總和1234011101101011011100111001343425500.240.240.170.351431選擇次數選擇結果1102011101111001101011111001

x1x2

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

?先對群體進行隨機配對；

?其次隨機設置交叉點位置；

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

?首先確定出各個個體的基因變異位置，下表所示為隨機產生的變異點位置，其中的數字表示變異點設置在該基因座處；

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

[注意]

需要說明的是，表中有些欄的數據是隨機產生的。這里為了更好地說明問題，我們特意選擇了一些較好的數值以便能夠得到較好的結果，而在實際運算過程中有可能需要一定的循環次數才能達到這個最優結果。個體編號子群體p(1)適值占總數的百分比總和1234011101111111111001111010349850530.140.420.210.232351

x1x2

35777172第十八頁，共二十七頁，編輯于2023年，星期三個體編號初始群體p(0)適值fi(x1,x2)占總數的百分比fi/f1234011101101011011100111001343425500.240.240.170.35

x1x2

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

x1x2

35777172fi=253fmax=98f=58.75第十九頁，共二十七頁，編輯于2023年，星期三1.3遺傳算法的發展進化算法與其他科學技術一樣，都經歷一段成長過程，逐漸發展壯大。此過程可大致分為三個時期：萌芽期、成長期和發展期。

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

?50年代后期，一些生物學家著手采用電子計算機模擬生物的遺傳系統，盡管這些工作純粹是研究生物現象，但其中已使用現代遺傳算法的一些標識方式。

?1965年，德國的L.Rechenberg等人正式提出進化策略的方法，當時的進化策略只有一個個體，而且進化操作也只有變異一種。

?1965年，美國的L.j.Fogel正式提出進化規劃，在計算中采用多個個體組成的群體，而且只運用變異操作。

?60年代期間，美國J.H.Holland在研究自適應系統時，提出系統本身與外部環境相互協調的遺傳算法。1968年，J.H.Holland教授又提出模式理論，它成為遺傳算法的主要理論基礎。

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

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

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

?1975年，De.Jong在其博士論文中結合模式定理進行了大量的純數值函數優化計算實驗，樹立了遺傳算法的工作框架，得到了一些重要且具有指導意義的結論。

?1987年，美國D.Lawrence總結人們長期從事遺傳算法的經驗，公開出版《遺傳算法和模擬退火(GeneticAlgorithmandSimulatedAnnealing)》一書，以論文集形式用大量實例介紹遺傳算法。

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

?1985年，在美國舉行第一屆遺傳算法國際學術會議(InternationalConferenceonGeneticAlgorithms，簡稱ICGA），與會者交流運用遺傳算法的經驗。隨后，

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

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

?1996年Z.Michalewicz的專著《遺傳算法+數據結構=進化程序》深入討論了遺傳算法的各種專門問題。同年，T.Back的專著《進化算法的理論與實踐：進化策略、進化規劃、遺傳算法》

深入闡明進化算法的許多理論問題。

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

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

?90年代期間，有關遺傳算法的國際會議也比較活躍，見下表。

?我國開展遺傳算法研究，主要在90年代。目前，已成為繼專家系統、人工神經網絡之后有關人工智能方面的第三個熱點課題。第二十三頁，共二十七頁，編輯于2023年，星期三1.4遺傳算法的應用遺傳算法提供了一種求解復雜系統優化間題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科。下面是遺傳算法的一些主要應用領域：

(1)函數優化函數優化是遺傳算法的經典應用領域，也是對遺傳算法進行性能評價的常用算例。對于一些非線性、多模型、多目標的函數優化問題，用其他優化方法較難求解，用遺傳算法可以方便地得到較好的結果。

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

(3)生產調度問題生產調度問題在很多情況下所建立起來的數學模型難以精確求解，即使經過一些簡化之后可以進行求解，也會因簡化得太多而使得求解結果與實際相差甚遠。而目前在現實生產中也主要是靠一些經驗來進行調度。現在遺傳算法已成為解決復雜調度問題的有效工具，在單件生產車間調度、流水線生產車間調度、生產規劃、任務分配等方面遺傳算法都得到了有效的應用。

(4)自動控制在自動控制領域中很多與優化相關的問題需要求解，遺傳算法已在其中得到了初步的應用，并顯示出了良好的效果。例如用遺傳算法進行航空控制系統的優化、使用遺傳算法設計