《遺傳算法》PPT課件.ppt

1、遺傳算法,2021/1/1,華中農業(yè)大學理學院,2,2021/1/1,華中農業(yè)大學理學院,3,第1章 人工智能概述 1.1 什么是人工智能 1.2 人工智能的研究意義、目標和策略 1.3 人工智能的學科范疇 1.4 人工智能的研究內容 1.5 人工智能的研究途徑與方法 1.6 人工智能的基本技術 1.7 人工智能的應用 1.8 人工智能的分支領域與研究方向 1.9 人工智能的發(fā)展概況,2021/1/1,華中農業(yè)大學理學院,4,1.1 什么是人工智能 人工智能（Artificial Intelligence”，AI） 1.1.1 人工智能概念的一般描述 部分學者對人工智能概念的描述： 人工智能是

2、那些與人的思維相關的活動，諸如決策、問題求解和學習等的自動化（Bellman, 1978）； 人工智能是一種計算機能夠思維，使機器具有智力的激動人心的新嘗試（Haugeland, 1985）； 人工智能是研究如何讓計算機做現階段只有人才能做得好的事情（Rich Knight,1991）；,2021/1/1,華中農業(yè)大學理學院,5, 人工智能是那些使知覺、推理和行為成為可能的計算的研究（Winston, 1992）； 廣義地講，人工智能是關于人造物的智能行為，而智能行為包括知覺、推理、學習、交流和在復雜環(huán)境中的行為（Nilsson，1998）。 Stuart Russell和Peter Norv

3、ig則把已有的一些人工智能定義分為4類：像人一樣思考的系統(tǒng)、像人一樣行動的系統(tǒng)、理性地思考的系統(tǒng)、理性地行動的系統(tǒng)（2003）。,2021/1/1,華中農業(yè)大學理學院,6,1.1.2 圖靈測試和中文屋子 圖靈測試”（Turing Test）,2021/1/1,華中農業(yè)大學理學院,7,約翰.西爾勒(John Searle)的 “中文屋子”,2021/1/1,華中農業(yè)大學理學院,8,1.1.3 腦智能和群智能 腦（主要指人腦）的宏觀心理層次的智能表現稱為腦智能（Brain Intelligence, BI）。 由群體行為所表現出的智能稱為群智能（Swarm Intelligence, SI）。 腦

4、智能和群智能是屬于不同層次的智能： 腦智能是一種個體智能（Individual Intelligence, II）； 群智能是一種社會智能（Social Intelligence, SI）， 或者說系統(tǒng)智能（System Intelligence, SI）。,2021/1/1,華中農業(yè)大學理學院,9,1.1.4 符號智能和計算智能 1. 符號智能 符號智能就是符號人工智能，它是模擬腦智能的人工智能，也就是所說的傳統(tǒng)人工智能或經典人工智能。符號智能以符號形式的知識和信息為基礎，主要通過邏輯推理，運用知識進行問題求解。符號智能的主要內容包括知識獲?。╧nowledge acquisition）、知

5、識表示（knowledge representation）、知識組織與管理和知識運用等技術（這些構成了所謂的知識工程（Knowledge Engineering, KE）以及基于知識的智能系統(tǒng)等。,2021/1/1,華中農業(yè)大學理學院,10,2. 計算智能 計算智能就是計算人工智能，它是模擬群智能的人工智能。計算智能以數值數據為基礎，主要通過數值計算，運用算法進行問題求解。計算智能的主要內容包括：神經計算（Neural Computation， NC）、進化計算（亦稱演化計算，Evolutionary Computation，EC，包括遺傳算法（Genetic Algorithm，GA）、進化

6、規(guī)劃（Evolutionary Planning，EP）、進化策略（Evolutionary Strategies，ES）等）、免疫計算（immune computation）、粒群計算（Particle Swarm Algorithm，PSA）、蟻群算法（Ant Colony Algorithm，ACA）、自然計算（Natural Computation，NC）以及人工生命（Artificial Life，AL）等。,2021/1/1,華中農業(yè)大學理學院,11,1.2 人工智能的研究意義、目標和策略 1.2.1 為什么要研究人工智能 使當前的電腦更好用，更有用，以擴大和延伸人類智能； 信息化

7、社會的迫切要求； 自動化發(fā)展的必然趨勢； 有益于探索人類自身智能的奧秘。,2021/1/1,華中農業(yè)大學理學院,12,1.2.2 人工智能的研究目標和策略 研究目標就是制造智能機器和智能系統(tǒng)，實現智能化社會。具體來講，就是要使計算機不僅具有腦智能和群智能，還要具有看、聽、說、寫等感知和交流能力。 研究策略則是先部分地或某種程度地實現機器的智能，并運用智能技術解決各種實際問題特別是工程問題，從而使現有的計算機更靈活、更好用和更有用，成為人類的智能化信息處理工具，而逐步擴展和不斷延伸人的智能，逐步實現智能化。,2021/1/1,華中農業(yè)大學理學院,13,1.3 人工智能的學科范疇 人工智能已構成信

