[production scheduling] solve the zero waiting problem of production scheduling based on immune algorithm matlab source code

1, Introduction to immune algorithm

1 Introduction
The word "Immune" is derived from Latin. Long ago, it was noted that patients with infectious diseases will have varying degrees of immunity to the disease after recovery. In medicine, immunity refers to a physiological response of the body to contact antigenic foreign bodies. In 1958, Australian scholar Burnet first put forward the theory related to Immune Algorithm (IA) - clonal selection principle [1]. In 1973, Jerne proposed the model of Immune system [2]. Based on Burnet's clonal selection theory, he created the unique network theory, gave the mathematical framework of Immune system, and used differential equation modeling to simulate the dynamic changes of lymphocytes.
In 1986, Farm al and others constructed the dynamic model of immune system based on the theory of immune network, which showed the possibility of the combination of immune system and other artificial intelligence methods, and created a precedent in the research of immune system. They first used a set of randomly generated differential equations to establish
In the artificial immune system, the inappropriate differential equations in the equation group are removed by using the fitness threshold filtering method, and the retained differential equations are generated by genetic operations such as crossover, mutation and reversal. After continuous iterative calculation, the best set of differential equations is found.
Since then, the research on immune algorithm has attracted more and more scholars' interest in the world. For decades, the related research results have involved many fields such as nonlinear optimization, combinatorial optimization, control engineering, robot, fault diagnosis, image processing and so on [3-6]. Immune algorithm is a new intelligent optimization algorithm artificially constructed by imitating biological immune mechanism and combining gene evolution mechanism. It has the characteristics of general immune system, adopts group search strategy, and finally obtains the optimal solution with a large probability through iterative calculation. Compared with other algorithms, immune algorithm uses its own characteristics of diversity and maintenance mechanism to ensure the diversity of population, overcome the inevitable "premature" problem in the general optimization process (especially the multi peak optimization process), and can obtain the global optimal solution. Immune algorithm has the advantages of adaptability, randomness, parallelism, global convergence and population diversity.

2 immune algorithm theory
Biological immune system is a complex adaptive system. The immune system can recognize pathogens and has the ability of learning, memory and pattern recognition. Therefore, its information processing mechanism can be used for reference to solve scientific and engineering problems. Immune algorithm is based on biological immune system to recognize external
The new research direction of intelligent optimization method based on immune principle was born.

2.1 biological immune system
Traditional immunity refers to the body's defense ability against infection, while modern immunity refers to the function of the body's immune system to recognize and eliminate antigenic foreign bodies, so as to maintain the body's physiological balance and stability. Immunity is a physiological response of the body. When pathogens (i.e. antigens) enter the human body, these antigens will stimulate immune cells (lymphoid B cells and T cells) to produce a special protein antibody against the pathogenic organism. The antibody can eliminate the pathogenic organism and remain in the human body after eliminating the pathogenic organism. When the same pathogen invades the human body again, the
Pathogenic organisms will be quickly destroyed by the remaining antibodies in the body [7]
Immunology related concepts
Immunity refers to the sum of biological effects produced in the process of recognition and response of the body to itself and foreign bodies. Under normal circumstances, it is a physiological function to maintain the stability of the body's circulation. The organism recognizes allogeneic antigen, produces immune response to it and clears it; The body does not produce its own antigen
Immune response.
Antigen is a substance that can stimulate the body to produce immune response and bind to response products. It is not an organic part of the immune system, but it is the initiating factor to initiate the immune response.
Antibody is an immune molecule that can specifically recognize and clear antigens, including globulin substances with anti-bacterial and anti toxin immune functions. Therefore, antibody is also called immunoglobulin molecule, which is produced by plasma cells differentiated from B cells.
T cells and B cells
T cells and B cells are the main components of lymphocytes. Stimulated by antigen, B cells can proliferate and differentiate into a large number of plasma cells, which have the function of synthesizing and secreting antibodies. However, B cells cannot recognize most antigens and must rely on the auxiliary ability to recognize antigens
T cells to assist B cell activation and produce antibodies.
Biological immune system mechanism
Biological immune system is a complex system composed of immune molecules, immune tissues and immune cells. These tissues and organs that make up the immune system are distributed all over the human body to complete various immune defense functions. They are well-known lymphoid organs and lymphoid tissues.
Immune recognition
Immune recognition is the main function of the immune system. The essence of recognition is to distinguish between "self" and "non self". Immune recognition is realized by the combination of antigen receptor and antigen on lymphocytes.
Immune learning
The process of immune recognition is also a learning process. The result of learning is that the individual affinity of immune cells is improved, the population size is expanded, and the optimal individuals are preserved in the form of immune memory.
Immune memory
When the immune system first encounters an antigen, lymphocytes need a certain time to adjust to better recognize the antigen, and retain the memory information of the antigen in the form of optimal antibody after recognition. When the immune system encounters the same or structurally similar antigen again
Under the action of associative memory, the response speed is greatly improved.
clonal selection
Immune response and immune cell proliferation occur above a specific matching threshold. When lymphocytes recognize antigens, B cells are activated, proliferate and replicate to produce cloned B cells, and then the cloned cells undergo the process of variation to produce antibodies specific for antigens.
Individual diversity
According to immunological knowledge, the immune system has more than 100 different proteins, but there are more than 1000 external potential antigens and pattern types to be recognized. In order to realize antigen recognition which is much larger than its own, an effective diversity individual generation mechanism is needed. Biological of antibody diversity
The mechanisms mainly include combinatorial reorganization of immune receptor library, somatic high-frequency mutation and gene conversion.
Distributed and adaptive
The distributed characteristics of the immune system first depend on the distributed characteristics of pathogens, that is, pathogens are dispersed in the body. Because the immune response mechanism is through the interaction of local cells without centralized control, the distributed immune system further enhances its adaptive characteristics
Sex. All these important information processing characteristics of immune system provide strong support for the application in the field of information and computing.

