基本遗传算法c.ppt

1、遗传算法,主要内容,概述 基本遗传算法 遗传算法的数学理论 应用举例,概述,遗传算法（Genetic Algorithms）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。 1975年美国霍兰(Holland)教授发表了第一本比较系统论述遗传算法的专著自然系统与人工系统中的适应性(Adaptation in Natural and Artificial Systems)。该书系统地阐述了遗传算法的基本理论和方法。,概述,遗传算法，从数学角度看，是一种概率性搜索算法；从工程学角度看，它是一种自适应的迭代寻优过程。它从某一随机产生的或者特定的初始群体出发，按照一定得操

2、作规则，不断的迭代计算，并根据每一个个体的适应度，保留优良品种，淘汰次品，引导搜索过程向最优解逼近。 遗传算法的主要特点是直接对结构对象进行操作；具有内在的隐并行性和较好的全局寻优能力；采用概率化得寻优方法。,基本遗传算法,基本遗传算法（simple genetic algorithms, SGA）只使用选择算子、交叉算子和变异算子这三种基本遗传算子。其遗传进化操作简单，容易理解，是其他遗传算法的雏形和基础。 基本遗传算法的构成要素主要有：染色体编码，个体适应度评价，遗传算子以及遗传参数设置等。,基本遗传算法的构成要素,1、染色体编码方法 基本遗传算法使用固定长度的二进制符号串来表示群体中的个

3、体，其等位基因是由二值符号集0,1所组成。初始种群众各个个体的基因值可用均匀分布的随机数来生成。如： X = 001011011001110010 就可表示一个个体，该个体的染色体长度是 n = 18。,基本遗传算法的构成要素,2、适应度函数 基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正或零。这样，根据不同种类的问题，必须预先确定好由目标函数到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。,基本遗传算法的构成要素,3、遗传算子 基本遗传算法使用下述三种遗传算子： （

4、1）选择算子 按照某种策略从父代中挑选个体进入中间群体，如使用比例选择。 （2）交叉算子 随机地从中间群体中抽取两个个体，并按照某种交叉策略使两个个体相互交换部分染色体码串，从而形成两个新的个体。如使用单点交叉。 （3）变异算子 按照一定的概率，改变染色体中某些基因的值。 （4）基本遗传算法的运行参数,选择算子-比例选择方法,比例选择算法是一种回放式随机采样的方法。其基本思想是：各个个体被选中的概率与其适应度大小成正比。 设某一代的群体大小为n，某一个体得适应度值为 ，那么它被选中的概率为：,选择算子-比例选择方法,将每个串的选取概率画在一张轮盘上。 每转动一次轮盘，指针落入串i所占区域的概率

5、为 ，当 比较大时，串i被选取的概率就比较大。当某一个体被选中时，它就完全复制产生下一代。,交叉算子,交叉算子有一点交叉、二点交叉、多点交叉和均匀交叉。 一点交叉如下进行： （1）在染色体中随机选择一个点作为交叉点； （2）第一个父辈的交叉点前的串和第二个父辈交叉点后的串组成一个新的染色体，第二个父辈的交叉点前的串和第一个父辈交叉点后的串组成另一个新的染色体。例如，下面两个进行交叉： 11010 01100101101 yxyyx yxxyyyxyxxy 形成新的串11010yxxyyyxyxxy和yxyyx01100101101 替代生成他们的父辈串放入中间群体。,变异算子,对于基本遗传算法

6、中二进制编码符号串所表示的个体，若需要进行变异操作的某一基因值为0，则变异操作将该基因值变为1；反之，若原有基因值为1，则变异操作将其变为0。 基本位变异算子的具体执行过程： （1）对个体的每一个基因座，依变异概率 指定其为变异点； （2）对每一个指定的变异点，对其基因值做取反运算或用其他等位基因来代替，从而产生出一个新的个体。,基本遗传算法的运行参数,M：群体大小，即群体中所含个体的数量，一般取为 20 100 。 T： 遗传运算的终止进化代数， 一般取为 100 500。 ：交叉概率，一般取为 0.40.9. ：变异概率，一般取为 0.0001 0.1. 注：这4个运行参数对遗传算法的求解