8、息技術領域的一個重要學科。當前的人工智能既屬于計算機科學技術的一個前沿領域，也屬于信息處理和自動化技術的一個前沿領域。還涉及到智能科學、認知科學、心理科學、腦及神經科學、生命科學、語言學、邏輯學、行為科學、教育科學、系統(tǒng)科學、數理科學以及控制論、科學方法論、哲學甚至經濟學等眾多學科領域。人工智能實際上是一門綜合性的交叉學科和邊緣學科。,2021/1/1,華中農業(yè)大學理學院,14,1.4 人工智能的研究內容 1.5.1 搜索與求解 1.5.2 學習與發(fā)現 1.5.3 知識與推理 1.5.4 發(fā)明與創(chuàng)造 1.5.5 感知與交流 1.5.6 記憶與聯想 1.5.7 系統(tǒng)與建造 1.5.8 應用與工程

9、,2021/1/1,華中農業(yè)大學理學院,15,1.5 人工智能的研究途徑與方法 1.5.1 心理模擬，符號推演 1.5.2 生理模擬，神經計算 1.5.3 行為模擬，控制進化 1.5.4 群體模擬，仿生計算 1.5.5 博采廣鑒，自然計算 1.5.6 原理分析，數學建模,2021/1/1,華中農業(yè)大學理學院,16,1.6 人工智能的基本技術 表示 運算 搜索,2021/1/1,華中農業(yè)大學理學院,17,1.7 人工智能的應用 1.7.1 難題求解 1.7.2 自動規(guī)劃、調度與配置 1.7.3 機器定理證明 1.7.4 自動程序設計 1.7.5 機器翻譯 1.7.6 智能控制 1.7.7 智能管

10、理 1.7.8 智能決策 1.7.9 智能通信 1.7.10 智能仿真,2021/1/1,華中農業(yè)大學理學院,18,1.7.11 智能CAD 1.7.12 智能制造 1.7.13 智能CAI 1.7.14 智能人機接口 1.7.15 模式識別 1.7.16 數據挖掘與數據庫中的知識發(fā)現 1.7.17 計算機輔助創(chuàng)新 1.7.18 計算機文藝創(chuàng)作 1.7.19 機器博弈 1.7.20 智能機器人,2021/1/1,華中農業(yè)大學理學院,19,1.8 人工智能的分支領域與研究方向 從模擬的層次和所用的方法來看，人工智能可分為符號智能和計算智能兩大主要分支領域。而這兩大領域各自又有一些子領域和研究方向

11、。如符號智能中又有圖搜索、自動推理、不確定性推理、知識工程、符號學習等。計算智能中又有神經計算、進化計算、免疫計算、蟻群計算、粒群計算、自然計算等。另外，智能Agent也是人工智能的一個新興的重要領域。智能Agent或者說Agent智能則是以符號智能和計算智能為基礎的更高一級的人工智能。 從模擬的腦智能或腦功能來看，AI中有機器學習、機器感知、機器聯想、機器推理、機器行為等分支領域。而機器學習又可分為符號學習、連接學習、統(tǒng)計學習等許多研究領域和方向。機器感知又可分為計算機視覺、計算機聽覺、模式識別、圖像識別與理解、語音識別、自然語言處理等領域和方向。,2021/1/1,華中農業(yè)大學理學院,20

12、,從應用角度看，如1.7節(jié)所述，AI中有難題求解等數十種分支領域和研究方向。 從系統(tǒng)角度看，有智能計算機系統(tǒng)和智能應用系統(tǒng)兩大類。智能計算機系統(tǒng)又可分為：智能硬件平臺、智能操作系統(tǒng)、智能網絡系統(tǒng)等。智能應用系統(tǒng)又可分為：基于知識的智能系統(tǒng)、基于算法的智能系統(tǒng)和兼有知識和算法的智能系統(tǒng)等。另外，還有分布式人工智能系統(tǒng)。 從基礎理論看，AI中有數理邏輯和多種非標準邏輯、圖論、人工神經網絡、模糊集、粗糙集、概率統(tǒng)計（貝葉斯統(tǒng)計決策理論）和貝葉斯網絡、統(tǒng)計學習理論與支持向量機、形式語言與自動機等領域和方向。,2021/1/1,華中農業(yè)大學理學院,21,1.9 人工智能學科的發(fā)展概況 1.9.1 人工智

13、能學科的產生 1.9.2 符號主義途徑發(fā)展概況 1.9.3 連接主義途徑發(fā)展概況 1.9.4 計算智能異軍突起 1.9.5 智能Agent方興未艾,2021/1/1,華中農業(yè)大學理學院,22,1.9.6 現狀與發(fā)展趨勢 多種途徑齊頭并進，多種方法協(xié)作互補。 新思想、新技術不斷涌現，新領域、新方向不斷開拓。 理論研究更加深入，應用研究愈加廣泛。 研究隊伍日益壯大，社會影響越來越大。,2021/1/1,華中農業(yè)大學理學院,23,雖然在通向人工智能最終目標的道路上，還有不少困難、問題和挑戰(zhàn)，但前進和發(fā)展畢竟是大勢所趨。,2021/1/1,華中農業(yè)大學理學院,24,智能交通,2021/1/1,華中農業(yè)

