数学公式完整版：https://blog.csdn.net/weixin_51245887/article/details/126918727

遗传算法概述

背景知识

生物遗传概念

遗传算法中的作用

适应度（Fitness）

适应函数值。度量某个物种对于生存环境的适应程度

选择（Selection）

决定以一定的概率从种群中选择若干个个体的操作

交叉（Crossover）

通过交配原则产生一组新解的过程

变异（Mutation）

编码的某一个分量发生变化的过程

编码（Coding）

表现型到基因型的映射

解码（Decoding）

基因型到表现型的映射

群体（population）

选定的一组解

种群（reproduction）

根据适应函数值选取的一组解

适者生存

算法停止时，最优目标值的解有最大的可能被保留

个体

解

染色体（chromosome）

解的编码（字符串、向量等）

基因（gene）

解中每一分量的特征（如各分量的值）

遗传算法（GA）

概要

  • 枚举法
  • 启发式算法
  • 搜索算法

原理

  1. 是模拟生物在自然环境下的进化和遗传过程而形成的一种 自适应全局优化概率方法
  2. 其采纳了 自然进化模型，从代表问题可能潜在解集的一个 种群 开始
  3. 适者生存、优胜劣汰

算法过程

  1. 初始化。设置进化代数计数器t⭠0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)。
  2. 个体评价。计算群体P(t)中各个个体的适应度。
  3. 选择运算。将选择算子作用于群体。
  4. 交叉运算。将交叉算子作用于群体。
  5. 变异运算。将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
  6. 终止条件判断。若t≤T，则：t⭠t+1，转到步骤二；若t>T，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。
  7. 示意图 image-20220917173131637

特点

  • 遗传算法以 决策变量的编码 作为运算对象
  • 遗传算法直接以 目标函数值 作为搜索信息
  • 遗传算法同时使用 多个搜索点 的搜索信息
  • 遗传算法使用 概率搜索技术

基本遗传算法

由 Holland 提出，简称 SGA（Simple Genetic Algorithm）。

构成要素

  1. 染色体编码方法 使用 固定长度的二进制符号串 来表示群体中的个体
  2. 个体适应度评价
  3. 基本遗传算子
  4. 算法的运行参数

伪代码描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Procedure SGA
begin
// 初始值，M为个体总数，t为代数，T为最大进化数 
M=PopulationSize, t=0, T=maxGeneration;
init P(t); // 初始化群体P，一开始为第0代
while(t<=T):
    for i=1 to M do:
        Evaluate Fitness of P(t);
    for i=1 to M do:
        Selection Operation to P(t);
    for i=1 to M/2 do:
        Crossover Operation to P(t);
    for i=1 to M do:
        Mutation operation to P(t);
    for i=1 to M do:
        P(t+1)=P(t)
     t=t+1
end

算法图解参考上图

个体适应度评价

所有个体适应度必须为正数或零，不能为负数。

适应度函数变换常用方法

但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大 值，也有求函数最小值，显然上面两式保证不了所有情况下个体的适应度 都是非负数这个要求，需要进行适应度函数尺度转换，将 目标函数值 f(x) 变换为个体的适应度F(x) 。

image-20221012213710525

image-20221012213726845

比例选择又称为轮盘赌选择（Roulette Wheel ）

遗传算法的应用步骤

  1. 确定决策变量及其各种约束条件，即确定出个体的表现型 X 和问题的解空间。
  2. 建立优化模型，即确定出目标函数的类型及其数学描述形式或量化方法。
  3. 确定表示可行解的染色体编码方法，也即确定个体的基因型 X 及遗传算法的搜索空间。
  4. 确定解码方法，即确定出由个体基因型 X 到个体表现型 X 的对应关系或转换方法。
  5. 确定个体适应度的量化评价方法，即确定由目标函数值 $f(x)$ 到个体适应度 $F(x)$ 的转换规则。
  6. 设计遗传算子，即确定选择运算、交叉运算和变异运算等遗传算子的操作方法。
  7. 确定遗传算法的有关运行参数，即确定出遗传算法的 $M,T,p_{c},p_{m}$ 等参数。

image-20221012221848724

模式定理

模式

模式（schema）表示一些相似的模块。他描述了在某些位置上的具有相似结构特征的个体编码串的一个子集。

例如：模式 $H = 1**11$，模式 $H = 00**$ ，“$$”代表通配符。

模式阶

在模式H中具有确定基因值的位置数目称该模式的模式阶（schema order），记为 $ o(H)$。

例如：$o(100_01_)=5，o(*******0)=1$

模式定义长度

模式 H 中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离称为该模式的模式定义长度（Schema Defining Length），记为 $δ(H)$。

