遗传算法的基本原理与方法.docx

遗传算法的基本原理与方法－－笔记遗传算法的实现有6个主要因素：参数的编码、初始种群的设定、适应度函数的设计、遗传操作、算法控制参数的设定、约束条件的处理基因gene染色体chromosome群体population复制reproduction交叉crossover变异mutation适应性fitnessSGA基本遗传算法(SimpleGeneticAlgorithm)遗传算子GeneticOperatorSGA基本步骤1．染色体编码与解码2．个体适应度的检测评估3．遗传算子(选择运算使用比例选择算子、交叉运算使用单点交叉算子、变异运算使用基本位变异算子或者均匀变异算子)4．运行的主要参数：M群体规模T终止条件Pc交叉概率Pm变异概率优化问题的基本遗传算法构造过程：1．确定决策变量和约束条件2．建立优化模型3．确定编码方法4．确定解码方法5．确定个体评价方法6．设计遗传算子和确定遗传算法的运行参数一、编码(CodingandDecoding)编码：把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法解码：由遗传算法解空间向问题空间的转换二进制编码的缺点之一是HammingCliff海明悬崖：某些相邻整数的二进制代码间有很大的海明距离，使得交叉和突变都难以跨越。

DeJong依据模式定理，提出的编码准则：1、积木块规则：编码应当易于生成与所求问题相关的短距和低阶的积木块2、最小字符集规则：编码应采用最小字符集以使问题得到自然的表示和描述主要的编码方法有：二进制编码、格雷码、浮点数编码、多参数级联编码、多参数交叉编码编码的评估策略：完备性、健全性、非冗余性二、选择选择是在群体中选择生命力强的个体产生新的群体的过程根据每个个体的适应度值大小选择，适应度较高的个体被遗传到下一代群体的概率较大这样使得群体中个体的适应度值接近最优解常用的选择算子：轮盘赌选择（RouletteWheelSelection）、随机竞争选择（StochasticTournament）、最佳保留选择、无回放随机选择、确定式选择、无回放余数随机选择、均匀选择、最优保存策略、随机联赛选择、排挤选择（小生境常用）三、交叉交叉：是按较大的概率从群体中选择两个个体，交换两个个体的某个或某些位交叉运算产生子代，子代继承了父代的基本特征交叉算子的设计包括两个主要内容：确定交叉点位置、如何进行部分基因的交换几种适合二进制编码和浮点数编码个体的交叉算子：单点交叉、两点交叉与多点交叉、均匀交叉、算术交叉。

交叉算法是产生新个体的主要算法，它决定了遗传算法的全局搜索能力四、变异变异：是以较小概率对个体编码串上的某个或某些位值进行改变变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成新的个体变异本身是一种随机算法，只是产生新个体的辅助算法，它决定了遗传算法的局部搜索能力适合于二进制编码和浮点数编码个体的几种变异算子：基本位变异、均匀变异、边界变异、非均匀变异、高斯近似变异五、适应度函数适应度函数也称评价函数，是根据目标函数确定的用于区分群体中个体好坏的标准，总是非负的，任何情况下都希望其值越大越好在选择操作中，会出现两个成为遗传算法欺骗的问题：（1）在遗传算法初期，通常会产生一些超常个体，按照比例选择法，这些超常个体会因竞争力突出，而控制选择过程，影响到算法的全局优化性能2）遗传算法后期，当算法趋于收敛时，由于种群中个体适应度差异较小，继续优化的潜能降低，可能获得某个局部最优解适应度函数的设计主要满足以下条件：（1）单值、连续、非负、最大化2）合理、一致性3）计算量小（4）通用性强在遗传算法的不同阶段，还需要对个体适应度进行适当的扩大或缩小，成为适应度的尺度变换，主要有三种：线性尺度变换、乘幂尺度变换、指数尺度变换。

六、控制参数的选择0.4交叉概率Pc始终控制着遗传运算中起主导地位的交叉算子，一般建议取值范围是0.99变异概率Pm一般建议取值范围是0.0001〜0.1群体规模一般可以根据实际情况在10〜200之间选定七、约束条件的处理根据具体问题一般可选择三种方法：搜索空间限定法、可行解变换法、罚函数法。