遗传算法模式定理

遗传算法遗传算法是一种借鉴生物遗传和进化机制寻求最优解的计算方法。

该方法模拟生物进化中的复制、交换、变异等过程，并通过模拟自然选择压力的方式推动问题解集向最优解方向移动。

遗传算法为解决多种难以采用传统数学方法求解的复杂问题提供了新的思路。

1. 遗传算法的发展历史研究者采用计算机模拟生物进化过程并解决优化问题的尝试始于20世纪40至50年代。

20世纪60年代中期，美国密歇根大学的Holland教授提出了位串编码技术，这种编码技术适用于变异操作和交叉操作，他指出在研究和设计人工自适应系统时可借鉴生物遗传的机制，以群体的方式进行自适应搜索。

70年代中期，Holland提出遗传算法的模式定理（Schema Theorem），奠定了遗传算法的理论基础。

11967年，Holland教授的学生De Jong首次将遗传算法应用于函数优化中，2设计了遗传算法执行策略和性能评价指标。

他挑选的5个专门用于遗传算法数值实验的函数至今仍被频繁使用，而他提出的在线(on-line)和离线(off-line)指标则仍是目前衡量遗传算法优化性能的主要手段。

1989年，Goldberg出版专著“Genetic Algorithm in Search, Optimization, and Machine learning”3。

该书全面阐述了遗传算法的基本原理及应用，并系统总结了遗传算法的主要研究成果。

该书对遗传算法科学基础的奠定做出了重要贡献。

1991年，Davis编辑出版了专著“Handbook of Genetic Algorithms”，该书中介绍了遗传算法在工程技术和社会生活中的大量应用实例。

41992年，美国斯坦福大学的Koza出版专著“Genetic Programming, on the Programming of Computers by Means of Natural Selection”，在此书中，他将遗传算法应用于计算机程序的优化设计和自动生成，并在此基础上提出遗传编程（Genetic Programming, GP）的概念5。

遗传算法总结By xudong 内容提要遗传算法的实现过程遗传算法基本理论遗传算法的三个算例TSP问题装箱问题网络结构优化遗传算法的实现过程产生初始种群在适应度函数的基础上选择parents从parents中产生children有三种途径：将parents中最优秀的个体直接保留到children杂交变异遗传算法实现流程下面以一个函数优化的过程为例说明遗传算法的工作过程，材料来自matlab中遗传算法的算法说明。

【生成初始种群】这是函数的等值线图，图中的蓝点表示初始种群中的个体。

【生成下一代种群】图中的符号表示下一代个体，具体不同符号表示不同的产生途径。

【迭代过程】可以看出，随着迭代的增加，整个种群逐渐收敛到最优解。

遗传算法基本理论这里只叙述定理的内容和评价，定理中所涉及的概念和定理的推导过程大家感兴趣的话可以翻翻书。

【模式定理】内容：遗传算法中，在选择、交叉、变异算子的作用下，具有低阶、短的定义长度，并且平均适应度高于群体平均适应度的模式将按指数级增长。

评价：看到这个定理首先想到的就是《自私的基因中》的核心观点，基因是进化的基本单位。

短小，并且适应度高的基因在进化过程中被保留下来，并且在群体中不断增加。

【积木块假定】内容：基因能够互相拼接在一起，形成适应度更高的编码串。

评价：模式定理是说遗传算法能够产生高质量的建筑砖头（基因），积木块假定是说可以用这些高质量的建筑砖头建造高质量的大楼（编码串）。

需要注意的是，我们把上述内容称为假定，而并非定理，这是因为有时候积木块假定并不成立，也就是说高质量的转头不一定能够建成高质量的大楼。

出现这种情况的原因是1+1<2的现象，各个基因之间高度相关，适应度很高的两个基因之间存在很强的负交互作用，结果导致整体的适应度下降。

【遗传算法收敛性】内容1.不保留优秀个体，收敛于最优解的概率小于12.保留优秀个体，遗传算法收敛于最优解的概率等于1评价：这两个定理说明了我们为什么在遗传算法中保留优秀个体的一个原因，保留优秀个体的另外一个原因是保证遗传算法每一代的解总是单调减少的（假设目标是极小化目标函数）。

8.3遗传算法基本定理1、模式的概念所谓模式就是一个相同的构形，它描述的是一个数字串的子集合，在这个集合中的所有数字串之间、在某些确定位置上是相同的。

模式一般用大写字母H 表示。

用3个字符的字母表[0,1,]V =*组成的三元组来描述模式，其中，符号*代表不确定数字，即在特定位置上可以与数字0或1相匹配。

例如，字符串长为5的模式110H =**，并称数字串 A=01110是模式 H 的一个代表串，这是因为数字串A 与模式H 在确定位置2、3和5 上相匹配。

遗传算法的操作过程非常简单，从一个含有N 个染色体的初始群体出发，不断循环地执行选择、交叉和变异运算。

看起来遗传算法是按这种简单的模式直接作用在一个个数字串组成的群体上，实际上，在每一代的计算过程中，这种数字串的显式操作过程蕴含了大量模式的隐含操作。

这里，首先讨论选择、交叉和变异算子对模式作用的影响。

对于由 N 个二进制数字串组成的群体中，至多包含有2L N 个模式（所有符号*都为确定数字时），式中L 为数字串长。

在遗传算法的执行过程中，所有的模式并不是以同等的机会发生的。

有些模式比起其他的模式更明确，例如，模式0111*和模式0****相比，在相似性方面，模式0111*就比较明确。

有些模式的跨度要比另一些模式的长，例如，模式11***和模式11***相比，在长度方面，模式11***要跨越整个串长。

为了定量地描述模式，下面介绍两个基本概念：模式的定义长度和模式的阶。

模式H 的定义长度是指模式H 中第1个常数位置与最后1个常数位置之间的距离，用()H δ表示。

例如，模式10111H =***的定义长度为1()4H δ=，这是因为模式1H 中第1个常数的位置为1，最后回个常数的位置为5，它们之间的距离为5-1=4；另一个模式20H =******中仅有1个常数位置，即第1个和最后1个常数位置是同一个位置，因此其定义长度2()0H δ=。

模式H 的阶是指出现在模式H 中常数的个数，用()O H 表示。