求解选址问题遗传算法的适应度函数选择

孙 涛

(1.中国石油大学胜利学院基础科学学院，山东 东营 257000;2.中国石油大学储运与建筑工程学院，山东 青岛 266580)

配送中心选址问题是指在一个固定连续区域内分布着一些需求点，要求在此区域建立配送中心，在满足一定约束的前提下，确定配送中心的位置和需求点的分配方案，使得配送距离最短或配送费用最低。由于问题的复杂性，传统优化方法很难取得好的效果，而以遗传算法为代表的智能算法能够更加有效地求解此类问题。遗传算法是一种高效的全局优化技术，在优化运算、机器学习、智能控制等许多领域都得到了成功的运用［1-3］，目前已有众多研究将遗传算法应用于配送中心选址问题［4-6］上，本文在使用遗传算法时，将配送中心的位置坐标进行编码，使用贪心算法给出近似最优分配方案并计算适应度函数，通过遗传进化，得出最终的配送中心位置坐标与需求点的分配方案，并通过实例将算法与使用分枝定界法进行比较。

1 配送中心选址问题的数学模型

假设在一连续的平面区域D内分布着n个需求点，需求点的位置坐标(aj，bj)，j=1，2，…，n，要求在区域D内建立p个配送中心，给出配送距离最短或配送费用最低的配送中心位置及需求点的分配方案，其优化问题的数学模型

其中，cij为连接的权重，(xi，yi)为配送中心的位置坐标，i=1，2，…，p，j=1，2，…，n。约束(1)表明一个需求点只能连接到一个配送中心;约束(2)为配送中心连接需求点不能超过k;约束(3)为配送中心位置坐标的几何约束。

2 遗传算法的实现

2.1 编码方案

遗传算法的编码是对问题的可行解进行某种编码，将问题的解空间转化为编码空间，每一个可行解对应一个编码，称为个体或染色体，常用的编码有二进制编码、实数编码等。由于模型中既含有连续变量，又含有离散变量，为简化运算，本文采用实数编码，将p个配送中心的位置坐标按顺序写成一个2p维的实数向量，每个实数向量即为一个个体。

2.2 确定适应度函数

适应度是衡量个体优劣的指标，它直接决定每个个体的存活概率，而适应度函数的构造一般是对目标函数值进行改造，这时需要计算每个个体对应的目标函数值，对于每个个体，由于配送中心位置坐标已经确定，模型就简化成了一个0－1规划模型，通过求解这一简化模型可得到每个个体对应的分配方案和目标函数值，从而得到每个个体对应的可行解与适应度函数。

在此并不求解最优的分配方案，而是选用贪心算法给出一个近似最优分配方案，具体做法如下:

(1)按需求点到配送中心的距离由小到大排列;

(2)将距离最小的需求点与配送中心选出，将此需求点归入这一配送中心;

(3)删除这一需求点对应的所有距离值;

(4)检验配送中心是否已达到最大连接数，如果已达最大连接数，则删除配送中心对应的所有距离值。

(5)返回步骤(1)，直到所有需求点分配完成。

2.3 遗传算子的确定

(1)选择算子模拟的是“物竞天择，适者生存”的自然进化原理，是从当前种群中以一定概率选取个体用作父本去繁殖后代，个体被选中的概率与适应度值有关。常用的选择方法有比例选择、排序选择等，本文使用的是比例选择。

(2)交叉算子模拟生物进化中的有性繁殖，是从种群中选择两个父本个体，通过两交换组合产生两个新个体。常用的交叉方案有单点交叉、双点交叉、均匀交叉等，本文采用单点交叉。

(3)变异算子选择。对交叉后的染色体进行变异是为了防止算法陷入局部搜索，提高算法达到全局最优解的机会，变异操作采用均匀变异，即随机选取父染色体的一个基因，然后用在可行域内区间中均匀分布的一个随机数代替［2］。

2.4 保优与终止进化准则

在算法中，记录每次迭代的最优染色体，每次迭代都将记录的上一代的最优染色体取代新种群中适应度最差的染色体，以保证优良基因的延续。遗传算法的终止准则常常是根据计算代价与计算结果的权衡，本文采用预先设定进行时限的终止准则。

3 算例分析

在一矩形区域，随机分布44个需求点，其坐标见表1，现要求在上述区域设置6个地址建立配送中心，使得需求度到配送中心的总路程最短，其中每个需求点只能连接到一个配送中心，而每个配送中心的最大连接数为8。使用遗传算法运算，种群规模为40，进化600代。分别使用贪心算法和分枝定界法计算适应度，其中分枝定界法求解使用MATLAB函数bintprog实现。

表1 区域站点原始数据

遗传算法的迭代过程比较见图1，从图1中可知虽然贪心算法只给出了近似最优的分配方案，但经过遗传算法的进化，算法仍然能够收敛到全局最优解。

图1 算法优化过程图

两种算法的主要优化结果见表2，虽然所得到的中心位置各异，但最终的目标函数值相差不大，在计算时间上，由于使用贪心算法在每次迭代中不用求解最优，与使用分枝定界法相比，计算效率高出两个数量级。

表2 主要优化结果对比

4 结束语

使用遗传算法求解配送中心选址问题，将配送中心的位置坐标和需求点的分配方案分开，将位置坐标进行实数编码，在计算适应度函数时，采用贪心算法给出分配方案，从而得到适应度函数。与使用分枝定界法比较，虽然贪心算法只给出了近似最优的分配方案，但由于遗传算法的全局寻优能力，算法仍然能够收敛到全局最优解，而且由于贪心算法方法简单、计算量小，在计算时间上，较使用分枝定界法有明显的优势，实际的算例也验证了算法的收敛性和有效性。

［1］阮晓青，周义仓.数学建模引论［M］.北京:高等教育出版社，2006:116-188.

［2］史峰，王辉，郁磊，等.MATLAB智能算法30个案例分析［M］.北京:北京航空航天大学出版社，2011:17-26.

［3］王小平，曹立明.遗传算法——理论、应用与软件实现［M］.西安:西安交通大学出版社，2002:1-50.

［4］吴坚，史忠科.基于遗传算法的配送中心选址问题［J］.华南理工大学学报:自然科学版，2004.6，32(6):71-74.

［5］刘扬，鞠志忠，鲍云波.一类多级星式网络的拓扑优化设计方法［J］.大庆石油学院学报，2009，33(2):68-73.

［6］姜大立，杨西龙.易腐物品配送中心连续选址模型及其遗传算法［J］.系统工程理论与实践，2003(2):62-67.