一 遗传算法概述

本章简单介绍遗传算法的概念、特点

1 算法概念

遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说，其本质是一种高效，并行，全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识并自适应的控制搜索过程以求得最优解。

遗传算法常用于求解非线性最优化问题，函数最值问题，旅行商问题，背包问题。但遗传算法主要还是解决优化类问题，尤其是那种不能直接求解的十分复杂的问题。

是的，你没有看错，就是那位孟德尔~

---

2 基本特点

算法特点	介绍
智能式搜索	根据适应度（也就是目标函数）进行智能搜索
渐进式搜索	利用复制，交叉，突变，选择等操作使下一代的结果优于上一代，经过几代的运行，解就会慢慢向局部最优聚集靠拢。
得到全局最优解	利用交叉和突变操作产生新个体，扩大了搜索的范围，使得解逐渐逼近全局最优解，而不会陷入局部最优解。
黑箱式结构	依据问题的特性进行编码（输入），和确定适应度（输出）。具有只考虑输入与输出关系的黑箱式结构，并不深究输入和输出关系的原因。
通用性强	不要求明确的数学表达式，只需要一些简单的原则要求，可应用于解决离散问题、函数关系不明确的复杂问题
并行式运算	每次迭代运算都是对群体中，所有的个体同时进行运算，运算方式是搜索速度快的并行式运算。

---

3 启发式算法

启发式算法是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义:一个基于直观或经验构造的算法，在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。

简单来说，就是得到的解不一定是全局最优解，可能会和全局最优解存在一定的偏离。遗传算法也是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。它的每个解都是近似最优，不能保证是全局最优。这决定了遗传算法的每次结果都有可能不相同。但是遗传算法常用来求解十分复杂的问题，甚至连明确的表达式都没有的问题。

可以理解为牛刀，不需要过于精细的维护就能保持良好的性能，对噪声和干扰不敏感，用于处理复杂结构

---

二 原理与方法

本章介绍遗传算法的实现流程：个体编码，种群初始化，适应度计算，选择运算，交叉运算，变异运算，展开讨论每一具体步骤。

1 实现步骤

(1) 整体流程

标准遗传算法实现的基本步骤是：个体编码，种群初始化，适应度计算，选择运算，交叉运算，变异运算。遗传算法模拟基因重组与进化的自然过程,把需要解决的问题的参数编译成二进制码，也就是基因。许多基因（二进制串）组成一个染色体（个体），由染色体进行交叉，变异的运算。经过世代遗传，得到最后优化的结果。流程图如下：

(2) 生物学角度理解
一个染色体代表一个个体，N个个体形成一个种群，计算每一个个体的适应度大小。从种群中挑选适应度大的个体，进行遗传、交叉、变异等操作生成下一代种群。

(3) 数学角度理解
对某个待求解的问题，先随机生成N个初始解，形成一个解集。根据适应度函数计算每一个解的好坏，留下好的解，对留下的解进行相关操作，再生成下一组解，迭代循环，最后得到理想值。

---

1.1 个体编码

(1) 什么是编码
编码即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就成为编码。编码的目的是使后续交叉变异等操做更容易进行。

(2) 编码方法
二进制编码方法是遗传算法中最主要的一种编码方法,使用二进制符号0和1构成二进制编码符号串，代表个体基因型。符号串的长度与问题要求精度有关。但是，二进制编码在连续函数离散化时存在映射误差，符号长度不当会造成精度达不到或搜索空间增大的问题。举例说明：

• 函数 f(x) = xsin(25 pi x) + 3.0 定义域为 [-1,2],

• 假设精度为0.001，那么就是3000个数。
  需要12位二进制编码（2 ^ 11=2048）

• 需注意：12位可以达到4096个数，超出搜索范围。这会造成搜索空间增大的问题。

但仍需要以补满位数为前提，优先保证满足精度，12位二进制，在[-1,2]上分4096个数，精度为0.0007，matlab绘图如下：

---

1.2 种群初始化

