改进的遗传神经网络优化选址方法

李景文,俞 娜,姜建武+,李 旭

(1.桂林理工大学 广西空间信息与测绘重点实验室，广西 桂林 541006；2.桂林理工大学 测绘地理信息学院，广西 桂林 541006)

0 引 言

选址问题是地理信息资源优化配置的重要研究领域之一[1]，如何有效、科学合理选出最优方案是选址工作的难点问题。近年来，国内研究学者通过采用不同的算法来研究优化选址问题，生力军[2]通过将量子理论融入粒子群算法中，提高了最优选址的寻优能力和效率能力；王志刚等[3]采用人工蜂群算法对配送中心最优化方案进行求解；袁群等[4]将遗传算法、禁忌搜索算法和贪婪算法相结合得到混合遗传算法，通过实验对比分析验证了该混合算法模型的有效性。目前在选址方法中利用遗传算法和神经网络对选址都具有很好的优化效果，但是这些算法存在易于过早局部收敛的缺点[5]，影响了选址的优化精度。因此本文在GA-BP(genetic algorithm and back propagation)算法基础上探索利用模糊C均值聚类算法改进遗传神经网络模型，以达到选址最优化状态。首先通过影响因子权重值确定方法建立选址中心决策矩阵，确定影响因子及其取值范围，利用变异系数法计算得到影响因子的权重，然后通过模糊C均值聚类算法对影响因子的输入数据进行优化定性筛选，然后对符合相应指标的要素进行归一化处理，再利用遗传算法对神经网络算法的权重和阈值进行优化，解决了收敛速度缓慢的问题，为得到优化的选址方案提供了一种方法。

1 GA-BP算法

GA-BP算法是对神经网络的参数进行编码，按照误差平方和最小的原则和“适者生存，优胜劣汰”的进化理论，用优化的参数训练网络[6]。该算法具有较高的预测精度[7]，利用GA来优化BP神经网络初始权重和阈值，提高BP神经网络的收敛速度，减少BP算法陷入局部最优的可能性[8]。GA-BP算法的具体步骤如下：

(1)首先确定神经网络的相应结构；依据该网络结构，确定其阈值、权值并对确定的该阈值权值等待求参数进行编码；

(2)对种群进行初始化处理的同时，对训练的样本进行归一化处理，将处理过后的数据送入神经网络中；

(3)其次利用BP神经网络计算误差，采用该误差做适应度函数，进而得到所有个体的适应度值；

(4)然后通过选择操作、交叉操作和变异操作得到下一代种群；

(5)寻找(3)式得到的适应度值，在满足遗传终止限定条件的情况下寻找得到最佳个体；

(6)对最佳个体进行解码，分别赋值于神经网络的权值和阈值；

(7)最后对BP神经网络进行再次训练，当满足终止条件时，保留其结构并预测输出。

GA遗传算法能够利用其全局最优的特点，帮助BP算法解决局部优化等缺陷，能够将全局最优和局部最优有机结合，互为补偿，达到良好的优化效果，得出了最优的权值和阈值[9]。但该算法存在缺少考虑影响因子权重的问题以及算法在求解时易与过早收敛的缺陷，因此本文在GA-BP算法基础上提出了利用模糊C均值聚类算法改进遗传神经网络模型的优化选址方法。

2 C-GA-BP算法描述

C-GA-BP(fuzzy C-means and genetic algorithm and back propagation)算法是通过影响因子权重值确定，建立了选址中心决策矩阵，确定了影响因子及其取值范围，利用变异系数法得到了影响因子的权重值，并且对输入数据的筛选过滤与归一化处理，限定了输入数据的范围，简化了数据的处理，依据输入数据的范围限定输入数据，提高了输入数据的精度，降低了迭代次数，提高了效率。

2.1 C-GA-BP算法流程

C-GA-BP算法思想是在建立选址中心决策矩阵的基础上确定相应影响因子及其取值范围，利用变异系数法计算求得影响因子的权重值，然后通过模糊C均值聚类分析算法对输入数据进行定性筛选和归一化处理，减少数据量，提高计算速度。具体算法流程如图1所示。

图1 C-GA-BP算法流程

2.2 影响因子权重值确定方法

为了更好分析影响因子对优化选址方法的影响，根据可拓原理，选取影响选址的主要影响因子组成影响因子集合，建立选址中心决策矩阵，然后利用变异系数法对这些影响因子进行分析，确定影响因子权重值

(1)

(2)

式(1)中，R0表示同意方案的决策矩阵，Q0表示满意方案，xi表示选址方案中的决策影响因子，xoj表示决策矩阵的影响因子xi的取值区间。式(2)中，Rj表示待选方案的决策矩阵，Qj表示第j个候选方案，xji为第j个候选方案对应于影响因子xi的量值。

通过上述选址中心决策矩阵的建立和对影响因子的分析，再利用变异系数法来计算求得各个影响因子的权重。具体操作步骤如下：

(1)计算第i项的影响因子的均方差

(3)

(4)

(2)计算求得第i项影响因子的变异系数

(5)

(3)通过变异系数来计算得到第i项影响因子的权重

(6)

则各因子的权重为

通过计算影响因子权重值，克服主观人为决策因素和客观地理因素的对选址方案的影响，可以更加精确得到最理想的选址方案。

2.3 C-GA-BP计算过程

(1)首先确定选址方案，利用影响因子权重值确定方法建立选址中心决策矩阵，确定影响选址的因子及其相应的取值范围，然后利用变异系数法求得出各个影响因子之间的权重值，根据权重对输入数据进行归一化处理，归一化处理公式如下

