### NSGA-II 算法在车间调度中的应用 NSGA-II（Non-dominated Sorting Genetic Algorithm II）是一种高效的多目标优化算法，广泛应用于解决柔性作业车间调度问题（Flexible Job Shop Scheduling Problem, FJSP）。该算法通过遗传操作和非支配排序机制，在多个目标之间寻找最优解集，例如最小化生产时间、最大化资源利用率等。 在车间调度中，NSGA-II 的实现通常包括以下几个关键步骤： 1. **编码方案**：每个个体表示一种调度方案，通常采用工序排列或机器分配的方式进行编码。 2. **适应度评估**：计算个体的多个目标函数值，如最大完工时间（makespan）、总延迟时间等。 3. **选择机制**：使用非支配排序和拥挤度比较来选择下一代种群。 4. **交叉与变异**：设计适合问题特性的遗传算子，生成新的个体。 5. **局部搜索**：可结合局部搜索策略提高解的质量。 以下是一个简化的 NSGA-II 解决车间调度问题的 Python 代码示例，展示其基本框架： ```python import random import numpy as np # 定义个体类 class Individual: def __init__(self, schedule): self.schedule = schedule # 工序安排 self.makespan = 0 # 最大完工时间 self.cost = 0 # 成本或其他目标 self.rank = 0 # 非支配等级 self.crowding_distance = 0 def evaluate(self): # 模拟评估函数，实际应根据调度方案计算目标值 self.makespan = sum(self.schedule) % 100 + 100 self.cost = sum(self.schedule) % 50 + 50 # 初始化种群 def initialize_population(pop_size, chromosome_length): population = [] for _ in range(pop_size): schedule = random.sample(range(chromosome_length), chromosome_length) individual = Individual(schedule) individual.evaluate() population.append(individual) return population # 非支配排序 def fast_non_dominated_sort(population): fronts = [[]] S = [[] for _ in range(len(population))] n = [0] * len(population) for p in range(len(population)): for q in range(len(population)): if dominates(population[p], population[q]): S[p].append(q) elif dominates(population[q], population[p]): n[p] += 1 if n[p] == 0: fronts[0].append(p) i = 0 while fronts[i]: next_front = [] for p in fronts[i]: for q in S[p]: n[q] -= 1 if n[q] == 0: next_front.append(q) i += 1 fronts.append(next_front) return fronts[:-1] # 判断个体p是否支配q def dominates(p, q): p_better = (p.makespan < q.makespan and p.cost <= q.cost) or \ (p.makespan <= q.makespan and p.cost < q.cost) return p_better # 拥挤度计算 def calculate_crowding_distance(front, population): for individual in front: population[individual].crowding_distance = 0 for obj_index in [0, 1]: # 假设有两个目标函数 front.sort(key=lambda x: population[x].makespan if obj_index == 0 else population[x].cost) population[front[0]].crowding_distance = float('inf') population[front[-1]].crowding_distance = float('inf') max_val = getattr(population[front[-1]], 'makespan' if obj_index == 0 else 'cost') min_val = getattr(population[front[0]], 'makespan' if obj_index == 0 else 'cost') if max_val != min_val: for i in range(1, len(front) - 1): val_i_minus_1 = getattr(population[front[i - 1]], 'makespan' if obj_index == 0 else 'cost') val_i_plus_1 = getattr(population[front[i + 1]], 'makespan' if obj_index == 0 else 'cost') population[front[i]].crowding_distance += (val_i_plus_1 - val_i_minus_1) / (max_val - min_val) # 选择父代 def tournament_selection(population, k=2): participants = random.sample(population, k) best = min(participants, key=lambda x: (x.rank, -x.crowding_distance)) return best # 交叉操作 def crossover(parent1, parent2): point = random.randint(1, len(parent1.schedule) - 1) child_schedule = parent1.schedule[:point] + parent2.schedule[point:] return Individual(child_schedule) # 变异操作 def mutate(individual, mutation_rate=0.1): for i in range(len(individual.schedule)): if random.random() < mutation_rate: j = random.randint(0, len(individual.schedule) - 1) individual.schedule[i], individual.schedule[j] = individual.schedule[j], individual.schedule[i] individual.evaluate() # 主程序 def main(): pop_size = 50 generations = 100 chromosome_length = 10 # 工序数量 population = initialize_population(pop_size, chromosome_length) for gen in range(generations): offspring = [] for _ in range(pop_size // 2): parent1 = tournament_selection(population) parent2 = tournament_selection(population) child1 = crossover(parent1, parent2) child2 = crossover(parent2, parent1) mutate(child1) mutate(child2) offspring.extend([child1, child2]) combined_population = population + offspring fronts = fast_non_dominated_sort(combined_population) new_population = [] front_index = 0 while len(new_population) + len(fronts[front_index]) <= pop_size: calculate_crowding_distance(fronts[front_index], combined_population) new_population.extend(fronts[front_index]) front_index += 1 # 按拥挤度补充剩余个体 remaining = pop_size - len(new_population) if remaining > 0: calculate_crowding_distance(fronts[front_index], combined_population) fronts[front_index].sort( key=lambda x: combined_population[x].crowding_distance, reverse=True) new_population.extend(fronts[front_index][:remaining]) population = [combined_population[i] for i in new_population] # 输出帕累托前沿 pareto_front = fast_non_dominated_sort(population) print("Pareto Front Individuals:") for idx in pareto_front[0]: print(f"Schedule: {population[idx].schedule}, Makespan: {population[idx].makespan}, Cost: {population[idx].cost}") if __name__ == "__main__": main() ``` 上述代码为简化版本，仅用于演示 NSGA-II 在车间调度中的基本流程。实际应用中需要更复杂的编码方式、更精细的目标函数定义以及更高效的遗传算子设计[^2]。