遗传算法概述

《遗传算法概述》由会员分享，可在线阅读，更多相关《遗传算法概述（10页珍藏版）》请在金锄头文库上搜索。

1、遗传算法概述摘要 : 遗传算法 （genetic algorithms, GA） 就是人工智能得重要新分支,就是基于达尔文进化论,在微型计算机上 ,模拟生命进化机制而发展起来得一门学科。它根据适者生存、优胜劣汰等 自然进化规则来进行搜索计算机与问题求解。 对许多用传统数学难以解决或明显失效得非常 复杂得问题 ,特别就是最优化问题 ,GA 提供了一个行之有效得新途径。近年来,由于遗传算法求解复杂优化问题得巨大潜力及其在工业控制工程领域得成功应用,这种算法受到了广泛得关注。本文旨在阐述遗传算法得基本原理、操作步骤与应用中得一些基本问题 ,以及为了改 善 SGA 得鲁棒性而逐步发展形成得高级遗传算法

2、 （refine genetic algorithms, RGA） 得实现方 法。一、遗传算法得基本原理与特点 遗传算法将生物进化原理引入待优化参数形成得编码串群体中,按着一定得适值函数及一系列遗传操作对各个体进行筛选,从而使适值高得个体被保留下来,组成新得群体 ,新群体包含上一代得大量信息,并且引入了新一代得优于上一代得个体。这样周而复始,群体中各个体适值不断提高,直至满足一定得极限条件。此时,群体中适值最高得个体即为待优化参数得最优解。正就是由于遗传算法独具特色得工作原理,使它能够在复杂得空间进行全局优化搜索 ,并且具有较强得鲁棒性 ;另外 ,遗传算法对于搜索空间 ,基本上不需 要什么限制

3、性得假设 （如连续性、可微及单峰等 ）。同常规优化算法相比 ,遗传算法有以下特点。（ 1） 遗传算法就是对参数编码进行操作,而非对参数本身。 遗传算法首先基于一个有限得字母表 ,把最优化问题得自然参数集编码为有线长度得字符串。例如 ,一个最优化问题 :在整数区间 【0,31】上求函数 f（x）=x 2得最大值。 若采用传统方法 ,需要 不断调节 x 参数得取值 ,直至得到最大得函数值为止。 而采用遗传算法 ,优化过程 得第一步得就是把参数 x 编码为有限长度得字符串 ,常用二进制字符串 ,设参数 x 得编码长度为 5,“00000”代表 0,“ 11111”代表 31,在区间【 0,31】上得

4、数与二 进制编码之间采用线性映射方法;随机生成几个这样得字符串组成初始群体,对群体中得字符串进行遗产操作,直至满足一定得终止条件;求得最终群体中适值最大得字符串对应得十进制数,其相应得函数值则为所求解。 可以瞧出 ,遗传算法就是对一个参数编码群体进行得操作,这样提供得参数信息量大,优化效果好。（ 2） 遗传算法就是从许多点开始并行操作,并非局限于一点 ,从而可有效防止搜索过程收敛于局部最优解。（ 3） 遗传算法通过目标函数计算适值,并不需要其她推导与附加信息,因而对问题得依赖性较小。（ 4） 遗传算法得寻优规则就是由概率决定得,而非确定性得。（ 5） 遗传算法在解空间进行高效启发式搜索,而非盲

5、目得穷举或完全随机搜索。（ 6） 遗传算法对求解得优化问题没有太多得数学要求。 由于它得进化特性 ,它在解得 搜索中不需要了解问题得内在性质。遗传算法可以处理任意形式得目标函数与 约束 ,无论就是线性得还就是非线性得,离散得还就是连续得 ,甚至就是混合得搜索空间。（ 7） 遗传算法具有并行计算得特点,因而可通过大规模并行计算来提高计算速度。二、遗传算法得模式理论1、模式一个模式（schemata）就就是一个描述种群在位串得某些确定位置上具有相似性得一组符号串。为了描述一个模式，在用以表示位串得两个字符 0,1中加入一个通配符“ * ”，就构成 了一个表示模式用得 3个字符得符号表 0,1,*

