格雷码对遗传算法的改进研究

2022-09-10

1 引言

格雷码 (Gray Code) 起初主要应用于“模数”转换, 1 8 8 0年由法国工程师J e a nMaurice-Emlle·Baudot发明, 因Frank·Gray于1 9 5 3年申请专利“P u l s e C o d e Communication”得名[1]。

格雷码是一种具有反射特性和循环特性的单步自补码, 其循环、单步特性消除了随机取数时出现重大误差的可能, 其反射、自补特性使得求反非常方便。格雷码属于可靠性编码, 是一种错误最小化的编码, 因为它大大地减少了由一个状态到下一个状态时电路中的混淆。由于该编码相邻的两个码组之间只有一位不同, 因而在用于模-数转换中, 当模拟量发生微小变化而可能引起数字量发生变化时, 格雷码仅改变一位, 这样与其它码同时改变两位或多位的情况相比更为可靠, 即可减少出错的可能性。这就允许代码电路能以较少的错误在较高的速度下工作[1]。这种特性也是遗传算法中使用格雷码来进行个体编码的主要原因。

遗传算法的局部搜索能力不强, 究其原因, 主要是:新一代群体的产生主要是依靠上一代群体之间的随机交叉重组来完成的, 所以即使已经搜索到最优解附近, 而想要达到这个最优解, 却要费一番功夫。对于二进制编码方法表示的个体, 变异操作有时虽然只是一个基因座的差异, 而对应的参数值却是相差较大。但是若使用格雷码来对个体进行编码, 则编码串之间的一位差异, 对应的参数值也只是微小的差别。这样就相当于增强了遗传算法的局部搜索能力, 便于对连续函数进行局部空间搜索[2]。

对于遗传算法, 采用格雷码的主要优点是:1) 便于提高遗传算法的局部搜索能力。2) 交叉、变异等遗传操作便于实现。3) 符合最小字符集编码原则。4) 便于利用模式定理对算法进行理论分析[2]。

2 格雷码转化成二进制码

假设有一个格雷码为G=g m g m-1……g 2 g 1, 其对应的二进制编码为B=b m b m-1……b 2 b 1。由格雷码向二进制转化的公式为:b=g

但由此公式直接编写的程序效率太低, 所以一般并不使用此公式进行程序设计, 而是采用递推的方法, 高效地转换0~2147483647之间的数 (1~31位) 。推导方式如下表1 (以三位格雷码为例) :

由表1的数据可看出:如果, 按照序号01327645的方式遍历格雷码, 其编码实值是按自然数顺序排列。反之, 如果按此顺序遍历其二进制实值。则会发现遍历过的数据的个数减一即为二进制码所对应格雷码的实值。再观察序号顺序, 我们会发现:如果把二进制码分半, 前半部分从前向后遍历, 后半部分从后向前遍历。如果分半部分可再分, 则再将其分半。并按照前半部分从前向后遍历 (分解) , 后半部分从后向前遍历的方式遍历 (分解) , 直到不可分。即可实现按序号所描述顺序遍历二进制码。如果, 按此顺序遍历二进制码, 我们可以很方便地在序列中找到所要的二进制码与其对应的格雷码。本思想可以很方便地用递归实现。这样就实现了二进制到格雷码的转换。同样, 格雷码到二进制的转换, 也可以用相同的方法推出。为了加快运算, 我们跳过不必要的遍历将递归改为递推。这样就实现了格雷码与二进制之间的快速转换[1]。

此算法的时间复杂度约为O (n) , n为要转换数据的B I T数。

转化程序参见“格雷码简介及格雷码与二进制的转换程序 (C) ”[1]。

3 优化检验

3.1 检验工具Rosenbrock函数及算法参数

由Rosenbrock设计的Rosenbrock函数是考察优化方法是否具有迅速移向目标函数极值能力的一个典型例子[3]。实验通过考察Rosenbrock函数的全局最大值来对比二进制编码和格雷码在遗传算法中的性能差异。

Rosenbrock函数如下:

f (x1, x2) =100 (x12-x2) 2+ (1-x1) 2, 其中-2.048<=xi<=2.048 (i=1, 2)

对Rosenbrock函数求极值的两种不同编码的遗传算法的实现仍遵循遗传算法的一般过程。如图1所示[2]:

实验主要参数:

M:群体大小为2 0

T:遗传运算的终止进化代数为1 0 0;

P c:交叉概率为0.6;

P m:变异概率为0.01;

本文所指的适应值即个体的函数值f, 其对应的适应度为P f=f/M A X (M A X为全局最优解) 。

3.2 引入进化策略 (ES)

进化策略的研究始于1964年。在ES的发展中, Rechenberg和Schwefel做出了重要贡献。其中, Schwefel在Rechenberg提出的 (μ+1) -ES的策略基础上, 提出了 (μ+λ) -ES和 (μ, λ) -ES策略[4]。 (μ, λ) -ES策略是针对多父本和子本的。在算法过程中, μ个父本产生λ个子本, 但只有这λ个候选解竟争, 然后父本被拥有较好适应能力的子代完全取代。实验正是建立在这种策略的基础上, 先后50次求出进化过程中最早出现全局最大适应值的代数tm, 以及每次进化的全局最大适应值的平均值F, 并算出与之相对应的F的最大适应度的平均值P f=F/M A X。统计结果如表2所示:

不难看出, 基于进化策略的遗传算法更能较早的找到更优的全局最优解。

3.3 用格雷码改进遗传算法

基于二进制编码的遗传算法随机性较大, 局部搜索能力较差。实验进而将以上基于进化策略的遗传算法用格雷码加以改进, 考察进化过程中每一代适应度的平均值, 以较科学反映其变化的基本均势。本研究进行了50次实验, 将每次实验所得的进化代数, 染色体 (X) 的值, 以及每条染色体的适应值 (f) 记录到一个数据文件中。然后, 求出50次中各代 (1~100) 的适应值的平均值。为了放大两种编码所导致的结果上的差异, 我们分别对两种算法所对应的适应值平均值进行放大处理, 即f’=f2/1000。最后利用所得数据绘出f’和进化代数t的关系图, 如图2所示。

图中粗黑线G表示编码为格雷码的遗传算法所示的变化曲线, B表示二进制编码的变化曲线。从图中可以看出格雷码的变化曲线较为理想。由于局部搜索能力强, 虽然刚开始进化效率较低, 但最终能较好的搜索定位到较优的最大值, 而二制编码方法的遗传算法容易过早的出现早衰现象。

结果表明采用基于进化策略的格雷码进行编码的遗传算法, 既能较快速地搜索适应度大的个体, 又能大概率地搜索全局最优解, 是一种快速进行局部细致搜索的优秀的非线性方法。

摘要：格雷码编码具有较强的局部搜索能力。针对Rosenbrock函数采用基于进化策略的格雷码来优化遗传算法, 实验表明这种结合既能较快速地搜索适应度较大的个体, 也可以大概率地搜索全局最优解, 是一种快速进行局部细致搜索的优秀的非线性方法。

关键词：格雷码,进化策略,遗传算法,Rosenbrock函数