技術(shù)報(bào)告遺傳算法

1、遺傳算法1. 概述遺傳算法是從代表問題可能潛在的解集的一個種群(population )開始的，而一個種群則由經(jīng)過基因(gene)編碼的一定數(shù)目的個體 (individual) 組成。每個個體實(shí)際上是染色體 (chromosome)帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)(即基因型)是某種基因組合，它決定了個體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是 由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡化，如二進(jìn)制編碼， 初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代(

2、generation )演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應(yīng)度(fitness )大小選擇(selection )個體，并借助于自然遺傳學(xué)的遺傳算子(genetic operators)進(jìn)行組合交叉(crossover )和變異(mutation )，產(chǎn)生出代表新的解集的種群。這個過程將導(dǎo)致種群像自然進(jìn)化一樣的 后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼(decoding )，可以作為問題近似最優(yōu)解。1.1產(chǎn)生與背景生物只有經(jīng)過許多世代的不斷進(jìn)化(evolution,演化)，才能更好地完成生存與繁衍的任務(wù)。遺傳算法也遵循同樣的方式，需要隨著時(shí)間的推移不

3、斷成長、演化，最后才能收斂， 得到針對某類特定問題的一個或多個解。了解一些有關(guān)有生命的機(jī)體如何演化的知識，對理解遺傳算法的演化機(jī)制是是有幫助的。從本質(zhì)上說，任何生物機(jī)體不過就是一大堆細(xì)胞的集合。每個細(xì)胞都包含若干組相同的DNA鏈，人們一般稱之為染色體(chromosome)。染色體中包含的 DNA分為兩股，這兩股 DNA 鏈以螺旋狀絞合在一起，這就是我們所熟悉的DNA雙螺旋結(jié)構(gòu)模型。圖1.1 DNA雙螺旋結(jié)構(gòu)單個染色體是由稱作基因( gene)的更小結(jié)構(gòu)模塊組成，而基因則又由稱作核苷酸(nucleotide )的物質(zhì)組成。核苷酸一共只有四種類型，即：腺嘌呤(thymine)、鳥嘌呤(adeni

4、ne)、胞嘧啶(cytocine)、胸腺嘧啶(guanine)。它們常簡寫為T、A、C、G 這些核苷酸相互連接起來， 形成若干很長的基因鏈， 而每個基因編碼了生物機(jī)體的某種特征， 如頭 發(fā)的顏色，耳朵的樣子， 等。一個基因可能具有的不同設(shè)置 （如頭發(fā)的黑色、 棕色或金黃色） ， 稱為等位基因（ allele ），它們沿染色體縱向所處的物理部位稱為基因的座位（ locus ）。一個細(xì)胞中的染色體組 （ collection ）包含了復(fù)制該機(jī)體所需的全部信息。 這就是克隆 怎樣實(shí)行的秘密。你可以從被克隆施主（ donor ）身上，哪怕是一個血細(xì)胞中包含的信息， 復(fù)制出整個生物機(jī)體， 例如一只羊。

5、新的羊?qū)诿恳粋€方面和施主羊完全相同。 染色體的 這一集合就稱為生物機(jī)體的基因組（genome。在特殊基因組中等位基因的一種狀態(tài)稱為該機(jī)體的遺傳類型 （ genotype ）。這些就是用來生成實(shí)際的生物機(jī)體 所謂表現(xiàn)型（ phenotype ） -本身的硬編碼指令。你和我都是表現(xiàn)型。 我們的DNA攜帶了我們的遺傳類型。如將這些術(shù)語用到其他領(lǐng)域中， 則，設(shè)計(jì)汽車用的成套藍(lán)圖就是一個遺傳類型； 在生產(chǎn)線上隆隆作響的 成品汽車就是一個表現(xiàn)型； 只有設(shè)計(jì)被定型之前的， 那些完全陣舊的設(shè)計(jì)， 才勉強(qiáng)稱得上是 一個基因組。對于千千萬萬的動物和植物小到只有在顯微鏡下才能看到的單細(xì)胞生物，大到從空間衛(wèi)星上也

6、能見到的巨大珊瑚礁地球是它們共同的家， 不管它們的大小怎樣、 形狀或顏色又 怎樣。 一個生物機(jī)體被認(rèn)為取得了成功， 如果它得到了配偶并生下了一個子機(jī)體， 而后者完 全有希望來繼續(xù)進(jìn)一步復(fù)制自己。為了做到這一點(diǎn)，生物機(jī)體必須善長許多工作。例如，能尋找食物和水、能面對掠食者 來保衛(wèi)自己、 能使自己吸引潛在的配偶， 等。所有這些特長在某種程度上都和生物機(jī)體的遺 傳類型 生命的藍(lán)圖有關(guān)。生物機(jī)體的某些基因?qū)a(chǎn)生有助于它走向成功的屬性，而另一些基因則可能要妨礙它取得成功。 適應(yīng)，它的子孫后代也就愈多。當(dāng)兩個生物機(jī)體配對和復(fù)制時(shí)，新的染色體組。這一過程就叫重組（一個生物的成功的量度就是它的適應(yīng)性。 生物

7、機(jī)體愈能它們的染色體相互混合， 產(chǎn)生一個由雙方基因組成的全 recombination ）或交疊（ crossover, 又譯雜交 , 交叉 ,交換）。這樣就意味，后代繼承的可能大部分是上一代的優(yōu)良基因，也可能繼承了它們不少 的不良基因。如果是前一種情況，后代就可能變得比它的父母更能成功（例如，它對掠食者有更強(qiáng)的自衛(wèi)機(jī)制） ；如為后一種情況，后代甚至就有可能不能再復(fù)制自己。這里要著重注 意的是， 愈能適應(yīng)的子孫后代就愈有可能繼續(xù)復(fù)制并將其基因傳給下一個子孫后代。由此就會顯示一種趨向，每一代總是比其父母一代生存和匹配得更完美。作為它的一個很簡捷的例子，我們設(shè)想， 雌性動物僅僅吸引大眼睛的雄性。

8、這樣，在追 求雌性配偶的雄性中，眼睛的尺寸愈大， 其獲得成功的可能性也愈大。 你可以說， 動物的適 應(yīng)性正比于它的眼睛的直徑。 因此，你就可以看到， 從一個具有不同大小眼睛的雄性群體出 發(fā)，當(dāng)動物進(jìn)化時(shí)， 在同位基因中， 能產(chǎn)生大眼睛雄性動物的基因，相對于產(chǎn)生小眼睛雄性 動物的基因，就更有可能被復(fù)制到下一代。由此可以推出，當(dāng)進(jìn)化幾代之后，大眼睛將會在雄性群體占據(jù)統(tǒng)治地位。過些時(shí)候，你就可以說，生物正在向一種特殊的遺傳基因收斂。 達(dá)爾文的自然選擇學(xué)說是一種被人們廣泛接受的生物進(jìn)化學(xué)說。這種學(xué)說認(rèn)為， 生物要生存下去， 就必須進(jìn)行生存斗爭。 生存斗爭包括種內(nèi)斗爭、 種間斗爭以及生物跟無機(jī)環(huán)境之 間

