正文 字體大�。� 中
算法設(shè)計(jì)：關(guān)于遺傳算法的研究 [整理] (2010-06-12 10:49:13)
標(biāo)簽： 算法設(shè)計(jì) 遺傳算法 基本原理 算法思想 研究 源代碼 it 分類： 算法之道
關(guān)于遺傳算法的研究
---July、06.12。
------------------
網(wǎng)絡(luò)上一大堆關(guān)于此問(wèn)題的文章，但大都是你抄我的，而后我抄你的。
沒(méi)有自己的思維和想法。
----------------------------------------------------------------------
遺傳算法的原理
遺傳算法GA把問(wèn)題的解表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解。然后，把這些假設(shè)解置于問(wèn)題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過(guò)交叉，變異過(guò)程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，它就是問(wèn)題的最優(yōu)解。
-----------------------------------------
遺傳算法的目的
典型的遺傳算法CGA(Canonical Genetic Algorithm)通常用于解決下面這一類的靜態(tài)最優(yōu)化問(wèn)題：
考慮對(duì)于一群長(zhǎng)度為L(zhǎng)的二進(jìn)制編碼bi，i＝1，2，…，n；有
bi∈{0,1}L
給定目標(biāo)函數(shù)f，有f(bi)，并且
0<f(bi)<∞
同時(shí)
f(bi)≠f(bi+1)
求滿足下式
max{f(bi)|bi∈{0,1}L} 的bi。
//很明顯，遺傳算法是一種最優(yōu)化方法，它通過(guò)進(jìn)化和遺傳機(jī)理，從給出的原始解群中，不斷進(jìn)化產(chǎn)生新的解，最后收斂到一個(gè)特定的串bi處，即求出最優(yōu)解。
------------------------------------------------
遺傳算法的基本原理
長(zhǎng)度為L(zhǎng)的n個(gè)二進(jìn)制串bi(i＝1，2，…，n)組成了遺傳算法的初解群，也稱為初始群體。在每個(gè)串中，每個(gè)二進(jìn)制位就是個(gè)體染色體的基因。根據(jù)進(jìn)化術(shù)語(yǔ)，對(duì)群體執(zhí)行的操作有三種：
1．選擇(Selection)
這是從群體中選擇出較適應(yīng)環(huán)境的個(gè)體。這些選中的個(gè)體用于繁殖下一代。故有時(shí)也稱這一操作為再生(Reproduction)。由于在選擇用于繁殖下一代的個(gè)體時(shí)，是根據(jù)個(gè)體對(duì)環(huán)境的適應(yīng)度而決定其繁殖量的，故而有時(shí)也稱為非均勻再生(differential reproduction)。
2．交叉(Crossover)
這是在選中用于繁殖下一代的個(gè)體中，對(duì)兩個(gè)不同的個(gè)體的相同位置的基因進(jìn)行交換，從而產(chǎn)生新的個(gè)體。
3．變異(Mutation)
這是在選中的個(gè)體中，對(duì)個(gè)體中的某些基因執(zhí)行異向轉(zhuǎn)化。在串bi中，如果某位基因?yàn)?，產(chǎn)生變異時(shí)就是把它變成0；反亦反之。
--------------------------------------------------------
遺傳算法思想：
(1) 初始化群體;
(2) 計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值;
(3) 按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將進(jìn)入下一代的個(gè)體;
(4) 按概率Pc進(jìn)行交叉操作;
(5) 按概率Pc進(jìn)行突變操作;
(6) 沒(méi)有滿足某種停止條件，則轉(zhuǎn)第(2)步，否則進(jìn)入(7)。
(7) 輸出種群中適應(yīng)度值最優(yōu)的染色體作為問(wèn)題的滿意解或最優(yōu)解。
程序的停止條件最簡(jiǎn)單的有如下二種：完成了預(yù)先給定的進(jìn)化代數(shù)則停止；種群中的最優(yōu)個(gè)體在連續(xù)若干代沒(méi)有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒(méi)有改進(jìn)時(shí)停止。
---- ----------------------------------------------------------
遺傳算法的步驟和意義
1．初始化
選擇一個(gè)群體，即選擇一個(gè)串或個(gè)體的集合bi，i=1，2，...n。這個(gè)初始的群體也就是問(wèn)題假設(shè)解的集合。一般取n＝30-160。
通常以隨機(jī)方法產(chǎn)生串或個(gè)體的集合bi,i＝1，2，...n。問(wèn)題的最優(yōu)解將通過(guò)這些初始假設(shè)解進(jìn)化而求出。
2．選擇
根據(jù)適者生存原則選擇下一代的個(gè)體。在選擇時(shí)，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。
給出目標(biāo)函數(shù)f，則f(bi)稱為個(gè)體bi的適應(yīng)度。以
f(bi)
P{選中bi}=------------------*n
求和f(bj)(j=1....n)
為選中bi為下一代個(gè)體的次數(shù)。
顯然．從上式可知：
(1)適應(yīng)度較高的個(gè)體，繁殖下一代的數(shù)目較多。
(2)適應(yīng)度較小的個(gè)體，繁殖下一代的數(shù)目較少；甚至被淘汰。
這樣，就產(chǎn)生了對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代。對(duì)于問(wèn)題求解角度來(lái)講，就是選擇出和最優(yōu)解較接近的中間解。
3．交叉
對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率P。在選中的位置實(shí)行交換。這個(gè)過(guò)程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。
例如有個(gè)體
S1=100101
S2=010111
選擇它們的左邊3位進(jìn)行交叉操作，則有
S1=010101
S2=100111
一般而言，交叉幌宰P。取值為0.25—0.75。
4．變異
根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對(duì)某些個(gè)體的某些位執(zhí)行變異。在變異時(shí)，對(duì)執(zhí)行變異的串的對(duì)應(yīng)位求反，即把1變?yōu)?，把0變?yōu)?。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2。
例如有個(gè)體S＝101011。
對(duì)其的第1，4位置的基因進(jìn)行變異，則有
S'=001111
單靠變異不能在求解中得到好處。但是，它能保證算法過(guò)程不會(huì)產(chǎn)生無(wú)法進(jìn)化的單一群體。因?yàn)樵谒械膫�(gè)體一樣時(shí)，交叉是無(wú)法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。也就是說(shuō)，變異增加了全局優(yōu)化的特質(zhì)。
5．全局最優(yōu)收斂(Convergence to the global optimum)
當(dāng)最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閥值，或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)，則算法的迭代過(guò)程收斂、算法結(jié)束。否則，用經(jīng)過(guò)選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到第2步即選擇操作處繼續(xù)循環(huán)執(zhí)行。
------------------------------------------------------------------------------------------------------
遺傳算法問(wèn)題的具體設(shè)計(jì)與研究
#define
popsize
100
//種群密度
#define
length1
10
#define
length2
10
//基因大小
#define
chromlength
length1+length2
//染色體大小
int
maxgeneration=100;
//遺傳的總代數(shù)
double
pc=0.3;
//交叉位概率
double
pm=0.05;
//變異概率
struct
individual
//定義個(gè)體形狀
{
char
chrom[chromlength+1];
//染色體
double
value;
//FG(x)值
double
fitness;
//適配值
};
int
generation;
//每一次計(jì)算代數(shù)
int
best_index;
//最佳值
struct individual
bestindividual;
//最佳個(gè)體
struct individual
currentbest;
struct individual
population[popsize]; //種群
void
generateinitialpopulation(void);
//初始化編碼函數(shù)：對(duì)每一個(gè)體（總數(shù)100）的染色體的每一個(gè)二進(jìn)制位（總為10位）
//用random(10)隨機(jī)產(chǎn)生一個(gè)0~9之間的整數(shù)，判斷，小于5這一位為 ” 0 ”，大于5則為 ” 1 ”。
void generatenextpopulation(void); //生成下一代基因的函數(shù)：選擇，交叉，變異。
void evaluatepopulation(void);
//統(tǒng)計(jì)函數(shù)：計(jì)算每一個(gè)體的FG(x)值，適配值，并找出每一代種群中的最佳值與最差值。
long decodechromosome(char*, int,
int);
//解碼函數(shù)：將20位無(wú)符號(hào)的二進(jìn)制數(shù)解碼成兩個(gè)有符號(hào)的十進(jìn)制數(shù)。
void calculateobjectvalue(void); //計(jì)算每一個(gè)體中的“FG(x)值函數(shù)。
void calculatefitnessvalue(void); //計(jì)算每一個(gè)體的適配值函數(shù)。
void findbestandworstindividual(void); //找出每一代中的最佳值與最差值函數(shù)
void performevolution(void); //保留最大適配值
void selectionoperator(void); //選擇復(fù)制函數(shù)
void crossoveroperator(void); //交叉函數(shù)
void mutationoperator(void); //變異函數(shù)
void outputtextreport(FILE *fp1, FILE *fp2); //輸出函數(shù)
void
main(void)
//主程序開始
{
FILE *fp1, *fp2;
fp1=fopen("show1.txt",
"w");
//顯示輸出結(jié)果
fp2=fopen("show2.txt", "w");
generation=0;
//從第0代開始
generateinitialpopulation();
//初始化隨機(jī)產(chǎn)生100個(gè)個(gè)體
evaluatepopulation();
//統(tǒng)計(jì)
while
(generation<maxgeneration)
//繼續(xù)計(jì)算直到最大代數(shù)
{
generation++;
generatenextpopulation();
evaluatepopulation();
performevolution();
outputtextreport(fp1,
fp2);
}
}
void
calculateobjectvalue(void);
//計(jì)算每一個(gè)體中的“FG(x)值函數(shù)：將染色體解碼（調(diào)用解碼函數(shù)）得出x1、x2值代入FG(x)公式中得出FG(x)值。
{
int i;
long temp1, temp2;
double x1, x2;
for(i=0;i<popsize;i++)
{
temp1=decodechromosome(population[i].chrom,
0, length1);
temp2=decodechromosome(population[i].chrom,
length1, length2);
x1=10.24*temp1/1023.0-5.12;
x2=10.24*temp2/1023.0-5.12;
population[i].value=(1+(x1+x2+1)*(x1+x2+1)*(19-14*x1+3*x1*x1-14*x2+6*x1*x2+3*x2*x2))*(30+(2*x1-3*x2)*(2*x1-3*x2)*(18-32*x1+12*x1*x1+48*x2-36*x1*x2+27*x2*x2));
}
}
void selectionoperator(void)
//選擇函數(shù)：利用輪盤賭法選擇個(gè)體
{
int i, index;
double p, sum=0.0;
double cfitness[popsize];
struct individual newpopulation[popsize];
for(i=0;i<popsize;i++)
sum+=population[i].fitness;
//計(jì)算總的適配值
for(i=0;i<popsize;i++)
cfitness[i]=population[i].fitness/sum;
//計(jì)算每一個(gè)體適配值復(fù)制的概率
for(i=1;i<popsize;i++)
cfitness[i]= cfitness[i-1]+
cfitness[i];
for(i=0;i<popsize;i++)
{
p=rand( )%1000/1000.0;
index=0;
while
(p>cfitness[index])
//隨機(jī)生成數(shù)p若大于復(fù)制概率，
index++;
//就進(jìn)行復(fù)制，經(jīng)選擇后復(fù)制生成
newpopulation[i]=population[index];
//子代*/
}
for(i=0;i<popsize;i++)
population[i]=newpopulation[i];
//將子代賦值給計(jì)算的這一代
}
void
crossoveroperator(void)
//交叉函數(shù)：對(duì)復(fù)制后的個(gè)體按交叉概率pc實(shí)施交叉操作
{
int i, j;
int index[popsize];
int point, temp;
double p;
char ch;
for(i=0;i<popsize;i++)
index[i]=i;
for(i=0;i<popsize;i++)
//隨機(jī)配對(duì)
{
point=random(popsize-i);
temp=index[i];
index[i]=index[point+i];
index[point+i]=temp;
}
for(i=0;i<popsize-1;i+=2)
{
p=rand()%1000/1000.0;
if(p<pc)
//交叉：生成隨機(jī)值p與pc相比較，小于pc值便交叉，實(shí)現(xiàn)了pc的作用。
{
point=random(chromlength-1)+1;
for(j=point;j<chromlength;j++)
{
ch=population[index[i]].chrom[j];
//產(chǎn)生一個(gè)20以內(nèi)的隨機(jī)數(shù)point，
population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
population[index[i+1]].chrom[j]=ch;
}
}
}
}
void
mutationoperator(void)
//變異函數(shù)
{
int i, j;
double p;
for(i=0;i<popsize;i++)
for(j=0;j<chromlength;j++)
{
p=rand()%1000/1000.0;
if(p<pm)
//變異：生成隨機(jī)值p與pm相比較，小于pm值則由
”0 ” 變成 ” 1 ” 或由 ” 1 ” 變成 ” 0 ”，實(shí)現(xiàn)了pm的作用。
population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';
}
}
//有待進(jìn)一步研究中。July、06.12。
分享
頂
閱讀┊ ┊ ┊┊ ┊打印┊
已投稿到：
排行榜 圈子
加載中，請(qǐng)稍候......
前一篇：排序問(wèn)題：直接插入排序的算法思想 [原創(chuàng)]
后一篇：排序問(wèn)題：選擇排序算法思想 [原創(chuàng)]
評(píng)論 重要提示：警惕虛假中獎(jiǎng)信息 帶你的博客進(jìn)入新時(shí)代 關(guān)注每日最熱門博客
發(fā)評(píng)論 Qing時(shí)代來(lái)臨，不容錯(cuò)過(guò) 這里有屬于你的小清新 關(guān)注每日最熱門博客
登錄名： 密碼： 找回密碼 注冊(cè)
昵 稱：
驗(yàn)證碼： 請(qǐng)點(diǎn)擊后輸入驗(yàn)證碼
以上網(wǎng)友發(fā)言只代表其個(gè)人觀點(diǎn)，不代表新浪網(wǎng)的觀點(diǎn)或立場(chǎng)。
< 前一篇排序問(wèn)題：直接插入排序的算法思想 [原創(chuàng)]
后一篇 >排序問(wèn)題：選擇排序算法思想 [原創(chuàng)]
