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