9、的斗爭三個方面。 在生存斗爭中， 具有有利變異的個體容易存活下來， 并且有更多的機(jī)會 將有利變異傳給后代； 具有不利變異的個體就容易被淘汰， 產(chǎn)生后代的機(jī)會也少的多。 因此， 凡是在生存斗爭中獲勝的個體都是對環(huán)境適應(yīng)性比較強(qiáng)的。 達(dá)爾文把這種在生存斗爭中適者 生存，不適者淘汰的過程叫做自然選擇。它表明，遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。自然界中的多種生物之所以能夠適應(yīng)環(huán)境而得以生存進(jìn)化， 是和遺傳和變異生命現(xiàn)象分不開的。正是生物的這種遺傳特性，使生物界的物種能夠保持相對的穩(wěn)定；而生物的變異特性，使生物個體產(chǎn)生新的性狀，以至于形成新的物種，推動了生物的進(jìn)化和發(fā)展。遺傳算法是模擬達(dá)爾文的遺傳選擇

10、和自然淘汰的生物進(jìn)化過程的計(jì)算模型。它的思想源于生物遺傳學(xué)和 適者生存的自然規(guī)律，是具有“生存檢測” 的迭代過程的搜索算法。 遺傳算法以一種群體 中的所有個體為對象， 并利用隨機(jī)化技術(shù)指導(dǎo)對一個被編碼的參數(shù)空間進(jìn)行高效搜索。 其中， 選擇、 交叉和變異構(gòu)成了遺傳算法的遺傳操作；參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的 設(shè)計(jì)、遺傳操作設(shè)計(jì)、控制參數(shù)設(shè)定五個要素組成了遺傳算法的核心內(nèi)容。 作為一種新的 全局優(yōu)化搜索算法， 遺傳算法以其簡單通用、 魯棒性強(qiáng)、 適于并行處理以及高效、 實(shí)用等顯 著特點(diǎn)，在各個領(lǐng)域得到了廣泛應(yīng)用，取得了良好效果，并逐漸成為重要的智能算法之一。生物的進(jìn)化是一個奇妙的優(yōu)化過程

11、， 它通過選擇淘汰， 突然變異， 基因遺傳等規(guī)律產(chǎn)生 適應(yīng)環(huán)境變化的優(yōu)良物種。遺傳算法是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。1.2 研究思想遺傳算法受到達(dá)爾文進(jìn)化論的影響很大。在遺傳算法中，問題的解是逐漸進(jìn)化得到的。 遺傳算法的計(jì)算從一組可能解開始，這組解被稱作種群( Population )，在算法中被表 示成基因。 我們又把種群中的解拿出來去構(gòu)成新的一個種群， 這是因?yàn)槲覀兤谕碌姆N群要 比舊的種群要好！當(dāng)然，新的種群中的解要有這樣的性質(zhì)，就必須按照它的適應(yīng)度去選擇， 適應(yīng)度越高， 它參與構(gòu)造新的種群的機(jī)會就越大。 這個過程一次又一次的重復(fù)， 一直到我們 所給的約束條件滿足為止，

12、比如說種群中解得個數(shù)或者種群的良好程度。生物的進(jìn)化是一個奇妙的優(yōu)化過程， 它通過選擇淘汰， 突然變異， 基因遺傳等規(guī)律產(chǎn)生 適應(yīng)環(huán)境變化的優(yōu)良物種。遺傳算法是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。遺傳算法的基本思想是基于 Darwin 進(jìn)化論和 Mendel 的遺傳學(xué)說的。Darwin 進(jìn)化論最重要的是適者生存原理。它認(rèn)為每一物種在發(fā)展中越來越適應(yīng)環(huán)境。 物種每個個體的基本特征由后代所繼承， 但后代又會產(chǎn)生一些異于父代的新變化。 在環(huán)境變 化時(shí)，只有那些熊適應(yīng)環(huán)境的個體特征方能保留下來。Mendel 遺傳學(xué)說最重要的是基因遺傳原理。它認(rèn)為遺傳以密碼方式存在細(xì)胞中，并以 基因形式包含在染

13、色體內(nèi)。 每個基因有特殊的位置并控制某種特殊性質(zhì)； 所以， 每個基因產(chǎn) 生的個體對環(huán)境具有某種適應(yīng)性。 基因突變和基因雜交可產(chǎn)生更適應(yīng)于環(huán)境的后代。 經(jīng)過存 優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來。由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法； 故而在這個算法中 要用到各種進(jìn)化和遺傳學(xué)的概念。2. 基本工作原理遺傳算法的基本原理正是基于模仿生物界遺傳學(xué)的遺傳過程。 它把問題的參數(shù)用基因代 表，把問題的解用染色體代表(在計(jì)算機(jī)里用二進(jìn)制碼表示) ，從而得到一個由具有不同染 色體的個體組成的群體。 這個群體在問題特定的環(huán)境里生存競爭， 適者有最好的機(jī)會生存和 產(chǎn)生后代。 后

14、代隨機(jī)化地繼承了父代的最好特征， 并也在生存環(huán)境的控制支配下繼續(xù)這一過 程。群體的染色體都將逐漸適應(yīng)環(huán)境，不斷進(jìn)化，最后收斂到一族最適應(yīng)環(huán)境的類似個體， 即得到問題最優(yōu)的解 值得注意的一點(diǎn)是， 現(xiàn)在的遺傳算法是受生物進(jìn)化論學(xué)說的啟發(fā)提出 的，這種學(xué)說對我們用計(jì)算機(jī)解決復(fù)雜問題很有用。2.1 生物遺傳學(xué)概念由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法；故而在這個算法中要用到各種進(jìn)化和遺傳學(xué)的概念。 首先給出遺傳學(xué)概念、 遺傳算法概念和相應(yīng)的數(shù)學(xué)概念三 者之間的對應(yīng)關(guān)系.這些概念如下：表2.1概念對照表序 號遺傳學(xué)概念遺傳算法概念數(shù)學(xué)概念1個體要處理的基本對象、結(jié)構(gòu)也就是可行解2群體

