遗传算法求FSP问题

### 使用遗传算法解决FSP调度问题

#### 1. 遗传算法简介
遗传算法(GA)是一种模拟自然选择和遗传机制的并行随机搜索最优化方法[^2]。此算法通过模仿自然界中的“优胜劣汰，适者生存”的原则来进行数学仿真。

#### 2. FSP问题描述
流水车间调度问题(FSP, Flow Shop Scheduling Problem)，是指一系列工件需经过相同顺序的不同机器加工，在给定约束条件下最小化完成时间或其他性能指标的问题[^5]。

#### 3. 编码方案
对于FSP而言，一种常见的编码方式是排列编码(permutation encoding)，即染色体表示为一个整数序列，代表各工件处理次序。例如：

chromosome = [4, 2, 1, 3]

这表明第四个工件最先被处理，其次是第二个、第一个以及第三个工件。

#### 4. 初始化种群
创建初始种群时可以随机生成若干符合条件的个体作为起始点。为了保证多样性，应尽可能覆盖较大的解空间范围。

#### 5. 计算适应度值
针对每一个可能的解决方案(即每条染色体),计算其对应的完工时间和/或其它评价标准得分。较低的总耗时意味着更高的适应度分数。

#### 6. 选择操作
依据适应度比例选取部分优秀个体参与繁殖下一代的操作。常用的选择策略包括轮盘赌法(Roulette Wheel Selection)等概率抽样手段。

#### 7. 交叉变异
按照预设的概率执行单点或多点交叉(crossover)与位移突变(mutation):

- **交叉**: 将两个父代的部分基因片段交换位置形成新的后代;

- **变异**: 对某些选定的位置上的数值做微调改变;

这些过程有助于探索更广阔的潜在最优区域。

#### 8. 替换旧群体
用新产生的子代替换掉当前世代的一部分成员，从而构成下一轮迭代的基础材料。

#### 9. 终止条件判断
当达到预定的最大循环次数或是找到满意程度足够高的可行解之后停止运算，并输出最终结果。

以下是Python语言下的简单实现框架:

import random
from copy import deepcopy

def generate_initial_population(size=100):
    """初始化种群"""
    population = []
    for _ in range(size):
        chromosome = list(range(num_jobs))
        random.shuffle(chromosome)
        population.append(chromosome)
    return population


def evaluate_fitness(individual):
    """评估适应度"""
    makespan = calculate_makespan(individual)
    fitness_value = 1 / (makespan + 1e-6)  # 加一个小常数防止除零错误
    return fitness_value


def selection(population_with_fitnesses):
    """选择操作"""
    total_fit = sum([item[1] for item in population_with_fitnesses])
    pick = random.uniform(0, total_fit)
    current = 0
    for individual, fit in population_with_fitnesses:
        current += fit
        if current > pick:
            return individual


def crossover(parent1, parent2):
    """交叉操作"""
    point = random.randint(1, num_jobs - 1)
    child = [-1]*num_jobs
    
    segment_from_parent_1 = parent1[:point]
    
    index_in_child = 0
    for gene in parent2:
        if gene not in segment_from_parent_1 and index_in_child >= point:
            break
        elif gene not in segment_from_parent_1:
            continue
        else:
            child[index_in_child] = gene
            index_in_child += 1
            
    remaining_genes = set(parent2).difference(set(child))
    for i in range(len(child)):
        if child[i]==-1:
            child[i]=remaining_genes.pop()
            
    return child
    

def mutate(individual, mutation_rate=0.01):
    """变异操作"""
    mutated_individual = deepcopy(individual)
    for idx in range(len(mutated_individual)):
        if random.random() < mutation_rate:
            swap_idx = int(random.random()*len(mutated_individual))
            temp = mutated_individual[idx]
            mutated_individual[idx] = mutated_individual[swap_idx]
            mutated_individual[swap_idx] = temp
    return mutated_individual


if __name__ == '__main__':
    max_generations = 1000
    pop_size = 100
    elite_count = 10
    mutation_prob = 0.01
    num_jobs = 10  # 假设有十个任务需要安排到三台设备上运行
    
    best_solution = None
    best_fitness = float('-inf')
    
    population = generate_initial_population(pop_size)

    for generation in range(max_generations):
        
        evaluated_pop = [(indiv, evaluate_fitness(indiv)) for indiv in population]

        sorted_evaluated_pop = sorted(evaluated_pop, key=lambda x:x[1], reverse=True)[:elite_count]
        
        next_gen = [individual for individual,_ in sorted_evaluated_pop]
        
        while len(next_gen)<pop_size:
            p1 = selection(evaluated_pop)
            p2 = selection(evaluated_pop)
            offspring = crossover(p1,p2)
            offspring_mutated = mutate(offspring, mutation_prob)
            next_gen.append(offspring_mutated)
                
        population = next_gen
        
        curr_best_indv,curr_best_fit = max(sorted_evaluated_pop,key=lambda x:x[1])

        if curr_best_fit>best_fitness:
            best_fitness = curr_best_fit
            best_solution = curr_best_indv
                
print(f'Best solution found:{best_solution}, with fitness {best_fitness}')