本文主要參考張秀芬等人的《支持復(fù)雜產(chǎn)品并行拆卸序列規(guī)劃的遺傳算法》纪岁。
文章摘要如下：
為高效求解復(fù)雜產(chǎn)品的并行拆卸序列規(guī)劃問(wèn)題, 提出基于遺傳算法的復(fù)雜產(chǎn)品并行拆卸序列規(guī)劃方法. 針對(duì)并行拆卸序列規(guī)劃問(wèn)題中拆卸序列長(zhǎng)度和每步拆卸零部件個(gè)數(shù)不確定的特點(diǎn), 提出并行序列染色體編碼方法, 分別將拆卸單元序列和拆卸步長(zhǎng)作為染色體的前段和后段, 以此表示一個(gè)拆卸序列. 基于該染色體編碼, 采用拆卸混合圖描述產(chǎn)品零部件間裝配約束關(guān)系和拆卸優(yōu)先級(jí), 并導(dǎo)出拆卸約束矩陣和鄰接矩陣, 由矩陣隨機(jī)獲取可行的初始染色體種群; 將基本拆卸時(shí)間和不可行拆卸懲罰因子作為優(yōu)化目標(biāo)來(lái)構(gòu)建適應(yīng)度函數(shù), 確保最優(yōu)解的可行性; 在初始染色體種群的基礎(chǔ)上, 適應(yīng)度函數(shù)最小為優(yōu)化目標(biāo), 通過(guò)遺傳、交叉和變異遺傳算子實(shí)現(xiàn)并行拆卸序列的優(yōu)化. 最后通過(guò)實(shí)例驗(yàn)證了該方法的可行性和實(shí)用性.
大致的想法就是通過(guò)遺傳算法對(duì)找出一個(gè)最優(yōu)的拆解方式里烦，使得整個(gè)部件的拆卸耗時(shí)最短。
１.首先確定染色體編碼方式：
給出一個(gè)示例：
2.然后是初始化種群锥债，其步驟如下：
以上兩步的代碼如下：
import numpy as np
import copy
from parameter import *
from random import sample
def Species_initial():
Species=np.zeros((M,N*2))
for m in range(M):
Wm_temp=copy.deepcopy(Wm)
st=0;sn=N
while st<N:
Wmt=Wm_temp.T
Alter=[]
#如果某一個(gè)零件沒(méi)有前置拆卸零件岸售， print(max_spend)則將其保存到備選零件中
for i in range(N):
kk=Species[m,0:st]-1
if i not in kk:
if (Wmt[i,:]==0).all():
Alter.append(i)
#如果備選零件數(shù)小于拆卸并行度，則將所有的零件加入一個(gè)基因中
lens=len(Alter)
if Dp>=lens:
sample_num=lens
else:
sample_num=Dp
Sample=sample(Alter,sample_num)
Species[m,st:st+sample_num]=np.array(Sample)+1#前半部分放零件編號(hào)
Species[m,sn]=sample_num#后面放并行長(zhǎng)度
st=st+sample_num#更新位置
sn=sn+1
#如果已經(jīng)加入樂(lè)備選翰灾，則將原來(lái)的矩陣進(jìn)行更新缕粹，避免下次重復(fù)選擇
for i in range(st):
for j in range(N):
op=int(Species[m,i]-1)
# print(op)
if Wm_temp[op,j]==-1:
Wm_temp[op,j]=0
return Species
3.確定適應(yīng)度函數(shù)：
#計(jì)算適應(yīng)度值
def GA_fitness(Specie):
i=N;#染色體的拆卸步長(zhǎng)基因序號(hào),從22到43
st=0;#染色體的拆卸零件基因序號(hào)，從0到21
Total_Spends=0#每個(gè)序列的拆卸時(shí)間總和
while int(Specie[i])!=0:#從染色體的第N=22個(gè)基因片段開(kāi)始纸淮，只要執(zhí)行步長(zhǎng)不是0平斩，就一直執(zhí)行計(jì)算
spend=[]#保存每組并行節(jié)點(diǎn)的拆卸時(shí)間
num=int(Specie[i])#將拆卸步長(zhǎng)強(qiáng)制轉(zhuǎn)化為整型
for j in range(st,st+num):#執(zhí)行循環(huán)操作，將每個(gè)并行節(jié)點(diǎn)的拆卸時(shí)間保存進(jìn)列表spend
spend.append(Spends[int(Specie[j])-1])
max_spend=max(spend)#找出列表中最大值咽块，即并行操作中最耗時(shí)的一個(gè)拆卸
Total_Spends=Total_Spends+max_spend#總的拆卸時(shí)長(zhǎng)等于每個(gè)并行拆卸中最大時(shí)間之和绘面，見(jiàn)文中適應(yīng)度函數(shù)前半部分
i=i+1#進(jìn)行下一個(gè)拆卸步長(zhǎng)
st=st+num#拆卸零件同步進(jìn)行更新
P=0#懲罰項(xiàng)初始化為0，
Wm_temp=copy.deepcopy(Wm)#對(duì)約束矩陣進(jìn)行深度拷貝
#判斷進(jìn)化過(guò)程中的解是否可行
for j in range(0,N):
Wmt=Wm_temp.T#對(duì)約束矩陣進(jìn)行轉(zhuǎn)置操作，便于通過(guò)判斷列是否全為0揭璃，來(lái)判斷是否為可行解
num=int(Specie[j])-1#約束下標(biāo)=零件序號(hào)-1
#如果權(quán)重矩陣中當(dāng)前零件對(duì)應(yīng)的行全為0晚凿，則將原約束矩陣中對(duì)應(yīng)列全置為1，
#便于下一個(gè)拆卸操作的判斷塘辅，這里稍微有點(diǎn)繞晃虫，需要想清楚原理
if (Wmt[num,:]==0).all():
Wm_temp[num,:]=0
#如果權(quán)重矩陣中當(dāng)前零件對(duì)應(yīng)的行不全為0，意思是當(dāng)前拆卸的零件還有前置依賴零件沒(méi)有拆除
#因此扣墩，該拆卸不可能正常進(jìn)行哲银，因此這個(gè)解是不可行的，將懲罰項(xiàng)設(shè)為1呻惕，直接跳出循環(huán)
else:
P=1
break
#綜合以上兩部分荆责，返回適應(yīng)度函數(shù)值，見(jiàn)文章第4頁(yè)左下角適應(yīng)度函數(shù)公式
return Total_Spends+200*P
4.遺傳算法實(shí)現(xiàn)見(jiàn)論文2.6亚脆，代碼實(shí)現(xiàn)如下：
#如果終止條件不滿足做院，利用輪盤賭算法實(shí)現(xiàn)找出根據(jù)概率找出兩個(gè)適應(yīng)度較小的染色體
#輪盤賭方法
def RouletteWheelSelection(genetic_fitness_list):#genetic_fitness_list為第(1)步得到的適應(yīng)度列表
#計(jì)算適應(yīng)度總和與每個(gè)適應(yīng)度的比例，由于本文要求適應(yīng)度越低越好濒持，所以是反著來(lái)
max_fitness=np.max(genetic_fitness_list)
genetic_fitness_list=max_fitness/genetic_fitness_list
sum_fitness=genetic_fitness_list.sum()
prob_fitness=genetic_fitness_list/sum_fitness
#需要隨機(jī)生成兩個(gè)概率用于染色體選擇
prob1=random.random()
prob2=random.random()
#待選的兩個(gè)染色體的在列表中位置
selection1=0
selection2=0
#因?yàn)橐x擇兩個(gè)染色體键耕，所以要轉(zhuǎn)兩次，輪盤轉(zhuǎn)起來(lái)啦柑营，具體原理應(yīng)該能看懂吧
prob_total=0
for i in range(len(genetic_fitness_list)):
prob_total=prob_total+prob_fitness[i]
if prob_total>prob1:
selection1=i
break
prob_total=0
for i in range(len(genetic_fitness_list)):
prob_total=prob_total+prob_fitness[i]
if prob_total>prob2 and i!=selection1:
selection2=i
break
return selection1,selection2
#交叉
def CrossOver(Species_inition,s1,s2):
crosspoint=np.random.randint(1,N)
new_specie1_part1=Species_inition[s1,0:crosspoint]
c=filter(lambda x:x not in new_specie1_part1,Species_inition[s2,0:N])
new_specie1_part2=np.array(list(c))
new_specie1_part3=Species_inition[s2,N:N*2]
new_specie2_part1=Species_inition[s2,0:crosspoint]
c=filter(lambda x:x not in new_specie2_part1,Species_inition[s1,0:N])
new_specie2_part2=np.array(list(c))
new_specie2_part3=Species_inition[s1,N:N*2]
new_specie1=np.hstack((new_specie1_part1,new_specie1_part2,new_specie1_part3))
new_specie2=np.hstack((new_specie2_part1,new_specie2_part2,new_specie2_part3))
return new_specie1,new_specie2
#變異
def Mutation(s):
m1,m2=np.random.randint(0,N,2)
n1,n2=np.random.randint(N,N*2,2)
temp1=copy.deepcopy(s[m1])
s[m1]=copy.deepcopy(s[m2])
s[m2]=copy.deepcopy(temp1)
temp2=copy.deepcopy(s[n1])
s[n1]=copy.deepcopy(s[n2])
s[n2]=copy.deepcopy(temp2)
c=np.array(list(filter(lambda x:x!=0,s)))
d=np.zeros((len(s)-len(c)))
s=np.hstack((c,d))
return s
# for i in range(iteration):
5.仿真示例：
參數(shù)初始化
import numpy as np
#參數(shù)初始化
Dp=3#拆卸并行度
N=22#節(jié)點(diǎn)個(gè)數(shù)
M=10#種群規(guī)模
iteration=500
#約束矩陣
Wm=np.zeros((22,22))
Wm[8][0]=-1;Wm[9][1]=-1;Wm[5][2]=-1;Wm[5][3]=-1;Wm[19][4]=-1;Wm[20][4]=-1;
Wm[8][5]=-1;Wm[9][5]=-1;Wm[18][5]=-1;Wm[19][5]=-1;Wm[18][6]=-1;Wm[18][7]=-1;
Wm[6][8]=-1;Wm[18][8]=-1;Wm[7][9]=-1;Wm[18][9]=-1;Wm[10][14]=-1;Wm[11][15]=-1;
Wm[12][16]=-1;Wm[13][17]=-1;Wm[10][18]=-1;Wm[11][18]=-1;Wm[12][18]=-1;
Wm[13][18]=-1;Wm[18][19]=-1;Wm[20][19]=-1;Wm[18][20]=-1;Wm[2][21]=-1;Wm[3][21]=-1;
Wm[4][21]=-1;Wm[5][21]=-1;Wm[18][21]=-1;
#每個(gè)零件拆卸時(shí)間
Spends=[1,1,1,1,5.5,2,1,1,0.5,0.5,2,2,2,2,0.5,0.5,0.5,0.5,5,2,3,0]
執(zhí)行算法：
Species_inition=Species_initial()
for x in range(iteration):
GA_fitness_list=[]
for i in range(M):
GA_fitness_list.append(GA_fitness(Species_inition[i]))
s1,s2=RouletteWheelSelection(GA_fitness_list)
son1,son2=CrossOver(Species_inition,s1,s2)
son1=Mutation(son1)
son2=Mutation(son2)
g1=GA_fitness(son1)
g2=GA_fitness(son2)
if g1<min(GA_fitness_list):
i1=GA_fitness_list.index(min(GA_fitness_list))
Species_inition[i1]=son1
if g2<min(GA_fitness_list):
i2=GA_fitness_list.index(min(GA_fitness_list))
Species_inition[i2]=son2
print("第",x+1,"次迭代后屈雄，最小適應(yīng)度函數(shù)值為:",min(GA_fitness_list))
print("當(dāng)Dp為",Dp,"時(shí)，最小適應(yīng)度函數(shù)值為:",min(GA_fitness_list))
min_i=GA_fitness_list.index(min(GA_fitness_list))
best_specie=Species_inition[min_i]
print("當(dāng)Dp為",Dp,"時(shí)官套，最優(yōu)序列為:",best_specie)
c=filter(lambda x:x!=0,best_specie[N:N*2])
c=np.array(list(c))
lc=0
for x in range(len(c)):
num=int(c[x])
for y in range(num):
plt.plot(x,best_specie[lc],'rs')
lc=lc+1
plt.show()
效果結(jié)果：
第 1 次迭代后酒奶，最小適應(yīng)度函數(shù)值為: 20.5
第 2 次迭代后，最小適應(yīng)度函數(shù)值為: 20.5
第 3 次迭代后奶赔，最小適應(yīng)度函數(shù)值為: 20.5
第 4 次迭代后惋嚎，最小適應(yīng)度函數(shù)值為: 20.5
第 5 次迭代后，最小適應(yīng)度函數(shù)值為: 20.5
第 6 次迭代后站刑，最小適應(yīng)度函數(shù)值為: 20.5
第 7 次迭代后另伍，最小適應(yīng)度函數(shù)值為: 20.5
第 8 次迭代后，最小適應(yīng)度函數(shù)值為: 20.5
第 9 次迭代后绞旅，最小適應(yīng)度函數(shù)值為: 20.5
第 10 次迭代后质况，最小適應(yīng)度函數(shù)值為: 20.5
第 11 次迭代后，最小適應(yīng)度函數(shù)值為: 20.5
第 12 次迭代后玻靡，最小適應(yīng)度函數(shù)值為: 20.5
第 13 次迭代后，最小適應(yīng)度函數(shù)值為: 20.5
第 14 次迭代后中贝，最小適應(yīng)度函數(shù)值為: 20.5
第 15 次迭代后囤捻，最小適應(yīng)度函數(shù)值為: 20.5
第 16 次迭代后，最小適應(yīng)度函數(shù)值為: 20.5
第 17 次迭代后邻寿，最小適應(yīng)度函數(shù)值為: 20.0
第 18 次迭代后蝎土，最小適應(yīng)度函數(shù)值為: 20.0
第 19 次迭代后视哑，最小適應(yīng)度函數(shù)值為: 20.0
第 20 次迭代后，最小適應(yīng)度函數(shù)值為: 20.0
第 21 次迭代后誊涯，最小適應(yīng)度函數(shù)值為: 19.0
......
第 484 次迭代后挡毅，最小適應(yīng)度函數(shù)值為: 19.0
第 485 次迭代后，最小適應(yīng)度函數(shù)值為: 18.5
......
第 500 次迭代后暴构，最小適應(yīng)度函數(shù)值為: 18.5
當(dāng)Dp為 3 時(shí)跪呈，最小適應(yīng)度函數(shù)值為: 18.5
當(dāng)Dp為 3 時(shí)，最優(yōu)序列為:
[11. 14. 12. 15. 18. 13. 19. 21. 17. 8. 7. 16. 20. 9. 10. 5. 6. 1. 3. 2. 4.
- 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[Finished in 33.1s]
- 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
拆卸步驟：
