遗传算法系列之五:多目标遗传算法和遗传编程

您所在的位置：网站首页 › 遗传编程算法有哪些 › 遗传算法系列之五:多目标遗传算法和遗传编程

遗传算法系列之五:多目标遗传算法和遗传编程

2023-09-29 07:00| 来源: 网络整理| 查看: 265

在遗传算法深入研究的阶段，人们提出将各种将遗传算法应用到更广泛领域，从而产生了一些有趣的后续工作。这些后续工作中，多目标遗传算法和遗传编程由于它们重要性而获得了独立命名。这篇博客就来介绍这两个工作。

1. 多目标遗传算法

很多优化问题是多目标优化问题，目标之间一般都是互相冲突的。比如在公路路线设计中，需要兼顾至少两个目标：1）路线经过多的居民点，方便大家出行，2）路线尽量少经过居民点附近，减少土地征用和房屋拆迁费用。在遗传算法出现之后，有人提出了各种方法将遗传算法应用于多目标优化。多目标遗传算法按照选择方法可以分为两种类型：基于线性加权和基于Pareto排序。

1.1 基于线性加权的多目标遗传算法

这种算法的思路很简单，将多目标按照线性加权的方式转化为单目标，然后应用传统遗传算法求解，如下公式所示

(1)

$\begin{eqnarray*} fitness(\pmb{I}) = \sum_{k=1}^{K}w_k \times f_k(\pmb{I}) \end{eqnarray*}$ \begin{eqnarray*} fitness(\pmb{I}) = \sum_{k=1}^{K}w_k \times f_k(\pmb{I}) \end{eqnarray*}

其中

w_i

表示第i个目标的权重，

f_k

表示归一化之后的第i个目标值。我们很容易知道，这类方法的关键是怎么设计权重。比如，Random Weight Genetic Algorithm (RWGA) 采用随机权重的方式，每次计算适应度都对所有个体随机地产生不同目标的权重，然后进行选择操作。 Vector-Evaluated Genetic Algorithm (VEGA) 也是基于线性加权的多目标遗传算法。如果有K个目标，VEGA 会随机地将种群分为K个同等大小子种群，在不同的子种群按照不同的目标函数设定目标值，然后再进行选择操作。VEGA 实质上是基于线性加权的多目标遗传算法。VEGA 是第一个多目标遗传算法，开启了十几年的研究潮流。

1.2 基于Pareto排序的多目标遗传算法

基于线性加权的多目标遗传算法给大家的感觉怪怪的，并不是真正多目标优化的实质。那么什么是真正的多目标优化。Pareto 在1986 年提出 Pareto 支配概念，其定义为：假设两个解决方案 I1 和 I2，对所有目标而言，I1 均优于 I2，则我们称 I1 支配I2。若 I1 没有被其他解所支配，则 I1 称为 Pareto 解。Pareto 解的集合被称为Pareto front。真正的多目标优化应该求解出Pareto front，选择Pareto front中的解应该提交人工解决。基于Pareto 排序的多目标遗传算法便是致力求解出 Pareto front。Multi Objective Genetic Algorithm (MOGA)、 Non -dominated Sorting Genetic Algorithm (NSGA) 和 improved Non-dominated Sorting Genetic Algorithm (NSGA-II) 都是常用的基于 Pareto 排序的多目标遗传算法。

基于 Pareto 排序的多目标遗传算法首先要解决的是适应度函数设计问题。MOGA 采用的适应度函数

$fitness(\pmb{I}) = 1 + nq(\pmb{I})$ fitness(\pmb{I}) = 1 + nq(\pmb{I})

，其中nq(x)表示被个体

$\pmb{I}$ \pmb{I}

支配的个体数量。NSGA 和 NSGA-II 再采用另外一种计算适应度函数的方法

step 1: 令i=1 step 2: 在种群 P 中找到所有不支配其他个体的个体，将它们的适应度设为i； step 3: 令i = i + 1 step 4: 将step2中找到的个体从种群删除。如果种群不为空，则重新从step2开始执行；否则结束。

