神经网络与遗传算法之欧阳体创编

5.4 神经网络与遗传算法简介

时间：2021.02.03 创作：欧阳体 在本节中，我们将着重讲述一些在网络设计、优化、性能分析、通信路由优化、选择、神经网络控制优化中有重要应用的常用的算法，包括神经网络算法、遗传算法、模拟退火算法等方法。用这些算法可以较容易地解决一些很复杂的，常规算法很难解决的问题。这些算法都有着很深的理论背景，本节不准备详细地讨论这些算法的理论，只对算法的原理和方法作简要的讨论。 5.4.1神经网络

1. 神经网络的简单原理

人工神经网络（ Artificial Neural Networks， 简写为ANNs）也简称为神经网络（NNs）或称作连接模型（Connectionist Model） ，是对人脑或自然神经网络（Natural Neural Network）若干基本特性的抽象和模拟。人工神经网络以对大脑的生理研究成果为基础的，其目的在于模拟大脑的某些机理与机制，实现某个方面的功能。所以说, 人工神经网络是由人工建立的以有向图为拓扑结构的动态系统，它通过对连续或断续的输入作出状态相应而进行信息处理。它是根据人的认识过程而开发出的

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

一种算法。假如我们现在只有一些输入和相应的输出，而对如何由输入得到输出的机理并不清楚，那么我们可以把输入与输出之间的未知过程看成是一个“网络”，通过不断地给这个网络输入和相应的输出来“训练”这个网络，网络根据输入和输出不断地调节自己的各节点之间的权值来满足输入和输出。这样，当训练结束后，我们给定一个输入，网络便会根据自己已调节好的权值计算出一个输出。这就是神经网络的简单原理。

2. 神经元和神经网络的结构

如上所述，神经网络的基本结构如图5.35所示：

图5.35

神经网络一般都有多层，分为输入层，输出层和隐含层，层数越多，计算结果越精确，但所需的时间也就越长，所以实际应用中要根据要求设计网络层数。神经网络中每一个节点叫做一个人工神经元，他对应于人脑中的神经元。人脑神经元由细胞体、树突和轴突三部分组成，是一种根须状蔓延物。神经元的中心有一闭点，称为细胞体，它能对接受到的信息进行处理，细胞体周围的纤维有两类，轴突是较长的神经纤维，是发出信息的。树突的神经纤维较短，而分支众多，是接收信息的。一个神经元的轴突末端与另一神经元的树突之间密切接触，传递神经元冲动的地方称为突触。经过突触的信息传递是有方向性的，不同的突触进行的冲动传递效果不一样，有的使后一神经元发生兴奋，有的使其发生抑制。

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

由人脑神经元的工作机理，人们构造了人工神经元的数学模型，它是人脑的模拟和简化，如图5.36所示。

图5.36 McCulloch-Pitts网络

在图中，wi是表示神经元对信息xi的感知能力，称为关联权，fz称为输出函数或激活函数，采用激活函数的人工神经网络也称阈网络。McCulloch-Pitts输出函数定义为

其中，sgn()为符号函数，称为阈值。

一般来说，一个人工神经元有多个输入和一个输出，另外有一个激活函数，不同的激发函数对应了不同的网络，也决定了网络的用途。从方程可以看出，当wi确定时，任给一组输入

xi，i1,•••,n，也就很容易得到输出。而现在我们的想法是：对给

定的输入，确定权数wi，使得通过方程计算出来的输出尽可能与实际值吻合，这即是学习的过程。学习也称为训练，指的是通过神经网络所在环境的刺激作用调整神经网络的权数wi，使得神经网络对外部环境以一种新的方式作出反应。学习分为有指导学习和无监督学习：在有正确输入输出数据条件下调整和确定权数wi的方法称为有指导学习；而在只知输入数据不知输出结果的前提下确定权数的方法称为无监督学习。人工神经网络的主要工作就是通过学习，建立模型和确定wi的值。

神经网络按照网络结构和激发函数的不同可分为许多种，我们在此只对感知器、BP网络及Hopfield神经网络进行简介。

3．感知机

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

首先介绍单层前向神经网络。单层前向神经网络的模型结构如图5.37所示。

