| 導購 | 订阅 | 在线投稿
分享
 
 
 

有關遺傳算法

來源:互聯網網民  2008-06-01 01:47:48  評論

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

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

用遺傳算法解決問題時,首先要對待解決問題的模型結構和參數進行編碼,一般用字符串表示,這個過程就將問題符號化、離散化了。也有在連續空間定義的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),這些算子的目的在于擴展有限個體的覆蓋面,體現全局搜索的思想;

(6) t:=t+1;假如不滿足終止條件繼續(3)。

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

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

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

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

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

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

TPopulation類包含兩個重要過程:

FillFitness: 評價函數,對每個個體進行解碼(decode)並計算出其適應度值,具體操作在用戶類中實現。

Statistic: 對當前群體進行統計,如求總適應度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(); // 評價函數

virtual void Statistics(); // 統計函數

};

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是一個概率過程,所以每次叠代的情況是不一樣的;系統參數不同,叠代情況也不同。在實驗中參數一般選取如下:個體數n=50-200,變異概率Pm=0.03, 交叉概率Pc=0.6。變異概率太大,會導致不穩定。

 
特别声明:以上内容(如有图片或视频亦包括在内)为网络用户发布,本站仅提供信息存储服务。
 
  遺傳算法(Genetic Algorithm, GA)是近幾年發展起來的一種嶄新的全局優化算法,它借用了生物遺傳學的觀點,通過自然選擇、遺傳、變異等作用機制,實現各個個體的適應性的提高。這一點體現了自然界中"物競天擇、適者生存"的進化過程。 1962年Holland教授首次提出了GA算法的思想,從而吸引了大批的研究者,迅速推廣到優化、搜索、機器學習等方面,並奠定了堅實的理論基礎。 用遺傳算法解決問題時,首先要對待解決問題的模型結構和參數進行編碼,一般用字符串表示,這個過程就將問題符號化、離散化了。也有在連續空間定義的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),這些算子的目的在于擴展有限個體的覆蓋面,體現全局搜索的思想; (6) t:=t+1;假如不滿足終止條件繼續(3)。 GA中最常用的算子有如下幾種: (1) 選擇算子(selection/reprodUCtion): 選擇算子從群體中按某一概率成對選擇個體,某個體xi被選擇的概率Pi與其適應度值成正比。最通常的實現方法是輪盤賭(roulette wheel)模型。 (2) 交叉算子(Crossover): 交叉算子將被選中的兩個個體的基因鏈按概率pc進行交叉,生成兩個新的個體,交叉位置是隨機的。其中Pc是一個系統參數。 (3) 變異算子(Mutation): 變異算子將新個體的基因鏈的各位按概率pm進行變異,對二值基因鏈(0,1編碼)來說即是取反。 上述各種算子的實現是多種多樣的,而且許多新的算子正在不斷地提出,以改進GA的某些性能。系統參數(個體數n,基因鏈長度l,交叉概率Pc,變異概率Pm等)對算法的收斂速度及結果有很大的影響,應視具體問題選取不同的值。 GA的程序設計應考慮到通用性,而且要有較強的適應新的算子的能力。OOP中的類的繼續爲我們提供了這一可能。定義兩個基本結構:基因(ALLELE)和個體(INDIVIDUAL),以個體的集合作爲群體類TPopulation的數據成員,而TSGA類則由群體派生出來,定義GA的基本操作。對任一個應用實例,可以在TSGA類上派生,並定義新的操作。 TPopulation類包含兩個重要過程: FillFitness: 評價函數,對每個個體進行解碼(decode)並計算出其適應度值,具體操作在用戶類中實現。 Statistic: 對當前群體進行統計,如求總適應度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(); // 評價函數 virtual void Statistics(); // 統計函數 }; 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是一個概率過程,所以每次叠代的情況是不一樣的;系統參數不同,叠代情況也不同。在實驗中參數一般選取如下:個體數n=50-200,變異概率Pm=0.03, 交叉概率Pc=0.6。變異概率太大,會導致不穩定。
󰈣󰈤
王朝萬家燈火計劃
期待原創作者加盟
 
 
 
>>返回首頁<<
 
 
 
 
 
 熱帖排行
 
 
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有