遗传算法的描述

计算智能课上遗留遗传算法问题的课后思考

计算智能课上讲到遗传算法，在“遗传算法用于求解数值优化问题”部分有点跟不上老师的速度，课间和回来之后翻书重新看这一部分，希望能有所理解。

这些都是我的个人理解，请自行辨别正误。

课上PPT举出的例子的具体数值和我课后用的教材上的数值不太一样，但不影响理解。

要用遗传算法解决问题，第一步需要映射，将所求的目标映射到二进制空间；因为遗传过程中需要的交叉变异需要通过位运算进行，二进制数字才能比较好地进行位运算。

题目

例题，无约束单目标优化问题：

s.t. 是指 subject to （such that），“受约束”

翻译一下，这道题说的是，求使得 能够达到最大值时，与值，其中和的取值范围受以上约束

我怀疑这教材是想顺便锻炼一下读者的英文文献阅读能力

要求精度达到小数点后五位

根据题目条件求二进制数字串的长度

第一步，将区间按照精度要求进行映射，粗俗一点地解释就是将运算区间映射到题目指定“分辨率”的二进制数字串，为什么是二进制数字串？因为我们需要通过后面对二进制数串（所谓“遗传信息”）进行位操作，体现“遗传”的思想。

这个二进制数串的长度应该充分反映题目中要运算的各个数值，本题中我们需要对两个数值使用遗传算法，因此需要求出这两个数值各自占用的比特长度，然后将它们相加，获得本题需要的比特长度。

为变量 的最大值， 为 的最小值，用 的最大值减去 的最小值，就求出了原始数值浮动的区间，然后再乘以题目要求的精度带来的倍数—— ，于是得到了本题所用的区间长度，此时的区间长度是用十进制数字表示的

第二步，将十进制数字区间映射到二进制数字区间，十进制到二进制肯定不会那么“恰巧”是一个整进制数，于是我们只能求出最近的二进制边界整进制数值，也即

代入本题数值，即求

和 中的 和

求得 为21bit， 为18bit

需要的总比特位 ，代入数值，于是得到总比特长度

种群初始化

接下来是随机生成符合长度要求（也仅仅只是符合长度要求）的二进制数串。数串的内容完全随机。书上的例子是给了十个个体，那么我们认为容纳这个种群的环境给了10个个体数目的供给，

第一个是0000 0101 0100 1010 0100 1101 1110 1111 1110 001

第二个是0101 1001 0110 1011 1011 1010 1110 1100 1110 110

第三个是1011 1000 1100 1101 1101 0101 1101 1110 0010 011

……

第九个是1110 0010 1111 0111 1101 1111 1011 1110 0111 111

第十个是1111 1001 0111 0011 1100 1010 0011 1011 1011 110

这些都是随机生成的满足长度要求的二进制数字串，鉴于需要的篇幅太长，我懒得写了，有兴趣的读者请翻阅《计算智能导论》尚荣华等编著.西安电子科技大学出版社.ISBN 978-7-5606-5344-0.第59页查看剩下的几个随机数例子

个体评价（遗传表达）

如果要对这些二进制数串代表的内容进行评估，就需要一个将其映射回原来十进制数字的“还原算法”，姑且认为是开动了蛋白质工厂照着基因生产蛋白质。

二进制遗传信息到十进制数字表征的算法如下：

例如，假设在计算的某一步我们获得了以下遗传信息，需要将其转化为十进制数字

注意，这个二进制数串只是举例时随机拿出的，并不具有特别的含义，而且我们仅仅将二进制数串看做一个零一序列，在进行转换之前不在意其数字意义

<---------------------39bit----------------------->

接下来开始转换

以下Bin指Binary——二进制，Dec指Decimal——十进制，不再赘述

于是前21bit的 对应的转换(000001010100101001001)Bin=(43337)Dec

后18bit的 对应的转换(101111011111110001)Bin=(194545)Dec

于是我们从没有数学含义的二进制零一数串转化，得到了两个具有数学含义的十进制数字

接下来是评估，评估方法和题目有关，所谓的用于衡量是否满足评估标准的值，在遗传算法中称为“适应度”，例如本题对每个“遗传信息”求对应的“适应度”函数eval（evaluate，评估，vt.）就是：

这里的 教材上没有说明是什么含义，但是不难猜测，v可能是指vector，向量，即一组有顺序的数字

于是以上面的遗传信息000001010100101001001101111011111110001作为例子，其对应的十进制有意义数字我们上一步已经求得，分别是 和 ，代入

于是以此类推，可以求得

……

题目要求是令函数取得最大值，简单地比较一下大小，发现 最大， 最小

选择（物竞天择）

教材上管这个叫“轮盘赌”，这个过程画成转盘的方式确实比较直观一些，但是我用另一个思路来理解这个问题

如果觉得轮盘赌很难理解的话，可以把它理解为一个一维随机变量：

先画出一个有长度的线段，

|---------------------------------------------|

令每个个体按照其适应度（ 的值）在线段上按比例占领一定的长度，

|--1--|--2---|--------3--------|---4---|--5---|

最后在一维横轴给定区间上以定模长的方式取区间内的随机数

第一次取随机数：|------^--------------------------------------|

第二次取随机数：|--------------------^------------------------|

……

第种群数目次取随机数：|-------------------------------------------^-|

