### [job shop scheduling] solving flexible job shop scheduling problem based on Matlab genetic algorithm [including Matlab source code 660]

Matlab scientific research 2021-08-10 09:14:53 阅读数:868

job shop scheduling solving flexible

## One 、 brief introduction

1 Overview of genetic algorithm
Genetic algorithm (ga) （Genetic Algorithm,GA） It's part of evolutionary computing , It is a computational model that simulates the biological evolution process of Darwin's genetic selection and natural elimination , It is a method to search the optimal solution by simulating the natural evolution process . The algorithm is simple 、 Universal , Strong robustness , Suitable for parallel processing .

2 Characteristics and application of genetic algorithm
Genetic algorithm is a kind of robust search algorithm which can be used for complex system optimization , Compared with the traditional optimization algorithm , It has the following characteristics ：
（1） Take the code of decision variable as the operation object . Traditional optimization algorithms often directly use the actual value of decision variables to optimize calculation , But genetic algorithm uses some form of coding of decision variables as the operation object . This coding method for decision variables , So we can learn from the concepts of chromosome and gene in Biology , It can imitate the genetic and evolutionary incentives of organisms in nature , Genetic operators can also be easily applied .
（2） Directly use fitness as search information . The traditional optimization algorithm not only needs to use the value of the objective function , Moreover, the search process is often constrained by the continuity of the objective function , There may be a need to meet “ The derivative of the objective function must exist ” To determine the search direction . The genetic algorithm only uses the fitness function value transformed by the objective function value to determine the further search range , No other auxiliary information such as derivative value of objective function is required . Directly using the objective function value or individual fitness value can also focus the search range into the search space with higher fitness , To improve search efficiency .
（3） Search information using multiple points , With implicit parallelism . The traditional optimization algorithm is often an iterative search process starting from an initial point in the solution space . A single point provides little search information , So the search efficiency is not high , It is also possible to fall into the local optimal solution and stop ; Genetic algorithm starts the search process of the optimal solution from the initial population composed of many individuals , Instead of searching from a single individual . Of the initial population 、 choice 、 cross 、 Mutation and other operations , Produce a new generation of groups , It includes a lot of group information . This information can avoid searching some unnecessary points , So as to avoid falling into local optimization , Gradually approach the global optimal solution .
（4） Use probabilistic search instead of deterministic rules . Traditional optimization algorithms often use deterministic search methods , The transfer from one search point to another has a definite transfer direction and transfer relationship , This certainty may make the search less than optimal , It limits the application scope of the algorithm . Genetic algorithm is an adaptive search technology , Its choice 、 cross 、 Operations such as mutation are carried out in a probabilistic way , Increases the flexibility of the search process , And it can converge to the optimal solution with a large probability , It has good global optimization ability . but , Crossover probability 、 Mutation probability and other parameters will also affect the search results and search efficiency of the algorithm , Therefore, how to select the parameters of genetic algorithm is an important problem in its application .
Sum up , Because the overall search strategy and optimization search method of genetic algorithm do not depend on gradient information or other auxiliary knowledge , Only the objective function affecting the search direction and the corresponding fitness function need to be solved , Therefore, genetic algorithm provides a general framework for solving complex system problems . It does not depend on the specific area of the problem , Strong robustness to the types of problems , So it is widely used in various fields , Include ： Function optimization 、 Combinatorial optimal production scheduling problem 、 Auto-Control
、 Robotics 、 The image processing （ Image restoration 、 Image edge feature extraction …)、 Artificial life 、 Genetic programming 、 machine learning .

3 The basic flow and implementation technology of genetic algorithm
Basic genetic algorithm （Simple Genetic Algorithms,SGA） Use only the selection operator 、 Crossover operator and mutation operator are three genetic operators , Evolution is simple , It is the basis of other genetic algorithms .

3.1 The basic flow of genetic algorithm
Generate a number of randomly determined lengths （ The length is related to the accuracy of the problem to be solved ） The initial population of coding ;
Each individual is evaluated by fitness function , Individuals with high fitness value were selected to participate in genetic operation , Individuals with low fitness are eliminated ;
Genetically manipulated （ Copy 、 cross 、 variation ） A new generation of population is formed by the collection of individuals , Until the stop criteria are met （ Evolution algebra GEN>=?）;
The best realized individual in the offspring is taken as the execution result of the genetic algorithm .

