项目场景：
上次，我讲述了遗传算法应用在车间调度中的编码方式，今天，我讲一下解码，参考书目依然是高亮的《柔性作业车间调度智能算法及应用》
解码方式：
代码如下：
这是一组MK01的数据为测试数据，染色体编码为MSOS，最后用甘特图画出结果（注：此为没有收敛的）
import numpy as np
import copy
from mpl_toolkits.mplot3d import Axes3D
from matplotlib import cm
import matplotlib.pyplot as plt
import random
import itertools
#导入要解决的问题：Matrix:问题矩阵 J_num:工件数 M_num:机器数 Max_O_len：工序最长的值
from Problem import Matrix,J_num,M_num,Max_O_len
import time
CHS=[1, 3, 2, 1, 1, 2, 1, 1, 1, 2, 3, 5, 1, 2, 1, 2, 2, 6, 1, 1, 1, 3, 2, 5, 3, 1, 1, 2, 2, 3, 1, 1, 1, 1, 3, 2, 1,
2, 1, 3, 1, 5, 2, 2, 1, 1, 2, 5, 1, 1, 2, 1, 2, 2, 1, 1, 3, 1, 2, 1, 6, 6, 9, 8, 1, 1, 6, 8, 2, 3, 7, 2, 2, 7,
6, 1, 8, 6, 9, 8, 5, 10, 5, 7, 5, 3, 4, 4, 5, 2, 10, 1, 7, 4, 2, 8, 9, 1, 4, 10, 6, 9, 5, 3, 2, 9, 3, 7, 1, 3,
8, 7, 3, 9, 5, 4, 10, 4, 10, 10]
O=[
[[ 5, 9999, 4, 9999, 9999, 9999],
[9999, 1, 5, 9999, 3, 9999],
[9999, 9999, 4, 9999, 9999, 2],
[ 1, 6, 9999, 9999, 9999, 5],
[9999, 9999, 1, 9999, 9999, 9999],
[9999, 9999, 6, 3, 9999, 6]],
[[9999, 6, 9999, 9999, 9999, 9999],
[9999, 9999, 1, 9999, 9999, 9999],
[ 2, 9999, 9999, 9999, 9999, 9999],
[9999, 6, 9999, 6, 9999, 9999],
[ 1, 6, 9999, 9999, 9999, 5],
[ 0, 0, 0, 0, 0, 0]],
[[9999, 6, 9999, 9999, 9999, 9999],
[9999, 9999, 4, 9999, 9999, 2],
[ 1, 6, 9999, 9999, 9999, 5],
[9999, 6, 4, 9999, 9999, 6],
[ 1, 9999, 9999, 9999, 5, 9999],
[ 0, 0, 0, 0, 0, 0]],
[[ 1, 6, 9999, 9999, 9999, 5],
[9999, 6, 9999, 9999, 9999, 9999],
[9999, 9999, 1, 9999, 9999, 9999],
[9999, 1, 5, 9999, 3, 9999],
[9999, 9999, 4, 9999, 9999, 2],
[ 0, 0, 0, 0, 0, 0]],
[[9999, 1, 5, 9999, 3, 9999],
[ 1, 6, 9999, 9999, 9999, 5],
[9999, 6, 9999, 9999, 9999, 9999],
[ 5, 9999, 4, 9999, 9999, 9999],
[9999, 6, 9999, 6, 9999, 9999],
[9999, 6, 4, 9999, 9999, 6]],
[[9999, 9999, 4, 9999, 9999, 2],
[ 2, 9999, 9999, 9999, 9999, 9999],
[9999, 6, 4, 9999, 9999, 6],
[9999, 6, 9999, 9999, 9999, 9999],
[ 1, 6, 9999, 9999, 9999, 5],
[ 3, 9999, 9999, 2, 9999, 9999]],
[[9999, 9999, 9999, 9999, 9999, 1],
[ 3, 9999, 9999, 2, 9999, 9999],
[9999, 6, 4, 9999, 9999, 6],
[ 6, 6, 9999, 9999, 1, 9999],
[9999, 9999, 1, 9999, 9999, 9999],
[ 0, 0, 0, 0, 0, 0]],
[[9999, 9999, 4, 9999, 9999, 2],
[9999, 6, 4, 9999, 9999, 6],
[ 1, 6, 9999, 9999, 9999, 5],
[9999, 6, 9999, 9999, 9999, 9999],
[9999, 6, 9999, 6, 9999, 9999],
[ 0, 0, 0, 0, 0, 0]],
[[9999, 9999, 9999, 9999, 9999, 1],
[ 1, 9999, 9999, 9999, 5, 9999],
[9999, 9999, 6, 3, 9999, 6],
[ 2, 9999, 9999, 9999, 9999, 9999],
[9999, 6, 4, 9999, 9999, 6],
[9999, 6, 9999, 6, 9999, 9999]],
[[9999, 9999, 4, 9999, 9999, 2],
[9999, 6, 4, 9999, 9999, 6],
[9999, 1, 5, 9999, 3, 9999],
[9999, 9999, 9999, 9999, 9999, 1],
[9999, 6, 9999, 6, 9999, 9999],
[ 3, 9999, 9999, 2, 9999, 9999]]
]
T0=60
n=10
Max_Onum=6
M0=6
# 染色体解码
def Chromosome_decoding( CHS,O,T0,n,Max_Onum,M0):
# 初始化
JM = np.zeros((n, Max_Onum), dtype=int) # JM(j,h)表示工件Ji的工序Oh的机器号
T = np.zeros((n, Max_Onum), dtype=int) # T（j,h）表示工件Jj的工序Oh的加工时间
# 步骤1：对机器选择部分进行解码，从左到右依次读取并转换成机器顺序矩阵JM和时间顺序矩阵T
MS = CHS[0:T0]
OS = CHS[T0:2 * T0]
GX_num = 0
for J_j in MS: # 将机器选择部分转换成机器顺序矩阵和时间顺序矩阵
GX_num += 1
JM_j = int((GX_num - 1) / Max_Onum) # 机器顺序矩阵的横坐标
JM_h = int((GX_num - 1) % Max_Onum) # 机器顺序矩阵的纵坐标
O_j = np.array(O[JM_j][JM_h])
Mac_using = []
Mac_time = []
for Mac_num in range(len(O_j)): # 寻找MS对应部分的机器时间和机器顺序
if O_j[Mac_num] != 9999:
Mac_using.append(Mac_num)
Mac_time.append(O_j[Mac_num])
else:
continue
JM[JM_j][JM_h] += Mac_using[J_j - 1] # 机器顺序矩阵
T[JM_j][JM_h] += Mac_time[J_j - 1] # 时间顺序矩阵
# 步骤2：按照步骤1对应的T和JM依次得到每个工件工序对应的加工机器和加工时间
Start_time = np.zeros((M0, T0), dtype=int) # 机器开始加工的时间
End_time = np.zeros((M0, T0), dtype=int) # 机器结束加工的时间
Counter_List = []
T_count = 0
for OS_j in OS: # 通过机器顺序矩阵和时间顺序矩阵的到工序的加工机器和加工时间
Counter_List.append(OS_j)
M_i_h = Counter_List.count(OS_j) # 该工件的第几道工序
M_i = JM[OS_j - 1][M_i_h - 1] # 这道工序使用的机器
P_ij = T[OS_j - 1][M_i_h - 1] # 这道工序的加工时间
OS_site = (OS_j - 1) * Max_Onum + M_i_h - 1
# 确定工序为机器的第几道加工工序
M_n_list = [[M_n, End_time[M_i][M_n]] for M_n in range(len(End_time[M_i])) if End_time[M_i][M_n] != 0]
# Oij为工件的第一道加工工序，且是机器M_i的第一道加工工序，直接从机器M_i的零时刻进行加工
if M_i_h == 1 and len(M_n_list) == 0:
Start_time[M_i][OS_site] = 0
End_time[M_i][OS_site] += P_ij
# 工序O_jh是机器M_i的第一道工序，不是工件的第一道工序，从上道工序完工时间处开始加工
elif len(M_n_list) == 0 and M_i_h > 1:
# 寻找该工件上一道工序的完工时间：
SD_Machine = JM[OS_j - 1][M_i_h - 2] # 上道工序的加工机器
S = End_time[SD_Machine][OS_site - 1]
Start_time[M_i][OS_site] = S
End_time[M_i][OS_site] = S + P_ij
# 工序不是机器的第一道工序，是工件的第一道工序
elif len(M_n_list) != 0 and M_i_h == 1:
M_n_list = dict(M_n_list)
M_n_list = sorted(M_n_list.items(), key=lambda item: item[1]) # 此机器上各已加工时间结束时间
M_n_Start = [[M_n_list[key][0], Start_time[M_i][M_n_list[key][0]]] for key in
range(len(M_n_list))] # 此机器上已加工工序各开始时间
if len(M_n_list) > 1:
for i_tem in range(len(M_n_list) - 1):
if i_tem == 0 and M_n_Start[i_tem][1] >= P_ij:
Start_time[M_i][OS_site] = 0
break
elif M_n_Start[i_tem + 1][1] - M_n_list[i_tem][1] >= P_ij:
Start_time[M_i][OS_site] = M_n_list[i_tem][1]
break
elif i_tem == len(M_n_list) - 2:
Start_time[M_i][OS_site] = M_n_list[i_tem + 1][1]
else:
if M_n_Start[0][1] >= P_ij:
Start_time[M_i][OS_site] = 0
else:
Start_time[M_i][OS_site] = M_n_list[0][1]
End_time[M_i][OS_site] = Start_time[M_i][OS_site] + P_ij
else: # 工序既不是机器的第一道工序，也不是工件的第一道工序
M_n_list = dict(M_n_list)
M_n_list = sorted(M_n_list.items(), key=lambda item: item[1]) # 此机器上各已加工时间结束时间
M_n_Start = [[M_n_list[key][0], Start_time[M_i][M_n_list[key][0]]] for key in
range(len(M_n_list))] # 此机器上已加工工序各开始时间
SD_Machine = JM[OS_j - 1][M_i_h - 2] # 该工件上道工序加工工件
S = End_time[SD_Machine][OS_site - 1] # 该工序上道工序完工时间
Max_Machine_time = max([M_n_list[k_1][1] for k_1 in range(len(M_n_list))])
Start_time[M_i][OS_site] = max(Max_Machine_time, S)
if len(M_n_list) > 1:
for i_tem in range(len(M_n_list) - 1):
if M_n_Start[0][1] > S and M_n_Start[0][1] - S >= P_ij:
Start_time[M_i][OS_site] = S
break
if M_n_Start[i_tem + 1][1] - M_n_list[i_tem][1] >= P_ij and M_n_Start[i_tem + 1][1] > S:
if M_n_list[i_tem][1] > S:
Start_time[M_i][OS_site] = M_n_list[i_tem][1]
elif M_n_Start[i_tem + 1][1] - S >= P_ij:
Start_time[M_i][OS_site] = S
break
else:
if M_n_Start[0][1] > S and M_n_Start[0][1] - S >= P_ij:
Start_time[M_i][OS_site] = S
End_time[M_i][OS_site] = Start_time[M_i][OS_site] + P_ij
Fitness = np.max(End_time)
for i in range(len(End_time)):
for j in range(len(End_time[i])):
if End_time[i][j] - Start_time[i][j] == 0:
Start_time[i][j] = 0
End_time[i][j] = 0
return Start_time, End_time, Fitness
C=Chromosome_decoding( CHS,O,T0,n,Max_Onum,M0)
print(C)
#绘制甘特图
def gatt(CHS,T0,n,Max_Onum,M0):
CHromo = Chromosome_decoding( CHS,O,T0,n,Max_Onum,M0)
# print(CHromo)
End_time = CHromo[1]
Start_time = CHromo[0]
N =M0
Start = []
End = []
M = ['red', 'blue', 'yellow', 'orange', 'green', 'palegoldenrod', 'purple', 'pink', 'Thistle', 'Magenta',
'SlateBlue', 'RoyalBlue', 'Cyan', 'Aqua', 'floralwhite', 'ghostwhite', 'goldenrod', 'mediumslateblue',
'navajowhite',
'navy', 'sandybrown', 'moccasin']
s = ('/', '+', 'x', '\\', '||', 'o', '///', '//' '.', '//', '#', '||')
for i in range(N):
for j in range(T0):
if End_time[i][j] != 0 and End_time[i][j] - Start_time[i][j] != 0:
plt.barh(i, width=End_time[i][j] - Start_time[i][j], height=0.5, left=Start_time[i][j],
color=M[int(j / Max_Onum)], edgecolor='black')
plt.text(x=Start_time[i][j] + 0.1, y=i, s=(int(j / Max_Onum) + 1, j % Max_Onum + 1),
fontsize=8)
Start.append(Start_time[i][j])
End.append(End_time[i][j])
plt.yticks(np.arange(i + 1), np.arange(1, i + 2))
plt.show()
gatt(CHS,T0,n,Max_Onum,M0)
结果
解码后的矩阵：
(array([[ 6, 0, 0, 16, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 20, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 4,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 0, 0, 0,
0, 1, 0, 22, 0, 0, 0, 0, 0, 0, 0, 67],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0,
0, 0, 0, 42, 0, 0, 0, 0, 0, 0, 36, 0, 0, 0, 0, 0,
6, 18, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 24, 0, 0,
0, 0, 0, 0, 0, 0, 0, 48, 0, 0, 0, 0],
[ 0, 0, 0, 0, 17, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 28,
0, 0, 0, 0, 48, 0, 0, 0, 0, 0, 0, 42, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 37, 0, 0, 4, 0, 0, 0, 0,
0, 0, 0, 0, 24, 0, 9, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 38, 0, 0, 0, 13, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 46, 0, 0, 0,
0, 0, 0, 36, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 30, 0,
0, 0, 19, 0, 0, 52, 0, 0, 0, 0, 61, 0],
[ 0, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
37, 0, 0, 0, 0, 49, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 36, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 54, 0, 0, 0],
[ 0, 0, 14, 0, 0, 0, 0, 0, 0, 0, 29, 0, 0, 18, 0, 0,
0, 0, 0, 0, 0, 0, 58, 0, 0, 0, 0, 0, 0, 52, 0, 0,
0, 0, 24, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 60, 0, 0]]), array([[11, 0, 0, 17, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0, 21, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 6,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 0, 0, 0,
0, 2, 0, 24, 0, 0, 0, 0, 0, 0, 0, 70],
[ 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 18, 0, 0, 0,
0, 0, 0, 48, 0, 0, 0, 0, 0, 0, 42, 0, 0, 0, 0, 0,
12, 24, 0, 0, 0, 0, 36, 0, 0, 0, 0, 0, 0, 30, 0, 0,
0, 0, 0, 0, 0, 0, 0, 54, 0, 0, 0, 0],
[ 0, 0, 0, 0, 18, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 32,
0, 0, 0, 0, 49, 0, 0, 0, 0, 0, 0, 46, 0, 0, 4, 0,
0, 0, 0, 0, 0, 0, 0, 0, 38, 0, 0, 8, 0, 0, 0, 0,
0, 0, 0, 0, 28, 0, 13, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 41, 0, 0, 0, 19, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 52, 0, 0, 0,
0, 0, 0, 38, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 36, 0,
0, 0, 22, 0, 0, 58, 0, 0, 0, 0, 67, 0],
[ 0, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
42, 0, 0, 0, 0, 52, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 37, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 57, 0, 0, 0],
[ 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 34, 0, 0, 20, 0, 0,
0, 0, 0, 0, 0, 0, 60, 0, 0, 0, 0, 0, 0, 58, 0, 0,
0, 0, 29, 0, 4, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0, 0, 61, 0, 0]]), 70)
甘特图：
