遗传算法解决有工序顺序约束的大规模FJSP问题

Question

链接的表格是转向架架修的工序活动情况列表(链接：https://pan.baidu.com/s/1j4werqkMiKuVkVgwkkfiYQ
提取码：1234)，包括活动序号（按字符串处理），工时（浮点数），邻接前序工序活动（按照字符串处理，多个字符之间用;隔开），工序执行工位限制（按字符串处理）等信息。邻接前序工序活动指的是某工序在开始前必须要完成其他的工序，部分工序活动不存在任何前置工序，则表格内为空。有些工序存在多道前序工序，在表格中这些前序工序的编号之间用“;”给相隔开。此外工序之间还存在工位限制，即部分多道工序之间虽然不存在前后顺序要求，但是必须在同一个工位上执行，而每个工位在某一时刻只能执行一道工序，必须等执行完成才能开始进行另一道工序的执行。只有两道工序的执行工位不同，才可以并行。所有工序一旦开始执行，均不能中途停止，切换工位不消耗任何时间。请根据表格中工序数据的具体情况（邻接约束多少，解空间的大小，工位限制情况等）。我想要求解所有工序都完成的最短总工时，请用python采用遗传算法来求解，请帮忙分析下编码策略，初始化和变异交叉选择的策略，如果不用遗传算法，那么其他的启发式算法例如粒子群，蚁群算法等能不能解，求众位帮帮忙。

Answer 1

引用讯飞星火
首先，我们需要解析表格中的数据，将其转换为适合遗传算法处理的格式。我们可以使用pandas库来读取和处理表格数据。

import pandas as pd

# 读取表格数据
data = pd.read_excel('https://pan.baidu.com/s/1j4werqkMiKuVkVgwkkfiYQ', sheet_name='工序活动情况列表')

# 提取所需信息
activities = data['活动序号'].tolist()
durations = data['工时'].astype(float).tolist()
precedences = data['邻接前序工序活动'].str.split(';').tolist()
constraints = data['工序执行工位限制'].tolist()

接下来，我们需要设计一个编码策略，将问题转化为染色体表示。我们可以使用字典来表示染色体，其中键是工序编号，值是该工序在染色体中的索引。这样，我们可以通过染色体的索引顺序来确定工序的执行顺序。

def create_chromosome():
    chromosome = {}
    for i, activity in enumerate(activities):
        chromosome[activity] = i
    return chromosome

初始化策略可以采用随机生成染色体的方法。

import random

def initialize_population(size):
    population = []
    for _ in range(size):
        chromosome = create_chromosome()
        population.append(chromosome)
    return population

变异策略可以采用交换两个工序位置的方法。

def mutate(chromosome):
    keys = list(chromosome.keys())
    i, j = random.sample(range(len(keys)), 2)
    key_i, key_j = keys[i], keys[j]
    chromosome[key_i], chromosome[key_j] = chromosome[key_j], chromosome[key_i]

交叉策略可以采用部分匹配交叉（PMX）方法。

def crossover(parent1, parent2):
    keys = list(parent1.keys())
    size = len(keys)
    start, end = sorted(random.sample(range(size), 2))
    child1, child2 = {key: -1 for key in keys}, {key: -1 for key in keys}
    
    for i in range(start, end + 1):
        child1[keys[i]], child2[keys[i]] = parent2[keys[i]], parent1[keys[i]]
    
    for key in keys:
        if child1[key] == -1:
            child1[key] = parent1[key]
        if child2[key] == -1:
            child2[key] = parent2[key]
    
    return child1, child2

评估策略需要根据约束条件计算每个染色体的适应度值。适应度值可以定义为所有工序的总工时减去违反约束条件的惩罚值。

def evaluate(chromosome):
    total_duration = sum(durations)
    penalty = 0
    
    for i, activity in enumerate(activities):
        for precedence in precedences[i]:
            if chromosome[activity] < chromosome[precedence]:
                penalty += durations[i]
                break
        
        for constraint in constraints[i]:
            if constraint != '' and chromosome[activity] != chromosome[constraint]:
                penalty += durations[i]
                break
    
    return total_duration - penalty

最后，我们可以使用遗传算法求解最短总工时。

def genetic_algorithm(population_size, generations, mutation_rate, crossover_rate):
    population = initialize_population(population_size)
    
    for generation in range(generations):
        fitness_values = [evaluate(chromosome) for chromosome in population]
        best_index = fitness_values.index(max(fitness_values))
        best_chromosome = population[best_index]
        print(f'Generation {generation + 1}: Best fitness = {fitness_values[best_index]}')
        
        new_population = [best_chromosome]
        
        while len(new_population) < population_size:
            parent1, parent2 = random.choices(population, k=2)
            
            if random.random() < crossover_rate:
                child1, child2 = crossover(parent1, parent2)
            else:
                child1, child2 = parent1, parent2
            
            if random.random() < mutation_rate:
                mutate(child1)
            if random.random() < mutation_rate:
                mutate(child2)
            
            new_population.extend([child1, child2])
        
        population = new_population
    
    best_index = fitness_values.index(max(fitness_values))
    best_chromosome = population[best_index]
    return best_chromosome, fitness_values[best_index]

通过调整遗传算法的参数，例如种群大小、迭代次数、变异率和交叉率，可以得到不同的解。