人工智能-遺傳算法(ppt72頁)(編輯修改稿)

　

【文章內容簡介】 本特征 30 （ 3）全局最優解 遺傳算法由于采用交換、突變等操作，產生新的個體，擴大了搜索范圍，使得搜索得到的優化結果是全局最優解而不是局部最優解。 （ 4）黑箱式結構 遺傳算法根據所解決問題的特性，進行編碼和選擇適應度。一旦完成字符串和適應度的表達，其余的復制、交換、突變等操作都可按常規手續執行。個體的編碼如同輸入，適應度如同輸出。因此遺傳算法從某種意義上講是一種只考慮輸入與輸出關系的黑箱問題。 遺傳算法的基本特征 31 （ 5）通用性強 傳統的優化算法，需要將所解決的問題用 數學式子 表示，常常要求解該數學函數的一階導數或二階導數。采用遺傳算法，只用編碼及適應度表示問題，并不要求明確的數學方程及導數表達式。因此，遺傳算法通用性強，可應用于離散問題及函數關系不明確的復雜問題，有人稱遺傳算法是一種 框架型算法 ，它只有一些簡單的原則要求，在實施過程中可以賦予更多的含義。 （ 6）并行式算法 遺傳算法是從初始群體出發，經過復制、交換、突變等操作，產生一組新的群體。每次迭代計算，都是針對一組個體同時進行，而不是針對某個個體進行。因此，盡管遺傳算法是一種搜索算法，但是由于采用這種并行機理，搜索速度很高。這種并行式計算是遺傳算法的一個重要特征。 遺傳算法的基本特征 32 遺傳算法受生物進化與遺傳的啟發，形成一種獨特的優化方式，因此，遺傳算法的運算原則常常與生物進化及遺傳學說吻合，而且其術語也常常仿效生物學的術語。 遺傳算法的運算基礎是字符串，它就相當于生物學中的染色體。 字符串由一系列字符組成，每個字符都有特定的含義，反應所解決問題的某個特征，這就相當于基因，即染色體 DNA的片段。 在進行交換、突變操作時，遺傳算法只涉及到字符串某些片段，這就類似于遺傳過程只涉及某些基因而不是整個染色體。 遺傳算法的生物學含義 33 遺傳學很注重 等位基因 ，它是反映生物某一形態所對應的基因。在遺傳算法的字符串中，每個字符都反映問題的某一特性，這也就相當于等位基因，至于等位基因的位置，也就相當于該字符在字符串中的位置。 在遺傳學中，雜交產生的子代里顯現出親本的性狀，稱作顯性性狀，未顯現出來的親本性狀叫作隱性性狀。控制顯性性狀的基因是 顯性基因 ，用大寫英文字母表示。控制隱性性狀的基因是隱性基因 ，用小寫英文字母表示。在遺傳算法中，模仿這種大、小字母表達方式，對顯性基因和隱性基因采取不同的操作。 遺傳算法的生物學含義 34 生物學術語在遺傳算法中的對應意義如下表。 序號 生物學 遺傳算法 1 2 3 4 5 6 染色體（ Chromosome） 基因（ Gene） 等位基因（ Allele） 基因位置（ Locus） 基因型（ Genotype） 表現型（ Phenotype） 字符串 字符 對應的字符 字符的位置 字符串結構 字符串含義 遺傳算法的生物學含義 35 根據前面所講的示例，可以看出遺傳算法的實施過程中包括編碼、產生群體、計算適應度、復制、交換、突變等操作。 遺傳算法的詳細流程如下圖。 遺傳算法的工作步驟 36 Gen：遺傳（迭代）的代次。表明遺傳算法反復執行的次數，即已產生群體的代次數目。 M：群體中擁有的個體數目。 i：已處理個體的累計數，當 i等于 M，表明這一代的個體已全部處理完畢，需要轉入下一代群體。 交叉率 Pc 就是參加交叉運算的染色體個數占全體染色體總數的比例，記為 Pc,取值范圍一般為 ～ 。 變異率 Pm 是指發生變異的基因位數所占全體染色體的基因總位數的比例，記為 Pm，取值范圍一般為 ～ 。 復制概率 Pt 用于控制復制與淘汰的個體數目。 Pc Pt Pm No No Yes Gen： =0 隨機產生初始群體 滿足終止條件 計算群體中各個體的適應度 i： =0 i： =M? 選擇遺傳算子及概率 根據適應度選擇兩個個體 i： =i+1 執行交換 將兩個交換結果添入新群體 i： =i+1 將復制結果添入新群體 執行復制 根據適應度選擇一個個體 將突變結果添入新群體 執行突變 Gen： =Gen+1 輸出結果 結束 Yes 37 概括地講，遺傳算法主要執行以下四步： （ 1） 隨機地建立由字符串組成的初始群體； （ 2） 計算各個體的適應度； （ 3） 根據遺傳概率，利用下述操作產生新群體： 1） 復制 。將已有的優良個體復制后添入新群體中，刪除劣 質個體； 2） 交換 。將選出的兩個個體進行交換，所產生的新個體添 入新群體中。 3） 突變 。隨機地改變某一個體的某個字符后添入新群體中。 （ 4） 反復執行（ 2）、（ 3）后，一旦達到終止條件， 選擇最佳個體作為遺傳算法的結果。 38 遺傳算法的工作對象是字符串，因此對字符串的編碼有兩點要求：一是字符串要反映所研究問題的性質；二是字符串的表達要便于計算處理。 遺傳算法關鍵問題 （ 1） 編碼 遺傳算法常常用二進制的 0/1字符編碼。當問題比較簡單，例如只描述高 /低、大 /小等布爾型性質時，每一位 0/1變量就代表一個性質。 例如，某事物只涉及到貴 /賤、大 /小及好 /壞時，我們可用三位 0/1字符表示，并規定第 1位字符代表貴 /賤，第 2位字符代表大 /小，第 3位字符代表好 /壞。如 111代表貴 大 好，而 100代表貴 小 好。 39 當問題的性質要用數值描述時，則編碼變成用二進制數表示十進制數。例如，用 4位 0/1字符串表示 1 ～ 16。 根據排列計算，長度（位數）為 L的 0/1字符串，可以表達 2*2*2‥ ‥ 2 = 2L 種情況。如果所描述性質的最小值不是 0時，即性質介于 Umin～ Umax之間，為了減小字符串長度，可以采用映射的方法，用 2L個二進制數表示 [ Umin， Umax ]。這時，令 L個 0表示 Umin ， L個 1 表示 Umax ，其中 L大小取決于（ Umax — Umin ），其余的數則用線性插值決定。例如，對于 [ 16， 31 ]的十進制數，我們可以用 4位二進制 0/1字符在 [ 0000， 1111 ]范圍內表示。 （ 1） 編碼 Umin 0…0 … Umax 1…1 40 對于兼有多種性質的問題，可以采用長字符串順序分別表示。例如，可選 25位 0/1字符串表示物體的體積、重量及顏色，其中前 10位數表示體積量，中間 10位數表示重量，后 5位數表示顏色。 在遺傳算法中，字符串的長度常常是固定的，以便按統一的方式執行操作。個別研究者采用不等長的字符串，這時就需要跟蹤記錄，經常調整操作方式，比較煩瑣。 從生物學角度看，編碼就相當于選擇遺傳物質，它是研究遺傳的基礎。同樣，在遺傳算法中編碼也是一項基礎性工作。 （ 1） 編碼 41 在遺傳算法中，衡量個體優劣的尺度是 適應度 。根據適應度的大小，決定某些個體是繁殖或是消亡。因此，適應度是驅動遺傳算法的動力。從生物學角度講，適應度相當于“生存競爭，適者生存”的生物生存能力，在遺傳過程中具有重要意義。 通常，