14、大學理學院,25,圖像識別系統(tǒng),2021/1/1,華中農業(yè)大學理學院,26,云松 鑾仙玉骨寒， 松虬雪友繁。 大千收眼底， 斯調不同凡。,2021/1/1,華中農業(yè)大學理學院,27,（無題） 白沙平舟夜?jié)暎?春日曉露路相逢。 朱樓寒雨離歌淚， 不堪腸斷雨乘風。,2021/1/1,華中農業(yè)大學理學院,28,2021/1/1,華中農業(yè)大學理學院,29,2021/1/1,華中農業(yè)大學理學院,30,2021/1/1,華中農業(yè)大學理學院,31,2021/1/1,華中農業(yè)大學理學院,32,遺傳算法主要內容,一、遺傳算法入門 二、遺傳算法的主要特征 三、遺傳算法的運行步驟 四、基本遺傳算法的構成要素 五、

15、遺傳算法的數學理論 六、遺傳算法的基本實現技術 七、遺傳算法的特點 八、遺傳算法的應用,2021/1/1,華中農業(yè)大學理學院,33,遺傳算法(Genetic Algorithm, GA)是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法，它借用了生物遺傳學的觀點，通過自然選擇、遺傳、變異等作用機制，實現各個個體的適應性的提高。這一點體現了自然界中“物競天擇、適者生存”進化過程。1962年Holland教授首次 提出了GA算法的思想，從而吸引了大批的研究者，迅速推廣到優(yōu)化、搜索、機器學習等方 面，并奠定了堅實的理論基礎。 遺傳算法是 John Holland大腦的產物，早在上個世紀60年代，他已提出了這種

16、想法。但不可思議的是，他沒有感到需要在計算機上實際試驗出結果，而寧愿利用筆和紙來作修修補補的工作！ 直到后來他的一名學生編寫出程序并在一臺個人計算機上運行后，才使人們終于看到在軟件中利用他的思想能夠得到什么。,一、遺傳算法入門,2021/1/1,華中農業(yè)大學理學院,34,一、遺傳算法入門,生物只有經過許多世代的不斷演化（evolution），才能更好地完成生存與繁衍的任務。 遺傳算法也遵循同樣的方式，需要隨著時間的推移不斷成長、演化，最后才能收斂，得到針對某類特定問題的一個或多個解。 因此，了解一些有關有生命的機體如何演化的知識，對理解遺傳算法的演化機制是是有幫助的。我們將扼要闡述自然演化的機

17、制（通常稱為“濕”演化算法），以及與之相關的術語。理解自然演化的基本機制。我想，你也會和我一樣，深深嘆服自然母親的令人著迷！,2021/1/1,華中農業(yè)大學理學院,35,本質上說，任何生物機體就是一大堆細胞的集合。每個細胞都包含若干組相同的DNA鏈，人們一般稱之為染色體（chromosome）。染色體中包含的DNA分為兩股，這兩股DNA鏈以螺旋狀絞合在一起，如下面圖所示那樣，這就是我們所熟悉的DNA雙螺旋結構模型。,DNA雙螺旋結構,一、遺傳算法入門,2021/1/1,華中農業(yè)大學理學院,36,單個染色體是由稱作基因（gene）的更小的結構模塊組成，而基因則又由稱作核苷酸（nucleotide

18、）的物質組成。 核苷酸一共只有四種類型，即：腺嘌呤(thymine)、鳥嘌呤(adenine)、胞嘧啶(cytocine)、胸腺嘧啶(guanine)。常簡寫為T、A、C、G。這些核苷酸相互連接起來，形成若干很長的基因鏈，而每個基因編碼了生物機體的某種特征，如頭發(fā)的顏色，耳朵的樣子，等。一個基因可能具有的不同設置（如頭發(fā)的黑色、棕色或金黃色），稱為等位基因（allele），它們沿染色體縱向所處的物理部位稱為基因的座位（locus）。,一、遺傳算法入門,2021/1/1,華中農業(yè)大學理學院,37,二進制數速成（A Quick Lesson in Binary Numbers）,數字15,如果要把

19、15寫成8位的二進制，則要寫成下面這樣的形式，其中高位都是，但也要把前面寫出來，以使整個長度達到： 00001111,2021/1/1,華中農業(yè)大學理學院,38,計算機內的進化 （ Evolution Inside Your Computer ）,遺傳算法工作過程本質上就是模擬生物的進化過程。 首先，要規(guī)定一種編碼方法，使得你的問題的任何一個潛在可行解都能表示成為一個“數字”染色體。 然后，創(chuàng)建一個由隨機的染色體組成的初始群體（每個染色體代表了一個不同的候選解），并在一段時期中，以培育適應性最強的個體的辦法，讓它們進化，在此期間，染色體的某些位置上要加入少量的變異。 經過許多代后，運氣好一點，

