最优化计算方法.doc
《最优化计算方法.doc》由会员分享,可在线阅读,更多相关《最优化计算方法.doc(71页珍藏版)》请在三一文库上搜索。
1、最优化计算方法-遗传算法 1 遗传算法的历史简介 二十世纪六十年代,I.Rechenberg在他的演化战略中第一次引入了进化算法的思想(起初称之为Evolutionsstragegie)。他的这一思想逐渐被其他一些研究者发展。遗传算法(Genetic Algorithms) 是John Holland 发明的,后来他和他的学生及他的同事又不断发展了它。终于,在1975年John Holland 出版了专著自然系统和人工系统中的自适应(Adaptation In Natural and Artificial Systems)。1992年,John Koza 曾经使用遗传算法编出新的程序去做一些具
2、体的工作。他称他的这种方法为“进化规划”(Genetic Programming,简称GP)。其中使用了LISP规划方法,这是因为这种语言中的程序被表示为“分析树”(Parse Tree),而这种遗传算法就是以这些分析树为对象的。 2 生物学与进化论背景 1)基因所有的生物都是由细胞组成的。在每一个细胞中都有想同序列的染色体。染色体是一串DNA的片断,它为整个有机体提供了一种复制模式。染色体是由基因组成的,或者说染色体就是一块块的基因。每一个基因为一个特定的蛋白质编码。或者更简单的说,每一个基因为生物体的某一特定特征编码,比如说眼睛的颜色。所有可能的某一特定特征的属性(比如:蓝色,桔黄色等)被
3、称之为等位基因。每一个基因在染色体上都有其特定的位置,这个位置一般被称作位点(Locus)。全部序列的基因物质(或者全部的染色体)称之为基因组(或染色体组)(Genome)。基因组上特定序列的基因被称作基因型(Genotype)。基因型和后天的表现型两者是有机体的显性、生理和心理特征。比如说眼睛的颜色、智力的基础。2)复制(Reproduction) 在复制中,首先发生的是交叉(Crossover)。来自于父代的基因按照一定的方式组成了新的基因。新的子代还可能发生变异(Mutation)。变异的意思是DNA上的某一些成分的基因复制中出现的误差。3)生物的进化(Evolution)进化是发生在作
4、为生物体结构编码的染色体上,通过对染色体的译码部分地生成生物体。人们现在还不完全清楚染色体的编码和译码过程的细节,但下面几个关于进化理论的一般特性已广为人们所接受: 进化过程是发生在染色体上,而不是发生在它们所编码的生物体上。 自然选择把染色体以及由它们所译成的结构的表现联系在一起,那些适应性好的个体的染色体经常比差的个体的染色体有更多的繁殖机会。 繁殖过程是进化发生的那一刻。变异可以使生物体子代的染色体不同于它们父代的染色体.通过结合两个父代染色体中的物质,重组过程可以在子代中产生有很大差异的染色体。 生物进化没有记忆。有关产生个体的信息包含在个体所携带的染色体的集合以及染色体编码的结构之中
5、,这些个体会很好地适应它们的环境。大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化的。自然选择决定了群体中哪些个体能够存活并繁殖;有性生殖保证了后代基因中的混合和重组。比起那些仅包含单个亲本的基因拷贝和依靠偶然的变异来改进的后代,这种由基因重组产生的后代进化要快得多。自然选择的原则是适应者生存,不适应者淘汰。自然进化的这些特征早在“年代就引起了美国Michigan大学的Join Holland的极大兴趣,那时,他和他的学生们己在从事如何建立能学习的机器的研究。Holland注意到学习不仅可以通过单个生物体的适应而且通过一个种群的许多代的进化适应也能发生。受达尔文进化论-适者生存的启发
6、,他逐渐认识到,在机器学习的研究中,为获得一个好的学习算法,仅靠单个策略的建立和改进是不够的,还要依赖于一个包含许多候选策略的群体的繁殖。他们的研究想法起源于遗传进化,Holland就将这个研究领域取名为遗传算法,一直到1975年Hol1and出版了那本颇有影响的专著Adaptation In Natural and Artificial Systems,遗传算法这个名称才逐渐为人所知。 3 遗传算法概述 1)遗传算法的主要特征 我们的目的是获得“最好解”,可以把这种任务看成是一个优化过程。对于小空间,经典的穷举法就足够了;而对大空间,则需要使用特殊的人工智能技术。遗传算法(Genetic A
7、lgorithm)是这些技术中的一种,它是一类模拟生物进化过程而产生的由选择算子、杂交算子和变异算子三个基本算子组成的全局寻优算法。它从一个初始解族出发,由选择算子选出性状好的父本,由杂交算子进行杂交运算,变异算子进行少许变异,在一定概率规则控制下随机搜索模型空间。一代代进化,直到最终解族对应的误差值达到设定的要求。 遗传算法的结构 function Genetic Algorithm initialize evaluate while (not termination-condition) select from alter evaluate end 在第次迭代,遗传算法维持一个潜在解的群体
8、。每个解用其“适应值”评价。然后通过选择更合适个体(次迭代)形成一个新的群体。新的群体的成员通过杂交和变异进行变换,形成新的解。杂交组合了两个亲体染色体(即待求参数的二进制编码串)的特征,通过交换父代相应的片断形成了两个相似的后代。例如父代染色体为和,在第二个基因后杂交,产生的后代为和。杂交算子的目的是在不同潜在解之间进行信息交换。变异是通过用一个等于变异率的概率随机地改变被选择染色体上的一个或多个基因(染色体中的一个二进制位)。变异算子的意图是向群体引入一些额外的变化性。 遗传算法的特点:() 它不是直接作用于参变量集上,而是作用于参变量的某种编码形成的数字串上。() 它不是从单个点,而是从
9、一个解族开始搜索解空间,与传统的“点对点”式的搜索方法不同。() 它仅仅利用适应值信息评估个体的优劣,无须求导数或其它辅助信息。() 它利用概率转移规则,而非确定性规则。 遗传算法的优势: () 不容易陷入局部极值,能以很大的概率找到全局最优解。 () 由于其固有的并行性,适合于大规模并行计算。 2)遗传算法的运行步骤 一般性描述 不失一般性,考虑求最大值的问题。问题:求一个有个变量的函数的最大值。假设每个变量为域内的一个值,且对所有的,。假定以某个要求的精度优化函数:这里取自变量小数点后第6位。 )编码和解码 要达到要求的精度,每个域应该被分割为个等尺寸的区间。用表示使成立的最小整数。这样,
10、对每个变量,由串长为的二进制编码表达可以满足精度要求。以下的公式对应于每个串的自变量的值:其中表示二进制串的十进制值。代表一个潜在解的染色体被长度为的二进制串表达;前位对应区间里的一个值,随后的位对应区间里的一个值,等等;最后的位对应区间里的一个值。 )产生潜在解初始群体 简单地以位的方式随机地设定个染色体。如果确实有一些关于最优分布的知识,可以使用这些信息来设定初始潜在解的集合。 )根据适应值评价解的适应程度并据此生成新群体 通常使用一个根据适应值调节刻度宽度的轮盘。按照如下方法构造轮盘(假设这里的适应值为正值,否则可以使用一些比例机制调整):l 计算每个染色体的适应值;l 计算群体的总适应
11、值: l 计算每个染色体的选择概率: l 计算每个染色体的累计概率: 对轮盘转动次,每次按照下面的方法为新群体选择一个单个的染色体:l 产生一个在区间0,1里的随机数;l 如果,则选择第一个染色体;否则选择使成立的第个染色体()。 这样做的效果是:好的染色体得到多个拷贝,中等染色体保持平稳,最差染色体死亡。 )杂交(crossover)和变异(mutation)决定新群体的性状: 设杂交概率为,此概率给出预计要进行杂交的染色体个数。对于新群体中的每个染色体:l 产生一个在区间0,1里的随机数;l 如果,则选择给定的染色体进行杂交。 随机地对被选择的染色体配对:对染色体中的每一个,产生一个在区间
12、1, (为总长,即染色体位数)里的随机整数。表示杂交点的位置。两个染色体 和 被他们的子代和 所替代。 下一步的变异,是在一位一位( bit-by-bit )的基础上进行的。另一个遗传系统参数,变异率,给出了我们预计的变异位数:。整个群体中所有染色体的每一位都有均等的机会经历变异,即从0到1或者相反:l 产生一个在区间0,1里的随机数;l 如果,变异此位。 随着选择、杂交和变异的进行,新群体就为下一次的评价做好了准备。该评价是用来为下一次选择过程建立概率分布的,即建立一个根据当前适应值构造宽距的轮盘,其它的部分只是上述步骤的循环重复。 遗传算法的实例描述 )遗传算法的基本术语遗传学遗传算法染色
13、体(Chromosome)解的编码(数据、数组位串)基因(Gene)解中每一个分量的特征(特性、个性探测器、位)等位基因(Allele)特性值基因座(Locus)串中位置基因型(Genotype)结构表现型(Phenotype)参数集、解码结构、候选解遗传隐匿非线性个体(Individual)解适者生存在算法停止时,最优目标值的解有最大的可能性被留住适应性(Fitness)适应度函数值群体(Population)选定的一组解(其中解的个数为群体的规模)复制(Reproduction)根据适应函数值选取的一组解交配(Crossover)通过交配原则产生一组新解的过程变异(Mutation)编码的
14、某一个分量发生变化的过程 )基本遗传算法的理论说明 基本遗传算法(也称为标准遗传算法或简单遗传算法,Simple Genetic Algorithm,简称SGA)是一种群体型操作,该操作以群体中的所有个体为对象,只使用基本遗传算子:选择算子(Genetic Operator)、交叉算子(Selection Operator)和变异算子(Mutation Operator),其遗传进化操作过程简单,容易理解,是其他一些遗传算法的基础,它不仅给各种遗传算法提供了一个基本框架,同时也具有一定的应用价值。选择、交叉和变异是遗传算法的3个主要操作算子,它们构成了所谓的遗传操作,使遗传算法具有了其他传统方
15、法没有的特点。 1基本遗传算法的数学模型 基本遗传算法可表示为式中:C-个体的编码方法; E-个体适应度评价函数; -初始种群; M-种群大小;-选择算子;-交叉算子;-变异算子;T - 遗传运算终止条件。 2基本遗传算法的步骤说明 a) 染色体编码(Chromosome Coding)与解码(Decode) 基本遗传算法使用固定长度的二进制符号串表示群体中的个体,其等位基因有二值所组成。初始群体中各个个体的基因可用均匀分布的随机数来生成。例如: X=100111001000101101 就表示一个个体,该个体的染色体长度是n=18。l 编码:设某一参数的取值范围为,我们用长度为k的二进制编码
16、符号来表示该参数,则它总共产生种不同的编码,可使参数编码时的对应关系为: 0000000000=0 0000000001=1 0000000010=2 1111111111= 其中 。l 解码:假设某一个体的编码为,则对应的解码公式为:- 例如:设有参数,现用5位二进制编码对X进行编码,得 个二进制串(染色体): 00000,00001,00010,00011,00100,00101,00110,00111 01000,01001,01010,01011,01100,01101,01110,01111 10000,10001,10010,10011,10100,10101,10110,1011
17、1 11000,11001,11010,11011,11100,11101,11110,11111对于任一个二进制串,只要代入公式,就可得到对应的解码,如,它对应的十进制为:则对应参数X 的值为:。 b) 个体适应度的检测评估 基本遗传算法按与个体适应度成正比的概率来决定当前群体中各个个体遗传到下一代群体中的机会的多少。为了正确估计这个概率,要求所有个体的适应度必须为非负数,所以根据不同种类的问题,需要预先确定好由目标函数值到个体适应度之间的转换规律,特别是要预先确定好当目标函数值为负数是的处理方法。例如:可选取一个适当大的正数c,使个体的适应度为目标函数值加上正数c。 c) 遗传算子 基本遗
18、传算法使用下列三种遗传算子:l 选择运算使用比例选择算子。比例选择因子是利用比例与各个个体适应度的概率决定其子孙的遗传可能性。若设种群数为M,个体i 的适应度为,则个体i 被选取的概率为: 当个体选择的概率给定后,产生之间的均匀随机数来决定哪个个体参加交配。若个体的选择概率大,则能被选中,它的遗传基因就会种群扩大;若个体的选择概率小,则被淘汰。l 交叉运算使用单点交叉算子。只有一个交叉点位置,任意挑选经过选择操作后种群中两个个体作为交叉对象,随机产生一个交叉点位置,两个个体在交叉位置互换部分基因码,形成两个子个体,如同所示: 父个体111011单点交叉11000子个体1父个体201100011
19、11子个体2l 变异运算使用基本位变异算子或均匀变异算子。为了避免问题过早收敛,对于二进制的基因码组成的个体种群,实现基因码的小概率翻转,即0变为1,1变为0,如图所示 110 11 变异110 00 d ) 基本遗传算法的运行参数 基本遗传算法有下列4个运行参数需要预先设定,即: -为群体大小,即群体中所含个体的数量,一般取为 :20 100;T -为遗传运算终止进化代数,一般取为:100 500;-为交叉概率,一般取为:0.4 0.99;-为变异概率,一般取为:0.0001 0.1。)基本遗传算法的具体例证 下面通过具体的例子介绍遗传算法的实际工作过程。 问题:求下列函数的极大值:其中及。
20、假定对每个变量要求的精度是小数点后第4位。如图所示,该函数有多个局部极值点。图1 目标函数的图像下面介绍求解该优化问题的遗传算法的构造过程:第一步 确定决策变量和约束条件 由题意已知,决策变量为和,约束条件为:及。 第二步 建立优化模型 题目已经给出了问题的数学模型。 第三步 确定编码方法要进行编码工作,即将变量转换成二进制。串的长度取决于所要求的精度。例如,变量的区间是,要求的精度是小数点后第4位,也就意味着每个变量应该被分成至少个部分。对每一个变量的二进制串位数 (用表示),用以下公式计算:第四步 确定解码方法从二进制串返回一个实际的值可用下面的公式来实现:其中代表变量的十进位值。由于要求
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 计算方法
链接地址:https://www.31doc.com/p-2757282.html