linux小組分享會_遺傳算法

遺傳算法初步
維基百科：
https://zh.wikipedia.org/wiki/%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95

遺傳算法（英語：genetic algorithm (GA) ）是計算數學中用於解決最佳化的搜索算法，是進化算法的一種。進化算法最初是借鑒了進化生物學中的一些現象而發展起來的，這些現象包括遺傳、突變、自然選擇以及雜交等。
遺傳算法通常實現方式為一種計算機模擬。對於一個最優化問題，一定數量的候選解（稱為個體）可抽象表示為染色體，使種群向更好的解進化。傳統上，解用二進制表示（即0和1的串），但也可以用其他表示方法。進化從完全隨機個體的種群開始，之後一代一代發生。在每一代中評價整個種群的適應度，從當前種群中隨機地選擇多個個體（基於它們的適應度），通過自然選擇和突變產生新的生命種群，該種群在算法的下一次迭代中成為當前種群。

遺傳算法的機理

在遺傳算法裡，優化問題的解被稱為個體，它表示為一個變量序列，叫做染色體或者基因串。染色體一般被表達為簡單的字符串或數字串，不過也有其他的依賴於特殊問題的表示方法適用，這一過程稱為編碼。首先，算法隨機生成一定數量的個體，有時候操作者也可以干預這個隨機產生過程，以提高初始種群的質量。在每一代中，都會評價每一個體，並通過計算適應度函數得到適應度數值。按照適應度排序種群個體，適應度高的在前面。這裡的“高”是相對於初始的種群的低適應度而言。
下一步是產生下一代個體並組成種群。這個過程是通過選擇和繁殖完成，其中繁殖包括交配（crossover，在算法研究領域中我們稱之為交叉操作）和突變（mutation）。選擇則是根據新個體的適應度進行，但同時不意味著完全以適應度高低為導向，因為單純選擇適應度高的個體將可能導致算法快速收斂到局部最優解而非全局最優解，我們稱之為早熟。作為折中，遺傳算法依據原則：適應度越高，被選擇的機會越高，而適應度低的，被選擇的機會就低。初始的數據可以通過這樣的選擇過程組成一個相對優化的群體。之後，被選擇的個體進入交配過程。一般的遺傳算法都有一個交配概率（又稱為交叉概率），范圍一般是0.6~1，這個交配概率反映兩個被選中的個體進行交配的概率。例如，交配概率為0.8，則80%的“夫妻”會生育後代。每兩個個體通過交配產生兩個新個體，代替原來的“老”個體，而不交配的個體則保持不變。交配父母的染色體相互交換，從而產生兩個新的染色體，第一個個體前半段是父親的染色體，後半段是母親的，第二個個體則正好相反。不過這裡的半段並不是真正的一半，這個位置叫做交配點，也是隨機產生的，可以是染色體的任意位置。再下一步是突變，通過突變產生新的“子”個體。一般遺傳算法都有一個固定的突變常數（又稱為變異概率），通常是0.1或者更小，這代表變異發生的概率。根據這個概率，新個體的染色體隨機的突變，通常就是改變染色體的一個字節（0變到1，或者1變到0）。
經過這一系列的過程（選擇、交配和突變），產生的新一代個體不同於初始的一代，並一代一代向增加整體適應度的方向發展，因為總是更常選擇最好的個體產生下一代，而適應度低的個體逐漸被淘汰掉。這樣的過程不斷的重復：評價每個個體，計算適應度，兩兩交配，然後突變，產生第三代。周而復始，直到終止條件滿足為止。一般終止條件有以下幾種：
進化次數限制；
計算耗費的資源限制（例如計算時間、計算占用的內存等）；
一個個體已經滿足最優值的條件，即最優值已經找到；
適應度已經達到飽和，繼續進化不會產生適應度更好的個體；
人為干預；
以及以上兩種或更多種的組合。

算法

