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