15、個體的集合被選定的一組可行解3染色體個體的表現(xiàn)形式可行解的編碼4基因染色體中的兀素編碼中的兀素5基因位某一基因在染色體中的位置兀素在編碼中的位置6適應(yīng)值個體對于環(huán)境的適應(yīng)程度， 或在環(huán)境壓力下的生存能力可行解所對應(yīng)的適應(yīng)函數(shù)值7種群被選定的一組染色體或個體根據(jù)入選概率定出的一組可行解8選擇從群體中選擇優(yōu)勝的個體， 淘汰劣質(zhì)個體的操作保留或復(fù)制適應(yīng)值大的可行解， 去掉小的可行解9交叉一組染色體上對應(yīng)基因段的 交換根據(jù)交叉原則產(chǎn)生的一組新解10交叉概率染色體對應(yīng)基因段交換的概 率(可能性大小)閉區(qū)間0,1上的一個值，一般為0.650.9011變異染色體水平上基因變化編碼的某些兀素被改變12變異概率

16、染色體上基因變化的概率(可能性大小)開區(qū)間(0,1)內(nèi)的一個值，一般為 0.0010.0113進(jìn)化、 適者生 存?zhèn)€體進(jìn)行優(yōu)勝劣汰的進(jìn)化， 一代又一代地優(yōu)化目標(biāo)函數(shù)取到最大值，最優(yōu)的可 行解2.2步驟和實(shí)現(xiàn)方法遺傳算法計(jì)算優(yōu)化的操作過程就如同生物學(xué)上生物遺傳進(jìn)化的過程，主要有三個基本操作(或稱為算子)：選擇(Selection )、交叉(Crossover )、變異(Mutation )。遺傳算法基本步驟主要是：先把問題的解表示成“染色體”，在算法中也就是以二進(jìn)制編碼的串，在執(zhí)行遺傳算法之前，給出一群“染色體”，也就是假設(shè)的可行解。然后，把這些假設(shè)的可行解置于問題的 “環(huán)境”中，并按適者生存的原

17、則， 從中選擇出較適應(yīng)環(huán)境的 “染 色體”進(jìn)行復(fù)制，再通過交叉、變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。經(jīng)過這樣 的一代一代地進(jìn)化，最后就會收斂到最適應(yīng)環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解。遺傳算法的一般算法：創(chuàng)建一個隨機(jī)的初始狀態(tài)初始種群是從解中隨機(jī)選擇出來的，將這些解比喻為染色體或基因，該種群被稱為第一代，這和符號人工智能系統(tǒng)的情況不一樣， 在那里問題的初始狀態(tài) 已經(jīng)給定了。評估適應(yīng)度 對每一個解（染色體）指定一個適應(yīng)度的值，根據(jù)問題求解的實(shí)際接近程度 來指定（以便逼近求解問題的答案）。不要把這些“解”與問題的“答案”混為一談，可以把它理解成為要得到答案，系統(tǒng)可能需要利用的那些特

18、性。繁殖（包括子代突變）帶有較高適應(yīng)度值的那些染色體更可能產(chǎn)生后代（后代產(chǎn)生后也將發(fā)生突變）。后代是父母的產(chǎn)物，他們由來自父母的基因結(jié)合而成，這個過程被稱為“雜 交”。下一代如果新的一代包含一個解，能產(chǎn)生一個充分接近或等于期望答案的輸出， 那么 問題就已經(jīng)解決了。 如果情況并非如此， 新的一代將重復(fù)他們父母所進(jìn)行的繁衍過程， 一代 一代演化下去，直到達(dá)到期望的解為止。并行計(jì)算非常容易將遺傳算法用到并行計(jì)算和群集環(huán)境中。一種方法是直接把每個節(jié)點(diǎn)當(dāng)成一個并行的種群看待。然后有機(jī)體根據(jù)不同的繁殖方法從一個節(jié)點(diǎn)遷移到另一個節(jié) 點(diǎn)。另一種方法是“農(nóng)場主 /勞工”體系結(jié)構(gòu)，指定一個節(jié)點(diǎn)為“農(nóng)場主”節(jié)點(diǎn)，負(fù)

19、責(zé)選擇 有機(jī)體和分派適應(yīng)度的值，另外的節(jié)點(diǎn)作為“勞工”節(jié)點(diǎn)，負(fù)責(zé)重新組合、變異和適應(yīng)度函數(shù)的評估。遺傳算法的具體步驟：1）選擇編碼策略，把參數(shù)集合（可行解集合）轉(zhuǎn)換染色體結(jié)構(gòu)空間；2）定義適應(yīng)函數(shù)，便于計(jì)算適應(yīng)值；3）確定遺傳策略，包括選擇群體大小，選擇、交叉、變異方法以及確定交叉概率、變異 概率等遺傳參數(shù)；4）隨機(jī)產(chǎn)生初始化群體；5）計(jì)算群體中的個體或染色體解碼后的適應(yīng)值；6）按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用于群體，形成下一代群體；7）判斷群體性能是否滿足某一指標(biāo)、或者是否已完成預(yù)定的迭代次數(shù)，不滿足則返回第五步、或者修改遺傳策略再返回第六步。圖2.1一個遺傳算法的具體步驟遺傳算法

20、有很多種具體的不同實(shí)現(xiàn)過程， 以上介紹的是標(biāo)準(zhǔn)遺傳算法的主要步驟， 此算 法會一直運(yùn)行直到找到滿足條件的最優(yōu)解為止1）群體規(guī)模群體規(guī)模N影響到GA的最終性能和效率。 當(dāng)規(guī)模太小時(shí)，由于群體對大部分搜索空間 只給出了不充分的樣本量， 所以得到的結(jié)果一般不佳， 大的群體更有希望包含大量搜索空間 的代表， 從而可以防止過早收斂到局部最優(yōu)解； 然而群體越大， 每一代需要的計(jì)算量也就越 多，這可能會導(dǎo)致一個無法接受的慢收斂，在試驗(yàn)中群體規(guī)模的變化范圍從10160。2）編碼與解碼 編碼就是把問題的解用數(shù)字串表示， 遺傳算子也是直接對串進(jìn)行操作的。 這樣， 如何用 適當(dāng)?shù)拇畞肀硎締栴}的解也就成了GA的一個重

21、要問題。在GA的許多應(yīng)用中都是用二進(jìn)制的數(shù)字串來表示， 目前也有用浮點(diǎn)數(shù)來表示的。 浮點(diǎn)數(shù)表示精度會提高， 但是增加迭代時(shí)間。 下面只介紹用二進(jìn)制串進(jìn)行的編碼， 首先確定要優(yōu)化的參數(shù)并確定每個參數(shù)的大致變化范圍， 這個范圍選擇得不好， 也會影響遺傳算法的性能。 根據(jù)每個參數(shù)的精度和參數(shù)空間的大小來 確定二進(jìn)制的位數(shù)，然后把每個參數(shù)的二進(jìn)制串一個一個地排列起來，就構(gòu)成了GA的一個個體或者稱作染色體。 數(shù)字串中優(yōu)化變量的排列方式也是一個比較重要的問題，合適的排列方式除了便于編碼和解碼之外，對GA的性能也有一定的影響。3）遺傳算法中個體的選擇選擇就是根據(jù)適應(yīng)值從群體中選擇串進(jìn)行拷貝的過程， 一旦一個

