現(xiàn)代生物遺傳學(xué)中描述的生物進(jìn)化理論:
遺傳物質(zhì)的主要載體是染色體(chromsome),染色體主要由DNA和蛋白質(zhì)組成。其中DNA為最主要的遺傳物質(zhì)。
基因(gene)是有遺傳效應(yīng)的片斷,它存儲(chǔ)著遺傳信息,可以準(zhǔn)確地復(fù)制,也能發(fā)生突變,并可通過(guò)控制蛋白質(zhì)的合成而控制生物的狀態(tài).生物自身通過(guò)對(duì)基因的復(fù)制(reproduction)和交叉(crossover,即基因分離,基因組合和基因連鎖互換)的操作時(shí)其性狀的遺傳得到選擇和控制。生物的遺傳特性,使生物界的物種能保持相對(duì)的穩(wěn)定;生物的變異特性,使生物個(gè)體產(chǎn)生新的性狀,以至于形成了新的物種(量變積累為質(zhì)變),推動(dòng)了生物的進(jìn)化和發(fā)展。
遺傳學(xué)算法和遺傳學(xué)中的基礎(chǔ)術(shù)語(yǔ)比較
| 染色體(chromosome) |
數(shù)據(jù),數(shù)組,序列 |
| 基因(gene) |
單個(gè)元素,位 |
| 等位基因(allele) |
數(shù)據(jù)值,屬性,值 |
| 基因座(locus) |
位置,iterator位置 |
| 表現(xiàn)型(phenotype) |
參數(shù)集,解碼結(jié)構(gòu),候選解 |
| 遺傳隱匿(epistasis) |
非線性 |
染色體又可以叫做基因型個(gè)體(individuals),一定數(shù)量的個(gè)體組成了群體(population),群體中個(gè)體的數(shù)量叫做群體大小。各個(gè)個(gè)體對(duì)環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)
遺傳算法的準(zhǔn)備工作:
1)數(shù)據(jù)轉(zhuǎn)換操作,包括表現(xiàn)型到基因型的轉(zhuǎn)換和基因型到表現(xiàn)型的轉(zhuǎn)換。前者是把求解空間中的參數(shù)轉(zhuǎn)化成遺傳空間中的染色體或者個(gè)體(encoding),后者是它的逆操作(decoding)
2)確定適應(yīng)度計(jì)算函數(shù),可以將個(gè)體值經(jīng)過(guò)該函數(shù)轉(zhuǎn)換為該個(gè)體的適應(yīng)度,該適應(yīng)度的高低要能充分反映該個(gè)體對(duì)于解得優(yōu)秀程度。非常重要的過(guò)程！
遺傳算法的基本步驟
遺傳算法是具有"生成+檢測(cè)"(generate-and-test)的迭代過(guò)程的搜索算法。
基本過(guò)程為:
1)編碼,創(chuàng)建初始集團(tuán)
2)集團(tuán)中個(gè)體適應(yīng)度計(jì)算
3)評(píng)估適應(yīng)度
4)根據(jù)適應(yīng)度選擇個(gè)體
5)被選擇個(gè)體進(jìn)行交叉繁殖,
6)在繁殖的過(guò)程中引入變異機(jī)制
7)繁殖出新的集團(tuán),回到第二步
一個(gè)簡(jiǎn)單的遺傳算法的例子:求 [0,31]范圍內(nèi)的y=(x-10)^2的最小值
1)編碼算法選擇為"將x轉(zhuǎn)化為2進(jìn)制的串",串的長(zhǎng)度為5位。(等位基因的值為0 or 1)
2)計(jì)算適應(yīng)度的方法是:先將個(gè)體串進(jìn)行解碼,轉(zhuǎn)化為int型的x值,然后使用y=(x-10)^2作為其適應(yīng)度計(jì)算合適(由于是最小值,所以結(jié)果越小,適應(yīng)度也越好)
3)正式開(kāi)始,先設(shè)置群體大小為4,然后初始化群體 => (在[0,31]范圍內(nèi)隨機(jī)選取4個(gè)整數(shù)就可以,編碼)
4)計(jì)算適應(yīng)度Fi(由于是最小值,可以選取一個(gè)大的基準(zhǔn)線1000,Fi = 1000 - (x-10)^2)
5)計(jì)算每個(gè)個(gè)體的選擇概率.選擇概率要能夠反映個(gè)體的優(yōu)秀程度.這里用一個(gè)很簡(jiǎn)單的方法來(lái)確定選擇概率
P=Fi / TOTAL(Fi).
6)選擇.
根據(jù)所有個(gè)體的選擇概率進(jìn)行淘汰選擇.這里使用的是一個(gè)賭輪的方式進(jìn)行淘汰選擇.先按照每個(gè)個(gè)體的選擇概率創(chuàng)建一個(gè)賭輪,然后選取4次,每次先產(chǎn)生一個(gè)0-1的隨機(jī)小數(shù),然后判斷該隨機(jī)數(shù)落在那個(gè)段內(nèi)就選取相對(duì)應(yīng)的個(gè)體.這個(gè)過(guò)程中,選取概率P高的個(gè)體將可能被多次選擇,而概率低的就可能被淘汰.
下面是一個(gè)簡(jiǎn)單的賭輪的例子
13% 35% 15% 37%
----------|----------------------------|------------|-*-------------------------|
個(gè)體1 個(gè)體2 個(gè)體3 ^0.67 個(gè)體4
隨機(jī)數(shù)為0.67落在了個(gè)體4的端內(nèi).本次選擇了個(gè)體4.
被選中的個(gè)體將進(jìn)入配對(duì)庫(kù)(mating pool,配對(duì)集團(tuán))準(zhǔn)備開(kāi)始繁殖.
7)簡(jiǎn)單交叉
先對(duì)配對(duì)庫(kù)中的個(gè)體進(jìn)行隨機(jī)配對(duì).然后在配對(duì)的2個(gè)個(gè)體中設(shè)置交叉點(diǎn),交換2個(gè)個(gè)體的信息后產(chǎn)生下一代.
比如( | 代表簡(jiǎn)單串的交叉位置)
( 0110|1, 1100|0 ) --交叉--> (01100,11001)
( 01|000, 11|011 ) --交叉--> (01011,11000)
2個(gè)父代的個(gè)體在交叉后繁殖出了下一代的同樣數(shù)量的個(gè)體.
復(fù)雜的交叉在交叉的位置,交叉的方法,雙親的數(shù)量上都可以選擇.其目的都在于盡可能的培育出更優(yōu)秀的后
代
8)變異
變異操作時(shí)按照基因座來(lái)的.比如說(shuō)沒(méi)計(jì)算2萬(wàn)個(gè)基因座就發(fā)生一個(gè)變異(我們現(xiàn)在的每個(gè)個(gè)體有5個(gè)基因座.也就是說(shuō)要進(jìn)化1000代后才會(huì)在其中的某個(gè)基因座發(fā)生一次變異.)變異的結(jié)果是基因座上的等位基因發(fā)生了變化.我們這里的例子就是把0變成1或則1變成0.
至此,我們已經(jīng)產(chǎn)生了一個(gè)新的(下一代)集團(tuán).然后回到第4步,周而復(fù)始,生生不息下去:)
偽代碼實(shí)例(適合愛(ài)看代碼的朋友~):
//Init population
foreach individual in population
{
individual = Encode(Random(0,31));
}
while (App.IsRun)
{
//計(jì)算個(gè)體適應(yīng)度
int TotalF = 0;
foreach individual in population
{
individual.F = 1000 - (Decode(individual)-10)^2;
TotalF += individual.F;
}
//------選擇過(guò)程,計(jì)算個(gè)體選擇概率-----------
foreach individual in population
{
individual.P = individual.F / TotalF;
}
//選擇
for(int i=0;i<4;i++)
{
//SelectIndividual(float p)是根據(jù)隨機(jī)數(shù)落在段落計(jì)算選取哪個(gè)個(gè)體的函數(shù)
MatingPool[i] = population[SelectIndividual(Random(0,1))];
}
//-------簡(jiǎn)單交叉---------------------------
//由于只有4個(gè)個(gè)體,配對(duì)2次
for(int i=0;i<2;i++)
{
MatingPool.Parents[i].Mother = MatingPool.RandomPop();
MatingPool.Parents[i].Father = MatingPool.RandomPop();
}
//交叉后創(chuàng)建新的集團(tuán)
population.Clean();
foreach Parent in MatingPool.Parents
{
//注意在copy 雙親的染色體時(shí)在某個(gè)基因座上發(fā)生的變異未表現(xiàn).
child1 = Parent.Mother.DivHeader + Parent.Father.DivEnd;
child2 = Parent.Father.DivHeader + Parent.Mother.DivEnd;
population.push(child1);
population.push(child2);
}
}
小結(jié):
遺傳算法中最重要的過(guò)程就是選擇和交叉。
選擇要能夠合理的反映"適者生存"的自然法則，而交叉必須將由利的基因盡量遺傳給下一代(這個(gè)算法很關(guān)鍵！)
還有就是編碼的過(guò)程要能夠使編碼后的染色體能充分反映個(gè)體的特征并且能夠方便計(jì)算。
這篇文章是原來(lái)學(xué)習(xí)的一些回憶的整理,因?yàn)樽罱獙?shí)用了.不正確的地方還希望大家多多指出~