遺傳算法的C#實現(xiàn)及應(yīng)用
作者:吳曉春 分類：自動化/計算機技術(shù)
摘 要 用C＃語言來實現(xiàn)遺傳算法的通用代碼GA類，然后調(diào)動GA類解決組合優(yōu)化領(lǐng)域的經(jīng)典問題TSP，并給出了該算法的實現(xiàn)程序。
關(guān)鍵詞 遺傳算法,TSP問題
遺傳算法的歷史起源可追溯至60年代，Holland于1975年出版的著名著作《自然系統(tǒng)和人工系統(tǒng)的適配》系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極為重要的模式理論。這一理論首次確認了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性。
進入80年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。
一、遺傳算法的C# 實現(xiàn)
遺傳算法是模擬生物遺傳進化的過程，在全局優(yōu)化過程中找到最優(yōu)解或其近似解的有效算法。簡單地說，讓多個隨機解不斷地繁殖，每一代解不斷地進化，最后得到最優(yōu)解或近似最優(yōu)解。解決某一問題的遺傳算法的實現(xiàn)過程有以下幾個步驟：
(1) 初始：隨機產(chǎn)生待解決問題的若干解，每個解稱為染色體（又稱個體），所有解稱為群體。
(2) 適應(yīng)度：計算群體中每個染色體的適應(yīng)度，代表解的優(yōu)化程度。
(3) 新一代群體：通過下列步驟的循環(huán)產(chǎn)生新一代的群體，稱子代群體。即新的若干個解。
1) 選擇：按照適應(yīng)度選擇兩個父代染色體作為雙親染色體。適應(yīng)度高，被選擇的幾率就高。
2) 交叉：按照交叉率由雙親染色體交叉形成兩個新一代染色體， 若交叉不能完成，直接由雙親復(fù)制產(chǎn)生兩個子代染色體。
3) 變異：按照變異率讓染色體的某個基因產(chǎn)生突變形成新的染色體。
4) 替換：使用新的群體代替原群體。即新的若干個解代替原來的若干個解。
(4) 測試：如果群體繁殖的次數(shù)已經(jīng)足夠，返回群體中的適應(yīng)度最優(yōu)的個體作為解。
(5) 循環(huán)：返回到第2步
上述步驟中，群體初始化、適應(yīng)度計算、選擇、交叉、變異都與具體的問題緊緊聯(lián)系，其代碼受具體問題的制約。為了通用性，在實現(xiàn)遺傳算法時，用代理代表這些功能。遺傳算法的通用C#代碼包括三個類，分別為基因類（GAGene）、染色體類（GAChromosome）、遺傳算法類（GA）。
基因類GAGene由構(gòu)造方法和Value屬性組成，Value是字串型，對應(yīng)實際問題的最基本信息。染色體類GAChromosome繼承ArrayList來實現(xiàn)，由若干基因順序組成。遺傳算法類GA實現(xiàn)遺傳算法的總體功能。
初始群體的產(chǎn)生是采用隨機的方法產(chǎn)生問題的多個解，核心代碼如下：
public void Initialize()//產(chǎn)生第一代群體
{ try{
if (this.EnableLogging && this.LogFilePath != "")
System.IO.File.Delete(LogFilePath);//染色體數(shù)據(jù)存盤
if (this.EnableLogging)
{ AddToLogFile("序號 染色體 適應(yīng)度");
AddToLogFile("--------------------------------------------------");
}
}
catch (System.IO.IOException exp){}
m_thisGeneration = new System.Collections.ArrayList();//當(dāng)前群體,
for (int i = 0; i < PopulationSize; i++) //PopulationSize為群體大小,即染色體個數(shù)
{
GAChromosome newParent = new GAChromosome(m_init, m_fit, m_mutate);
//利用m_init生成染色體，并用m_fit計算染色體的適應(yīng)度，染色體變異時使用m_mutate
m_thisGeneration.Add(newParent);//添加到群體中
if (this.EnableLogging)AppendToLogFile(i, newParent);//數(shù)據(jù)存盤
}
RankPopulation();//根據(jù)適應(yīng)度對染色體排序
}
在構(gòu)造染色體new GAChromosome(m_init, m_fit, m_mutate)時，通過三個參數(shù)的代理方法來生成染色體、計算適應(yīng)度、實現(xiàn)變異。具體代碼隨具體問題而不同。
新一代群體，又稱為子代群體，它是在父代群體中選擇優(yōu)秀的染色體經(jīng)過交叉、變異產(chǎn)生的。為了保證子代群體比父代群體在整體上更為優(yōu)秀，選擇方法、交叉方法和變異方法都要根據(jù)具體問題來設(shè)計調(diào)整，基于子代比父代比更優(yōu)秀的趨勢，群體向著最優(yōu)解靠近，通過不斷的循環(huán)(繁殖)，總能找到最優(yōu)解或其近似解。核心代碼如下：
