C語言開發(fā)：有關遺傳算法
日期：09-26 來源：中國設計秀 作者：cnwebshow.com
關鍵字：c語言開發(fā)，編程開發(fā)
遺傳算法(Genetic Algorithm, GA)是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法，它借用了生物遺傳學的觀點，通過自然選擇、遺傳、變異等作用機制，實現(xiàn)各個個體的適應性的提高。這一點體現(xiàn)了自然界中"物競天擇、適者生存"的進化過程。
1962年Holland教授首次提出了GA算法的思想，從而吸引了大批的研究者，迅速推廣到優(yōu)化、搜索、機器學習等方面，并奠定了堅實的理論基礎。
用遺傳算法解決問題時，首先要對待解決問題的模型結(jié)構(gò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) 應用選擇算子產(chǎn)生中間代Xr(t)；
(5) 對Xr(t)應用其它的算子，產(chǎn)生新一代群體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等)對算法的收斂速度及結(jié)果有很大的影響，應視具體問題選取不同的值。
GA的程序設計應考慮到通用性，而且要有較強的適應新的算子的能力。OOP中的類的繼承為我們提供了這一可能。定義兩個基本結(jié)構(gòu)：基因(ALLELE)和個體(INDIVIDUAL)，以個體的集合作為群體類TPopulation的數(shù)據(jù)成員，而TSGA類則由群體派生出來，定義GA的基本操作。對任一個應用實例，可以在TSGA類上派生，并定義新的操作。
TPopulation類包含兩個重要過程：
FillFitness: 評價函數(shù)，對每個個體進行解碼(decode)并計算出其適應度值，具體操作在用戶類中實現(xiàn)。
Statistic: 對當前群體進行統(tǒng)計，如求總適應度sumfitness、平均適應度average、最好個體fmax、最壞個體fmin等。
SGA的結(jié)構(gòu)及類定義如下(用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(); // 產(chǎn)生新的一代
};
用戶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)定。