例如：$δ(11*0**_) = 3，δ(0_**1) = 4，δ(**0***) = 1$

在选择算子的作用下

$$ \frac{m(H,t)}{m(H,t+1)}=\frac{\bar{F}(t)}{f(H,t)}\ \Longleftrightarrow m(H,t+1)=m(H,t)\frac{f(H,t)}{ \bar{F}(t)}\ let \quad \frac{f(H,t)}{\bar{F}(t)}=1+C \ \Longrightarrow m(H,t+1)=m(H,t)(1+C)\ \Longrightarrow m(H,t)=m(H,O)·(1+C)^{t} $$

其中

符号

含义

$t$

在进化过程中的第 $t$ 代

$H$

模式 $H$

$m(H, t)$

当前群体 $P(t)$ 中与 $H$ 匹配的个体数

$\bar F(t)$

第 t 代群体的平均适应度

$f(H,t)$

群体中 H 隐含的总个体的平均适应度

结论：在选择算子作用下，对于平均适应度高于群体平均适应度的模式，其样本数将呈指数级增长：而对于平均适应度低于群体平均适应度的模式，其样本数将呈指数级减少。

在交叉算子的作用下

$$ m(H,t+1)≥m(H,t)·(1+C)·[1-p_{c}·\frac{δ(H)}{l-1}] $$

$δ(H)$越小，则$m(H,t)$越容易呈指数级增长；

$δ(H)$越大，则$m(H,t)$越不容易呈指数级增长。

在变异算子的作用下

某一模式被破坏的概率： $$ 1-(1-p_{m})^{o(H)} $$ 当 $p_{m}<<1$ 时： $$ 1-(1-p_{m})^{o(H)}≈o(H)·p_{m} $$ 在变异算子的作用下，模式 H 的生存概率： $$ p_{s}≈1-o(H)·p_{m} $$ $o(H)$越小，模式 H 越易于生存；

$o(H)$越大，模式 H 越易于被破坏。

在算子总作用下

$$ m(H,t+1)≥m(H,t)·\frac{f(H,t)}{\bar F(t)}·[1-p_{c}·\frac{δ(H)}{l-1}-o(H)·p_{m}] $$

⭐总结：遗传算法中，在选择、交叉和变异算子的作用下，具有低阶、短的定义长度，并且平均适应度高于群体平均适应度的模式将按指数级增长。

【积木块假设】

个体的基因块通过选择、交叉、变异等遗传算子的作用，能够相互拼接在一起，形成适应度更高的个体编码串。

遗传算法基本实现技术

编码

编码方法很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。

常见的编码分类：二进制编码、浮点编码、符号编码。

二进制编码

编码

假设某一参数的取值范围 [$U_{min},U_{max}$ ] , 我们用长度为 n 的二进制编码符号串来表示参数，共产生 $2^{n}$ 种不同的编码，δ为二进制编码的编码精度。则： $$ δ = \frac{U_{max}-U_{min}}{2^{n}-1} $$ 解码

假设某一个体的编码是： $$ X:b_{i}b_{i-1}b_{i-2}····b_{2}b_{1} $$ 则解码公式为： $$ x = U_{min}+(\sum_{i=1}^{n}b·2^{i-1})· \frac{U_{max}-U_{min}}{2^{n}-1} $$

[例] 设 -3.0 ≤ x ≤ 12.1 , 精度要求 δ = 1/10000

由编码公式

image-20220928234410284

格雷码编码

格雷码特点：两个相邻的编码串之间只有一位编码值不同。

解码和编码过程：决策变量 ↔二进制↔格雷码

浮点数编码

个体的每个基因值用_某一范围内_的一个浮点数来表示，个体的编码长度等于其决策变量的个数。

编码方法

某一个优化问题含有5个变量 $x_{i}(i=1,2, … ,5)$，每个变量都有其对应的上下限$[U_{min}^{i}, U_{max}^{i}]$，则：

image-20220929083709177

就表示一个个体的基因型，其对应的表现型是： $x = [5.80,6.90,3.50,3.80,5.00]^{T}$

符号编码

个体染色体编码串中基因值取自一个无数值含义、只有代码含义的符号集。

多参数级联编码

将各个参数分别以某种编码方法进行编码，然后再将它们的编码按一 定顺序联接在一起就组成了表示全部参数的个体编码。这种编码方法 称为多参数级联编码方法。 $$ \underbrace{b_{11}b_{12}···b_{1l_{1}}}{x{1}}\underbrace{b_{21}b_{22}···b_{2l_{2 }}}{x{2}}····\underbrace{b_{n1}b_{n2}···b_{nl_{1}}}{x{n}} $$

多参数交叉编码方法

将各个参数中起主要作用的码位集中在一起。