2.2 concept of immune algorithm
Immune algorithm is a new intelligent search algorithm inspired by biological immune system. It is a heuristic random search algorithm which combines deterministic and random selection and has the ability of "exploration" and "mining". In the immune algorithm, the problem to be optimized in the optimization problem corresponds to the antigen in the immune response, the feasible solution corresponds to the antibody (B cell), and the feasible solution quality corresponds to the affinity between the immune cell and the antigen. In this way, the optimization process of optimization problem can be corresponding to the process of biological immune system recognizing antigen and realizing antibody evolution, and the evolution process in biological immune response can be abstracted as a mathematical evolutionary optimization process to form an intelligent optimization algorithm.
Immune algorithm is abstracted from the mechanism of biological immune system. Many concepts and operators in the algorithm correspond to the concepts and immune mechanism in immune system. The corresponding relationship between immune algorithm and biological immune system concept is shown in Table 1. Because antibodies are produced by B cells
, in the immune algorithm, antibodies and B cells are not distinguished, which correspond to the feasible solution of the optimization problem.
Table 1 corresponding relationship between immune algorithm and biological immune system concept

According to the above correspondence, an immune algorithm for optimization calculation is formed by simulating the process of biological immune response. The algorithm mainly includes the following modules:
(1) Antigen recognition and initial antibody production. According to the characteristics of the problem to be optimized, an appropriate antibody coding rule is designed, and under this coding rule, the prior knowledge of the problem is used to generate the initial antibody population.
(2) Antibody evaluation. Evaluate the quality of antibody. The evaluation criteria are mainly antibody affinity and individual concentration. The evaluated high-quality antibody will be subjected to evolutionary immune operation, and the low-quality antibody will be updated.
(3) Immune operation. Immune selection, cloning, mutation, clonal inhibition, population refresh and other operators are used to simulate various immune operations in biological immune response, form evolutionary rules and methods based on the clonal selection principle of biological immune system, and realize the optimization search of various optimization problems

