遗传算法原理

时间:2024-03-17 17:25:45编辑:奇事君

遗传算法的基本原理

遗传算法本质上是对染色体模式所进行的一系列运算,即通过选择算子将当前种群中的优良模式遗传到下一代种群中,利用交叉算子进行模式重组,利用变异算子进行模式突变。步骤基本框架1.编码由于遗传算法不能直接处理问题空间的参数,因此必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。这一转换操作就叫做编码,也可以称作(问题的)表示(representation)。评估编码策略常采用以下3个规范: (a)完备性(completeness):问题空间中的所有点(候选解)都能作为GA空间中的点(染色体)表现。 (b)健全性(soundness): GA空间中的染色体能对应所有问题空间中的候选解。 (c)非冗余性(nonredundancy):染色体和候选解一一对应。2.适应度函数进化论中的适应度,是表示某一个体对环境的适应能力,也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数,是用来判断群体中的个体的优劣程度的指标,它是根据所求问题的目标函数来进行评估的。遗传算法在搜索进化过程中一般不需要其他外部信息,仅用评估函数来评估个体或解的优劣,并作为以后遗传操作的依据。由于遗传算法中,适应度函数要比较排序并在此基础上计算选择概率,所以适应度函数的值要取正值。由此可见,在不少场合,将目标函数映射成求最大值形式且函数值非负的适应度函数是必要的。适应度函数的设计主要满足以下条件:(a)单值、连续、非负、最大化(b) 合理、一致性 (c)计算量小 (d)通用性强。 在具体应用中,适应度函数的设计要结合求解问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能。3.初始群体选取遗传算法中初始群体中的个体是随机产生的。一般来讲,初始群体的设定可采取如下的策略:(a)根据问题固有知识,设法把握最优解所占空间在整个问题空间中的分布范围,然后,在此分布范围内设定初始群体。(b)先随机生成一定数目的个体,然后从中挑出最好的个体加到初始群体中。这种过程不断迭代,直到初始群体中个体数达到了预先确定的规模。

遗传算法简单易懂的例子

遗传算法的例子如下:求解函数 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在区间[0,9]的最大值。对于求解函数最大值问题,一般选择二进制编码:实数编码:直接用实数表示基因,容易理解且不需要解码过程,但容易过早收敛,从而陷入局部最优;二进制编码:稳定性高,种群多样性大,但需要的存储空间大,需要解码且难以理解。以目标函数 f(x) = x + 10sin(5x) + 7cos(4x), x∈[0,9] 为例。设定求解的精度为小数点后4位,可以将x的解空间划分为 (9-0)×(1e+4)=90000个等分。2^16<90000<2^17,需要17位二进制数来表示这些解。换句话说,一个解的编码就是一个17位的二进制串。这些二进制串是随机生成的。一个这样的二进制串代表一条染色体串,这里染色体串的长度为17。对于任何一条这样的染色体将它复原(解码)到[0,9]这个区间中。可以采用以下公式来解码:x = 0 + decimal(chromosome)×(9-0)/(2^17-1)decimal( )( 将二进制数转化为十进制数。)一般化解码公式:f(x), x∈[lower_bound, upper_bound]x = lower_bound + decimal(chromosome)×(upper_bound-lower_bound)/(2^chromosome_size-1)f(x), x∈[lower_bound, upper_bound]x = lower_bound + decimal(chromosome)×(upper_bound-lower_bound)/(2^chromosome_size-1)lower_bound:函数定义域的下限。upper_bound:函数定义域的上限。chromosome_size:染色体的长度。通过上述公式,我们就可以成功地将二进制染色体串解码成[0,9]区间中的十进制实数解。

上一篇:爬虫网

下一篇:我是一个小草