22、串被選擇， 則將這個串 的拷貝放入在一個新的暫時(shí)群體交配池中， 以便進(jìn)行交叉和變異。 選擇的方法有確定性選擇、 輪盤賭選擇、無退還隨機(jī)選擇、窗口選擇方法，兩兩競爭法，線性標(biāo)準(zhǔn)化方法，還有退還和 無退還的剩余隨機(jī)選擇方法等。3. 計(jì)算機(jī)內(nèi)的進(jìn)化遺傳算法的工作過程本質(zhì)上就是模擬生物的進(jìn)化過程。 首先， 要規(guī)定一種編碼方法， 使 得你的問題的任何一個潛在可行解都能表示成為一個 “數(shù)字 ”染色體。 然后， 創(chuàng)建一個由隨機(jī) 的染色體組成的初始群體 （每個染色體代表了一個不同的候選解） ，并在一段時(shí)期中， 以培 育適應(yīng)性最強(qiáng)的個體的辦法， 讓它們進(jìn)化， 在此期間， 染色體的某些位置上要加入少量的變 異。經(jīng)

23、過許多世代后，運(yùn)氣好一點(diǎn)， 遺傳算法將會收斂到一個解。 遺傳算法不保證一定能得 到解， 如果有解也不保證找到的是最優(yōu)解， 但只要采用的方法正確， 你通常都能為遺傳算法 編出一個能夠很好運(yùn)行的程序。遺傳算法的最大優(yōu)點(diǎn)就是，你不需要知道怎么去解決一個問題; 你需要知道的僅僅是， 用什么的方式對可行解進(jìn)行編碼， 使得它能被遺傳算法機(jī)制所 利用。通常， 代表可行解的染色體采用一系列的二進(jìn)制位作為編碼。在運(yùn)行開始時(shí)， 你創(chuàng)建一個染色體的群體，每個染色體都是一組隨機(jī)的2進(jìn)制位。2進(jìn)制位（即染色體）的長度在整個群體中都是一樣的。作為一個例子，長度為 20 的染色體的形狀如下 :010100101001010

24、01111重要的事情就在于，每個染色體都用這樣的方式編碼成為由0 和 1 組成的字符串，而它們通過 譯碼 就能用來表示你手頭問題的一個解。這可能是一個很差的解，也可能是一個 十分完美的解， 但每一個單個的染色體都代表了一個可行解。 初始群體通常都是很糟的， 有 點(diǎn)像英國板球隊(duì)或美國足球隊(duì)。 但不管怎樣， 正如前面說過的那樣， 一個初始的群體已經(jīng)創(chuàng) 建完成（對這一例子，不妨設(shè)共有 100 個成員），這樣，你就可以開始做下面列出的一系 列工作：不斷進(jìn)行下列循環(huán)，直到尋找出一個解 :（1 ）檢查每個染色體，看它解決問題的性能怎樣，并相應(yīng)地為它分配一個適應(yīng)性分?jǐn)?shù)。（2 ）從當(dāng)前群體中選出 2 個成員。

25、被選出的概率正比于染色體的適應(yīng)性， 適應(yīng)性分?jǐn)?shù)愈高， 被選中的可能性也就愈大。常用的方法就是采用所謂的 輪盤賭選擇 法 或 賭 輪選 擇 法 （Roulette wheel selection ）。（ 3 ）按照預(yù)先設(shè)定的 雜交率 （ Crossover Rate ），從每個選中染色體的一個隨機(jī)的點(diǎn) 上進(jìn)行雜交（ crossover ）。（ 4 ）按照預(yù)定的 變異率 （ mutation rate ），通過對被選染色體的位的循環(huán)，把相應(yīng) 的位進(jìn)行翻轉(zhuǎn)（ flip ）。（5 ）重復(fù)步驟（ 2），（ 3），（ 4 ），直到 100 個成員的新群體被創(chuàng)建出來。結(jié)束循環(huán)以上算法中步驟 1 到步驟 5

26、的一次循環(huán)稱為一個代（或世代， generation ）。而我把 這整個的循環(huán)稱作一個時(shí)代 （epoch ） ，在我的正文和代碼中將始終都用這樣方式來稱呼。3.1 輪盤賭選擇輪盤賭選擇是從染色體群體中選擇一些成員的方法， 被選中的機(jī)率和它們的適應(yīng)性分?jǐn)?shù) 成比例， 染色體的適應(yīng)性分?jǐn)?shù)愈高， 被選中的概率也愈多。 這不保證適應(yīng)性分?jǐn)?shù)最高的成員 一定能選入下一代，僅僅說明它有最大的概率被選中。其工作過程是這樣的：設(shè)想群體全體成員的適當(dāng)性分?jǐn)?shù)由一張餅圖來代表 （ 見圖 3.4） ，這一餅圖就和用于賭 博的轉(zhuǎn)輪形狀一樣。 我們要為群體中每一染色體指定餅圖中一個小塊。 塊的大小與染色體的 適應(yīng)性分?jǐn)?shù)成比例

27、， 適應(yīng)性分?jǐn)?shù)愈高， 它在餅圖中對應(yīng)的小塊所占面積也愈大。 為了選取一 個染色體，你要做的，就是旋轉(zhuǎn)這個輪子，并把一個小球拋入其中，讓它翻來翻去地跳動， 直到輪盤停止時(shí)， 看小球停止在哪一塊上， 就選中與它對應(yīng)的那個染色體。 本章后面我就會 告訴你怎樣來編寫這種程序的準(zhǔn)確算法。圖3.1染色體的輪盤賭式選擇3.2雜交率雜交率就是用來確定2個染色體進(jìn)行局部的位 （bit ）的互換以產(chǎn)生2個新的子代的概率。實(shí)驗(yàn)表明這一數(shù)值通常取為0.7左右是理想的，盡管某些問題領(lǐng)域可能需要更高一些或較低一些的值。每一次，我們從群體中選擇2個染色體，同時(shí)生成其值在0到1之間一個隨機(jī)數(shù)，然后根據(jù)此數(shù)據(jù)的值來確定兩個染色

