有關遺傳算法

2019-11-17 05:21:57

字體：大中小

來源：轉載

供稿：網(wǎng)友

　　遺傳算法(Genetic Algorithm, GA)是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法，它借用了生物遺傳學的觀點，通過自然選擇、遺傳、變異等作用機制，實現(xiàn)各個個體的適應性的提高。這一點體現(xiàn)了自然界中"物競天擇、適者生存"的進化過程。

1962年Holland教授首次提出了GA算法的思想，從而吸引了大批的研究者，迅速推廣到優(yōu)化、搜索、機器學習等方面，并奠定了堅實的理論基礎。

用遺傳算法解決問題時，首先要對待解決問題的模型結構和參數(shù)進行編碼，一般用字符串表示，這個過程就將問題符號化、離散化了。也有在連續(xù)空間定義的GA(Genetic Algorithm in Continuous Space, GACS)，暫不討論。

一個串行運算的遺傳算法(Seguential Genetic Algoritm, SGA)按如下過程進行：

(1) 對待解決問題進行編碼；
(2) 隨機初始化群體X(0):=(x1, x2, … xn)；
(3) 對當前群體X(t)中每個個體xi計算其適應度F(xi)，適應度表示了該個體的性能好壞；
(4) 應用選擇算子產生中間代Xr(t)；
(5) 對Xr(t)應用其它的算子，產生新一代群體X(t+1)，這些算子的目的在于擴展有限個體的覆蓋面，體現(xiàn)全局搜索的思想；
(6) t:=t+1；假如不滿足終止條件繼續(xù)(3)。

GA中最常用的算子有如下幾種：

(1) 選擇算子(selection/rePRodUCtion): 選擇算子從群體中按某一概率成對選擇個體，某個體xi被選擇的概率Pi與其適應度值成正比。最通常的實現(xiàn)方法是輪盤賭(roulette wheel)模型。

(2) 交叉算子(Crossover): 交叉算子將被選中的兩個個體的基因鏈按概率pc進行交叉，生成兩個新的個體，交叉位置是隨機的。其中Pc是一個系統(tǒng)參數(shù)。

(3) 變異算子(Mutation): 變異算子將新個體的基因鏈的各位按概率pm進行變異，對二值基因鏈(0,1編碼)來說即是取反。

上述各種算子的實現(xiàn)是多種多樣的，而且許多新的算子正在不斷地提出，以改進GA的某些性能。系統(tǒng)參數(shù)(個體數(shù)n,基因鏈長度l,交叉概率Pc,變異概率Pm等)對算法的收斂速度及結果有很大的影響，應視具體問題選取不同的值。

GA的程序設計應考慮到通用性，而且要有較強的適應新的算子的能力。OOP中的類的繼續(xù)為我們提供了這一可能。定義兩個基本結構：基因(ALLELE)和個體(INDIVIDUAL)，以個體的集合作為群體類TPopulation的數(shù)據(jù)成員，而TSGA類則由群體派生出來，定義GA的基本操作。對任一個應用實例，可以在TSGA類上派生，并定義新的操作。

TPopulation類包含兩個重要過程：

FillFitness: 評價函數(shù)，對每個個體進行解碼(decode)并計算出其適應度值，具體操作在用戶類中實現(xiàn)。
Statistic: 對當前群體進行統(tǒng)計，如求總適應度sumfitness、平均適應度average、最好個體fmax、最壞個體fmin等。

SGA的結構及類定義如下(用C++編寫)：

typedef char ALLELE; // 基因類型
typedef struct{
ALLELE *chrom;
float fitness; // fitness of Chromosome
}INDIVIDUAL; // 個體定義

class TPopulation{ // 群體類定義
public:
int size; // Size of population: n
int lchrom; // Length of chromosome: l
float sumfitness, average;
INDIVIDUAL *fmin, *fmax;
INDIVIDUAL *pop;

TPopulation(int popsize, int strlength);
~TPopulation();
inline INDIVIDUAL &Individual(int i){ return pop[i];};
void FillFitness(); // 評價函數(shù)
virtual void Statistics(); // 統(tǒng)計函數(shù)
};

class TSGA : public TPopulation{ // TSGA類派生于群體類
public:
float pcross; // Probability of Crossover
float pmutation; // Probability of Mutation
int gen; // Counter of generation

TSGA(int size, int strlength, float pm=0.03, float pc=0.6):
TPopulation(size, strlength)
{gen=0; pcross=pc; pmutation=pm; } ;
virtual INDIVIDUAL& Select();
virtual void Crossover(INDIVIDUAL &parent1, INDIVIDUAL
&parent2,INDIVIDUAL &child1, INDIVIDUAL &child2);
virtual ALLELE Mutation(ALLELE alleleval);
virtual void Generate(); // 產生新的一代
};

用戶GA類定義如下：

class TSGAfit : public TSGA{

public:

TSGAfit(int size,float pm=0.0333,float pc=0.6)

:TSGA(size,24,pm,pc){};

void print();

};

由于GA是一個概率過程，所以每次迭代的情況是不一樣的；系統(tǒng)參數(shù)不同，迭代情況也不同。在實驗中參數(shù)一般選取如下：個體數(shù)n=50-200，變異概率Pm=0.03, 交叉概率Pc=0.6。變異概率太大，會導致不穩(wěn)定。

上一篇：CRC-16/CRC-32 程序代碼

下一篇：Unicode:寬字節(jié)字符集