(7)

式中：xmax为该指标样本数据中的最大值，xmin为该指标样本数据中的最小值，x为该样本指标数据，x*为归一化处理后的数值，μ为影响因子的权重值。

(2)依据选址对象确定模糊C均值聚类模型，分类数c，加权参数z和初始隶属度矩阵U。

(3)根据模糊C均值模型，目标化下式目标函数

(8)

式中：dik表示为各个对象到聚类中心的距离值，m表示对象维度，U表示聚类矩阵，其距离计算公式如下

(9)

根据数值解的集合，计算每个解与最优解之间的相应距离，并将距离值最高的k个值用作下一步的输入值[10]。距离值计算公式如下

(10)

式中：Ri表示每个解i与最优解之间的距离值，Xij是每个值之间i的各个因子取值，XIL为合格值。

(4)初始化目标的聚类矩U

(11)

(5)计算求得目标对象的聚类中心V,集群中心采用下式可获得

(12)

其中，n表示未分类对象个数，uik表示第k个元素在第i类的相关隶属度，z表示加权参数。

(7)随机产生初始权重种群p，种群中的每一条染色体由权重向量和阈值向量所组成，表示为W=(w1i,w2i,…,wui,b1i,b2i,…,bvi), 其中 (i=1，2，…，N, 其中N为种群大小),u为神经网络结构中权重总数，v为神经网络中隐含层和输出层总阈值。

3 仿真实验及结果

3.1 实验分析

为了验证本文提出的C-GA-BP算法在优化选址方面的有效性，选取黑龙江省物流公司的选址需求进行仿真实验。拟在该省22个市辖区中，建设3个物流公司以满足各个市辖区对物流的需求。物流公司的建设既要满足建设成本最低，也要满足实际的物流需求。市辖区坐标以及市辖区所对应的物流需求量见表1。表中i表示市辖区，(x,y)表示市辖区坐标；wi为需求量。

表1 物流公司建设需求点坐标及需求量

通过实地考察和建设物流公司的经验与调研情况，归纳得到几个建设物流公司的影响因子：建设成本、交通要素、员工成本、周边环境、客户和商家的分布以及配送距离7个影响因子。表2为通过变异系数法得到的影响因子权重表。

表2 影响因子权重

该选址方案所选用的实验平台为MATLAB R2016a，在进一步验证该方法的可行性过程中，由上述表2可知，建设成本影响因子所占的权重最大，故据物流公司建设需求点坐标及其需求量，分别采用BP算法模型、GA-BP算法模型、C-GA-BP算法模型对选址的建设成本进行优化计算，在迭代次数均为80次的情况下，3种算法模型的建设费用分别如图2所示。

图2 寻优曲线对比

通过图2对比可知，在迭代次数相同的情况下，C-GA-BP 算法模型的训练得到的建设成本费用明显低于BP神经网络和GA-BP算法，因此可得出C-GA-BP算法在训练建设成本方面的确有优化能力。

在精度优化方面，利用GA-BP和C-GA-BP算法模型对精度进行训练，来验证C-GA-BP算该实验方法的精确度。将初始个体数和迭代次数的取值都以选取3个物流公司为主，通过对模型的训练，算法和参数的调整，同时与GA-BP算法的收敛曲线进行比较，验证C-GA-BP算法的收敛性。两种模型分别训练100次，分别选出其中目标进化函数收敛效果最好的结果图进行比较。其中GA-BP算法模型的收敛图如图3所示，C-GA-BP算法模型的收敛图如图4 所示。

图3 GA-BP训练

图4 C-GA-BP训练

通过对比，GA-BP算法模型训练精度与C-GA-BP算法模型训练精度相比较，在收敛速度方面具有明显的差距。两者相同的训练次数相同的情况下，C-GA-BP算法模型的精度达到了5.224×10-9，而GA-BP算法模型的精度为2.3026×10-8，C-GA-BP算法模型的精度明显高于GA-BP算法模型的精度，大大提高了收敛速度，由此可见，C-GA-BP 算法的确对于在选址方面具有明显的优化效果，并且具有一定的优越性。

3.2 与部分文献比较

为了进一步验证该算法的精准优化效果，选用AFSA算法[5]、BFO-AFSA算法[5]、ICS算法[11]、GA-BP算法各个算法比较结果见表3。

表3 算法比较结果

对上述表中算法参数设置均相同的情况下，迭代次数均为50次时，所有算法平均适应度与迭代次数之间的关系及运行结果如图5所示。

图5 算法运行结果对比

通过结合上述所有实验图表与参考文献中算法的运行结果对比数据，可以看出C-GA-BP算法不仅在迭代次数相同的情况下，平均适应度值最优，收敛速度快，而且在选址方面的确具有训练精度高和优化选址的优点，结合图2中C-GA-BP算法在建设成本方面优化得到的结果，通过实验得出了图6为C-GA-BP选址优化方案。

图6 C-GA-BP优化选址方案

4 结束语

本文提出的C-GA-BP算法优化选址方法，通过影响因子权重值确定方法，建立了选址中心决策矩阵，确定了影响因子及其取值范围，利用变异系数法得到了影响因子的权重值，并且对输入数据的筛选过滤与归一化处理，更好得到最优化的选址方案。该优化方法经过实验验证可得，在提高训练精度的同时降低了建设所耗成本,从而得到建设成本最低的选址方案，解决了GA-BP算法模型运行数据量大、收敛速度缓慢、过早收敛和易陷入局部最优解[12]的双重问题，为建设选址提供了新的方法。