28、體是否要進(jìn)行雜交。如果數(shù)值低于雜交率（0.7）就進(jìn)行雜交，然后你就沿著染色體的長度隨機(jī)選擇一個位置，并把此位置后面所有的位進(jìn)行互換。例如，設(shè)給定的 2個染色體為：1000100111001001001010001001000011沿著它們的長度你隨機(jī)選擇一個位置，比如說 10 ,然后互換第10位之后所有位。這 樣兩個染色體就變成了（我已在開始互換的位置加了一個空格）：100010011 01000011010100010 100100103.3變異率變異率（突變率）就是在一個染色體中將位實(shí)行翻轉(zhuǎn)（ flip，即0變1，1變0 ）的幾率。這對于二進(jìn)制編碼的基因來說通常都是很低的值，比如0.001

29、。因此，無論你從群體中怎樣選擇染色體，你首先是檢查是否要雜交，然后再從頭到尾檢 查子代染色體的各個位，并按所規(guī)定的幾率對其中的某些位實(shí)行突變（翻轉(zhuǎn)）。4. 實(shí)際應(yīng)用4.1 二維下料問題遺傳算法是一種優(yōu)化算法， 所以可以應(yīng)用在很多地方。 尤其是對于比較復(fù)雜或者難于求 出精確解的問題，該方法給出了比較好的解決方案。二維下料問題是說， 在固定寬度的板材上切割下一些要求大小的目標(biāo)物， 使得消耗的板 材長度最小。對于這個問題，可以把他抽象為這樣的數(shù)學(xué)模型：每一個目標(biāo)物設(shè)置一個 id 號，這樣 一組 id 號就構(gòu)成了一個切割順序。顯然，在這樣的模型下，切割順序和切割方式對于最終 的結(jié)果有比較大的影響。略去

30、切割方式，本文在一種切割方式下，集中對切割順序作一個小小的分析。 我選擇的切割方法是： 將進(jìn)入的目標(biāo)物從下到上， 從左到右地在板材上找空閑位置， 找 到后將板材上的該區(qū)域標(biāo)記；重復(fù)上述過程直到?jīng)]有目標(biāo)物進(jìn)入為止。在上述切割方式下， 我的目標(biāo)轉(zhuǎn)化為找到一個合適的序列使得切割后使用的板材長度盡 可能地小。對于這個序列， 我使用了遺傳算法。 遺傳算法控制參數(shù)很多， 尤其是初始種群的選取對 于該算法有較大影響。 我選擇了從大到小排列目標(biāo)物， 然后象擠牙膏那樣生成一組新的序列。 用這樣的序列進(jìn)行進(jìn)化。 基本上對于較小數(shù)目的目標(biāo)物， 很快能給出次優(yōu)序列。 從本人實(shí)驗(yàn) 的結(jié)果看，優(yōu)化率( (直接切割所需長度

31、優(yōu)化后所需長度) / 直接切割所需長度)平均為 11%，有時(shí)甚至高達(dá) 28%?？梢姡瑑?yōu)化和不優(yōu)化還是有很大差別的。4.2 排課問題在排課問題中， 我們的主要任務(wù)是將班級、教室、 課程、 教師安排在一周內(nèi)且不發(fā)生時(shí) 間沖突。據(jù)此，我們給出如下描述：學(xué)校有R間教室，C個班，S門課程，T位教師，P個時(shí)間段。1) 教室集合R(R1,R2,Rn),每間教室分別可容納(X1,X2Xr)人；2) 班級集合C (C1,C2,Cn),每個班級分別有(K1,K2,Kc)人，其中有x個班級上 合班課；3) 課程集合S (S1,S2,Sn),每門課對應(yīng) Ci個班，1位教師，(K Ci Cn );4) 教師集合T( T

32、1,T2,Tn),每位教師對應(yīng) Sm1課，Cn個班，(K Sm Sn,1 Cn Cn), 在初始設(shè)置時(shí)設(shè)定教師的排課要求。5) 時(shí)間集合P(P1, P2,，Pn),假設(shè)一周上五天課，每天分為五個教學(xué)單元，每個單元為 2 個課時(shí)，即上午 2 個，下午 2 個, 晚上 1 個，則時(shí)間集合包含 25 個時(shí)間段。如 11 代 表周一第一個教學(xué)單元,即周一 1、2節(jié), 12代表周一第二個教學(xué)單元,即周一3、4節(jié),以此類推，這些時(shí)間段構(gòu)成一個時(shí)間集合P(11,12,13,.55)。一張正確的課表應(yīng)至少滿足以下硬約束條件：1) 一個教師或者一個班級或者一個教室在同一時(shí)間段內(nèi)只能安排一門課程；2) 分配的教室

33、可容納人數(shù)應(yīng)該大于學(xué)生數(shù)。除了上述的硬性約束, 還有些軟約束, 這些軟約束有助于使得課表更加合理, 更加人性 化。這些軟約束條件可能是：1) 盡量在早上安排必修課，而下午安排選修課，晚上盡量不排課；2) 盡可能滿足個別教師的特殊上課時(shí)間要求；3) 一門課盡量分散在一個星期中， 即某天上完某一門課后， 要隔一天以上再上這門課， 以使教師有充足的時(shí)間備課和批改作業(yè)，而學(xué)生也有足夠的時(shí)間復(fù)習(xí)消化；4) 一個教師的課不能排滿一整天；5) 學(xué)生課表中的上課時(shí)間不能過分集中， 應(yīng)避免一天課程很滿而另一天卻一整天沒課的 情況。這些軟約束條件各院校有所不同， 在我們的研究中， 旨在我們定義的約束范圍內(nèi)給出一

34、個遺傳算法的解決方法，并對其進(jìn)行優(yōu)化操作。遺傳算法采用類似基因演化的循環(huán)過程，其演算過程如下：1) 隨機(jī)產(chǎn)生一定數(shù)目的初始種群2) 對個體適應(yīng)度進(jìn)行評估，如果個體的適應(yīng)度符合優(yōu)化準(zhǔn)則，則輸出最佳個體及其代 表的最優(yōu)解，并結(jié)束計(jì)算，否則轉(zhuǎn)向第 3 步。3) 依據(jù)適應(yīng)度選擇再生個體4) 按照一定的交叉概率和交叉方法生成新的個體5) 按照一定的變異概率和變異方法生成新的個體6) 由交叉和變異產(chǎn)生新一代的種群，然后返回第2 步。以下是遺傳算法的偽代碼。BEGIN:I = 0;Initialize P(I);Fitness P(I);While(not Terminate-Condition)I +;G

