《2022年非常有价值的资料NSGA_matlab遗传算法 .pdf》由会员分享,可在线阅读,更多相关《2022年非常有价值的资料NSGA_matlab遗传算法 .pdf(20页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、MULTI-OBJECTIVEOPTIMIZATIONUSINGEVOLUTIONARYALGORITHMS(MOEA)ARAVINDSESHADRI1. Multi-ObjectiveOptimizationUsingNSGA-IINSGA(Non-DominatedSortingin GeneticAlgorithms5) is a popularnon-dominationbased genetic algorithmfor multi-objectiveoptimization.It is a verye?ectivealgorithmbuthas been generallycrit
2、icizedfor its computationalcom-plexity,lack of elitismand for choosing the optimalparametervalue for sharingparametershare. A modi?edversion, NSGA-II( 3) was developed,which has abettersortingalgorithm, incorporateselitismand no sharing parameterneeds tobe chosen a priori . NSGA-IIis discussed in de
3、tailin thisreportand two sampletest functionsare optimizedusing it.2. GeneralDescriptionofNSGA-IIThe populationis initializedas usual.Once the populationin initializedthepopulationis sorted based on non-dominationinto each front.The ?rst front beingcompletelynon-dominantset in the currentpopulationa
4、nd the second front beingdominatedby the individualsin the ?rst front only and the front goes so on. Eachindividualin the each frontare assigned rank (?tness)values or based on frontinwhich theybelong to.Individualsin ?rst frontare given a ?tness value of 1 andindividualsin second are assigned ?tnes
5、s value as 2 and so on.In additionto ?tness value a new parametercalled crowdingdistanceis cal-culatedfor each individual.The crowdingdistanceis a measure of how close anindividualis to its neighbors.Large average crowding distance will result in betterdiversityin the population.Parents are selected
6、 from the populationby using binarytournamentselectionbased on the rank and crowdingdistance.An individualis selected in the rank islesser than the other or if crowdingdistance is greater than the other1. The selectedpopulationgenerates o?springs from crossover and mutationoperators,which willbe dis
7、cussed in detailin a later section.The populationwith the currentpopulationand currento?springs is sorted againbased on non-dominationand only the best N individualsare selected, where N isthe populationsize. The selection is based on rank and the on crowdingdistanceon the last front.3. DetailedDesc
8、riptionofNSGA-II3.1. PopulationInitialization.The populationis initializedbased on the prob-lem range and constraintsif any.NSGA因为计算复杂度, 缺乏优越性以及选择最优的共享函数而受到批评,NSGA-2 是一种更好的排序算法, 结合了优越性以及不需要事先选择共享参数等优点.适应值分配方案大的拥挤距离会带来种群的多样性名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -
9、 第 1 页,共 20 页 - - - - - - - - - 2ARA VINDSESHADRI3.2. Non-Dominatedsort.The initializedpopulationis sortedbased on non-domination2. The fast sort algorithm3 is describedas below for each? for each individualp in main populationP do the following InitializeSp= ?.This set wouldcontainall the individua
10、lsthatisbeing dominatedby p. Initializenp= 0. This would be the number of individualsthatdomi-nate p. for each individualq in P? if p dominatedq thenadd q to the set Spi.e. Sp= Sp q? else if q dominatesp thenincrementthe dominationcounterfor p i.e. np= np+ 1 if np= 0 i.e.no individualsdominatep then
11、 p belongs to the ?rstfront;Set rank of individualp to one i.e prank= 1.Updatethe ?rstfrontset by adding p to frontone i.e F1= F1 p? Thisis carried out for all the individualsin main populationP .? Initializethe frontcounter to one. i = 1? followingis carried out while the ithfront is nonemptyi.e. F
12、i= ? Q = ?. The set for storing the individualsfor (i + 1)thfront. for each individualp in front Fi? for each individualq in Sp(Spis the set of individualsdominatedby p)nq= nq- 1, decrement the dominationcount for individualq.if nq=0 then none of the individualsin the subsequentfronts would dominate
13、q. Hence set qrank= i + 1. Updatethe set Q withindividualq i.e. Q = Q q. Incrementthe frontcounterby one. Now the set Q is the next frontand hence Fi= Q.This algorithmis betterthan the originalNSGA ( 5) since it utilizethe infor-mationabout the set that an individualdominate(Sp) and number of indivi
14、dualsthatdominatethe individual(np).3.3. CrowdingDistance.Once the non-dominatedsort is complete the crowdingdistance is assigned. Since the individualsare selected based on rank and crowdingdistance all the individualsin the populationare assigned a crowding distance value.Crowdingdistanceis assign
15、ed frontwise and comparingthe crowdingdistancebetween two individualsin di?erentfront is meaningless. The crowing distanceiscalculatedas below? For each front Fi, n is the number of individuals. initializethe distance to be zero for all the individualsi.e. Fi(dj) = 0,where j corresponds to the jthin
16、dividualin front Fi. for each objectivefunctionm? Sort the individualsin front Fibased on objectivem i.e.I =sort (Fi,m).拥挤距离对同一层的有效, 而对于不同的层次, 是没有效的.这个地方恰好说反了, 应该是当p 优于q 的时候, 使np自加1; 当q 优于p 的时候, 使 sp 增加元素s名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 20 页 - -
17、- - - - - - - NSGA-II3? Assign in?nitedistance to boundaryvalues for each individualin Fii.e. I (d1) = and I (dn) = ? for k = 2 to (n -1)I (dk) = I (dk) +I (k + 1).m -I (k -1).m2(1 -k)p1,k+ (1 + k)p2,kc2,k=12(c+ 1)c,if 0 1p( ) =1c+2,if 1.Thisdistributioncan be obtainedfroma uniformlysampledrandomnum
18、berubetween (0, 1). cis the distributionindex for crossover3. Thatis (u) =(2 u)12(1 -u)13Thisdeterminehow wellspreadthe childrenwillbe fromtheirparents.拥挤比较算了p小于 q则 : (1) p的层数低于q的层数 ; (2) 如果 p和 q处于同一层时, p的距离大于q的距离名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 2
19、0 页 - - - - - - - - - 4ARA VINDSESHADRIPopulationPool Sizec2005020m+ 1-1,if rk 0.5k=1 -2(1 -rk)1g(x)2)where,g(x) =1 + 9(6i =1xi4Thedecisionspace upperboundand lowerboundfor thatparticularcomponent.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 20 页 - - - - - -
20、- - - NSGA-II50.20.40.60.8100.20.40.60.811.21.4f(x1)f(x2)Pareto Optima for MOP1 (Objective Space Solution)Figure1. MOP1PopulationPool Sizec20010020名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 20 页 - - - - - - - - - 6ARA VINDSESHADRI00.511.52 01200.20.40.60.81
21、1.21.41.6f(x2)MOP2 using NSGA-IIf(x1)f(x3)Figure2.MOP2:One of the solutionsafter1000 generations(view1)00.511.5200.511.5200.20.40.60.811.21.41.6f(x1)MOP2 using NSGA-IIf(x2)f(x3)Figure3.MOP2:One of the solutionsafter1000 generations(view2)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整
22、理 - - - - - - - 第 6 页,共 20 页 - - - - - - - - - NSGA-II700.511.5200.511.5200.511.52f(x2)MOP2 using NSGA-IIf(x1)f(x3)Figure4.MOP2:One of the solutionsafter1000 generations(view3)PopulationPool Sizec20010020GenerationsTour Sizem1000220Table4.MOP2-Parametersfor NSGA-II(Figures9)PopulationPool Sizec10005
23、00205No simulationwas done to verify名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 20 页 - - - - - - - - - 8ARA VINDSESHADRI00.511.5200.511.5200.511.52f(x1)MOP2 using NSGA-IIf(x2)f(x3)Figure5.MOP2:Second set of the solutionsafter 2000 genera-tions (view 1)00.511
24、.52 00.511.5200.20.40.60.811.21.41.6f(x2)MOP2 using NSGA-IIf(x1)f(x3)Figure6.MOP2:Second of the solutionsafter 2000 generations(view2)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 20 页 - - - - - - - - - NSGA-II9012 00.511.5200.20.40.60.811.21.41.6f(x2)MOP2 usi
25、ng NSGA-IIf(x1)f(x3)Figure7.MOP2:Second of the solutionsafter 2000 generations(view3)00.511.5200.511.5200.511.52f(x2)MOP2 using NSGA-IIf(x1)f(x3)Figure8.MOP2:Second of the solutionsafter 2000 generations(view4)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 20 页
26、 - - - - - - - - - 10ARA VINDSESHADRI00.511.5200.511.5200.511.52f(x1)MOP2 using NSGA-IIf(x2)f(x3)Figure9.MOP2:Anotherset of the solutions after 1000 gener-ations (view1)00.511.500.511.500.511.5f(x2)MOP2 using NSGA-IIf(x1)f(x3)Figure10. MOP2:Modi?edsolutionsafter1000 generations(view1)名师资料总结 - - -精品资
27、料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 20 页 - - - - - - - - - NSGA-II1100.511.500.20.40.60.811.21.400.20.40.60.811.21.4f(x2)MOP2 using NSGA-IIf(x1)f(x3)Figure11. MOP2:Modi?edsolutionsafter1000 generations(view2)00.511.500.511.500.511.5f(x2)MOP2 using NSGA-IIf(x1)f(x3
28、)Figure12. MOP2:Modi?edsolutionsafter1000 generations(view3)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页,共 20 页 - - - - - - - - - 12ARA VINDSESHADRI00.511.500.511.500.20.40.60.811.21.4f(x2)MOP2 using NSGA-IIf(x1)f(x3)Figure13. MOP2:Modi?edsolutionsafter1000 ge
29、nerations(view4)? Occasionallythe crossover operatordidnotresultin a childwithintherange of parents.? For any set of populationthe number of individualswithinany front withmaximumdistancedid not go beyond 5.I assumed thatit should be 6.But I am not able to visualize if the objectivespace dimensiongo
30、 beyond 3.Even though this does not have any relevance to the abilityof the algorithm,while debugging I had to ?nd out if my algorithmwas workingproperlyornot and it took me some time to visualize and ?gure this out.7. PotentialImprovements? The crowdingdistance assignment has to be modi?edso that b
31、etterspreadof solutionis possible.Sometimes in my opiniona betterspread may beachieved if we do not assign in?nitedistanceto the boundarysolutions.This is just my intuitionand I have no simulationresult to substantiateit.? In my opiniona bettergenetic operatorscan be designed speci?callyforNSGA-IIal
32、gorithmso the crowdingoperator will result in a better diversityof individuals.8. SourceCode8.1.FunctionforInitialization.% Initializepopulation% functionf= initialize_variables(N,problem)% N -Populationsize% problem-takesintegervalues1 and 2 where,%1 forMOP1%2 forMOP2名师资料总结 - - -精品资料欢迎下载 - - - - -
33、- - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页,共 20 页 - - - - - - - - - NSGA-II13% ThisfunctioninitializesthepopulationwithN individualsand each% individualhavingM decisionvariablesbasedon theselectedproblem.% M = 6 forproblemMOP1andM = 12 forproblemMOP2. The objectivespace% forMOP1is2 dimens
34、ionalwhileforMOP2is3 dimensional.functionf= initialize_variables(N,problem)% BoththeMOP s giveninHomework # 5 has 0 to1 asitsrangeforallthe% decisionvariables.min = 0;max = 1;switchproblemcase 1M = 6;K = 8;case 2M = 12;K = 15;end fori= 1 :N% Initializethedecisionvariablesforj= 1 :Mf(i,j)= rand(1);%
35、i.ef(i,j)= min+ (max -min)*rand(1);end% Evaluatetheobjectivefunctionf(i,M+ 1:K)= evaluate_objective(f(i,:),problem);end8.2.Non-DominatedSortandCrowdingDistanceCalculation.%Non-DonimationSort% Thisfunctionsortthecurrentpopultionbasedon non-domination.Allthe% individualsinthefirstfrontaregivena rankof
36、1,thesecondfront% individualsareassignedrank2 andso on.Afterassigningtherankthe% crowdingineachfrontiscalculated.functionf= non_domination_sort_mod(x,problem)N,M= size(x);switchproblemcase 1M = 2;V = 6;case 2M = 3;V = 12;end front= 1;% Thereisnothingtothisassignment,usedonlytomanipulateeasilyin% MAT
37、LAB.F(front).f= ;individual= ;fori= 1 :N% Number ofindividualsthatdominatethisindividualindividual(i).n= 0;% Individualswhichthisindividualdominateindividual(i).p= ;forj= 1 :Ndom_less= 0;dom_equal= 0;dom_more = 0;fork = 1 :Mif(x(i,V+ k) 1whileisempty(find(candidate(1:j- 1)= candidate(j)candidate(j)=
38、 round(pop*rand(1);ifcandidate(j)= 0candidate(j)= 1;endendendendforj= 1 :tour_sizec_obj_rank(j)= chromosome(candidate(j),rank);c_obj_distance(j)= chromosome(candidate(j),distance);endmin_candidate= .find(c_obj_rank= min(c_obj_rank);iflength(min_candidate)= 1max_candidate= .find(c_obj_distance(min_ca
39、ndidate)= max(c_obj_distance(min_candidate);iflength(max_candidate)= 1max_candidate= max_candidate(1);endf(i,:)= chromosome(candidate(min_candidate(max_candidate),:);elsef(i,:)= chromosome(candidate(min_candidate(1),:);endend8.4.GeneticOperator.functionf= genetic_operator(parent_chromosome,pro,mu,mu
40、m);N,M= size(parent_chromosome);switchprocase 1M = 2;V = 6;case 2M = 3;V = 12;end p = 1;was_crossover= 0;was_mutation= 0;l_limit= 0;u_limit= 1;fori= 1 :Nifrand(1) 0.9child_1= ;child_2= ;parent_1= round(N*rand(1);ifparent_1 1parent_1= 1;endparent_2= round(N*rand(1);ifparent_2 1parent_2= 1;名师资料总结 - -
41、-精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页,共 20 页 - - - - - - - - - 16ARA VINDSESHADRIendwhileisequal(parent_chromosome(parent_1,:),parent_chromosome(parent_2,:)parent_2= round(N*rand(1);ifparent_2 1parent_2= 1;endendparent_1= parent_chromosome(parent_1,:);parent_2= pa
42、rent_chromosome(parent_2,:);forj= 1 :V%SBX (SimulatedBinaryCrossover)% Generatea randomnumberu(j)= rand(1);ifu(j) u_limitchild_1(j)= u_limit;elseifchild_1(j) u_limitchild_2(j)= u_limit;elseifchild_2(j) l_limitchild_2(j)= l_limit;endendchild_1(:,V+ 1:M + V) = evaluate_objective(child_1,pro);child_2(:
43、,V+ 1:M + V) = evaluate_objective(child_2,pro);was_crossover= 1;was_mutation= 0;elseparent_3= round(N*rand(1);ifparent_3 1parent_3= 1;end% Make surethatthemutationdoes notresultinvariablesoutof% thesearchspace.ForboththeMOP stherangefordecisionspace% is0,1.Incasedifferentvariableshavedifferentdecisi
44、on% spaceeachvariablecan be assigneda range.child_3= parent_chromosome(parent_3,:);forj= 1 :Vr(j)= rand(1);ifr(j) u_limitchild_3(j)= u_limit;elseifchild_3(j) popremaining= pop -previous_index;temp_pop= .sorted_chromosome(previous_index+ 1 :current_index,:);temp_sort,temp_sort_index= .sort(temp_pop(:
45、,M + V + 2), descend );名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页,共 20 页 - - - - - - - - - 18ARA VINDSESHADRIforj= 1 :remainingf(previous_index+ j,:)= temp_pop(temp_sort_index(j),:);endreturn;elseifcurrent_index popf(previous_index+ 1 :current_index,:)= .sor
46、ted_chromosome(previous_index+ 1 :current_index,:);elsef(previous_index+ 1 :current_index,:)= .sorted_chromosome(previous_index+ 1 :current_index,:);return;endprevious_index= current_index;end8.7.MainFunctionNSGA-II.%MainScript% Main programtoruntheNSGA-IIMOEA.% initialize_variableshas twoarguments;
47、Firstbeingthepopulationsize% and thesecondtheproblemnumber.1 correspondstoMOP1and2% correspondstoMOP2.%Initializethevariables% Declarethevariablesand initializetheirvalues% pop -population% gen -generations% pro-problemnumberfunctionnsga_2();pop = 500;gen = 1000;pro= 2;switchprocase1M = 2;V = 6;case
48、 2M = 3;V = 12;endchromosome= initialize_variables(pop,pro);%Sorttheinitializedpopulation% Sortthepopulationusingnon-domination-sort.Thisreturnstwocolumns% foreachindividualwhicharetherankand thecrowdingdistance% correspondingtotheirpositioninthefronttheybelong.chromosome= non_domination_sort_mod(ch
49、romosome,pro);fori= 1 :gen%Selecttheparents% Parentsareselectedforreproductiontogenerateoffspringd.The% originalNSGA-IIusesa binarytournamentselectionbased on the% crowded-comparisionoperator.The argumentsare% pool-sizeofthematingpool.Itiscommon tohave thistobe halfthe%populationsize.% tour-Tourname
50、ntsize.OriginalNSGA-IIuses a binarytournament%selection,buttosee theeffectoftournamentsizethisiskept%arbitary,tobe choosenby theuser.pool= round(pop/2);tour= 2;parent_chromosome= tournament_selection(chromosome,pool,tour);%PerfromcrossoverandMutationoperator% The originalNSGA-IIalgorithmusesSimulate