随机数落到哪里就认为哪个个体被进化接受了

具体的计算，根据教材上的案例一步一步来说的话是这样的（注意，我的写法和教材并不完全一致）

1. 计算群体的总适应度 ， 代入之前给的例子 ，计算得到

2. 计算随机取点落到每个个体所在区间内（认为该个体适应了选择）的概率

   ……

3. 根据上述概率，求出每个区间的下限 和上限；

   例如对于 ， 它的区间下限就是0，上限

   |------|----------------------------------------------|

   0-----------------------------------------------------1

   对于 ，它的区间下限是 ，上限是 ，其中 上一步计算出结果是0.1161，而

   |------|----|------------------------------------|

   0------------------------------------------------1

   对于 ，区间下限是 ，上限是

   |------|----|--|---------------------------|

   0------------------------------------------1

   以此类推，如上面第一行所说， 的区间下限是 ，区间上限是 ，

   通过累加 得到 ；为 加上 就可以得到

4. 随机生成 区间内的数字共k个，然后让每个随机数落在这个总长度为1的区间上，选出这k个被落到的个体

   （这里吐槽一下，我发现上面做了那么多除法运算就是为了把整个总适应度映射到区间上，方便把生成的随机数撒上去，但实际上对随机数取模的时候完全可以以整个总适应度为长度取模，从而避免大量的除法运算；不知道为什么不这样做，难道是不好控制精度？）

   1 2 3 4 5

   repeat:10 srand(time(0)) int ir=rand()%10000 float fr=r/10000 end

   假设生成的数字是0.7060, 0.0318, 0.2769, 0.0462, 0.0971, 0.8235, 0.6948, 0.3171, 0.9502, 0.0344

   于是对应地，被落到的个体依次是

   于是我们称这些个体 被选择了，它们适应了外部条件，至于其他的个体就被淘汰掉了，不过不要着急，实验还没结束，我们仍然需要记录新的种群中的每个个体，这时候需要按照上面随机数落下的顺序记录每个个体，无论是否重复，并且按照随机数落下的顺序赋予它们新的个体编号

于是，新一轮的个体分别是：

（原 ，篇幅所限上面没有给出过 的遗传信息）

（原 ，照抄即可）

（原 ，篇幅所限同样之前没有给出过个体的遗传信息）

（原 ，注意出现了重复遗传信息的个体，这是自然选择，不要管，照抄即可）

……

（原 ，照抄）

（原 ，照抄）

这样，我们就得到了新一轮种群中的个体，并记录了它们的遗传信息

交叉（染色体互换）

染色体交叉互换是自然界生物有性生殖中的重要部分，遗传算法刻意模仿了这个过程 但不完全

任取两个幸运个体，例如 和 ，令 和 进行生命大和谐，假设产生了两个子代 和

每次生命大和谐时，我们都随机地取一个遗传信息上的位置作为断点，从这里将亲代的遗传信息裂开，然后交叉互换，将互换之后的结果称为子代

（阅读表格前请注意：断点是随机选择的，从断点处将遗传信息人为地分为了前半部分和后半部分）

我们随意地取17作为断点位置

进行交叉互换，注意遗传信息后半部分

变异（基因突变）

基因突变比较简单，随机选一个“幸运”(考虑到一般来说基因突变都是有害的，说幸运不如说倒霉)个体，在它的遗传信息上随机选一个“幸运”基因，1变0，0变1

例如我们选择了“幸运”个体 ，用高能射线照射，令其基因突变，于是遗传信息上随机位置处的基因说变就变

假设是16位基因遭到了突变(mutation)

流程

至此，我们已经将整个流程中的每个环节介绍完毕，现在将它们组合起来

1
2
3
4
5
6
7
8
9
10

产生初始种群P<t>[]
do{
    子代种群C<t>[] ← 染色体互换(一部分P<t>[]);
    突变种群M<t>[] ← 基因突变(一部分P<t>[]);
    /*没有进行染色体互换或者基因突变的个体P<t>[]姑且称为P'<t>[]*/
    P<t+1>[] ← 物竞天择( eval(P<t>'[],C<t>[],M<t>[]) );
    P<t>[] ← P<t+1>[];
}
while(继续循环的条件)
output(P<t>[])

注意到亲代生出子代之后，亲代就消失了，可以，这很三体星人

实验结果

实验结果和评估啥的翻教材第64页吧，我这里就不写了。况且图片用Markdown它也画不出来

“悬崖”问题

用二进制数字串编码反映十进制数字世界存在“悬崖问题”，如果我们需要对十进制数字的一位进行变动，可能牵扯到许多位二进制数串

所谓表征空间个体之间的距离和其遗传信息的Hamming距离二者之间的差距

例如，不断运作的筛选算法需要个体的某段表征为8Dec才能符合条件，但是目前这个个体的表征为7Dec，也就是说其遗传信息目前是(0111)Bin，使其变动为8Dec对应的(1000)Bin,需要四位二进制数串全部发生变化，这很困难

很显然这是进制之间互相映射，以及我们忽略了二进制数串的数学含义（所有的数学运算都是在映射到十进制之后进行的，在二进制域我们实际上只进行过位变换）两方面因素共同导致的

这类问题可以通过选用合适的编码方法缓解

Knighthana @ XDU

2023/03/23