基于遗传算法的复杂产品拆卸序列规划

本文主要参考张秀芬等人的《支持复杂产品并行拆卸序列规划的遗传算法》。
文章摘要如下：
　　为高效求解复杂产品的并行拆卸序列规划问题, 提出基于遗传算法的复杂产品并行拆卸序列规划方法. 针对并行拆卸序列规划问题中拆卸序列长度和每步拆卸零部件个数不确定的特点, 提出并行序列染色体编码方法, 分别将拆卸单元序列和拆卸步长作为染色体的前段和后段, 以此表示一个拆卸序列. 基于该染色体编码, 采用拆卸混合图描述产品零部件间装配约束关系和拆卸优先级, 并导出拆卸约束矩阵和邻接矩阵, 由矩阵随机获取可行的初始染色体种群; 将基本拆卸时间和不可行拆卸惩罚因子作为优化目标来构建适应度函数, 确保最优解的可行性; 在初始染色体种群的基础上, 适应度函数最小为优化目标, 通过遗传、交叉和变异遗传算子实现并行拆卸序列的优化. 最后通过实例验证了该方法的可行性和实用性.
大致的想法就是通过遗传算法对找出一个最优的拆解方式，使得整个部件的拆卸耗时最短。
１.首先确定染色体编码方式：

并行序列染色体编码方案.png

给出一个示例：

并行序列染色体编码示例.png

2.然后是初始化种群，其步骤如下：

初始化步骤.png

以上两步的代码如下：

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=[]
            #如果某一个零件没有前置拆卸零件，       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)
            #如果备选零件数小于拆卸并行度，则将所有的零件加入一个基因中
            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#前半部分放零件编号
            Species[m,sn]=sample_num#后面放并行长度
            st=st+sample_num#更新位置
            sn=sn+1
            
            #如果已经加入乐备选，则将原来的矩阵进行更新，避免下次重复选择
            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.确定适应度函数：

适应度函数.png

#计算适应度值
def GA_fitness(Specie):
   i=N;#染色体的拆卸步长基因序号,从22到43
   st=0;#染色体的拆卸零件基因序号，从0到21
   Total_Spends=0#每个序列的拆卸时间总和

   while int(Specie[i])!=0:#从染色体的第N=22个基因片段开始，只要执行步长不是0，就一直执行计算
       spend=[]#保存每组并行节点的拆卸时间
       num=int(Specie[i])#将拆卸步长强制转化为整型
       for j in range(st,st+num):#执行循环操作，将每个并行节点的拆卸时间保存进列表spend
           spend.append(Spends[int(Specie[j])-1])
       max_spend=max(spend)#找出列表中最大值，即并行操作中最耗时的一个拆卸
       Total_Spends=Total_Spends+max_spend#总的拆卸时长等于每个并行拆卸中最大时间之和，见文中适应度函数前半部分
       i=i+1#进行下一个拆卸步长
       st=st+num#拆卸零件同步进行更新

   P=0#惩罚项初始化为0，
   Wm_temp=copy.deepcopy(Wm)#对约束矩阵进行深度拷贝
   #判断进化过程中的解是否可行
   for j in range(0,N):
       Wmt=Wm_temp.T#对约束矩阵进行转置操作，便于通过判断列是否全为0，来判断是否为可行解
       num=int(Specie[j])-1#约束下标=零件序号-1
       #如果权重矩阵中当前零件对应的行全为0，则将原约束矩阵中对应列全置为1，
       #便于下一个拆卸操作的判断，这里稍微有点绕，需要想清楚原理
       if (Wmt[num,:]==0).all():
           Wm_temp[num,:]=0
       #如果权重矩阵中当前零件对应的行不全为0，意思是当前拆卸的零件还有前置依赖零件没有拆除
       #因此，该拆卸不可能正常进行，因此这个解是不可行的，将惩罚项设为1，直接跳出循环
       else:
           P=1
           break
   #综合以上两部分，返回适应度函数值，见文章第4页左下角适应度函数公式
   return Total_Spends+200*P

4.遗传算法实现见论文2.6，代码实现如下：

#如果终止条件不满足，利用轮盘赌算法实现找出根据概率找出两个适应度较小的染色体
#轮盘赌方法
def RouletteWheelSelection(genetic_fitness_list):#genetic_fitness_list为第(1)步得到的适应度列表
    #计算适应度总和与每个适应度的比例，由于本文要求适应度越低越好，所以是反着来
    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
    #需要随机生成两个概率用于染色体选择
    prob1=random.random()
    prob2=random.random()
    #待选的两个染色体的在列表中位置
    selection1=0
    selection2=0

    #因为要选择两个染色体，所以要转两次，轮盘转起来啦，具体原理应该能看懂吧
    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.仿真示例：

零件爆炸图.png

拆卸混合图模型 .png

组件信息与编码表.png

参数初始化

import numpy as np
#参数初始化
Dp=3#拆卸并行度
N=22#节点个数
M=10#种群规模
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;

#每个零件拆卸时间
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]

执行算法：

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,"次迭代后，最小适应度函数值为:",min(GA_fitness_list))
print("当Dp为",Dp,"时，最小适应度函数值为:",min(GA_fitness_list))
min_i=GA_fitness_list.index(min(GA_fitness_list))
best_specie=Species_inition[min_i]
print("当Dp为",Dp,"时，最优序列为:",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()

效果结果：
第 1 次迭代后，最小适应度函数值为: 20.5
第 2 次迭代后，最小适应度函数值为: 20.5
第 3 次迭代后，最小适应度函数值为: 20.5
第 4 次迭代后，最小适应度函数值为: 20.5
第 5 次迭代后，最小适应度函数值为: 20.5
第 6 次迭代后，最小适应度函数值为: 20.5
第 7 次迭代后，最小适应度函数值为: 20.5
第 8 次迭代后，最小适应度函数值为: 20.5
第 9 次迭代后，最小适应度函数值为: 20.5
第 10 次迭代后，最小适应度函数值为: 20.5
第 11 次迭代后，最小适应度函数值为: 20.5
第 12 次迭代后，最小适应度函数值为: 20.5
第 13 次迭代后，最小适应度函数值为: 20.5
第 14 次迭代后，最小适应度函数值为: 20.5
第 15 次迭代后，最小适应度函数值为: 20.5
第 16 次迭代后，最小适应度函数值为: 20.5
第 17 次迭代后，最小适应度函数值为: 20.0
第 18 次迭代后，最小适应度函数值为: 20.0
第 19 次迭代后，最小适应度函数值为: 20.0
第 20 次迭代后，最小适应度函数值为: 20.0
第 21 次迭代后，最小适应度函数值为: 19.0
......
第 484 次迭代后，最小适应度函数值为: 19.0
第 485 次迭代后，最小适应度函数值为: 18.5
......
第 500 次迭代后，最小适应度函数值为: 18.5
当Dp为 3 时，最小适应度函数值为: 18.5
当Dp为 3 时，最优序列为:
[11. 14. 12. 15. 18. 13. 19. 21. 17. 8. 7. 16. 20. 9. 10. 5. 6. 1. 3. 2. 4.

1. 1. 1. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
        [Finished in 33.1s]

拆卸步骤：

拆卸并行度为3时的最优规划结果