20、遺傳算法會收斂到一個解。 遺傳算法不保證一定能得到解，也不保證找到的是最優(yōu)解，但只要采用的方法正確，通常都能為遺傳算法編出一個能夠很好運行的程序。 遺傳算法的最大優(yōu)點就是， 你不需知道怎么去解決一個問題; 需要知道的僅是，用怎么方式對可行解進行編碼，使得它能能被遺傳算法機制所利用。,2021/1/1,華中農業(yè)大學理學院,39,通常，代表可行解的染色體采用一系列的二進制位作為編碼。在運行開始時，創(chuàng)建一個染色體的群體，每個染色體都是一組隨機的進制位。進制位（即染色體）的長度在整個群體中都是一樣的。 作為一個例子，長度為 20的染色體的形狀如下: 01010010100101001111 重要的事情

21、是，每個染色體都用這樣的方式編碼成為由 0和1組成的字符串，而它們通過 譯碼 就能用來表示你手頭問題的一個解。這可能是一個很差的解，也可能是一個十分完美的解，但每一個單個的染色體都代表了一個可行解。初始群體通常都是 較糟的 ，有點中國男足球隊。但，一個初始的群體已經創(chuàng)建完成（對這一例子，不妨設共有100個成員），這樣，就可以開始做下面列出的一系列工作。,2021/1/1,華中農業(yè)大學理學院,40,不斷進行下列循環(huán)，直到尋找出一個解 : 1.檢查每個染色體，看它解決問題的性能怎樣，并相應地為它分配一個適應性分數。 2. 從當前群體中選出2個成員。被選出的概率正比于染色體的適應性，適應性分數愈高，

22、被選中的可能性也就愈大。常用的方法就是采用所謂的 輪盤賭選擇 法 或 賭 輪選擇 法 (Roulette wheel selection )。 3.按照預先設定的 雜交率 （Crossover Rate ），從每個選中染色體的一個隨機的點上進行雜交（crossover ）。 4.按照預定的 變異率 （ mutation rate ），通過對被選染色體的位的循環(huán)，把相應的位實行翻轉（ flip ）。 5.重復步驟2，3，4，直到100個成員的新群體被創(chuàng)建出來。 結束循環(huán) 以上算法中步驟1 到步驟5 的一次循環(huán)稱為一個代（或世代，generation）。而我把這整個的循環(huán)稱作一個時代（epoch）

23、 。,2021/1/1,華中農業(yè)大學理學院,41,什么是輪盤賭選擇？ ( Whats the Roulette Wheel Selection ),輪盤賭選擇是從染色體群體中選擇一些成員的方法，被選中的機率和它們的適應性分數成比例，染色體的適應性分數愈高，被選中的概率也愈多。這不保證適應性分數最高的成員一定能選入下一代，僅僅說明它有最大的概率被選中。其工作過程是這樣的： 設想群體全體成員的適當性分數由一張餅圖來代表 (見下圖)，這一餅圖就和用于賭博的轉輪形狀一樣。我們要為群體中每一染色體指定餅圖中一個小塊。塊的大小與染色體的適應性分數成比例，適應性分數愈高，它在餅圖中對應的小塊所占面積也愈大。

24、為了選取一個染色體，你要做的，就是旋轉這個輪子，并把一個小球拋入其中，讓它翻來翻去地跳動，直到輪盤停止時，看小球停止在哪一塊上，就選中與它對應的那個染色體。,染色體的輪盤賭式選擇,2021/1/1,華中農業(yè)大學理學院,42,輪盤賭選擇,SGenome 程序通過循環(huán)來考察各基因組，把它們相應的適應性分數一個一個累加起來，直到這一 部分累加和 大于 fSlice 值時，就返回該基因組。,2021/1/1,華中農業(yè)大學理學院,43,什么是雜交率？( Whats the Crossover Rate ),雜交率就是用來確定 2個染色體進行局部的位（bit）的互換以產生2個新的子代的概率。 實驗表明這一

25、數值通常取為0.7左右是理想的，盡管某些問題領域可能需要更高一些或較低一些的值。 每次，從群體中選擇 2個染色體，同時生成其值在0到1之間一個隨機數，然后根據此數據的值來確定兩個染色體是否要進行雜交。如果數值低于雜交率(O.7)就進行雜交，就沿著染色體的長度隨機選擇一個位置，并把此位置后面所有的位進行互換。 例如，設給定的 2個染色體為: 10001001110010010 01010001001000011 沿著它們的長度你隨機選擇一個位置，比如說 10，然后互換第10位之后所有位。這樣兩個染色體就變成了： 100010011 01000011 010100010 10010010,雜交操作