選擇初始生命種群循環
評價種群中的個體適應度
以比例原則（分數高的挑中概率也較高）選擇產生下一個種群（輪盤法（roulette
wheel selection）、競爭法（tournament selection）及等級輪盤法（Rank
Based Wheel Selection））。不僅僅挑分數最高的的原因是這麼做可能收斂到局部的最佳點，而非整體的。改變該種群（交叉和變異）
直到停止循環的條件滿足
個人理解：
所謂遺傳算法，是一種隨機化算法，像這類隨機化算法是從平時生活中總結出來的，而遺傳算法就是從生物的遺傳之中總結出來的，其思想與生物遺產類似，具體代碼可以根據不同問題進行改變。
經典例題：旅行商問題（TSP）
假設有一個旅行商人要拜訪N個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，
而且最後要回到原來出發的城市。
路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。
算法介紹：
根據達爾文的進化論，我們可以總結出遺傳算法的一般步驟：
達爾文進化論：
1.評估每條染色體所對應個體的適應度。
2.遵照適應度越高，選擇概率越大的原則，從種群中選擇兩個個體作為父方和母方。
3.抽取父母雙方的染色體，進行交叉，產生子代。
4.對子代的染色體進行變異。
5.重復2，3，4步驟，直到新種群的產生。
遺傳算法步驟：
1. 初始化 t←0進化代數計數器；T是最大進化代數；隨機生成M個個體作為初始群體 P（t）；
2. 個體評價 計算P（t）中各個個體的適應度值；
3. 選擇運算 將選擇算子作用於群體；
4. 交叉運算 將交叉算子作用於群體；
5. 變異運算 將變異算子作用於群體，並通過以上運算得到下一代群體P（t + 1）;
6. 終止條件判斷 t≦T：t← t+1 轉到步驟2；
t>T：終止 輸出解。 、
▲Procedures GA： 偽代碼
begin
initialize P(0);
t = 0; //t是進化的代數，一代、二代、三代...
while(t <= T) do
for i = 1 to M do //M是初始種群的個體數
Evaluate fitness of P(t); //計算P（t）中各個個體的適應度
end for
for i = 1 to M do
Select operation to P(t); //將選擇算子作用於群體
end for
for i = 1 to M/2 do
Crossover operation to P(t); //將交叉算子作用於群體
end for
for i = 1 to M do
Mutation operation to P(t); //將變異算子作用於群體
end for
for i = 1 to M do
P(t+1) = P(t); //得到下一代群體P（t + 1）
end for
t = t + 1; //終止條件判斷 t≦T：t← t+1 轉到步驟2
end while
end
這裡的一些專業術語會在下面的程序中具體介紹到。
下面來看代碼，其中有較詳細注釋：