或用矩阵表示为 其中，W(wij)mn为权系数矩阵，X，Y，分别为输入向量、输出

向量及阈值向量。

确定权数wij的基本思想是修正wij使得输入输出偏差尽可能小。权的修正公式为：

wij(t)t(dj(t)yj(t))xi(t)mnW(t1)W(t)W(t),W(t)(wij(t))，

，其中，

xi(t)，dj(t)，i1,•••,m，j1,•••,n分别表示第t组用于学习的输入和期望输出数据，t称为学习效率，用于控制调整速度。与权值修正原理类似，阈值修正公式可假设为：(t1)(t)(t),(t)t(dj(t)yj(t))n1，通过更新权数和阈值使得输入输出偏差趋于零。若将激活函数f()取为阶跃函数，上述思想即是感知机原理。

图5.37

由此，我们给出感知机学习规则算法步骤为：

用t表示学习步骤的序号，t0表示学习前的神经网络的初始状态。

第1步：赋初值。

给网络上权数和阈值赋初值，如wij0，i0； 第2步：计算样本实际输出。

选择一个样本作为网络输入，计算样本在目前神经网络中的实际输出。如，对于第p个样本，感知机输出为：

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

Y(p)(Y1(p)，•••，Y(p))n，

其中，Yi(p)f(wijxji)，i1,,n

•••第3步：计算误差。

计算感知机输出的实际结果与期望输出之差：tDpYp 第4步：权数修正。

如果t0，则转第2步，否则调整权值：

第5步：若训练样本已完全输入或输出误差小于预设值，则学习结束；否则，转第2步继续学习。

如果对给定的两类样本数据(通常就是用于学习的输入数据)，在空间中可以用一条直线（平面）将其分开，则称该样本数据是线性样本，否则称为非线性样本，对样本进行分类或识别即属于人工神经网络的重要应用之一。感知机可以识别二值逻辑加问题，而不能识别异或问题。对于非线性问题，可以用反向传播（BP）模型解决。

4. BP网络

图5.38 多层前向神经网络结构

BP网络应用得最为广泛，最为重要的一种神经网络。这种网络一般有多层，有输入层，输出层和隐含层，上一层的输出即是下一层的输入，输出层所在的层数就是神经网络的层数。一般的多层前向神经网络结构如图5.38所示。

在实际应用中，BP网络的激活函数一般采用S型函数：

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

f(z)11ez，这是因为S型函数有很好的函数特性，其效果又近

似于符号函数，现主要讨论采用S型函数的多层前向神经网络的学习方法。

假设有一个K层的神经网络，从第0层到第1层的原始输入向量、权矩阵、第1层神经元接受向量和第1层输出向量以及它们之间的关系为：

1z1x11xz22XZ1W1TX11xzn1n0，W1(wij)n0n1，1y11y2Y1f(Z1)1yn1，

第k1层到第k层的权矩阵、神经元接受向量和输出向量以及它们之间的关系分别为：

z1ky1kkkzy22ZkWkTYk1Ykf(Zk)kkkzWk(wij)nk1nknkynk，，

其中，

yikf(zik)。

我们先讨论单样本学习规则。学习规则是：确定W，使得 最小，其中

TD(d1，d2，•••，dnK)为理想输出。

采用S型函数的前向多层神经网络的反推学习(BP)算法步骤如下：

第1步：选定学习的数组{X(t)，D(t)}，t1,2,始权矩阵W(0)；

第2步：用学习数据X(t)计算Y1(t)，Y2(t)，••••••,T，随机确定初

，Yk(t)；

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

第3步：计算

F(W)wKijnK1nKy1K1K1y22(BK)TK1ynK1①

Kdy1Kdy2BKdiagK,K,dz1dz2KdynK,KWK1BK1dznK，

T其中，

KKBK1dy,dy2,112K,WK1I,dnKynK。

F(W)wK1ijnK2nK1②

y1K2K2y22(BK2)TK2ynK1，

K1dyn,KK1WKBKdznK1

K1dy1K1dy2BK1diagK1,K1,dz2dz1F(W)wkijnk1nk③kK2时，其中，

