加密存储
之前写在另⼀个账号上，结果那个账号登不上去了…于是我copy过来了。原⽂链接：
但是原⽂代码有⼀些错误，所以直接看这篇就好了
⼀、遗传算法概念及基本步骤
在问题正式开始前，先简单介绍⼀下遗传算法。
遗传算法借⽤了⽣物遗传学的思想，以及⾃然界中的“物竞天择，适者⽣存”原则，将问题的解表⽰成“染⾊体”通过模拟⾃然选择、交叉、变异等操作，实现个体适应度的提⾼，不断迭代，逐步寻最优解(或次优解)。遗传算法在求解问题时，从⼀组随机产⽣的初始种开始搜索。种中⼀个个体(individual)表⽰问题的⼀个解，称为染⾊体(chromosome)。种通过连续的迭代进⾏进化，每⼀次迭代操作产⽣⼀代(generation)。在每⼀代中⽤适应度函数(fitnessfunction)或⽬标函数(objective function)对每个个体进⾏评价(evaluation)适应度值⾼的个体被选中的概率⾼。迭代过程的下⼀代称为⼦代(offspring)，通过选择(selection)交叉(crossover)变异(mutation)等遗传算⼦产⽣⼦代。遗传算法有五个基本要素：编码和解码；种初始化⽅法；适应度函数；遗传算⼦(主要包括选择、交叉、变异等)；遗传参数设置(种规模、遗传算⼦的概率等)等。
假设P表⽰种规模,t表⽰当前代,P(t)和C(t)表⽰第t代的⽗代和⼦代，那么基本的遗传算法执⾏步骤如下：
步骤1：按照⼀定的初始化⽅法产⽣初始种P(t)t=0。
步骤2：评价种P(t)计算每个个体的适应度值。
步骤3：判断是否满⾜终⽌条件，如果满⾜则输出结果；否则转步骤4。
步骤4 ：按照选择、交叉、变异等遗传算⼦产⽣⼦代C(t)。
步骤5：P(t)=C(t)转步骤2t=t+1。
图1所⽰为基本遗传算法的流程框图。
图1
⼆、柔性作业车间调度问题（FJSP）
柔性作业车间问题即FJSP问题，描述如下：n个⼯件（J1，J2，……，Jn）要在m台机器（M1，M2，……，Mm）上加⼯，每个⼯件包含⼀道或多道⼯序，⼯序顺序是预先确定的，每道⼯序可以在不同的机器上加⼯，⼯序的加⼯时间随加⼯机器的不同⽽不同；调度⽬标是为每道⼯序选择最合适的机器，确定每台机器上各道⼯序的最佳加⼯顺序及开⼯时间，使整个系统的某些性能指标达到最优。因此，柔性作业车间调度问题包含两个⼦问题：确定各⼯件的加⼯机器(机器选择⼦问题)和确定各个机器上的加⼯先后顺序(⼯序排序⼦问题)。 此外，在加⼯过程中还需要满⾜下⾯的约束条件：
(1)同⼀台机器在某⼀时刻只能加⼯⼀个⼯件。
(2)同⼀⼯件的同⼀道⼯序在同⼀时刻只能被⼀台机器加⼯。
(3)每个⼯件的每道⼯序⼀旦开始，加⼯便不能中断。
(4)不同⼯件之间具有相同的优先级。
(5)不同⼯件的⼯序之间没有先后约束，同⼀⼯件的⼯序之间有先后约束。
(6)所有⼯件在零时刻都可以被加⼯。
FJSP可以分为完全柔性车间作业问题（T-FJSP）和部分柔性车间作业问题（P-FJSP），在T-FJSP中，所有⼯件的每⼀道⼯序都可以在每⼀台机器上进⾏加⼯，⽽P-FJSP中，⾄少存在⼀道⼯序的加⼯机器只是所有机器中的某⼏台。为了更好的理解，放图。图2为T-FJSP，图3为P-FJSP。
图2
图3
管三、FJSP的染⾊体编码
染⾊体编码就是将问题的解⽤染⾊体的形式表达出来，这也是遗传算法的关键。所编的码必须利于之后选择交叉变异过程的进⾏。在前⾯已经讲到，柔性作业车间调度问题包含两个⼦问题：确定各⼯件的加⼯机器(机器选择⼦问题)和确定各个机器上的加⼯先后顺序(⼯序排序⼦问题)。我们将其简称为机器选择（machine selection，MS）和⼯序排序（operations sequencing，OS）。以此为基础，进⾏染⾊体编码。见图4
图4
3.1机器选择部分（MS）和⼯序选择部分（OS）
本来想分开写，因为图是⼀起的，所以也⼀起写了，见图5。
机器选择部分的编码⽅式：
每个⼯件的每道⼯序按顺序排列，⽐如第⼀个⼯件的第⼀道⼯序为O11，第n个⼯件的m道⼯序为Onm。按顺序排列：
O11,O12,O21,O22,O23……每个框代表的是每个⼯序所选择的机器，如第⼀个框代表的是O择的机器。框框⾥的数字则代表：此道⼯序能够选择的机器⾥的第⼏个机器。⽐如O11能够加⼯的机器为M1、M2、M3、M4、M5,4代表为这五台机器⾥的第四台机器，为
M4，O12⼯序能够加⼯的机器为M2和M4，1则代表这两台机器⾥的第⼆台机器，为M2。以此⽣成MS这边的染⾊体。
⼯序排序部分的编码⽅式：
见图5右半部分，数字⼏则代表为第⼏个⼯件，数字出现的次数为⼯序的顺序。即数字1第⼀次出现为第⼀个⼯件的第⼀道⼯序，数字1第⼆次出现为第⼀个⼯件的第⼆道⼯序，数字2第3次出现为第⼆个⼯件的第三道⼯序。
图5
四、FJSP初始化
为了能够后续得到更优质的解，初始解不随机⽣成，⽽是经过⼀些处理，这样能够更好更快地得到后续优质解。现对初始解进⾏三种⽅法的处理（按照⼀定概率设置）。分别为全局选择、局部选择和随机选择。时间有限今天就先写全局选择。
4.1全局选择
设置⼀个数组，长度和机器数相等，数组的顺序依次对应加⼯机器的顺序，每⼀位上的值对应相应机器上的加⼯时间。随机在⼯件集中选择⼀个⼯件，从当前⼯件的第1道⼯序开始，将当前⼯序的可选加⼯机器的加⼯时间加上数组中对应的时间。从中选择最短的时间作为当前⼯序的加⼯机器，并且将数组更新，即把被选择的加⼯机器的加⼯时间加到数组中相应的位置上，以此类推，直到当前⼯件的所有⼯序的加⼯机器选择完毕后，然后再随机选择⼀个⼯件开始，直到所有⼯件的⼯序选择完毕为⽌。这样保证了最短加⼯机器先被选到⽽且保证了加⼯机器上的⼯作负荷平衡。 具体执⾏步骤如下：
步骤1：设置⼀个整型数组，长度等于机器总数m，依次为机器号顺序，数组对应机器[M1，M2，…Mm]上的总负荷。同时初始化数组中每⼀个元素值为零。
步骤2：随机从⼯件集中选择⼀个⼯件，同时选择当前⼯件的第1道⼯序。
步骤3：将当前⼯序的可选加⼯机器集中的加⼯机器的加⼯时间和数组中相应机器位置的时间数值相加，但不更新数组。
步骤4：从相加后的时间值中，选择最⼩的那台机器作为当前⼯序的加⼯机器将被选的机器在可选机器集中的顺序号设置为MS部分相应基因位的值。
步骤5：将当前被选择的加⼯机器的加⼯时间加到数组中相应位置机器的加⼯负荷中，同时更新数组作为下⼀次选择的依据。
步骤6：选择当前⼯件的下⼀道⼯序，重复执⾏步骤3到步骤5，直到当前⼯件的所有⼯序的加⼯机器选择完毕为⽌。
步骤7：从⼯件集中除去已被选择的⼯件，从剩下的⼯件集中随机选择⼀个⼯件，同时选择当前⼯件的第1道⼯序，重复执⾏步骤3到步骤6，直到⼯件集中的所有⼯件被选择完毕为⽌。
以图3所⽰P-FJSP为例，假设第⼀次随机选择到的加⼯⼯件是⼯件J1，第⼆次选择⼯件J2，则前四道⼯序的执⾏过程如图6所⽰。
图6
4.2 局部选择
局部选择同全局选择原理上基本⼀致，但是每次对⼀个⼯件选择完毕时，数组需要重新设置为0，且不存在随机选择⼯件，直接看⼀下具体步骤：
步骤1：设置⼀个整型数组，长度等于机器总数m，依次为机器号顺序，数组对应机器[M1，M2…Mm]上的总负荷。同时初始化数组中每⼀个元素值为零。
步骤2：选择⼯件集中的第1个⼯件，同时选择当前⼯件的第1道⼯序。
步骤3：将当前⼯序的可选加⼯机器集中的加⼯机器的加⼯时间和数组中相应机器位置的时间数值相加，但不更新数组。
步骤4：从相加后的时间值中，选择最⼩的那台机器作为当前⼯序的加⼯机器，将被选的机器在可选机器集中的顺序号设置为MS部分相应基因位的值。
步骤5：将当前被选择的加⼯机器的加⼯时间加到数组中相应位置机器的加⼯负荷中，同时更新数组作为下⼀次选择的依据。
步骤6：选择当前⼯件的下⼀道⼯序，重复执⾏步骤3到步骤5，直到当前⼯件的所有⼯序的加⼯机器选择完毕为⽌。
步骤7：将数组中的每⼀位元素的值重新设置为零。
速记教程步骤8：从⼯件集中除去已被选择的⼯件，选择⼯件集中下⼀个⼯件，同时选择当前⼯件的第⼀道⼯序，重复执⾏步骤3到步骤7，直到⼯件集中的所有⼯件被选择完毕为⽌。
以图3所⽰P-FJSP为例，依次选择⼯件J1和J2，执⾏过程如图7所⽰。
图7
4.3 随机选择
为了保证初始种的多样性，初始种应分散于解空间。⼀部分种的机器选择部分采⽤随机初始化⽅法。RS与GS、LS的区别主要在于每⼀个基因位上的数字（即⼯序可选的机器号）是随机产⽣的。具体步骤如下：
步骤1：选择⼯件集中的第1个⼯件，同时选择当前⼯件的第1道⼯序。
步骤2：在[1，m]区间内随机产⽣⼀个数（m为对应⼯序可选择的机器数），即从当前⼯序的可选加⼯机器集中随机选择⼀个机器；同时将产⽣的随机数设置为MS染⾊体部分相应基因位的值。
步骤3：选择当前⼯件的下⼀道⼯序，执⾏步骤2，直到当前⼯件的所有⼯序的加⼯机器选择完毕为⽌。
步骤4：选择⼯件集中的下⼀个⼯件，重复执⾏步骤2到步骤3，直到⼯件集中的所有⼯件被选择完毕为⽌。
每个染⾊体的OS部分采⽤随机的⽅法⽣成。
4.4初始化代码
代码思路基本已经写在每⼀步的代码解释⾥了
墨水生产import numpy as np
import random
class Encode:
def __init__(self,Matrix,Pop_size,J,J_num,M_num):
self.Matrix = Matrix #⼯件各⼯序对应的机器加⼯时间矩阵
self.GS_num = int(0.6*Pop_size) #全局选择初始化⽣成的种数量
人体穴位模型self.LS_num = int(0.2*Pop_size) #局部选择初始化⽣成的种数量
self.RS_num = int(0.2*Pop_size) #随机选择初始化⽣成的种数量
self.J = J #各⼯件对应的⼯序数量
侧安全气囊self.J_num = J_num
self.M_num = M_num
self.Len_Chromo = 0
for i in J.values():
self.Len_Chromo += i #计算⼯序长度（如第⼀个⼯件有五道⼯序，第⼆个⼯件有⼗道⼯序，则长度为15）
def OS_List(self): #⽣成⼯序排列部分
OS_list = []
for key,value in self.J.items():
OS_add = [key for j in range(value)]
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议