26、（Crossover Revisited）,這一函數要求個染色體在同一隨機位置上斷裂開，然后將它們在斷開點以后部分進行互換，以形成 2 個新的染色體 ( 子代 ) 。 void CgaBob:Crossover( const vector 這兩循環(huán)把 2 個 parent 染色體在雜交點（ CP,crossover point ）以后的所有位進行了互換，并把新染色體賦給了 2 個子代 : baby1 和 baby2 。,2021/1/1,華中農業(yè)大學理學院,45,什么是變異率？( Whats the Mutation Rate? ),變異率（突變率） 就是在一個染色體中將位實行翻轉（flip，

27、即0 變1，1變 0）的幾率。這對于二進制編碼的基因來說通常都是很低的值，比如 0.001 。 因此，無論你從群體中怎樣選擇染色體，你首先是檢查是否要雜交，然后再從頭到尾檢查子代染色體的各個位，并按所規(guī)定的幾率對其中的某些位實行突變（翻轉）。,2021/1/1,華中農業(yè)大學理學院,46,變異操作（Mutation Revisited）,這一函數所做的工作，不過就是沿著一個染色體的長度，一bit一bit地進行考察，并按m_dMutationRate給定的幾率，將其中某些bit實行翻轉。 void CgaBob:Mutate(vector /移到下一個bit 遺傳算法程序也就這樣完成了！,2021

28、/1/1,華中農業(yè)大學理學院,47,用遺傳算法解決問題時，首先要對待解決問題的模型結構和參數進行編碼，一般用字符串表示，這個過程就將問題符號化、離散化了。也有在連續(xù)空間定義的GA(Genetic Algorithm in Continuous Space, GACS)，暫不討論。：,2021/1/1,華中農業(yè)大學理學院,48,一個串行運算的遺傳算法(Seguential Genetic Algoritm, SGA)按如下過程進行,(1)對待解決問題進行編碼； (2)隨機初始化群體X(0):=(x1, x2, xn)； (3)對當前群體X(t)中每個個體xi計算其適應度F(xi)，適應度表示了該

29、個體的性能好 壞； (4)應用選擇算子產生中間代Xr(t)； (5)對Xr(t)應用其它的算子，產生新一代群體X(t+1)，這些算子的目的在于擴展有限個體的覆蓋面，體現全局搜索的思想； (6)t:=t+1；如果不滿足終止條件繼續(xù)(3),2021/1/1,華中農業(yè)大學理學院,49,GA中最常用的算子,(1)選擇算子(selection/reproduction): 選擇算子從群體中按某一概率成對選擇個體，某個體xi被選擇的概率Pi與其適應度值成正比。最通常的實現方法是輪盤賭(roulett e wheel)模型。 (2)交叉算子(Crossover): 交叉算子將被選中的兩個個體的基因鏈按概率p

30、c進行交叉，生成兩個新的個體，交叉位置是隨機的。其中Pc是一個系統(tǒng)參數。 (3)變異算子(Mutation): 變異算子將新個體的基因鏈的各位按概率pm進行變異，對二值基因鏈(0,1編碼)來說即是取反。 上述各種算子的實現是多種多樣的，而且許多新的算子正不斷提出，以改進GA的某些性能。系統(tǒng)參數(個體數n,基因鏈長度l,交叉概率Pc,變異概率Pm等)對算法的收斂速度及結果有很大的影響，應視具體問題選取不同的值。,2021/1/1,華中農業(yè)大學理學院,50,TPopulation類包含兩個重要過程： FillFitness:評價函數，對每個個體進行解碼(decode)并計算出其適應度值，具體操作在

31、用戶類中實現。 Statistic:對當前群體進行統(tǒng)計，如求總適應度sumfitness、平均適應度average、最好個體fmax、最壞個體fmin等。 TSGA類在TPopulation類的基礎上派生，以GA的系統(tǒng)參數為構造函數的參數，它有4個重要的成員函數： Select:選擇算子，基本選擇策略采用輪盤賭模型。輪盤經任意旋轉停止后指針所指向區(qū)域被選中，所以fi值大的被選中的概率就大。 Crossover:交叉算子，以概率Pc在兩基因鏈上的隨機位置交換子串。 Mutation:變異算子，以概率Pm對基因鏈上每一個基因進行隨機干擾(取反)。 Generate: 產生下代，包括了評價、統(tǒng)計、選

32、擇、交叉、變異等全部過程，每運行一 次，產生新的一代。,2021/1/1,華中農業(yè)大學理學院,51,二、遺傳算法的主要特征,遺傳算法目的是獲得“最好解”，可以把這種任務看成是一個優(yōu)化過程。 對于小空間，經典的窮舉法就足夠了； 而對大空間，則需要使用特殊的人工智能技術。 遺傳算法(Genetic Algorithm)是人工智能技術中的一種，是一類模擬生物進化過程而產生的,由選擇算子、雜交算子和變異算子三個基本算子組成的全局尋優(yōu)算法。 過程： 它從一個初始族出發(fā)，由選擇算子選出性狀好的父本，由雜交算子進行雜交運算，變異算子進行少許變異，在一定概率規(guī)則控制下隨機搜索模型空間。一代代進化，直到最終解族

33、對應的誤差泛函值達到設定的要求。,2021/1/1,華中農業(yè)大學理學院,52,遺傳算法的結構： Procedure Genetic Algorithm begin t=0 initialize p(t) evaluate p(t) while (not termination-condition) do begin t=t+1 select p(t) from p(t-1) alter p(t) evaluate p(t) end end,二、遺傳算法的主要特征：,圖1遺傳算法的結構：,2021/1/1,華中農業(yè)大學理學院,53,在第次迭代，遺傳算法維持一個潛在解的群體,每個解,用其“適應值”

34、評價。然后通過選擇更合適個體（t+1 次迭代）形成一個新的群體。新的群體的成員通過雜交和變異進行變換，形成新的解。雜交組合了兩個親體染色體（即待求參數的二進制編碼串）的特征，通過交換父代相應的片斷形成了兩個相似的后代。,例如父代染色體為,和,在第二個基因后雜交，產生的后代為,和,二、遺傳算法的主要特征：,2021/1/1,華中農業(yè)大學理學院,54,雜交算子的目的是在不同潛在解之間進行信息交換。變異是通過用一個等于變異率的概率隨機地改變被選擇染色體上的一個或多個基因（染色體中的一個二進制位）。變異算子的意圖是向群體引入一些額外的變化性。,二、遺傳算法的主要特征：,2021/1/1,華中農業(yè)大學理

35、學院,55,遺傳算法的特點： (1).它不是直接作用于參變量集上，而是作用于參變量的某種編碼形成的數字串上。 (2).它不是從單個點，而是從一個解族開始搜索解空間，與傳統(tǒng)“點對點”式的搜索方法不同。 (3).它僅僅利用適應值信息評估個體的優(yōu)劣，無須求導數或其它輔助信息。 (4).它利用概率轉移規(guī)則，而非確定性規(guī)則。,優(yōu)勢： (1). 不容易陷入局部極值，能以很大的概率找到全局最優(yōu)解。 (2). 由于其固有的并行性，適合于大規(guī)模并行計算。,2021/1/1,華中農業(yè)大學理學院,56,三、遺傳算法的運行步驟：,1. 一般性描述： 不失一般性，考慮求最大值的問題。問題：,2021/1/1,華中農業(yè)大

36、學理學院,57,1) 編碼和解碼 2)產生潛在解初始群體 3)根據適應值評價解的適應程度并據此生成新群體 4)雜交(crossover)和變異(mutation)決定新群體的性狀 隨著選擇、雜交和變異的進行，新群體就為下一次的評價做好了準備。該評價是用來為下一次選擇過程建立概率分布的，即建立一個根據當前適應值構造寬距的輪盤。其它的部分只是上述步驟的循環(huán)重復,三、遺傳算法的運行步驟：,2021/1/1,華中農業(yè)大學理學院,58,1) 編碼和解碼,2021/1/1,華中農業(yè)大學理學院,59,2)產生潛在解初始群體,簡單地以位的方式隨機地設定pop_size個染色體。如果確實有一些關于最優(yōu)分布的知識

