使⽤python 编写离散型⼯⼚选址问题的遗传算法（课程作业）
离散型⼯⼚选址问题的遗传算法
⼀、问题描述
1.1 ⼯⼚选址问题
⼯⼚选址（facility location），就是确定在何处建⼚、仓储中⼼或建⽴服务设施。它不仅关系到设施建设的投资和建设速度，⽽且在很⼤程度上决定了所提供的产品和服务的成本，从⽽影响企业的⽣产管理活动和经济效益。除了少数的原材料采掘企业，如矿产企业、原⽊采伐企业必须将选址定在相应资源丰富的所在地，绝⼤多数企业都将⾯临着不同的选址问题的决策。随着全球制造的出现，现代企业的选址问题涉及的范围已超出某⼀地区、某⼀国家了，⽽是在全球范围内考虑选址的问题。
离散选址是指在有限的侯选位置⾥⾯，选取最为合适的⼀个或⼀组位置为最优⽅案，对应的模型叫做离散选址模型。它与连续选址模型的区别在于：它所拥有的侯选⽅案只有有限个元素，在进⾏选址时只需对有限个位置进⾏分析。离散选址问题⼀般都可以⽤混合整数规划模型来表⽰，模型中的⽬标函数可以采⽤以选址问题的最短距离为⽬标，如p-Median问题和p-Center问题及其衍⽣问题。也可以采⽤选址问题的最⼩费⽤为⽬标等。
1.2 离散选址模型
给定某⼀地区所有需求点的地址集合，要求从备选地址中选出⼀定数⽬的地址建⽴⼯⼚，从⽽建⽴⼀系列的配送区域，实现各个需求点的配送，使得在选出点建⽴的⼯⼚与各需求点形成的配送系统总配送费⽤最少。为了便于建⽴模型，需作⼀定的假设，假设系统满⾜如下⼀些条件：
仅在⼀定的被选对象内考虑新的⼯⼚建⼚；运输费⽤与运输量成正⽐；需求点的需求按区域总计；⼯⼚⽣产能⼒可以满⾜需求；各需求点的需求量⼀定且为⼰知；
总费⽤只考虑固定的⼯⼚建址费⽤和运输费⽤。
该选址问题的混合整数规划模型为：
式中，为⼯⼚备选地点的个数；为需求点的个数；为可设置⼯⼚的最⼤个数；；为从⼯⼚到需求点的运输量；为整数变量，当=1时表⽰地被选中，当=0时表⽰地未被选中；为第地的需求量；为被选⼯⼚的建设容量（供应能⼒）；为从地到地的包括装卸运输费在内的单位运输费⽤；为被选⼯⼚的固定费⽤（包括基本投资费和固定经营费）。
⽬标函数(1)中，等式右边第⼀项是从⼯⼚到需求点的运输成本；第⼆项是⼯⼚设置的固定成本。式(2)表⽰从各⼯⼚向某需求点供给的物资总和应满⾜该需求点的需求量；式(3)表⽰如果i地点被选中建⼚，则从它发出的货物总量不超过它的建设容量（供应能⼒）；式(4)表⽰选上的⼯⼚个数不得超过原定的最⼤限额。
⼆、遗传算法设计
m n p x ij i j y i y i i y i i b j j a i i c ij i j d i i
2.1 遗传算法的基本步骤
遗传编码 初始种的⽣成 适应度评估检测
<；未满⾜迭代终⽌条件>1. 选择
2. 交叉
3. 变异
4. 适应度评估检测
2.2 遗传编码
采⽤⼆重结构编码对离散⼯⼚选址模型的约束条件进⾏处理，这种编码⽅式可以避免⽆效染⾊体的产⽣，提⾼遗传算法的搜索效率。⼆重结构编码⽅法如图1所⽰。染⾊体表⽰的⼆重结构由变量码和附加码两⾏组成。上⾏为变量的附加码，，表⽰⼯⼚备选地的序号，下⾏为变量对应于附加码的值表⽰该⼯⼚是否被选中。
附加码……变量码
…
…
图1 ⼯⼚选址的⼆重结构编码
个体编码时，⾸先按洗牌⽅式随机产⽣附加码，列于上⾏；然后随机产⽣下⾏的变量码值{0或1}，这样构成⼀个个体的⼆重结构编码。按照这种⽅式随机产⽣初始体。
由式(2)、式(3)很容易得出约束条件。因此，个体解码时（图1），按照从左到右的顺序，依次考虑变量的附加码，即按照顺序考虑附加码为的⼯⼚。如果为1的⼯⼚容量之和⼩于所有需求点的需求量之和，则随机产⽣⼀个不⼤于的⾃然数；如果
为0，则强制该数为1，并将附加码为的⼯⼚的容量与处理前变量码为1的⼯⼚的容量相加。按照这种⽅法处理，直到变量码为1的
⼯⼚的容量之和不⼩于所有需求点的需求量之和为⽌。 解码算法的步骤为：
若则执⾏否则执⾏随机产⽣⼀个不⼤于的⾃然数为如果则令返回否则继续执⾏算法终⽌。
对于⼀个含有8个备选⼯⼚的选址问题，如果随机产⽣的附加码序列为9、3、1、5、4、6、8、10，2，7，该个体的⼆重结构编码如图2所⽰。它对应⼀个选址⽅案，变量码为1的⼯⼚被选中，即选择序号为3、5、6，10，7的地址建⼚。
step 1.step 2.step 3.step 4.WHILE DO
step 5.END  DO
s (k )y s (k )s (k )=i y s (k )s (k )s (1)s (2)s (k )s (m )y s (1)
y s (2)
y s (k )
y s (m )
{s (k ),k =l ,⋯,m }b ⩽j =1∑
n
j a y i =1∑
m
i i s (k )y s (k )m s (k )y s (k )s (k )step 1:sum =1y a ,sum =
i =1∑
m
s k s k 2b ;
j =1∑
n
j step 2:sum <1sum ,2step 3,step 4；
step 3:m s (k ),y =s (k )0,sum =1sum +1a ,y s (k )s (k )=1,step 2;step 3;step 4:
931546810270
1
1
1
1
1
图2 ⼀个个体的⼆重结构编码
2.3 适值计算
离散型⼯⼚选址问题的适值函数为
，可以将适值函数看成两个部分组成，分别是（运输成
本），（固定成本）。对于⼀个染⾊体⽽⾔，由于的值是确定的，⽽且是已知的，所以固定成本可以直接算出来，那么可以将适值函数简化为
，其中，因此可以应⽤产⼤于销的运输问题模型求出的值，利⽤式(1)可以求出
⽬标函数的值。由于适值是体中个体⽣存机会选择的唯⼀确定性指标，所以适值函数的形式直接决定着体的进化⾏为。为了直接将适值函数与体中的个体优劣度量相联系，在遗传算法中适值规定为⾮负，并且在任何情况下总是越⼤越好。对于本节讨论的选址问题所建⽴的⽬标函数，式(1)是求最⼩值，因此，令适值函数的倒数，即可求出该染⾊体的适值。
2.4 选择操作
采⽤最优⽅式实现选择操作，即种中适值最⼤的个体直接遗传到下⼀代，并把进化到⽬前为⽌最好的个体代替当代产⽣的最差个体直接复制到下⼀代，其余个体按照赌选择⽅法产⽣⼦代。赌选择
⼜称⽐例选择⽅法.其基本思想是：各个个体被选中的概率与其适应度⼤⼩成正⽐。具体操作如下：
1. 计算出体中每个个体的适应度f（i=1，2，…，M），M为体⼤⼩；
2. 计算出每个个体被遗传到下⼀代体中的概率；
3.计算出每个个体的累积概率；
（称为染⾊体的积累概率）4.在[0,1]区间内产⽣⼀个均匀分布的伪随机数；5.若，则选择个体1，否则，选择个体，使得：成⽴；6.重夏（4）、（5）共M次
2.5 遗传操作
遗传操作调⽤了Python的遗传算法的库交叉
min f =
c x +
d y i =1∑j
∑
ij ij i =1∑
i i
c x i =1∑m j ∑
n
ij ij d y i =1∑
m
i i y i d i min f =c x +M
i =1
∑m j
∑
n
ij ij M =d y i =1∑
m
i i x ij f P x =
(i )f
x j =1∑
N (j )
f x (i )q =
i P x j =1
∑
i
(j )
q i X [i ],i =1,2,...,n r r <q [1]k q [k −1]<r ⩽q [k ]geatpy
对于交叉操作，采⽤通常的操作算⼦，产⽣新个体的上⾏附加码会出现重复。因此，采⽤部分映射交叉()算⼦。我们通过调⽤geatpy库的Xovpm函数来实现。图3为两个⽗代个体经
操作产⽣两个⼦代个体的情况。
图3 ⼆重结构编码的PMX
需要说明的是，PMX操作只针对个体的上⾏附加码，⼦代个体的下⾏变量仍根据其⽗代个体中附加码
与变量码的对应关系确定。变异
对于变异操作，采⽤逆位遗传算⼦。如图4所⽰，对⽗代个体随机选择两个变异点，两点间的上⾏附加码按相反顺序重新排列，⽽下⾏的变
量码顺序则保持不变。
图4 逆位遗传变异
三、程序代码
import  geatpy as  ga  # 解遗传算法的库from  pymprog import  *  # 解运输问题的库import  numpy as  np import  xlrd
# -------------------解码函数---------------------------def  decode (Y , A , B , m ):    # step1
List1 = np .multiply (np .array (Y ), np .array (A ))  # 计算 y*a    sum1 = 0  # 再把他们累加起来    for  i in  List1:        sum1 += i    sum2 = 0    for  j in  B :        sum2 += j    # step2
while  sum1 < sum2:
k = np .random .randint (0, m )
PMX PMX
k = np.random.randint(0, m)
if Y[k]==0:
sum1 += A[k]
Y[k]=1
else:
k = np.random.randint(1, m +1)
continue
# else:
# print("算法终⽌")
return Y
# -----------------------适值函数-------------------------------
# 固定成本函数
def Fixed_cost(List2):
fixed_cost =0# 再进⾏累加计算计算建⼚的固定成本
for i in List2:
fixed_cost += ipython生成1到100之间随机数
return fixed_cost
# 运输成本函数
def report(Y_decode, A, B):# 返回(产地，销地)：运价；产地：产量；销地：销量
# 把⽬标函数简化成产⼤于销的运输问题
a =("A1","A2","A3","A4","A5","A6","A7","A8","A9","A10")# ⼯⼚（产地）
b =("B1","B2","B3","B4","B5","B6","B7","B8","B9","B10",
"B11","B12","B13","B14","B15","B16","B17","B18","B19","B20","B21")# 需求地（销地）    datas =dict()# 定义⼀个空字典 (产地，销地)：运价
datac =dict()# 定义⼀个空字典产地：产量
datax =dict()# 定义⼀个空字典销地：销量
List3 = np.multiply(np.array(Y_decode), np.array(A))# 计算 y*a    产量
# （产地，销地）：运价
Data = xlrd.open_workbook('单位运输费⽤.xlsx')# 读取Excel运价列表
table = Data.sheets()[0]# 读取Excel列表的sheet1
for i in range(0,10):# 先从⼗⾏⾥⾯拿出⼀⾏来
x = np.w_values(i))
for j in range(0,21):# 再从21列中取⼀列
data = x[j]
datas[a[i], b[j]]= data  # (产地，销地)：运价
# 产地：产量
y = List3
for i in range(0,10):
datac[a[i]]= y[i]# 产地：产量
# 销地：销量
for j in range(0,21):
datax[b[j]]= B[j]# 销地：销量
return(datas, datac, datax)
def Transport_cost(datas, datac, datax):
a =("A1","A2","A3","A4","A5","A6","A7","A8","A9","A10")# ⼯⼚（产地）
b =("B1","B2","B3","B4","B5","B6","B7","B8","B9","B10",
"B11","B12","B13","B14","B15","B16","B17","B18","B19","B20","B21")# 需求地（销地）# 开始模型计算
X = np.zeros((10,21))# ⽣成10⾏21列的0矩阵
cost =0.0
begin('Transport')
x = var('x', datas.keys())# 调运⽅案
minimize(sum(datas[i, j]* x[i, j]for(i, j)in datas.keys()),'Cost')# 总运费最少
for i in datac.keys():# 产地产量约束