among ,GEN Is the current algebra ;M It's population size ,i Represents the number of populations .

3.2 Implementation technology of genetic algorithm
Basic genetic algorithm （SGA） Coded by 、 Fitness function 、 Genetic operators （ choice 、 cross 、 variation ） And operation parameters .
3.2.1 code
（1） Binary code
The length of binary coded string is related to the accuracy of the problem . We need to ensure that every individual in the solution space can be encoded .
advantage ： Ed 、 The decoding operation is simple , inheritance 、 Crossover is easy to achieve
shortcoming ： The length is large
（2） Other coding methods
Gray code 、 Floating point code 、 Symbolic encoding 、 Multi parameter coding, etc
3.2.2 Fitness function
The fitness function should effectively reflect the gap between each chromosome and the chromosome of the optimal solution of the problem .
3.2.3 Selection operator

3.2.4 Crossover operator
Cross operation refers to the exchange of some genes between two paired chromosomes in some way , And two new individuals ; Crossover operation is an important feature that distinguishes genetic algorithm from other evolutionary algorithms , Is the main way to produce new individuals . Before crossing, individuals in the group need to be paired , Generally, the principle of random pairing is adopted .
Commonly used crossover ：
A single point of intersection
Two point intersection （ Multi-point crossover , The more cross points , The more likely the individual's structure is to be destroyed , Generally, multi-point intersection is not adopted ）
Uniform cross
Arithmetic crossover
3.2.5 Mutation operator
The mutation operation in genetic algorithm refers to replacing the gene values at some loci in the individual chromosome coding string with other alleles at this locus , So as to form a new individual .

In terms of the ability to generate new individuals in the operation of genetic algorithm , Cross operation is the main method to generate new individuals , It determines the global search ability of genetic algorithm ; Mutation is only an auxiliary method to generate new individuals , But it is also an essential operation step , It determines the local search ability of genetic algorithm . The combination of crossover operator and mutation operator completes the global search and local search of the search space , Thus, the genetic algorithm can complete the optimization process of the optimization problem with good search performance .

3.2.6 Operation parameters

4 The basic principle of genetic algorithm
4.1 Pattern theorem

4.2 Building block hypothesis
With low order 、 The definition length is short , The pattern whose fitness value is higher than the average fitness value of the population is called gene block or building block .
Building block hypothesis ： Individual gene blocks are selected 、 cross 、 The role of genetic operators such as mutation , Can be spliced together , Form individual coding strings with higher fitness .
The building block hypothesis illustrates the basic idea of using genetic algorithm to solve various problems , That is, better solutions can be produced by directly splicing building blocks together .

## Two 、 Source code