kdy1kdy2Bkdiagk,k,dz1dz2y1k1k1y22(Bk)Tk1ynk1，

kdynk,kWk1Bk1dznk。

，修正公式为：

第4步：反向修正

Wk(t1)Wk(t)Wk(t)，kK,K1,•••,1W(t)，

1F(W)Wk(t)t(t)k2wijnk1nk其中，

y1k1(t)k1y2(t)t(Bk(t))Tk1ynk1(t)。

第5步：循环利用T个学习样本，重复第2步～第4步，对网络权数进行调整，直到整个训练集误差最小（网络达到稳定状

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

态）。

当激活函数

dykjdzkjf(x)11ex时，

，代入①、②、③使计

kf(zkj1,•••,nkj)(1f(zj))，i1,•••,nk1，算可以得以简化。

BP网络的用途十分广泛，可用于以下方面：①函数逼近：用输入矢量和相应的输出矢量训练一个网络逼近一个函数；②模式识别：用一个特定的输出矢量将它与输入矢量联系起来；③分类：把输入矢量以所定义的合适方式进行分类；④数据压缩：减少输出矢量维数以便于传输或存储。

5. Hopfield神经网络

前面介绍的感知机和BP网络都属于前向网络。前向网络结构简单、易于编程，但计算能力不够强大。反馈神经网络是一个反馈动力学系统，具有更强的计算能力。其一般结构如图5.39所示。

图5.39 反馈神经网络的一般结构

反馈型神经网络中，神经元之间信息交互关系不再是从一层传递到另一层，而是各神经元之间都存在关系，存在从输出到输入的反馈，所以反馈型神经网络可能是不稳定的。反馈型神经网络有连续型和离散型两类，连续型用微分方程描述，离散型用差分方程描述。

J.Hopfield将神经网络和动力学系统研究结合起来，于20世纪

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

80年代提出了一个全新的神经网络模型—Hopfield神经网络，并把一个最优化问题的目标函数转换成网络的能量函数，把问题的变量对应于网络的状态，求解出了旅行商问题的准优解。

Hopfield神经网络属于反馈型神经网络，若Hopfield神经网络的权数矩阵是对角线元素为0的对称矩阵，即：wij0，

wijwji，则可以证明这种神经网络是稳定网络，即反馈与迭代

的计算过程所产生的变动越来越小，一直到达平衡状态。

1）离散Hopfield神经网络

离散Hopfield神经网络神经元的输出为离散值0和1，分别代表神经元抑制和激活状态，若神经元的输出信息小于阈值，神经元输出值为0；反之输出值为1。对于有n个神经元的离散Hopfield神经网络，其权数矩阵为nn维对称阵，每个神经元都有一个阈值，故有一个n维的阈值向量，权数矩阵和阈值矢量就定义了唯一一个n个神经元的离散Hopfield神经网络。

Hopfield网络中的神经元公式可表示为：

其中，yi(0)表示神经元i的初始状态，yi(t1)表示神经元i在

t1时刻的状态，同时也是神经元i在t1时刻的输出，i表示神

经元i的阈值。一个n个神经元的离散Hopfield网络在t时刻的状

