當前位置：首頁 > 编程资源 > 综合教程 >内容正文

综合教程

遗传算法(GA)入门知识梳理(超详细)

發布時間：2023/12/3 综合教程 29 生活家

生活随笔收集整理的這篇文章主要介紹了遗传算法(GA)入门知识梳理(超详细) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

一、遺傳算法的生物背景

二、遺傳算法(GA)思想

2.1遺傳算法的組成

2.2編碼

2.3適應度函數

2.4遺傳算子

2.4 運行參數

三、基本遺傳算法(SGA)偽代碼

3.1算法流程圖

3.2 算法偽代碼

四、遺傳算法的優化、應用前景

4.2 遺傳算法的優化

4.3 遺傳算法的應用

五、遺傳算法實例分析

一、遺傳算法的生物背景

生物在自然界中生存繁衍,顯示出了其對自然環境的優異自適應能力.遺傳算法(Genetic Algorithms,簡稱GA)就是對生物遺傳和進化過程的計算機模擬.它是一種自適應全局優化概率搜索算法,于1980年左右正式誕生.

首先我們要知道,遺傳算法是基于生物進化理論而產生的,因此作為遺傳算法生物背景的介紹,下面的概念有必要了解:

種群(Population):生物進化以群體形式進行,這樣的一個群體稱種群;
個體:組成種群的單個生物;
基因(Gene):一個遺傳因子;
染色體(Chromosome):包含一組的基因;
遺傳與變異:新個體會遺傳父母雙方各一部分的基因,同時有一定的幾率發生基因變異;
選擇(Selection):按一定概率從種群中選擇若干個體,選擇過程是基于適應度的優勝劣汰;
交叉(Crossover):兩個染色體某一相同位置處的DNA被切斷,然后兩者交叉組合形成兩個新的? ? ? ? ? ? ? ? ? ? ? ? ? ? ?染色體;
編碼(Coding):DNA中遺傳信息的排列,是從表現型到基因型的映射;
解碼(Decoding):基因型到表現型的映射;

按照達爾文進化理論,物種生存競爭,適者生存,對環境適應度高的、牛b的個體參與繁殖的機會比較多,后代就會越來越多,適應度低的個體參與繁殖的機會比較少,后代就會越來越少。進一步概括,就是繁殖過程,會發生基因交叉(Crossover),基因突變(Mutation).適應度(Fitness)低的個體會逐步淘汰,而適應度高的個體會越來越多.那么經過N代的自然選擇后,保存下來的個體都是適應度高的,其中很可能包含那個史上適應度最高的個體.

說到這里,善于思考的你一定想到如果把適應度比作一個函數的函數值,而將n個個體比作該函數在給定區間上的部分自變量的值,那么遺傳算法不就相當于搜索該區間上令函數取的最值(適應度最大)的自變量(個體)的值嘛,沒錯,這正是遺傳算法的一方面應用,我們在后文中會有具體的實例來向你展示算法到底是怎么做到的.

二、遺傳算法(GA)思想

2.1遺傳算法的組成

1.編碼(產生初始種群)

2.適應度函數

3.遺傳算子(選擇,交叉,變異)

4.運行參數

借鑒生物進化論,遺傳算法將要解決的問題模擬成一個生物進化過程,通過復制,交叉,變異等操作產生下一代的解,并逐步淘汰掉適應度函數值低的解,增加適應度函數值高的解,這樣進化N代后就會進化出適應度函數值很高的個體.

舉個例子,用遺傳算法解決"0-1背包問題"的思路:0-1背包的解可以編碼成一串0-1字符串(0:不取,1:取);首先,隨機產生m個0-1字符串,然后評價這些字符串作為0-1背包問題的價值的大小;再從中隨機選擇一部分字符串通過交叉、變異操作產生下一代m個字符串,而且價值較高的解被選中的概率比較高,這樣經過n代的進化后就會產生出0-1背包的一個"近似最優解".

