化工网站制作,广州市安全平台,响应式模板,立创电子元器件商城官网省流#xff1a;这是一个错误的代码备份#xff0c;如果你需要可以直接运行的完整代码#xff0c;请移步GitHub。
本以为手搓了一个单机调度和并行机调度的遗传算法#xff0c;就可以尝试写开放车间的遗传算法了#xff0c;结果手搓了两天#xff0c;开始作业时间和结束…省流这是一个错误的代码备份如果你需要可以直接运行的完整代码请移步GitHub。
本以为手搓了一个单机调度和并行机调度的遗传算法就可以尝试写开放车间的遗传算法了结果手搓了两天开始作业时间和结束作业时间的计算还是没整明白。
后来参考了GitHub上一个作业车间调度问题的遗传算法代码发现哪有我这么写代码的人家都是把各个对象和方法封装成一个一个的类所谓的面向对象编程我这写的是啥玩意。。。
所以决定这个算法就不纠缠了因为继续按照我这样的逻辑写下去基本写不通我菜你们要是能走通踢我还不如重新捡起我面向对象的思想从一开始就做好属性和功能的封装。
先把代码搁这备个份。
说明除了cal_start_and_finish_time函数外别的函数都是对的改一下编码就可以直接用不过这几个函数都挺简单的应该没人用得上代码的编码方式我是参考的Genetic Algorithms for Open Shop Scheduling and Re-Scheduling这篇论文其实这种编码方式我暂时看不出能有啥出类拔萃的效果单纯因为它不是主流的编码方式又比较好理解所以做了一个尝试。
GitHub上大佬写的作业车间传统遗传算法代码我给看明白了争取尽量把开放车间的代码封装出来。
以上又是觉得自己是个大菜逼的一天5555。
import random
import numpy as np
import matplotlib.pyplot as plt
import copy# TODO: 暂时看不懂这种有工序约束的多机调度问题怎么编码这个是作业车间的先看开放车间问题
# # 机器约束矩阵10个工件5台机器
# machine_constraint_matrix [[2, 1, 4, 2, 1, 2, 4, 3, 4, 5],
# [1, 4, 5, 1, 4, 3, 5, 1, 2, 4],
# [5, 5, 2, 5, 3, 5, 2, 2, 5, 3],
# [4, 3, 3, 3, 2, 1, 3, 4, 1, 2],
# [3, 2, 1, 4, 5, 4, 1, 5, 3, 1]]
# # 加工时间矩阵
# pro_time_matrix [[53, 21, 12, 55, 83, 92, 93, 60, 44, 96],
# [21, 71, 42, 77, 19, 54, 87, 41, 49, 75],
# [34, 26, 31, 66, 64, 43, 87, 38, 98, 43],
# [55, 52, 39, 77, 34, 62, 69, 24, 17, 79],
# [95, 16, 98, 79, 37, 79, 77, 83, 25, 77]]# m台相同的机器n个工件每个工件有1道工序可任意选择1台机器进行加工# 定义遗传算法参数
POP_SIZE 100 # 种群大小
MAX_GEN 100 # 最大迭代次数
CROSSOVER_RATE 0.7 # 交叉概率
MUTATION_RATE 0.2 # 变异概率def sort_by_id(id, sequence):# 根据id对sequence进行排序new_sequence sequence[:]for i in range(len(id)):sequence[i] new_sequence[id[i]]# 随机生成初始种群这里用一个元组表示工件和机器的分配关系如元组(0,1)表示编号为1的工件在编号为0的机器上加工工件和机器编码都是从0开始
def get_init_pop(pop_size):pop []job [(m, n) for m in range(machine_num) for n in range(len(job_id))]for _ in range(pop_size):random.shuffle(job)pop.append(job[:])return pop# TODO: 开始时间和结束时间计算有问题这个函数废了
# 将输入的一维job进行二维转换计算start_time和finish_time
def cal_start_and_finish_time(job):# 按照输入的工序进行排序sorted_job sorted(job, keylambda x: x[0]) # 按照设备排序sorted_pro_time [pro_times[j[0]][j[1]] for j in sorted_job] # 对应的加工时间# 转换成二维列表sorted_job [sorted_job[i:i len(job_id)] for i in range(0, len(sorted_job), len(job_id))]sorted_pro_time [sorted_pro_time[i:i len(job_id)] for i in range(0, len(sorted_pro_time), len(job_id))]# 对每台机器的总加工时间进行加和用于排序# 这里直接规定当各机器无法同时开工时选择总加工时间最长的机器最先开工start_seq [i[0] for i in sorted(enumerate(pro_times), keylambda x: sum(x[1]), reverseTrue)] # 机器开始加工的顺序start_time [[] for _ in range(len(sorted_job))]finish_time [[] for _ in range(len(sorted_job))]# 第一台开工的机器的第一个工件的start_time和finish_timestart_time[start_seq[0]].append(arr_times[sorted_job[start_seq[0]][0][1]])finish_time[start_seq[0]].append(start_time[start_seq[0]][0] sorted_pro_time[start_seq[0]][0])# 单独先把第一个开工的机器的start_time和finish_time计算出来for j in range(1, len(pro_times[0])):start_time[start_seq[0]].append(max(finish_time[start_seq[0]][-1], arr_times[sorted_job[start_seq[0]][j][1]]))finish_time[start_seq[0]].append(start_time[start_seq[0]][j] sorted_pro_time[start_seq[0]][j])# 计算每台机器的第一个工件的开始加工时间for i in range(1, len(start_seq)):# 一个工件不能同时在两台机器加工start_time[start_seq[i]].append(-1)for k in range(i):if sorted_job[start_seq[i]][0][1] sorted_job[start_seq[k]][0][1]:start_time[start_seq[i]][-1] finish_time[start_seq[k]][0]elif k i - 1 and start_time[start_seq[i]][-1] -1:start_time[start_seq[i]][-1] arr_times[sorted_job[start_seq[i]][0][1]]finish_time[start_seq[i]].append(start_time[start_seq[i]][0] sorted_pro_time[start_seq[i]][0])# 计算其他行列for i in range(1, len(start_seq)):for j in range(1, len(pro_times[0])):start_time[start_seq[i]].append(-1)for k in range(i):# 写着写着突然发现不对还是需要判断前边两台机器上正在加工的工件是不是当前机器即将要加工的工件# 感觉这里把自己绕进去了实际上当某个工件在当前机器上的加工时间特别大可能是其在别的机器上加工时间的几倍或者是别的工件加工时间之和的时候这个if判断还要向前或者向后搜索很多轮# 但是如果真有这样一道工序存在应该不需要什么算法直接可以看出结果所以这里只搜索相邻的两轮# TODO: but逻辑还是欠严谨这是一段失败的代码或许证明这思路就不行先到这里吧麻了if finish_time[start_seq[i]][j - 1] finish_time[start_seq[k]][j - 1]:if sorted_job[start_seq[i]][j][1] sorted_job[start_seq[k]][j - 1][1]:start_time[start_seq[i]][-1] max(finish_time[start_seq[i]][-1],finish_time[start_seq[k]][j - 1])elif k i - 1 and start_time[start_seq[i]][-1] -1:start_time[start_seq[i]][-1] max(finish_time[start_seq[i]][-1],arr_times[sorted_job[start_seq[i]][j][1]])elif finish_time[start_seq[k]][j - 1] finish_time[start_seq[i]][j - 1] finish_time[start_seq[k]][j]:if sorted_job[start_seq[i]][j][1] sorted_job[start_seq[k]][j][1]:start_time[start_seq[i]][-1] max(finish_time[start_seq[i]][-1], finish_time[start_seq[k]][j])elif k i - 1 and start_time[start_seq[i]][-1] -1:start_time[start_seq[i]][-1] max(finish_time[start_seq[i]][-1],arr_times[sorted_job[start_seq[i]][j][1]])else:start_time[start_seq[i]][-1] max(finish_time[start_seq[i]][-1],arr_times[sorted_job[start_seq[i]][j][1]])finish_time[start_seq[i]].append(start_time[start_seq[i]][j] sorted_pro_time[start_seq[i]][j])return sorted_job, sorted_pro_time, start_time, finish_time# 计算染色体的适应度makespan 以最小化交货期延时为目标函数这里计算的是交货期总延时时间
def fitness(job):sorted_job, sorted_pro_time, start_time, finish_time cal_start_and_finish_time(job)# 计算适应度目标函数是最小化总延货期max_finish_time [] # 记录每个工件在各机器上的最后的完工时间for k in range(len(job_id)):# 定位定位到sorted_job中所有元组的第二个元素为i的索引indices [(i, j) for i, row in enumerate(sorted_job) for j, (x, y) in enumerate(row) if y k]max_ft 0for id in indices:max_ft finish_time[id[0]][id[1]] if finish_time[id[0]][id[1]] max_ft else max_ftmax_finish_time.append(max_ft)delay_time [max(mf - d, 0) for mf, d in zip(max_finish_time, deadlines)] # 总延货期# print(sorted_job,sorted_job)# print(sorted_pro_time,sorted_pro_time)# print(start_time,start_time)# print(finish_time,finish_time)# print(delay_time,delay_time)# print(sum(delay_time),sum(delay_time))return sum(delay_time)# 选择父代这里选择POP_SIZE/2个作为父代
def selection(pop):fitness_values [1 / fitness(job) for job in pop] # 以最小化交货期总延时为目标函数这里把最小化问题转变为最大化问题total_fitness sum(fitness_values)prob [fitness_value / total_fitness for fitness_value in fitness_values] # 轮盘赌这里是每个适应度值被选中的概率# 按概率分布prob从区间[0,len(pop))中随机抽取size个元素不允许重复抽取即轮盘赌选择selected_indices np.random.choice(len(pop), sizePOP_SIZE // 2, pprob, replaceFalse)return [pop[i] for i in selected_indices]# 交叉操作 这里是单点交叉
def crossover(job_p1, job_p2):cross_point random.randint(1, len(job_p1) - 1)job_c1 job_p1[:cross_point] [gene for gene in job_p2 if gene not in job_p1[:cross_point]]job_c2 job_p2[:cross_point] [gene for gene in job_p1 if gene not in job_p2[:cross_point]]return job_c1, job_c2# 变异操作因为元组是不可变类型这里采取的变异方式是随机交换两个点
def mutation(job):while True:index1 random.randint(0, len(job) - 1)index2 random.randint(0, len(job) - 1)if index1 ! index2:breaktemp job[index1]job[index1] job[index2]job[index2] tempreturn job# 主遗传算法循环
# 以最小化延迟交货时间为目标函数
def GA(): # 工件加工顺序是否为无序best_job [(m, n) for m in range(machine_num) for n in range(len(job_id))] # 初始化最佳个体best_makespan fitness(best_job) # 获得最佳个体的适应度值# 创建一个空列表来存储每代的适应度值fitness_history [best_makespan]pop get_init_pop(POP_SIZE)for _ in range(1, MAX_GEN 1):pop selection(pop) # 选择new_population []while len(new_population) POP_SIZE:parent1, parent2 random.sample(pop, 2) # 不重复抽样2个if random.random() CROSSOVER_RATE:child1, child2 crossover(parent1, parent2) # 交叉new_population.extend([child1, child2])else:new_population.extend([parent1, parent2])pop [mutation(job) if random.random() MUTATION_RATE else job for job in new_population] # 变异best_gen_job min(pop, keylambda x: fitness(x))best_gen_makespan fitness(best_gen_job) # 每一次迭代获得最佳个体的适应度值# print(job_id)# print(best_gen_job)# print(best_gen_makespan,best_makespan,best_gen_makespan best_makespan)if best_gen_makespan best_makespan: # 更新最小fitness值best_makespan best_gen_makespanbest_job copy.deepcopy(best_gen_job)fitness_history.append(best_makespan) # 把本次迭代结果保存到fitness_history中用于绘迭代曲线# print(best_job)# print(best_makespan)# print()# 绘制迭代曲线图plt.plot(range(MAX_GEN 1), fitness_history)plt.xlabel(Generation)plt.ylabel(Fitness Value)plt.title(Genetic Algorithm Convergence)plt.show()return best_job, best_makespandef plot_gantt(job):# 准备一系列颜色colors [blue, yellow, orange, green, palegoldenrod, purple, pink, Thistle, Magenta, SlateBlue,RoyalBlue, Cyan, Aqua, floralwhite, ghostwhite, goldenrod, mediumslateblue, navajowhite,moccasin, white, navy, sandybrown, moccasin]job_colors random.sample(colors, len(job) // machine_num)# 计算每个工件的开始时间和结束时间sorted_job, sorted_pro_time, start_time, finish_time cal_start_and_finish_time(job)id [[0] * len(sorted_job[0]) for _ in range(machine_num)]job_color [[0] * len(sorted_job[0]) for _ in range(machine_num)]for i in range(machine_num):for j in range(len(id[0])):id[i][j] sorted_job[i][j][1]job_color[i][j] job_colors[id[i][j]]print(sorted_job, sorted_job)print(sorted_pro_time, sorted_pro_time)print(start_time:, start_time)print(finish_time:, finish_time)# 创建图表和子图plt.figure(figsize(12, 6))# 绘制工序的甘特图for i in range(len(start_time)):for j in range(len(start_time[i])):plt.barh(i, finish_time[i][j] - start_time[i][j], height0.5, leftstart_time[i][j], colorjob_color[i][j],edgecolorblack)plt.text(x(start_time[i][j] finish_time[i][j]) / 2, yi, sid[i][j], fontsize14)# 设置纵坐标轴刻度为机器编号machines [fMachine {i} for i in range(len(start_time))]plt.yticks(range(len(machines)), machines)# 设置横坐标轴刻度为时间# start min([min(row) for row in start_time])start 0end max([max(row) for row in finish_time])plt.xticks(range(start, end 1))plt.xlabel(Time)# 图表样式设置plt.ylabel(Machines)plt.title(Gantt Chart)# plt.grid(axisx)# 自动调整图表布局plt.tight_layout()# 显示图表plt.show()if __name__ __main__:# n个工件每个工件都需要到m台不同机器上各加工一次加工顺序任意每台机器上的加工时间已知job_id [0, 1, 2, 3, 4, 5, 6, 7, 8] # 工件编号pro_times [[4, 7, 6, 5, 8, 3, 5, 5, 10],[7, 10, 1, 5, 7, 5, 8, 7, 3],[7, 1, 8, 9, 3, 7, 8, 6, 1]] # 加工时间arr_times [3, 2, 4, 5, 3, 2, 1, 8, 6] # 到达时间deadlines [46, 35, 49, 41, 40, 48, 49, 37, 36] # 交货期machine_num 3 # 3台完全相同的并行机编号为0,1,2best_job, best_makespan GA()print(最佳调度顺序和分配, best_job)print(最小交货期延时时间, best_makespan)plot_gantt(best_job)# job_id [0, 1, 2, 3] # 工件编号# pro_times [[4, 7, 6, 5],# [7, 10, 1, 5],# [7, 1, 8, 9]] # 加工时间# arr_times [3, 2, 4, 5] # 到达时间# deadlines [6, 5, 9, 11] # 交货期# machine_num 3 # 3台完全相同的并行机编号为0,1,2# # best_job, best_makespan GA()# # print(最佳调度顺序和分配, best_job)# print(最小交货期延时时间, best_makespan)# # plot_gantt(best_job)# job [(1, 2), (0, 2), (1, 1), (2, 2), (2, 0), (0, 0), (0, 1), (0, 3), (1, 0), (2, 1), (2, 3), (1, 3)]# cal_start_and_finish_time(job)# plot_gantt(job)