/*************************************************************************
	> File Name: yichuan.cpp
	> Author:chudongfang 
	> Mail:[email protected] 
	> Created Time: 2016年06月19日 星期日 23時50分57秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#define INF (1ll<<60)-1

#define city_num    10//城市的數目
#define unit_num    100//種群中個體的數目
#define probability 60//變異概率
#define genmax      100//最大產生代數
#define group_num   100//產生種群數量

using namespace std;
typedef long long ll;

typedef struct individual //一個個體
{
	int path[city_num];//個體的路徑
    int lenth;         //路徑的長度
}INDI;

typedef struct unit//一個種群
{
    INDI group[unit_num]; //數組存儲個體
    INDI best;            //最優個體
    int  best_gen;        //最優個體所在的代數
    int  cur_gen;         //種群當前的代數
}UNIT;

//1.初始化t←0進化代數計數器；genmax是最大進化代數；隨機生成unit_num個個體作為初始群體P(t)；
void init();

//2.個體評價
void assess();

//3.選擇運算 將選擇算子作用於群體
void choose(int gen);

//4.交叉運算 將交叉算子作用於群體，保留較優個體，淘汰較差個體
void cross();

//5.變異運算 將變異算子作用於群體，並通過以上運算得到下一代群體p(t+1)
void mutation();

//總調用函數，決定一個種群的進化
void sovel();

//子模塊
INDI  cross_once(int father,int mother);
void mutation_one(int x);

//打印，供測試用
void print();

//城市距離表，鄰接矩陣方式儲存無向圖
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}
};

//創建一個種群
UNIT  Group;

//儲存每個種群進化的結果
INDI  bestsovel[105];

//在這裡創建了多個種群，這樣使得解更具有准確性。
int main(int argc,char *argv[])
{
    //時間種子產生隨機數
	srand(time(0));

    //對產生的種群進行一一求解
    for(int i=0;i<group_num;i++)
    {
        sovel();
        bestsovel[i]=Group.best;
    }

    //輸出每個種群的最優個體（解）
    for(int i=0;i<group_num;i++)
        printf("%dth=%d\n",i,bestsovel[i].lenth);
    
    //排序，並輸出所有種群的最優解
    INDI t;
    for(int i=0;i<group_num;i++)
    {
        for(int j=i;j<group_num;j++)
        {
            if(bestsovel[i].lenth>bestsovel[j].lenth)
            {
                t=bestsovel[i];
                bestsovel[i]=bestsovel[j];
                bestsovel[j]=t;
            }
        }
    }
    

    printf("最優解：");
    for(int i=0;i<city_num;i++)
        printf("%4d",bestsovel[0].path[i]);

    printf("\n最優值：%d",bestsovel[0].lenth);

    return 0;
}

//對一個種群進行求解。
void sovel()
{    
    init();
    for(int  i=1;i<=genmax;i++) //種群繁雜代數
    {
        Group.cur_gen=i;
        assess();               //評估
        choose(Group.cur_gen);  //找最優個體
        cross();                //交叉,優勝劣汰，保留較優個體，淘汰較差個體
        mutation();             //變異
    }
}

void init()
{
    Group.best.lenth=0x3f3f3f3f;//初始化一個很大的值，便於下面比較
    Group.best_gen=0;//記錄產生最好結果的代數
    Group.cur_gen=0;//當前代數為0
    
    //把每一個個體隨機初始化
    for(int i=0;i<unit_num;i++)//unit_num個個體
    {
        bool  flag[city_num]={0};//用來標記其是否已經儲存過
        for(int j=0;j<city_num;j++)
        {     
            int t=rand()%city_num;
            //保證每個數字不重復
            while(flag[t])
                t=rand()%city_num;
             
            flag[t]=true;
            Group.group[i].path[j]=t;
        }
    }
}

//個體評價
void assess()
{
    //計算出每個個體的適應度值，即其路徑長度
    for(int k=0;k<unit_num;k++)
    {
        int rel=0;
        for(int i=1;i<city_num;i++)//根據其經過的節點，計算其路徑
            rel+=length_table[Group.group[k].path[i-1]][Group.group[k].path[i]];
    
        rel+=length_table[Group.group[k].path[city_num-1]][Group.group[k].path[0]];
        Group.group[k].lenth=rel;
    }
}

//先進行排序，然後選擇出最優解
void choose(int gen)
{
    //進行排序
    INDI t;
    for(int i=0;i<unit_num;i++)
    {
        for(int j=i;j<unit_num;j++)
        {
            if(Group.group[i].lenth>Group.group[j].lenth)
            {
                t             =Group.group[i];
                Group.group[i]=Group.group[j];
                Group.group[j]=t;
            }
        }
    }
    
    //選出這個種群的最優個體，並儲存
    if(Group.best.lenth>Group.group[0].lenth)
    {
        Group.best.lenth=Group.group[0].lenth;
        for(int i=0;i<city_num;i++)
            Group.best.path[i]=Group.group[0].path[i];
        Group.best_gen        =gen;
    }
}

//對一個種群中的個體，按一定方式進行交叉運算,並淘汰掉一部分，保存較優個體
void cross()
{
    for(int i=unit_num/2;i<unit_num;i++)//很容易看出，這裡淘汰了後部分個體
        Group.group[i]=cross_once(i-unit_num/2,i-unit_num/2+1);
}

//交叉兩個個體
INDI  cross_once(int father,int mother)
{
    INDI son;
    int t;
    int pos=0;
    int l=rand()%city_num;//隨機生成兩個數
    int r=rand()%city_num;
    if(l>r)
    {
        t=l;
        l=r;
        r=t;
    }
    
    bool flag[city_num]={0};
        
    for(int i=l;i<=r;i++)
        flag[Group.group[father].path[i]]=true;

    for(int i=0;i<l;i++)
    {
        while(flag[Group.group[mother].path[pos]])
            pos++;
        son.path[i]=Group.group[mother].path[pos++];
    }
    
    //父親的一段全部放在兒子中
    for(int i=l;i<=r;i++)
        son.path[i]=Group.group[father].path[i];

    //母親的在不與父親的一段重復的情況下，把其元素放在兒子中
    for(int i=r+1;i<city_num;i++)
    {
        while(flag[Group.group[mother].path[pos]])
            pos++;
        son.path[i]=Group.group[mother].path[pos++];
    }
    
    return son;
}

//對一個種群的全部個體都進行變異運算
void mutation()
{
    for(int i=0;i<unit_num;i++)
    {
        mutation_one(i);
    }
}

//對一個個體的變異運算
void mutation_one(int x)
{
    int pro=rand()%100;
    if(pro>probability)  
        return ;
    //隨機生成兩個數
    int first =rand()%city_num;
    int second=rand()%city_num;
    
    while(first==second)
        second=rand()%city_num;

    //進行交換
    int t;
    t=Group.group[x].path[first];
    Group.group[x].path[first]=Group.group[x].path[second];
    Group.group[x].path[second]=t;
}

void print()
{
    for(int i=0;i<unit_num;i++)
    {
        for(int j=0;j<city_num;j++)
        {
            printf("%4d",Group.group[i].path[j]);
        }
        printf("\n");
    }
    printf("\n\n\n");
}

運行結果：
0th=10
1th=10
2th=10
3th=10
4th=10
5th=10
6th=10
7th=10
8th=10
9th=10
10th=10
11th=10
12th=10
13th=10
14th=10
15th=10
16th=10
17th=10
18th=10
19th=10
20th=10
21th=10
22th=10
23th=10
24th=10
25th=10
26th=10
27th=10
28th=10
29th=10
30th=1811
31th=10
32th=10
33th=10
34th=10
35th=10
36th=10
37th=10
38th=10
39th=10
40th=10
41th=10
42th=10
43th=10
44th=10
45th=10
46th=10
47th=10
48th=10
49th=10
50th=10
51th=10
52th=10
53th=10
54th=10
55th=10
56th=10
57th=10
58th=10
59th=10
60th=10
61th=10
62th=10
63th=10
64th=10
65th=10
66th=1969
67th=1811
68th=10
69th=10
70th=10
71th=10
72th=10
73th=10
74th=10
75th=1969
76th=10
77th=10
78th=10
79th=10
80th=10
81th=10
82th=10
83th=10
84th=10
85th=10
86th=10
87th=10
88th=10
89th=10
90th=10
91th=10
92th=10
93th=10
94th=10
95th=10
96th=10
97th=10
98th=10
99th=10
最優解： 6 5 4 3 2 1 0 9 8 7
最優值：10
real 0m0.585s
user 0m0.580s
sys 0m0.004s
參數分析：
在這裡，以下參數越大其結果越精確，不過其耗時也相應變大，所以這裡要充分衡量其參數大小，以便於在耗時較少的情況下的到更優的解。

#define unit_num    100//種群中個體的數目
#define probability 60//變異概率
#define genmax      100//最大產生代數
#define group_num   100//產生種群數量

簡單總結一下遺傳算法，遺傳算法是一個根據生物進化的過程中總結出來的，其與生物進化相似，優勝劣汰，遺傳變異。其大概就分為：初始化、個體評估、選擇、交叉、變異這幾個過程，可以根據具體不同的問題，編不同的程序，但大致思想一樣。
以上內容不足之處請多多指教！
轉載請注明出處：http://write.blog.csdn.net/postedit/51720607