6、。因此用三个元素符号表 0,1,* 可以构造出任意一种模式。当一个模式与一个特定位串相匹配时,意味着该模式中得1 与位串中得 1相匹配 ,模式中得 0与位串中得 0相匹配,模式中得“ * ”与位串中得 0或 1相匹配。例如 ,模 式 00*00 匹配了两个位串，即 00100,00000;模式 *111* 可以与 01110,01111,11110,11111 中得任何一个相匹配 ;模式 0*1* 则匹配了长度为 5,第一位为 0、第三位为 1 得八个位串 ,即00100,00101,00110,00111,01100,01101,01110,01111。模式得思路提供了一种简单而有效得方法,

7、使能够在有限符号表得基础上讨论有限长位串得严谨定义得相似性。 应强调得就是 ,“*”只就是一个代表其她符号得一个元符号,它不能被遗传算法直接处理 ,但可以据此计算出所有可能得模式。一般地，假定符号表得基数就是k,例如 0,1得基数就是2,则定义在该符号表上得长度为I得位串中,所有可能包含得最大模式数为(k +I)1,原因就是在I个位置中得任何一个位置上即可以取k个字符中得任何一个又可以取通配符“*”，即共有k + I个不同得表示，则I个位置5 得全排列数为(k +1)1例如，对长度I=5,k=2(对应0,1),则会有3X 3 X 3X 3X 3=3 =243=(k +I)I种 不同得符号串，而

8、位串得数量仅为kI=25=32。可见，模式得数量要大于位串得数量。对于由0、1与*定义且长度为I得符号串所能组成得最大模式数为(2+I)I。对于任一长度为I得给定位串，当任一位置上只有两种不同表示时，所含模式数为2I个,因此对于含有n个位串个体得种群可能包含得模式数在2Inx 2I之间。不难瞧出，遗产算法正就是利用种群中位串之间得众多得相似性以及适值之间得相关性 , 来引导遗传算法进行有效地搜索。为了区分 不同类型得模式 , 对模式 H 定义两个量 : 模式位数 (order) 与模式得定义长度 (defining length)分别表示为0(H)与(H)。O(H)就是H中有定义得非“ * ”

9、位得个数，模式定义长度(H) 就是指H中左右两端有定义位置之间得距离。这两个量为分析位串得相似性及分析遗传操作 对重要模式得影响提供了基本手段。2、复制对模式得影响设在给定时间(代)t,种群A(t)包含m个特定模式H,记为m=m(H,t)在复制过程中,A(t)中得任何一个位串A i以概率Pi=f i/刀fi被选中并进行复制。假如选择就是有放回得抽样，且两代种群之间没有交叠(即若A(t)得规模为n,则在产生A(t+1)时, 必须从A(t)中选n个位串进匹配集),可以期望在复制完成后，在t+1时刻,特定模式H得数量 为:m(H,t+1)=m(H,t)nf(H)/刀 fi其中,f(H)就是在t时刻对

10、应模式 H得位串得平均适值，因为整个群得平均适值f=刀fi/n, 则上式又可写为m(H,t+1)=m(H,t)经过复制操作后 ,下一代中特定模式得数量 H 正比于所在位串得平均适值与种群平均适 值得比值。若 f(H), 则 H 得数量将增加 ,若 f(H)0)。从对复制得分析可以瞧到,虽然复制过程成功得以并行方式控制着模式数量以指数规模增减 ,但由于复制只就是将某些高适值个体全盘复制,或者淘汰某些低适值个体,而决不会产生新得模式结构 ,因而性能得改进就是有限得。2、 交叉对模式得影响 交叉过程就是位串之间有组织得随机得信息交换。 交叉操作对一个模式 H 得影响与模式 得定义长度(H)有关,(H

11、)越大,模式H被分裂得可能性越大，因为交叉操作要随机选择出 进行匹配得一对位串上得某一随机位置进行交叉。显然(H)越大,H得跨度就越大，随机交叉点落入其中得可能性就越大 , 从而 H 得存活率就降低。例如位串长度 l=7, 有如下包含 两个模式得位串 A 为A=01111000 H1=*1*0, (H1)=5H2=*10*,(H2)=1 随机产生得交叉位置在 3与4 之间A=H1=,Pd=5/6H2=,Pd=1/6模式 H1 定义长 (H1)=5, 若交叉点始终就是随机地从 l1=71=6 个可能得位置选取 , 则模式 H1被破坏得概率为Pd=(H1)/(l1)=5/6 它得存活概率为Ps=1

