有關遺傳算法

遺傳算法(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。變異概率太大,會導致不穩定。

遺傳算法在黑盒測試中的應用
上海中科院上海小衛星工程部(200050) 陳 浩 劉海濤摘 要:提出了一種利用遺傳算法幫助測試人員在較短時間內完成軟件模塊的黑盒測試,並給出測試結果和好的測試用例的方法。 關鍵詞: 遺傳算法 測試用例 耦合...查看完整版>>遺傳算法在黑盒測試中的應用
 
旅行銷售員問題的遺傳算法實現
旅行銷售員問題的遺傳算法實現摘要:本文借助于遺傳算法給出了旅行銷售員問題較優解的求解方法,並用C#語言實現。1. 旅行銷售員問題的描述和相關定理爲了方便討論旅行銷售員問題(Traveling Saleman Problem,簡稱TS...查看完整版>>旅行銷售員問題的遺傳算法實現
 
功能豐富的Perl:Perl用于實現遺傳算法
  如果您的機器上已經安裝了 Perl 5.005 或者更高的版本,您可以運行一下文章中的例子。您的系統最好應該是安裝了最近的(2000 年或者更遲些)主流的 UNIX(Linux,Solaris,BSD),但其它種類的操作系統可能也可以...查看完整版>>功能豐富的Perl:Perl用于實現遺傳算法
 
遺傳算法
遺傳算法(Genetic Algorithm)是一類借鑒生物界的進化規律(適者生存,優勝劣汰遺傳機制)演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975年首先提出,其主要特點是直接對結構對象進行操作,不存在求導和...查看完整版>>遺傳算法
 
遺傳算法的一個例子(C/C++)
遺傳算法的一個例子(C/C++)作者:newsuppy摘要: m個工件分配給m架機床的效益最優化問題,使用一種遺傳算法解決。 一,已知效益矩陣EeijM1M2M3M4M5J15648 3J264985J343254J472453J536455 Jn爲工件,Mn爲機床,矩陣對應...查看完整版>>遺傳算法的一個例子(C/C++)
 
遺傳算法介紹(內含實例)
現代生物遺傳學中描述的生物進化理論:遺傳物質的主要載體是染色體(chromsome),染色體主要由DNA和蛋白質組成。其中DNA爲最主要的遺傳物質。基因(gene)是有遺傳效應的片斷,它存儲著遺傳信息,可以准確地複制,也能發生突...查看完整版>>遺傳算法介紹(內含實例)
 
旅行銷售員問題的遺傳算法實現
旅行銷售員問題的遺傳算法實現摘要:本文借助于遺傳算法給出了旅行銷售員問題較優解的求解方法,並用C#語言實現。1. 旅行銷售員問題的描述和相關定理爲了方便討論旅行銷售員問題(Traveling Saleman Problem,簡稱TS...查看完整版>>旅行銷售員問題的遺傳算法實現
 
遺傳算法
遺傳算法(Genetic Algorithm)是一類借鑒生物界的進化規律(適者生存,優勝劣汰遺傳機制)演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975年首先提出,其主要特點是直接對結構對象進行操作,不存在求導和...查看完整版>>遺傳算法
 
銀屑病到底傳染嗎?與遺傳有關嗎?
有許多人都認爲銀屑病是一種傳染病,其實,銀屑病是不傳染的,但是銀屑病與遺傳有關。銀屑病是一種自身免疫功能紊亂和環境、氣候等多種因素引起的皮膚良性增生。它不會傳染給他人,雖然有一定的遺傳傾向,但患病的絕...查看完整版>>銀屑病到底傳染嗎?與遺傳有關嗎?
 
 
回到王朝網路移動版首頁