•••，y(t)]n态可以用一个n维向量表示为：Y(t)[y1(t)，y2(t)，T。

若采用符号激活函数时，将Hopfield网络的能量函数定义为：

任意神经元的能量函数为：

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

容易推出从t时刻到t1时刻的能量变化量为

由于采用的是符号激活函数，所以无论神经元i的状态变化如何，显然有Ei0，其中等号仅在神经元i的状态不变时成立。又由于神经元i的任意性，所以当网络按某一规则进行状态更新后，网络的总能量在减少。这样经过不断的迭代，网络最终达到稳定状态。

在算法的构造上可以采用同步和异步两种方式，异步算法就是每次只调节一个神经元，其它神经元保持不变。同步算法就是同一时刻对所有神经元同时调整。

下面仅给出Hopfield网络异步算法的基本步骤，对于同步，读者不难自己给出。

Hopfield网络异步算法：

第1步：初始化。任选一个初始状态

Y(0)＝0,1n；

第2步：更新状态。随机选取一个神经元，进行状态更新： 第3步：检验。检验Y(t)是否为网络的平衡点，若是转第4步；否则，转第2步；

第4步：输出。输出Y(t)。 2）连续Hopfield神经网络

Hopfield利用模拟电子线路功能构造了反馈型神经网络的电路模型，建立的能量函数表达式为

nn1nn1E(y)wijyiyjIiyi2i1j1i1i1Riyi0fi1(x)dx （5-140）

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

其中，yifi(zi)，fi为Sigmoid函数，wij为神经元i和神经元j之

间的连接权数。wijwji，Ri对应电路中的电阻，zi为神经元i的接受值，Ii为外部偏置电流输入值，

1i1Rinyi0fi1(x)dx为增益项。

对应的连续Hopfield神经网络状态变化用微分方程表示为

ndziAziwijyjIij1dtyf(z)，i1,2,•••,niii （5-141）

其中，A是与Ri有关的常数，当RiR0时，A1R。

（5-140）和（5-141）有如下关系：

dziEdtyi （5-142）

容易证明，若f为单调增函数，有：

dE0dt，且当且仅当

dzidE0，(i1,2,•••,n)0dt时，dt。所以，连续Hopfield神经网络的状

态总是向着能量E减少的方向运动的，因此网络总能收敛到稳定状态，网络的稳定点同时也是能量E的极小点。

具体地，Hopfield神经网络的计算步骤：

第1步：针对实际的组合优化问题构造能量函数，使得能量函数有好的稳定性；

第2步：由能量函数，根据（5-142）的关系求解出Hopfield神经网络状态变化方程（5-141）；

第3步：用数值方法（如Matlab软件）求解方程（5-141）得到平衡点，得极小值。

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

需要注意的是：

① 能量E的极小点有局部极小点和全局极小点两类，在具体的数值计算过程中，难免会陷入局部极小，所以有吸引子的热点研究。为了避免局部极小，可以采用多种方法的组合，如与遗传算法、模拟退火等方法的结合。

② 无论对离散型还是连续型的Hopfield神经网络，只要权值矩阵是对称阵，网络就是稳定的，但由于Hopfield神经网络神经元的连接权值在整个计算过程中是不变的，所以Hopfield神经网络不具有学习能力。

6. 神经网络算法的应用实例 1）地震级预测

表5.3学习样本集及内符结果

频度 0.270 0.176 0.124 0.074 0.192 0.235 0.212 0.125 0.210 0.074 0.093 0.161 0.136 0.178 0.161 0.143 0.153 B值 0.60 0.66 0.76 0.85 0.63 0.71 0.70 0.74 0.68 0.83 0.57 0.55 0.72 0.75 0.69 0.70 0.43 缺震 蠕变 能量 0.9954 0.8796 0.1093 0.1472 0.9703 0.8205 0.6402 0.2217 0.6857 0.7605 0.3802 0.1798 0.7933 1 0.636 0.9409 0.4263 0.8507 0.8353 0.7605 0.3703 0.8048 0.5440 0.2215 0.8234 0.8212 0.7357 0.3905 0.7037 0.7583 0.3739 0.1798 0.8277 0.8234 0.7453 0.3833 0.7943 0.652 0.9420 0.4265 0.131 0.9106 0.8237 0.5707 0.1721 0.9003 0.8596 0.8526 0.8743 0.7437 0.2861 0.5106 0.9003 0.7236 0.2802 0.3107 0.7843 0.7882 0.5773 0.5586 0.601 0.8093 0.7785 0.5881 0.2942 1 0.4003 0.2320 值 期望输出 3.9 4.8 4.9 4.0 4.1 4.0 4.4 5.0 4.3 4.0 3.9 3.9 4.1 3.9 5.5 4.0 4.1 实际输出 4.0 4.9 4.8 4.3 4.3 4.1 4.7 4.9 4.7 4.3 4.0 4.1 4.0 4.2 5.1 4.4 4.0 震级ΔM 0.1 0.1 -0.1 0.3 0.2 0.1 0.3 -0.1 0.4 0.3 0.1 0.2 -0.1 0.3 -0.4 0.4 -0.1 欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

0.186 0.127 0.231 0.67 0.75 0.69 0.9651 0.8117 0.6396 0.8650 0.7134 0.7383 0.2942 0.5905 1 0.8003 0.5339 0.2178 4.8 3.7 4.0 5.0 4.3 4.1 0.2 0.6 0.1 现选取某地区20组地震数据（每组数据有诸如频度、蠕变、能量、b值、缺震、值等具有代表性的六个指标）作为输入，目的是预测震级，因此选择输入层为6个节点，输出层为1个节点，隐层节点确定为2个。用S函数作为激活函数。建立神经网络模型，对地震样本数据采用BP算法进行学习，以期对地震级进行有效预测，如表5.3所示。

需要注意的是，在隐层结点确定的情况下，由于训练次数过大会使测试误差增大，影响网络的外推能力 。故在训练过程中每经过一定训练次数后，要停止训练并测试其测试误差，当发现测试误差开始上升时，网络便达到最佳训练次数，此时网络便具有最佳的外推能力。

为检验该网络对预报震级的效能如何，能否达到要求的精度还必须进行内符检验。内符情况如表5.3，可以看出我们所构造的用于该地区地震活动预测的神经网络模型基本能识别训练样本，如果取|M|0.5，内符检验正确率为95%。外推能力检验采用交叉法进行，把同样的训练样本分成7，7，6三个子集，每次抽出一个子集不参加训练，用它来测试外推能力，分析结果如表5.4。可以看出最大预测震级与实际震级之差为0.7，如果限定|M|0.5为预报正确，则预报震级的准确率为85%。

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

表5.4 预测效能分析

编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 实际震级 3.9 4.0 4.1 4.3 3.8 4.4 4.0 5.0 3.9 5.1 4.0 3.8 5.5 3.9 3.9 4.6 3.9 4.9 3.9 4.4 检验震级 3.3 4.3 3.6 4.6 4.0 4.1 3.7 4.6 4.6 5.4 3.6 3.6 5.4 4.1 3.5 5.2 4.0 4.8 4.3 4.0 震级差ΔM -0.6 0.3 -0.5 0.3 0.2 0.3 -0.3 -0.4 0.7 0.3 -0.4 -0.2 -0.1 -0.2 -0.4 0.6 0.4 -0.1 0.4 -0.4 2) 基于Hopfield网络的TSP问题求解

