遗传算法柔性作业车间调度问题

### 使用遗传算法解决柔性作业车间调度问题

#### 初始化种群
为了有效利用遗传算法来处理柔性作业车间调度问题，初始化阶段至关重要。初始种群的质量直接影响到后续迭代过程中的收敛速度和最终解的质量。通常采用随机生成的方式创建多个可行解作为初始个体，并确保这些个体满足所有约束条件[^2]。

import random

def initialize_population(size, jobs):
    population = []
    for _ in range(size):
        chromosome = [random.sample(jobs[i], len(jobs[i])) for i in range(len(jobs))]
        population.append(chromosome)
    return population

#### 编码策略
对于柔性作业车间调度问题而言，合理的编码方式能够简化问题描述并提高求解效率。一种常见的做法是以工序序列表达染色体结构，即每个基因代表某项任务在一个特定机器上的执行顺序；另一种则是基于操作的时间安排来进行编码，在这种情况下，染色体会记录下每台设备上各项工作的起始时间点。

#### 适应度函数设计
适应度评估决定了哪些解决方案会被保留下来参与下一代的选择繁殖环节。针对该类问题的特点，可以构建多目标评价体系，综合考量完成全部订单所需的最短周期、资源利用率等多个方面因素。具体实现时可通过加权平均法或其他组合形式得出单值化的评分标准[^1]。

def fitness_function(individual):
    makespan = calculate_makespan(individual)  # 计算最大完工时间
    resource_utilization = evaluate_resource_usage(individual)  # 资源使用率
    
    weights = (0.6, 0.4)  # 设置权重比例
    score = sum(w * v for w, v in zip(weights, (makespan, resource_utilization)))
    
    return 1 / (score + 1e-8)  # 返回倒数以最大化适应度

#### 遗传操作定义
交叉变异等基本遗传运算有助于探索更广阔的搜索空间从而找到更好的全局最优解。例如通过部分映射交配(PMX)或循环交配(CX)等方式交换父代间的优良特性片段形成新的后代；而位翻转突变则是在一定概率范围内改变某些位置上的数值达到扰动目的。

from copy import deepcopy

def crossover(parents):
    offspring = deepcopy(parents[0])
    start, end = sorted(random.sample(range(len(offspring)), 2))
    mapping = {parents[0][i]: parents[1][i] for i in range(start, end)}
    
    for idx in range(len(offspring)):
        while offspring[idx] in mapping and not start <= idx < end:
            offspring[idx] = mapping[offspring[idx]]
            
    return offspring


def mutate(individual, mutation_rate=0.05):
    mutated_individual = individual[:]
    for i in range(len(mutated_individual)):
        if random.random() < mutation_rate:
            j = int(random.uniform(0, len(mutated_individual)))
            mutated_individual[i], mutated_individual[j] = \
                mutated_individual[j], mutated_individual[i]
                
    return mutated_individual