编码方法

  1. 先对各个参数进行分组编码
  2. 取各个参数编码串中的最高位联接在一起作为前n位编码；再取次高位同上……

参数编码： $$ \overbrace{b_{11}b_{12}b_{13}···b_{1m}}^{x_{1}}\overbrace{b_{21}b_{22}b_{23}···b_{2m}}^{x_{2}}····\overbrace{b_{n1}b_{n2}b_{n3}···b_{nm}}^{x_{n}} $$ 个体编码串： $$ b_{11}b_{21}b_{31}···b_{n1} b_{12}b_{22}b_{32}···b_{n2} ··· b_{1m}b_{2m}b_{3m}···b_{nm} $$

适应度函数

度量个体适应度的函数称为适应度函数。

目标函数

是指所关心的目标 (某一变量y) 与相关的因素 ( 某些变量$x_{i}$ ) 的函数关系。

适应度尺度变换

对个体适应度所做的扩大或者缩小变换

常见变换方法：

  • 线性尺度变换 $F^{‘}=aF+b$
  • 乘幂尺度变换 $F^{‘}=F^{k}$
  • 指数尺度变换 $F^{‘}=exp(-βF)$

（$F$：原适应度，$F’$：尺度变换后的新适应度）

选择算子

遗传算法使用选择算子（或称复制算子， Reproduction Operator）来对群体中的个体进行优胜劣汰操作；适应度 较高的个体被遗传到下一代群体中的概率较大；适应度较 低的个体被遗传到下一代群体中的概率较小.

比例选择

各个个体被选中的概率与其适应度大小成正比。设群体大小为M，个体 i 的适应度为$F_{i}$，则个体i被选中的概率$p_{is}$为: $$ p_{is}=F_{i}/\sum_{i=1}^{M}F_{i} \quad\quad (i=1,2,3,…,M) $$

最优保存策略

  1. 找出当前群体中适应度最高的个体和适应度最低的个体。
  2. 若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要高，则以当前种群中的最佳个体作为新的迄今为止的最好个体。
  3. 用迄今为止的最好个体替换掉当前群体中的最差个体

确定式采样选择

  1. 计算群体中各个个体在下一代群体中的期望生存数目$N_{i}$: $$ N_{i} = M · F_{i}/\sum^{M}_{i=1}F_{i}\quad\quad (i=1,2,3,…,M) $$
  2. 用$N_{i}$的整数部分确定各个对应个体在下一代群体中的生存数目。
  3. 按照$N_{i}$的小数部分对个体进行降序排序，顺序取前 $M-\sum ^{M}_{i=1}[N_{i}]$ 个个体加入到下一代群体中。

无回放随机选择

亦称期望值选择方法(Expected Value Model)。

  1. 计算群体中各个个体在下一代群体中的期望生存数目$N_{i}$: $$ N_{i} = M · F_{i}/\sum^{M}_{i=1}F_{i}\quad\quad (i=1,2,3,…,M) $$
  2. 若某一个体被选中参与交叉运算，则它在下一代中的生存期望数目减去0.5，若未参与交叉运算，则它在下一代中的生存期望数目减去1.0。
  3. 随着选择过程的进行，若某一个个体的生存期望数目小于0时，则该个体就不在有机会被选中。

无回放余数随机选择

  1. 计算群体中各个个体在下一代群体中的期望生存数目$N_{i}$: $$ N_{i} = M · F_{i}/\sum^{M}_{i=1}F_{i}\quad\quad (i=1,2,3,…,M) $$
  2. 用$N_{i}$的整数部分$N_{i}$确定各个对应个体在下一代群体中的生存数目。
  3. 以$F_{i}-N_{i}·\sum^{M}{i=1}F/M$ 为各个个体的新的适应度，用比例选择方法来确定下一代群体中还未确定的 $M-\sum ^{M}{i=1}N_{i}$ 个体。

排序选择

对群体中各个个体按其适应度大小来进行排序，基于这个排序来分配各个个体被选中的概率。

  1. 对群体中的所有个体按其适应度大小进行降序排序。
  2. 根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体。
  3. 以各个个体所分配到的概率值作为其能够被遗传到下一代的概率，基于这些概率值用比例选择的方法来产生下一代群体。

随机联赛选择

每次选取几个个体之中适应值最高的一个个体遗传到下一代群体。

  1. 从群体中随机选取N个个体进行适应度大小的比较，将其中适应度最高的个体遗传到下一代群体中。
  2. 将上述过程重复M次，就可得到下一代群体中的M个个体。

交叉算子

交叉算子是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体

单点交叉

在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对的部分染色体。

特点：若邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度的话，则这种单点交叉操作破坏这种个体性状和降低个体适应度的可能性最小。

双点交叉

