多目标动、静态进化优化算法研究外文翻译资料

英语原文共 3 页，剩余内容已隐藏，支付完成后下载完整资料

---

第三章 遗传算法介绍

基于达尔文适者生存的自然选择学说的遗传与进化算法已经成为一种高级优化工具，其中包括遗传算法、遗传编程、进化策略、进化编程。对所有这些算法细致的讲解无疑超出了本书的范围，所以单取其中遗传算法。遗传算法是运用最广泛的非传统优化算法，诸多文献当中包含了对于遗传算法的论述，诸如基于二进制编码的遗传算法、实数编码遗传算法、微编码方式的遗传算法、混合编码的遗传算法等等。本章节主要着重于讲解二进制编码遗传算法的工作机理。

3.1 遗传算法流程

遗传算法是一种基于种群概念的概率性以及最优化工具，适从生物基因机理以及达尔文自然选择学说。基于二进制编码的遗传算法由Ann Arbor在1965年首次引入，尽管论述这一伟大构想的著作直到1975年才正式出版，但是也无法阻止这本书成为遗传算法的重要基础。二进制编码遗传算法以概率性为重要基础，实行重复搜索，其核心部分可以如下论述(流程框图见Fig.3.1)：

1. 随机生成最初种群解集
2. 计算每个个体的适应值（最大化问题中目标函数值）。顺便一提，遗传算法通常被用来解决最大化问题，因此最小化问题必须转化为最大化问题来进行解决，转化方法如下：

假设ℱ（?）是一个最小化问题，通过以下方式转化为最大化问题：

①运用二象性原理转化为求解- ℱ（?）的最大化问题

②当ℱ（?）ne;0时，转化为求解 的最大化问题

③当ℱ（?）ge;0时，转化为求解 的最大化问题

④转化为求解 的最大化问题

1. 种群计算通过使用不同的算子实现，这些算子包括重组算子、交叉算子、变异算子，特殊算子。这些算子的作用请君继续往下看。
2. 种群中每个个体不一定如他们适应值表现的那样优秀，而重组算子的作用就是通过适应值从种群中选出优秀个体。因此重组算子概率性的获得由优秀个体形成的配对池。必须要注意，一个配对池当总可能会包含多个某个优秀体的复制体，配对池的规模保持重组之前的规模。因此，配对池的平均适应度值将会高于上一代种群。在遗传算法当中，有一系列重组方案，例如比例选择（Roulette-Wheel选择），锦标赛选择，排列选择等等。
3. 从上一代配对池中选择的配对个体（也称作父代），可能会根据交叉概率参与到交叉计算。在交叉计算当中，在父代与子代个体当中会发生信息交换，而且若父代为优秀个体，子代个体有极大可能性也为优秀个体。交叉算子有很多种类型，例如单点交叉、两点交叉、多点交叉、均匀交叉等等。
4. 在生物学上，突变意味着个体的突然变化。例如牛群当中大部分均为黑色，但是我们却从中发现一头白色的牛，那么我们就可以断定在牛繁殖过程中在基因层面发生了突然变化，这种变化就被称作变异。在遗传算法搜索中，变异算子用来从当前种群中获得局部变化。因此，如果某个个体陷入了局部最小，变异算子能够用来使这个个体从局部最小的情况脱困，随之发生的，这个个体可能跳跃到种群的任意位置。
5. 重组之后，完成交叉算子与变异算子的计算后，第一代的遗传算法即完成。为了终止算法，会运用到不同的条件，例如遗传代数的最大值，个体精确度期望值等等。

开始

初始化种群，Gen=0

No

Genge;Max_gen?

计算种群成员适应度

Yes

重组

结束

交叉

变异

Gen=Gen 1

Figure 3.1:GA流程图

3.2 基于二进制编码的遗传算法

为了帮助大家理解这种算法，构想一个待优化的问题，叙述如下。

Maximate ?=?（ ， ） （3.1）

Subject to

,

其中 、 为实际变量。

下列步骤使用二进制编码的遗传算法解决上述问题：