2.3 characteristics of immune algorithm
Immune algorithm is an adaptive intelligent system inspired by immunology to simulate the function and principle of biological immune system to solve complex problems. It retains some characteristics of biological immune system [8], including:
(1) Global search capability. The immune algorithm proposed by imitating the immune response process is an optimization algorithm with global search ability. The immune algorithm uses mutation operator and population refresh operator to continuously generate new individuals and explore feasible solutions while locally searching the neighborhood of high-quality antibodies
The new region of the interval ensures that the algorithm searches in the complete feasible solution interval and has global convergence performance.
(2) Diversity maintenance mechanism. Immune algorithm uses the diversity maintenance mechanism of biological immune system for reference to calculate the antibody concentration, and takes the concentration calculation results as an important standard to evaluate the individual advantages and disadvantages of antibody: it suppresses the antibody with high concentration and ensures the good diversity of antibody population, which is also an important aspect to ensure the global convergence performance of the algorithm.
(3) Strong robustness. The immune algorithm based on biological immune mechanism does not aim at specific problems, and does not emphasize the setting of algorithm parameters and the quality of initial solution. Using its heuristic intelligent search mechanism, even if it starts from the poor solution population, it can finally search the global optimal solution of the problem. It does not depend strongly on the problem and initial solution, and has strong adaptability and robustness.
(4) Parallel distributed search mechanism. Immune algorithm does not need centralized control and can realize parallel processing. Moreover, the optimization process of immune algorithm is a multi-process parallel optimization. While searching for the optimal solution of the problem, multiple suboptimal solutions of the problem can be obtained, that is, in addition to finding the best solution of the problem, several better alternatives will be obtained, especially suitable for multimodal optimization problems.

2.4 immune algorithm operator
Similar to other intelligent optimization algorithms such as genetic algorithm, the evolutionary optimization process of immune algorithm is also realized by operators. The operators of immune algorithm include affinity evaluation operator, antibody concentration evaluation operator, incentive calculation operator, immune selection operator, cloning operator and mutation operator
Operator, clone suppression operator and population refresh operator [9]. Since the coding methods of the algorithm may be real coding, discrete coding, etc., the algorithm operators under different coding methods will also be different.
Affinity evaluation operator
Affinity represents the binding strength between immune cells and antigens, which is similar to the fitness in genetic algorithm. The affinity evaluation operator is usually a function aff(x): SER, where S is the feasible solution interval of the problem and R is the real number field. The input of the function is an antibody individual (feasible solution), and the output is the affinity evaluation result. For different optimization problems, the affinity evaluation function should be defined according to the characteristics of the problem on the premise of understanding the essence of the problem. Generally, the function value or the simple treatment of the function value (such as reciprocal, inverse, etc.) can be used as the affinity evaluation for the function optimization problem. For the combinatorial optimization problem or the more complex optimization problem in application, it needs to be analyzed in detail.
Antibody concentration evaluation operator
Antibody concentration represents the diversity of antibody population. Too high antibody concentration means that there are a large number of very similar individuals in the population, then the optimization search will focus on a region of the feasible solution interval, which is not conducive to global optimization. Therefore, individuals with high concentration should be suppressed in the optimization algorithm
System to ensure individual diversity.
Antibody concentration is usually defined as:

Immune selection operator
The immune selection operator determines which antibodies are selected to enter the clone selection operation according to the excitation degree of the antibody. The antibody individuals with high motivation in the antibody group have better quality, are more likely to be selected for clonal selection, and have more search value in the search space.
Clone operator

Discrete coding algorithm mutation operator
The discrete coding algorithm is mainly binary coding. Its mutation strategy is to randomly select a few bits from the antibody string of the mutation source, change the value of the bits (take the inverse) and make them fall in the neighborhood of the discrete spatial mutation source.
Clone suppression operator
Clone inhibition operator is used to reselect the mutated clones, inhibit the antibodies with low affinity, and retain the antibodies with high affinity into the new antibody population. In the process of clone inhibition, the source antibody operated by clone operator and clone are obtained by mutation operator
When the antibody group forms a set, the clone inhibition operation will retain the antibody with the highest affinity in this set and inhibit other antibodies.
Because the source antibody operated by the clone mutation operator is the high-quality antibody in the population, and the temporary antibody set operated by the clone suppression operator contains the parent's source antibody, the operator operation of the immune algorithm implies the optimal individual retention mechanism.
Population refresh operator
The population refresh operator is used to refresh the antibodies with low incentive in the population, delete these antibodies from the antibody population and replace them with randomly generated new antibodies, which is conducive to maintaining the diversity of antibodies, realizing global search and exploring new feasible solution space areas.