TSP（Traveling salesman Problem）问题描述：一个装备保障人员欲到n个营区去补给装备，每两个营区i和j之间的距离为dij，如何选择一条道路使得装备保障人员每个营区走一遍后回到起点且所走路径最短。

如果固定一个营区为起终点，则枚举n个营区需要(n1)!个枚举，若以计算机1秒可以完成24个营区所有路径枚举为单位，

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

则营区数为25时需24秒，营区数为26时需10分，．．．，营区数为３０时需10.8年，营区数为31时需325年，．．．，计算量为o(n!)，TSP问题属于NP,故枚举法解TSP问题是个不好的方法。

下面给出这个问题具体的神经网络求解方法。

用一个nn矩阵表示TSP的解，其第i行表示装备保障人员到达该营区的顺序，第i行由数字0，1组成一个n维向量，其中只能有一个分量为1，1所在的序数表示装备保障人员到达的序数。如向量（00100）表示商人第3个访问该营区。下面的矩阵表示一个五营区TSP问题的一个解。

它是一个置换矩阵，表示商人行走的路线为：31425。

由此构造nn个神经元的神经网络，对应(i,j)位置的神经元，其输出为yij，输入为zij，两个营区x和y的距离为dxy，各营区距离信息通过建立能量函数表达式产生对突触权值的约束。

能量函数为：

nDnABCnnEyxiyxjyxiyziyijndxzyxi(yzi1yzi1)2x1i1ji2i1x1xz2i1j12x1zxi1nnnn2其中，A，B，C，D为惩罚因子，yxi表示城市x的第i个神经元的状态，wxi,yjyxi表示营区x的第i个神经元到营区y的第j个神经元

的连接权。第一项表示仅当所有的营区最多只被访问一次时取得极小值0，第二项表示仅当每次最多只被访问一个营区时取得极小值0，第三项表示当且仅当所有的n个营区一共被访问n次

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