35、A-Operation P(I);Fitness P(I);END.染色體編碼GA中首要考慮的是如何表現(xiàn)其問題，即如何對染色體編碼，使之適用于GA操作。在經(jīng)典的遺傳算法中， 常采用浮點(diǎn)數(shù)或二進(jìn)制的編碼方法， 而研究中， 每條染色體代表每位教師 的課表，其結(jié)構(gòu)表示如下：教師 ID 班級 ID 課程 ID 教室 上課時(shí)間安排染色體在程序中可用十進(jìn)制數(shù)編碼，例如：某一教師編號為1247，要教授“數(shù)據(jù)庫原理”這門課， “數(shù)據(jù)庫原理”課程編號為 8017，周學(xué)時(shí)為 4，班級為 01811、 01812，隨機(jī)產(chǎn) 生 上 課 時(shí) 間 ， 隨 機(jī) 選 擇 大 于 兩 班 總 人 數(shù) 的 教 室 ， 則 可 生

36、 成 染 色 體 如 ： “124701811018128017024012241 ”其中 02401， 2241 分別代表教室及上課時(shí)間星期二第二 個教學(xué)單元(即上午 3、4 節(jié))和星期四第一個教學(xué)單元(即上午1、2節(jié))。按如上編碼， 兩條染色體對后 9位作交叉操作， 不會影響到每位教師所教授的課程， 也 不會造成教師課表內(nèi)含其他教師的教授課程或每代演化后染色體結(jié)構(gòu)不合理等問題。每一條染色體表示一種可能的排課結(jié)果， 至于排課結(jié)果的優(yōu)劣， 則由適應(yīng)度函數(shù)評估染 色體的適應(yīng)值來決定。適應(yīng)度函數(shù)遺傳算法在進(jìn)化中是以每個個體的適應(yīng)度值為依據(jù)來選取下一代種群的。 適應(yīng)度函數(shù)設(shè) 定的好壞直接影響到遺傳算

37、法的收斂速度和能否找到最優(yōu)解。 在本系統(tǒng)中， 適應(yīng)度函數(shù)的設(shè) 計(jì)思想是對每條染色體中存在的沖突類型進(jìn)行加權(quán)求和，其中權(quán)值 Wi 代表的是第 i 條規(guī)則 的重要程度，若某條染色體違反了某條規(guī)則 i ，則將其值 Pi 置為 1（若沒有違反規(guī)則 i ，則 Pi 值為 0），其受到的懲罰值為 Wi*Pi ，對染色體中存在的沖突進(jìn)行加權(quán)求和并加上 1 后，則表示其擁有較好的授課時(shí)段和初始化時(shí)就需要考慮到教室及時(shí)30 人的班級占用可容 200 人再求其倒數(shù)， 如以下公式所示。 染色體適應(yīng)度函數(shù)值越大， 教室，其在下一代的演化中的生存概率就較大。遺傳操作初始化 Initialize 初始化的目的在于為后面的

38、遺傳操作提供初始種群。在我們的算法中， 由于每次對一位教師進(jìn)行遺傳操作， 間的設(shè)定，這其中包括教室可容人數(shù)的最優(yōu)逼近（即避免一個的教室這種情況） ，以及上課時(shí)間安排的合理性，這在排課問題描述中已有解釋。2）選擇 Select選擇運(yùn)算用于模擬生物界去劣存優(yōu)的自然選擇現(xiàn)象。 它從舊種群中選擇出適應(yīng)度高的某 種染色體， 放入配對集合中， 為染色體交叉和變異運(yùn)算產(chǎn)生新種群做準(zhǔn)備。 適應(yīng)度越高的染 色體被選擇的可能性越大，選擇操作的方法有許多，如輪盤賭選擇法（ roulette wheel selection ），局部選擇法 （ local selection ），錦標(biāo)賽選擇法（ tournament

39、selection ）等。研究中，我們選用了局部選擇法中的一種：截?cái)噙x擇法（truncation selection）。在截?cái)噙x擇法中， 染色體按適應(yīng)度函數(shù)值由高到低排序， 只有最優(yōu)秀的個體才能被選作 父個體。其中，用于決定染色體被選作父個體的百分比的參數(shù)稱為截?cái)嚅y值Trunc ，其取值范圍為 50%10%。在該閥值之外的個體不能產(chǎn)生子個體。選擇強(qiáng)度與截?cái)嚅y值的關(guān)系截?cái)嚅y值 1% 10% 20% 40% 50% 80%選擇強(qiáng)度 2.66 1.76 1.2 0.97 0.8 0.34其中選擇強(qiáng)度是將正規(guī)高斯分布應(yīng)用于選擇方法，期望平均適應(yīng)度。 選擇強(qiáng)度表示為：SelIntTrunc（Trunc）

40、 =式中 fc 為下列高斯分布的積分下限：Trunc =3）交叉 Crossover 交叉是根據(jù)選擇操作的結(jié)果，選取兩條染色體作為父個體，再取一隨機(jī)值（設(shè)為 r ）與 系統(tǒng)預(yù)設(shè)的交叉率值（設(shè)為 t ）比較，若 rt 則進(jìn)行交換基因。4）變異 Mutate變異是隨機(jī)改變?nèi)旧w中任一授課時(shí)段， 將時(shí)段隨機(jī)抽取一點(diǎn)在設(shè)定范圍內(nèi)改變。 變異 運(yùn)算模仿了生物在自然遺傳環(huán)境中由于各種偶然因素引起的基因突變， 通過變異， 染色體適 應(yīng)度有可能加強(qiáng)也有可能降低， 但它確保了種群中遺傳基因類型的多樣性， 使搜索能在盡可 能大的空間中進(jìn)行，獲得最優(yōu)解的可能性大大加強(qiáng)。變異操作與交叉操作類似，即定義一個變異概率 p

41、m在變異時(shí)先產(chǎn)生一個隨機(jī)數(shù)r,當(dāng)rrandom0,1的概率接收新解，其中 random0,1是0 , 1之間的隨機(jī)數(shù)。若達(dá)到溫度Tk的平衡狀態(tài)轉(zhuǎn)(4),否則轉(zhuǎn)(3);4) 按一定方式降低溫度，可定義下降函數(shù)為Tk+仁a Tk,k+1 t,其中a 0,1;5) 若滿足收斂判據(jù),退火過程結(jié)束;否則轉(zhuǎn)(3)。通過以上分析可知, 在模擬退火過程中, 其退火溫度控制著求解過程向最小值的優(yōu)化方 向進(jìn)行，同時(shí)它又以概率 exp(- f/Tk)接收劣質(zhì)解，因此算法可以跳出局部極值點(diǎn)。只要 初始溫度足夠高,退火過程足夠慢,算法能夠收斂到全局最優(yōu)解。4.4 黑盒測試中的應(yīng)用在軟件測試中, 黑盒測試主要是針對模塊進(jìn)