上面两种适应度函数都能够挖掘种群中 Pareto 支配关系，效果如下图所示(左边的图表示 NSGA 和 NAGA-II 的适应度函数，右边的图是 MOGA 的适应度函数)。

多目标遗传算法的目标函数

基于Pareto排序的多目标遗传算法还有另一个关键点：我们要找的是 Pareto 解的集合，而不是一个 Pareto 解，因此我们需要鼓励多样性。不同算法有不同鼓励多样性的手段。MOGA 和 NSGA 采用的多样性方法被称为 fitness sharing 。fitness sharing 方法首先用下面的公式计算不同个体之间的距离。

(2)

$\begin{eqnarray*} d(I_1,I_2) = \sqrt{ \sum_{k=1}^{K}(\frac{f_k(I_1)-f_k(I_2)}{f_k^{max}-f_k^{min}})^2 } \nonumber \end{eqnarray*}$ \begin{eqnarray*} d(I_1,I_2) = \sqrt{ \sum_{k=1}^{K}(\frac{f_k(I_1)-f_k(I_2)}{f_k^{max}-f_k^{min}})^2 } \nonumber \end{eqnarray*}

其中

$f_k^{max}$ f_k^{max}

表示目前找到的最大k目标值，同理可知

$f_k^{min}$ f_k^{min}

。对于个体 I ，我们可以计算它的 niche count (求高手翻译，这个是啥玩意？)

(3)

$\begin{eqnarray*} nc(I) = \sum_{X,fitness(X) = fitness(I)} max(\frac{\sigma_{sharing} - d(I,X)}{\sigma_{sharing}}, 0) \nonumber \end{eqnarray*}$ \begin{eqnarray*} nc(I) = \sum_{X,fitness(X) = fitness(I)} max(\frac{\sigma_{sharing} - d(I,X)}{\sigma_{sharing}}, 0) \nonumber \end{eqnarray*}

再用个体的 niche count 调整个体的适应度

(4)

$\begin{eqnarray*} fitness(I)' = \frac{fitness(I)}{nc(I)} \nonumber \end{eqnarray*}$ \begin{eqnarray*} fitness(I)' = \frac{fitness(I)}{nc(I)} \nonumber \end{eqnarray*}

NSGA-II采用的是另一种被称为 crowding distance 的方法。个体 I 的crowding distance 用 cd(I) 表示。适应度值为i的个体用集合

F_i

表示。对于每个集合

F_i

，我们执行如下操作：

step 1:对于每一个目标k, 我们按照目标值从小到大将集合

F_i

中个体排序； step 2:假设集合

F_i

中个体有l个，则

cd_k(I[1,k])

和

cd_k(I[l,k])

等于无限，其他 (5)

$\begin{eqnarray*} cd_k(I[i,k]) = \frac{f_k(I[i-1,k])-f_k(I[i+1,k])}{f_k^{max}-f_k^{min}} \nonumber \end{eqnarray*}$ \begin{eqnarray*} cd_k(I[i,k]) = \frac{f_k(I[i-1,k])-f_k(I[i+1,k])}{f_k^{max}-f_k^{min}} \nonumber \end{eqnarray*}

其中I[i,k]表示按照第k个目标值排在第i位的个体。 step 3:计算

$cd(I)=sum_{k=1}^{K}cd_k(I)$ cd(I)=sum_{k=1}^{K}cd_k(I)

。

计算得到每个个体的 crowding distance 之后，我们不用它去调整适应度，而是用了一种别样的选择方法。我们随机选择两个个体。如果两个适应度不同，则选择适应度大的个体；如果适应度相同，则选择 crowding distance 大的个体。下图就是 fitness sharing 和 crowding distance 的示意图（左边图表示 fitness sharing, 右边图表示 crowding distance）。

多目标遗传算法保持多样性

自1985年VEGA发表之后，Fonseca、Deb 和 Goldberg 等大神引领着研究者们为了更好的多目标遗传算法贡献自己的聪明才智，引发了一波研究潮流。时光荏苒，岁月如梭。几十年过去了，转眼到了 2000 年后，多目标遗传算法的坑大部分被填完，研究基本定型，便很难看到有影响力的多目标遗传算法研究了。一篇 2006 年综述对十几年来的研究成果进行总结，算是给多目标遗传算法的研究画上了一句号。潮起了十几年又潮落了。

