编码与实数编码

遗传算法与进化计算——编码与实数编码遗传算法包括五个基本组成部分：问题解的遗传表示创建解的初始种群的方法根据个体适应值，对其进行优劣判断的评价函数用来改变复制过程中产生的子代个体的遗传算子在遗传算法中，编码是把问题的各个潜在解转化成个体（染色体）的关键。根据编码结构，编码方式可分成一维编码和多位编码。一维编码是应用最广泛的形式，但是，使用一维编码来表示多维问题的解会损失多维结构中相当多的信息。根据编码内容，编码方法还可分成两类：仅包含解、包含解和参数。对各种给定问题的遗传算法通常采用仅包含解的编码方法。进化策略采用第二种编码方法，一个个体不仅包含问题的可能解，也包含与变异有关的方差和协方差等进化参数。二进制编码存在的问题采用二进制编码的根据来自于遗传算法的模式理论，但是有很多不同的意见。实践经验和理论分析都表明，对于连续变量而言，二进制编码存在严重缺陷，通常会在目标函数中引入附加的多峰性，使得编码后的目标函数比原始问题更复杂。Hamming悬崖是指两个在表现型空间中相距很小的个体可能存在很大的Hamming距离。例如，10000000和01111111这两个个体，在表现型空间中是相邻的点，具有最小的欧氏距离，但是在基因型空间中却具有最大的Hamming距离。要翻越Hamming悬崖，个体所有的位要同时作改变。而通过交叉和变异来翻越Hamming悬崖的可能性非常小，故二进制编码无法维持表现型空间中的位置。二进制编码存在的问题对于许多工程优化的问题，用二进制位串来表示它们的解是不合适的，而且不同的问题往往需要不同的编码方式。一般有以下几种:①二进制编码；②实属编码；③整数或字母排列编码；④一般数据结构编码。实数编码的各种算子对于函数优化问题，实数编码最为有效，在函数优化和约束优化领域，实数编码比二进制和Gray编码更为有效。就拓扑结构而言，实数编码在基因型空间和表现型空间中是一致的，因此，容易从传统优化方法中借鉴好的技巧来形成幼小的遗传算子。由于组合优化问题要找寻满足约束条件的最佳排列组合，因此，整数和字母排列编码最有效。对于有些复杂的实际问题，染色体中的基因用多维数组或数据结构来表示更为有效。实数编码的各种算子用于实属编码的染色体由实数向量组成，对于n个变量的问题，相应的实数向量是𝒙=(𝑥1,𝑥2,…,𝑥𝑛)。实属编码的遗传算子大体有四类：传统算子、算术算子、基于方向的算子和随即算子。其中，传统算子是二进制算子的直接延伸。1.算术交叉（ArithmeticalCrossover）两个向量𝒙1和𝒙2的加权平均表示为𝜆1𝒙1+𝜆2𝒙2(11.17)如果加权系数𝜆1和𝜆2的约束条件是𝜆1+𝜆2=1，𝜆10,𝜆20(11.18)那么式（11.17）所示的加权组合就是凸组合。如果加权系数不满足非负约束，就称为仿射组合；如果加权系数在实数空间内，那么就称为线性组合。实数编码的各种算子类似地，两个向量的加权组合为𝒙1′=𝜆1𝒙1+𝜆2𝒙2(11.19)𝒙2′=𝜆1𝒙2+𝜆2𝒙1(11.20)因加权系数约束条件不同，有三种类型的交叉：凸交叉（ConvexCrossover）、仿射交叉（AffineCrossover）和线性交叉（LinearCrossover）。如果对两个父代个体𝒙1和𝒙2进行交叉、那么凸交叉、仿射交叉和线性交叉的后代分别位于课本图11.14的实线、虚线和整个解空间。特别地，𝜆1=𝜆2=0.5的情况称作平均交叉或中间交叉。实数编码的各种算子2.混合交叉（BlendCrossover）基本思想是在由父代个体构成的超三角形内随机地生成后代。先考虑一维情况，设两个父代个体分别是𝑝1和𝑝2，并且𝑝1𝑝2。定义𝐼=|𝑝1−𝑝2|，并且0𝛼，𝛽1，那么后代在以下区间内随机生成：[𝑝1−𝛼𝐼,𝑝2+𝛽𝐼](11.21)上式被称为BLX−𝛼−𝛽,混合交叉的具体含义可由下图来说明。图11.5一维情况下的混合交叉实数编码的各种算子对于两个边路的情况，交叉的后代将产生于两个区间构成的三角形中，而在n个变量的情况下，后代则位于由n个区间构成的超三角形中。这种混合交叉也被称为盒子BLX（简称BBLX），区别于方向BLX（简称DBLX）。如果种群沿着问题空间的对角线分布，那么沿着父代所定义的对角线进行采样应该比从盒子中采样更有意义。基于这种假设，DBLX的采样发生在与父代定义的对角线平行的区间，而BBLX则在父代定义的超三角形中均匀采样。DBLX表示为BLX−𝛼−𝛽−𝛾，并且可以考虑为BBLX与两个个体所连对角线相对的两个对角被裁掉的一种特例，实数编码的各种算子可用图11.6来说明。其中，参数𝛾表示被保留部分。例如，BLX−0.0−0.0−1.0表示的采样区间是由两个父代个体所定义的盒子全部被保留；BLX−0.0−0.0−0.5表示被裁去的是腰长为1.0−0.5=0.5的等腰三角形（图中的阴影部分），而采样区域是盒子中剩下的部分。𝑝1𝑝2𝑝1𝑝2𝛾a)盒子BLXb)方向BLX图11.6二维情况下的混合交叉实数编码的各种算子3.单峰正态分布交叉在采样区域的选取方面，单峰正态分布交叉（UNDX）与方向BLX相似，也是沿父代定义的对角线区域进行采样。不同的是，UNDX在由三个父代定义的正态分布区域中个后代。图11.7所示为二维情况下的UNDX，在父代个体𝑝1和𝑝2的连线上，正态分布的标准差于这两个个体间的距离𝑑1成正比。图11.7单峰正态分布交叉实数编码的各种算子而在与该连线正交的方向上，正态分布的标准差与第3个父代个体𝑝3到连线的距离𝑑2成正比。设随机数𝑧𝑘~𝑁0,𝜎𝑘2,𝑘=1,2,…,𝑛,𝜕和𝛽是常数，那么子代个体𝒄1和𝒄2按以下方式产生：（11.22），（11.23）（11.24）实数编码的各种算子4.边界算子（BoundaryOperator）一般认为，全局最优解的存在区域是可行区域的边界，因此，对于许多约束优化问题，如果只搜索由一系列约束条件所定义的解空间的边界可能效果会更好。球（Sphere）交叉就是实现这种思想的一种实践，其后代根据下式生成：,i=1,2,…,n(11.25)式中，(x1,x2,…,xn)和(y1,y2,…,yn)分别表示父代的两个个体，而(z1,z2,…,zn)表示所生成的一个后代个体；随机数𝛼∈1,𝜂。实数编码的各种算子5.基于方向的交叉（Direction-basedCrossover）基本思想是根据目标函数值来确定遗传搜索的方向。如果由两个父代个体𝒑1和𝒑2生成一个后代个体C，那么（11.26）式中，r是[0,1]区域内的随机数，并且，父代个体𝒑2不差于𝒑1，也就是说，对于最大化问题，有𝑓𝒑2≥𝑓𝒑1，而对于最小化问题，有𝑓𝒑2≤𝑓𝒑1。实数编码的各种算子6.非均匀变异（Non-uniformMutation）非均匀变异是一种自适应变异算子，搜索步长在进化过程的不同阶段会自适应地调整，前半阶段它能在整个定义域中大范围搜索，以尽快发现可能的最优区域，随着算法的进行，搜索范围依概率“越来越小”，到算法临近结束时仅在当前解的小领域中搜索，这样能够准确定位最优解而不会再从当前最优区域中“逃逸”。实数编码的各种算子7.有向变异基本思想是通过在某个方向上的随机变动实现对父代个体的变异操作，通常在近似梯度方向上进行。在染色体接近边界等情况下，如果变异还是近似梯度方向上进行，就有可能出现染色体陷落在解空间的某个角落的情况，即所谓的“陷落”现象。解决的办法是，在随机方向上进行变异。实数编码的各种算子8.高斯变异(1)高斯变异是改进遗传算法对重点搜索区域的局部搜索性能的另一种变异操作方法。所谓高斯变异操作是指进行变异操作时，用符合均值为、方差为2的正态分布的一个随机数来替换原有基因值。(2)操作•高斯变异的具体操作过程与均匀变异类似。•具体实现高斯变异时，符合正态分布的随机数Q可由一些符合均匀分布的随机数利用公式来近似产生。