3 types of immune algorithms
3.1 clone selection algorithm
Castro proposed a clonal selection algorithm based on clonal selection theory of immune system [10], which is an evolutionary algorithm simulating the learning process of immune system. Antibody production by immune response is the learning process of the immune system. The antigen is recognized by some matched B cells. These B cells divide and the resulting sub-b cells change on the basis of the mother cell, so as to seek better B cells matched with the antigen, and the sub-b cells matched with the antigen will divide again... This cycle will finally find the B cells completely matched with the antigen, B cells become plasma cells to produce antibodies. This process is a clonal selection process. Clonal selection algorithm simulates this process for optimization.
3.2 immune genetic algorithm
Chun et al. Proposed an immune algorithm, which is essentially an improved genetic algorithm [11]. According to the theory of somatic cell and immune network, the selection operation of genetic algorithm is improved, so as to maintain the diversity of population and improve the global optimization ability of the algorithm. By adding immune memory to the algorithm
Function, which improves the convergence speed of the algorithm. The immune genetic algorithm regards the antigen as the objective function, the antibody as the feasible solution, and the affinity between the antibody and the antigen as the fitness of the feasible solution. Immune genetic algorithm introduces the concept of antibody concentration and uses information entropy to describe the number of similar feasible solutions in the population. The selection operation of immune genetic algorithm is based on the affinity between antibody and antigen and the concentration of antibody. The selection rate of antibody with high affinity and low concentration is large, which suppresses the antibody with high concentration in the population and maintains the diversity of the population.
3.3 reverse selection algorithm
T cells in the immune system develop in the thymus, and immature T cells that react with their own proteins are destroyed. Therefore, mature T cells have the nature of enduring themselves, do not react with their own proteins, but only react with foreign proteins, so as to identify "self" and "non self". This is the so-called reverse selection principle. Forrest proposes a reverse selection algorithm based on the reverse selection principle for anomaly detection
Test [12]. The algorithm mainly includes two steps: first, generate a detector set, in which each detector does not match the protected data; second, continuously compare each detector in the set with the protected data. If the detector matches the protected data, it is determined that the data has changed.

3.4 vaccine immune algorithm
Jiao Licheng et al. Proposed a vaccine based immune algorithm based on the theory of immune system [13]. The algorithm adds immune operator to the genetic algorithm to improve the convergence speed of the algorithm and prevent population degradation. Immune operator includes two parts: vaccination and immune selection. The former is to improve affinity, and the latter is to prevent population degradation. Theoretical analysis shows that the immune algorithm is convergent.
The basic steps of vaccine immune algorithm are: randomly generate NP individuals to form the initial parent population; Vaccine extraction based on prior knowledge; Calculate the affinity of all individuals in the current parent population and judge the stop condition: mutate the current parent population to generate offspring
Population: the offspring population was vaccinated to obtain a new population; A new generation of male parent was obtained by immune selection operation on the new population and entered the immune cycle.

4 immune algorithm process
At present, there is no unified immune algorithm and block diagram. The following describes an algorithm flow containing immune operators in section 4.2.4, which is divided into the following steps:
(1) Firstly, antigen recognition is carried out, that is, to understand the problem to be optimized, analyze the feasibility of the problem, extract a priori knowledge, construct an appropriate affinity function, and formulate various constraints.
(2) Then the initial antibody population is generated, the feasible solution of the problem is expressed as the antibody in the solution space by coding, and an initial population is randomly generated in the solution space.
(3) The affinity of each feasible solution in the population is evaluated.
(4) Judge whether the algorithm termination conditions are met: if the conditions are met, terminate the algorithm optimization process and output the calculation results; otherwise, continue the optimization operation.

(5) The antibody concentration and excitation were calculated.
(6) Immune treatment, including immune selection, cloning, mutation and clonal inhibition.

Immune selection: select high-quality antibodies according to the affinity and concentration calculation results of antibodies in the population to activate them:
Cloning: Clone and replicate the activated antibody to obtain several copies; Mutation: mutate the cloned copy to cause affinity mutation;
Clonal inhibition: re select the mutation results, inhibit the antibodies with low affinity, and retain the mutation results with high affinity.
(7) The population is refreshed, and the randomly generated new antibody is used to replace the antibody with low incentive in the population to form a new generation of antibody, and turn to step (3).
The operation flow of immune algorithm is shown in Figure 1.