时取得最小值0，第四项表示按照当前的访问路线的安排，所需要走的路径的总长度。

相应的连接矩阵

1yxi0城市x在第i个被访问 城市x不在第i个被访 问

对A，B，C，D四个惩罚因子，通常取较大正数值。

利用Hopfield网络求解TSP问题，可以得到一组接近最优（也包括最优）的解，效果较为满意，表现出引人注目的潜在能力。

5.4.2 遗传算法

1. 遗传算法的简单原理

遗传算法(Genetic Algorithm，GA)是一种基于自然群体遗传演化机制的高度并行、随机、自适应高效探索算法，它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。由于其具有健壮性，特别适合于处理传统搜索算法解决不

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

好的复杂的和非线性问题。

我们先通过一个例子来了解遗传算法的原理： 假定我们要求函数

f(x)x2的极大值，其中x为自然数，

0x31。现在，我们将每一个数看成一个生命体，通过进化，

我们看谁能最后生存下来，谁就是我们所寻找的数。

① 编码

我们将每一个数作为一个生命体，那么必须给其赋予一定的基因，这个过程叫做编码。我们可以把变量x编码成5位长的二进制无符号整数表示形式，比如x13可表示为01101的形式，也就是说，数13的基因为01101。

② 初始群体的生成

由于遗传的需要，我们必须设定一些初始的生物群体，让其作为生物繁殖的第一代，需要说明的是，初始群体的每个个体都是通过随机方法产生的，这样便可以保证生物的多样性和竞争的公平性。

③ 适应度评估检测

生物的进化服从适者生存，优胜劣汰的进化规则，因此，我们必须规定什么样的基因是“优”的，什么样的基因是“劣”的，在这里，我们称为适应度。显然，由于我们要求最大值，因此，能使

f(x)x2的

f(x)x2较大的基因是优的，使f(x)x2较小

f(x)x2定义为适应度函数，

的基因是劣的，因此，我们可以将用来衡量某一生物体的适应程度。

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

④ 选择

接下来，我们便可以进行优胜劣汰的过程，这个过程在遗传算法里叫做选择。注意，选择应该是一个随机的过程，基因差的生物体不一定会被淘汰，只是其被淘汰概率比较大罢了，这与自然界中的规律是相同的。因此，我们可以采取赌论的方式来进行选择。

⑤ 交叉操作

接下来进行交叉繁殖，随机选出两个生物体，让其交换一部分基因，这样便形成了两个新的生物体，为第二代。

⑥ 变异

生物界中不但存在着遗传，同时还存在着变异，在这里我们也引入变异，使生物体的基因中的某一位以一定的概率发生变化，这样引入适当的扰动，能避免局部极值的问题。

以上的算法便是最简单的遗传算法，通过以上步骤不断地进化，生物体的基因便逐渐地趋向最优，最后便能得到我们想要的结果。

2. 基本遗传算法的步骤

从上面的例子中，我们便能得到遗传算法的一般步骤， 第1步： 编码。选择问题的一个编码，给出一个有N个染色体的初始群体pop(1)，t1；

第2步： 对群体pop(t)中的每个染色体popi(t)，计算它的适应函数

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

f(i)fitness(popi(t))；

第3步：若停止规则满足，则算法停止；否则，计算概率

pif(i)f(i)i1N,i1,,N （5-143）

并以概率(5-143)从pop(t)中随机选一些染色体构成一个种群

newpop(t1){popj(t)|j1,,N}；

第4步：通过交叉，交叉概率为Pc，得到有N个染色体的

crosspop(t1)；

第5步：以一个较小的概率pm，使得一个染色体的基因发生变异，形成mutpop(t1);tt1,一个新的群体pop(t)mutpop(t);返回第2步。

种群的选取方式（5.143）称为轮盘赌。在实际应用中，交叉概率Pc一般取为： 0.75～0.95；变异概率pm取为：0.005～0.01。一般流程如图图5.40所示：

图5.40 基本遗传算法的步骤