37、，可以使用這些信息來設定初始潛在解的集合。,2021/1/1,華中農業(yè)大學理學院,60,3)根據適應值評價解的適應程度并據此生成新群體,通常使用一個根據適應值調節(jié)刻度寬度的輪盤。按照如下方法構造輪盤（假設這里的適應值時正值，否則可以使用一些比例機制調整）：,2021/1/1,華中農業(yè)大學理學院,61,2021/1/1,華中農業(yè)大學理學院,62,4)雜交(crossover)和變異(mutation)決定新群體的性狀,2021/1/1,華中農業(yè)大學理學院,63,隨著選擇、雜交和變異的進行，新群體就為下一次的評價做好了準備。該評價是用來為下一次選擇過程建立概率分布的，即建立一個根據當前適應值構造寬

38、距的輪盤。其它的部分只是上述步驟的循環(huán)重復，見圖1。,2021/1/1,華中農業(yè)大學理學院,64,例1：,2021/1/1,華中農業(yè)大學理學院,65,1)解碼和解碼：,變量的定義域長度為15.1，所要求的精度意味著區(qū)間-3.0, 12.1至少要被分為15.110000個等距區(qū)間。由于，因此染色體的第一部分需要18位。,2021/1/1,華中農業(yè)大學理學院,66,(010001001011010000111110010100010) 的前18位010001001011010000表示,2021/1/1,華中農業(yè)大學理學院,67,2) 產生潛在解初始群體：,2021/1/1,華中農業(yè)大學理學院,6

39、8,3)根據適應值評價解的適應程度并據此生成新群體：,2021/1/1,華中農業(yè)大學理學院,69,3)根據適應值評價解的適應程度并據此生成新群體：,2021/1/1,華中農業(yè)大學理學院,70,2021/1/1,華中農業(yè)大學理學院,71,4) 雜交(crossover)和變異(mutation)決定新群體的性狀：,2021/1/1,華中農業(yè)大學理學院,72,2021/1/1,華中農業(yè)大學理學院,73,2021/1/1,華中農業(yè)大學理學院,74,群體的當前版本為：,2021/1/1,華中農業(yè)大學理學院,75,2021/1/1,華中農業(yè)大學理學院,76,表2.2把染色體中的位號翻譯成染色體中的位數：

