MATLAB遗传算法求解带容量约束的物流配送选址问题实例
作者：麦哥爱西芹

遗传算法编程问题实例：
在经度范围为(116, 118)，纬度范围为(38, 40)的矩形区域内，散布着37个需求点，各个需求点的坐标及需求量见表1。要求在该矩形区域内确定N个位置建立配送中心。已知各配送中心容量不得超过容量上限M，每个超市只由一个配送中心负责配送，使得N个配送中心到所有超市的总配送成本（配送单位距离单位需求量的所需成本×距离×需求量）最小，其中配送中心到超市的距离为直线距离。请建立该问题的模型，利用遗传算法编程求解上述问题。
N可以取2，3，4，5，6，…等, M为一给定常数值。

UP点评，问题特点：
1.物流配送中心从所有需求点中选取；
2.每个配送中心总容量不得超过M；
3.要建立的配送中心数量N是预先设定的，M和N的取值要自行搭配好才能取得理想的效果。
4.所需数据格式如下表所示，一共分为四列。每一行代表某一个需求点的信息，数据和行数可以自行修改、增加或删减。

表1 各需求点坐标及需求量
需求点编号 经度 纬度 需求量
1 117.7720592 39.08821561 5218.094945
2 116.9989782 39.6397973 4521.733721
3 117.8264179 38.07323562 4778.649348
4 116.6061083 38.87106277 2759.595145
5 116.862585 39.95203733 4515.60023
6 117.4665673 39.89143264 5693.063149
7 116.5973 39.30830377 3312.346684
8 116.821379 38.66138895 2610.725152
9 116.9166144 39.96411058 2457.623938
10 117.5378874 38.80649106 5285.531204
11 117.2728554 38.69527045 5922.943294
12 116.8805004 39.4104718 2907.942467
13 116.5708162 39.79950304 5789.040526
14 117.7081947 38.24760011 4404.125137
15 117.6288227 39.41511748 4131.169348
16 117.622711 39.8795264 4563.233263
17 116.9046042 39.20021963 2261.453284
18 117.6826602 38.09136654 4245.345405
19 116.4700835 39.59746491 3520.228847
20 116.6929386 38.59281374 4486.226597
21 116.2189886 39.4204627 4010.417392
22 116.5408416 39.71655645 3085.099796
23 117.9240698 38.16432146 3272.277061
24 117.841495 39.75077665 5160.572439
25 116.0061165 39.30308279 5740.982966
26 116.7995794 38.91246552 4700.715897
27 116.5303186 39.8080365 4932.080876
28 117.0639808 39.66946388 5483.275955
29 116.3250182 38.67945028 5418.980766
30 116.5808915 39.52083053 4809.73109
31 117.0432767 38.59867832 5150.427732
32 116.3512265 39.98647718 3238.895439
33 117.0642774 38.721908 4115.64644
34 117.3109633 39.10773535 3669.711337
35 117.3595839 39.7080327 4838.445514
36 116.5258875 38.90563749 3753.752111
37 116.590771 39.04932663 5311.735335

2 求解模型的遗传算法设计
遗传算法是一种基于自然选择和群体遗传机理的搜索算法,它模拟了自然选择和自然遗传过程中的繁殖、杂交和突变现象.再利用遗传算法求解问题时,问题的每一个可能解都被编码成一个“染色体”,即个体,若干个个体构成了群体(所有可能解).在遗传算法开始时,总是随机的产生一些个体(即初始解),根据预定的目标函数对每一个个体进行评估,给出一个适应度值,基于此适应度值,选择一些个体用来产生下一代,选择操作体现了“适者生存”的原理,“好”的个体被用来产生下一代,“坏”的个体则被淘汰,然后选择出来的个体,经过交叉和变异算子进行再组合生成新的一代,这一代的个体由于继承了上一代的一些优良性状,因而在性能上要优于上一代,这样逐步朝着最优解的方向进化.因此,遗传算法可以看成是一个由可行解组成的群体初步进化的过程.

