文章目录
![](https://aitechtogether.com/wp-content/uploads/2023/05/5506d15d-5598-46a9-9702-7d9748b13f12.gif)
遗传算法主要借用生物进化中的“适者生存”的规律。
遗传算法包括两个数据转换操作,一个是从表现型到基因型的转换,将搜索空间中的参数或解
转化成遗传空间中的染色体或者个体
,这个过程叫做编码(coding)。另一个就是从基因型到变现型的转换,即将个体转换成搜索空间中的参数,这个过程叫做解码(decode)。
遗传算法中包含了五个基本要素:参数编码,初始群体的设定,适应度函数的设计;遗传操作设计和控制参数设定。
由于遗传算法不能直接处理问题空间的参数,因此,必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。它们由基因按一定的结构组成。由于遗传算法的健壮性,对编码的要求并不苛刻。对一个具体的应用问题如何编码是应用遗传算法的首要问题,也是遗传算法应用的难点。事实上,还不存在一种通用的编码方法,特殊的问题往往采用特殊的方法。
1、编码
1.1 位串编码
将问题空间的参数编码为一维排列的染色体的方法,称为一维染色体编码方法。一维染色体编码中最常用的符号集是二值符号集,即采用二进制编码(Binary Encoding)。
(1)二进制编码
二进制编码是用若干二进制数表示一个个体,将原问题的解空间映射到位串空间上,然后在位串空间上进来遗传操作。<>/font
优点:二进制编码类似于生物染色体的组成,从而使算法易于用生物遗传理论来解释,并使得遗传操作若交叉、变异等很容易实现。另外,采用二进制编码时,算法处理的模式数最多。
缺点:
①相邻整数的二进制编码可能具有较大的Hamming举例。例如,15和16的二进制表示为01111和10000,因此,算法要从15改进到16则必须改变所有的位。这种缺陷造成了Hamming悬崖(Hamming Cliffs),将降低遗传算子的搜索效率。
②二进制编码时,一般要先给出求解的精度。但求解的精度确定后,就很难在算法执行的过程中进行调整,这就是算法缺乏微调(fine-tuning)的功能。若在算法一开始就选择较高的精度,那么串长就很大,这样也会降低算法的效率。
③在求解高维优化问题的时候,二进制编码串将非常长,从而使得算法的搜索效率很低。
(2)Gray编码
编码是将二进制编码通过一个变换进行转换得到的编码。
设二进制串对应
串
,则从二进制编码到
编码的变换为:
上式子(1)中,表示摸2的加法,也就是异或运算,不同为1,相同为0。
举个例子说明一下:
假设有一个二进制编码串,那么我们将它转化为Gray编码后为
。
从一个Gray串到二进制串的变换为:
举个例子说明一下:
假设有一个Gray编码串,将其转化为二进制编码串后为
。
Gray编码的优点是克服了二进制编码的Hamming悬崖的缺点。
1.2 实数编码
为克服二进制编码的缺点,对问题的变量是实向量的情形,可以直接采用实数编码。
实数编码是用若干实数表示一个个体,然后在实数空间上进行遗传操作。
采用实数表达法不必进行数制转换,可直接在解的表现型上进行遗传操作。从而可引入与问题领域相关的启发式信息来增加算法的搜索能力。近年来,遗传算法在求解高维或复杂优化问题时一般使用实数编码。
1.3 多参数级联编码
对于多参数优化问题的遗传算法,常采用多参数级联编码。其基本思想是把每个参数先进行二进制编码得到子串,再把这些子串连成一个完整的染色体。多参数级联编码中的每个子串对应各自的编码参数,所以,可以有不同的串长度和参数的取值范围。
2、群体设定
由于遗传算法是对群体进行操作的,所以,必须为遗传操作准备一个由若干初始解组成的初始群体。群体设定主要包括两个方面:初始种群的产生和种群规模的确定。
2.1 初始种群的产生
遗传算法中初始群体中的个体可以是随机产生的,但最好采用如下策略设定:
①根据问题固有知识,设法把握最优解所占空间在整个问题空间中的分布范围,然后,在此分布范围内设定初始群体。
②先随机产生一定数目的个体,然后从中挑选最好的个体加人初始群体中。这种过程不断迭代,直到初始群体中个体数目达到了预先确定的规模。
2.2 种群规模的确定
群体中个体的数量称为种群规模。
种群规模影响遗传优化的结果和效率。当种群规模太小时,遗传算法的优化性能一般不会太好,容易陷入局部最优解。而当种群规模太大时,则计算复杂。
种群规模的确定受遗传操作中选择操作的影响很大。模式定理表明:若种群规模为,则遗传操作可从这
个个体中生成和检测
个模式,并在此基础上能够不断形成和优化积木块,直到找到最优解。
显然,种群规模越大,遗传操作所处理的模式就越多,产生有意义的积木块并逐步进化为最优解的机会就越高。种群规模太小,会使遗传算法的搜索空间范围有限,因而搜索有可能停止在未成熟阶段,出现未成熟收敛现象,使算法陷入局部最优解。因此,必须保持种群的多样性,即种群规模不能太小。
另一方面,种群规模太大会带来若干弊病:
- 一是群体越大,其适应度评估次数增加,所以计算量也增加,从而影响算法效率;
- 二是群体中个体生存下来的概率大多采用和适应度成比例的方法,当群体中个体非常多时,少量适应度很高的个体会被选择而生存下来,但大多数个体却被淘汰,这会影响配对库的形成,从而影响交叉操作。
种群规模一般取为20~100。
文章出处登录后可见!