遗传算法的C#实现及应用
作者:吴晓春 分类：自动化/计算机技术
摘 要 用C＃语言来实现遗传算法的通用代码GA类，然后调动GA类解决组合优化领域的经典问题TSP，并给出了该算法的实现程序。
关键词 遗传算法,TSP问题
遗传算法的历史起源可追溯至60年代，Holland于1975年出版的著名著作《自然系统和人工系统的适配》系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论。这一理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。
进入80年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。
一、遗传算法的C# 实现
遗传算法是模拟生物遗传进化的过程，在全局优化过程中找到最优解或其近似解的有效算法。简单地说，让多个随机解不断地繁殖，每一代解不断地进化，最后得到最优解或近似最优解。解决某一问题的遗传算法的实现过程有以下几个步骤：
(1) 初始：随机产生待解决问题的若干解，每个解称为染色体（又称个体），所有解称为群体。
(2) 适应度：计算群体中每个染色体的适应度，代表解的优化程度。
(3) 新一代群体：通过下列步骤的循环产生新一代的群体，称子代群体。即新的若干个解。
1) 选择：按照适应度选择两个父代染色体作为双亲染色体。适应度高，被选择的几率就高。
2) 交叉：按照交叉率由双亲染色体交叉形成两个新一代染色体， 若交叉不能完成，直接由双亲复制产生两个子代染色体。
3) 变异：按照变异率让染色体的某个基因产生突变形成新的染色体。
4) 替换：使用新的群体代替原群体。即新的若干个解代替原来的若干个解。
(4) 测试：如果群体繁殖的次数已经足够，返回群体中的适应度最优的个体作为解。
(5) 循环：返回到第2步
上述步骤中，群体初始化、适应度计算、选择、交叉、变异都与具体的问题紧紧联系，其代码受具体问题的制约。为了通用性，在实现遗传算法时，用代理代表这些功能。遗传算法的通用C#代码包括三个类，分别为基因类（GAGene）、染色体类（GAChromosome）、遗传算法类（GA）。
基因类GAGene由构造方法和Value属性组成，Value是字串型，对应实际问题的最基本信息。染色体类GAChromosome继承ArrayList来实现，由若干基因顺序组成。遗传算法类GA实现遗传算法的总体功能。
初始群体的产生是采用随机的方法产生问题的多个解，核心代码如下：
public void Initialize()//产生第一代群体
{ try{
if (this.EnableLogging && this.LogFilePath != "")
System.IO.File.Delete(LogFilePath);//染色体数据存盘
if (this.EnableLogging)
{ AddToLogFile("序号 染色体 适应度");
AddToLogFile("--------------------------------------------------");
}
}
catch (System.IO.IOException exp){}
m_thisGeneration = new System.Collections.ArrayList();//当前群体,
for (int i = 0; i < PopulationSize; i++) //PopulationSize为群体大小,即染色体个数
{
GAChromosome newParent = new GAChromosome(m_init, m_fit, m_mutate);
//利用m_init生成染色体，并用m_fit计算染色体的适应度，染色体变异时使用m_mutate
m_thisGeneration.Add(newParent);//添加到群体中
if (this.EnableLogging)AppendToLogFile(i, newParent);//数据存盘
}
RankPopulation();//根据适应度对染色体排序
}
在构造染色体new GAChromosome(m_init, m_fit, m_mutate)时，通过三个参数的代理方法来生成染色体、计算适应度、实现变异。具体代码随具体问题而不同。
新一代群体，又称为子代群体，它是在父代群体中选择优秀的染色体经过交叉、变异产生的。为了保证子代群体比父代群体在整体上更为优秀，选择方法、交叉方法和变异方法都要根据具体问题来设计调整，基于子代比父代比更优秀的趋势，群体向着最优解靠近，通过不断的循环(繁殖)，总能找到最优解或其近似解。核心代码如下：
