遗传算法！

一.什么是遗传算法？
遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究，是一种随机全局搜索优化方法，它模拟了自然选择和遗传中发生的复制、交叉(crossover)和变异(mutation)等现象，从任一初始种群（Population）出发，通过随机选择、交叉和变异操作，产生一群更适合环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代不断繁衍进化，最后收敛到一群最适应环境的个体（Individual），从而求得问题的优质解。

二.遗传算法常用术语介绍：
由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到一些生物遗传学知识，下面是我们将会用一些术语：

① 染色体(Chromosome)：染色体又可称为基因型个体(individuals)，一定数量的个体组成了群体(population)，群体中个体的数量叫做群体大小（population size）。

② 位串(Bit String)：个体的表示形式。对应于遗传学中的染色体。

③ 基因(Gene)：基因是染色体中的元素，用于表示个体的特征。例如有一个串（即染色体）S=1011，则其中的1，0，1，1这4个元素分别称为基因。

④ 特征值( Feature)：在用串表示整数时，基因的特征值与二进制数的权一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。

⑤ 适应度(Fitness)：各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。这个函数通常会被用来计算个体在群体中被使用的概率。

⑥ 基因型(Genotype)：或称遗传型，是指基因组定义遗传特征和表现。对于于GA中的位串。

⑦ 表现型(Phenotype)：生物体的基因型在特定环境下的表现特征。对应于GA中的位串解码后的参数。

三.遗传算法基本过程介绍：
基本遗传算法(也称标准遗传算法或简单遗传算法，Simple Genetic Algorithm，简称SGA)是一种群体型操作，该操作以群体中的所有个体为对象，只使用基本遗传算子(Genetic Operator)：选择算子(Selection Operator)、交叉算子(Crossover Operator)和变异算子(Mutation Operator)，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。选择、交叉和变异是遗传算法的3个主要操作算子，它们构成了遗传操作，使遗传算法具有了其它方法没有的特点。

其表示方法如下：

其中，

表示个体的编码方案

表示个体适应度评价函数

表示初始种群

表示种群大小

表示选择算子

表示交叉算子

表示变异算子

表示遗传算法终止条件

四.遗传算法的步骤
1.染色体编码

(1)编码

解空间中的解在遗传算法中的表示形式。从问题的解(solution)到基因型的映射称为编码，即把一个问题的可行解从其解空间转换到遗传算法的搜索空间的转换方法。遗传算法在进行搜索之前先将解空间的解表示成遗传算法的基因型串(也就是染色体)结构数据，这些串结构数据的不同组合就构成了不同的点。

常见的编码方法有二进制编码、格雷码编码、 浮点数编码、各参数级联编码、多参数交叉编码等。

二进制编码：即组成染色体的基因序列是由二进制数表示，具有编码解码简单易用，交叉变异易于程序实现等特点。

格雷编码：两个相邻的数用格雷码表示，其对应的码位只有一个不相同，从而可以提高算法的局部搜索能力。这是格雷码相比二进制码而言所具备的优势。

浮点数编码：是指将个体范围映射到对应浮点数区间范围，精度可以随浮点数区间大小而改变。

举个栗子

设某一参数的取值范围为 ，我们用长度为k的二进制编码符号来表示该参数，则它总共产生 种不同的编码，可使参数编码时的对应关系：

其中，

(2)解码 ：

遗传算法染色体向问题解的转换。假设某一个体的编码，则对应的解码公式为

举个栗子

设有参数 ，现用5位二进制编码对X进行编码，得 个二进制串（染色体）：

对于任一个二进制中，只要带入上面公式，就可以得到对应的解码，如

，它对应的十进制为

，则对应参数X的值为

2.初始群体的生成

设置最大进化代数 ，群体大小 ，交叉概率 ，变异概率 ，随机生成 个个体作为初始化群体 。

3.适应度值评估检测

适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数的定义方式不同。根据具体问题，计算群体P(t)中各个个体的适应度。

适应度尺度变换：一般来讲，是指算法迭代的不同阶段，能够通过适当改变个体的适应度大小，进而避免群体间适应度相当而造成的竞争减弱，导致种群收敛于局部最优解。

尺度变换选用的经典方法：线性尺度变换、乘幂尺度变换以及指数尺度变换。

介绍如下：

（1）线性尺度变换

是用一个线性函数表示，其中a为比例系数，b为平移系数，F为变换前适应度尺度，变换后适应度尺度。

（2）乘幂尺度变换

是将原适应度尺度F取k次幂。其中k为幂，F为转变前适应度尺度，为转变后适应度尺度。

（3）指数尺度变换