Step1-群体初始化：种群初始大小N根据问题的复杂程度任意选择。在这一类型的遗传算法当中，个体由一系列由0和1组成的二进制代码表示。这种个体编码方式可以同生物学中的染色体结合起来，一串二进制编码的每一位就相当于染色体上的一个基因片段。二进制代码的长度由期望精度决定，例如，如果我们期望 的精度为ε，则用ℓ位二进制代码代表，ℓ可以通过下列式子确定：

（3. 2）

从上式不难发现，一个二进制代码的计算复杂度由其长度L决定。

假定每个变量长度为10bits，因此，在当前问题中，遗传算法字符串的长度仅仅为20bits。再假定遗传算法字符串初始化为以下：

1 0 0 hellip; 1

0 1 1 hellip; 0

1 1 1 hellip; 0

0 0 1 hellip; 1

hellip;

1 0 1 hellip; 1

Step2-适应度计算：为了确定每一个个体的适应度（即为一串二进制代码），变量 与 的实值应该被首先计算。在知道某一个变量的最大值与最小值的前提下（这里以 为例子），通过解码二进制子串，并将这个值赋给，它的实值可以通过线性绘图原理给定如下：

（3. 3）

其中ℓ为子串长度，D表示二进制代码解码之后的值。

二进制数字的解码值可以通过以下方式求解得到：

首先任意定义一串二进制代码，例如1 0 1 1 0，则它的解码值可以通过如下计算得到， 。第二个变量 的实值也可以通过相同的方法计算求得。得到变量 和 的实值之后，将他们代入函数（ ， ）求解二进制代码的适应度值。不断地重复计算过程，获得整个种群中每个个体的适应度值。

Step3-重组算子：包含在种群中的个体可能没有如同Step2中计算那样优秀。在这一步，重组算子依据适应度值被用来从种群中选择优秀个体。到目前为，已经有几种较为成熟的重组算子被开发出来了，接下来争对这几种重组算子逐一介绍。

1. 比例选择/轮盘法

在这种方式中，个体被选择的可能性依据其适应度值确定，并且成比例关系，这种方法通过轮盘游戏（如图Fig3.2）的方式来实现。

Pointer

N times

Figure 3.2:比例选择轮盘法

轮盘被根据种群的大小划分为N份，每一分的比例关系按照种群中个体的适应度值确定，顺时针或者逆时针转动转盘，当转盘停止转动，由指针确定获胜区域。转盘上的每一个区域即代表遗传算法中每一个个体被选择为胜出者的概率，第i块区域的概率值可以通过以下计算得到：

（3. 4）

这个转盘转动N次，但是每一次只有一块区域被选择为胜利者。整个过程如下所示：

GA - strings Fitness Probability of being selected

1 0 0 hellip; 1

0 1 1 hellip; 0

1 1 1 hellip; 1

hellip;

1 0 1 hellip; 1

在这种方法中，一个优秀个体可能会被多次选择。因此，最终得到配对池可能如下所示：

1 0 1 hellip; 1

1 1 1 hellip; 0

1 1 1 hellip; 0

hellip;

1 0 1 hellip; 1

一种GA搜索的要点在于种群的多样性以及竞争压力，这两点分别与探测型和搜索型方法类似，而且这种方式的GA搜索在很多有关文献都有使用。这两种因素具有相关性，也就是说，当竞争压力增加，种群的多样性就会相应的降低，反之亦然。但是必须要注意，如果竞争压力增加，搜索进程将会着重于优秀个体（按适应度值），而其结果，将会造成种群的多样性降低。最终将会导致算法过早收敛，得到一个次优的结果。另一方面，较低的竞争压力将会导致搜索的合理性以及连续性降低，算法将会在中途停止。因此，竞争压力在GA搜索中极为重要，合理的竞争压力选择有助于搜索算法健康运行。诸位必须被告知，上述基于适应度的重组方式可能会出现一些难题，例如上面提到的，算法过早收敛以及停滞现象。为了解决这些问题，在竞争压力的选择上，Baker采用了基于排列的重组方式。

1. 排列选择