Snip20160218_112. 遗传编程

遗传编程是遗传算法另一个重要的后续工作。顾名思义，遗传编程中的一个个体代表了解决某个问题的候选程序，遗传编程模拟自然选择挑选出正确的程序。遗传编程是人类追求自动编程的一次尝试。遗传编程的两个重要概念是基因型和表现型。基因型就是种群个体的编码；表现型是种群个体所表示的程序片段。其实遗传算法就已经有这两个概念雏形了，遗传算法则强调了这两个概念。遗传编程之所以会强调这两个概念，因为遗传编程很难直接处理程序片段（表现型），反而容易处理程序片段的内在结构（基因型）。根据基因型形态的不同，遗传编程方法可以分为三种：线性遗传编程、基于树的遗传编程和基于图的遗传编程。

2.1 线性遗传编程

线性遗传编程有广义和狭义之分。广义线性遗传编程将候选程序编码进定长或者变长的字符串，即基因型是线性字符串。狭义线性遗传编程中的候选程序是汇编语言或者高级编程语言程序。一个狭义线性遗传编程的个体可以是一段简单 C 语言指令。这些指令作用在一个或者两个预习定义的变量或者常量上（变量数量一般为指令个数的4倍）。下图是一个狭义线性遗传编程候选程序的示例。

线性编程

除了狭义线性遗传编程之外，广义线性遗传编程还包括：Multi-Expression Programming (MEP), Grammatical Evolution (GE), Gene Expression Programming (GEP), Cartesian Genetic Programming (CGP)，和 Genetic Algorithm for Deriving Software (GADS)。其中我们就介绍一下适合电路设计的笛卡尔遗传编程 (Cartesian Genetic Programming, CGP)。比如我们要用两个加操作两个减操作和两个乘操作得到如下运算。

笛卡尔遗传编程

笛卡尔遗传编程将下面的一个候选程序编写进字符串”001 100 131 201 044 254 2573″。字符串中的三位数字“xyz”表示x操作的输入是y和z两个连线，字符串中最后的四位数字”opqr”表示输出opqr四个连线。笛卡尔遗传编程只用变异操作，而不用交叉操作。

笛卡尔遗传编程

因为笛卡尔遗传编程的表现型是图，所以有人将笛卡尔遗传编程归入基于图的遗传编程。这里，我们将所有基因型是线性字符串的遗传编程归入线性遗传编程类别。对线性遗传编程感兴趣的同学可以阅读论文 Oltean et al. (2003)。

2.2 基于树的遗传编程

基于树的遗传编程的基因型是树结构。基于树的遗传编程是遗传编程最早的形态，也是遗传编程的主流方法。在之前的博客“欺骗”深度学习的遗传算法中正则表达式生成问题用的就是基于树的遗传编程。基于树的遗传编程的交叉操作如下所示，两个颗树之间随机交换子树。

基于树的遗传编程交叉算子交叉操作

基于树的遗传编程的变异操作有两种：一种是随机变换树中的符号或者操作符，另一种是随机变换子树。下图左下角是变换符号或者操作符的结果，右下角是变换子树的结果。

基于树的遗传编程变异算子变异操作

上面的树结构（基因型）都是表达了一个数学公式，我们在树结构上定义一下语法操作符，便可以表达一段程序了。比如，下图是定义了CL操作符之后，For循环的树结构。

2.3 基于图的遗传编程

树是一种特殊的图，因此人们很自然地想到将基于树的遗传编程扩展到基于图的遗传编程。下图就是基于图的遗传编程的基因型的一个示例。

Snip20160229_5

遗传编程是人类实现“程序编写程序”的一次尝试。但到目前为止，遗传编程大体上依然只是实验室里好玩的toy system。参考文献 Oltean, Mihai, and Crina Grosan. “A comparison of several linear genetic programming techniques.” Complex Systems 14.4 (2003): 285-314.

【本文地址】

遗传算法系列之五:多目标遗传算法和遗传编程

遗传算法系列之五:多目标遗传算法和遗传编程

今日新闻

推荐新闻