毕设项目-混合约束的流水车间调度问题python项目源码(多种算法+代码详细注释).zip

import datetime import os import sys import time import numpy as np from modele.factory import Factory import random class GeneticFactory(Factory): def __init__(self, cross_probability=0.7, mutations_probability=0.1): super().__init__() # 遗传种群 self.orders = [] self.orders_mid = [] self.orders_end = [] # 遗传种群的解 self.results = [] self.results_mid = [] self.results_end = [] # 交叉概率 self.cross_probability = cross_probability # 变异概率 self.mutations_probability = mutations_probability # 最终结果 self.genetic_order = None self.genetic_result = None self.genetic_time = None def genetic_complete(self, epochs=50): self.clear_results() start_time = time.time() # 随机生成 n 个（工件数量）初始个体 作为初始种群 job_num = len(self.jobs) self.generate_orders(job_num, job_num) # 从小到大排序 self.__synchronous_sort(self.orders, self.results, False) # 重复的epoch次数 重复100次就终止 repeat_epochs = 0 last_epoch_result = 0 for epoch in range(epochs): for _ in range(job_num): # 交叉 if self.__try_trigger(self.cross_probability) is True: # 从orders中随机选取两个序列 orders_num = len(self.results) indexs = [idx for idx in range(orders_num)] weights = [(orders_num - idx) / orders_num for idx in range(orders_num)] idx1, idx2 = random.choices(indexs, weights, k=2) while idx1 == idx2: idx1, idx2 = random.choices(indexs, weights, k=2) child_order1, child_order2 = self.cross_order(self.orders[idx1], self.orders[idx2]) # 把新的结果添加到中间群落里 res1 = self.complete(child_order1) res2 = self.complete(child_order2) self.orders_mid.append(child_order1) self.orders_mid.append(child_order2) self.results_mid.append(res1) self.results_mid.append(res2) # 变异 if self.__try_trigger(self.mutations_probability) is True: # 从orders中随机选取一个序列，进行变异 orders_num = len(self.results) indexs = [idx for idx in range(orders_num)] weights = [1 / idx for idx in range(1, orders_num + 1)] idx = random.choices(indexs, weights)[0] # 四种变异都变一下 # 插入重排变异 ins_order, ins_res = self.insert_order(self.orders[idx]) self.orders_mid.append(ins_order) self.results_mid.append(ins_res) # 交换变异 mut_order = self.mutations_order(self.orders[idx]) mut_res = self.complete(mut_order) self.orders_mid.append(mut_order) self.results_mid.append(mut_res) # 相邻交换变异 exc_order = self.exchange_order(self.orders[idx]) exc_res = self.complete(exc_order) self.orders_mid.append(exc_order) self.results_mid.append(exc_res) # 倒置变异 rev_order = self.reverse_order(self.orders[idx]) rev_res = self.complete(rev_order) self.orders_mid.append(rev_order) self.results_mid.append(rev_res) # 计算 result 和 mid result中的序列完工时间，进行排序，取前job_num个作为新的种群，清空 mid # 把结果全放到mid中进行计算 orders_num = len(self.orders) for i in range(orders_num): self.orders_mid.append(self.orders[i]) self.results_mid.append(self.results[i]) # 对mid进行排序 self.__synchronous_sort(self.orders_mid, self.results_mid) # 取前面orders_num个放回 for i in range(orders_num): self.orders[i] = self.orders_mid[i] self.results[i] = self.results_mid[i] # 清空 mid self.orders_mid = [] self.results_mid = [] # 将最优结果存入end中 self.orders_end.append(self.orders[0]) self.results_end.append(self.results[0]) # 判断是否终止 if self.results[0] == last_epoch_result: repeat_epochs = repeat_epochs + 1 if repeat_epochs > 100: break else: last_epoch_result = self.results[0] repeat_epochs = 0 now = datetime.datetime.now() print("%s [%s] cost: %.2f s, epoch: %d, result: %d" % ( now.strftime('%Y-%m-%d %H:%M:%S'), self.filename, time.time() - start_time, epoch, self.results[0])) # 50个epoch完成后 从end中筛选出最小的 min_res = min(self.results_end) index = self.results_end.index(min_res) self.genetic_order = self.orders_end[index] self.genetic_result = self.results_end[index] self.genetic_time = time.time() - start_time print(self.results_end) def mutations_order(self, order): """ 变异，随机取两个位置进行交换 :param order: 原序列 :return: 变异后的序列 """ length = len(order) l = random.randint(0, length - 1) r = random.randint(0, length - 1) while l == r: r = random.randint(0, length - 1) mut_order = [item for item in order] mut_order[l], mut_order[r] = mut_order[r], mut_order[l] return mut_order def exchange_order(self, order): """ 随机选取两个相邻工件，交换前后顺序 :param order: 原序列 :return: 交换后的序列 """ length = len(order) i = random.randint(0, length - 2) exc_order = [item for item in order] exc_order[i], exc_order[i + 1] = exc_order[i + 1], exc_order[i] return exc_order def reverse_order(self, order): """ 随机选取两个工件，将这两道工件之间的顺序完全倒置 :param order: 原序列 :return: 倒置部分之后的序列 """ length = len(order) l = random.randint(0, length - 1) r = random.randint(0, length - 1) while l == r: r = random.randint(0, length - 1) if l > r: l, r = r, l rev_order = [item for item in order] while l < r: rev_order[l], rev_order[r] = rev_order[r], rev_order[l] l = l + 1 r = r - 1 return rev_order def insert_order(self, order): """ 从序列中选出一个工件 重新插入最合适的地方 :param order: 原序列 :return: 新序列，结果 """ length = len(order) temp = [item for item in order] # 从队列中取出1个工件，并重新选择地方插入放回 destroyed = temp.pop(random.randint(0, length - 1)) # 重新插入最佳位置 min_res = sys.maxsize min_idx = 0 # 每个工件都有 n 种插法 for idx in range(len(temp)): temp.insert(idx, destroyed) res = self.complete(temp) if res < min_res: min_res = res min_idx = idx # 返回原貌 temp.pop(idx) # 放入结果最小的位置