是指首先将原尺度乘以一个，然后取反，将作为自然数e的幂，其中的大小决定了适应度尺度变换的强弱。

4.遗传算子

遗传算法使用以下三种遗传算子：

（1）选择

选择操作从旧群体中以一定概率选择优良个体组成新的种群，以繁殖得到下一代个体。个体被选中的概率跟适应度值有关，个体适应度值越高，被选中的概率越大。以轮盘赌法为例，若设种群数为 ，个体 的适应度为 ，则个体i被选取的概率为：

当个体选择的概率给定后，产生[0,1]之间均匀随机数来决定哪个个体参加交配。若个体的选择概率大，则有机会被多次选中，那么它的遗传基因就会在种群中扩大；若个体的选择概率小，则被淘汰的可能性会大。

（2）交叉

交叉操作是指从种群中随机选择两个个体，通过两个染色体的交换组合，把父串的优秀特征遗传给子串，从而产生新的优秀个体。

在实际应用中，使用率最高的是单点交叉算子，该算子在配对的染色体中随机的选择一个交叉位置，然后在该交叉位置对配对的染色体进行基因位变换。该算子的执行过程如下图所示。

单点交叉算子流程图
注：其他交叉算子包括：

a)双点交叉或多点交叉，即对配对的染色体随机设置两个或者多个交叉点，然后进行交叉运算，改变染色体基因序列。

b)均匀交叉，即配对的染色体基因序列上的每个位置都以等概率进行交叉，以此组成新的基因序列。

c)算术交叉，是指配对染色体之间采用线性组合方式进行交叉，改变染色体基因序列。

交叉算子示意图
（3）变异

为了防止遗传算法在优化过程中陷入局部最优解，在搜索过程中，需要对个体进行变异，在实际应用中，主要采用单点变异，也叫位变异，即只需要对基因序列中某一个位进行变异，以二进制编码为例，即0变为1，而1变为0。

群体 经过选择、交叉、变异运算后得到下一代群体 。

5.终止判断条件

若 ，则 ，转到步骤2；否则以进化过程中所得到的具有最大适应度的个体作为最好的解输出，终止运算。

遗传算法全过程图：

从遗传算法运算流程可以看出，进化操作过程简单，容易理解，它给其它各种遗传算法提供了一个基本框架。

需要注意的是：

遗传算法有4个运行参数需要预先设定，即

：种群大小

：遗传算法的终止进化代数

：交叉概率，一般为0.4~0.99

：变异概率，一般取0.001~0.1

五.遗传算法应用举例
以Max-cut problem问题为例，即将一个无向图切成2个部分（子图），从而使得2个子图之间的边数最多。

Step 1, 初始解

（1）设置种群的大小，编码染色体，初始种群:

设定种群的大小为10，编码位数为7位（因为有7个节点），初始人口:

S1=7(0001111)，S2=5(0011010)，S3=7(1110000)，S4=7(1011011)
S5=7(0101100)，S6=5(0111100)，S7=3(1110011)，S8=4(0011110)，S9=6(0001101)，S10=6(1101001)；

其中，编码方式为：对无向图的每个节点进行编号，把无向图切成两个子图，划为子图1的用1表示，划为子图2的用0表示。

例如S1=7,表示把无向图切成两个子图，两个子图之间的边数为7，此时我们可以把编号为4，5，6，7的顶点划为子图1，把编号为1，2，3的顶点划为子图2，故可编码为0001111，但不唯一(因为两个子图之间的边数为7的切割方式并不唯一)。

（2）定义适应度函数：

计算两部分之间的边数

Step2:选择父代

（用轮盘赌方法从群体中随机选择两个父代）

S4=7（1011011）

S5=7（0101100）

Step3:杂交

对选取的父代进行杂交得到子代，其中杂交方法为若两个父代的同一节点在相同集合中，则保留；否则，对随机分配该节点至任意集合中。

交叉后： 子代=0011110（4）

Step4:变异

设定遗传概率，在0.05的概率下，将子代的某个节点从一个集合移动到另一个集合中。变异后：

子代=0010110(6)

Step5：群体更新

子代=0010110(6)

从S1=7(0001111)，S2=5(0011010)，S3=7(1110000)，S4=7(1011011)，
S5=7(0101100)，S6=5(0111100)，S7=3(1110011)，S8=4(0011110)，S9=6(0001101)，S10=6(1101001)

中选取质量最差的个体出来，将这个用子代个体替换掉。

以上5步构成一代，一代一代往前进化，若干代停止。

六.代码编写说明

(a). 代码模块说明

代码一共分为main()、Init()、Genetic_Construction()、Genetic_Crossover()、Genetic_Mutation()、Genetic_Update()、Check()和Output()等8个函数模块构成，