作為遺傳算法(GA)的入門,我們應做到掌握基本遺傳算法(SGA),并了解相應拓展.下面我將著重講解基本遺傳算法(SGA),兼并相應拓展

2.2編碼

正如研究基因是從染色體入手的,染色體也就是基因的串,編碼也就是基因的編碼,需要將問題的解編碼成字符串的形式才能使用遺傳算法.前輩們研究出了很多種編碼方法,其中最常用的編碼方式是二進制編碼(SGA的編碼方式),即將問題的解編碼成二進制位數組的形式.例如,問題的解是整數,那么可以就將其編碼成二進制數組的形式.將0-1字符串作為0-1背包問題的解就屬于二進制編碼(例如01001就表示了2號和5號裝入背包,其他的不裝入).基因能夠在一定意義上包含它所代表的的問題的解,不同的編碼方式往往取決于問題本身.下面再簡單介紹幾種常用的編碼方式:

1.二進制編碼:正如上文說到,基本遺傳算法采用二進制編碼,這是將基因用0和1表示的方式

2.互換編碼:(用于解決排序問題,如TSP問題和調度問題),在TSP問題中,一串基因編碼用來表示遍歷的城市序列,如:651234,表示六個城市,先經過城市6,再經過城市5.以此類推.

3.樹形編碼:(用于解決遺傳規劃中的演化編程或者表示),例如問題:給出多個輸入和輸出,要求寫出一個函數使得每個輸入盡可能進地映射為輸出.則基因就是樹形結構中的一些函數.

2.3適應度函數

適應度函數(Fitness Function):用于評價某個染色體或者個體的適應度,用f(x)表示.有時需要區分染色體的適應度函數和問題的目標函數.例如:0-1背包問題的目標函數是所取的物品的價值,但將物品價值作為染色體的適應度函數可能并不一定合適.適應度函數與目標函數是正相關的,可對目標函數做一些變形來得到適應度函數.

2.4遺傳算子

遺傳算子分為選擇算子,交叉算子,變異算子

2.4.1選擇算子

遺傳算法使用選擇運算對個體進行優勝劣汰操作,基本遺傳算法(SGA)一種常用的選擇策略是"比例選擇",也就是個體被選中的概率與其適應度函數值成正比.假設群體的總個數是n,那么一個個體Xi被選中的概率就是f(Xi)/(f(X1)+f(X2)+......+f(Xn)).

比例選擇的實現算法就是所謂的'輪盤賭算法'(RWS),可以簡單地用以下代碼表示輪盤賭算法

/*

* 按設定的概率，隨機選中一個個體

* P[i]表示第i個個體被選中的概率

*/

int RWS()