2、编码
利用遗传算法求解问题时,首先要确定问题的目标函数和变量,然后对变量进行编码,这样做主要是因为在遗传算法中,问题的解是用数字串来表示的,而且遗传算子也是直接对串进行操作的.编码方式可以分为二进制编码和实数编码.若用二进制编码表示个体,则二进制数转化为十进制数的解码公式可以为:

其中（bi1,bi2,…bil）,为某个个体的第i段,每段段长都为l,每个bik都是0或者1,Ti和Ri是第段分量Xi的定义域的两个端点.
3、遗传操作
遗传操作是模拟生物基因的操作,他的任务就是根据个体适应度对其施加一定的操作,从而实现优胜劣汰的进化过程.从优化搜索的角度来看,遗传操作可以使问题的解逐代优化,逼近最优解,遗传操作包括以下三个基本遗传算子:选择、交叉、变异.选择和交叉基本上完成了遗传算法的大部分搜索功能,变异增加了遗传算法找到最优解的能力.
3.1、选择
选择是指从群体中选择优良个体并淘汰劣质个体的操作.它建立在适应度评估的基础上.适应度越大的个体,被选中上的可能性就越大,他的“子孙”在下一代中的个数就越多,选择出来的个体就被放入配对库中.目前常用的选择方法有轮赌盘方法、最佳个体保留法、期望值法、排序选择法、竞争法、线性标准化法.
3.2、交叉
交叉就是指把两个父代个体的部分结构加以替换重组而生成新的个体的操作,交叉的目的是为了在下一代产生新的个体,通过交叉操作,遗传算法的搜索能力得到了飞跃性的提高.交叉是遗传算法获取优良个体的重要手段.交叉操作是按照一定的交叉概率在匹配库中随机的选取两个个体进行的,交叉位置也是随机的,交叉概率一般取得很大,为0.6~0.9.
3.3、变异
变异就是以很小的变异概率Pm随机地改变种群中个体的某些基因的值,变异操作的基本过程是:产生一个[0,1]之间的随机数rand,如果rand<Pm,则进行变异操作.变异操作本身是一种局部随机搜索,与选择、交叉算子结合在一起,能够避免由于选择和交叉算子而引起的某些信息永久性丢失,保证了遗传算法的有效性,使遗传算法具有了局部随机搜索能力,同时使得遗传算法能够保持群体的多样性,以防出现未成熟收敛.在变异操作中,变异概率不宜取得过大,如果Pm>0.5,遗传算法就退化为了随机搜索.

已知信息：37个需求点的坐标位置图

如何确定建立N个配送中心位置，在每个配送中心不超过最大容量M的条件下，使得N个配送中心到所有超市的总配送成本（配送单位距离单位需求量的所需成本×距离×需求量）最小呢？当然是通过算法优化求解啦！

先看下求解结果！
当取物流配送中心数量N=6，最大容量M=40000时，运行结果:
选择6个配送中心的运行结果：

最优解:
所选物流配送中心的编号为:16 18 19 4 2 11
超出容量约束限制的配送中心有0个
总配送成本为：372225.1222
其中：
编号16配送的需求点有：6 15 24 35, 总配送量为:25041.3454
编号18配送的需求点有：3 14 23, 总配送量为:16976.7853
编号19配送的需求点有：7 13 21 22 25 27 30 32, 总配送量为:39697.2441
编号4配送的需求点有：8 17 20 26 29 36 37, 总配送量为:31303.1843
编号2配送的需求点有：5 9 12 28, 总配送量为:19880.0428
编号11配送的需求点有：1 10 31 33 34, 总配送量为:29132.4748

当取物流配送中心数量N=4，最大容量M=50000时，运行结果:
选择4个配送中心的运行结果：

最优解:
所选物流配送中心的编号为:8 35 14 22
超出容量约束限制的配送中心有0个
总配送成本为：517401.5704
其中：
编号8配送的需求点有：4 11 17 20 26 29 31 33 36 37, 总配送量为:49099.5715
编号35配送的需求点有：1 2 6 15 16 24 28 34, 总配送量为:42962.5879
编号14配送的需求点有：3 10 18 23, 总配送量为:22360.4524
编号22配送的需求点有：5 7 9 12 13 19 21 25 27 30 32, 总配送量为:47994.4856

下面进行程序演示！