164 lines
5.4 KiB
Python
164 lines
5.4 KiB
Python
import itertools
|
||
import random
|
||
|
||
import numpy as np
|
||
|
||
from Decode import Decode
|
||
from Instance import *
|
||
|
||
|
||
class GA():
|
||
def __init__(self):
|
||
self.Pop_size = 500 # 种群数量
|
||
self.Pc = 0.8 # 交叉概率
|
||
self.Pm = 0.15 # 降低变异概率到0.15
|
||
self.Pv = 0.5 # 选择何种方式进行交叉的概率阈值
|
||
self.Pw = 0.95 # 选择何种方式进行变异的概率阈值
|
||
self.Max_Itertions = 100
|
||
|
||
# 适应度
|
||
def fitness(self, CHS, J, Processing_time, M_num, Len):
|
||
Fit = []
|
||
for i in range(len(CHS)):
|
||
d = Decode(J, Processing_time, M_num) # 实例化一个解码器，传入问题参数
|
||
Fit.append(d.decode(CHS[i], Len))
|
||
return Fit
|
||
|
||
def pmx_crossover(self, parent1, parent2, length):
|
||
if length <= 1:
|
||
return parent1.copy(), parent2.copy()
|
||
|
||
# 确保交叉区间[a, b]有效（a < b）
|
||
a = random.randint(0, length - 2)
|
||
b = random.randint(a + 1, length - 1)
|
||
|
||
child1 = parent1.copy()
|
||
child2 = parent2.copy()
|
||
|
||
# 建立映射表（parent1[a:b+1]与parent2[a:b+1]的对应关系）
|
||
map1 = {parent1[i]: parent2[i] for i in range(a, b + 1)} # p1→p2的映射
|
||
map2 = {parent2[i]: parent1[i] for i in range(a, b + 1)} # p2→p1的映射
|
||
|
||
# 处理child1：交叉区间外的元素替换
|
||
for i in range(length):
|
||
if i < a or i > b:
|
||
val = child1[i]
|
||
# 限制循环次数，避免无限循环（最多循环len(map1)次）
|
||
loop_count = 0
|
||
max_loop = len(map1)
|
||
while val in map1 and map1[val] in parent1[a:b + 1] and loop_count < max_loop:
|
||
val = map1[val]
|
||
loop_count += 1
|
||
child1[i] = map1.get(val, val) # 若超出循环次数，直接使用当前val
|
||
|
||
# 处理child2：交叉区间外的元素替换
|
||
for i in range(length):
|
||
if i < a or i > b:
|
||
val = child2[i]
|
||
loop_count = 0
|
||
max_loop = len(map2)
|
||
while val in map2 and map2[val] in parent2[a:b + 1] and loop_count < max_loop:
|
||
val = map2[val]
|
||
loop_count += 1
|
||
child2[i] = map2.get(val, val)
|
||
|
||
return child1, child2
|
||
|
||
# 机器部分交叉
|
||
def machine_cross(self, CHS1, CHS2, T0):
|
||
"""
|
||
:param CHS1: 基因1
|
||
:param CHS2: 基因2
|
||
:param T0: 工序总数
|
||
:return: 交叉后的基因
|
||
"""
|
||
OS1, MS1 = CHS1[:T0], CHS1[T0:]
|
||
OS2, MS2 = CHS2[:T0], CHS2[T0:]
|
||
|
||
# 随机选择交叉位置
|
||
T_r = list(range(T0))
|
||
random.shuffle(T_r)
|
||
r = random.randint(1, T0 // 2) # 交叉部分长度
|
||
R = T_r[:r]
|
||
|
||
# 交换机器选择部分
|
||
for i in R:
|
||
MS1[i], MS2[i] = MS2[i], MS1[i]
|
||
|
||
return np.hstack((OS1, MS1)), np.hstack((OS2, MS2))
|
||
|
||
# 工序部分交叉（使用PMX交叉）
|
||
def operation_cross(self, CHS1, CHS2, T0, J_num):
|
||
OS1 = list(CHS1[T0:2 * T0]) # 确保转换为列表
|
||
OS2 = list(CHS2[T0:2 * T0])
|
||
MS1 = CHS1[0:T0].copy()
|
||
MS2 = CHS2[0:T0].copy()
|
||
|
||
# 调用修复后的PMX交叉
|
||
new_os1, new_os2 = self.pmx_crossover(OS1, OS2, T0)
|
||
|
||
CHS1 = np.hstack((MS1, new_os1))
|
||
CHS2 = np.hstack((MS2, new_os2))
|
||
return CHS1, CHS2
|
||
|
||
# 机器部分变异（仅在可用机器集中选择）
|
||
def machine_variation(self, CHS, O, T0, J):
|
||
"""
|
||
:param CHS: 基因
|
||
:param O: 加工时间矩阵
|
||
:param T0: 工序总数
|
||
:param J: 各工件加工信息
|
||
:return: 变异后的基因
|
||
"""
|
||
OS = CHS[:T0]
|
||
MS = CHS[T0:]
|
||
|
||
# 确定变异位置数量
|
||
r = random.randint(1, max(1, T0 // 10)) # 最多变异10%的位置
|
||
positions = random.sample(range(T0), r)
|
||
|
||
for pos in positions:
|
||
# 找到该位置对应的工件和工序
|
||
site = 0
|
||
job = -1
|
||
op = -1
|
||
for k, v in J.items():
|
||
if site + v > pos:
|
||
job = k - 1 # 转换为0索引
|
||
op = pos - site
|
||
break
|
||
site += v
|
||
|
||
# 获取该工序的可用机器
|
||
D = O[job][op]
|
||
available_machines = [k for k, val in enumerate(D) if val != 9999]
|
||
if len(available_machines) <= 1:
|
||
continue # 只有一个可用机器时不变异
|
||
|
||
# 随机选择一个不同的可用机器
|
||
current_idx = MS[pos]
|
||
current_machine = available_machines[current_idx]
|
||
new_machine = random.choice([m for m in available_machines if m != current_machine])
|
||
MS[pos] = available_machines.index(new_machine)
|
||
|
||
return np.hstack((OS, MS))
|
||
|
||
# 工序部分变异
|
||
def operation_variation(self, CHS, T0, J_num, J, O, M_num):
|
||
"""
|
||
:param CHS: 基因
|
||
:param T0: 工序总数
|
||
:param J_num: 工件总数
|
||
:param J: 各工件加工信息
|
||
:param O: 加工时间矩阵
|
||
:param M_num: 机器总数
|
||
:return: 变异后的基因
|
||
"""
|
||
OS = list(CHS[:T0])
|
||
MS = CHS[T0:]
|
||
|
||
# 随机选择两个位置交换
|
||
i, j = random.sample(range(T0), 2)
|
||
OS[i], OS[j] = OS[j], OS[i]
|
||
|
||
return np.hstack((OS, MS)) |