由此也可以看出，与传统的搜索方法相比，遗传算法是采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。 对搜索空间没有任何特殊要求（如连通性、凸性等），只利用适应性信息，不需要 导数等其它辅助信息，适应范围更广。搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化。

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

3. 遗传算法的基本特点 1）结构特点

遗传算法是以适应值提供的启发式信息进行搜索的，与其他启发式(模拟退火、爬山法、

神经网络等) 方法相比，在结构和工作过程方面的特点见表5.5。

表5.5 遗传算法的结构特点

适应性结构 初始结构 适应值度量 定长字符串组成 的种群 选取随机产生个体 组成种群 规范化的适应值函数 系统状态形式 种群 循环终止条件 设定的可接受水平(代数) 产生结果方法 当前种群中的最好个体 变更结构方式 复制、交叉、变异及其他 控制参数种类 N，G，Pc，Pr，Pm 2）实验性能方面的特点

①高效性：遗传算法具有大范围全局搜索的特点，与问题领域无关，前期工作量比少；

②健壮性：遗传算法的搜索是用种群作为基本单元，采用3个不同作用的基本算子进行搜索的，解的结果随时间增加而趋于稳定，不受初始解的影响，而且不因实例的不同而变；

③通用性和灵活性：遗传算法可用于多种优化搜索问题，解题程序可以通用，针对不同的实例，适当调整算子参数，就可以使算法执行获得最佳的解结果和占用CPU机时的关系。

4.遗传算法的应用

遗传算法主要是用来寻优，它具有很多优点：它能有效地

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

避免局部最优现象，有及其顽强的鲁棒性，并且在寻优过程中，基本不需要任何搜索空间的知识和其他辅助信息等等。

为了理解遗传算法的思想，我们将前面的例子进行完，整个过程如下：

初始群体01101 11000 01000 10011 x的值13 24 8 19 适应度169 576 64 361 选择概率0.14 0.49 0.06 0.31

选择上的计数（来自赌轮）1 2 0 1 交叉处0110|1 1100|0 11|000 10|011 下一代群体01100 11001 11011 10000 x的值12 25 27 16 适应度144 625 729 256

．．． ．．． ．．． ．．． ．．．

下面再看一个基于遗传算法的最短路径求解问题：

最短路径问题可以用图论描述，现求解如图5.41所示的图15点加权有向图从顶点1到顶点15的最短路径。

图5.41 15点加权有向图

用遗传算法求解最短路径需经如下几个步骤： 第1步：染色体编码。

对于给定的图，将图中各顶点按顶点号自然排序，然后按

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

此顺序将每个待选顶点作为染色体的一个基因，当基因值为1时，表示相应的顶点被选入该条路径中，否则反之。此染色体中的基因排列顺序即为各顶点在此通路中出现的先后顺序，染色体的长度应等于该图中顶点的个数。

第2步：计算每个个体适应度。

对具有n个顶点的图，已知各顶点(vi,vj)的边长度d(vi,vj)，把vi1到vin间一条通路长 度定义为适应函数

xmf(i)d(vi1,vin)r1n1，求该优化问题就是要寻找解

，使f(xm)最小。 第3步：选择操作。

选择作为交叉的双亲，是根据前代染色体的适应函数所确

定的，质量好的个体，即从起点到终点路径长度最短的个体被选中的概率最大。

第4步：交叉与变异操作。

将被选中的两个染色体进行交叉操作的过程是先产生一个随机数，确定交叉点位于染色体的第几位基因上，然后在此位置进行部分基因互换。变异操作是将染色体中某位基因逆换，即由1变为0，或反之。变异的意义为在某条路径上去掉或增加某顶点，但这样做的结果不一定能使路径长度减少，也就是说有可能使各代中产生的比较好的方案在遗传过程中丢失，迟缓了获得最优解的速度。

为使算法尽可能快地获得更好的解，改善遗传算法的收敛

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

性，在变异操作时，可增加个体寻优的自学习过程，即在某位基因互换后新算法所产生的染色体的适应函数值，若适应函数值更小，即获得路径更短，则保留；否则保持原来的解不变。若有连续N/3次没有得到更好的解，则该过程结束。其中，N表示从起点到终点的顶点数。