{

m =0;

r =Random(0,1); //r為0至1的隨機數

for(i=1;i<=N; i++)

{

/* 產生的隨機數在m~m+P[i]間則認為選中了i

* 因此i被選中的概率是P[i]

*/

m=m+P[i];

if(r<=m) return i;

}

?2.4.2交叉算子

所謂交叉運算,是指兩個相互配對的染色體依據交叉概率Pc按照某種方式相互交換其部分基因,從而形成像個新的個體.交叉運算在GA中起關鍵作用,是產生新個體的主要方法.交叉的方法也有很多,基本遺傳算法(SGA)主要采用單點交叉法,即選擇一個交叉點,兩條染色體交換部分基因,構造兩條新染色體,例如:

交叉前：

染色體1: 00000|011100000000|10000

染色體2: 11100|000001111110|00101

交叉后：

染色體1: 00000|000001111110|10000

染色體2: 11100|011100000000|00101

染色體交叉是以一定概率發生的,這個概率記為Pc

另外,在這里介紹兩種其他交叉方法:

1.雙點交叉法:選擇兩個交叉點,子代基因在兩個交叉點間部分來自一個父代基因,部分來自另一個父代基因,如:

交叉前：

染色體1: 01 |0010| 11|00

染色體2: 11 |0111| 01|10

交叉后：

染色體1:11 |0010| 01|00

染色體2:01 |0111| 11|10

2.基于"與/或"的交叉法:

對父代按位"與"邏輯運算產生一子代A,按位"或"邏輯運算產生另一子代B.如:

交叉前:

染色體1: 01001011

染色體2: 11011101

交叉后：

染色體1: 01001001(A,兩個染色體與運算結果)

染色體2: 11011111(B,兩個染色體或運算結果)

2.4.3變異算子

變異是指依據變異概率將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。GA中的變異運算是產生新個體的輔助方法，它決定了GA的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。

注：變異概率Pm不能太小，這樣降低全局搜索能力；也不能太大，Pm > 0.5，這時GA退化為隨機搜索。

在繁殖過程，新產生的染色體中的基因會以一定的概率出錯，稱為變異。變異發生的概率記為Pm

變異算子也有很多,基本遺傳算法(GA)采用基本位變異算子

基本位變異算子:

基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為0，則變異操作將其變為1；反之，若原有基因值為1，則變異操作將其變為0。

變異前：

000001110000000010000

變異后：

000001110000100010000

2.4 運行參數

GA運行時參數的選擇應視具體問題而定,在一般情況下,GA都應包括的參數有:

1.種群規模M

種群規模指的是群體中個體的個數.實驗發現,種群規模并不是越大就能優化遺傳算法,種群的大小推薦使用20-30,一些研究表明,種群規模的大小取決于編碼的方法,具體說就是編碼串的大小.也就是說,如果基因編碼為32位時種群規模大小最好為32的話,那么當基因編碼為16位時種群的規模就變為原來的兩倍.

2.交叉率Pc

交叉率一般來說應該比較大,推薦使用80%-95%.

3.變異率Pm

變異率一般來說應該比較小,一般使用0.1%-1%最好.

4.終止進化代數T

設定一個值,作為進化的代數.

三、基本遺傳算法(SGA)偽代碼

3.1算法流程圖

3.2 算法偽代碼

/*

* Pc：交叉發生的概率

* Pm：變異發生的概率

* M：種群規模

* G：終止進化的代數

* Tf：進化產生的任何一個個體的適應度函數超過Tf，則可以終止進化過程

*/

初始化Pm，Pc，M，G，Tf等參數。隨機產生第一代種群Pop

do

{

　　計算種群Pop中每一個體的適應度F(i)。

　　初始化空種群newPop

do

{

　　　　根據適應度以比例選擇算法從種群Pop中選出2個個體

if ( random ( 0 , 1 ) < Pc )

{

　　　　　　對2個個體按交叉概率Pc執行交叉操作

}

if ( random ( 0 , 1 ) < Pm )

{

　　　　　　對2個個體按變異概率Pm執行變異操作

}

將2個新個體加入種群newPop中

} until ( M個子代被創建 )

用newPop取代Pop

}until ( 任何染色體得分超過Tf，或繁殖代數超過G )

四、遺傳算法的優化、應用前景

4.1遺傳算法的優缺點

優點:

群體搜索，易于并行化處理;

不是盲目窮舉，而是啟發式搜索;

適應度函數不受連續、可微等條件的約束，適用范圍很廣;

容易實現。一旦有了一個遺傳算法的程序，如果想解決一個新的問題，只需針對新的問題重新進行基因編碼就行；如果編碼方法也相同，那只需要改變一下適應度函數就可以了;

缺點:

全局搜索能力不強,很容易陷入局部最優解跳不出來;

將遺傳算法用于解決各種實際問題后，人們發現遣傳算法也會由于各種原因過早向目標函數的局部最優解收斂，從而很難找到全局最優解。

4.2 遺傳算法的優化

針對遺傳算法的缺點,人們想出來很多方法來優化遺傳算法,例如：針對原先的定長二進制編碼方案；提出了動態編碼、實數編碼等改進方案；針對按比例的選擇機制，提出了競爭選擇、按續挑選等改進方案；針對原先的一點交算子，提出了兩點交、多點交、均勻交等算子；針對原先遺傳算法各控制參數在進化過程中不變的情況，提出了退化遺傳算法、自適應遺傳算法等。這里講兩種經常用到的方法:

4.2.1災變

遺傳算法的局部搜索能力較強，但是很容易陷入局部極值。引用網上的一段原話: “那么如何解決遺傳算法容易陷入局部極值的問題呢？讓我們來看看大自然提供的方案。

六千五百萬年以前，恐龍和靈長類動物并存，恐龍在地球上占絕對統治地位，如果恐龍沒有滅絕靈長類動物是絕沒有可能統治地球的。正是恐龍的滅絕才使靈長類動物有了充分進化的余地，事實上地球至少經歷了5次物種大滅絕，每次物種滅絕都給更加高級的生物提供了充分進化的余地。所以要跳出局部極值就必須殺死當前所有的優秀個體，從而讓遠離當前極值的點有充分的進化余地。這就是災變的思想。”

災變就是殺掉最優秀的個體，這樣才可能產生更優秀的物種。那何時進行災變，災變次數又如何設定？

何時進行災變，可以采用災變倒計數的方式。如果n代還沒有出現比之前更優秀的個體時，可以發生災變。災變次數可以這樣來確定，如果若干次災變后產生的個體的適應度與沒災變前的一樣，可停止災變。

4.2.2精英主義

當利用交叉和變異產生新的一代時，我們有很大的可能把在某個中間步驟中得到的最優解丟失。

精英主義的思想是,在每一次產生新的一代時，首先把當前最優解原封不動的復制到新的一代中。然后按照前面所說的那樣做就行。精英主義方法可以大幅提高運算速度，因為它可以防止丟失掉找到的最好的解。

精英主義是基本遺傳算法的一種優化。為了防止進化過程中產生的最優解被交叉和變異所破壞，可以將每一代中的最優解原封不動的復制到下一代中。

4.3 遺傳算法的應用

遺傳算法的主要有以下八方面的應用：

（1）組合優化（2）函數優化（3）自動控制（4）生產調度

（5）圖像處理（6）機器學習（7）人工生命（8）數據挖掘

五、遺傳算法實例分析

我們先來看一個簡單地問題:求二次函數在區間[0,4]上的最大值

采用遺傳算法,可以找到相應的參數:

解空間:區間[0,4];

個體:區間[0,4]之間的點x;

適應度函數:由于目標函數值易計算,直接將目標函數作為適應度函數;

交叉概率:該問題Pc取1;

變異概率:Pm可取0.005;

問題求解:

1.編碼,確定種群規模

我們采用4位二進制編碼,這樣會產生16種不同的結果,相當于將區間分成了16份,每一份長度0.25;

取種群規模為4;初始種群為隨機產生的4個二進制字符串:

x1:0110

x2:1100

x3:0011

x4:0010

2.定義適應度函數

四個個體的適應度為:

f(x1)=f(6×0.25)=2.25

f(x2)=f(12×0.25)=9

f(x3)=f(3×0.25)=0.5625

f(x4)=f(2×0.25)=0.25

3.根據輪盤賭算法計算各個個體的選擇概率:

p(x1)=0.184

p(x2)=0.75

p(x3)=0.046

p(x4)=0.02

從0和1之間產生四個隨機數,如果隨機數的值小于p(x),則表明該個體被選中,進行一輪復制;假設隨機數為r1=0.13,r2=0.42,r3=0.36,r4=0.11,則產生的群體為

x1'=0110;

x2'=1100;

x3'=0110(x3被舍去,復制x1);

x4'=0010(x4被舍去,復制x2);

4.交叉

產生隨機數,若小于交叉概率Pc,則發生交叉,假設x1'與x2'的后兩位發生交換,得到種群

x1''=0100

x2''=1110

x3'=0110

x4'=0010

5.變異

產生隨機數.若小于變異概率Pm,則發生變異,假設x2''的最后以為發生變異,得到種群

x1''=0100

x2'''=1111

x3'=0110

x4'=0010

這樣進行一輪進化,得到的新種群

x1''=0100

x2'''=1111(適應度最高)

x3'=0110

x4'=0010

出現了適應度最高的個體x2''',將該字符串輸出,就得到相應區間[0,4]中的函數值最大的x=4

這是一個簡單的二次函數實例,有了這個思想,在實際操作中,我們更常用到的是二元函數的最值問題,例如:

求,的最大值

如以下代碼:

#pragma once//保證文件只被編譯一次
#include<random>
#include<vector>
#include<iostream>
#include<cmath>
#include<ctime>
#include <cstdlib>
#include <bitset>
#include<iomanip>
using namespace std;
const double PI = 3.141592653589793;//定義一個不可改變的常量值PI
const int Po_Size = 50;//種群規模
const int Ev_Algebra = 500;//進化代數
const double Ov_Probability = 0.850; //交叉概率,交叉概率用于判斷兩兩個體是否需要交叉
const double Va_Probability = 0.050;//變異概率,變異概率用于判斷任一個體是否需要變異
const int De_Variable = 2;//函數自變量的個數,如果要進行多元函數的最值求解，直接修改自變量數個De_Variable即可
const int length1 = 24;//精確到6位小數，用24位二進制編碼
const int length2 = 23;//精確到6位小數，用23位二進制編碼
class X_Range //自變量取值范圍類，適用于多個變量
{
private:double Upper;//變量的上界取值double Lower;//變量的下界取值
public:X_Range(double m_Upper, double m_Lower);//構造函數double GetUpper()const;//獲取變量上限double GetLower()const;//獲取變量下限
};
class Individual //定義個體類
{
private:double Variable[De_Variable];//存放變量x1,x2,x3........double Fitness;//適應值double ReFitness;//適應值概率double SumFitness;//累加概率，為輪盤轉做準備
public:Individual() {}//默認構造函數Individual(double* m_Variable);//構造函數double* GetVariable();//獲取變量值void ChaFitness(const double m_fitness);//修改適應值void ChaReFitness(const double m_ReFitness);//修改適應值概率void ChaSumFitness(const double m_SumFitness);//修改累加概率double GetFitness()const;//獲取適應值double GetReFitness()const;//獲取適應值概率double GetSumFitness()const;//獲取累加概率
};
void Initialize();//隨機初始化種群，得到第一代個體
void CaculaFitness();//計算個體的適應值
void CaculaReFitness();//計算個體的適應值概率
void CalculaSumFitness();//計算累加個體概率
void seclect();//種群選擇
double Scand();//隨機產生0到49的隨機整數
void crossing();//雜交
void variating();//變異
void genetic_algorithm();//遺傳算法
#include"GeneticAlgorithm.h"//包含頭文件
//自變量取值范圍向量和種群向量定義
const X_Range Range[De_Variable] = { X_Range(-3.0,12.1) ,X_Range(4.1,5.8) };//自變量（或者基因）x1,x2的取值范圍
vector<Individual> nowpopulation;//P(t)種群
vector<Individual> midpopulation;//中間種群，存放輪盤選擇后的優秀個體
vector<Individual> nextpopulation;//P(t+1)種群
//X_Range類實現
X_Range::X_Range(double m_Lower, double m_Upper) :Lower(m_Lower), Upper(m_Upper){}//X_Range類構造函數實現
double X_Range::GetUpper()const//獲取變量上限
{return Upper;
}
double X_Range::GetLower()const//獲取變量下限
{return Lower;
}
//Individual類實現
Individual::Individual(double* m_Variable)//構造函數
{for (int i = 0; i < De_Variable; i++)//用for循環自變量逐個賦值{if (m_Variable[i] >= Range[i].GetLower() && m_Variable[i] <= Range[i].GetUpper())//這里要進行自變量取值范圍判斷{Variable[i] = m_Variable[i];//自變量賦值}else//不滿足要求則發出出錯警告并返回{cerr << "自變量取值不滿足要求" << endl;exit(1);//停止程序，我會以隨機函數的方式生成自變量的值(基因值)，這里說明基因值不在規定范圍內}}//初始化時默認適應值等值為0this->Fitness = 0;this->ReFitness = 0;this->SumFitness = 0;
}
double* Individual::GetVariable()//獲取基因值
{return Variable;
}
double Individual::GetFitness()const//獲取適應值
{return Fitness;
}
double Individual::GetReFitness()const //獲取適應值概率
{return ReFitness;
}
double Individual::GetSumFitness()const//獲取累加概率
{return SumFitness;
}
void Individual::ChaFitness(const double m_fitness)//修改適應值
{this->Fitness = m_fitness;
}
void Individual::ChaReFitness(const double m_ReFitness)//修改適應值概率
{this->ReFitness = m_ReFitness;
}
void Individual::ChaSumFitness(const double m_SumFitness)//修改累加概率
{this->SumFitness = m_SumFitness;
}
//遺傳算法的準備工作
void Initialize()//隨機初始化種群，得到第一代種群
{
//產生指定范圍的隨機變量（基因）double X[Po_Size][De_Variable];//為了使程序可以滿足多元函數最值的計算，用矩陣保存產生的隨機數變量值for (int j = 0; j < De_Variable; j++){default_random_engine e(time(0));//引擎，生成隨機序列uniform_real_distribution<double> u(Range[j].GetLower(), Range[j].GetUpper());//分布for (int i = 0; i < Po_Size; i++)//先按列存儲隨機數{X[i][j] = u(e);//循環結束時，所有隨機值就保存在X矩陣中}}
//生成對象（染色體）并加入到初始種群中for (int i = 0; i < Po_Size; i++){double variable[De_Variable];for (int j = 0; j < De_Variable; j++){variable[j] = X[i][j];//按行保存}Individual Indivi(variable);//生成一個對象（染色體）nowpopulation.push_back(Indivi);//加入到種群population中}
}
void CaculaFitness()//計算個體的適應值
{//f(x1,x2) = 21.5+x1*sin(4pi*x1)+x2*sin(20pi*x2)）為適應度計算函數double fitness = 0;//臨時適應值double x[De_Variable];//臨時存儲自變量（基因）for (int i = 0; i < Po_Size; i++){for (int j = 0; j < De_Variable; j++)x[j] = nowpopulation.at(i).GetVariable()[j];//這樣更直觀fitness = 21.5 + x[0] * sin(4 * PI*x[0]) + 2 * sin(20 * PI*x[1]);//適應度計算nowpopulation.at(i).ChaFitness(fitness);//修改當前染色體的適應值}
}
void CaculaReFitness()//計算適應值概率
{double sum = 0;//適應值累加器double temp = 0;for (int i = 0; i < Po_Size; i++)//計算出適應值之和{sum += nowpopulation.at(i).GetFitness();}for (int j = 0; j < Po_Size; j++){temp = nowpopulation.at(j).GetFitness() / sum;//計算概率nowpopulation.at(j).ChaReFitness(temp);//修改個體的適應度概率}
}
void CalculaSumFitness()//計算累加個體概率
{double summation = 0;//累加器for (int k = 0; k < Po_Size; k++){summation += nowpopulation.at(k).GetReFitness();nowpopulation.at(k).ChaSumFitness(summation);//當前累加結果賦值}
}
void seclect() //種群選擇
{//隨機生生成0到1的小數double array[Po_Size];//隨機數保存變量default_random_engine e(time(0));//引擎，生成隨機序列uniform_real_distribution<double> u(0.0, 1.0); //分布for (int i = 0; i < Po_Size; i++)array[i] = u(e);//輪盤進行選擇for (int j = 0; j < Po_Size; j++){for (int i = 1; i < Po_Size; i++){if (array[j] < nowpopulation[i - 1].GetSumFitness()){midpopulation.push_back(nowpopulation.at(i - 1));//加入到中間種群}if (array[j] >= nowpopulation.at(i - 1).GetSumFitness() && array[j] <= nowpopulation.at(i).GetSumFitness()){midpopulation.push_back(nowpopulation.at(i));//加入到中間種群}}}nowpopulation.clear();//清空nowpopulation
}
double Scand() //隨機產生0到1的小數
{int N = rand() % 999;return double(N)/1000.0;;//隨機產生0到1的小數
}
void crossing()//雜交
{int num = 0;//記錄次數double corss = 0.0;//保存隨機產生的概率值srand((unsigned)time(NULL));//根據系統時間設置隨機數種子,設置一次隨機種子就行double array1[De_Variable], array2[De_Variable];//臨時存儲父親和母親的變量值while (num< Po_Size-1)//個體1與個體2雜交，個體3與個體4雜交......個體i和個體i+1雜交{//判斷雙親是否需要雜交，隨機生成一個0到1的小數，如果這個數大于雜交概率，則放棄雜交，直接遺傳給下一代，否則，對父母體進行雜交corss = Scand();if (corss <= Ov_Probability)//如果corss小于等于雜交概率Ov_Probability就進行單點雜交{//首先尋找對應下標的個體并且保存for (int i = 0; i < De_Variable; i++){array1[i] = midpopulation.at(num).GetVariable()[i];//父親的自變量array2[i] = midpopulation.at(num + 1).GetVariable()[i];//母親自變量}int localx1, localx2;//記錄基因交叉點的位置int corssx1[length1], corssx2[length2];//作為交換基因的數組double newx1[2], newx2[2];//分別用來保存基因交換后所對應自變量值bool p1 = true, p2 = true;//然后對雙親變量進行編碼并且進行單點雜交for (int j = 0; j < De_Variable; j++)//array1的x1編碼之后和array2的x1編碼后進行單點雜交，以此類推{if (j == 0)//x1進行編碼并且雜交{bitset<length1> array1b1((array1[j] + 3.0)* pow(10, 6));//加上3.0形成一個unsigaed數之后在進行母體1的x1編碼bitset<length1> array2b1((array2[j] + 3.0)* pow(10, 6));//加上3.0形成一個unsigaed數之后在進行母體2的x1編碼//現在隨機生成0到length1-1的數，確定交叉點的位置localx1 = rand() % length1;//現在進行單點交叉，交換雙親localx1后面的基因for (int i = 0; i < localx1; i++)corssx1[i] = array1b1[i];for (int k = 0; k < localx1; k++)array1b1[k] = array2b1[k];for (int s = 0; s < localx1; s++)array2b1[s] = corssx1[s];//新值保存在newx1數組中，x1基因完成單點雜交操作newx1[0] = double(array1b1.to_ullong()) / pow(10, 6) - 3.0;newx2[0] = double(array2b1.to_ullong()) / pow(10, 6) - 3.0;//對新產生的值進行判斷，判斷是否超出范圍，如果超出范圍則不雜交if (newx1[0]< Range[0].GetLower() || newx1[0]>Range[0].GetUpper() || newx2[0]<Range[0].GetLower() || newx2[0]>Range[0].GetUpper()){p1 = false;break;}}if (j == 1)//x2進行編碼并且雜交{bitset<length2> array1b2((array1[j]) * pow(10, 6));//母體1的x2編碼bitset<length2> array2b2((array2[j]) * pow(10, 6));//母體2的x2編碼//現在隨機生成0到length2-1的數，確定交叉點的位置localx2 = rand() % length2;//現在進行單點交叉，交換雙親localx2后面的基因for (int i = 0; i < localx2; i++)corssx2[i] = array1b2[i];for (int k = 0; k < localx2; k++)array1b2[k] = array2b2[k];for (int s = 0; s < localx2; s++)array2b2[s] = corssx2[s];//新值保存在newx2數組中，x2基因完成單點雜交操作newx1[1] = double(array1b2.to_ullong()) / pow(10, 6);newx2[1] = double(array2b2.to_ullong()) / pow(10, 6);//對新產生的值進行判斷，判斷是否超出范圍，如果超出范圍則不雜交if (newx1[1]< Range[1].GetLower() || newx1[1]>Range[1].GetUpper() || newx2[1]<Range[1].GetLower() || newx2[1]>Range[1].GetUpper()){p2 = false;break;}}}if (p1 == true && p2 == true){Individual newchiled1(newx1);Individual newchiled2(newx2);nextpopulation.push_back(newchiled1);nextpopulation.push_back(newchiled2);}else//將原來的個體遺傳給下一代{nextpopulation.push_back(midpopulation.at(num));nextpopulation.push_back(midpopulation.at(num + 1));}}else//否則直接遺傳給下一代nextpopulation{nextpopulation.push_back(midpopulation.at(num));//生成一個新的個體并且加入到nextpopulation中nextpopulation.push_back(midpopulation.at(num + 1));}num += 2;}midpopulation.clear();//清空midpopulation
}
void variating()//變異
{int num = 0;while (num<Po_Size){double variation = Scand();//隨機產生一個0到1的小數，用于判斷是否進行變異if (variation <= Va_Probability)//如果variation小于變異系數，則需要進行變異{double x[2];bool p = true;int x1local, x2local;x[0] = nextpopulation.at(num).GetVariable()[0];x[1] = nextpopulation.at(num).GetVariable()[1];bitset<length1> array1((x[0]+ 3.0)* pow(10, 6));//x1編碼bitset<length2> array2(x[1]*pow(10,6));//x2編碼x1local = rand() % length1;//array1該位取反x2local = rand() % length2;//array2該位取反array1.flip(x1local);//改變array1 x1local位的狀態array2.flip(x2local);//改變array2 x2local位的狀態x[0] = double(array1.to_ullong()) / pow(10, 6) - 3.0;x[1] = double(array2.to_ullong()) / pow(10, 6);//判斷是否符合條件if (x[0]< Range[0].GetLower() || x[0]>Range[0].GetUpper() || x[1]<Range[1].GetLower() || x[1]>Range[1].GetUpper())p = false;if (!p)nowpopulation.push_back(nextpopulation.at(num));if (p){Individual newchiled(x);nowpopulation.push_back(newchiled);}}elsenowpopulation.push_back(nextpopulation.at(num));num++;}nextpopulation.clear();//清空nextpopulation
}
void genetic_algorithm()
{Initialize();//初始化種群,隨機生成第一代個體//進化500代for (int i = 0; i < Ev_Algebra; i++){CaculaFitness();//適應度計算CaculaReFitness();//適應度概率計算CalculaSumFitness();//計算累加個體概率seclect();//選擇crossing();//雜交variating();//變異}CaculaFitness();//適應度計算double maxfitness=nowpopulation.at(0).GetFitness();int maxid = 0;int k;for (k = 0; k < Po_Size; k++){if (maxfitness < nowpopulation.at(k).GetFitness()){maxfitness = nowpopulation.at(k).GetFitness();maxid = k;}}//進化500代之后輸出cout << "x1"<<setw(10)<<"x2" << setw(15)<<"Fitness" << endl;for (int j = 0; j < Po_Size; j++)cout<<nowpopulation.at(j).GetVariable()[0]<<setw(10)<<nowpopulation.at(j).GetVariable()[1] << setw(10) <<nowpopulation.at(j).GetFitness() << endl;cout << "x1=" << nowpopulation.at(maxid).GetVariable()[0] << " ，" << "x2=" << nowpopulation.at(maxid).GetVariable()[1] << "時取得最大值：" << maxfitness << endl;
}
int main()
{genetic_algorithm();system("pause");return 0;
}

運行結果:

總結

以上是生活随笔為你收集整理的遗传算法(GA)入门知识梳理(超详细)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：了解为什么这个直观的工具是您团队的通用团
下一篇： jstl视图_使用JSTL视图探索Spr