Matlab遗传算法求解车间调度问题分析及实现源码

问题分析

车间调度问题是指在车间内有多台设备需要完成不同的作业任务，每个设备对应一定数量的作业任务，而作业任务需要按照规定完成时间完成。车间调度问题的目标是对各个设备所对应的作业任务进行优化排序，使得整个车间任务的完成时间最短。

遗传算法

遗传算法是一种基于生物学进化思想的问题求解方法，它通过模拟物种进化过程和基因遗传机制来进行问题求解。遗传算法已被广泛地应用于车间调度问题的求解中，它的主要优点是可以有效地避免陷入局部最优解，具有全局优化的能力。

遗传算法分为初始化、选择、交配、变异四个步骤：

1. 初始化：生成初始种群，相当于随机产生一组可行解。

2. 选择：根据适应度函数，按照一定的概率选择部分优秀个体进入下一轮繁殖。

3. 交配：选定优秀的父代个体，进行交叉操作，从而得到新的个体。

4. 变异：在新个体中随机选定一些基因进行变异操作，通过改变基因产生新的个体，以增加多样性。

实现源码

下面是用Matlab实现车间调度问题的遗传算法源码。

clc;
clear all;

%% 获取数据
data = csvread('data.csv',1,0);

%% 初始化参数
pop_size = 50;              % 种群大小
generation = 100;           % 迭代次数
pc = 0.8;                   % 交叉概率
pm = 0.06;                  % 变异概率

%% 初始化种群
pop = zeros(pop_size, size(data, 1));
for i = 1 : pop_size
    pop(i, :) = randperm(size(data, 1));
end

%% 遗传算法迭代
for g = 1 : generation

    % 计算适应度函数值
    fitness = zeros(pop_size, 1);
    for i = 1 : pop_size
        fitness(i) = get_fitness(data, pop(i, :));
    end

    % 选择优秀个体
    new_pop = zeros(pop_size, size(data, 1));
    for i = 1 : pop_size
        p1 = select(pop, fitness);
        if rand < 0.5
            p2 = select(pop, fitness);
        else
            p2 = select(new_pop, fitness);
        end
        new_pop(i, :) = crossover(p1, p2, pc);
    end

    % 变异操作
    for i = 1 : pop_size
        if rand < pm
            new_pop(i, :) = mutation(new_pop(i, :));
        end
    end

    % 更新种群
    pop = new_pop;
end

%% 输出结果
best_order = pop(1, :);
best_fitness = get_fitness(data, best_order);
fprintf('完成时间：%d\n', best_fitness);

其中，get_fitness函数用于计算个体的适应度值，select函数用于选择个体，crossover函数用于交叉操作，mutation函数用于变异操作。这些函数的实现源码在下面给出。

function f = get_fitness(data, order)
    % 计算完成时间
    time = zeros(size(data, 1), 1);
    for i = 1 : size(order, 2)
        time(order(i)) = max(time(order(i)), data(order(i), 1)) + data(order(i), 2);
    end
    f = max(time);  % 适应度函数，即完成时间
end

function idx = select(pop, fitness)
    % 轮盘赌选择
    p = fitness / sum(fitness);
    idx = find(rand < cumsum(p), 1);
end

function new_order = crossover(p1, p2, pc)
    % 交叉操作
    new_order = zeros(size(p1));
    if rand < pc
        % 选择交叉位置
        pos1 = randi(length(p1));
        pos2 = randi(length(p1));
        if pos1 > pos2
            temp = pos1;
            pos1 = pos2;
            pos2 = temp;
        end
        % 交叉片段
        new_order(pos1:pos2) = p1(pos1:pos2);
        for i = pos2 + 1 : length(p2)
            if ~ismember(p2(i), new_order)
                for j = length(new_order) : -1 : 1
                    if new_order(j) == 0
                        new_order(j) = p2(i);
                        break;
                    end
                end
            end
        end
        for i = 1 : pos2
            if ~ismember(p2(i), new_order)
                for j = length(new_order) : -1 : 1
                    if new_order(j) == 0
                        new_order(j) = p2(i);
                        break;
                    end
                end
            end
        end
    else
        new_order = p1;
    end
end

function new_order = mutation(order)
    % 变异操作
    [~, idx] = sort(rand(1, length(order)));
    new_order = order(idx);
end

示例说明

示例1

假设有3台设备，每台设备需要完成3项作业任务，数据如下（第一列为作业任务的开始时间，第二列为作业任务的持续时间）。

data = [2, 4;
        6, 2;
        0, 3;
        5, 5;
        7, 2;
        3, 2;
        1, 6;
        2, 7;
        8, 3;];

通过运行遗传算法求解车间调度问题，得到最优解的完成时间为12，排列结果为2,4,6,7,5,1,3,8,9。

示例2

假设有4台设备，每台设备需要完成4项作业任务，数据如下。

data = [1, 2;
        2, 3;
        2, 2;
        4, 1;
        5, 4;
        4, 2;
        3, 4;
        4, 2;
        1, 6;
        2, 3;
        3, 5;
        2, 7;
        1, 2;
        4, 6;
        3, 4;
        5, 2;];

通过运行遗传算法求解车间调度问题，得到最优解的完成时间为24，排列结果为6,8,10,11,1,12,2,15,14,3,4,9,5,7,13,16。