42、行的功能測試。 最普遍的方法是以軟件的功 能說明書為基礎(chǔ)將軟件的輸入劃分為若干個等價(jià)類, 多次運(yùn)行該軟件來檢驗(yàn)軟件對于不同的 等價(jià)類是否能滿足要求。 但是在實(shí)際應(yīng)用中, 有的模塊太大或輸入?yún)?shù)太多, 等價(jià)類劃分后 需要進(jìn)行的測試工作可能是一個極大的任務(wù)。 這時(shí), 如何選擇最優(yōu)的測試用例就成為測試人 員的一個重要任務(wù)。遺傳算法是模仿生物遺傳和進(jìn)化機(jī)制的一種最優(yōu)化方法， 它把類似于遺傳基因的一些行 為，如交叉重組、變異、選擇和淘汰等引入到算法求解的改進(jìn)過程中。遺傳算法的特點(diǎn)之一 是，它同時(shí)保留著若干局部最優(yōu)解， 通過交叉重組或者解的變異來尋求更好的解。 與貪婪算 法相比， 遺傳算法更可能找到全局最

43、優(yōu)解， 而貪婪算法則容易限于局部最優(yōu)而達(dá)不到全局最 優(yōu)。如果能夠?qū)⑦z傳算法有效地運(yùn)用于黑盒測試中， 幫助測試人員選擇最優(yōu)的測試用例， 那 么將給測試工作帶來極大的幫助。應(yīng)用方法 在設(shè)計(jì)具體的算法之前，我們先介紹遺傳算法的基本算法，其算法框架如下： 第一步，初始化：選取P個候選解作為初始解，把其中最好的解作為暫定（最優(yōu)）解。 第二步，解的改進(jìn)：若滿足終止條件，輸出暫定解，算法終止。否則，進(jìn)行以下步驟的 運(yùn)算：1）解的交叉重組：從P個解中選出兩個或兩個以上的解進(jìn)行交叉重組，得到新解，重復(fù)該運(yùn)算若干次。2）變異：在候選解中隨機(jī)加進(jìn)一些變異，產(chǎn)生新解。3）搜索： 對新產(chǎn)生的解用局部搜索法進(jìn)行改良。 若

44、能得到比候選解更好的解， 更新候選 解。4）全部解中按一定的準(zhǔn)則選出p個解作為下一代的候選解，更新暫定解。了解了遺傳算法的算法框架后， 進(jìn)一步要做的就是在軟件的黑盒測試中， 如何將不同的 等價(jià)類轉(zhuǎn)變?yōu)檫z傳算法的候選解， 如何設(shè)定解的優(yōu)劣標(biāo)準(zhǔn)，如何設(shè)置合適的終止條件。我們假定一個軟件模塊的輸入?yún)?shù)有5個：A、B、C、D E,經(jīng)過合理的等價(jià)類劃分后，每個參數(shù)又有5個不同的等價(jià)類：A1A5,E1E5。我們采用一個廣義的遺傳算法候選解概念，一般的遺傳算法往往將候選解形式定為二進(jìn)制的數(shù)據(jù)串，比如：111010、010001 等等，而在不同等價(jià)類輸入作為候選解時(shí)我們將候選解形式定為（按照上面假定為 基礎(chǔ)）

45、：A3B1C2D4E5A2B2C4D1E3等等。這樣我們解決了候選解的問 題，在解的優(yōu)劣標(biāo)準(zhǔn)以及終止條件的設(shè)定問題上，我們需要借助工具作為標(biāo)準(zhǔn)。軟件測試的目的是提高軟件的可靠性，終止條件當(dāng)然是軟件達(dá)到了測試的目的及要求。 而解的優(yōu)劣標(biāo)準(zhǔn)正好與軟件質(zhì)量相反， 即軟件失效幾率越大， 這個測試用例 （一個輸入的解） 越優(yōu)。中結(jié)合北大的青鳥黑盒測試環(huán)境提出了一種基于測試執(zhí)行的失效數(shù)據(jù)模型JBFDM（Jade Bird failure data model）。利用該模型我們可以做到：1）提供一致的失效數(shù)據(jù)建模、收集及管理的可靠性度量過程，從而支持可靠性度量；2）利用測試及軟件現(xiàn)場收集的數(shù)據(jù)來評價(jià)測試計(jì)劃

46、、操作概圖及測試方法的有效性。 軟件測試的目的是發(fā)現(xiàn)錯誤， 在黑盒測試中， 錯誤表現(xiàn)的形式是軟件失效。 但是由于軟件錯誤并不是軟件失效的充分條件，換句話說，并不是所有錯誤都會在測試或運(yùn)行時(shí)暴露， 所以黑盒測試的目的就是盡可能的通過運(yùn)行測試用例使軟件失效而發(fā)現(xiàn)錯誤。在我們對測試用例的評價(jià)時(shí)，用以下的數(shù)據(jù)表示測試用例的優(yōu)劣：A=P+ 入/M+XF其中A表示遺傳算法中的適應(yīng)度Adaptaio , P表示該測試用例在實(shí)際中發(fā)生的幾率Probability ,M表示平均失效時(shí)間（MTTF , f表示失效等級。因?yàn)闇y試是針對使用的，所 以發(fā)生幾率高的測試用例適應(yīng)度高就不難理解了；而M平均失效時(shí)間越長， 該

47、測試用例應(yīng)該不容易發(fā)現(xiàn)軟件的錯誤，所以A越低；F則表示某些特殊情況發(fā)生使軟件嚴(yán)重失效（比如造成死機(jī)、損壞儀器等等），此時(shí)該測試用例以及其后代必須被重點(diǎn)關(guān)注，所以此時(shí)A越 大。入、是相應(yīng)于各個具體的被測試軟件模塊而定的系數(shù)。在實(shí)際應(yīng)用中，由于軟件失效的可能性不是特別大， 所以遺傳結(jié)果往往是發(fā)生幾率高的測試用例后代較多。 所以我們應(yīng)該 針對具體被測試軟件設(shè)計(jì)準(zhǔn)確的發(fā)生概率產(chǎn)生算法。對于該算法的說明如下：1）每一個輸入?yún)?shù)往往有一個幾率（可以事先定義） ，可以簡單相加來求得該測試用例 的概率。但是在輸入?yún)?shù)有較強(qiáng)相關(guān)性時(shí)， 此方法并不能準(zhǔn)確求得某個測試用例的發(fā)生概率， 一個解決辦法是設(shè)置輸入?yún)?shù)的相

