遗传算法 NSGA II

% % function nsgaii() % clear,clc % % nPop=60; % nGen=20; % LowUpDecVar=[-10,10;0,10;]; % flagCrossover=1; % pCrossoverProbablity=0.7; % toleranceNearRelatives=0.0001; % % Chromosome=ReplaceChromosomeNSGAII(nPop,nGen,LowUpDecVar,toleranceNearRelatives,pCrossoverProbablity,flagCrossover) % % plot(Chromosome(:,3),Chromosome(:,4),'r*') % % % function ObjValue=EvaluateObjective(Chromosome) % [x1,x2]=deal2(Chromosome); % y1=x1^4-10*x1^2+x1*x2-x2^4-x1^2*x2^2; % y2=x2^4-x1^2*x2^2-x1^4+x1*x2; % ObjValue=[y1,y2;]; function Chromosome=ReplaceChromosomeNSGAII(nPop,nGen,LowUpDecVar,toleranceNearRelatives,pCrossoverProbablity,flagCrossover,EvaluateObjective) % Copyright (c) 2009, Chen Shengzhao % All rights reserved. % % Redistribution and use in source and binary forms, with or without % modification, are permitted provided that the following conditions are % met: % % * Redistributions of source code must retain the above copyright % notice, this list of conditions and the following disclaimer. % * Redistributions in binary form must reproduce the above copyright % notice, this list of conditions and the following disclaimer in % the documentation and/or other materials provided with the distribution % % THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" % AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE % IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE % ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE % LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR % CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF % SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS % INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN % CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) % ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE % POSSIBILITY OF SUCH DAMAGE. % flagCrossover=0: SBX method; flagCrossover=1: BLX method; nDecVar=size(LowUpDecVar,1); nObj=length(EvaluateObjective(zeros(1,nDecVar))); Chromosome=InitializePopulation(nPop,nObj,LowUpDecVar,EvaluateObjective); Chromosome=NonDominatedSort(Chromosome,nDecVar); nPool=ceil(nPop/2);nTour=2; for iN=1:nGen disp(['进化到第 ',num2str(iN),' 代。']) ChromosomeSeed=TournamentSelection(Chromosome,nPool,nTour); ChildChromosome=GeneticOperator(ChromosomeSeed,nTour,LowUpDecVar,pCrossoverProbablity,flagCrossover,EvaluateObjective); ChildChromosome=KillNearRelatives(ChildChromosome,ChildChromosome,toleranceNearRelatives); ChildChromosome=KillNearRelatives(Chromosome,ChildChromosome,toleranceNearRelatives); ChromosomeNew=[Chromosome;ChildChromosome;]; ChromosomeNew=NonDominatedSort(ChromosomeNew,nDecVar); Chromosome=ChromosomeNew(1:nPop,:); end function Chromosome=InitializePopulation(nPop,nObj,LowUpDecVar,EvaluateObjective) % [1] 吴鹏.MATLAB高效编程技巧与应用：25个案例分析[M].北京航空航天大学出版社.2010.6.p134-151 nDecVar=size(LowUpDecVar,1); Chromosome=zeros(nPop,nDecVar+nObj); for iN=1:nDecVar Chromosome(:,iN)=LowUpDecVar(iN,1)+rand(nPop,1)*(LowUpDecVar(iN,2)-LowUpDecVar(iN,1)); end for iN=1:nPop Chromosome(iN,nDecVar+1:end)=EvaluateObjective(Chromosome(iN,1:nDecVar)); end function Chromosome=NonDominatedSort(Chromosome,nDecVar) % Reference: % [1] Kalyanmoy Deb, Associate Member, IEEE, Amrit Pratap, Sameer Agarwal, % and T. Meyarivan.A Fast and Elitist Multiobjective Genetic Algorithm: % NSGA-II.IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, % APRIL 2002.p182-197. % [2] Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and T Meyarivan.A Fast % Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective % Optimization: NSGA-II. % [3] Deb, K. (1999) Multi-objective genetic algorithms: Problem % difficulties and construction of test Functions. Evolutionary % Computation, 7(3), 205–230. % [4] ARAVIND SESHADRI.A FAST ELITIST MULTIOBJECTIVE GENETIC ALGORITHM: NSGA-II. % [5] Ankita Golchha, Shahana Gajala Qureshi. Non-Dominated Sorting Genetic % Algorithm-II – A Succinct Survey.International Journal of Computer % Science and Information Technologies, Vol. 6 (1) , 2015, 252-255 nPop=size(Chromosome,1); nObj=size(Chromosome,2)-nDecVar; A=zeros(nPop,nPop); A0=1; for iN=nDecVar+1:nDecVar+nObj for jN=1:nPop A(:,jN)=(Chromosome(jN,iN)>=Chromosome(:,iN)); end A0=A0.*(A-eye(nPop)); end % [~,Seq]=sort(sum(A0)); Chromosome=Chromosome(Seq,:) % 本句可以粗略排序，未考虑拥挤度 A0=[transpose(1:nPop),A0]; Seq0=zeros(nPop,1);iSeq=1; CrowdDistance0=Seq0; while ~isempty(A0) DominatedIndex=min(sum(A0(:,2:end)))+1; SeqA0=(sum(A0(:,2:end))<DominatedIndex); Seq=A0(SeqA0,1); [SeqCrowd,CrowdDistance]=getCrowdDistance(Chromosome(Seq,:),nDecVar); CrowdDistance0(iSeq:iSeq+length(Seq)-1)=CrowdDistance; Seq0(iSeq:iSeq+length(Seq)-1)=Seq(SeqCrowd); iSeq=iSeq+length(Seq); A0(SeqA0>0,:)=[]; A0(:,[0,SeqA0]>0)=[]; end Chromosome=Chromosome(Seq0,:); function [SeqCrowd,CrowdDistance]=getCrowdDistance(Chromosome,nDecVar) nPop=size(Chromosome,1); if nPop<1 disp('No chromosome in THIS Rank.');SeqCrowd=[];CrowdDistance=[];return; elseif nPop<3 SeqCrowd=1:nPop;CrowdDistance=Inf*ones(nPop,1);return; end CrowdDistance=zeros(nPop,1); for iN=nDecVar+1:size(Chromosome,2) [ChromosomeNew,Seq]=sort(Chromosome(:,iN)); CrowdDistance(Seq)=CrowdDistance(Seq)+[Inf;(ChromosomeNew(3:end)-ChromosomeNew(1:end-2))/(ChromosomeNew(end)-ChromosomeNew(1)+eps);Inf;]; end [CrowdDistance,SeqCrowd]=sort(CrowdDistance,1,'descend'); function ChromosomeSeed=TournamentSelection(Chromosome,nPool,nTour) SelectedNO=1; while length(SelectedNO)<nPool SelectedNO=unique(min(randi(size(Chromosome,1),nPool,nTour),[],2)); end ChromosomeSeed=Chromosome(SelectedNO,:); function ChildChromosome=GeneticOperator(ChromosomeSeed,nTour,LowUpDecVar,pCrossoverProbablity,flagCrossover,EvaluateObjective) % flagCrossover=0: SBX method; flagCrossover=1: BLX method; nDecVar=size(LowUpDecVar,1); nPop=size(ChromosomeSeed,1); etam=20; N0=nPop*2;iN0=1; ChildChromosome=zeros(N0,size(ChromosomeSeed,2)); for iN=1:nPop if rand(1)<pCrossoverProbablity randRow=randperm(nPop); ParentChromosome=ChromosomeSeed(randRow(1:2),1:nDecVar); ChildChromosome(iN0:iN0+1,1:nDecVar)=CrossoverOperater(ParentChromosome,nDecVar,flagCrossover); iN0=iN0+2; else ParentChromosome=ChromosomeSeed(min(randi(nPop,nTour,1)),1:nDecVar); rk=rand(nDecVar,1); Deltak=(2*rk.*(rk<=0.5)).^(1/(1+etam))-1*(rk<=0.5)+1*(rk>0.5)-(2*(1-rk).*(rk>0.5)).^(1/(1+etam)); ChildChromosome(iN0,1:nDecVar)=ParentChromosome+transpose(LowUpDecVar(:,2)-LowUpDecVar(:,1).*Deltak); iN0=iN0+1; end end ChildChromosome=ChildChromosome(1:iN0-1,:); for iN=1:nDecVar Seq= ChildChromosome(:,iN)<LowUpDecVar(iN,1); ChildChromosome(Seq,iN)=LowUpDecVar(iN,1); Seq=ChildChromosome(:,iN)>LowUpDecVar(iN,2); ChildChromosome(Seq,iN)=LowUpDecVar(iN,2); end for iN0=1:size(ChildChromosome,1) ChildChromosome(iN0,nDecVar+1:end)=EvaluateObjective(ChildChromosome(iN0,1:nDecVar)); end function ChildChromosome=CrossoverOperater(ParentChromosome,nDecVar,flagCrossover) % flagCrossover=0: SBX method; flagCrossover=1: BLX method; etac=20; if flagCrossover<1 u=rand(1,nDecVar); Beta=(2*u.*(u<=0.5)).^(1/(1+etac))+(1/2./(1-u).*(u>0.5)).^(1/(1+etac)); ChildChromosome=[(1-Beta).*ParentChromosome(1,:)+(1+Beta).*ParentChromosome(2,:);(1+Beta).*ParentChromosome(1,:)+(1-Beta).*ParentChromosome(2,:);]/2; else alpha=rand(1); Beta=rand(1,nDecVar)*(1+2*alpha)-