利用蚁群算法优化前向神经网络

工神经网络(ANN)是大脑及其活动的一个理论化的数学模型,由大量的处理单元(神经元)互连而成的,是神经元联结形式的数学抽象,是一个大规模的非线性自适应模型。人工神经网络具有高速的运算能力,很强的自学习能力、自适应能力和非线性映射能力以及良好的容错性,因而它在模式识别、图像处理、信号及信息处理、系统优化和智能控制等许多领域得到了广泛的应用。

  人工神经网络的学习算法可以分为:局部搜索算法,包括误差反传(BP)算法、牛顿法和共轭梯度法等;线性化算法;随机优化算法,包括遗传算法(GA)、演化算法(EA)、模拟退火算法(SA)等。

  蚁群算法是一种基于模拟蚂蚁群行为的随机搜索优化算法。虽然单个蚂蚁的能力非常有限,但多个蚂蚁构成的群体具有找到蚁穴与食物之间最短路径的能力,这种能力是靠其在所经过的路径上留下的一种挥发性分泌物(pheromone)来实现的。蚂蚁个体间通过这种信息的交流寻求通向食物的最短路径。已有相关计算实例表明该算法具有良好的收敛速度,且在得到的最优解更接近理论的最优解。

  本文尝试将蚁群算法引入到前向神经网络的优化训练中来,建立了基于该算法的前向神经网络训练模型,编制了基于C++语言的优化计算程序,并针对多个实例与多个算法进行了比较分析。

  前向神经网络模型

  前向人工神经网络具有数层相连的处理单元,连接可从一层中的每个神经元到下一层的所有神经元,且网络中不存在反馈环,是常用的一种人工神经网络模型。在本文中只考虑三层前向网络,且输出层为线性层,隐层神经元的非线性作用函数(激活函数)为双曲线正切函数:

  其中输入层神经元把输入网络的数据不做任何处理直接作为该神经元的输出。设输入层神经元的输出为(x1,x2,Λ,xn),隐层神经元的输入为(s1,s2,Λ,sh),隐层神经元的输出为(z1,z2,Λ,zh),输出层神经元的输出为(y1,y2,Λ,ym),则网络的输入-输出为:

  其中{wij}为输入层-隐层的连接权值,{wi0}隐层神经元的阈值,{vki}为隐层-输出层的连接权值,{vk0}为输出层神经元的阈值。网络的输入-输出映射也可简写为:

  1≤k≤m (5)

  前向神经网络的训练样本集为

  A={Xi,Tii=1,2,A,n)}

  (其中Xi∈Rn,为第i组训练数据的输入,Ti∈Rm为与第i组训练数据的输入对应的期望输出,Tki为输出层第k个神经元的期望输出),设第i组训练数据的输入的实际输出为Yi∈Rm,Yki为输出层第k个神经元的实际输出,则基于该训练样本集的误差函数为

  该函数是一个具有多个极小点的非线性函数,则对该前向神经网络的训练过程为调整各个神经元之间的连接权值和阀值{wij},{wi0},{vki},{vk0},直至误差函数E达到最小。

  误差反向传播算法(BP算法)是一种梯度下降算法,具有概念清楚、计算简单的特点,但是它收敛缓慢,且极易陷入局部极小,且对于较大的搜索空间,多峰值和不可微函数也不能搜索到全局极小。为此人们提出了很多改进的学习算法,其中最简单且容易实现的是加入动量项的变学习率BP算法,这种算法一般都比较有效,但是收敛速度还是比较慢,仍是局部搜索算法,从本质上仍然摆脱不了陷入局部极小的可能。为了摆脱局部极小,人们已经尝试将可用于非线性优化的遗传算法、演化算法以及模拟退火算法等进行前向人工神经网络的训练。

  蚁群算法

  蚁群算法简介

  蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。因此,由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象:某一条路径走过的蚂蚁越多,后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。蚁群算法就是根据这一特点,通过模仿蚂蚁的行为,从而实现寻优。这种优化过程的本质在于:

  选择机制:分泌物越多的路径,被选择的概率越大。

  更新机制:路径上面的分泌物会随蚂蚁的经过而增长,而且同时也随时间的推移逐渐挥发消失。

  协调机制:蚂蚁间实际上是通过分泌物来互相通信、协同工作的。

  蚁群算法正是充分利用了选择、更新和协调的优化机制,即通过个体之间的信息交流与相互协作最终找到最优解,使它具有很强的发现较优解的能力。

  蚁群算法具体实现

  蚁群算法求解连续空间上的优化问题 以求解非线形规划问题为例。考虑如下的非线性规划问题:minF(x1,x2,Λ,xn),使得,ai1x1+ai2x2+Λ+ainxn≥bi,i=1,2,Λ,r。这里F为任一非线形函数,约束条件构成Rn上的一个凸包。可以使用不等式变换的方法求得包含这个凸包的最小的n维立方体。设该立方体为

  设系统中有m只蚂蚁,我们将解的n个分量看成n个顶点,第i个顶点代表第i个分量,在第i个顶点到第i+1个顶点之间有ki条连线,代表第i个分量的取值可能在ki个不同的子区间。我们记其中第j条连线上在t时刻的信息量为τij(t)。每只蚂蚁要从第1个顶点出发,按照一定的策略选择某一条连线到达第2个顶点,再从第2个顶点出发,…,在到达第n个顶点后,在kn条连线中选取某一条连线到达终点。每个蚂蚁所走过的路径代表一个解的初始方案,它指出解的每一个分量所在的子区间。用pijk(t)表示在t时刻蚂蚁k由城市i转移到城市j的概率,则(式(7))

  为了确定解的具体值,可在各个子区间已有的取值中保存若干个适应度较好的解的相应分量作为候选组,为了加快收敛速度,参考具有变异特征的蚁群算法提出的具有变异特征的蚁群算法,使用遗传操作在候选组中确定新解的相应分量的值。首先可随机在候选组中选择两个值,然后对他们实行交叉变换、变异变换,以得到新值作为解的相应分量。该候选组中的值在动态的更新,一旦有一个更好的解的分量在该子区间中,就用这个值替换其中的较差者。

  在m只蚂蚁得到m个解后,要对它们进行评估,本人使用Lagrange函数作为评估解的优劣的适应度函数,否则要对每个解进行合法性检查并去除其中的不合法解。然后要根据适应度函数值更新各条边上的信息量。要根据下式对各路径上的信息量作更新:

  Δτijk表示蚂蚁k在本次循环中在城市i和j之间留下的信息量。

  重复这样的迭代过程,直至满足停止条件。

  候选组里的遗传操作 若候选组里的候选值的个数gi=0,即候选组里没有候选值,此时则产生一个[li+(j-1)×length,min(ui,li+j×length]间的随即数作为解分量的值wij,vij,跳过选择、交叉、变异等遗传操作。

  若gi=1,即候选组里只有一个候选值wik,vik,则跳过交叉、选择等操作,直接对这个候选值wik,vik进行变异操作。

  若gi=2,即候选组里有两个候选值,则跳过选择操作,直接对这两个候选值进行交叉、变异等操作。

  否则,选择两个分量后进行交叉、变异操作。

  在选择操作中,根据候选组里各候选值的适应度的大小,用“赌轮”的方法选取两个值。设第j个值所在解的适应度为fj,则它被选中的概率为

  在交叉操作中,设所选择的两个值为wij(1),vij(1)和wij(2),vij(2),其适应度分别为f1,f2,且f1>f2,我们以概率Pcross进行交叉操作。随机产生p∈[0,1],若p>Pcross,则进行交叉操作。取随机数r∈[0,1],交叉结果值

  在所有蚂蚁都得到解以后,修改边条上的信息量按式(8)和式(9)相应地更新各子区间上的信息量。但对Δτijk的更新应按下式进行:

  其中W为一个常数,fk为蚂蚁k的解的适应度。

  前向神经网络的训练过程

  基于上述的定义,用蚁群算法训练具有三层前向神经网络,可按以下步骤进行:

  输入相关参数:输入最大迭代次数number,每次迭代选取的适应度最好的解的个数num,每个分量的ki个子区间中信息量最大的子区间被选种的概率q0(其余子区间被选中概率为(1-q0))。

  初始化:通过神经网络在控制变量可行域内随机产成m只蚂蚁,即产生m组{wij},{wi0},{vki},{vk0},且各个分量均为[-1,1]区间内的随机数。

  迭代过程:对于n个分量,分别对m个蚂蚁进行循环更新相应的信息量τij(t),对候选组中的分量进行遗传操作,计算新解的适应度,对各边的信息量进行修改,根据适应度的优劣增删候选组中的值。判断是否满足结束条件,若不满足则继续迭代。

  第(3)步的具体算法如下:

  while not结束条件(如最大迭代次数) do

  {for i=1 to n do (对n个分量循环)

  {for k=1 to m do (对m个蚂蚁循环)

  {根据q0和概率pijk(t)确定第i个分量的值在第j个子区间;

  局部更新第j个子区间的信息量τij(t);

  在第j个子区间候选组里通过遗传操作生成第i个分量值;}

  计算新解的适应度函数值;}

  修改个条边上的信息量;

  取适应度最好的num个解将其各分量直接插入相应的子区间的候选组中,并淘汰候选组中的较差者。}

  上述过程中根据下列公式选取第i个分量的值所在的子区间号j:

  由于算法中以q0的概率选择ki个子区间中信息量最大的子区间,因此信息量最大的那个子区间常常被选中,这就使得新一代解的该分量值集中在这个子区间,容易发生停滞现象。为了避免这种现象,在上述过程中对所选的子区间的信息量进行局部更新,对被选中的子区间立即适当地减少其信息量,使其他蚂蚁选中该子区间的概率降低。设第k个个体的第i个分量选中第j个子区间,则按下式局部更新子区间j的信息量:

  这样,更新后的信息量是原来的信息量和有关第i个分量各子区间的最小信息量的凸组合。当信息量最大的子区间被多次选中之后,信息量减少到ki个子区间的信息量的平均水平,从而蚂蚁选择其他子区间的概率增加,增加了所建立解的多样性,同时也有效减少了停滞现象的发生。

  实验结果

  为了评价蚁群算法的性能,笔者做了大量的计算机模拟试验,在此给出了两个函数COS(X)和SIN(X)函数的实验结果,选择蚂蚁群规模m=20;每次迭代选取的适应度最好的解的个数num=10;每个分量的ki个子区间中信