假设，在一个遗传算法问题种群当中，只存在四个个体，它们的适应度分别表示为 、 、 、 。根据总适应度值，分别赋值80%、10%、7%、3%（即上式中的 ）。基于适应度的比例选择算法完成执行，四个个体被选择的概率分别为0.8、0.1、0.07、0.03（如图Fig.3.3）。因此，存在过早收

敛的可能性。

Figure 3.3:基于适应度的比例选择的饼状图

为了解决这个问题，一种基于排列的重组方式被采用，详细内容论述如下。

排列选择包含两个步骤。

第一步，将种群内个体按照适应度值升序排列（即按照 、 、 、 ），适应度最低的个体排列在第一位，其他依次排列。因此，在这个例子当中， 、 、 、的排列等级分别为1、2、3、4。

第二步，根据分配的排名进行比例选择方式计算。每个个体占据的百分比区域可以通过下式计算求解： ，其中 表示第i个体的排名。因此， 、 、 、分别占据总区域的40%、30%、20%、10%（如图Fig.3.4）。诸君注意，基于排名方式的比例选择方法要优于基于适应度的比例选择方法。

Figure 3.4:基于排名方式的比例选择饼状图

1. 锦标赛选择

Brindle首先研究锦标赛选择方式。在这种方法中，随机选择锦标赛规模n，这个值要小于种群规模N，从种群中随机选择n个个体，根据适应度确定最优个体，将最优个体复制到配对池，然后将n个个体返还到种群中。因此，在每一次锦标赛选择中，仅仅只有唯一个体被选择，N轮锦标赛之后，配对池的容量变为N，每一个个体在这个过程中可能会被复制多次，这种计算方式的效率要快于基于排名方式和基于适应度的比例选择。

有兴趣的读者可以参考Goldberg和Deb的关于比较不同选择方法的工作。

1. 精英选择

这种方法首先由Kenneth De Jong提出来。精英选择首先从种群中定义一个精英个体，在运用上述任何一种方法进行重组时很可能会造成精英个体的消亡，所以将其直接复制到下一代来保证其存活。

Step4-交叉算法：

在交叉算法中，两个子代个体通过两个父代个体之间的内容交换产生。为了实现这一操作，父代个体或者配对个体将从配对池中随机选择，因此， 对配对组合从整个种群产生，通过猜硬币的方式，决定父代是否进行交叉运算，进行交叉运算的概率将为 。如果交叉运算的概率发生了，父代个体将会通过交叉的方式产生两个子代个体。因此，他们将会保持种群的完整性。又要注意了，通常交叉运算的概率接近于1.0，因此几乎所有的父代个体之间将会发生交叉运算。首先使用随机数产生器获得一个范围在0.0到1.0之间的随机数值，如果这个数字小于交叉运算的概率，则可以认为此次掷硬币操作的结果为真，否则判定为假，如果交叉运算被触发，那么父代就参与到交叉运算当中。

一旦选择出发生交叉运算的配对，染色体上的交叉位置通过随机数发生器产生一个整数确定，这个随机数的值在1-（L-1）之间，其中L为二进制代码的长度。个体参与到交叉是一个概率性的过程，这个概率值表示为 。在GA文献中存在大量的交叉方法，下面挑选其中击中介绍。

1. 单点交叉：

首先随机选择染色体上的交叉位置，选定交叉位置之后，左半部分保持不变，右半部分进行交换操作。诸君请听我一句话，在交换之后，不管交换操作改变的是左半部分还是右半部分，子代个体保持不变。一般而言，我们更倾向于保持交叉位置的左边部分不变，右半部分进行位交换操作。参与到单点交换操作的父代个体如下：

0 1 0 1 1 0 1 0 1 1 | 1 0 0 1 1 0 1 0 0 1

0 0 1 1 0 1 0 0 1 0 | 1 1 1 0 1 0 0 1 0 1

经过单点交叉之后得到的子代个体表示为：

0 1 0 1 1 0 1 0 1 1 | 1 1 1 0 1 0 0 1 0 1

0 0 1 1 0 1 0 0 1 0 | 1 0 0 1 1 0 1 0 0 1

1. 两点交叉：

在染色体上随机选择两点交叉位置，参与到两

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[138522]，资料为PDF文档或Word文档，PDF文档可免费转换为Word