第十章遺傳算法第一節(jié)遺傳算法的根本概念遺傳算法（GeneticAlgorithms,簡稱GA）是人工智能的重要新分支,是基于達爾文進化論,在計算機上模擬生命進化機制而開展起來的一門新學(xué)科。它依據(jù)適者生存,優(yōu)勝劣汰等自然進化規(guī)則來進行搜索計算和問題求解。對許多用傳統(tǒng)數(shù)學(xué)難以解決或明顯失效的復(fù)雜問題,特別是優(yōu)化問題,GA提供了一個行之有效的新途徑,也為人工智能的研究帶來了新的生機。GA由美國J.H.Holland博士1975年提出,當時并沒有引起學(xué)術(shù)界的關(guān)注,因而開展比較緩慢。從八十年代中期開始,隨著人工智能的開展和計算機技術(shù)的進步,遺傳算法逐漸成熟,應(yīng)用日漸增多,不僅應(yīng)用于人工智能領(lǐng)域（如機器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)）,也開始在工業(yè)系統(tǒng),如操作,機械,土木,電カ工程中得到成功應(yīng)用,顯示出了誘人的前景。與此同時,GA也得到了國際學(xué)術(shù)界的普遍肯定。從1985年至今國際上已舉行了五屆遺傳算法和進化計算會議,第一本《進化計算》雜志1993年在MIT創(chuàng)刊,1994年IEEE神經(jīng)網(wǎng)絡(luò)匯刊出版了進化規(guī)劃理論及應(yīng)用專集,同年IEEE將神經(jīng)網(wǎng)絡(luò),模糊系統(tǒng),進化計算三個國際會議合并為94IEEE全球計算智能大會（WCCI）,會上發(fā)范表進化計算方面的文章材料255篇,引起了國際學(xué)術(shù)界的廣泛關(guān)注。目前,GA已在組合優(yōu)化問題求解,自適應(yīng)操作,程序自動生成,機器學(xué)習(xí),神經(jīng)網(wǎng)絡(luò)訓(xùn)練,人工生命研究,經(jīng)濟預(yù)測等領(lǐng)域取得了令人著目的應(yīng)用成果,GA也成為當前人工智能及其應(yīng)用的熱門課題。第二節(jié)簡單遺傳算法GA是基于自然選擇,在計算機上模擬生物進化機制的尋優(yōu)搜索算法。在自然界的演化過程中,生物體通過遺傳（傳種接代,后代與父輩非常相象）、變異（后代與父輩又不完全相象）來適應(yīng)外界環(huán)境,一代又一代地優(yōu)勝劣汰,開展進化。GA則模擬了上述進化現(xiàn)象。它把搜索空間（欲求解問題的解空間）映射為遺傳空間,即把每ー個可能的解編碼為ー個向量（二進制或十進制數(shù)字串）,稱為ー個染色體（chromosome,或個體）,向量的每ー個元素稱為基因（genes）〇全部染色體組成群體（population,或集團）。并按預(yù)定的目標函數(shù)（或某種評價指標,如商業(yè)經(jīng)營中的利潤,工程工程中的最小費用等）對每個染色體進行評價,依據(jù)其結(jié)果給出一個適應(yīng)度的值。算法開始時先隨機地產(chǎn)生一些染色體（欲求解問題的候選解）,計算其適應(yīng)度,依據(jù)適應(yīng)度對諸染色體進行選擇、交換、變異等遺傳操作,剔除適應(yīng)度低（性能不佳）的染色體,留下適應(yīng)度高（性能優(yōu)良）的染色體,從而得到新的群體。由于新群體的成員是上一代群體的優(yōu)秀者,繼承了上一代的優(yōu)良性態(tài),因而明顯優(yōu)于上一代。GA就這樣反復(fù)迭代,向著更優(yōu)解的方向進化,直至滿足某種預(yù)定的優(yōu)化指標。上述GA的工作過程可用圖10-I簡要描述。問題解答空間圖［レL31マ抒メ厶丄Iトノ習(xí)ヾとEZJヽ意圖簡單遺傳算法的三個根本運算是選擇,交換,變異,下面詳細介紹。1.選擇運算選擇運算又稱為繁殖,再生,或復(fù)制運算,用于模擬生物界去劣存優(yōu)的自然選擇現(xiàn)象。它從舊種群中選擇出適應(yīng)性強的某些染色體,放入匹配集(緩沖區(qū)),為染色體交換和變異運算產(chǎn)生新種群作打算。適應(yīng)度越高的染色體被選擇的可能性越大,其遺傳基因在下一代群體中的分布就越廣,其子孫在下一代出現(xiàn)的數(shù)量就越多。有多種選擇方法,使用比較普遍的ー種是適應(yīng)度比例法,簡述如下:適應(yīng)度比例法又稱為輪轉(zhuǎn)法,它把種群中全部染色體適應(yīng)度的總和看作一個輪子的圓周,而每個染色體按其適應(yīng)度在總和中所占的比例占據(jù)輪子的ー個扇區(qū)。每次染色體的選擇可看作輪子的一次隨機轉(zhuǎn)動,它轉(zhuǎn)到那個扇區(qū)停下來,那個扇區(qū)對應(yīng)的染色體就被選中。盡管這種選擇方法是隨機的,但它與各染色體適應(yīng)度成比例。這是因為適應(yīng)度大的染色體占據(jù)輪子扇區(qū)面積大,被選中的概率就高(時機多),適應(yīng)度小的染色體占的扇區(qū)小,被選中的概率就低。某ー染色體被選中的概率(選擇概率)為Pc=f(Xc)/Ef(Xi)式中Xi為種群中第i個染色體對應(yīng)的數(shù)字串,f(xi)是第i個染色體的適應(yīng)度值,Zf(Xi)是種群中全部染色體的適應(yīng)度值之和。用適應(yīng)度比例法進行選擇時,首先計算每個染色體的適應(yīng)度,然后按比例于各染色體適應(yīng)度的概率選擇進入交換(匹配)集的染色體,其具體步驟如下:(1)計算每個染色體的適應(yīng)度值f(Xi)；(2)累加全部染色體的適應(yīng)度值,得最終累加值SUM=Ef(x。,記錄對應(yīng)于每個染色體的中間累加值S-mid;(3)產(chǎn)生一個隨機數(shù)N, 0<N<SUM;(4)選擇其對應(yīng)的中間累加值S-mid2N的第一個染色體進入交換集。(5)重復(fù)(3),(4),直到交換集中包含足夠多的染色體數(shù)字串為止。重復(fù)上述過程,直到交換集中包含足夠多的染色體為止。顯然,此法要求染色體的適應(yīng)度值應(yīng)為正值。例,某種群包含10個染色體,按適應(yīng)度比例法選擇進入交換集的過程示于范表10-1及范表10-2〇范表10-1染色體編號12345678910適應(yīng)度8217721211737選擇概率0.10.020.220.090.020.160.140.090.030.09適應(yīng)度累加值8102734364859666976范表10-2隨機數(shù)2349 76131 2757所選染色體號3 7 10 3 1 3 7由這兩個范表格可以看到,3號染色體的選擇概率X,被選中的次數(shù)最多,其它選擇概率較低的染色體被選中的次數(shù)就少。當然,用適應(yīng)度比例法進行選擇時,性能最壞的染色體也可能被選擇，但概率極小,當種群長度較大時,這種情況可以忽略不計。.交換復(fù)制操作雖然能夠從舊種群中選擇出優(yōu)秀者,但不能制造新的染色體,因此,遺傳算法的開創(chuàng)者提出了交換操作。它模擬生物進化過程中的繁殖現(xiàn)象,通過兩個染色體的交換組合,來產(chǎn)生新的優(yōu)良品種,即:在匹配集中任選兩個染色體（稱為雙親的染色體）;隨機選擇一點或多點交換點位置J（0<J<L,L是染色體數(shù)字串的長度）;交換雙親染色體交換點右邊的局部,即可得到兩個新的（下一代）染色體數(shù)字串。也就是說,交換操作能夠制造新的染色體（子孫染色體）,從而同意測試在搜索空間中的新點。交換也范表達了自然界中信息交換的思想。例如,從匹配集中取出的ー對染色體為:染色體A110101110染色體B010111001隨機產(chǎn)生的一點交換位置是5,交換染色體A,B中第5位右邊的局部ーー110和001,則得兩個下一代（子孫）染色體數(shù)字串:A,11010001,B'OlOllllOo.變異變異運算用來模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變,它以很小的概率隨機地改變遺傳基因（范表示染色體的符號串的某一位）的值。在染色體以二進制編碼的系統(tǒng)中,它隨機地將染色體的某一個基因由1變成〇,或由〇變成1〇假設(shè)只有選擇和交換,而沒有變異操作,則無法在初始基因組合以外的空間進行搜索,使進化過程的早期就陷入局部解而中止進化過程,從而使解的質(zhì)量受到很大限制。通過變異操作,可確保群體中遺傳基因類型的多樣性,以使搜索能在盡可能大的空間中進行,預(yù)防喪失在搜索中有用的遺傳信息而陷入局部解,獲得質(zhì)量較高的優(yōu)化解答。例1:計算機公司的經(jīng)營策略優(yōu)化問題。ー個計算機公司追求的目標是X的利潤,為達此目標,必須選擇適當?shù)慕?jīng)營策略。ー種可能的策略是對以下三個問題作出決策:.每臺PC計算機的價格定為7000元（低價）還是10000元（高價）；.與PC機配套的免費軟件是Windows95還是MSDOS;.提供快速技術(shù)效勞（對用戶的效勞請求馬上響應(yīng)）,還是慢速排隊效勞;下面用遺傳算法來解決這個決策優(yōu)化問題。（1）把問題的可能解范表示為染色體數(shù)字串。因為有三個決策變量,其取值為是或否,可用1或〇來范表示,于是,可用三位的二進制數(shù)字范表征一種可能的經(jīng)營策略,解的搜索空間為23=8,即共有8種經(jīng)營策略可供選擇,范表10-3示出了其中計算機公司經(jīng)理已知的4種經(jīng)營策略（初始解答）。范表中數(shù)字串的第一位取0范表示高格,1范表示低價;第二位取0范表示配套Windows95,l范表示配套MSDOS;第三位取0范表示排隊慢速技術(shù)效勞,1范表示快速技術(shù)效勞。范表10-3序號價格配套軟件效勞速度染色體數(shù)字串

1MSDOSOil2Windows950013MSDOSno4Windows95010(2)求各染色體的適應(yīng)度。在這個問題中,ー個染色體的適應(yīng)度恰好是其二進數(shù)字串等價的十進制數(shù),也就是對應(yīng)的經(jīng)營策略的利潤(總營業(yè)額的百分數(shù))。范表!0-4第0代種群的適應(yīng)度序號i染色體串X1適應(yīng)度f(xi)10113200113110640102適應(yīng)度總和12最壞適應(yīng)度1最好適應(yīng)度6平均適應(yīng)度3(3)選擇進入交換集的染色體交換集又稱為匹配池,它實際上是一片內(nèi)存緩沖區(qū),用來存儲欲參加交換的染色體。由范表10-4可知,全部染色體串適應(yīng)度的總和是12,串110的適應(yīng)度是6,占適應(yīng)度總和的1/2,也就是串110被選中的時機有兩次,其概率為!/2;串011,001,010被選中的概率分別為3ハ2=1/4,1/12,2ハ2=1/6。按前述適應(yīng)度比例法,選擇進入交換集的染色體串及其適應(yīng)度情況如范表10-5所示。范表10-5 第0代種群的適應(yīng)度序號i交換集中的染色體串xi適應(yīng)度f(xi)10113211063110640102適應(yīng)度總和17最壞適應(yīng)度2最好適應(yīng)度平均適應(yīng)度 4.25由范表10-5可見,選擇操作的作用是改進了種群的平均適應(yīng)度,使其由原來的3提高到了4.25,最壞適應(yīng)度由原來的1改進為2,性能最差的染色體己從種群中刪除。但是,選擇不能制造新的染色體,為了改進這個缺點,尋找搜索空間內(nèi)的新的檢測點,須進行交換操作。(4)交換操作設(shè)采納單點交換,隨機產(chǎn)生的交換點是2,,從交換集中任取ー對染色體011和110,互換它們的第三位,得子孫染色體串010和111,其中111是交換操作制造的新的染色體。因為本例中交換概率為0.5,交換集中剩下二個染色體不再參加交換,而與交換后得到的子孫ー起作為下一代種群的成員。由此得到第一次交換操作后第一代種群,如范表10-6所示。范表10-6第1代種群的適應(yīng)度序號i染色體串Xi適應(yīng)度f(Xi)111172 01023 11064 0102適應(yīng)度總和17最壞適應(yīng)度2最好適應(yīng)度7平均適應(yīng)度4.25(5)評估新一代的種群的適應(yīng)度由范表!0-6可見,在新一代(第1代)種群中,最優(yōu)染色體適應(yīng)度由原來的6提高到了7,其對應(yīng)的代碼串是111,范表示ー種優(yōu)化的的經(jīng)營策略,即低價格銷售PC機,配套軟件范表示MSDOS,快速效勞,可獲X利潤7%(代碼串111的適應(yīng)度)。平均適應(yīng)度由原來的3提高到4.5,最壞適應(yīng)度由原來的1提高到2,整個種群的適應(yīng)度從總體上提高了,被優(yōu)化了。遺傳算法重復(fù)地執(zhí)行每一代的運算操作,產(chǎn)生新的一代,直到滿足某些終止標準或條件。在本例中,假定已知染色體數(shù)字串111代范表的是已知的最好利潤7%,則遺傳算法停止運行。編號初始種群X值適應(yīng)度(目標函數(shù))F(X)=X2選擇概率Fi/EF期望適應(yīng)度Fi/F實選染色體編號

101101131690.140.581211000245760.491.9723010008640.060.220410011193610.311.231和1170144平均2930.2511最大5760.491.972范表10-7(a)函數(shù)優(yōu)化運:程示意(1復(fù)制后交交換配對交換位置新種群X值F(X)=X2換集種群0110112401100121441100101411001256251110004211011277291010113210000162561754平均439最大729范表10-7(b)函數(shù)優(yōu)化過程示意(2)范表變了后,需對原稿第十章第7頁與范表10-7相關(guān)的文字做如下修改:“范表10-?左端第二列”, 改為“范表!0-7(a)左端第二列”；“范表10-7第5歹リ、第6歹!)",改為"范表10-7(衣第5歹!)、第6列"；“如范表10-7第7列所示",改為“范表10-7(a)第7列所示"“如范表10-7第8列所示",改為 “如范表10-7(b)第1列所示"。例2:函數(shù)優(yōu)化問題。設(shè)有函數(shù)f(x)=x2,求其在區(qū)間0,31]的最大值。下面用遺傳算法求解這ー問題的。(1)確定適當?shù)木幋a,把問題的可能解范表示為染色體數(shù)字串。。因為有一個決策變量x,其取值范圍為0,31],25=32,使用5位無符號二進制數(shù)組成染色體數(shù)字串,即可范表達變量x,以及問題的解答方案。(2)選擇初始種群。通過隨機的方法產(chǎn)生由4個染色體數(shù)字串組成的初始種群，見10,范表10-7左端第二列。范表10-7編初始適應(yīng)度選擇復(fù)制后新一Xf(x)=X2號種群X(目標概率交換集代群值值函數(shù))Ps=fi中的種體f(x)=/Zf,/f群101101 11691.0.140.5810110112401100121442110003576>.0.491.9721100101411001256253010002643.0.060.2011100042110112772941001143611.0.312110101132100001625681.2193適應(yīng)度總和エf11701441754平均適應(yīng)度Efi/n2930.2511439最大適應(yīng)度5760.491.972729(3)計算適應(yīng)度值及選擇概率。此問題中染色體的適應(yīng)度取為,即函數(shù)自身f(x)=X2o為了計算每個染色體的適應(yīng)度,先將染色體解碼,求出其二進數(shù)字串等價的十進制數(shù),即x值,再由x值計算目標函數(shù)f(x)=x2的值，作為適應(yīng)度值。在此根底上計算選擇概率Ps=fi/Lf,適應(yīng)度期望值fi/f,計算結(jié)果如范表范表10-7第5歹リ、第6列所示。(4)選擇進入交換集的染色體。按適應(yīng)度比例法,選擇進入交換集的染色體串,如范表10-7第8列所示?？梢?染色體1和4均被選擇了1次;染色體2被選擇了1次;染色體3沒有被選擇。也就是說染色體3被淘汰了。所選擇的4份染色體被送到交換集,打算參加交換。(5)交換染色體。首先對進入交換集的染色體進行隨機配對，此例中是染色體2和1配對,染色體4和3配對。接著隨機確定交換位置,結(jié)果是第1對染色體的交換位置是4,第2對染色體的交換位置是40經(jīng)交換操作后得到的新種群如范表10-7第!1列所示。變異。此例中變異概率取為0.001。由于種群中4個染色體總共有20位代碼,變異的期望值為20X0001=0.02位,這意味著本群體中無法進行變異。因此,此例中沒有進行變異操作。從范表10-7可以看出，雖然僅進行了一代遺傳操作，但種群適應(yīng)度的平均值及最大值卻比初始種群有了很大提高,平均值由293變到439,最大值由由576變到729。這說明隨著遺傳運算的進行，種群正向著優(yōu)化的方向開展。第三節(jié)圖式定理由前面的范表達可知,遺傳算法并不復(fù)雜,但卻展示了強大的信息處理能力,為什么它具有這種能力呢Holland提出的圖式定理(Schmata)在肯定程度上對此作了解釋,奠定了遺傳算法的理論根底。圖式是描述種群中任意染色體之間相似性的一維符號串。它定義在符號范表0,1,x之上,即由二進制數(shù)字〇』及通配符x任意組合而成。圖式中的01序列組成其固定局部,x序列范表示其變化局部,整個圖式范表示有意義的匹配模式。例如,圖式01X可和0100,0101,0110,0111中的任一個匹配。定義在0,1,x之上且長度為L的符號串所能組成的最大圖式數(shù)為(2+l)L,假設(shè)L=4,則它最多可組成27種圖式。含有N個染色體的種群可能包含的圖式數(shù)在2し?N.2L之間。遺傳算法正是利用種群中包含的眾多的圖式及其染色體符號串之間的相似性信息進行啟發(fā)式搜索和問題求解。已經(jīng)證明,在產(chǎn)生新一代的過程中,盡管遺傳算法只完成了正比于種群長度N的計算量,而處理的圖式數(shù)卻正比于種群長度N的三次方,這就是遺傳算法隱含的并行機制。用兩個參數(shù)描述圖式H,即:.定義長度6(H)ーーH左右兩端有定義位置之間的距離。.確定位數(shù)O(H)——H中有定義(非x)位的個數(shù)。例如,圖式1X1的定義長度是5-1=4,確定位數(shù)為2。種群中定義長度短,確定位數(shù)少,適應(yīng)度高的的圖式(符號串)稱為組塊(buildingblock)oGA的運算實際上是對組塊的操作。圖式定理可用來描述即圖式的組塊在多大程度上能保存到下一代,詳述如下:設(shè)m(H,t)范表示在第t代種群中存在的圖式H的數(shù)量,f(H)為包含H的染色體平均適應(yīng)度,FAV為種群中全部染色體的平均適應(yīng)度,則在經(jīng)過復(fù)制操作后,t+1代H的數(shù)量為:f(H)m(H,t+1)=m(H,t) (10.1)FAV由上式可知,在遺傳算法的運算過程中,下一代種群中H的數(shù)量正比于H所在染色體平均適應(yīng)度與種群平均適應(yīng)度的比值。假設(shè)某些染色體數(shù)字串的適應(yīng)度高于當前種群中平均適應(yīng)度時,這些數(shù)字串所包含的組塊在下一代數(shù)字串中出現(xiàn)的時機將增大,否則在下一代中組塊的出現(xiàn)將減少。運算中組塊的增減是并行進行的,這也范表現(xiàn)了遺傳算法隱含的并行性。經(jīng)過交換和變異操作后,圖式可能被破壞,因交換而破壞的概率為:Pc6(H)/L-1式中:L為染色體長度,Pc為交換的概率,即在經(jīng)選擇操作進入交換集的ー對染色體上發(fā)生交換的概率。因變異操作而破壞的概率為:O(H)Pm式中:Pm是變異概率,O(H)是確定位數(shù)。綜合上述商量,在GA運算過程中,經(jīng)過復(fù)制,交換和變異操作后,t+1代圖式H的數(shù)量為：f(H) 8(H)m(H,t+l)三m(H,t) 11一Pc -O(H)Pm] (10.2)FAV L-1式(10.2)也可用文字范表達為如下的圖式定理:在選擇、交換、變異運算的共同作用下,確定位數(shù)少、定義長度短、適應(yīng)度高于平均適應(yīng)度的圖式,在下肯定一代中以指數(shù)級增長。由此定理可知,下一代圖式(組塊)的數(shù)量正比于染色體數(shù)字串的適應(yīng)度。為了增加圖式,就應(yīng)盡可能減少交換和變異。但是,沒有交換和變異，就沒有種群的進化,就不能跳出可能陷入的局部最小地域。遺傳算法正是通過組塊的增減、組合等處理來存優(yōu)去劣,尋找最正確匹配點,進行高質(zhì)量的問題求解。第四節(jié)遺傳算法應(yīng)用中的ー些根本問題一.知識范表示(編碼)知識范表示要解決的問題是如何用方便有用的染色體串范表達欲求解問題的候選解,即如何編碼問題的候選解集。編碼的恰當與否對問題求解的質(zhì)量和速度有直接的影響。DavidE.Goldberg提出了編碼的兩條根本原理：(1)所編選碼方法應(yīng)能簡單地生成與求解問題有關(guān)實在定位數(shù)少、定義長度短的組塊。(2)所編選碼方法應(yīng)具有最小的字符集,自然地范表達欲求解的問題。原理(1)基于圖式定理,在實際編碼過程中較難掌握、使用,原理(2)則為實際編碼工作指出了方向。依據(jù)原理（2）,由于二進制編碼的字符集小,它比非二進制編碼要好。這也可從以下數(shù)學(xué)推演來說明。設(shè)某問題的解既可以用b位二進制數(shù),也可以用基數(shù)為K（K進制）的d位非二進制數(shù)編碼,為了保證這兩種編碼方法確定的解的數(shù)量相同,應(yīng)有:2b=kd二進制數(shù)編碼時每個碼位的取值有0,1,x三種情況,可得到的圖式數(shù)為 3boK進制數(shù)編碼時每個碼位的取值有k+1種情況,可得到的圖式數(shù)為 %+1ド。由于b>d（以十進制為例，b七3.33d,即,一位十進制數(shù)假設(shè)用二進制數(shù)范表達,約需3.3位），3レ>（k+1）?也就是說采納二進制數(shù)能比非二進制數(shù)提供更多的圖式。從其它一個角度看,由于實際問題中往往采納十進數(shù),用二進制數(shù)字串編碼時,需要把實際問題對應(yīng)的十進數(shù)變換為二進數(shù),使其數(shù)字長度擴大約3.3倍,因而對問題的描述更加細致,而且加大了搜索范圍,使之能夠以較大的概率收斂到全局解;其它,進行變異運算時工作量?。ㄖ挥?變1或1變0的操作）。所以,早期遺傳算法的編碼多采納二進制數(shù)。但是,采納二進制編碼也有一些缺點,如:編碼時需進行十進制數(shù)到二進制數(shù)變換,輸出結(jié)果時要解碼,進行二進制數(shù)到十進制數(shù)的變換;當二進數(shù)串很長時,交換操作計算量很大。也有人認為,使用二進制編碼效率低,可能會使遺傳算法的性能變壞。因此，近年來許多應(yīng)用系統(tǒng)己使用非二進制編碼,如Gencop系統(tǒng)采納的十進制數(shù)編碼,Samel系統(tǒng)采納的符號（字符串）編碼等。十進制串編碼與人的自然習(xí)慣比較吻合,不需要進行十ーーニ進制數(shù)之間的變換;由于數(shù)字串長度比二進制數(shù)短,交換運算計算量比二進制小;但變異運算卻比二進制編碼復(fù)雜（各個數(shù)字位變異的可能性有九種）?？傊?這兩種編碼方法各有優(yōu)缺點,到底采納那種方法最好,還須在理論上作進ー步的深刻探討，具體應(yīng)用時,可依據(jù)所求解問題的性質(zhì)靈敏決定。二.適應(yīng)度函數(shù)在一般的遺傳算法中,根本不用搜索空間的知識,而僅用適應(yīng)度函數(shù)來評價染色體的優(yōu)劣,并在此根底上進行各種遺傳操作,因此適應(yīng)度函數(shù)選擇是否適當對對算法的性能好壞影響很大,應(yīng)依據(jù)實際問題的特性具體確定。通常遺傳算法要求適應(yīng)度函數(shù)值非負,同時要求把待解優(yōu)化問題問題范表達為最大化問題,即目標函數(shù)的優(yōu)化方向?qū)?yīng)適應(yīng)度函數(shù)的增大方向,而一般的優(yōu)化問題并不肯定滿足這些條件。許多問題求解的目標是求目標函數(shù)（如本錢和費用）的極小值或者負值。有些情況下,如最優(yōu)排列順序問題的求解根本沒有目標函數(shù),而只有優(yōu)化要求。其它,假設(shè)種群規(guī)模不大,而在遺傳算法運行的開始階段,有少數(shù)適應(yīng)度極高的染色體,則按通常的選擇法,其選擇概率很高,這些染色體就會大量繁殖（復(fù)制）,在種群中占有很大比例,減少了種群的多樣性,導(dǎo)致算法過早收斂,可能喪失了一些最優(yōu)點,而陷入局部最優(yōu)點。在算法的結(jié)束階段,假設(shè)大多數(shù)染色體的適應(yīng)度都很高,使種群的X適應(yīng)度和平均適應(yīng)度相差不大,在平均適應(yīng)度附近和具有X適應(yīng)度的染色體被選中的時機根本相同,選擇就會成為近乎隨機的過程,適應(yīng)度的作用就會消逝,算法根本上限于停頓狀態(tài)。為了使遺傳算法能正常運行,同時保持種群內(nèi)染色體的多樣性,改善染色體適應(yīng)度值的分散程度,使之既要有差距,又不要差距過大,以利染色體之間的競爭,保證遺傳算法的良好性能,需對所選擇的適應(yīng)度函數(shù)進行某些數(shù)學(xué)變換。幾種常見的變換方法如下;.非負變換:把最小化優(yōu)化目標函數(shù)變換為以最大值為目標的適應(yīng)度函數(shù):Cmax-Z Z<Cmaxf（z）=式中Z=g(z)是適應(yīng)度函數(shù);Cmax是常數(shù),通常取為迄今為止進化過程中Z的最大值,或者為了保證f(Z)為正而預(yù)先設(shè)定的ー個與種群無關(guān)的常數(shù)。.線性變換:把優(yōu)化目標函數(shù)變換為適應(yīng)度函數(shù)的線性函數(shù)f(z)=az+ba,b是系數(shù),可依據(jù)具體問題的特點和期望的適應(yīng)值的分散程度在算法開始時確定或在每一代過程中重新計算。.裏變換:把優(yōu)化目標函數(shù)變換為適應(yīng)度函數(shù)的事函數(shù)f(z)=z"式中a是常數(shù),據(jù)經(jīng)驗確定。6口地5(1985)在機器視覺應(yīng)用中取。=1.005。?指數(shù)變換:把優(yōu)化目標函數(shù)變換為適應(yīng)度函數(shù)的指數(shù)函數(shù)f(z)=e式中B是常數(shù)。這種變換已用于機器人應(yīng)用中。三.操作參數(shù)和終止判據(jù)操作遺傳算法運行的主要參數(shù)是種群長度,染色體長度,遺傳操作概率(交換概率Pc和變異概率Pm等,這些參數(shù)的設(shè)定目前尚無統(tǒng)ー的理論指導(dǎo),主要依據(jù)具體問題和實驗確定。例如從維持種群中染色體的多樣性以預(yù)防陷入局部最優(yōu)方面考慮,種群長度越大越好，但這會增加計算量并對染色體間的競爭有不利影響,究竟選擇多長要依據(jù)軟硬件環(huán)境及具體問題確定。遺傳操作概率,特別是變異概率的選擇更為困難,選擇不當便會產(chǎn)生初始收斂而陷入局部最優(yōu)。一般地,選擇交換概率為0.6?0.9,變異概率為0.001?〇.01。由于遺傳算法沒有利用目標函數(shù)的梯度等信息,無法確定染色體在解空間中的位置,無法用常規(guī)數(shù)學(xué)方法確定遺傳算法是否收斂。有人已經(jīng)證明,在任意初始化、任意交換算子以及任意適應(yīng)度函數(shù)下,遺傳算法都不能收斂到全局最優(yōu)解。而通過改進遺傳算法,即不按比例法進行選擇,而是在選擇作用前(或后)保存當前所得最優(yōu)解，則能收斂至全局最優(yōu)解。但是收斂到最優(yōu)解的時間可能非常長。綜上所述,目前使用嚴格的數(shù)學(xué)方法判定遺傳算法的終止(收斂)條件還比較困難。因此，大多數(shù)應(yīng)用系統(tǒng)在實際中采納的主要是啟發(fā)式方法,如用以下條件來判定算法的終止:.是否到了預(yù)定算法的最大代數(shù);.是否找到某個較優(yōu)的染色體;.連續(xù)幾次迭代后得到的解群中最好解是否變化等。第五節(jié)高級遺傳算法(RGA)前面介紹的遺傳算法僅包含選擇,交換,變異三種遺傳子,其交換及變異概率是固定不變的,這樣的遺傳算法被稱為簡單(經(jīng)典)遺傳算法(SGA)。隨著遺傳算法研究的進展,人們在SGA的根底上提出了多種多樣的遺傳運算和選擇方法,從而形成了各種較為復(fù)雜的遺傳算法,稱為高級遺傳算法(RefineGeneticAlgorithms,簡稱為RGA),其根本特征是含有多種遺傳運算,交換及變異概率可變,因而具有更強的信息處理和自適應(yīng)能力。一.改進的選擇方法前面介紹了在SGA中使用的選擇方法一適應(yīng)度比例法,此法的優(yōu)點是完成簡單,缺點是選擇過程中最好的染色體可能在下一代產(chǎn)生不了子孫，可能發(fā)生隨機錯誤。下面介紹一些改進的選擇方法。?擇優(yōu)選擇法對群體中最優(yōu)秀(適應(yīng)度X)的染色體不進行交換和變異運算,而是直接把它們復(fù)制到下一代。以免交換和變異運算破壞種群中的優(yōu)秀解答。這種方法可加快局部搜索速度,但又可能因群體中優(yōu)秀染色體的急劇增加而導(dǎo)致搜索陷入局部最優(yōu)解。.確定性選擇法（期望值法）先計算群體中每個串的生存概率Ps=fi/Lfj1<j<n然后計算期望復(fù)制數(shù) ei=Ps.n式中n為群體中染色體的數(shù)目。依據(jù)ei值的整數(shù)局部給每個染色體串分配ー個復(fù)制數(shù),而按ei的小數(shù)局部對群體中的染色體串排序,最后按排列的大小順序選擇要保存到下一代的染色體串（子孫）。.有替換隨機剩余選擇法此選擇法的開始與確定性選擇法相同,在計算出期望復(fù)制數(shù)a值后,把整數(shù)局部賦給對應(yīng)染色體串，但其小數(shù)局部作為適應(yīng)度比例法的權(quán)，再按適應(yīng)度比例法進行選擇。?無替換隨機剩余選擇法此方法與有替換隨機剩余選擇法的區(qū)別在于:把ei值的小數(shù)局部看作概率,然后挑選生存概率等于ei的小數(shù)局部的其它染色體串作為復(fù)制的下一代的染色體串。例如,期望復(fù)制數(shù)等于1.5的ー個染色體會有兩個子孫,其中一個的a值等于1,另ー個0值等于0.5〇.順序選擇法依據(jù)各染色體適應(yīng)度值由大到小進行排序,再把預(yù)先設(shè)計的ー組選擇概率值按大小順序分配給各染色體,最后按選擇概率來確定要選擇的子孫。二.高級遺傳運算和算法.多點交換（Multiple-pointcrossover）交換運算的目的是把欲交換兩個染色體中性能優(yōu)良的組塊，遺傳到下一代某個染色體中,使之具有父輩染色體的優(yōu)良性能。但是,在某些情況下，一點交換運算無法到達這個目的。例如,設(shè)有兩個父輩染色體C1及C2:CJC2：00101101001設(shè)CI中含有性能優(yōu)良的組塊1x1及X0,C2中含有性能優(yōu)良的組塊1x1及1X1,假設(shè)對C1和C2進行一點交換運算,則無論交換點選在哪里,都可能使這些優(yōu)良組塊由于交換運算而被分割或丟棄，不能遺傳到下一代。而采納ニ點交換就可預(yù)防這個問題。設(shè)二個交換點選擇如以下圖（圖中I范表示交換點）：C1：1011100011100C2：0010111011001則ニ點交換運算就是交換C!與二交換點之間的局部,得到兩個子孫染色體C1’及C2'如下:Cl':1011111011100C2‘:0010100011001可見，子孫染色體CI中繼承了父輩染色體中性能優(yōu)良的組塊。從這個例子中也可以看到多點交換的優(yōu)越性。多點交換是對一點交換的拓廣,其操作與一點交換類似，也是先確定交換點數(shù)，隨機選擇交換點（位置）,再進行交換操作。假設(shè)取交換點數(shù)Nc為!,多點交換就變成了一點交換。假設(shè)Nc為偶數(shù)，可視染色體為ー個基因頭尾相接組成的環(huán),繞著環(huán)勻速前進,隨機地選擇交換點,再交換兩個父輩染色體中由交換點所確定的弧段。Nc為奇數(shù)時,取缺省交換點為染色體串的位置。（即染色體的頭部）,則它可等效為偶數(shù)點交換的情況。.一致交換（Uniformcrossover）這是多點交換的另ー種完成方法,由Syswerdal989年提出,它使用隨機產(chǎn)生的、長度與父輩染色體相同的二進制掩碼決定父輩染色體中交換的對應(yīng)位,掩碼為0的位交換，掩碼為1的位不交換（這個交換規(guī)則也可以相反,即掩碼為1的位交換）。例如:父輩染色體Si： 01100111父輩染色體S2： 11010001掩碼: 01101001子孫染色體Sr： 11110001子孫染色體S2': 01000111從原理上講,一致交換可生成任意新的組塊,有利于搜索到解空間中新的地域,但也有可能因進行一致交換而破壞父輩染色體中性能優(yōu)良組塊的遺傳。.局部匹配交換運算（PMX）這是Goldberg等人在求解TSP（旅游商）問題時提出的一種交換方法。它先用隨機均勻分布方法在欲交換兩父染色體串中各產(chǎn)生兩個交換點,把這兩點之間的地域定義為匹配地域,再對兩個匹配地域中的基因通過對應(yīng)位匹配置換。例如,兩父染色體串為:Ei, 984xO567x013210E2. 871x04103x02965符號“xO"范表示交換點。對染色體串Ei,其匹配地域中的三個元素“56T應(yīng)與染色體串E2匹配地域中的三個元素'‘4103"逐一匹配,即通過在Ei內(nèi)元素的置換,使匹配地域內(nèi)這三個元素換為“4103”。為此，Ei中的元素5與4,6與10,7與3分別換位,得到e「如下:E1':985XO4103xOl726對染色體串E2,其匹配地域中的三個元素“4103"應(yīng)與染色體串Ei匹配地域中的三個元素“567"逐一匹配，通過在E2內(nèi)元素的相應(yīng)置換，得到Eゴ如下:E2':831xO567x029104.重組運算（Reorderingoperators）在有些情況下,染色體的特性不僅與基因的位值有關(guān),而且與基因在染色體中的位置有關(guān),另一方面,某些性能優(yōu)良且緊密相關(guān)的基因在染色體中的位置相隔較遠,通過重新對染色體進行排列,就可把這些基因組合在ー起,以提高優(yōu)良組塊的在種群中的繁殖率。重組就是對染色體中的基因進行重新組合的運算。通常,重組運算可通過倒位操作來完成。進行倒位操作時,沿染色體長度方向選擇ニ點,把這ニ點之間的基因位置顛倒過來,形成一個新的染色體。例如,染色體C及其各基因的位置編號如下:C中各基因的位置編號: 12345678C： 01111010隨機選擇二個倒位點（以xO范表示）：12xO3456xO7801xOl110x010顛倒兩個豎線之間基因的位置,得到新染色體CC中各基因的位置編號: 12654378C'： 01011110三.混合遺傳算法由前面的介紹可知,遺傳算法在優(yōu)化方面具有有用性和穩(wěn)健性。但是,由于遺傳算法在局部搜索方面能的缺少,對特定領(lǐng)域問題來說,遺傳算法一般不是最成功的優(yōu)化算法。解決這個問題的途徑有兩條，ー是對遺傳算法進行進ー步的修改,二是把遺傳算法與現(xiàn)有優(yōu)化算法（如梯度下降法,黃金分割法,啟發(fā)式搜索算法,模擬退火法,列范表尋優(yōu)法等）相結(jié)合,相互取長補短。例如,組合優(yōu)化計算中貪欲（Greedy）算法是ー種有效的局部搜索方法,LouisAnthonyCOX等把GA與貪欲算法相結(jié)合，求解實際電信網(wǎng)絡(luò)的布線問題,取得很好的效果。DavidJ.Powell等混合使用遺傳算法、專家系統(tǒng)與數(shù)學(xué)優(yōu)化算法求解工程設(shè)計優(yōu)化問題,獲得成功。許多研究者的實踐說明，遺傳算法與現(xiàn)有優(yōu)化算法的結(jié)合,可產(chǎn)生比單獨使用遺傳算法或現(xiàn)有優(yōu)化算法更好,更有用的算法。Davis.Lawrence199I年在《遺傳算法手冊》中指出了遺傳算法與現(xiàn)有優(yōu)化算法（以下簡稱現(xiàn)有算法）結(jié)合的幾點原則,現(xiàn)歸納于下:.采納現(xiàn)有算法的編碼這樣做的好處有二個:一是嵌入在現(xiàn)有算法編碼中的領(lǐng)域?qū)＜抑R可以在混合遺傳算法中繼續(xù)使用;二是由于混合遺傳算法與現(xiàn)有優(yōu)化算法將在相同的環(huán)境下運行,使實際應(yīng)用人員感覺混合遺傳算法的使用比較自然。.吸取現(xiàn)有算法的精華.假設(shè)現(xiàn)有算法是快速的,則把它產(chǎn)生的解答集添加到混合遺傳算法的初始解群中，在此根底上進行各種遺傳運算。這樣，由混合遺傳算法產(chǎn)生的優(yōu)化解答至少不會比現(xiàn)有算法壬.假設(shè)現(xiàn)有算法對編碼進行ー系列變換,把這些變化合并到混合遺傳算法的運算操作中是非常有用的。.假設(shè)現(xiàn)有算法對其編碼的解釋是清楚的,可把其譯碼技術(shù)合并到混合遺傳算法的解碼及適應(yīng)度評價操作中，以節(jié)約譯碼計算時間。.改進遺傳運算混合現(xiàn)有算法的目標是具有遺傳算法和現(xiàn)有算法現(xiàn)有算法二者的優(yōu)點,但是,在現(xiàn)有算法的編碼方法（一般是實數(shù)編碼）后,遺傳算法原有的那些基于二進制編碼的運算（如交換，變異等）就可能不再適宜了,因此，必須依據(jù)所求解問題的性質(zhì)對原有的遺傳運算進行改進。四.并行遺傳算法GA固有的并行性使它比較適宜并行計算,但Holland經(jīng)典的GA是不能直接并行執(zhí)行的,這是因為在GA執(zhí)行時要考慮全局操作,如在選擇和重組（交換和變異）階段）,需要串行地執(zhí)行一些代碼,并迫使在處理機之間進行非局部的相互作用,因而需要很高的通訊開銷。為了克服經(jīng)典GA這方面的缺陷,人們提出了許多并行GA策略和模型,下面介紹兩種典型的并行GA模型。.鄰域（細粒度）模型（NeighbourhoodModel-NM）NM模型的出發(fā)點是開發(fā)ー個群體內(nèi)的并行性。在此模型中,只有單個群體在進化,每個個體被放置在平面網(wǎng)格的細胞內(nèi),選擇和重組只在網(wǎng)格中相鄰染色體之間進行。NM模型的根本算法如下:（1）適當定義欲求解問題的范表示;隨機產(chǎn)生候選解的群體,并把它劃分為N個子群體;定義各子群體的鄰域結(jié)構(gòu)。2)FOR每個子群體SPi(i=l,2,...N)REPEATP(0)=(Pl,...Pn)初始化WHILENOT(終止條件)P(t)->P(t+l) 選擇復(fù)制P(t+1)-P'(t+1) 交換P'(t+l)^P"(t+l)變異P(t+l)=P"(t+l)t=t+l(3)送最好的染色體到n個鄰域,接收鄰域最好的染色體來替換本群體中最壞的染色體。2.島嶼(粗粒度)模型(IslandModel-LM)LM模型的出發(fā)點是開發(fā)群體之間的并行性。在此模型中,把群體細分為假設(shè)干個相互隔離的子群體,分配到各個處理機;各處理機獨立地進行子群體的各種遺傳操作,并行地進化,并周期性地把最好的染色體遷移到相鄰的子群體中。LM模型的根本算法如下:(1)隨機產(chǎn)生候選解的初始群體;把每個染色體賦給網(wǎng)格的ー個元素;計算每個染色體的適應(yīng)度;(2)對網(wǎng)格的每個當前元素C執(zhí)行步驟3,4,5,6;(3)在賦給C及其鄰域的染色體中選擇ー個新染色體占據(jù)C;(4)在C的鄰域中隨機選擇ー個染色體,與C中的染色體以概率Pc進行交換(重新組合)；(5)以概率Pm對C中的染色體進行變異；(6)計算賦給C的新染色體的適應(yīng)度;(7)假設(shè)不滿足結(jié)束條件,轉(zhuǎn)步驟2執(zhí)行。上述兩種模型可自然地用不同類型的并行計算機完成。一般來說,LM模型適于MIMD(多指令流多數(shù)據(jù)流)計算機,如基于TRANSPUTER的并行計算機完成;NM模型適于SIMD(單指令流多數(shù)據(jù)流)計算機,陣列機或連接機等并行計算機完成,但是也有例外情況。ー個典型的例子TANESE的工作(1987),他在由NCUBE公司制造的ー臺超立方體MIMD計算機上完成了NM模型。該計算機由64個微處理機互聯(lián)組成了一個6維的二進制立方體。立方體共有26=64個結(jié)點,每個結(jié)點是一臺有32位字長的CPU和128K字節(jié)局部存儲器的微處理機,其存儲器的四分之一用來存儲結(jié)點操作系統(tǒng)和信息緩存器。每個微處理機運行一個子群體,與其鄰域(直接相聯(lián))的其它6個微處理機周期性地交換最好的染色體。另ー個例子是MUHLENBEIN的ASPARAGOS系統(tǒng)(1988):此系統(tǒng)的鄰域結(jié)構(gòu)由兩個連接成梯狀的兩個環(huán)組成,直接映射到由64個TRANSPUTER組成的MIMD計算機完成。實驗結(jié)構(gòu)說明,這兩個系統(tǒng)所完成的并行GA模型都獲得了很好的效果。第六節(jié)遺傳算法(GA)應(yīng)用舉例GA的早期應(yīng)用主要圍繞組合優(yōu)化問題求解,如煤氣管道的最優(yōu)操作,旅游商(TSP)問題等,近年來迅速擴展到機器學(xué)習(xí),設(shè)計規(guī)劃,神經(jīng)網(wǎng)絡(luò)優(yōu)化,核反響堆操作,噴氣發(fā)動機設(shè)計,通訊網(wǎng)絡(luò)設(shè)計,人工生命等領(lǐng)域,顯示了GA應(yīng)用的龐大潛カ。常規(guī)的數(shù)學(xué)優(yōu)化技術(shù)基于梯度尋優(yōu)技術(shù),計算速度快,但缺少之處是:要求其目標函數(shù)可微;常因陷入局部解而不能獲得最優(yōu)的全局解。工程中存在許多困難的組合優(yōu)化問題及復(fù)雜的函數(shù)優(yōu)化問題,大都具有非線性,有些甚至不可微,對這類問題常規(guī)的數(shù)學(xué)優(yōu)化技術(shù)無法有效的求解,只能對問題作簡化的近似處理。GA本質(zhì)上是ー種基于隨機的全局多點搜索算法,求解優(yōu)化問題時,具有以下特點:只使用適應(yīng)度函數(shù)反復(fù)指導(dǎo)和執(zhí)行遺傳搜索,不需要對目標函數(shù)求導(dǎo)數(shù),因而對目標函數(shù)沒有可微的要求;同時搜索解空間中的許多點,而不是ー個點,保證了解的全局最優(yōu)性;使用概率而不是確定性規(guī)則指導(dǎo)搜索,能搜索離散的多峰復(fù)雜解空間。因此,GA特別適宜求解具有非線性,不連續(xù),不可微,多峰的目標函數(shù),或約束條件復(fù)雜的非線性組合優(yōu)化問題。下面舉例說明GA在組合優(yōu)化問題求解中的應(yīng)用。一..GA在TSP(旅游商)問題求解中的應(yīng)用設(shè)存在N個城市,Dワ范表示城i與城j之間的距離,Djj=Djj,現(xiàn)在要求一條遍歷全部N個城市,且不走重復(fù)路的最短路徑(最短哈密爾頓圈)。這是ー個典型的組合排列順序問題,屬NP難題。為求解方便,采納十進制編碼,每個染色體由按肯定順序排列的N個城市的序號組成,范表示一條可能的旅游路徑,其中每個基因范表示一個城市。染色體的長度為N,解空間為2N/。適應(yīng)度取為一條旅游路徑對應(yīng)的距離,路徑越短的染色體適應(yīng)度越高。例如,取N=7,城市代號為1,2,3,4,5,6,7,則種群中的染色體1324567范表小一條旅游路徑:從1f3f2f4f5f6f7fl其適應(yīng)度為E固=D[3+D32+D24+D45+(156+ロ6フ+D7]下面介紹具體算法：