12、Pd=1/6类似得 , 模式 H2 得定义长度 (H2)=1, 它被破坏得概率为 Pd=1/6, 它存活得概率为 Ps=1Pd=5/6 、因此,模式H1比模式H2在交叉中更容易受到破坏。一般情况下可以计算出任何模式得交叉存活概率得下限为Ps在上面得讨论中，均假设交叉得概率为 1。若交叉得概率为Pc(即在选出进匹配集得一对 位串上发生交叉操作得概率 ), 则存活率为Ps在复制交叉之后 , 模式得数量则为即因此，在复制与交叉得综合作用之下，模式H得数量变化取决于其平均适值得高低与定义 长度得长短,f(H)越大,(H)越小,则H得数量就越多。3、变异对模式得影响变异就是对位串中得单个位置以概率Pm进

13、行随机替换，因而它可能破坏特定得模式。一个模式 H 要存活,意味着它所有得确定位置都存活。因此 ,由于单个位置得基因值存活得概率为 1Pm,而且由于每个变异得发生就是统计独立得，因此,一个特定模式仅当它得0(H)个确定位置都存活就是才存活，从而得到经变异后，特定模式得存活率为(1Pm)0(H),即(1Pm)自乘0(H) 次,由于一般情况下Pm1,H得存活率可表示为(1Pm)0(H) 10(H)Pm综合考虑复杂、交叉与变异操作得共同作用 ,则模式 H 在经历复制、交叉、变异操作之后 , 在下一代中得数量可表示为 也可近似表示为由上述分析可以得出结论 :定义长度短得、确定位数少得、平均适值高得模式

14、数量将随着代 数得增加呈指数增长。这个结论称为模式理论或遗传算法基本定理。根据模式理论,随着遗传算法一代一代地进行 ,那些定义长度短得 ,位数少得 ,高适值得模式将越来越多,因而可期望最后得到得位串得性能越来越得到改善,并最终趋向全局最优点。三、遗传算法中适值得调整为了使遗传算法有效得工作 ,必须保持种群内位串得多样性与位串之间得竞争机制。现将遗 传算法得运行分为开始、中间与结束三个阶段来考虑:在开始阶段 ,若一个规模不太大得种群内有少数非凡得个体 （适值很高得位串 ）,按通常得选择方法 ,这些个体会被大量得复制 ,在种群 中占有大得比重 ,这样就会减少种群得多样性,导致多早收敛 ,从而可能丢失一些有意义得搜索点或最优点 ,而进入局部最优 ;在结束阶段 ,即使种群内保持了很大得多样性,但若所有或大多数个体都有很高得适值 ,从而种群得平均适值与最大值相差无几,则平均适值附近得个体与具有最高适值得个体被选中得机会相同,这样选择就成了一个近乎随机得步骤,适值得作用就会消失 ,从而使搜索性能得不到明显得改进。因此,有必要对种群内各位串得适值进行有效得调整 ,既不能相差太大 ,又要拉开档次 ,强化位串之间得竞争性。1、 窗口法 它就是一种简单有效得适值调整方法,调整后得个体适值为F j=f j（f mina）其中,f j为原来个体得适值；为每代种群中个体适值得最小值