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
Two, some source code
%% includes charging stations1
clc;
clear all
close all
filename='.\evrptw_instances\c101_21.txt';
[NO,type,XCOORD, YCOORD,DEMAND,READY_TIME,DUE_DATE,SERVICE_TIME]=textread(filename,'%s%s%s%s%s%s%s%s'.'headerlines'.1); Empirical solution path K= Randperm (100); % Randomly sort customer points M=30; % Task capacity =200; % timewindows_yuanshi=[str2num(char(READY_TIME))'; str2num(char(DUE_DATE))']; % time window coordinate_yuanshi=[str2num(char(XCOORD)),str2num(char(YCOORD))]; % Coordinate information Coordinate_chongdianzhan =[coordinate_yuanshi(2:22.1)'; Coordinate_yuanshi (2:22, 2) '; ]'; Demand_yuanshi =str2num(char(DEMAND))'; Service_yuanshi =str2num(char(SERVICE_TIME))'; % All service time D=distanse(coordinate_yuanshi); % distance 1 coordinate=[coordinate_yuanshi(1,1),coordinate_yuanshi(K(1:M)+22,1)'; coordinate_yuanshi(1.2),coordinate_yuanshi(K(1:M)+22.2)'; ] '; % Center and customer location timeWindows =[timewindows_yuanshi(1.1),timewindows_yuanshi(1,K(1:M)+22) ;timewindows_yuanshi(1.2),timewindows_yuanshi(2,K(1:M)+22)]; % demand=[demand_yuanshi(1),demand_yuanshi(K(1:M)+22)]; % service=[service_yuanshi(1),service_yuanshi(K(1:M))+22]; % Coordinate_yuanshi1 =[Coordinate_yuanshi (1.1),coordinate_yuanshi(23:end,1)'; Coordinate_yuanshi coordinate_yuanshi (1, 2), (23: end, 2) '; ]';%中心和客户坐标位置
% D1=distanse(coordinate_yuanshi1);%距离
D2=distanse(coordinate);%距离
renwudian1=[1,K(1:M)+1];%包括起点的任务点
Q=77.751111;%电量
r=1;%消耗率
g=0.39;%充电
v=1;%速度
% %% 遗传参数初始化
C=500;%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定
Pc=0.9;%交叉概率
Pm=0.4;%变异概率
popsize=80;%种群数量
%经验公式m=[Σgi /aq]＋1,粗求车辆数
function [ farm ] = crossover( farm,n,k,popsize,Pc )
%CROSSOVER Summary of this function goes here
% Detailed explanation goes here
% ⑴随机产生交叉位，如果在交叉位的外侧两端的父代基因都是0的话，则对父代1
% 进行简单交叉；如果交叉位的外侧两端的父代基因不为0的话，则将左交叉位向左
% 移，直至移动到左交叉位的左端基因为0时停止。以左交叉位为起点，继续向右移
% 动右交叉位，直至右交叉位的右端基因为0为止。这样就保证了父代染色体都用1条
% 子路径来进行交叉。
% ⑵经过第1步操作，子代中仍会产生访问同一客户2次的情况，需要对
% 子代进行整理。在子代中选择那些具有重复情况的自然数，如果该自然数并非
% 在交叉位内的话，则删除之。子代如存在未访问到某一客户的情况，则在染色
% 体的交叉位外补上该客户对应的自然数。
% ⑶经过第2步的操作，如果产生了某一子路径为空的情况，即染色体中含
% 有2个连续的0，须继续进行第3步操作。将其中的1个0与染色体其它位上
% 的客户自然码进行交换。对该客户自然码的要求是该码的前一位与后一位均不
% 为0。本步操作可放在对子代的变异后进行。
function temp = minsert(chrom,num,n)%insert函数，向量中指定位置插入数
%n是要插入的位置（之后）
[x,xx] = size(chrom);
temp = zeros(1,xx+1); %初始化
temp(1,1:n) = chrom(1,1:n);
temp(1,n+1) = num;
temp(1,(n+2):(xx+1)) = chrom(1,(n+1):xx);
end
function temp = mdelete(chrom,n)%delete函数，向量中指定位置删除数
%n是要删除数的坐标
[x,xx] = size(chrom);
temp = zeros(1,xx-1); %初始化
temp(1,1:n-1) = chrom(1,1:n-1);
temp(1,n:xx-1) = chrom(1,(n+1):xx);
end
total = n+k+1;
for i = 1:(popsize/2) %按对进行交叉
if Pc > rand
chromosome1 = zeros(1,total);
chromosome2 = zeros(1,total);
chromosome1 = farm(i,:); %染色体1
chromosome2 = farm(popsize - i + 1,:); %染色体2
%第一步*************************************************************
ran1L = round(rand*(total-3)+2); %随机数1 注意1和最后不要随机到
while chromosome1(1,ran1L) == 0 %不能随机到0
ran1L = round(rand*(total-3)+2);
end
ran1R = ran1L;
ran2L = round(rand*(total-3)+2); %随机数2
while chromosome2(1,ran2L) == 0 %不能随机到0
ran2L = round(rand*(total-3)+2);
end
ran2R = ran2L;
while chromosome1(1,ran1L-1) ~= 0 %左移直至第一个0出现
ran1L = ran1L - 1;
end
while chromosome1(1,ran1R+1) ~= 0 %右移直至第一个0出现
ran1R = ran1R + 1;
end
while chromosome2(1,ran2L-1) ~= 0 %左移直至第一个0出现
ran2L = ran2L - 1;
end
while chromosome2(1,ran2R+1) ~= 0 %右移直至第一个0出现
ran2R = ran2R + 1;
end
%交换片段**********************************************************
temp1 = zeros(1,total); %临时储存
temp2 = zeros(1,total); %临时储存
length1 = ran1R-ran1L+1; %片段长
length2 = ran2R-ran2L+1; %片段长
for ii = 1:length1 %转移到临时储存
temp1(1,ii) = chromosome1(1,ran1L+ii-1);
end
for ii = 1:length2 %转移到临时储存
temp2(1,ii) = chromosome2(1,ran2L+ii-1);
end
chrom1 = zeros(1,total+length2-length1); %中间染色体1
chrom2 = zeros(1,total+length1-length2); %中间染色体2
%重新拼接染色体***************************************************
chrom1(1,1:ran1L-1) = chromosome1(1,1:ran1L-1);
chrom1(1,ran1L:ran1L+length2-1) = temp2(1,1:length2);
chrom1(1,ran1L+length2:total+length2-length1) = chromosome1(1,ran1R+1:total);
chrom2(1,1:ran2L-1) = chromosome2(1,1:ran2L-1);
chrom2(1,ran2L:ran2L+length1-1) = temp1(1,1:length1);
chrom2(1,ran2L+length1:total+length1-length2) = chromosome2(1,ran2R+1:total);
%第二步*************************************************************
nala1 = zeros(1,total);%搜索temp2中有而temp1中没有的数,那个数1中必定重复
nala11 = zeros(1,total);%存放nala中数的位置
nala2 = zeros(1,total);%搜索temp1中有而temp2中没有的数,那个数2中必定重复
nala22 = zeros(1,total);%存放nala中数的位置
%搜索相互没有的数
kk = 1; %nala的下标 好累啊，wwwww......
for ii = 1:length2
flag = 0;
for j = 1:length1
if temp2(1,ii) == temp1(1,j);
flag = 1;
end
end
if flag == 0
nala1(1,kk) = temp2(1,ii);
kk = kk + 1;
end
end
kk = 1; %nala的下标
for ii = 1:length1
flag = 0;
for j = 1:length2
if temp1(1,ii) == temp2(1,j);
flag = 1;
end
end
if flag == 0
nala2(1,kk) = temp1(1,ii);
kk = kk + 1;
end
end
%将多余的数设为0***************************************************
ii = 1;
while nala1(1,ii) ~= 0
[x,xx] = find(chrom1==nala1(1,ii)); %找出重复的位置
j = 1;
while xx(1,j) >= ran1L && xx(1,j) <= ran1L+length2-1
j = j + 1;
end
nala11(1,ii) = xx(1,j); %将重复数的位置保存下来
chrom1(1,xx(1,j)) = 0; %%重复的数变为零
ii = ii + 1;
end
ii = 1;
while nala2(1,ii) ~= 0
[x,xx] = find(chrom2==nala2(1,ii)); %找出重复的位置
j = 1;
while xx(1,j) >= ran2L && xx(1,j) <= ran2L+length1-1
j = j + 1;
end
nala22(1,ii) = xx(1,j); %将重复数的位置保存下来
chrom2(1,xx(1,j)) = 0; %%重复的数变为零
ii = ii + 1;
end
%补上没有的数******************************************************
[xx,x] = size(nonzeros(nala1));%得到nala的大小
[yy,y] = size(nonzeros(nala2));%得到nala的大小
if yy-xx < 0 %交换后变成yy>xx的情况
%交换
[chrom1,chrom2] = exchange(chrom1,chrom2);
[nala1,nala2] = exchange(nala1,nala2);
[nala11,nala22] = exchange(nala11,nala22);
end
% yy-xx > 0 --> 说明变化后1比2短-->1需要补0并且插入,2需要补0并且删0
% yy-xx < 0 --> 说明变化后2比1短-->2需要补0并且插入,1需要补0并且删0
%补0
ii = 1;
while nala11(1,ii) ~= 0
chrom1(1,nala11(1,ii)) = nala2(1,ii);%1中补0
chrom2(1,nala22(1,ii)) = nala1(1,ii);%2中补0
ii = ii + 1;
end
%||||||||stage3|||||||||
%当前ii在下一位的位置
%1插入&2删除*****************************************************
model1 = chrom1; %用来适应变量维度
model2 = chrom2;
j = 1; %!!!!!!!j初始化应该放在while循环外面，小错误不断啊
flag_nala22 = 1;
% %两个chrom的维度是一个问题
% chrom11 = zeros(1,total);
% chrom22 = zeros(1,total);
while nala2(1,ii) ~= 0
%插入，先扩充model->存储变维后的数据；然后chrom扩充，得到model保存的数据
model1 = [model1,0]; %注意顺序
model1 = minsert(chrom1,nala2(1,ii),1);
chrom1 = [chrom1,0];
chrom1 = model1;
%删除0，首先降序排列,用来从后向前删除；之后model变维
while flag_nala22 %又是一个错误，靠，nala22temp每次循环都会被初始化，1次就够了，细心细心，淡定淡定......
nala22temp = zeros(1,total-ii+1);
nala22temp = nala22(1,ii:total);
flag_nala22 = 0;
end
nala22temp = sort(nala22temp);
nala22temp = fliplr(nala22temp);
[q,qq] = size(chrom2);
model2 = zeros(1,qq-1); %注意顺序
model2 = mdelete(chrom2,nala22temp(1,j));
j = j + 1;
chrom2 = zeros(1,qq-1);
chrom2 = model2;
%千万不要忘记迭代+1
ii = ii + 1;
end
farm(i,:) = chrom1;
farm(popsize - i + 1,:) = chrom2;
%在整个算法中，我通过重复的数设0避免了0接着0的情况，很有成就感。
end %交叉概率检测
end %main loop
end %function
Copy the code3. Operation results
Fourth, note
Version: 2014 a