其中

main()函数构建了算法的主体框架；

Init()函数则是完成所有动态数组的初始化处理，读入数据,并存储图；

Genetic_Construction(),Genetic_Crossover(),Genetic_Mutation(),Genetic_Update()这4个函数则为整个遗传算法（初始化种群、选择、交叉、变异和更新群体）的实现过程；

Check()函数则用以检验分配方案的实际被切割边数与存储的被切割边数是否一致；

Output()函数则设置了结果的输出格式。

(b). 文本数据输入格式说明：

本文文本数据分为两部分

第一部分为以‘p’开头的总概栏，指明了总的点数和边数；

第二部分则是以‘e’开头的两个点的标号，代表这两个点相连接。

能直观想到的便是建立一个二维数组，两个标号分别为其下标，以布尔值或者标识值作为数组的存放值以判断两个点是否相连，诸如Graph[5][3]==1则表示5号点与3号点相连，若为0，则不相连。

©. 对Genetic_Construction()、Genetic_Crossover()、Genetic_Mutation()、Genetic_Update()这四个函数的重点介绍：

①Genetic_Construction()函数

Genetic_Construction()函数是遗传算法中种群初始化的过程。

对于一个种群，总会有一个数量大小吧，这就是Chromosome_Num的任务。

为方便起见，本文将种群的个数设置为固定的10。同时，笔者将个体的各种属性简化成各个标号点，属性选中为1，否则其值便为0，用Chromosome_CutValue数组代表当前个体的各个属性选中与否；

Chromosome二位数组第一个下标P代表的是第P个个体，第二个下标则代表了其的各个属性标号。

在构建的个体的属性赋值上，笔者选择了最简单的随机法构建，将结果的优化交给遗传算法的搜索过程。选择贪婪法构建初始的个体也是一种很好的方法，当然其它的合理的方法都是可以的。

在建立种群初始个体的时候，我们需要注意的一点是要保障种群的差异性，即个体之间的相似度不能太高，否则子代个体的变异率便不足，一个简单的理解便是有性繁殖与无性繁殖的区别，若杂交的个体相似度过高，便类似于无性繁殖。

② Genetic_Crossover()函数

解决初始种群（初始解集）的构建后，接下来便是遗传算法的核心，选择、交叉和变异算子的设计。

在Genetic_Crossover()中，本文对选择和交叉两个算子进行了设计。对于父亲节点的选择，可以是随机选择不同的两个，也可以按优秀度进行轮盘选择，本文选择第二种方法对父亲节点进行选择。

交叉算法的质量是直接决定解的质量的。本文的目的在于阐述遗传算法的一般过程，故为简要起见，笔者选择了非常简单的交叉算符——随机遗传，即对选取的父代进行杂交得到子代，其中杂交方法为若两个父代的同一节点在相同集合中，则保留；否则，对随机分配该节点至任意集合中。

之所以这样设计，笔者希望读者能够在理解代码的时候轻松一点，但更重要的是希望读者能够改进代码。无论是初始解的构建方法的改进，或者交叉算符的重新设计（可以尝试继承两父亲节点相同的部分，在不同的部分进行随机赋值或者其它处理），或者种群个体差异的评估规则改善，或者增加一个进化过程（诸如融入模拟退火，蚁群算法，禁忌搜索等）等等，笔者相信，无论哪一方面的改进，都会比笔者所给出的结果要优秀。

③ Genetic_Mutation()函数

在Genetic_Mutation()函数中，本文设定遗传概率为0.05，将交叉后的子代的某个节点从一个集合移动到另一个集合中。

④ Genetic_Update()函数

在Genetic_Update()中，我们对种群进行更新，若得到的子代的被切割边数大于群体中最小的被切割边数，则用该子代取代。

经过一次一次的种群更新，个体的解会向着最优解不断地靠近，最终最好的解到达并稳定在一个比较优秀的值，这个值或许是最优解也或许只是一个非常接近最优解的值。这也是启发式算法的弊端之一，无法保证和证明所求得的解的优秀度。

至此，遗传算法求解的过程便完成了，但是别忘了验证结果的正确性。

解：

Check_Max_Cut = 8

Max_Cut = 8

Distribution of each vertex :

0 1 0 1 1 0 1

附上相应的算例

Input

p 7 18

e 1 4

e 1 5

e 1 6

e 1 7

e 2 3

e 2 4

e 2 5

e 2 6

e 2 7

e 3 4

e 3 5

e 3 6

e 3 7

e 4 5

e 4 6

e 5 6

e 5 7

e 6 7