巢湖学院计算机系2009届毕业设计（论文）
第三章 简单遗传算法
3.1、什么是简单遗传算法
Holland的GA常被称为简单遗传算法(SGA)，操作对象是一群二进制串（称为染色体，个体）即种群（population）。这里的每个染色体对应于问题的一个解。从初始种群出发，采用基于是适应度比例的选择策略在当前种群中选择个体，使用交叉和变异操作来产生下一代种群。如此一代代进化下去，直到满足期望的终止条件。
简单遗传算法用于优化问题时，其最主要特征就是:它不在单点上寻优，而是从整个种群(population)中选择生命力强的个体产生新的种群;它使用随机转换原理而不是确定性规则来工作。遗传算法中常用的遗传操作包括三个基本算子:选择(selection )、交叉(crossover)、变异(mutation)，其中，选择算子用于从旧种群生成新种群，交叉算子用于从父代生成子代，变异算子用于对子代做某种变异，使其跳出局优解。简单遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。
遗传算法所得结果的好坏，主要依赖于遗传代数和解的规模，在实际应用中只能根据具体要求，在合理的时间内对问题进行求解，若所得解不能令人满意，可增大解组规模或遗传代数，但这是以延长计算时间为代价的。 3.2、遗传算法的基本概念
由于遗传算法的基本思想是基于进化论和遗传学说的，故要用到一些相关的进
化和遗传的概念[5]。其介绍如下：
(1) 串(string)
它是个体 (Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(chromosome).表示待求解问题的一个可能解，由若干基因组成，是GA操作的基本对象。
(2) 种群（population）
个体的集合称为种群，串是种群的组成元素，种群是GA的搜索空间。 (3) 种群大小(population size) 种群中个体的数量称为种群大小。 (4) 基因(Gene)
基因是串中的元素，基因用于表示个体的特征。可以表示为一个二进制位，一个整数或一个字符等。例如有一个串S=1011，则其中的1, 0, 1, 1这4个元素分别称为基因。
8
巢湖学院计算机系2009届毕业设计（论文）
(5) 基因位置(gene position)
一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置从串左向右计算，例如在串S= 1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。
(6) 适应度(Fitness)
表示某一个体对于环境的适应程度。通常由适应度函数表示。 (8) 选择(selection)
从种群中选择出较适应环境的个体，这些选中的个体用于繁殖下一代，故有时也称这一操作为再生(reproduction)。选择用于繁殖下一代的个体时时根据个体环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。
(8) 交叉(crossover)
在选中用于繁殖下一代的个体中，对两个不同个体的相同位置的基因进行交换，从而产生新的个体。
(9) 变异(mutation)
在选中的个体中，对个体中的某些基因执行异向转化。在串中，如果某位基因为1，产生变异时就把它变成0；反之则由0变成1. 3.3、遗传算法的组成要素
遗传算法主要由六大部分组成：染色体编码设计，初始种群的产生，适应度函数的设计，算法参数的设置，遗传操作，算法终止条件。
(1) 染色体编码设计
GA进化过程是建立在编码机制上的，编码对于算法的性能如搜索能力和种群多样性等的影响很大。常见的编码方式有二进制编码，浮点数编码和混合编码。针对TSP问题，我们采用二进制编码方式，对于某些特殊的问题，编码采用图或树的形式;对于非线性规划问题，我们常用的是浮点数编码。下面就简单介绍一下二进制编码。二进制编码就是采用二进制符号0和1来表现个体的遗传基因型。其优点在于，编码，解码操作简单，交叉，变异等遗传操作便于实现。其缺点在于，不便于反应所求问题的特定知识，对于一些连续函数的优化问题，也由于GA的随机特性而使得其局部搜索能力很差。
(2)初始群体的产生
初始化过程有很多种。在研究遗传算法时，常常随机产生初始群体，这样做的好处是产生方式不依赖于问题，也就是对于任何问题，我们都可以采用这种方式来生成初始群体，因此从随机初始群体出发能更清楚地考察算法的行为和性能。
9
巢湖学院计算机系2009届毕业设计（论文）
(3) 适应度函数
适应度函数是遗传算法与问题的接口，对遗传算法的收敛速度和结果影响很大。根据问题的特点而设计合适的评价函数，能产生适宜于遗传算法处理的状态空间，能使算法快速有效地收敛。评价函数的规范化方法是根据搜索空间中点的原始优劣情况计算其评价函数值。评价函数对遗传算法的性能影响很大:如果过分强调当前的较优个体，就会使较优个体过分繁殖，很快降低群体中的结构的多样性，使算法过早收敛到局部最优值;而如果对当前较优个体强调得不够，算法就很容易丢失当前群体中较优个体的结构信息，不能在合理的时间内收敛到较好的个体。
遗传算法只通过评价函数与问题相联系，既有优点又有缺点。遗传算法通常是使用评价函数的数值来确定遗传选择概率。只依赖数值而不关心评价函数的计算方式，使得遗传算法很稳定，对于不同问题的不同要求，只需设计相应的评价函数，而无需修改遗传算法的其它部分。
基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代种群中的机会多少。为了正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则。
(4) 简单遗传算法的参数
① 种群大小M，即种群中个体的数量。群体规模影响遗传优化的最终结果，以及遗传算法的执行效率，当群体规模太小时，遗传算法的优化性能一般不会太好，而采用较大的群体规模可以减少遗传算法陷入局部最优解的机会，但较大规模，意味着计算机复杂度提高。
② 交叉概率Pc，交叉概率Pc控制着交叉操作被使用的频度，较大的交叉概率可增强遗传算法开辟新的搜索区域的能力，但高性能的模式遭破坏的可能性较大;若选用交叉概率太低，遗传算法搜索可能陷入迟钝状态，一般选取概率是从0.25-1.00之间。
③变异概率Pm，变异在遗传算法中属于辅助性搜索操作，其主要目的是维持群体多样性，一般低频度的变异可防止群体中重要的单一的基因可能丢失，高频度变异将使遗传算法趋于纯粹的随机搜索。
④ 遗传算法的终止进化代数T。
运行参数对遗传算法的求解结果和求解效率都有一定的影响，合理的运行参数往往是通过多次试算后确定的
(5) 遗传操作
10
巢湖学院计算机系2009届毕业设计（论文）
遗传操作包括选择、交叉、变异，这三个操作在进化过程中起着非常重要的作用。 ① 选择算子
选择的目的是为了从当前群体中选出优良的个体，使他们有机会作为父代为下一代繁殖子孙。GA通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存的原则。选择方法一般是比例选择，轮盘赌选择。
采用轮盘赌选择 (roulette wheel selection)是最简单的一种选择方法。表3.1表示了11个个体适应度、选择概率和累积概率。为了选择交配个体，需要进行多轮选择。每一轮产生一个[0, 1]均匀随机数，将该随机数作为选择指针来确定被选个体。如表3.1所示，第一轮随机数为0.81则第六个个体被选中，第二轮随机数为0.32，则第二个个体被选中;依此类推，第3,4,5，6轮随机数为0.96, 0.01, 0.65, 0.42，则第9, 1, 5, 3个个体依次被选。显然适应度高的个体被选中的概率大，而且很有可能被选中，而适应度低的个体则很有可能被淘汰。
个体 适应度 选择概率 累计概率 表3.1 轮盘赌选择法的选择概率计算 1 2 3 4 5 6 7 8 9 2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.18 0.16 0.15 0.13 0.11 0.09 0.07 0.06 0.03 0.18 0.38 0.49 0.62 0.73 0.82 0.89 0.95 0.98 10 0.2 0.02 1.00 11 0.1 0.0 1.00 从统计意义讲，适应度大的个体被选中的机会也大。当然，适应度小的个体尽管被选择的概率小，但仍有可能被“破格”复制。这样就增加了个体的多样性，便于执行交叉及变异。所以轮盘赌选择方法既体现“适者生存”原则，又保持个体性态多种多样。
②交叉算子(Crossover)
在遗传算法中，交叉是产生新个体的主要手段，它仿照生物学中杂交的原理，将两个个体(染色体)的部分字符的基因互相交换。执行交换的个体是随机选择的。首先，要确定交叉的概率Pc，大致为0.5-0.8左右。这就是说，大概有50%-80%的个体要执行交叉，然后，采用上述轮盘赌选择的方法，按适应度大小选择被交叉的个体，依次两两进行交叉。交叉点的选择也是随机的，假设字符串长度为L，则在[0,L]区间内产生随机整数，该整数便是交叉点的位置，注意，交叉点不能选在左数第一位字符上，因为其交叉结果仍是原来的两个字符串。因此，长度为L的字符串，可供选择的交叉点为(L-1)个。根据交叉点的数目不同，分一点交叉和两点交叉。前者只选一个交叉点，该点之后的字符全部参加交换;后者选取两个交叉点，只有两点间的字符才参加交换。当字符串长度大时，常采用两点交叉，此外还有多点交叉，即对长字符串实行多段交叉。通过交叉，子代的字符串不同于亲代。正是有了交叉操作，群体的性态才多种多
11
巢湖学院计算机系2009届毕业设计（论文）
样。传统的优化算法，例如动态规划法，个体性态不能增添，只能在原有的个体群体中择优，从而限制了搜索寻优的范围。因此，有人认为假若没有交叉，遗传算法就失去优越性。
遗传算法的有效性主要来自选择和交叉操作，尤其是交叉，在遗传算法中起着核心作用。
这里介绍单点交叉算法。任意挑选经过选择操作后种群中两个个体作为交叉对象，即两个父个体经过染色体交叉重组产生两个子个体，如图3.1所 示。随机产生一个交叉点位置，父个体1和父个体2在交叉点位置之右的部分基因码互换，形成子个体和子个体2。类似地完成其它个体的交叉操作。
③ 变异算子(Mutation)
如果只考虑交叉操作实现进化机制，在多数情况下是不行的，这与生物近亲繁殖影响进化历程是类似的。因为，种群的个体数是有限的，.经过若干代交叉操作，因为源于一个较好祖先的子个体逐渐充斥整个种群的现象，问题会过早收敛，当然，最后获得的个体不能代表问题的最优解。为避免过早收敛，有必要在进化过程中加入具有新遗传基因的个体。解决办法之一是效法自然界生物变异。生物性状的变异实际上是控制该性状的基因码发生了突变，这对于保持生物多样性是非常重要的。模仿生物变异的遗传操作，对于二进制的基因码组成的个体种群，实现基因码的小概率翻转，即达到变异的目的。
变异是遗传算法中产生新个体的另一种方法，它是将某一个体的某一位字符进行补运算，即将0变为1，或将1变为0.如图3.2所示，第四位经过变异操作。
变异个体的选择以及变异位置的确定，都是采用随机的方法产生。首先，确定变异概率Pm, Pm通常较小，约为0.001-0.01，也就是说，1000个字符中有1-10个发生变异。然后，针对每个字符在[0, 1]之间产生三位有效数的均匀分布随机数。针对对应的字符，决定是否将实行变异。
随机确定变异的位置后，执行变异的方法有两种。一种是直接产生变异，另一种
12