48、關(guān)耦合度。 在遺傳算法的交叉、 變異時(shí)其同時(shí)進(jìn)行的幾率 與相關(guān)耦合度成正比， 即對于相關(guān)耦合度高的輸入?yún)?shù)， 它們同時(shí)進(jìn)行交叉、 變異的幾率高， 反之則低。2）檢驗(yàn)是否滿足測試要求時(shí)， 需要先設(shè)置一個計(jì)數(shù)器。 每運(yùn)行一個新的測試用例， 測試 計(jì)數(shù)器加一。 當(dāng)發(fā)現(xiàn)第一次失效或故障時(shí)， 計(jì)數(shù)器加二。 若產(chǎn)生的遺傳后代又使軟件發(fā)生失 效，則計(jì)數(shù)器加2 2。同理遞推，當(dāng)遺傳算法產(chǎn)生的測試用例連續(xù)n次使軟件失效，則計(jì)數(shù) 器加2no同時(shí)，記錄所有的測試情況（此工作由外圍的測試環(huán)境完成，比如北大的青鳥黑 盒測試環(huán)境）。如果出現(xiàn)嚴(yán)重錯誤則終止測試，進(jìn)行對程序的檢查。如果連續(xù)艮代測試用例 的遺傳后代都運(yùn)行良好，

49、計(jì)數(shù)器的值加2k。 k的值由具體被測試軟件的等價(jià)類數(shù)量、輸入?yún)?shù)個數(shù)等決定。 當(dāng)測試計(jì)數(shù)器的值達(dá)到所有黑盒測試用例等價(jià)類的數(shù)值時(shí)（對于我們上面所舉的例子，該值為5 5 = 3 1 2 5 ），結(jié)束測試。當(dāng)生成的孫子代、子代與父母代三代完全相同時(shí)， 算法也必須結(jié)束， 因?yàn)榇藭r(shí)測試不會有新的結(jié)果。 所以我們還要設(shè)置一個結(jié)束條 件。而且該條件強(qiáng)于計(jì)數(shù)器條件。3）每一組測試用例可以生成多個測試用例，根據(jù)適應(yīng)度函數(shù)大小決定留下哪些測試用例組成新的測試用例組。如果某測試用例使軟件的運(yùn)行發(fā)生了問題（即某個軟件錯誤發(fā)作），它的后代也同樣受困于該軟件錯誤， 算法很快能發(fā)現(xiàn)這些最佳測試用例并給出結(jié)果。 測試人員就

50、可以將它們交 給開發(fā)人員解決這些問題。 若軟件本身確實(shí)質(zhì)量優(yōu)良， 這些測試用例及其不同的后代無法發(fā) 現(xiàn)失效，算法也能盡快結(jié)束，而不是完成所有測試用例（雖然從理論上，我們希望測試盡可 能運(yùn)行所有測試用例） 。上節(jié)的算法，相對于運(yùn)行所有測試用例，并沒有比較明顯的優(yōu)點(diǎn)。尤其對于測試來說， 算法并沒有加速運(yùn)行測試用例， 好象還降低了運(yùn)行速度。 其實(shí)算法本身的確不是用來加速運(yùn) 行測試用例的， 其目的是找到一組最佳測試用例。 因?yàn)閷?shí)際上對于很多模塊運(yùn)行所有測試用 例或哪怕是所有等價(jià)類都是幾乎不可能的。以上一節(jié)舉的例子做說明，其輸入等價(jià)類大致有55=3125。如果一個模塊有10個輸入、每個輸入有10種等價(jià)類

51、， 那么輸入等價(jià)類為10 10。按運(yùn)行一個等價(jià)類需要1分鐘計(jì)算（很多循環(huán)運(yùn)行模塊可能不止1分鐘） ，需要幾個月才能運(yùn)行一遍所有等價(jià)類。這 時(shí)，運(yùn)用遺傳算法的優(yōu)勢就體現(xiàn)出來了。綜上所述， 本文提出了一種利用遺傳算法尋求最佳測試用例的測試方法原理。它能在較短時(shí)間內(nèi)完成軟件模塊的黑盒測試并給出測試結(jié)果和好的測試用例。利用該算法原理， 可以在測試集成環(huán)境中做一些設(shè)置或修改測試集成環(huán)境，這樣可以大大提高測試工作的效率。4.5求0,31范圍內(nèi)的y=（x-10）八2的最小值1）編碼算法選擇為 “將 x 轉(zhuǎn)化為 2 進(jìn)制的串” , 串的長度為 5 位。 （等位基因的值為 0 or 1）。2）計(jì)算適應(yīng)度的方法是

52、：先將個體串進(jìn)行解碼，轉(zhuǎn)化為int型的x值,然后使用=（x-10）A2 作為其適應(yīng)度計(jì)算合適 （由于是最小值 , 所以結(jié)果越小 ,適應(yīng)度也越好 ）。3）正式開始 , 先設(shè)置群體大小為 4, 然后初始化群體 = （ 在0,31 范圍內(nèi)隨機(jī)選取 4 個 整數(shù)就可以 , 編碼) 。4) 計(jì)算適應(yīng)度Fi(由于是最小值,可以選取一個大的基準(zhǔn)線1000,Fi = 1000 - (x-10)A2)5) 計(jì)算每個個體的選擇概率。 選擇概率要能夠反映個體的優(yōu)秀程度。 這里用一個很簡單 的方法來確定選擇概率 P=Fi / TOTAL(Fi) 。6) 選擇根據(jù)所有個體的選擇概率進(jìn)行淘汰選擇 . 這里使用的是一個賭輪

53、的方式進(jìn)行淘汰選擇。 先按照每個個體的選擇概率創(chuàng)建一個賭輪 , 然后選取 4次, 每次先產(chǎn)生一個 0-1 的隨機(jī)小數(shù) 然后判斷該隨機(jī)數(shù)落在那個段內(nèi)就選取相對應(yīng)的個體。這個過程中，選取概率P高的個體將可能被多次選擇 , 而概率低的就可能被淘汰。下面是一個簡單的賭輪的例子13% 35% 15% 37%個體 1個體 2個體 3 A0.67個體 4隨機(jī)數(shù)為 0.67 落在了個體 4 的端內(nèi)。本次選擇了個體 4，被選中的個體將進(jìn)入配對庫 (mating pool, 配對集團(tuán) ) 準(zhǔn)備開始繁殖。7) 簡單交叉先對配對庫中的個體進(jìn)行隨機(jī)配對。然后在配對的 2個個體中設(shè)置交叉點(diǎn) , 交換 2個個 體的信息后產(chǎn)生下一代。比如 ( | 代表簡單串的交叉位置 )( 0110|1, 1100|0 ) -交叉- (01100,11001)( 01|000, 11|011 ) -交叉- (01011,11000)2 個父代的個體在交叉后繁殖出了下一代的同樣數(shù)量的個體。復(fù)雜的交叉在交叉的位置交叉的方法 , 雙親的數(shù)量上都可以選擇 . 其