需要注意的是，交叉率不可太小，因为太小会延缓获得最优解的进度；变异率对规模大的优化问题影响较大，取值要小。群体中个体数的选取宜大一些。若太小有可能会得不到最优解。

经使用遗传算法，本例的最短路径解集为： 最短路径等于14。

目前，遗传算法所涉及的主要领域还有自动控制、规划设计、组合优化、图象处理、信号处理等。可见，遗传算法的应用研究已从初期的组合优化求解拓展到了许多更新、更工程化的应用方面，它是现代有关智能计算中的关键技术之一。 5.4.3模拟退火算法

1. 模拟退火算法原理

模拟退火算法主要用于解决组合优化问题，它是模拟物理中金属物质的退火过程而开发的一种优化算法。

根据统计力学的知识，金属物体在加热到一定的温度后，它的所有的分子在状态空间V中自由运动，在温度T，分子停留在

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

状态r满足波兹曼（Boltzmann）概率分布：

式中E(r)为在状态r时的能量，kB0为波兹曼常数。

容易证明：在同一温度，能量越小，概率越大，即分子停留在能量小的状态的可能性要大；当温度温度相当高时，每个状态的概率基本相同，接近1V，其中V为状态空间中状态的个数；温度T很低时，能量越低的状态的概率越高，总能量越小，T0时总能量最小。

对于组合优化问题来说，组合优化问题解空间中的每一点都代表一个具有不同目标函数值的解。所谓优化，就是在解空间中寻找目标函数最小（大）解的过程。若把目标函数看成能量函数，某一控制参数视为温度T，解空间当作状态空间，那么寻找基态的过程也就是求目标函数极小值的优化过程。

故将组合优化问题与金属物体退火类比，有表5.6：

表5.6 组合优化问题与金属物体退火类比

组合优化问题 解空间 最优解 目标函数 金属物体 状态空间 能量最低的状态 能量函数 由以上类比可知，组合优化问题zmin{f(x)|g(x)0，xD}的求解问题类比为退火过程，其中D是有限离散定义域。

2. 简单模拟退火算法的步骤 简单的模拟退火算法为：

x0第1步：任选一个初始解x0；xi：； k0；设定初始温度t0：tmax，终止温度tfinal，概率阈值（也可设置为random(0,1)）。 第2步：若在该温度达到内循环停止条件（是否符合收敛条件），则到第3步；否则，从邻域N(xi)中随机选一xj，计算

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

欧阳体创编 2021.02.03 欧阳美创编 2021.02.03

xj；若fij0，则xi：，否则计算exp(fijtk)，若

exp(fijtk)xj，则xi：；否则重复第2步；

d(tk)；k：k1；第3步：tk1：若满足停止条件（是否小于温度终止阈值tfinal），终止计算；否则，回到第2步。

在该算法中，包含一个内循环和一个外循环。内循环是第2步，它表示在同一温度tk时，在一些状态随机搜索。外循环主

d(tk)；k1和要包括第3步的温度下降变化tk1：迭代步数的变化k：停止条件。该算法的直观理解是：在一个给定的温度，搜索是从一个状态随机地变化到另一个状态，每一个状态到达的次数服从一个概率分布。温度很低时，以概率1停留在最优解。

对于算法中一些参数的处理，常用的方法为：令初始温度t0K（K充分大），其中max{f(j)|jD}min{f(j)|jD}；降

01温方法tk1tk，k0，；每一温度的迭代长度可采用固定的步数，步数的选取与问题大小有关；终止温度tfinal的选取可据经验决定或温度下降一定次数后都没有改善，即认为能量已降到最低，没必要再降温；算法的终止原则可以为零度法：即设定一个充分小的正数，当温度降至以下时，算法停止；或采用循环总数控制法，即设定总的温度下降次数，当温度迭代次数达到该设定值时，停止运算。 fijf(xj)f(xi)在实际应用中，模拟退火算法主要用于解决组合优化问题，典型的例子是用模拟退火算法来解决TSP问题；模拟退火算法也经常用在神经网络中，二者结合使用。

时间：2021.02.03 创作：欧阳体 欧阳体创编 2021.02.03 欧阳美创编 2021.02.03