function [Chromosome] = POX_GA(T,Iterations,PopSize,Pc,Pm)
%% INPUT:
%T--input matrix:
% For example:
% A partial flexible scheduling problem in which 8 jobs are processed
% on 8 machines, in which the number of available machining machines per
% step of job is less than or equal to the total number of machines
% J1 ={[5 3 5 3 3 0 10 9];[10 0 5 8 3 9 9 6];[0 10 0 5 6 2 4 5]};
% J2 ={[5 7 3 9 8 0 9 0];[0 8 5 2 6 7 10 9];[0 10 0 5 6 4 1 7];[10 8 9 6 4 7 0 0]};
% J3 ={[10 0 0 7 6 5 2 4];[0 10 6 4 8 9 10 0];[1 4 5 6 0 10 0 7]};
% J4 ={[3 1 6 5 9 7 8 4];[12 11 7 8 10 5 6 9];[4 6 2 10 3 9 5 7]};
% J5 ={[3 6 7 8 9 0 10 0];[10 0 7 4 9 8 6 0];[0 9 8 7 4 2 7 0];[11 9 0 6 7 5 3 6]};
% J6 ={[6 7 1 4 6 9 0 10];[11 0 9 9 9 7 6 4];[10 5 9 10 11 0 10 0]};
% J7 ={[5 4 2 6 7 0 10 0];[0 9 0 9 11 9 10 5];[0 8 9 3 8 6 0 10]};
% J8 ={[2 8 5 9 0 4 0 10];[7 4 7 8 9 0 10 0];[9 9 0 8 5 6 7 1];[9 0 3 7 1 5 8 0]};
%T={J1;J2;J3;J4;J5;J6;J7;J8}; 8*1 cell
%Iterations--The number of iterations of the genetic algorithm;
%PopSize--Population size in genetic algorithms,2*PopSize+1
%Pc--probability of crossover
%Pm--probability of mutation
%% OUTPUT
% Chromosome--The best Chromosome of the genetic algorithm
%% variable declaration
num_of_jobs = length(T); %number of jobs
num_of_machines = length(T{1}{1}); %number of machines
steps_of_job =[];
for i = 1:num_of_jobs
steps_of_job=[steps_of_job;length(T{i})];
end
len_of_chromosome = sum(steps_of_job);
PopSize = PopSize+1;
Performance1 =[];
machine_of_job=cell(num_of_jobs,1);
% calculate the machine set for each steps of each job
for i=1:num_of_jobs
steps=cell(steps_of_job(i),1);
for j = 1:steps_of_job(i)
machineset=[];
for k=1:length(T{i}{j})
if T{i}{j}(k)~=0
machineset=[machineset k];
end
end
steps{j}=machineset;
end
machine_of_job{i}=steps;
end
disp('begin interating ...')
%% Coding
[Population] = Coding(T,PopSize);
%% Population iteration
FITNESS = zeros(PopSize,1); % fitness values for population
for iterator = 1:Iterations
%% fitness calculation
for index=1:PopSize
chromosome=Population{index}; % choose one chromosome from population
[FitnessValue] = FitnessCalculator(T,chromosome); % fitness calculation
FITNESS(index)=FitnessValue; % the larger the Pfit_value
end
BestFitness=min(FITNESS); % find the best chromosome
position=find(FITNESS==BestFitness); % and the position,may be more than one
BestChromosome=Population{position(1)}; % choose one chromosome from population
%% Selection :Elitism and 2-tournament selection are used
Parent = cell(PopSize,1);
Pr =0.8;
for index =1:PopSize-1
pos = randperm(PopSize,2);
chromosome1 = Population{pos(1)};
chromosome2 = Population{pos(2)};
if (rand(1)<Pr) && FITNESS(pos(1))>FITNESS(pos(2))
chromosome = chromosome1;
else
chromosome = chromosome2;
end
Parent{index} = chromosome;
end
Parent{PopSize}=BestChromosome;
%% Crossover: IPOX for steps, MPX for machine
Children_group1=cell(PopSize,1);
for i=1:(PopSize-1)
%Parent individuals are selected for crossover operation:
%Parent1 is selected sequentially and Parent2 is selected randomly.
index_parent2 = randi([1,(PopSize-1)]);
Parent1=Parent{i};
Parent2=Parent{index_parent2};
Children1=zeros(2,len_of_chromosome);
Children2=zeros(2,len_of_chromosome);
if rand(1)<=Pc %Use the probability to determine if crossover is required
%% Part1: IPX for step
%Randomly divide the set of jobs {1,2,3...,n} into two non-empty sub-sets J1 and J2.
num_J1 = randi([1,num_of_jobs]);
if num_J1==num_of_jobs
num_J1 = fix(num_of_jobs/2);
end
J = randperm(num_of_jobs);
J1 =J(1:num_J1);
J2 =J(num_J1+1:num_of_jobs);
% Copy the jobs that Parent1 contains in J1 to Children1,
% and Parent2 contains in J2 to Children2, and keep them in place.
for index = 1:num_J1 % look for jobs that Parent1 are included in J1
job = J1(index);
for j = 1:len_of_chromosome
if job == Parent1(1,j)
Children1(1,j)=Parent1(1,j);
end
end
end
for index = 1:num_of_jobs-num_J1 % look for jobs that Parent2 are included in J2
job = J2(index);
for j = 1:len_of_chromosome
if job == Parent2(1,j)
Children2(1,j)=Parent2(1,j);
end
end
end
%Copy the jobs that Parent1 contains in J1 to Children2,
%and Parent2 contains in J2 to Children1 in their order.
for index = 1:len_of_chromosome % look for jobs that Parent1 are included in J1
job = Parent1(1,index);
if ~isempty(find(J1==job, 1))
for gene = 1:len_of_chromosome
if Children2(1,gene)==0
Children2(1,gene)=job;
break;
end
end
end
end
for index = 1:len_of_chromosome % look for jobs that Parent1 are included in J1
job = Parent2(1,index);
if ~isempty(find(J2==job, 1))
for gene = 1:len_of_chromosome
if Children1(1,gene)==0
Children1(1,gene)=job;
break;
end
end
end
end
%%IPOX cross operation completed
%% Part 2 MPX for machine
%The process of crossover operation is as follows: firstly, a set rand0_1
%composed of 0 and 1 that is equal to the length of chromosome is randomly
%generated, and then the genes at the same position of 1 in the set of rand0_1
%in the two parental generations are interchanged, and two offspring are
%obtained after the crossover
rand0_1 = zeros(1,len_of_chromosome);
for gene = 1:len_of_chromosome
if rand(1)>0.5
rand0_1(gene)=1;
end
end
for gene = 1:len_of_chromosome
if rand0_1(gene)==1
Children1(2,gene) = Parent2(2,gene);
Children2(2,gene) = Parent1(2,gene);
else
Children1(2,gene) = Parent1(2,gene);
Children2(2,gene) = Parent2(2,gene);
end
end
%MOX cross operation completed
else
Children1 = Parent1;
Children2 = Parent2;
end
%% Select the Fitness value best retained to the next generation
[Parent1_FitnessValue] = FitnessCalculator(T,Parent1);
[Parent2_FitnessValue] = FitnessCalculator(T,Parent2);
[Children1_FitnessValue] = FitnessCalculator(T,Children1);
[Children2_FitnessValue] = FitnessCalculator(T,Children2);
[~, pos] = max([Parent1_FitnessValue Parent2_FitnessValue Children1_FitnessValue Children2_FitnessValue]);
temp_group ={Parent1 Parent2 Children1 Children2};
% if rand(1)>0.5
% Children_group1{i}=Children1;
% else
% Children_group1{i}=Children2;
% end
Children_group1{i}=temp_group{pos};
end

