遺傳算法入門(mén)

《遺傳算法入門(mén)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、遺傳算法入門(mén)遺傳算法遺傳算法（GeneticAlgorithm,GA）是近幾年發(fā)展起來(lái)的一種嶄新的全局優(yōu)化算法。1962年霍蘭德(Holland)教授首次提出了GA算法的思想，它借用了仿真生物遺傳學(xué)和自然選擇機(jī)理，通過(guò)自然選擇、遺傳、變異等作用機(jī)制，實(shí)現(xiàn)各個(gè)個(gè)體的適應(yīng)性的提高。從某種程度上說(shuō)遺傳算法是對(duì)生物進(jìn)化過(guò)程進(jìn)行的數(shù)學(xué)方式仿真。這一點(diǎn)體現(xiàn)了自然界中"物競(jìng)天擇、適者生存"進(jìn)化過(guò)程。與自然界相似，遺傳算法對(duì)求解問(wèn)題的本身一無(wú)所知，它所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià),把問(wèn)題的解表示成染色體，并

2、基于適應(yīng)值來(lái)選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會(huì)。在算法中也即是以二進(jìn)制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群染色體，也即是假設(shè)解。然后，把這些假設(shè)解置于問(wèn)題的“環(huán)境”中，也即一個(gè)適應(yīng)度函數(shù)中來(lái)評(píng)價(jià)。并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的染色體進(jìn)行復(fù)制,淘汰低適應(yīng)度的個(gè)體，再通過(guò)交叉，變異過(guò)程產(chǎn)生更適應(yīng)環(huán)境的新一代染色體群。對(duì)這個(gè)新種群進(jìn)行下一輪進(jìn)化，至到最適合環(huán)境的值。遺傳算法已用于求解帶有應(yīng)用前景的一些問(wèn)題，例如遺傳程序設(shè)計(jì)、函數(shù)優(yōu)化、排序問(wèn)題、人工神經(jīng)網(wǎng)絡(luò)、分類(lèi)系統(tǒng)、計(jì)算機(jī)圖像處

3、理和機(jī)器人運(yùn)動(dòng)規(guī)劃等。術(shù)語(yǔ)說(shuō)明由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的搜索算法，所以在這個(gè)算法中會(huì)用到很多生物遺傳學(xué)知識(shí)，下面是我們將會(huì)用來(lái)的一些術(shù)語(yǔ)說(shuō)明：一、染色體(Chronmosome)染色體又可以叫做基因型個(gè)體(individuals),一定數(shù)量的個(gè)體組成了群體(population),群體中個(gè)體的數(shù)量叫做群體大小。二、基因(Gene)基因是串中的元素，基因用于表示個(gè)體的特征。例如有一個(gè)串S＝1011，則其中的1，0，1，1這4個(gè)元素分別稱(chēng)為基因。它們的值稱(chēng)為等位基因(Alletes)。三、基因

4、地點(diǎn)(Locus)基因地點(diǎn)在算法中表示一個(gè)基因在串中的位置稱(chēng)為基因位置(GenePosition)，有時(shí)也簡(jiǎn)稱(chēng)基因位。基因位置由串的左向右計(jì)算，例如在串S＝1101中，0的基因位置是3。四、基因特征值(GeneFeature)在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。五、適應(yīng)度(Fitness)各個(gè)個(gè)體對(duì)環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)。為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問(wèn)題中的每一個(gè)染色

5、體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù).這個(gè)函數(shù)是計(jì)算個(gè)體在群體中被使用的概率。操作算法霍蘭德(Holland)教授最初提出的算法也叫簡(jiǎn)單遺傳算法，簡(jiǎn)單遺傳算法的遺傳操作主要有三種：選擇(selection)、交叉(crossover)、變異(mutation)這也是遺傳算法中最常用的三種算法：1．選擇(selection)選擇操作也叫復(fù)制操作，從群體中按個(gè)體的適應(yīng)度函數(shù)值選擇出較適應(yīng)環(huán)境的個(gè)體。一般地說(shuō)，選擇將使適應(yīng)度高的個(gè)體繁殖下一代的數(shù)目較多，而適應(yīng)度較小的個(gè)體，繁殖下一代的數(shù)目較少,甚至被淘汰。最通常

6、的實(shí)現(xiàn)方法是輪盤(pán)賭(roulettewheel)模型。令Σfi表示群體的適應(yīng)度值之總和，fi表示種群中第i個(gè)染色體的適應(yīng)度值，它被選擇的概率正好為其適應(yīng)度值所占份額fi／Σfi。如下圖表中的數(shù)據(jù)適應(yīng)值總和Σfi=6650,適應(yīng)度為2200變選擇的可能為fi／Σfi=2200/6650=0.394.圖1.輪盤(pán)賭模型?Fitness值：220018001200950400100選擇概率：33310.2710.180.1430.060.015　2．交叉(Crossover)交叉算子將被選中的兩個(gè)個(gè)體的基因鏈按一

7、定概率pc進(jìn)行交叉，從而生成兩個(gè)新的個(gè)體，交叉位置pc是隨機(jī)的。其中Pc是一個(gè)系統(tǒng)參數(shù)。根據(jù)問(wèn)題的不同，交叉又為了單點(diǎn)交叉算子（SinglePointCrossover）、雙點(diǎn)交叉算子（TwoPointCrossover）、均勻交叉算子(UniformCrossover)，在此我們只討論單點(diǎn)交叉的情況。單點(diǎn)交叉操作的簡(jiǎn)單方式是將被選擇出的兩個(gè)個(gè)體S1和S2作為父母?jìng)€(gè)體，將兩者的部分基因碼值進(jìn)行交換。假設(shè)如下兩個(gè)8位的個(gè)體：S110001111S211101100產(chǎn)生一個(gè)在1到7之間的隨機(jī)數(shù)c，假如現(xiàn)在產(chǎn)生

8、的是2，將S1和S2的低二位交換：S1的高六位與S2的低六位組成數(shù)串10001100，這就是S1和S2的一個(gè)后代P1個(gè)體；S2的高六位與S1的低二位組成數(shù)串11101111，這就是S1和S2的一個(gè)后代P2個(gè)體。其交換過(guò)程如下圖所示：Crossover11110000Crossover11110000S110001111S211101100P110001100P2111011113．變異(Mutation)這是在選中的個(gè)體中，將