遗传算法及其应用.ppt

《遗传算法及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、遗传算法及其应用1、引言2、基本概念3、基本遗传算法4、基本遗传算法举例5、遗传算法的基本原理与方法6、遗传算法引用举例1、引言遗传算法简称GA（GeneticAlgorithms）是1962年由美国Michigan大学的Holland教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。遗传算法是以达尔文的自然选择学说为基础发展起来的。自然选择学说包括以下三个方面：（1）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。（2）变异：亲代和子代之间以及子代的不同

2、个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。（3）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种。遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并

3、行处理，并能到全局最优解。生物进化过程如下图2、基本概念2.1个体与种群个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。2.2适应度与适应度函数适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。适应度函数(fitnessfunction)就是问题中的全体个体与其适应度之间的一个对应关。它一般是一个实值函数。该函数就是遗传算法中指导搜索

4、的评价函数。2.3染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体(表现型)染色体（基因型）9----1001（2，5，6）----0101011102.4遗传操作亦称遗传算子(geneticoperator)，就是关于染色体的运算。遗传算法中有三种遗传操作：●选择-复制(selection-reproduction)●交叉(crossover，亦称交换、交配或杂交)●变异(mutation，亦称突变)选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体x

5、i∈S的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。这里的选择概率P(xi)的计算公式为交叉就是互换两个染色体某些位上的基因。例如,设染色体s1=01001011,s2=10010101,交换其后4位基因,即s1′=01000101,s2′=10011011可以看做是原染色体s1和s2的子代染色体。变异就是改变染色体某个(些)位上的基因。例如,设染色体s=11001101，将其第三位上的0变为1,即s=11001101→11101101=s′s′也可以看做是原染色体s的子代染色体。3基本遗传算法遗传算法基本流程框图生

6、成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束基本遗传算法的步骤步1在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；步2随机产生U中的N个个体s1,s2,…,sN，组成初始种群S={s1,s2,…,sN}，置代数计数器t=1；步3计算S中每个个体的适应度f(x)；步4若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。否则，转步5。步5按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1；步6按交叉率Pc所

7、决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；步7按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；步8将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；4基本遗传算法举例例4.1一元函数优化实例（约束优化问题）二维图形如图所示：式4.1下面介绍求解该优化问题的遗传算法的构造过程：第一步：确定决策变量和约束条件。式4.1给出，决策变量为x，约束条件为-2≤x≤2。第二步：建立优化模型。式4.1已经给

8、出了问题的数学模型。第三步：确定编码方法。要进行编码工作，即将变量转换成二进制编码串。串的长度