智能控制基础：第四章 遗传算法

第四章遗传算法第四章遗传算法4.1什么是遗传算法4.2

遗传算法的理论基础4.3示例及研究动态4.1概述4.1.1

遗传算法的生物遗传学基础4.1.2遗传算法的基本操作4.1.3

遗传算法的特点

4.1.1遗传算法的生物遗传学基础遗传算法是JohnH.Holland根据生物进化的模型提出的一种优化算法。它的主要因素是：遗传、变异、选择。遗传是指子代总是和亲代相似。是生物进化的基础。变异是指子代和亲代有某些不相似的现象，是生物个体之间相互区别的基础。选择是指具有精选的能力，它决定生物进化的方向。遗传算法正是吸取了“适者生存，优胜劣汰”的进化原理，从而能够在复杂空间中进行鲁棒搜索。Gen=1初始化种群编码计算适应值是否满足终止条件否是交叉选择Gen=Gen+1开始变异结束遗传算法流程图4.1.2遗传算法的基本操作

复制（ReproductionOperator）

交叉（CrossoverOperator）

变异（MutationOperator）

复制从一个旧种群（OldPopulation）中选择生命力强的个体位串（字符串）（IndividualString）产生新种群的过程。目标函数f是期望的最大效益或好处的某种量度。它决定位串被复制或淘汰的决定因素。往往高适应度的位串更有可能在下一代中产生一个或多个子孙。编号位串（x）适应度f(x)=x2占总数的百分比（％）1234011011100001000100111695766436114.449.25.530.9总和1170100.0编号位串（x）期望的复制数实际得到的复制数1234011011100001000100110.581.970.221.231201

交叉在遗传算法中起着核心的作用。是个体之间的重新组合以产生新个体。交叉前：串1：a1a2a3a4a5串2：b1b2b3b4b5交叉后：新串1：a1a2b3b4b5新串2：b1b2a3a4a5

变异某个字符串某一位的值偶然的（概率很小的）随机的改变。是一种防止过度成熟而丢失重要概念的保险策略。在遗传算法中的作用是第二位的，但却必不可少。4.1.3遗传算法的特点

是对参数的编码进行操作，而非对参数本身；是从许多点开始并行操作，而非局限于一点，可防止收敛于局部最优；通过目标函数来计算适应度，从而对问题依赖小；寻优规则是由概率决定的，而非确定性的；是在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索；

对寻优的函数基本无限制；具有并行计算的特点，因而可通过大规模并行计算来提高计算速度；更适合大规模复杂问题的优化；计算简单，功能强。4.2遗传算法的理论基础模式（Schemata）：是一个描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板（SimilarityTemplate)。

模式定理令染色体长为5位时，模式*1*01表示与11101，11001，01101，01001相匹配的模式。把模式中最初的常数和最后的常数之间的距离叫模式H的定义长度，记为

(H)，如（*1*01）=3；把模式中常数的个数称为阶，用O（H）表示，如O（*1*01

）=3；令世代t群体中，包含模式H的个数用m(H,t)表示；包含H的个体平均适应度用f(H)表示，群体中所有个体的平均适应度用表示，L表示染色体的长度，Pc为交叉概率，Pm为变异概率，则模式定理揭示了短的（（H）），低阶（O（H）），优于平均（f(H)/)，即有效模式，在子代中以指数级增长（即优胜）。4.3示例及小结示例：基于遗传算法的系统辨识