The evolutionary operation in immune algorithm is realized by evolutionary operator based on immune principle, such as immune selection, cloning, mutation and so on. Moreover, the calculation of antibody concentration and incentive degree is added in the algorithm, and the antibody concentration is used as a standard to evaluate individual quality, which is conducive to maintaining individual diversity and realizing global optimization.

5 description of key parameters
The following introduces the main parameters of immune algorithm, which plays a vital role in program design and debugging. The immune algorithm mainly includes the following key parameters:
Antibody population size NP
The antibody population retains the diversity of immune cells. Intuitively, the larger the population is, the better the global search ability of the immune algorithm is, but the amount of calculation of each generation of the algorithm increases accordingly. In most problems, NP 10 ~ 100 is more appropriate, generally no more than 200.
Proportion of immune selection
The more antibodies selected by immunization, the more clones will be produced, and the stronger the search ability, but the amount of calculation per generation will be increased. Generally, 10% ~ 50% of the antibody population size NP can be taken.
Multiple of antibody clone amplification
The multiple of cloning determines the number of cloned and expanded cells, which determines the search ability of the algorithm, mainly the local search ability. The larger the clone multiple, the better the local search ability and the better the global search ability, but the amount of calculation also increases, generally taking 5~
10 times.
Population refresh ratio
The elimination and renewal of cells is an important mechanism to produce antibody diversity, which has an important impact on the global search ability of immune algorithm. The updated antibody of each generation generally does not exceed 50% of the antibody population.
Maximum evolutionary algebra G
The maximum evolutionary algebra G is a parameter representing the end condition of the immune algorithm. It means that the immune algorithm stops running after running to the specified evolutionary algebra, and outputs the best individual in the current population as the optimal solution of the problem. Generally, 100 ~ 500 is taken as 6.
1.1 shortest path planning
Path planning is to find a collision free path from the beginning to the target state according to certain evaluation criteria in the environment with obstacles. The shortest path planning problem is a classical algorithm in graph theory. Its purpose is to find the shortest path between two nodes in a graph (composed of nodes and paths).
The specific form of this question is as follows:
(1) The shortest path problem of determining the starting point: the problem of finding the shortest path when the starting node is known.
(2) The shortest path problem of determining the end point: Contrary to the problem of determining the starting point, this problem is the problem of finding the shortest path with known end nodes. In an undirected graph, this problem is exactly the same as the problem of determining the starting point. In a directed graph, this problem is equivalent to the problem of determining the starting point by reversing all path directions.
(3) The shortest path problem of determining the starting point and end point: knowing the starting point and end point, find the shortest path between two nodes.
(4) Global shortest path problem: find all the shortest paths in the graph.
Let P(u, v) be the path from u to V in the map, then the sum of the edge weights on the path is called the weight of the path, which is recorded as w §. The path from u to V with the least weight P*(u, v) is called the shortest path from u to v.

2, Partial source code

% RUN=10;
% for run=1:RUN
%Number of machines
%Number of workpieces
%Initial antibody count
%Number of replacement antibodies
%Clone selection probability
%Cell clone number
%Concentration, clonal inhibition radius
%Excitation coefficient
%Variation probability
%Concentration selectivity
% %Feedback probability
% Pr=1;
%Number of iterations
OperationTime=[25 17 41  74 37  72  11 31  32  27 
               15 41 155 12 95  34  77 39  92  114  
               12 22 83  24 72  62  31 141 42  21  
               40 36 121 48 52  32  26 56  74  90 
               60 58 160 78 153 162 32 79  102 52 ];%Generate initial population
for i=1:N
    for j=1:n
%Calculate target value
%Calculated affinity
%Calculate similarity
%Calculate the concentration of each antibody
for i=1:N
    for j=1:N
        if Ayy(i,j)>Py
%Find the best individual
for i=1:N
    if bestmax>=MakeP(1,i)
