基于POX交叉的遗传算法求解流水车间调度(J-Shop)问题二

clc;clear;[jobN, machineN, taskDuration, taskUse, processSize] = readDataFile('ft06.txt');popSize = 200;chromLength = jobN * processSize;pc = 0.85;pm = 0.05;maxGen = 100;bestObjValue = 0;objValues = zeros(1, maxGen);avgObjValue = zeros(1, maxGen);bestChrom = zeros(1, chromLength);pop = initPop(popSize, chromLength, jobN);objValue = calObjValue(pop, jobN, machineN, processSize, taskDuration, taskUse);fitness = calFitness(objValue);for gen = 1:maxGen
    pop = selection(pop, fitness);
    pop = crossover(pop, pc, jobN);
    pop = mutation(pop, pm);

    objValue = calObjValue(pop, jobN, machineN, processSize, taskDuration, taskUse);
    fitness = calFitness(objValue);

    avgObjValue(gen) = sum(objValue) / popSize;
    [objValues, bestObjValue, bestChrom] = bestValue(gen, pop, ...
        objValue, objValues, bestObjValue, bestChrom);endfprintf('最优染色体: %s\n', mat2str(bestChrom));fprintf('最优时间: %d\n', bestObjValue);figure();plot(1:maxGen, objValues);title('种群最优个体目标函数（时间）变化图');figure();plot(1:maxGen, avgObjValue);title('种群目标函数值平均值（时间）变化图');[taskSTime, taskETime] = calTaskTime(bestChrom, jobN, machineN, ...
    processSize, taskDuration, taskUse);drawGantt(taskUse, taskSTime, taskETime);

function cpop = crossover(pop, pc, jobN)% 交叉，POX方法cpop = pop;for i = 1:2:size(pop, 1)
    if rand < pc        [p1, p2] = deal(pop(i, :), pop(i+1, :));
        [c1, c2] = deal(p1, p2);
        canJ = randperm(jobN);
        J = canJ(1:randi(jobN-1));
        [c1Lia, c2Lia] = deal(ismember(p1, J), ismember(p2, J));
        [c1(c1Lia), c2(c2Lia)] = deal(p2(c2Lia), p1(c1Lia));
        [cpop(i, :), cpop(i+1, :)] = deal(c1, c2); 
    endendend

function objValue = calObjValue(pop, jobN, machineN, processSize, taskDuration, taskUse)% 计算种群目标函数值（总完工时间）[popSize, ~] = size(pop);objValue = zeros(1, popSize);for i = 1:popSize    [~, taskETime] = calTaskTime(pop(i, :), jobN, machineN, ...
        processSize, taskDuration, taskUse);
    objValue(i) = max(max(taskETime));endend

function [taskSTime, taskETime] = calTaskTime(chrom, jobN, machineN, processSize, taskDuration, taskUse)% 计算染色体目标函数值（总完工时间）jobProcess = zeros(1, jobN);machETime = zeros(1, machineN);[taskSTime, taskETime] = deal(zeros(jobN, processSize));for j = 1:length(chrom)
    job = chrom(j);
    jobProcess(job) = jobProcess(job) + 1;
    process = jobProcess(job);
    machine = taskUse(job, process);
    if process == 1
        startTime = max([0, machETime(machine)]);
    else
        startTime = max([taskETime(job, process-1), machETime(machine)]);
    end
    taskSTime(job, process) = startTime;
    endTime = startTime + taskDuration(job, process);
    [taskETime(job, process), machETime(machine)] = deal(endTime);endend