A list,
Genetic Algorithm (GA) is a part of evolutionary computing. It is a computational model that simulates Darwin’s Genetic selection and natural selection of biological evolution process. It is a method to search for optimal solution by simulating natural evolution process. The algorithm is simple, universal, robust and 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 traditional optimization algorithm, it has the following characteristics: (1) The encoding of decision variables is taken as the operation object. Traditional optimization algorithms often directly use the actual value of the decision variable itself to optimize the calculation, but genetic algorithm uses a certain form of the decision variable encoding as the operation object. This method of encoding decision variables makes it possible for us to use the concepts of chromosomes and genes in biology for reference in optimization calculation, to imitate the genetic and evolutionary incentives of organisms in nature, and to easily apply genetic operators. (2) Directly use fitness as search information. The traditional optimization algorithm not only needs to use the value of the objective function, but also needs to satisfy the requirement of “the derivative of the objective function must exist” in order to determine the search direction. Genetic algorithm can only use the fitness function value transformed from the objective function value to determine the further search range, without the derivative value of the objective function and other auxiliary information. The objective function value or individual fitness value can be directly used to concentrate the search scope into the search space with higher fitness, so as to improve the search efficiency. (3) Search information of multiple points is used with implicit parallelism. Traditional optimization algorithms usually start from an initial point in the solution space to search the optimal solution iteratively. The search information provided by a single point is not much, so the search efficiency is not high, and there may be local optimal solution and stagnation. Genetic algorithms start the search process for optimal solutions from an initial population consisting of many individuals rather than from a single individual. The operation of selection, crossover and mutation on the initial population produces a new generation of population, which contains a lot of population information. This information can avoid searching some unnecessary points, so as to avoid falling into the local optimal solution and gradually approach the global optimal solution. (4) Use probabilistic search rather than deterministic rules. Traditional optimization algorithms often use deterministic search methods, the transfer of a search point to another search point has a certain direction and transfer relationship, such deterministic search may not reach the optimal shop, limit the scope of application of the algorithm. Genetic algorithm (GA) is a kind of adaptive search technology. Its selection, crossover, mutation and other operations are carried out in a probabilistic way, which increases the flexibility of the search process, and can converge to the optimal solution with a large probability, and has a good global optimization capability. However, crossover probability, mutation probability and other parameters can also affect the search results and search efficiency of the algorithm, so how to choose the parameters of genetic algorithm is a relatively important problem in its application. To sum up, genetic algorithm provides a general framework for solving complex system problems because the overall search strategy and optimal search mode of genetic algorithm do not depend on gradient information or other auxiliary knowledge in calculation, but only require the solution of objective function that affects the search direction and the corresponding fitness function. It is not dependent on the specific domain of the problem and has strong robustness to the type of the problem, so it is widely used in a variety of fields, including: function optimization, combinatorial optimization production scheduling problem, automatic control, robotics, image processing (image restoration, image edge feature extraction……) Artificial life, genetic programming, machine learning.
Simple Genetic Algorithms (SGA) only uses selection operator, crossover operator and mutation operator. It is the basis of other Genetic Algorithms because of its Simple evolution process.
3.1 The basic process of genetic algorithm generates a number of initial populations encoded by a certain length (length is related to the accuracy of the problem to be solved) in a random way; Each individual was evaluated by fitness function, and the individuals with high fitness were selected to participate in genetic operation, while the individuals with low fitness were eliminated. The collection of genetically manipulated individuals (replication, crossover, mutation) forms a new generation of population until the stop criterion (evolutionary algebra GEN>=?) is satisfied. ; The best cashed individual in the offspring is taken as the execution result of the genetic algorithm.
3.2 Implementation technology of Genetic Algorithm Basic genetic algorithm (SGA) is composed of coding, fitness function, genetic operator (selection, crossover, variation) and operating parameters. 3.2.1 Encoding (1) Binary encoding The length of the string encoded in binary is related to the accuracy of the problem solved. It is necessary to ensure that every individual in the solved space can be coded. Disadvantages: large length (2) Other coding methods gray code, floating point coding, symbol coding, multi-parameter coding, etc. 3.2.2 Fitness function Fitness function should effectively reflect the gap between each chromosome and the optimal solution of the problem chromosome. 3.2.3 Selecting the operator
In terms of the ability to generate new individuals in the process of genetic algorithm, crossover operation is the main method to generate new individuals, which determines the global search ability of genetic algorithm. Mutation operation is only an auxiliary method to generate new individuals, but it is also an essential operation step, which 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, so that the genetic algorithm can complete the optimization process with good search performance.
3.2.6 Operating Parameters
Ii. Source code
clear all;
clc;
format short g;
global D;
global q;
global q1;
global ss;
global E;
global L;
global ELL;
% test=xlsread('test.xlsx'.1);
%
% position=test(:,2:3);
% data=[
% 100 100 0 0 0 40
% 60 100 10 0.2 0 3
% 20 110 15 0.3 0 4
% 160 150 21 0.3 1 6
% 160 110 16 0.4 0 4
% 30 20 25 0.3 1 4
% 100 60 22 0.2 0 6
% 100 170 15 0.1 0 5
% 30 10 12 0.4 0 6
% 60 50 15 0.3 1 7
% 160 160 20 0.2 0 6
% 50 140 23 0.3 0 6];
position=[18.70 15.29
16.47 8.45
20.07 10.14
19.39 13.37
25.27 14.24
22.00 10.04
25.47 17.02
15.79 15.10
16.60 12.38
14.05 18.12
17.53 17.38
23.52 13.45
19.41 18.13
22.11 12.51
11.25 11.04
14.17 9.76
24.00 19.89
12.21 14.50]; % D D= squareForm (pdist(position(:,1:2),'euclidean')); % vehicle cost per vehicle: h % Fixed cost per vehicle: r. % vehicle speed v; % Maximum vehicle load Qmax. h=1; R=10; v=1; Qmax=200; epsilon=0.001;
R0=2; R1=0.8; % Vehicle travel time matrix T T=D/v between distribution center and demand points; % Maximum number of iterations Iter=30; % number of drops N N=size(position,1); % Speed update parameter: av=1; bv=0.01; cv=1; % soil volume update parameter: as=1; bs=0.01; cs=1; % Local soil renewal weight coefficient alpha=0.9; % Global soil renewal weight beta=0.9; % Initial amount of soil between any two points Initsoil Initsoil=1000; % initial soil mass matrix W?? W=ones(N)*1000; % Initial speed of each drop InitVel; % InitVel=100;
InitVel=randperm(100.1); % Global optimal objective function value TotalZ=1000000; % TotalRoute=[]; % main program t=0;
WaterDrop(1,N)=struct('SW', [],... % initial soil amount matrix corresponding to water droplets'Source', [],... The starting point of water droplets is1; Distribution center'Target', [],... %'VisitNode', [],... % Sequence of points visited (access path)'UnvisitNode', [],... % A collection of unaccessed points'Vel', [],... % Initial velocity of the drop'Soil', [],... % Initial amount of soil carried by water droplets'Q', [],... % The amount of water droplets loaded at departure'S', [],... % The time when the drop reaches source(k)'ZZ', [],... % The initial value of the object function corresponding to the drop'FK'[]); FV % q=test(:,4); % q1=TestData(:,5);
q=[0 6 5 11 6 3 8 5 6 4 5 7 6 10 9 4 7 8 ]';
% q1=[0 3.6 2 4.6 3.6 2.4 4.8 3 3.6 2.4 3 4.2 3.6 4 5.4 2.6 2.4 3]';
% ss=test(:,7); % Service time per demand point ss=[0 1.8 1.0 2.3 1.8 1.2 2.4 1.5 1.8 1.2 1.5 2.1 1.8 2.0 2.7 1.3 1.2 1.5]'; E=[0 5.0 4 1 2.0 5 2 1 3 1 2 2.0 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1;
L=[40 20 15 20 20 15 18 24 27 20 16 20 10 25 28 24.0 20 23]'; % % E=test(:,5); % L=test(:,6); % L=test(:,6); % Upper limit of time window for each demand point ELL=L-E; % EP=test(:,8); % LP=test(:,9); I=1:N; while t < Iter clc fprintf('The %d evolution \n',t+1); % Set the initial dynamic variable: % The optimal objective function value of this iteration Z=1000000; % Optimal path of this iteration Route=[];for k=1:N
WaterDrop(k).SW=W;
WaterDrop(k).Source=1;
WaterDrop(k).VisitNode=[1]; WaterDrop(k).UnvisitNode=I; WaterDrop(k).Vel= InitVel; % Initial amount of Soil carried by water droplets WaterDrop(k).soil =0; % WaterDrop(k).q (WaterDrop(k).source)=0; % The time when the drop reaches source(k); WaterDrop(k).S(WaterDrop(k).Source)=0; % Initial value of the objective function corresponding to the KTH drop WaterDrop(k).zz =0;
end
for k=1:N
while WaterDrop(k).Source~=1 || ~isequal(WaterDrop(k).UnvisitNode,[1])
WaterDrop(k).FK=[];
if WaterDrop(k).Source= =1
alt=2;
else
alt=1;
end
fori=alt:length(WaterDrop(k).UnvisitNode) WaterDrop(k).Q(WaterDrop(k).UnvisitNode(i))=WaterDrop(k).Q(WaterDrop(k).Source)+q(WaterDrop(k).UnvisitNode(i)); % Judge whether the load of point I is less than the maximum load of the vehicle and whether the time to reach point I is within the time window required by point Iif WaterDrop(k).Q(WaterDrop(k).UnvisitNode(i))<Qmax;
WaterDrop(k).FK=[WaterDrop(k).FK,WaterDrop(k).UnvisitNode(i)];
end
end
% for i=alt:N
% if ismember(i,WaterDrop(k).UnvisitNode)
% % ifsum(ismember(WaterDrop(k).UnvisitNode,i)) % WaterDrop(k).Q(i)=WaterDrop(k).Q(WaterDrop(k).Source)+q(i); % WaterDrop(k).S(i)=WaterDrop(k).S(WaterDrop(k).Source)+ss(WaterDrop(k).Source)+T(WaterDrop(k).Source,i); % % Determine whether the load at point I is less than the maximum load of the vehicle and whether the time to reach point I is within the time window required by point I %if WaterDrop(k).Q(i)<Qmax && WaterDrop(k).S(i)>=E(i) && WaterDrop(k).S(i)<=L(i)
% WaterDrop(k).FK=[WaterDrop(k).FK,i];
% end
% end
% end
if isempty(WaterDrop(k).FK)
WaterDrop(k).Target=1;
else% Calculate the probability of reaching the next serviceable demand point % Determine whether the minimum amount of soil on the path from source(k) to the next serviceable demand point is less than0
Minsoil=0;
for u=1:length(WaterDrop(k).FK)
ifWaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).FK(u))<Minsoil Minsoil=WaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).FK(u)); End end % Calculate the sum of the function f corresponding to the next service demand point (can increase improvement, adjust the node selection probability) SumF=0;
for u=1:length(WaterDrop(k).FK)
g(WaterDrop(k).Source,WaterDrop(k).FK(u))=WaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).FK(u))-Minsoil;
f(WaterDrop(k).Source,WaterDrop(k).FK(u))=1/ (0.01+g(WaterDrop(k).Source,WaterDrop(k).FK(u))); SumF=SumF+f(WaterDrop(k).Source,WaterDrop(k).FK(u)); End % Find the probability corresponding to service demand point P=[]; U=[];for u=1:length(WaterDrop(k).FK) P=[P,f(WaterDrop(k).Source,WaterDrop(k).FK(u))/SumF]; U=[U,WaterDrop(k).FK(u)]; WaterDrop(k).Target= u (RoutedGame(P)); WaterDrop(k). Vel=WaterDrop(k).vel +av/(bv+ CV *WaterDrop(k).sw (WaterDrop(k).source,WaterDrop(k).target)^2); Maxtime=max(epsilon,WaterDrop(k).Vel); % TT(WaterDrop(k).source,WaterDrop(k).target)=D(WaterDrop(k).source,WaterDrop(k).target)/Maxtime; DeltaSW(WaterDrop(k).source,WaterDrop(k).target)= as/(bs+cs*TT(WaterDrop(k).source,WaterDrop(k).target)^2); WaterDrop(k).sw (WaterDrop(k).source,WaterDrop(k).target)=... (1-alpha)*WaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).Target)-alpha*DeltaSW(WaterDrop(k).Source,WaterDrop(k).Target); WaterDrop(k).soil =WaterDrop(k).soil +DeltaSW(WaterDrop(k).source,WaterDrop(k).target); Penalty coefficient % cfe1=0;
% cfe2=0;
% cfe0=0; WaterDrop(k).S(WaterDrop(k).Target)=WaterDrop(k).S(WaterDrop(k).Source)+ss(WaterDrop(k).Source)+T(WaterDrop(k).Source,Wa terDrop(k).Target); %if WaterDrop(k).S(WaterDrop(k).Target)<E
% cfe1=EP(WaterDrop(k).Target)*abs(E-WaterDrop(k).Target);
% elseif WaterDrop(k).S(WaterDrop(k).Target)>L
% cfe1=LP(WaterDrop(k).Target)*abs(WaterDrop(k).Target-L);
% end
% cfe0=cfe1+cfe2;
if WaterDrop(k).Target= =1% (Ordered collection) Distribution vehicle returns to the distribution center WaterDrop(k).visitNode =[WaterDrop(k).visitnode,WaterDrop(k).target]; % added the fixed cost of using one vehicle to the objective function (represents the loop formed for one vehicle) WaterDrop(k).ZZ=WaterDrop(k).ZZ+h*D(WaterDrop(k).Source,WaterDrop(k).Target)+D(WaterDrop(k).Source,WaterDrop(k).Target)* (R0+R1*(q(WaterDrop(k).Target)))+R; WaterDrop(k).Source=WaterDrop(k).Target; WaterDrop(k).Q(WaterDrop(k).Source)=0;
WaterDrop(k).S(WaterDrop(k).Source)=0;
Copy the code3. Operation results
Fourth, note
Version: 2014 a