控制网

    梁佳成 （1978-）

    男，辽宁工业大学研究生，研究方向为智能控制。
 
    摘要：介绍了采用自适应遗传算法和改进BP 算法相结合的混合算法来训练BP网络的方法，即先用自适应遗传算法进行全局训练，再用改进BP 算法进行精确训练，以达到加快网络收敛速度和避免陷入局部极小值的目的。结果表明该算法收敛速度快、分类精度较高。

    关键词：改进BP 算法；自适应遗传算法；混合算法；VRP

    Abstract: In this paper, we introduce a method to train BP network by combing adaptive GA and improved BP algorithm. In order to speed up convergence of BP network and avoid trapping into local minimum, a global training is first done by the use of  adaptiveGA and then a refine training using improved BP algorithm to improve the solution . The result shows t hat this method issuperior to improved BP algorithm in the convergence speed and classification accuracy.

    Key words: improved BP algorithm; adaptive GA; hybrid algorithm; VRP

    1 引言

    全球经济的一体化使物流配送在供应链中的作用显得尤为重要。在物流配送系统中，配送车辆优化调度是关键的一环，也是节省运输费用和提高经济效益的重要手段。其中，车辆路径安排问题(VRP)又成为车辆优化调度的核心问题，由于其应用的广泛性和在经济上的重大价值，使得针对路径优化问题构造性能优良的启发式算法，成为了一个值得深入研究的课题。同时，遗传算法(GA)的出现为求解这一类问题提供了新的工具，Berthold、Malmborg等人都曾利用GA 进行过研究，并取得了一些成果，但总体上他们所得出解的质量都不高，这是由GA 本身局部搜索能力不强所致。针对GA 这一缺陷，本文在标准遗传算法基础上，将并行进化思想与阶段性进化思想相结合，设计了求解VRP 模型的混合遗传算法，并通过实验计算证明了该算法具有良好的寻优性能。
 
    2 VRP问题的数学描述

    车辆路径问题可以表述为：有一个总仓库(1, 2,...,n)和n个分仓库第k个仓库需运输的货物量为gk(k=1, 2,...,n)，总仓库派出多辆货车，将n个分仓库的所有货物运往总仓库，求满足货运需求的最低成本车辆运输行程路线。

    设总仓库派出m辆货车，每辆货车的载重量为q，且q>gi，Cij表示点i到点j的运输成本，总仓库的编号为0，各分仓库的编号为i(i=1,2,...,k)，另外还有几个变量定义如下：

    货车s由i驶向j；点i的货运任务由s货车完成

    由这些参数和变量可以求出VRP问题的数学模型表示为：

   （1） 
                       
    另外，还有几个约束条件如下：

    （1）货车的容量约束为 

    （2）

    （2）保证每个份仓库的运输任务仅由1辆货车来完成，所有的运输任务则由m辆货车协同完成。

    （3）

    （3）到达某一仓库的货车有且仅有一辆

    （4）

    （4）离开某一份仓库的货车有且仅有一辆

     （5）

    3 BP算法的改进

    BP算法是目前应用最为普遍的一种神经网络训练方法。标准BP 算法是一种简单的快速下降静态寻优算法。在修正权值时，如果只按照k时刻的负梯度方式进行，而没有考虑到以前积累的经验，常常会使学习过程发生振荡，收敛缓慢。本研究提出了动量法和各层变尺度学习步长相结合的策略，以提高网络的收敛速度并增强算法的可靠性。该改进算法分以下两种情况讨论权向量的修正。

    1) 若权向量为输出层的权向量，其调整公式为：

 （6）

    2) 若权向量为隐含层的权向量，其调整公式为：

 （7）

    = 6     （8）

    式中，w(k)和w (k+1) 分别为k及k+1时刻的权向量；是学习步长；D(k) 是k时刻的负梯度；mc是动量因子，由于各层权值的调整都与激励函数的函数的导数有关，且输出层权值正比于，隐含层的权值正比于。

    可见，多层权值的修正速率是不同的，离输出层越远的权值越难以修正，这是导致BP 网络训练速度缓慢的重要原因。因此,增大隐含层的学习步长能有效地提高网络的训练速度。同时引入动量因子mc，用来传递最后一次权值变化的影响，有助于使网络从误差曲面的局部极小值中跳出。

    4 自适应遗传算法的应用

    4.1 编码设计

    本文采用实数编码方案，码串由BP网络的学习参数(包括学习步长和动量因子)、各隐含层的节点数和各层的权值三部分组成。对于三层结构的BP 网络，其输入层和输出层的节点个数 m和n由实际问题决定。设其隐含层的节点个数为h，学习步长和动量因子分别为和mc，隐含层和输出层的权向量分别为w1和w2，那么个体编码为本实验采用双精度数组来表示个体。

    4.2 适应度函数设计

    以训练集样本对为网络的输入和期望输出，根据激励函数  ，即型函数的对数式计算网络输出，运行后计算网络输出和期望输出的误差，取其均方误差作为目标函数：

  （9）    
                   
    式中,x为种群中的个体；N为网络输入样本个数；M为输出层节点个数；、分别为第k个样本输入时，第j个输出节点的期望输出与实际输出。因目标函数为极小值问题，故将极小值问题转化为极大值问题,其适应度函数为：
         （10）      
                                     
    4.3 遗传算子设计

    (1) 选择。采用最优个体保存法和轮盘赌法相结合的策略。先保留父代个体中适应度最大的个体，直接进入下一代，再利用轮盘赌法对其他个体进行选择。这样可以使最优个体不丢失，适应度低的个体也有被选中的可能，保证了个体的多样性。

    (2) 交叉。具体做法是先使用选择算子在群体中选择两个父体和，根据父体的适应度确定交叉概率。交叉概率的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性。越大，新个体产生的速度越快，但过大时遗传模式被破坏的可能性也越大。交叉概率的计算公式如下：

       （11）                 
         （12） 
                                    
    式中，为交叉前父代双亲中适应度大者；和分别为群体最大适应度及平均适应度；=0.9；= 0.3。实验过程中可根据具体情况调节参数的值。对于两个父体，采用算术交叉，即

              （13）  
                                     
                （14）
                                   
    式中，和为子代个体；和为父代个体； 为(0,1)之间的实数。

    (3) 变异。变异算子首先用选择算子选出父个体，根据父个体的适应度确定变异概率：

               （15）

        （16）
                               
    式中,为需变异的个体的适应度；和分别为群体最大适应度及平均适应度；= 0.1，= 0.009，实验过程中根据具体情况调节这两个参数的值。对于选定的个体，采用均匀变异的方式进行变异，即在个体中随机地选择一个分量用来代替，其后代为，其中， 为(0 ,1)之间的一个随机数。

    5 混合算法

    在对改进BP算法和自适应遗传算法分析的基础上，提出先利用自适应遗传算法来全局训练神经元网络，再用改进BP算法来进行精确求解的混合算法，其算法流程如图1 所示。其中数据预处理是指把数据规格化在[0. 1 ,0.9]之间，这在一定程度上可以降低求解难度，加快BP 神经网络的收敛速度。

 图1   混合算法流程图

    使用均方误差函数作为判断网络是否达到预定精度的标准。

    6 算法仿真研究

    由于MATLAB 语言的基本数据单元是一个维数不加限制的矩阵，并且系统提供了大量处理矩阵的函数！因此，应用MATLAB语言编制遗传算法程序用于求解VRP问题时，可以将种群看作一个矩阵来处理，这有助于整体性地考虑和描述计算问题。为研究算法的有效性，安排了如下试验：

    随机产生一个总仓库（代号为0）和24个分仓库（代号为1-23的位置坐标和各仓库中需运输的货物量如表1 所示，试求运输车辆的载重量为q=10t时合理的需用车辆台数和车辆运输路径安排。