在个体编码串中随机设置两个交叉点，然后再进行部分基因交换。

  1. 在相互配对的两个个体编码串中随机设置两个交叉点
  2. 交换两个个体在所设定的两个交叉点之间的部分染色体 image-20221003172723469

多点交叉

在个体编码串中 随机设置两个交叉点，然后进行基因交换。

image-20221003172903979

均匀交叉

两个配对个体的每一个基因座上的基因都以相同的交叉概率进行交换。

  1. 随机产生一个与个体编码串长度等长的屏蔽字 $W=w_{1}w_{2}…w_{i}…w_{l}$，其中 $l$ 为个体编码串长度。
  2. 由下述规则从 A 和 B 两个父代个体中产生出两个新的子代个体 A’ 和 B’。
    • 若 $w_{i}=0$，则 A’ 在第 i 个基因座上的基因值继承 A 的对应基因值，B’ 在第 i 个基因座上的基因值继承 B 的对应基因值。
    • 若 $w_{i} =1$，则 A’ 在第 i 个基因座上的基因值继承 B 的对应基因值，B’ 在第 i 个基因座上的基因值继承 A 的对应基因值。
    image-20221003173710535

算术交叉

由两个个体的线性组合而产生出两个新的个体。

假设有两个个体$X_{A}$和$X_{B}$之间进行算术交叉，则交叉运算后所产生的两个新个体是: $$ \left{\begin{matrix}

X_{A}^{t+1} = \alpha X_{B}^{t} + (1 - \alpha )X_{A}^{t} \ X_{B}^{t+1} = \alpha X_{A}^{t} + (1 - \alpha )X_{B}^{t} \end{matrix}\right. $$ 其中 α 是一参数，如果 α (0< α <1)是一个常数，则为 均匀算术交叉；如果 α 是一个由进化代数所决定的变量，则称为非均匀算术交叉。

  1. 确定两个个体进行线性组合的系数 α。
  2. 依据上式生成新的两个个体。

变异算子

变异算子是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其它等位基因来替换，从而形成一个新的个体。

基本位变异

个体编码串中以变异概率 $P_{c}$ 随机指定的某一位或某几位基因座上的基因值作变异运算。

均匀变异

分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。

假设有一个个体为$X = x_{1}x_{2}…x_{k}…x_{l}$，若$x_{k}$为变异点，其取值范围为$[U^{k}{min}, U^{k}{max}]$，在该点对个体 X 进行均匀变异操作后，可得到一个新的个体 $X’= x_{1}x_{2}…x’_{k}…x_{l}$，其变异的新基因值是： $$ x’{k} = U^{k}{min}+r·(U_{max}^{k}-U_{min}^{k}) $$ 其中，r 为 [0,1] 范围内符合均匀分布的一个随机数。

  1. 依次指定个体编码串中的没个基因座为变异点。
  2. 对每一个变异点，以变异概率 $P_{m}$ 从对应基因的取值范围内取一随机数来替代原有基因值。

边界变异

随机地取基因座的两个对应边界基因值之一去替代原有基因值。(是均匀变异操作的一个变形)

在进由$X = x_{1}x_{2}…x_{k}…x_{l}$向$X’= x_{1}x_{2}…x’_{k}…x_{l}$的边界变异操作时，若变异点xk的基因取值范围为$[U^{k}{min}, U^k{max}]$，则新的$x’_{k}$由下式确定： $$ x’{k}=\left{\begin{matrix} U^{k}{min} \quad ,\quad if \quad random(0,1) =0 \ U^{k}_{max} \quad ,\quad if \quad random(0,1) =1 \end{matrix}\right. $$ 式中，random(0，1) 表示以均等的概率从0、1中任取其一。

非均匀变异

不是取均匀分布的随机数去替换原有的基因值，而是对原有基因作一随机扰动，以扰动后的结果作为变异后的新基因值。

在进由$X = x_{1}x_{2}…x_{k}…x_{l}$向$X’= x_{1}x_{2}…x’_{k}…x_{l}$的边界变异操作时，若变异点xk的基因取值范围为$[U^{k}{min}, U^k{max}]$，则新的$x’_{k}$由下式确定： $$ x’{k}=\left{\begin{matrix} x{k}+ \Delta (t,U^{k}{max}-x{k}) \quad ,\quad if \quad random(0,1) =0 \ x_{k}- \Delta (t,x_{k}-U^{k}_{min}) \quad ,\quad if \quad random(0,1) =1 \end{matrix}\right. $$ △(t, y)表示 [0,y] 范围内符合非均匀分布的一个随机数，要求随着进化代数t的增加，△(t, y)接近于0的概率也逐渐增加。 例如，△(t, y)可按下式定义： $$ \Delta (t, y) = y·(1-r^{(1-t/T)b}) $$ 其中，r为 [0,1] 范围内符合均匀分布的一个随机数，T是最大进化代数，b是一个系统参数。它决定了随机扰动对进化代数t的依赖程度。

高斯变异

进行变异操作时，用符合均值为μ、方差为$σ^{2}$的正态分布的一个随机数来替换原有基因值。

假定有12个在[0,1]范围内均匀分布的随机数$r_{i}(i=1,2,..,12)$，则符合$N(μ,σ^{2})$正态分布的一个随机数Q可由下式求得: $$ Q=μ+σ(\sum_{i=1}^{12}r_{i}-6) $$

遗传算法高级实现技术

倒位算子

倒位算子是颠倒个体编码中随机指定的两个基因座之间的基因排列顺序，从而形成一个新的染色体。

过程：

  1. 在个体编码串中随机指定两个基因座之后的位置为倒位点。
  2. 以倒位概率 $P_{i}$ 颠倒这两个倒位点之间的基因排列顺序。

image-20221007234228946

二倍体

生物学中，二倍体是指含有两个同源基因组的个体。

重要特性

  1. 二倍体的记忆能力 能够记忆以前经历过的环境及变化。
  2. 显性操作的鲁棒性 在显性操作的作用下，能够用其另一同源染色体对其进行校正。

双基因座显性映射

由 Hollstien 提出，每个二进制基因用两个基因来描述，一个称为 函数基因，取通常含义的 1 或 0；另一个称为 修饰基因，取值为 M（显性） 或 m（隐形）。当两个同源染色体中至少有一个修饰基因是M时，呈显性，否则为隐性。

之后 Hollstien 简化为 单基因座显性映射 ，描述基 因的字符集为${0, 1, 1_{0}}$，其中 $1_{0}$ 为隐性的 1，1 为显性的 1。

image-20221008143428436

与GA不同

  1. 显性形状也能进化，同源染色体之间需进行交叉操作
  2. 变异操作需考虑隐性性状
  3. 对个体进行交叉、变异运算后，需进行显性操作

DiploidyGA算法

  1. 初始化，并设置进化代数计数器初值：t=1 。
  2. 随机产生具有二倍体结构的初始群体 P(0)。
  3. 对初始群体 P(0) 进行显性操作。
  4. 评价初始群体P(0)中各个个体的适应度。
  5. 交叉操作：$P’(t)⬅Crossover[p(t)]$。由每两个随机配对的二倍体个体进行交叉操作时，共可产生四个单倍体个体。
  6. 变异操作：$P’’(t)⬅Mutation[p’(t)]$ 。在对群体中各个个体进行变异操作时，需要考虑隐性基因的作用。
  7. 对群体$P’’(t)$进行显性操作。
  8. 评价群体$P’’(t)$中各个个体的适应度。
  9. 个体选择、复制操作。
  10. 终止条件判断。若不满足终止条件，则：ｔ⬅ｔ＋１，转到第３步，继续进行进化操作过程；若满足终止条件，则输出当前最优个体，结束。

变长度染色体遗传算法

  • 编码 $$ X^{m}:(i_{1},v_{i})(i_{2},v_{2})···(i_{k},v_{k})···(i_{n},v_{n}) $$ $i_{k}$是所描述的基因在原常规染色体中的 基因座编号，$v_{k}$为对应的基因值。 例： image-20221008152328932
  • 解码 这能有什么用？？？？这么能扯

算法步骤(MessyGA)

  1. 初始化。随机产生M个染色体，长度全部为 k的个体，以它们作为变长度遗传算法的初始个体集合P(0)，其中k为根据问题的不同而设定的一个参数，并且 $k ≤ l $。
  2. 适应度评价。
  3. 基本处理阶段。对群体P(t)施加选择算子，以保留适应度较高的个体。
  4. 并列处理阶段。对群体P(t)世家变异算子、切断算子和拼接算子，以生成新的个体。
  5. 重复2-4步，直到满足终止条件为止。

切断算子

切断算子以某一预先指定的概率，在变长度染色 体中随机选择一个基因座，在该处将个体的基因型 切断，使之成为二个个体的基因型 。

拼接算子

拼接算子以某一预先指定的概率，将二个个体的 基因型连接在一起，使它们合并为一个个体的基因型。

遗传算法的运行参数

  • 编码串的长度 l
  • 群体大小M（一般建议取值20~100）
  • 交叉概率$P_{c}$（一般建议取值0.4~0.99）
  • 变异概率$P_{m}$（一般建议取值0.0001~0.1）
  • 终止代数T（一般建议取值100~1000）
    • 规定最大迭代次数T
    • 规定最小的偏差
    • 观察适应度的变化趋势
  • 代沟G
    • 表示每一代群体中被替换掉的个体在全部个体中所占的百分比。
    • G=1.0表示群体中的全部个体都是新产生的。

约束条件的处理方法

搜索空间限定法

对遗传算法的搜索空间的大小加以限制，使得搜索空间中表示一个个体的点与解空间中表示一个可行解的点有一一对应关系。

实现方法：1、用编码方法来保证总是能够产生出在解空间中有对应可行解的染色体。

2、用程序来保证直到产生出在解空间中有对应可行解的染色体之前，一直进行交叉运算和变异运算。

可行解变换法

寻找出一种个体基因型个个体表现型之间的多对一的变换关系，使进化过程中所产生的个体总能够通过这个变化而转化成解空间中满足约束条件的一个可行解。

罚函数法

对在解空间中无对应的可行解的个体，计算其适应度时，处以一个罚函数，从而降低个体适应度，使该个体被遗传到下一代群体中的机会减少。

下式对个体适应度进行调整： $$ F’(X)=\left{\begin{matrix} F(X) \quad \quad \qquad X 满足约束条件\ F(X)-P(X) \quad X不满足约束条件 \end{matrix}\right. $$ F(X)为原适应度，F’(X)为新适应度，P(X)为罚函数。

小生境遗传算法

在生物学上，**小生境(Niche)**是指特定环境下的一种生存环境。

生物在 其进化过程中，一般总是与自己相同的物种生活在一起，共同繁衍后 代；它们也都是在某一特定的地理区域中生存。

实现方法

  1. 基于预选择的小生境———（Cavicchio，1970）
  2. 基于排挤的小生境————（De Jong，1975）
  3. 基于共享函数的小生境——（Goldberg和Richardson，1987）

基于预选择的小生境算法

仅当新产生的子代个体的适应度 超过其父代个体的适应度 时，所产生出的子代个体才能替换其父代个体而遗传到下 一代群体中，否则父代个体仍保留在下一代群体中。

基于排挤的小生境算法

算法步骤：

  1. 初始化。建立初始群体，确定遗传参数，设定排挤银子CF。
  2. 计算个体适应度。
  3. 遗传操作（选择、交叉和变异）
  4. 从当前群体中随机选取群体规模的1/CF个个体组成排挤因子成员。
  5. 比较新产生的个体与排挤因子成员中最相似的个体，形成新的当前群体。
  6. 重复2-6步，直到满足终止条件。

特点：随着排挤过程的进行，群体中的个体逐渐被分类，从而形成各个小的生存环 境，并维持了群体的多样性。

基于共享函数的小生境算法

共享函数(sharing function)：用来确定每个个体在群体中的 共享度。一个个体的共享度等于该个体与群体内的 各个其它个体之间的共享函数值的总和。

设 $d_{ij}$ 表示个体 i 和个体 j 之间的关系密切程度，S为共享函数，$S_{i}$ 表示个体 i 在群体中的共享度: $$ S_{i}=\sum_{j=1}^{n}S(d_{ij}) $$ 个体适应度$f(i)$: $$ f_{s}(i)=f(i)/S_{i} $$

通过反映个体之间相似程度的 共享函数 来调整群体中各个个体的适应度，从而在这以后的群体进化过程中，算法能够依据这个调整后的新适应度来进行选择运算，以维护群体的多样性，创造出小生境的进化环境。

应用

多峰值函数全局最优化

在多峰值函数全局最优化中的应用：（没啥用。。。）

  • 首先两两比较群体中各个个体之间的距离，若这个距离在 预先指定的距离L之内的话，再比较两者之间的适应度大 小，并对其中适应度较低的个体施加一个较强的罚函数， 极大地降低其适应度，这样，对于在预先指定的某一距离 L之内的两个个体，其中较差的个体经处理后其适应度变 得更差，它在后面的进化过程中被淘汰掉的概率就极大。
  • 也就是说，在距离L之内将只存在一个优良的个体，从而 既维护了群体的多样性，又使得各个个体之间保持一定的 距离，并使得个体能够在整个约束空间中分散开来，这样就实现了一种小生境遗传算法。

算法过程

  1. 设置进化代数计数器t⬅1；随机生成M个初始个体组成初始群体P(t)，并求出各个个体的适应度$F_{i}\quad(i=1,2,···,M)$。
  2. 依据各个个体的适应度对其进行降序排序，记忆前N个个体(N<M)。
  3. 遗传运算（选择算子、交叉算子和变异算子）
  4. 小生境淘汰。将变异算子得到的 M 个个体和②中所记忆的N个个体合并在一起，得到一个含有M+N个个体的新群体；对这M+N个个体，求出每两个个体$X_{i}$和$X_{j}$之间的海明距离。当 $X_{i}-X_{j}<L$ 时，比较个体$X_{i}和X_{j}$的适应度大小，并对其中适应度较低的个体处以罚函数： $$ F_{min}(x_{i},x_{j})=Penalty $$
  5. 依据这M+N个个体的新适应度对各个个体进行降序排序，记忆前N个个体。
  6. 结束判定

混合遗传算法

特点

  • 引入了局部搜索过程
  • 增加了编码变换操作过程

基本原则

  1. 尽量采用原有算法的编码
  2. 利用原有算法的优点
  3. 改进遗传算子

*模拟退火算法

基于金属退火的机理而建立起的一种全局最优化方法，它能够以随机搜索技术从概率的意义上找出目标函数的全局最小点。

构成要素

  1. 搜索空间
  2. 能量函数E(x)
  3. 状态转移规则P
  4. 冷却进度表T(t)

算法过程

  1. 随机产生一个初始解，以它作为当前最优解，并计算目标函数值。
  2. 设置初始温度：$T=T_{0}$。
  3. 设置循环计数器初值：t=1。
  4. 对当前最优解作一随机变动,产生一新的解。计算新的目标函数值，并计算 目标函数值的增量D。
  5. 如果D＜0，则接受该新产生的解为当前最优解； 如果D＞0，则以概率p = exp(-D/T)接受该新产生的解为当前最优解。
  6. 如果t＜终止步数，则：t=t+1，转向第4步。
  7. 如果未到达冷却状态，则：T=T(t)，转向第3步； 如果已到达冷却状态，则：输出当前最优点，计算结束。

略。。。

数值函数和多目标优化

数值函数优化

纯数值函数优化

专门设计了一些具有复杂数学特征的纯数学函数，通过遗传算法对这些函数的优化计算情况来测试各种遗传算法的性能。

常用测试函数

  1. 连续函数或离散函数
  2. 凹函数或凸函数
  3. 二次函数或非二次函数
  4. 低维函数或高维函数
  5. 确定性函数或随机性函数
  6. 单峰值函数或多峰值函数

多目标优化

*GA的性能评估

  1. 适应值函数计算次数 发现同样适应性的个体，或者找到同样质 量的可行解，所需要的关于个体评价的适应值函数的计算次数（function evaluations）。

    该值越小说明相应GA的搜索效率越高。

  2. 在线和离线性能指标
    • 在线性能指标 含义：表示了算法从开始运行一直到当前为止的 时间段内性能值的平均值，它反映了算法的动态性能。 在环境e下策略s的在线性能 $X_{e}(s)$定义为： $$ X_{e}(s)=\frac{1}{T}\sum_{t=1}^{T}f_{e}(t) $$ $f_{e}(t)$是在环境e下第t时刻的平均目标函数值或平均适应度。
    • 离线性能指标 含义：表示了算法运行过程中各进 化代的最佳性能值的累积平均，它反映了算法的收敛性能。 在环境e下策略s的在线性能 $X_{e}^{*}(s)$定义为： $$ X_{e}^{}(s)=\frac{1}{T}\sum{t=1}^{T}f_{e}^{_}(t) $$ $f_{e}^{ *}(s)$是在环境 e 下［0, t］时间段内最好的目标函数值或最大的适应度。
  3. 最优解搜索性能 GA用于函数优化的目的就是发现问题的全局最优解， 所以通常采用当前群体发现的最佳可行解的改善情况作为度量GA搜索能力的基本指标。

基本概念

  1. 设$𝑋 ⊆ 𝑅^{𝑚}$是多目标优化模型的约束集， $𝑓(𝑥) ∈ 𝑅^{𝑝}$是多目标优化时的向量目标函数，$ 𝑥1 ∈ 𝑋, 𝑥2 ∈ 𝑋$ 。若 $$ 𝑓_{𝑘}(𝑥_{1}) ≤ 𝑓_{𝑘}(𝑥_{2}) (∀𝑘 = 1,2, ⋯ 𝑝) $$ 并且 $$ 𝑓_{𝑘}(𝑥1) < 𝑓_{𝑘}(𝑥2) (∃𝑘 = 1,2, ⋯ 𝑝) $$ 则称解𝑥1比解𝑥2优越。
  2. 设$𝑋 ⊆ 𝑅^{𝑚}$ 是多目标优化模型的约束集， $𝑓(𝑥) ∈ 𝑅^{𝑝}$ 是向量目标函数。若 $𝑥^{∗} ∈ 𝑋$，并且$x^{}$比 X 中的所有其他点都优越，则称 $x^{}$是多目标极小化模型的最优解。
  3. 设$𝑋 ⊆ 𝑅^{𝑚}$ 是多目标优化模型的约束集，$ 𝑓(𝑥) ∈ 𝑅^{𝑝}$ 是向量目标函数。若 $\tilde{𝑥}∈ 𝑋$，并且不存在比 $\tilde{𝑥}$ 更优越的 $x $，则称 $\tilde{𝑥}$ 为多目标极小化模型的 Pareto最优解，或称为非劣解。

多目标优化问题的最优解x *就是使向量目标函数f(x) 的每一个子目标函数都同时到达最优点的解.

多目标优化问题的Pareto最优解仅仅只是它的一个可以接受的“不坏”的解，并且通常的多目标优化问题大多都具有很多个Pareto最优解.

求解多目标优化问题的首要步骤和关键步骤是求出其 所有的Pareto最优解.

求解算法

  1. 权重系数变化法 对于一个多目标优化问题，若给其各个子目标函数 $𝑓_{𝑖 }(𝑥)\quad (i＝1，2，…，p)$，赋予不同的权重$𝑤_{i}(i＝1，2，… ，p)$，其中各$𝑤_{𝑖}$的大小代表相应子目标$𝑓_{𝑖}(𝑥)$ 在多目标优化问题中的重要程度。则各个子目标函数的线性加权和可表示为: $$ u(f(x))=\sum_{i=1}^{p}w_{i}f_{i}(x) $$ 以这个线性加权和作为多目标优化问题的评价函数，则多目标优化问题就可转化为单目标优化问题。
  2. 并列选择法
    1. 先将群体中的全部个体按子目标函数的数目均等地划分为一些子群体
    2. 对每个子群体分配一个子目标函数，各个子目标函数在其相应的子群体中独立地进行选择运算
    3. 各自选择出一些适应度较高的个体组成一个新的子群体
    4. 所有这些新生成的子群体合并为一个完整的群体，在这个完 整的群体中进行交叉运算和变异运算
    5. 不断地进行“分割—并列选择—合并”过程
    最终可求出多目标优化问题的Pareto最优解。
  3. 排序选择法 基于“Pareto最优个体”的概念来对群体中的各个个体进行排序，依据这个排列次序来进行进化过程中的选择运算。从而使得排在前面的Pareto最优个体将有更多的机会遗传到下一代群体中。如此这样经过一定代数的循环之后，最终就可求出多目标优化问题的Pareto最优解。
  4. *共享函数法
  5. *混合法

粒子群优化算法

简介

定义

粒子群优化算法（Particle Swarm Optimization，PSO）是进化计算的一个分支，是一种模拟自然界的生物活动的随机搜索算法。

PSO 模拟了自然界鸟群捕食和鱼群捕食的过程。通过群体中的协作寻找到问题的全局最优解。它是 1995 年由美国学者 Eberhart 和 Kennedy 提出的。

设想这样一个场景：一群鸟在随机搜索食物。已知在这块区域里只有一块食物，所有的鸟都不知道食物在哪里，但它们能感受到当前的位置离食物还有多远。

那么，找到食物的最优策略是什么呢？

  • 搜寻目前离食物最近的鸟的周围区域
  • 根据自己飞行的经验判断食物的所在

PSO的基础——信息的社会共享

每个寻优的问题解都被想像成一只鸟，称为“粒子”，所有粒子都在一个 N 维空间进行搜索； 所有的粒子都由一个fitness function 确定适应值以判断目前的位置好坏； 每一个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置；每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据它本身的飞 行经验以及同伴的飞行经验进行动态调整。

特点

  • 优点
    1. 设置参数较少
    2. 易于理解和描述
    3. 收敛速度较好
    4. 实现容易
  • 缺点
    1. 容易陷入局部最优
    2. 收敛精度不高
    3. 后期收敛速度较慢

算法流程

  1. 初始化 初始化粒子群体（群体规模为n），包括随机位置和速度。
  2. 评估 根据适应度函数，评估每个粒子的适应度。
  3. 找到局部最优 对每个粒子，将其当前适应值与其个体历史最佳位置（Pbest）对应的适应度作比较，如果当前的适应度更高，则将用当前位置更新历史最佳位置Pbest。
  4. 找到全局最优 对每个粒子，将其当前适应值与全局最佳位置（Gbest）对应的适应度作比较，如果当前的适应度更高，则将用当前粒子的位置更新全局最佳位置Gbest。
  5. 更新 根据公式 $$ v_{k+1}=c_{0}v_{k}+c_{1}\xi (p_{k}-x_{k})+c_{2}\eta(p_{g}-x_{k})\ x_{k+1}=x_{k}+v_{k+1} $$ 更新每个粒子的速度和位置
  6. 若未达终止条件，则回到第2步
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~

桂ICP备2024024328号