遺傳算法入門

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

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

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

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

4、地點(Locus)基因地點在算法中表示一個基因在串中的位置稱為基因位置(GenePosition)，有時也簡稱基因位?；蛭恢糜纱淖笙蛴矣嬎悖缭诖甋＝1101中，0的基因位置是3。四、基因特征值(GeneFeature)在用串表示整數(shù)時，基因的特征值與二進制數(shù)的權(quán)一致；例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。五、適應(yīng)度(Fitness)各個個體對環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)。為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個染色

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

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

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

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