表1   仓库位置坐标和货运量/t

    这里选择文献[4]中提出的公式来确定需要参与运输的车辆台数。
      
    实验中遗传算法参数popsize=50,gen=50 随机运行标准遗传算法和带改进BP-自适应遗传算子的改进遗传算法各14次，计算的总运输距离结果如表2所示。

                                        表2   计算的总运输距离结果/km
      
    由表2可看到改进算法得到3次最优结果972.47km,(0610182122230122080216119501971003 1341714150)，而标准遗传算法得到最优运输距离(路径)最短为988.96，而且14次运算得到的平均运输距离和标准差均比改进算法的结果差，由此可知改进后的算法在求解VRP，问题时收敛性好于标准算法。

    7 结论

    从试验的结果可以看出，基于改进BP-自适应遗传算法求解VRP问题时，标准遗传算法不易收敛，得到的解与最优解相比，有比较大的差距，这说明选择，交叉，变异算子在求解VRP问题时搜索能力较差，将进化算子引入改进标准遗传算法后，算法的搜寻能力得到了加强，敛性明显提高，仿真试验结果表明了改进后算法的可行性和有效性。

    其他作者：王艳秋（1955-），女，教授，博士，硕士研究生导师，研究方向为近代交流调速系统，智能控制；杨克俭（1980- ），男，辽宁工业大学研究生，研究方向为智能控制。
 
    参考文献

    [1]M ilosavljevic N Teodorovic D. A fuzzy approach to the vehicle assignment problem[J]. Transprotation Planning and Technology ,1997.20(1):33-47.

    [2]Teodorovic D,Pavkovic G.A simulated annealing technique approach to vehicle routing problem in the case of stochastic demand [J].Transportation Planning and Technology, 1995,19(1):19-29.

    [3]袁健,刘晋.随机需求情况VRP的Hopfield神经网络界解法[J].南京航空航天大学学报，2000．32（5）：579-584．

    [4]李军、谢秉磊、郭耀煌.非满载车辆调度问题的遗传算法[J].系统工程理论与实践，2000.20（3）：235-239．
 
    [5]金丕彦,芮勇. BP 算法各种改进算法的研究及应用[J].南京航空航天大学学报, 1994 (26) :201-205.

    [6]王小平,曹立明. 遗传算法--理论、应用与软件实现[M].西安:西安交通大学出版社,2002.

    [7]熊忠阳,刘道群,张玉芳. 用改进的遗传算法训练神经网络构造分类器[J]. 计算机应用,2005,25(1):31-34.

    [8]李仪,陈云浩,李京.基于微种群遗传算法和自适应BP算法的遥感遥感影像分类[J].光学技术,2005 ,31(1):17-20.

    [9]韩敏,程磊,邢军.基于神经网络的扎龙湿地覆盖分类研究[J].大连理工大学学报,2004,44(4):582-588.