• 1.
• 2.
• 3.
• 4.
• 5.
• 6.
• 7.
• 8.
• 9.
• 10.
• 11.
• 12.
• 13.
• 14.
• 15.
• 16.
• 17.
• 18.
• 19.
• 20.
• 21.
• 22.
• 23.
• 24.
• 25.
• 26.
• 27.
• 28.
• 29.
• 30.
• 31.
• 32.
• 33.
• 34.
• 35.
• 36.
• 37.
• 38.
• 39.
• 40.
• 41.
• 42.
• 43.
• 44.
• 45.
• 46.
• 47.
• 48.
• 49.
• 50.
• 51.
• 52.
• 53.
• 54.
• 55.
• 56.
• 57.
• 58.
• 59.
• 60.
• 61.
• 62.
• 63.
• 64.
• 65.
• 66.
• 67.
• 68.
• 69.
• 70.
• 71.
• 72.
• 73.
• 74.
• 75.
• 76.
• 77.
• 78.
• 79.
• 80.
• 81.
• 82.
• 83.
• 84.
• 85.
• 86.
• 87.
• 88.
• 89.
• 90.
• 91.
• 92.
• 93.
• 94.
• 95.
• 96.
• 97.
• 98.
• 99.
• 100.
• 101.
• 102.
• 103.
• 104.
• 105.
• 106.
• 107.
• 108.
• 109.
• 110.
• 111.
• 112.
• 113.
• 114.
• 115.
• 116.
• 117.
• 118.
• 119.
• 120.
• 121.
• 122.
• 123.
• 124.
• 125.
• 126.
• 127.
• 128.
• 129.
• 130.
• 131.
• 132.
• 133.
• 134.
• 135.
• 136.
• 137.
• 138.
• 139.
• 140.
• 141.
• 142.
• 143.
• 144.
• 145.
• 146.
• 147.
• 148.
• 149.
• 150.
• 151.
• 152.
• 153.
• 154.
• 155.
• 156.
• 157.
• 158.
• 159.
• 160.
• 161.
• 162.
• 163.
• 164.
• 165.
• 166.
• 167.
• 168.
• 169.
• 170.
• 171.
• 172.
• 173.
• 174.
• 175.
• 176.
• 177.
• 178.
• 179.
• 180.
• 181.
• 182.
• 183.
• 184.
• 185.
• 186.
• 187.
• 188.
• 189.
• 190.
• 191.
• 192.
• 193.
• 194.
• 195.

edition ：2014a