40、,2021/1/1,華中農業(yè)大學理學院,77,2021/1/1,華中農業(yè)大學理學院,78,2021/1/1,華中農業(yè)大學理學院,79,2021/1/1,華中農業(yè)大學理學院,80,但是，仔細檢查整個運行過程，可以發(fā)現早期代中的某些染色體的適應值要好于經過1000代后的最好染色體值35.47938。例如，第396代中的最好染色體的值為38.827553。這是由于取樣的隨機誤差造成的。跟蹤進化過程中的最好個體是容易的。在遺傳算法的實現中，通常在一獨立出來的位置保存“曾經最好”的個體；用這種方法，算法將報告整個過程的最好值，而不只是最終群體的最好值。,2021/1/1,華中農業(yè)大學理學院,81,例2：

41、,為四個連鎖飯店尋找最好的經營決策，其中一個經營飯店的決策包括要做出以下三項決定： （1）價格 漢堡包的價格應該定在50美分還是1美元？ （2）飲料 和漢堡包一起供應的應該是酒還是可樂？ （3）服務速度 飯店應該提供慢的還是快的服務？ 目的：找到這三個決定的組合以產生最高的利潤。 上述問題的表示方案： 串長 (l3）字母表規(guī)模（ k2） 映射 共有8種表示方案 遺傳算法解這個問題的第一步就是選取一個適當的表示方案。,2021/1/1,華中農業(yè)大學理學院,82,表1 飯店問題的表示方案（其中的4個）,群體規(guī)模N4,2021/1/1,華中農業(yè)大學理學院,83,表2 初始群體中經營決策的適應值,一個

42、簡單的遺傳算法由復制、雜交、變異三個算子組成,2021/1/1,華中農業(yè)大學理學院,84,表3 使用復制算子后產生的交配池,1.復制算子：采用賭盤選擇,2021/1/1,華中農業(yè)大學理學院,85,2.雜交算子：采用一點雜交,作用過程：a）產生一個在1到l1之間的隨機數i b）配對的兩個串相互對應的交換從i1到l的位段,例如：從交配池中選擇編號為1和2的串進行配對，且雜交點選在2（用分隔符|表示），雜交算子作用的結果為： 01 | 1 010 11 | 0 111,對交配池中指定百分比的個體應用雜交算子，假設雜交概率pc50，交配池中余下的50個體僅進行復制運算，即復制概率pr50。,2021/

43、1/1,華中農業(yè)大學理學院,86,表4 使用復制和雜交算子的作用結果,遺傳算法利用復制和雜交算子可以產生具有更高平均適應值和更好個體的群體,2021/1/1,華中農業(yè)大學理學院,87,3.變異算子：以一個很小的概率pm隨機改變染色體串上的某些位。 對于二進制串，就是將相應位上的0變?yōu)?或將1變?yōu)?。,例如：選交配池中編號為4的串進行變異，且變異點在2，則 010 000,變異算子相對而言，是次要算子，但在恢復群體中失去的多樣性方面具有潛在的作用。,2021/1/1,華中農業(yè)大學理學院,88,如圖所示：該函數有多個局部極大點。,2021/1/1,華中農業(yè)大學理學院,89,構造過程：第一步：確定決

44、策變量及其約束條件。,第三步：確定編碼方法。用長度為22位的二進制編碼串來分別表示決策變量x。,2021/1/1,華中農業(yè)大學理學院,90,22位二進制編碼串可以表示從0到4194303之間的4194304個不同的數，故將x的定義域離散化為4194304個均等的區(qū)間，包括兩個端點在內共有4194304個不同的離散點。從離散點0到離散點9，依次讓它們分別對應于從0000000000000000000000(0)到1111111111111111111111(41943043)之間的二進制編碼。這就構成了這個函數優(yōu)化問題的染色體編碼方法。 例如X：0000000000001101110001 就表

45、示一個個體的基因型。,2021/1/1,華中農業(yè)大學理學院,91,第四步：確定解碼方法。,解碼時將22位長的二進制編碼轉換為對應的十進制整數代碼，記為y。依據前述個體編碼方法相對定義域的離散化方法可知，將代碼y轉換為變量x的解碼公式為：,例如，對前述個體X：00000000001101110001 它由這樣的下列代碼所組成：y= 881經上式的解碼處理后，得到：x = 0.001890421x=,2021/1/1,華中農業(yè)大學理學院,92,第五步：確定個體評價方法。,由于目標函數的取值可正可負，并且優(yōu)化目標是求函數的最大值，故這里可將個體的適應度取為每次迭代的最小值的絕對值加上目標函數值，即有