(1) 初始设置
对于一个初始种群，我们需要对：种群的大小，迭代次数(即最大代数），交叉概率，变异概率，等相关参数进行初始化。

遗传算法中控制参数的选择非常关键，较大会影响到算法性能。尤其是：初始种群大小，二进制编码长度，交叉概率Pc，变异概率Pm。

【交叉运算】是产生新个体的主要方法，决定了遗传算法全局搜索能力，
【变异运算】作决定了遗传算法的局部搜索能力。所以，Pc和Pm的选择十分关键。

(2) 参数取值范围

参数名称	介绍
初始种群大小	一般情况下种群数目在10-200之间。数目较大会增加计算量，造成计算机速度降低，太小容易收敛到局部最优解
迭代次数	通常是在100-1000之间,与数据量的大小有关
交叉概率	一般取0.4 - 0.99，太高会使适应的结构很快就被破坏，概率太低搜索会始终停滞不前
变异概率	通常取0.0001-0.1， 太小会使新个体生过少，太大则使遗传算法变成随机搜索

---

1.3 适应度计算

(1) 适应度概念
适应度(Fitness):指在群体中，各个个体在优化计算中能达到或接近于或有助于找到最优解的优良程度。一般来说，一个个体如果适应度较高,遗传到下一代的概率就较大，反之适应度较低的个体遗传到下一代的概率就较小。遗传算法是一种概率引导搜索过程的算法。

【适应度函数】：度量个体适应度的函数就叫做适应度函数。适应度函数的设计应尽可能简单，这样可以减少时间复杂度和空间复杂度，降低计算的成本。

(2) 评价个体适应度过程

• 对个体编码串进行解码处理后，得到个体表现型。（就是二进制编码串进行解码，当然也有可能不是二进制串）
• 根据个体表新型计算对应个体的目标函数值。
• 根据问题类型（求最大值或最小值）,由目标函数按一定的规则转换求出个体的适应度。
• 对于适应度函数的选择，多数情况可以直接将目标函数值作为个体的适应度

例：
直接以目标函数f（x）转化为适应度函数 FIt（f（x））有：Fit(f(x))  =  f(x）目标函数求解要求 最大化Fit(f(x))  = -f(x) 目标函数求解要求 最小化

---

1.4 选择运算

(1) 基本介绍
选择又称复制，就是在群体中选择适应度较高的个体产生新群体的过程。选择操作建立在适应度函数已确立的基础上。从生物学角度讲，如果把适应度函数比作 ‘物竞’，那么选择操作就好比‘天择’。选择操作的目的就是选择出适应度较高的个体，提高全局的收敛性。更加直观的说法是：选择运算就是用来确定怎样从父代群体中选取个体遗传到下一代的操作。

(2) 实现方法
遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作，就是根据每个个体的适应度大小进行选择。下面介绍一种遗传算法常用的选择算子：轮盘赌

【轮盘赌】：每个个体进入下一代的概率就等于他的适应度值与整个种群中个体适应度值总和的比例。各个个体被选中的概率与其适应度函数值大小成正比，它是为了防止适应度数值较小的个体被直接淘汰而提出的。过程如下：

轮盘赌步骤	介绍
个体选择概率	就是指个体适应度值与整个种群中个体适应度值的总和的比。 （ 设第xi个的个体的个体选择概率表示为P（xi） ）
累积概率	指的是把每个个体的个体选择概率用线段表示，组合成一条长度为1的直线，先后顺序可以随意排列。个体的累积概率是个体前面所有数据长度的累加和。所以个体选择概率越大，对应长度区间越长
如何选择某个个体	在[0,1]中随机生成一个数，该数落在的区间，对应的个体就被选中。这就利用到了2的累积概率:个体 xi 对应有效区间为[Q(xi-1),Q(xi)]，显而易见，个体选择概率较大的个体被选中机会大。

（ 设第xi个个体的累积概率表示为Q（xi） ）

---

1.5 交叉运算

(1) 什么是交叉运算
在生物进化过程中，同源染色体交换重组，形成新染色体。模拟这个过程，遗传算法中用交叉算子产生新个体。交叉运算指对两个相互配对的染色体按某种方式相互交换其等位基因而形成两个新个体。是产生新个体的主要方法。

交叉运算之前需要对种群的个体进行两两配对，常用配对方法是随机配对。N个个体配对后形成N/2个组，交叉运算就在这些组的两个个体之间进行。常用的交叉方式为： 单点交叉，两点交叉（设置两个交叉点），均匀交叉，算数交叉。

(2) 单点交叉
单点交叉：在编码串中只设计一个交叉点，然后两个相互配对的个体在该点交换部分染色体。以两个相互配对的二进制编码串AB为例说明：

• 1.对个体两两配对（已执行）

• 2.随机设置某一基因座之后的位置为交叉点（基因座就是指串中的位置）
  

• 3.在交叉点处，依据叫交叉概率交换两个个体的部分染色体，交换后为:
  

这里就体现了编码的优点，编码使得交叉运算可以很简单的实现

---

1.6 变异运算

(1) 变异介绍
变异值是根据设置的，较小的概率，把个体编码串上的某些位置的值进行更改。类似于生物中的基因突变，比如二进制编码串中，0变异成1 , 1变异为0，从而产生新个体。交叉运算是产生新个体的主要方式，变异运算是辅助方法。

【变异】本身是一种随机算法，但同选择交叉结合之后，就能够避免因为选择和交叉而造成的某些遗传信息丢失的问题。

(2) 变异算法
变异算法目的：改善遗传算法局部搜索能力，维持群体多样性。变异算子包含：基本位变异，有效基因变异，均匀变异，边界变异等，下面简单介绍标准遗传算法中使用的 基本位变异：

• 先随机产生变异点
• 再根据变异概率将变异点基因取反（1变0,0变1）

(3) 举例说明

例：
(1) 假设x=3，采用二进制编码，编码串长度为8，设置x编译后为：1000 1111(2) 我假设第4位变异，于是：产生x’编码串：1001 1111(3) 将x’解码，得到十进制的x’，可以肯定：x’！= x （4）x’带入 适应度函数 中得到的值恰好比x的大，说明产生优秀的变异

再扩大到整个种群中N个个体，然后进行若干次迭代，就会产生许许多多的变异。总会有上述变异出适应度更高的个体的情况存在。促进了向最优解靠拢的过程。不断迭代，直至寻找到最优解。

交叉运算决定了遗传算法的全局搜索能力，而变异运算决定了局部搜索能力。
一定要注意，如果变异概率很大，那么整个搜索过程就退化为一个随机搜索过程。交叉算子和变异算子相互配合，使算法能够以优秀的性能解决问题。

---

2 总结

遗传算法实现过程：

• 把待解决的问题的参数，编码成而二进制码（或其它）也就是基因。
• 基因组成染色体（对应个体）。
• 设置对应适应度函数（目标函数）求出每个个体的适应度。
• 然后对许多染色体进行 选择运算 ， 交叉运算 ， 变异运算 。
• 再经过多次迭代（循环，或者称之为世代遗传）。
• 直至搜索到最大适应度的个体，找到最优解。

---

三 应用实例

用matlab中的GA函数求解函数最值问题。GA即实现遗传算法（Genetic Algorithm）的函数

1 GA工具使用教程

(1) matlab 中GA函数基本语法

函数格式：[x, fval] = ga(fun, nvars, A, b, Aeq, beq, lb, ub, nonlcon, options)

注意：该工具本身只提供计算最小值，后文讲如何计算最大值

---

(2) 输入参数介绍

名称	作用	使用方式
fun	目标函数（需要最小化的函数）	function handle，例如 @(x) x^2
nvars	变量个数	即优化问题的维度，几个自变量
A, b	线性不等式约束 A*x ≤ b	不需要则设为 []
Aeq, beq	线性等式约束 Aeq*x = beq	不需要则设为 []
lb	变量的下界	lb = [0, 0]，几个自变量，括号就设几个数，（简易理解：定义域下限）
ub	变量的上界	ub = [1, Inf] （即变量最大值，lnf为无穷大）
nonlcon	非线性约束函数	返回 [c, ceq]，其中 c ≤ 0 且 ceq = 0，不需要则设为 []
options	优化选项	通过 optimoptions(‘ga’, …) 设置，不需要则设为 []

【注意1】若直到末尾都不需设置参数，例如nonlcon 与options 无需设置，则可[]也可以省略
【注意2】若GA函数options 不设置，ga算法会使用默认优化选项，根据已知信息，自动调整options 参数值。
【options】参数值，就是我们上文讨论的：种群大小、最大迭代次数、交叉概率、变异函数、交叉函数等等。

---

(3)输出参数介绍

• x：找到的最优解.
• fval：最优解对应的目标函数值。

(4) 对应matlab代码

例
1 定义目标函数，如求最小化 f(x) = x₁² + x₂²fun = @(x) x^2 + 15x ;2 设置约束条件:(不需要则填写 [])* 线性不等式约束（例如 x₁ + x₂ ≤ 1）A = [1, 1];b = 1;* 变量上下界（例如 0 ≤ x₁ ≤ 5, x₂ ≥ -1）lb = [0, -1];ub = [5, Inf];* 非线性约束（需自定义函数 nonlcon.mfunction [c, ceq] = nonlcon(x)c = x(1)^2 + x(2)^2 - 1; % 非线性不等式约束 c ≤ 0ceq = []; % 非线性等式约束 ceq = 0end
3 设置遗传算法参数options = optimoptions('ga', ...'PopulationSize', 100, ...   % 种群大小'MaxGenerations', 200, ...   % 最大迭代次数'CrossoverFraction', 0.8, ...% 交叉概率'Display', 'iter');         % 显示迭代过程4 调用 ga 函数nvars = 2; % 变量个数[x, fval] = ga(fun, nvars, A, b, [], [], lb, ub, @nonlcon, options);5 输出最优解和最优值disp(['最优解: ', num2str(x)]);disp(['目标函数值: ', num2str(fval)]);

通过合理配置参数和约束，ga 函数可有效解决各类非线性、非凸优化问题

---

2 设置目标函数

例：
(1) 函数：y=x^2sin(8 pi x)+2x+3.0  (自拟)(2) 定义域：[-1,5],每隔 0.01取点(3) 求函数的最小值

---

3 搜索最小值

(1) matlab绘图

(2) 创建函数

(3) 设置GA函数
此处options使用默认设置，GA算法会根据设置数据的范围，默认初始化合适的options参数，如：种群数量，迭代次数，交叉概率等等。

答案为：

在函数中位置：

---

4 搜索最大值

(1) 调整参数
matlab里所有优化工具箱函数是求最小值，如果是要求函数的最大值，只要在编写函数的时候，把函数取负即可。做出如下更改：

运行结果为：
因为函数取负，故最大值为：10.5371，在x=4.8131处取得，见下图：

---