一、步驟：  二、重點： 1、編碼
由于遺傳算法不能直接處理問題空間的數(shù)據(jù)，所以我們必須將問題空間的數(shù)據(jù)映射成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，而算法程序是可以處理遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)的。比如現(xiàn)在要計算北京、天津、廣東、新疆這四個城市的一條最優(yōu)路徑，但算法程序不能夠直接處理北京、天津、廣東、新疆這些數(shù)據(jù)，所以我們得給它們編上號，北京（0）、天津（1）、廣東（2）、新疆（3），路徑（天津->新疆->北京->廣東）可以表示成基因型串結(jié)構(gòu)數(shù)據(jù)（1302），這樣算法程序只要直接處理它們的編號就行了。
（1）二進制編碼，基因用0或1表示（常用于解決01背包問題）
如：基因A：00100011010 (代表一個個體的染色體)
（2）互換編碼（用于解決排序問題，如旅行商問題和調(diào)度問題）
如旅行商問題中，一串基因編碼用來表示遍歷的城市順序，如：234517986，表示九個城市中，先經(jīng)過城市2，再經(jīng)過城市3，依此類推。
（3）樹形編碼（用于遺傳規(guī)劃中的演化編程或者表示）
如問題：給定了很多組輸入和輸出。請你為這些輸入輸出選擇一個函數(shù)，使得這個函數(shù)把每個輸入盡可能近地映射為輸出。
編碼方法：基因就是樹形結(jié)構(gòu)中的一些函數(shù)。
（4）值編碼 （二進制編碼不好用時，解決復雜的數(shù)值問題）（源代碼中使用類似此方法）
在值編碼中，每個基因就是一串取值。這些取值可以是與問題有關任何值：整數(shù)，實數(shù)，字符或者其他一些更復雜的東西。
2、適應度函數(shù)
遺傳算法對一個個體（解）的好壞用適應度函數(shù)值來評價，適應度函數(shù)值越大，解的質(zhì)量越好。適應度函數(shù)是遺傳算法進化過程的驅(qū)動力，也是進行自然選擇的唯一標準，它的設計應結(jié)合求解問題本身的要求而定。
如TSP問題，遍歷各城市路徑之和越小越好，這樣可以用可能的最大路徑長度減去實際經(jīng)過的路徑長度，作為該問題的適應度函數(shù)。
3、選擇
在進化中，適者生存，所以在遺傳算法運行過程中，會不斷地選擇優(yōu)者保留下來，同時也不斷地選擇劣者淘汰下去。選擇算子有很多種方法，以下是比較簡單常見的方法：
（1）排序選擇方法（源代碼中使用類似此方法）
排序選擇方法是指在計算每一個個體的適應度（源代碼中將路徑總長度當適應度）之后，根據(jù)適應度大小對個體排序，然后按照事先設置好的概率表按序分配給個體，作為個自的選擇概率。
（2）適應度比例方法
適應度比例方法是目前遺傳算法中最基本也是最常用的選擇方法，即各個個體的選擇概率和其適應度值成正比。
（3）最佳個體保留方法
即把群體中適應度最高的個體不進行交叉而直接復制到下一代。
4、交叉
生物進化的核心作用是生物遺傳基因的重組，相對應，遺傳算法的核心操作是交叉算子，所謂交叉是指兩個或兩個以上的父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。
（1）單交叉點法 （用于二進制編碼）
選擇一個交叉點,子代在交叉點前面的基因從一個父代基因那里得到,后面的部分從另外一個父代基因那里得到。
如：交叉前：
00000|01110000000010000
11100|00000111111000101
交叉后：
00000|00000111111000101
11100|01110000000010000
（2）雙交叉點法 （用于二進制編碼）
選擇兩個交叉點,子代基因在兩個交叉點間部分來自一個父代基因,其余部分來自于另外一個父代基因.
如：交叉前：
01 |0010| 11
11 |0111| 01
交叉后：
11 |0010| 01
01 |0111| 11
（3）基于“ 與/或 ”交叉法 （用于二進制編碼）
對父代按位"與”邏輯運算產(chǎn)生一子代A;按位”或”邏輯運算產(chǎn)生另一子代B。該交叉策略在解背包問題中效果較好 .
如：交叉前：
01001011
11011101
交叉后：
01001001
11011111
（4）單交叉點法 （用于互換編碼）
選擇一個交叉點，子代的從初始位置出發(fā)的部分從一個基因復制，然后在另一個基因中掃描，如果某個位點在子代中沒有，就把它添加進去。
如：交叉前：
87213 | 09546
98356 | 71420
交叉后：
87213 | 95640
98356 | 72104
（5）部分匹配交叉（PMX）法（用于互換編碼）
先隨機產(chǎn)生兩個交叉點，定義這兩點間的區(qū)域為匹配區(qū)域，并用交換兩個父代的匹配區(qū)域。
父代A：872 | 130 | 9546
父代B：983 | 567 | 1420 變?yōu)椋?br>
TEMP A: 872 | 567 | 9546
TEMP B: 983 | 130 | 1420
對于 TEMP A、TEMP Ｂ中匹配區(qū)域以外出現(xiàn)的數(shù)碼重復，要依據(jù)匹配區(qū)域內(nèi)的位置逐一進行替換。匹配關系：1<——>５?。?lt;——>６ ７<——>０
子代Ａ：802 | 567 | 9143
子代Ｂ：986 | 130 | 5427
（6）順序交叉法(OX) （用于互換編碼）
從父代Ａ隨機選一個編碼子串，放到子代Ａ的對應位置；子代Ａ空余的位置從父代Ｂ中按Ｂ的順序選?。ㄅc己有編碼不重復）。同理可得子代Ｂ。
父代A: 872 | 139 | 0546
父代B: 983 | 567 | 1420
交叉后：
子代A: 856 | 139 | 7420
子代B: 821 | 567 | 3904
（7）循環(huán)交叉（CX）（用于互換編碼）
CX同OX交叉都是從一個親代中取一些城市，而其它城市來自另外一個親代，但是二者不同之處在于：OX中來自第一個親代的編碼子串是隨機產(chǎn)生的，而CX卻不是，它是根據(jù)兩個雙親相應位置的編碼而確定的。
父代A：1 2 3 4 5 6 7 8 9
| | | | |
父代B：5 4 6 9 2 3 7 8 1
可得循環(huán)基因：1->5->2->4->9->1
用循環(huán)的基因構(gòu)成子代Ａ，順序與父代Ａ一樣
1 2 4 5 9
用父代Ｂ剩余的基因填滿子代Ａ：
1 2 6 4 5 3 7 8 9
子代Ｂ的編碼同理。（循環(huán)基因 5->1->9->4->2->5）
（8）兩交換啟發(fā)交叉(HGA)
兩交換啟發(fā)交叉方法的基本思想如下:
以8個城市的旅行商問題為例：設N個城市為1,2,3,4,5,6,7,8
隨機選出一對未匹配的雙親如下:
A = 3 7 2 6 4 8 1 5
B = 4 8 3 2 1 7 5 6
隨機選出初始城j=1(位置號),Sj=1(城市號),右轉(zhuǎn)動使1成為兩雙親的第一位置城市如下:
A1 = 1 5 3 7 2 6 4 8
B1 = 1 7 5 6 4 8 3 2
O1 = 1 × × × × × × ×
判斷因為d(1,5)＞d(1,7)則A1以7為中心右轉(zhuǎn)得如下中間代:
A2 = × 7 2 6 4 8 5 3
B2 = × 7 5 6 4 8 3 2
O2 = 1 7 × × × × × ×
從第2位開始繼續(xù)重復上述過程
判斷因為d(7,5)=d(7,2)則可任選5或2,A2以5為中心右轉(zhuǎn)得如下中間代:
A3 = × 7 5 3 2 6 4 8
B3 = × 7 5 6 4 8 3 2
O3 = 1 7 5 × × × × ×
如此反復得出
O = 1 7 5 3 2 6 4 8
（9）三交換啟發(fā)交叉(THGA)（源代碼中使用類似此方法）
三交換啟發(fā)交叉方法的基本思想如下:
選3個參加交配的染色體作為父代,以8個城市為例來說明這一過程,其中dij由前面的表1給出,父代染色體為
A?。健? 2 1 4 8 7 6 5
B?。健? 4 6 8 1 3 5 7
C?。健? 7 5 6 4 3 2 1
SUM1＝42,SUM2＝40,SUM3＝46(SUM1，SUM2，SUM3分別為這3種排法所走的距離總和數(shù)).
隨機選出初始城市j=1,Sj=3右轉(zhuǎn)動，使3成為3父代的第1位置.
A?。健? 2 1 4 8 7 6 5
B ＝ 3 5 7 2 4 6 8 1
C?。健? 2 1 8 7 5 6 4
由于d(3,2)＞d(3,5),所以有:
A?。健 痢? 2 1 4 8 7 6
B?。健 痢? 7 2 4 6 8 1
C?。健 痢? 6 4 2 1 8 7
由此規(guī)則計算可得:
O ＝ 3 5 7 6 8 4 2 1
5、變異
變異是指依據(jù)變異概率將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。GA中的變異運算是產(chǎn)生新個體的輔助方法，它決定了GA的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。
注：變異概率Pm不能太小，這樣降低全局搜索能力；也不能太大，Pm > 0.5，這時GA退化為隨機搜索。
（1）基本位變異算子（用于二進制編碼）
基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)?。
變異前：
000001110000000010000
變異后：
000001110001000010000
（2）逆轉(zhuǎn)變異算子（用于互換編碼）（源代碼中使用類似此方法）
在個體中隨機挑選兩個逆轉(zhuǎn)點，再將兩個逆轉(zhuǎn)點間的基因交換。
變異前：
1346798205
變異后：
1246798305
6、運行參數(shù)
GA運行時選擇的參數(shù)應該視解決的具體問題而定，到目前為止，還沒有一個適用于GA所有應用領域的關于算法參數(shù)的理論。下面是一般情況下使用GA時推薦的參數(shù)：
（1）交叉率
交叉率一般來說應該比較大，推薦使用80％-95％。
（2）變異率
變異率一般來說應該比較小，一般使用0.5％-1％最好。
（3）種群的規(guī)模
種群規(guī)模指的是群體中個體的個數(shù)。實驗發(fā)現(xiàn)，比較大的種群的規(guī)模并不能優(yōu)化遺傳算法的結(jié)果。種群的大小推薦使用20-30，一些研究表明，種群規(guī)模的大小取決于編碼的方法，具體的說就是編碼串（Encoded String）的大小。也就是說，如果說采用32位為基因編碼的時候種群的規(guī)模大小最好為32的話，那么當采用16位為基因編碼時種群的規(guī)模相應應變?yōu)樵瓉淼膬杀丁?br>
（4）遺傳運算的終止進化代數(shù)
個人的想法是，設定一個計數(shù)器，如果連續(xù)N代出現(xiàn)的最優(yōu)個體的適應度都一樣時，（嚴格的說應該是，連續(xù)N代子代種群的最優(yōu)個體適應度都<=父代最優(yōu)個性的適應度）可以終止運算。也可以簡單的根據(jù)經(jīng)驗固定進化的代數(shù)。
三、源代碼如下，已加詳細注釋
-
-
-
-
-
-
-
- #include "stdio.h"
- #include "string.h"
- #include "stdlib.h"
- #define city_num 10 //城市個數(shù)
- #define unit_num 50 //群體規(guī)模為50
- #define pc 0.9 //交叉概率為0.9
- #define pv 0.1 //變異概率為10%
- #define ps 0.6 //進行選擇時保留的比例
- #define genmax 15 //最大代數(shù)15
-
- typedef struct unit
- {
- int path[city_num];
- int length;
- }Unit;
- typedef struct node
- {
- int city;
- struct node *next;
- }Node;
- Unit group[unit_num];
- Unit bestone;
- int generation_num=0;
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- int length_table[10][10]={{0,1,1272,2567,1653,2097,1425,1177,3947,1},
- {1,0,1,2511,1633,2077,1369,1157,3961,1518},
- {1272,1,0,1,380,1490,821,856,3660,385},
- {2567,2511,1,0,1,2335,1562,2165,3995,933},
- {1653,1633,380,1,0,1,1041,1135,3870,456},
- {2097,2077,1490,2335,1,0,1,920,2170,1920},
- {1425,1369,821,1562,1041,1,0,1,4290,626},
- {1177,1157,856,2165,1135,920,1,0,1,1290},
- {3947,3961,3660,3995,3870,2170,4290,1,0,1},
- {1,1518,385,993,456,1920,626,1290,1,0}};
-
-
-
-
-
-
- Node *search_son(Node *p,int k)
- {
- while(p->next->city!=k)
- p=p->next;
- return p;
- }
-
- void Sort(Unit group[unit_num])
- {
- int i,j;
- Unit temp,*p1,*p2;
- for(j=1;j<=unit_num-1;j++)
- {
- for(i=1;i<=unit_num-1;i++)
- {
- p1=&group[i-1];
- p2=&group[i];
- if(p1->length>p2->length)
- {
- memcpy(&temp,p1,sizeof(Unit));
- memcpy(p1,p2,sizeof(Unit));
- memcpy(p2,&temp,sizeof(Unit));
- }
- }
- }
- if(group[0].length < bestone.length)
- memcpy(&bestone,&group[0],sizeof(Unit));
- }
-
- void Calculate_length(Unit *p)
- {
- int j;
- p->length=0;
- for(j=1;j<=city_num-1;j++)
- {
- p->length+=length_table[p->path[j-1]][p->path[j]];
- }
- p->length+=length_table[p->path[city_num-1]][p->path[0]];
- }
-
- int RandomInteger(int low,int high)
- {
- int rand_num;
- double d;
- d=(double)(rand()%100)/100.0;
- rand_num=(int)(d*(high-low+1))+low;
- return rand_num;
- }
-
- void Print_optimum(Unit group[unit_num],int k)
- {
- int i,j;
- Unit *p;
- printf("當前第 %d 代：\n",k);
- for(i=0;i<=unit_num-1;i++)
- {
- printf("第%2d代，個體%2d ：",k,i);
- p=&group[i];
- for(j=0;j<=city_num-1;j++)
- printf("%d ",p->path[j]);
- printf(" 總路徑長度為：%d \n",p->length);
- }
- }
-
- void Print_bestone(Unit *bestone)
- {
- int i;
- Unit *p=bestone;
- printf("\n\n最優(yōu)路徑為：\n");
- for(i=0;i<=city_num-1;i++)
- printf("%d-->",p->path[i]);
- printf("%d 總路徑長度為：%d \n",p->path[0],p->length);
- }
-
-
-
-
-
-
- void Cross_group(Unit *p1,Unit *p2,Unit *p3)
- {
- int i,j,k,Cross_group_point;
- int a,b,c;
- int son[city_num];
- Node *current1,*current2,*current3;
- Node *top1,*top2,*top3;
- Node *p;
-
- top1=current1=(Node *)malloc(sizeof(Node));
- top1->city=p1->path[0];
- top2=current2=(Node *)malloc(sizeof(Node));
- top2->city=p2->path[0];
- top3=current3=(Node *)malloc(sizeof(Node));
- top3->city=p3->path[0];
- for(i=1;i<city_num;i++)
- {
- current1->next=(Node *)malloc(sizeof(Node));
- current1=current1->next;
- current1->city=p1->path[i];
- current2->next=(Node *)malloc(sizeof(Node));
- current2=current2->next;
- current2->city=p2->path[i];
- current3->next=(Node *)malloc(sizeof(Node));
- current3=current3->next;
- current3->city=p3->path[i];
- }
- current1->next=top1;
- current2->next=top2;
- current3->next=top3;
- Cross_group_point=RandomInteger(0,city_num-1);
- while(Cross_group_point--)
- current1=current1->next;
- current2=search_son(top2,current1->next->city);
- current3=search_son(top3,current1->next->city);
- for(i=0;i<city_num;i++)
- {
- son[i]=current1->next->city;
- p=current1->next;
- current1->next=p->next;
- free(p);
- p=current2->next;
- current2->next=p->next;
- free(p);
- p=current3->next;
- current3->next=p->next;
- free(p);
- if(i==9)break;
- a=length_table[son[i]][current1->next->city];
- b=length_table[son[i]][current2->next->city];
- c=length_table[son[i]][current3->next->city];
- if(a<=b&&a<=c){
- current2=search_son(current2,current1->next->city);
- current3=search_son(current3,current1->next->city);
- }
- else if(b<=a&&b<=c){
- current1=search_son(current1,current2->next->city);
- current3=search_son(current3,current2->next->city);
- }
- else if(c<=a&&c<=b){
- current1=search_son(current1,current3->next->city);
- current2=search_son(current2,current3->next->city);
- }
- }
- memcpy(p1->path,son,sizeof(p1->path));
- Cross_group_point=RandomInteger(0,city_num-1);
- for(k=0,i=Cross_group_point;i<city_num;i++)
- p2->path[k++]=son[i];
- for(i=0;i<Cross_group_point;i++)
- p2->path[k++]=son[i];
- Cross_group_point=RandomInteger(0,city_num-1);
- for(k=0,i=Cross_group_point;i<city_num;i++)
- p3->path[k++]=son[i];
- for(i=0;i<Cross_group_point;i++)
- p3->path[k++]=son[i];
- Calculate_length(p1);
- Calculate_length(p2);
- Calculate_length(p3);
- }
-
- void Varation_group(Unit *group,int gen_num)
- {
- int flag,i,j,k,temp;
- Unit *p;
- flag=(gen_num>50)?(3*100*pv):(100*pv);
- while(flag--)
- {
- i=RandomInteger(0,unit_num-1);
- j=RandomInteger(0,city_num-1);
- k=RandomInteger(0,city_num-1);
- p=&group[i];
- temp=p->path[j];
- p->path[j]=p->path[k];
- p->path[k]=temp;
- Calculate_length(p);
- }
- }
-
- void Initial_bestone(Unit *bestone)
- {
- bestone->length=RAND_MAX;
- }
-
- void Initial_group(Unit *group)
- {
- int i,j,k;
- Unit *p;
- for(i=0;i<=unit_num-1;i++)
- {
- p=group+i;
- for(j=0;j<=city_num-1;j++)
- {
- k=0;
- if(j==0) p->path[j]=RandomInteger(0,city_num-1);
- else
- {
- p->path[j]=RandomInteger(0,city_num-1);
- while(k<j)
- {
- if(p->path[j]==p->path[k])
- {
- p->path[j]=RandomInteger(0,city_num-1);
- k=0;
- }
- else k++;
- }
- }
- }
- Calculate_length(p);
- }
- }
-
- void Evolution_group(Unit *group)
- {
- int i,j;
- int temp1,temp2;
- temp1=unit_num*(1-ps);
- temp2=unit_num*ps;
- for(i=1;i<=genmax;i++)
- {
-
- Sort(group);
- Print_optimum(group,i-1);
- for(j=0;j<=temp1-1;j++)
- memcpy(&group[j+temp2],&group[j],sizeof(Unit));
-
- for(j=0;j<unit_num-2;)
- {
- Cross_group(&group[j],&group[j+1],&group[j+2]);
- j+=3;
- }
-
- Varation_group(group,i);
- }
- Sort(group);
- Print_optimum(group,i-1);
- }
-
- int main()
- {
- srand((int)time(NULL));
- Initial_bestone(&bestone);
- Initial_group(group);
- Evolution_group(group);
- Print_bestone(&bestone);
- return 0;
- }
|