7、结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。,基本遗传算法,一般遗传算法的主要步骤如下： （1）随机产生一个由确定长度的特征字符串组成的初始种群。 （2）对该字符串种群迭代地执行下面的步骤：和步骤，直到满足停止准则为止： 计算种群中每个个体字符串的适应值。 应用复制、交叉和变异等遗传算子产生下一代种群。 （3）把在后代中出现的最好的个体字符串指定为遗传算法的执行结果，这个结果可以表示问题的一个解。,基本遗传算法,根据遗传算法思想，可以给出如图的基本遗传算法流程图 其中GEN是当前进化代

8、数；M是算法执行的最大次数。,基本遗传算法,基本遗传算法可以定义为一个八元组：,遗传算法的数学理论,模式理论 定义：基于三值字符集0、1、*所产生的能描述具有某些结构相似的0、1字符串集的字符串称作模式。 以长度为5的字符串为例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即00001，10001；又比如模式*1*0，描述了所有在位置2为“1”及位置5为“0”的字符串。由此可以看出，模式的概念为我们提供了一种简单地用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。这里需要强调的是，“*”只是一个描述符，而并非遗传算法中实际的运算符号，它是为描述方便而引入

9、的符号。通过模式，而将多个不同的串联系起来。,遗传算法的数学理论,模式阶：模式H中有确定值的基因位个数称作该模式的模式阶（schema order），记作O(H)。 例如，模式011*1*的阶数为4，而模式0*的阶数为1。显然一个模式的阶越高，其所代表的集合所包含的个体数目越少，因而确定性越高。 模式定义长度：模式H中的第一个确定位置和最后一个确定位置间的距离称作该模式的定义长度（defining length），记作(H)。 比如模式011*1*的定义距为4，而模式0*的定义距为0。,遗传算法的数学理论,M（H,t）表示在t时刻群体中包含模式H的字符串的个数。f（H,t）表示当前群体当中包含

10、模式H的个体的评估函数的平均值。 表示当前群体的平均的评估函数值。中间群体中包含模式H的字符串个数可表示为：,遗传算法的数学理论,设遗传算法的交叉概率和变异概率分别为 和 ，L为个体基因链码的长度，模式定理的表示方法如下： 由定理知，在选择、交叉和变异算子的作用下，具有低阶、短的定义长度，并且平均适应度高于群体平均适应度的模式将按指数级增长。,遗传算法的数学理论,由前面的模式定理可知，具有低阶、短定义距以及平均适应度高于群体适应度的模式在后代中将以指数级增长。这类模式在遗传算法中非常重要，我们称之为“积木”或“基因块”(building block)。如同搭“积木”一样，这些“好” 的模式在遗

11、传操作下相互拼接、结合，产生适应度更高的个体，从而找到更优的可行解。这正是“积木假说” （building block hypothesis）所揭示的内容。 积木块假设：低阶、短定义长度、高平均适应度的模式在遗传算子作用下，相互结合，能生成高阶、长定义长度、高平均适应度的模式，可最终生成全局最优解。,应用举例,应用步骤 第一步：确定决策变量及其各种约束条件，即确定出个体的表现型 X 和问题的解空间。 第二步：建立优化模型，即确定出目标函数的类型（是求目标函数最大值还是求目标函数的最小值）及其数学描述形式或量化方法。 第三步：确定表示可行劫的染色体编码方法，也即确定出个体的基因型 X 及遗传算法的搜索空间。 第四步：确定解码方法，即确定出由个体基因型 X 到个体表现型X的对应关系或转换方法。,应用举例,第五步：确定个体适应度的量化评价方法，即确定出由目标函数值 f(x) 到个体适应度 f(x)的转换规则。 第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。 第七步：确定遗传算法的有关运行参数，即确定出遗传算法的N,T , , 等参数。 由上述构造步骤可以看出，可行解的编码方法、遗传算子的设计是构造遗传算法是需要考虑的两个主要问题，也是设计遗传算法时的两个关