%The best individual corresponding to the best solution
%Preservation of previous generation population
   %Sort by affinity (clone selection)
   [f1,index1]=sort(Aff,'descend');%Descending order
   for i=1:N1
       for j=1:n
   for i=1:N1
   %According to the affinity of each antibody B The antibody was cloned
   for i=1:N1
       Mn(i)=round(M*f1(i)/ff1);%The number of individuals to be cloned for each antibody was stored in Mn(i)in
       MM=MM+Mn(i);%Number of actual clones;
   %Start cloning, population number is MM(Cell cloning)
   for k=1:N1
       for j=1:Mn(k)
   for i=1:MM
   %Calculate the affinity after cloning
   %Clonal recombination
   if rand(1)<Pz
       for i=1:round(MM/2)
           %Randomly generate a cross bit
           for s=0:n-1
               if (((rand(1,1)*n)<s+1)&((rand(1,1)*n)>=s))
           for k=1:n
               if Tw(1,k)~=Tw(2,1:j_bit);
           for k=1:n
           if Tw(2,k)~=Tw(1,1:j_bit);
 %The affinity of each antibody after variation was calculated
 %Compare before and after variation to determine whether to delete
 for i=1:MM
    if Aff_MM1(1,i)>Aff_MM3(1,i)
   %Gene mutation
   %According to a certain exchange probability Pc Exchange genes between two points;
   for i=1:MM
       if rand(1)<Pc
   %According to a certain probability Pi Arrange the genes between two points in reverse order;	
	if rand(1)<Pi

 %According to a certain probability Ps Shift the gene segment between two points;
	if rand(1)<Ps
%Clonal inhibition
%The affinity of each antibody after mutation was calculated
%Compare the antibodies before and after mutation to determine whether to delete;
for i=1:MM
    if Aff_MM1(1,i)>Aff_MM2(1,i)
% C_Swarm2=C;
% %Mutate the antibody at one or more points according to a certain probability;
% for i=1:MM
%        if rand(1)<Pm
%            C(i,:)=mutation(C(i,:),n);
%        end
% end
%  %The affinity of each antibody after variation was calculated
% [MakePC,CL,ST]=calculateC(m,n,MM,C,OperationTime);
% Aff_MM3=Aff_MM3calculate(MM,MakePC);
%  %Compare before and after variation to determine whether to delete
%  for i=1:MM
%     if Aff_MM1(1,i)>Aff_MM3(1,i)
%         C(i,:)=C_Swarm2(i,:);
%         Aff_MM1(1,i)=Aff_MM3(1,i);
%     end
% end
%Calculate the similarity of each antibody, and remove the individuals with high similarity
for i=1:MM
    for j=1:MM
        if Ayy_MM(i,j)>Py
for i=1:Nc
%calculation D Affinity of antibodies in
%merge P and D Two antibody groups were obtained NNc An antibody group of two chimeras E;

    if i>Nc
%Calculate the degree of excitation
for i=1:NNc
    act(1,i)= Aff_E(1,i)*exp(-Nong_E(1,i)/Pb);
%Affinity ranking of antibodies
%Sort and select the top with the highest incentive degree and different N Antibody groups F
    for i=1:NNc-1
    if f_E(i)>f_E(i+1)
    if inumber==N+1

%The affinity of antibodies was calculated and sorted
%Calculate target value
%Calculated affinity
for i=1:N

%Randomly generated antibody G replace F The last 0 of the excitation degree in.1*N Antibodies
% if generation<50
    for i=1:Ns

for i=1:N
%Find the best individual
for i=1:N
    if bestmax>=MakeP(1,i)
%The best individual corresponding to the best solution
%Find the global best solution
if bestmax<Bestmax
% painting Gantte chart
% seg(run,1)=Bestmax;
% end

3, Operation results

5, matlab version and references

1 matlab version

2 references
[1] Baoziyang, Yu Jizhou, Yang Shan. Intelligent optimization algorithm and its MATLAB example (2nd Edition) [M]. Electronic Industry Press, 2016
[2] Zhang Yan, Wu Shuigen. MATLAB optimization algorithm source code [M]. Tsinghua University Press, 2017

Keywords: MATLAB Algorithm AI

Added by itbegary on Thu, 23 Sep 2021 06:20:05 +0300