46、：,第六步：設計遺傳算子。選擇運算使用比例選擇算子；交叉運算使用單點交叉算子；變異運算使用基本位變異算子。,2021/1/1,華中農業(yè)大學理學院,93,第七步：確定遺傳算法的運行參數。,對于本例，設定基本遺傳算法的運行參數如下： 群體大小: N50 終止代數: ger100 交叉概率：pc0.65 變異概率：pm0.05,2021/1/1,華中農業(yè)大學理學院,94,2021/1/1,華中農業(yè)大學理學院,95,2021/1/1,華中農業(yè)大學理學院,96,由該組圖我們可以看出，隨著進化過程的進行，群體中適應度較低的一些個體被逐漸淘汰掉，而適應度較高的一些個體會越來越多并且它們都集中在所求問題的最優(yōu)

47、點附近，從而最終就可搜索到問題的最優(yōu)解。,2021/1/1,華中農業(yè)大學理學院,97,小結,遺傳算法描述了從第0代產生第1代的過程，然后遺傳算法迭代地執(zhí)行這個過程，直到滿足某個停止準則。在每一代中，算法首先計算群體中每個個體地適應值，然后利用適應值信息，遺傳算法分別以概率pc 、 pr 和pm 執(zhí)行雜交、復制和變異操作，從而產生新的群體。 應用遺傳算法求解問題需完成四個主要步驟： 1.確定表示方案 2.確定適應值度量 3.確定控制算法的參數和變量 4.確定指定結果的方法和停止運行的準則,2021/1/1,華中農業(yè)大學理學院,98,四、基本遺傳算法的構成要素,1.染色體編碼方法 最常用的是二進制

48、編碼，對于離散性變量直接編碼，對于連續(xù)性變量先離散化后再編碼 2.適應度函數 評估函數用來評估一個染色體的優(yōu)劣的絕對值 適應度函數評估一個染色體相對整個群體的優(yōu)劣的相對值的大小,2021/1/1,華中農業(yè)大學理學院,99,基本遺傳算法一般采用下面兩種方法之一將目標函數值f(x)變換為個體的適應度F(x)：,2021/1/1,華中農業(yè)大學理學院,100,其中，Cmax是一個適當地相對比較大的數，它可用下面幾種方法求得： 預先指定的一個較大的數。 進化到當前代為止的最大目標函數值。 當前代或最近幾代群體中的最大目標函數值。,2021/1/1,華中農業(yè)大學理學院,101,3.遺傳算子復制算子、交叉算

49、子、變異算子,2021/1/1,華中農業(yè)大學理學院,102,4.基本遺傳算法運行參數 N：群體大小，即群體中所含個體的數量，一般取20100 T：遺傳算法的終止進化代數，一般取100500 pc：雜交概率，一般取0.40.99 pm ：變異概率，一般取0.00010.1 pr ：復制概率,2021/1/1,華中農業(yè)大學理學院,103,四、基本遺傳算法的一般框架,算法過程： 1.隨機產生一個由確定長度的特征串組成的初始群體 2.對串群體迭代地執(zhí)行下面的步（i）和步（ii），直到滿足停止準則： （i）計算群體中每個個體的適應值 （ii）應用復制、雜交和變異算子產生下一代群體 3.把在任一代中出現地

50、最好地個體串指定為遺傳算法的執(zhí)行結果，這個結果可以表示問題的一個解（或近似解）,2021/1/1,華中農業(yè)大學理學院,104,2021/1/1,華中農業(yè)大學理學院,105,五、遺傳算法的數學理論,幾個相關的定義： 1、模式是一個相同的構形，它描述的是一個串的子集，這個集合中串之間在某些位上相同。 例如，添加符號*表示不確定字母，即0或1，考慮串長為7的模式H*11*0*，則串A0111000是模式H的一個表示，對于基數為k的字母表，每一個串有（k1）l 個模式。 2、模式的階出現在模式中確定位置的數目。在二進制中，一個模式的階就是所有的1或0的數目。 例如，模式H*11*0*的階為3 3、模式

51、的定義長度模式中第一個確定位置與最后一個確定位置之間的距離 例如，模式H*11*0*的定義長度r523,2021/1/1,華中農業(yè)大學理學院,106,定理1（模式定理）：具有短的定義長度、低階并且適應值在群體平均適應值以上的模式在遺傳算法迭代過程中將按指數增長率被采樣。 模式定理揭示了遺傳算法為什么有效！ 定理2（隱并行性）：ns n3, 其中 ns 有效模式數 n群體規(guī)模 該定理表明，每一代中除了僅對n個串的處理外，遺傳算法實際上處理大約O（n3）個模式，從而每代只執(zhí)行與群體規(guī)模成比例的計算量，就可以同時收到并行地對大約O（n3）個模式進行有效處理的目的，并且無須額外的存儲。 定理3（積木塊假設）：低階、短距、高平均適應值的模式（積木塊）在遺傳算子的作用下，相互結合，能生成高階、長距、高平均適應值的模式，