A FAST ELITIST MULTIOBJECTIVE GENETIC ALGORITHM: NSGA …

1 A FAST ELITIST MULTIOBJECTIVE GENETIC ALGORITHM: NSGA-IIARAVIND optimization Using NSGA-IINSGA ( [5]) is a popular non-domination based GENETIC algorithm for multi-objective optimization . It is a very effective algorithm but has been generallycriticized for its computational complexity, lack of elitism and for choosing theoptimal parameter value for sharing parameter share. A modified version, NSGA-II ( [3]) was developed, which has a better sorting algorithm , incorporates elitismand no sharing parameter needs to be chosena priori. NSGA-II is discussed indetail in Description of NSGA-IIThe population is initialized as usual. Once the population in initialized thepopulation is sorted based on non-domination into each front. The first front beingcompletely non-dominant set in the current population and the second front beingdominated by the individuals in the first front only and the front goes so on.

2 Eachindividual in the each front are assigned rank (fitness) values or based on front inwhich they belong to. Individuals in first front are given a fitness value of 1 andindividuals in second are assigned fitness value as 2 and so addition to fitness value a new parameter calledcrowding distanceis cal-culated for each individual. The crowding distance is a measure of how close anindividual is to its neighbors. Large average crowding distance will result in betterdiversity in the are selected from the population by using binary tournament selectionbased on the rank and crowding distance. An individual is selected in the rank islesser than the other or if crowding distance is greater than the other1. The selectedpopulation generates offsprings from crossover and mutation operators, which willbe discussed in detail in a later population with the current population and current offsprings is sorted againbased on non-domination and only the bestNindividuals are selected, whereNisthe population size.

3 The selection is based on rank and the on crowding distanceon the last Description of population is initialized based on the prob-lem range and constraints if distance is compared only if the rank for both individuals are same12 ARAVIND initialized population is sorted based on non-domination2. The fast sort algorithm [3] is described as below for each for each individualpin main populationPdo the following InitializeSp= . This set would contain all the individuals that isbeing dominated byp. Initializenp= 0. This would be the number of individuals that domi-natep. for each individualqinP ifpdominatedqthen addqto the {q} else ifqdominatespthen increment the domination counter + 1 ifnp= 0 no individuals dominatepthenpbelongs to the firstfront; Set rank of individualpto one 1. Update the firstfront set by addingpto front one {p} This is carried out for all the individuals in main populationP.

4 Initialize the front counter to 1 following is carried out while theithfront is nonempty Q= . The set for storing the individuals for (i+ 1)thfront. for each individualpin frontFi for each individualqinSp(Spis the set of individuals dominatedbyp) nq=nq 1, decrement the domination count for individualq. ifnq= 0 then none of the individuals in the subsequentfronts would dominateq. Hence setqrank=i+ 1. Updatethe setQwith q. Increment the front counter by one. Now the setQis the next front and henceFi= algorithm is better than the original NSGA ( [5]) since it utilize the infor-mation about the set that an individual dominate (Sp) and number of individualsthat dominate the individual (np). the non-dominated sort is complete the crowdingdistance is assigned. Since the individuals are selected based on rank and crowdingdistance all the individuals in the population are assigned a crowding distance distance is assigned front wise and comparing the crowding distancebetween two individuals in different front is meaning less.

5 The crowing distance iscalculated as below For each frontFi,nis the number of individuals. initialize the distance to be zero for all the individuals (dj) = 0,wherejcorresponds to thejthindividual in frontFi. for each objective function m Sort the individuals in frontFibased on (Fi, m).2An individual is said to dominate another if the objective functions of it is no worse than theother and at least in one of its objective functions it is better than the otherNSGA-II3 Assign infinite distance to boundary values for each (d1) = andI(dn) = fork= 2 to (n 1) I(dk) =I(dk) +I(k+ 1).m I(k 1).mfmaxm fminm I(k).mis the value of themthobjective function of thekthindividual inIThe basic idea behind the crowing distance is finding the euclidian distancebetween each individual in a front based on theirmobjectives in themdimensionalhyper space. The individuals in the boundary are always selected since they haveinfinite distance the individuals are sorted based on non-domination andwith crowding distance assigned, the selection is carried out using acrowded-comparison-operator( n).

6 The comparison is carried out as below based on(1)non-domination individuals in frontFiwill have their rankasprank=i.(2)crowding distanceFi(dj) p nqif prank< qrank or ifpandqbelong to the same frontFithenFi(dp)> Fi(dq) thecrowing distance should be individuals are selected by using a binary tournament selection with GA s useSimulated Binary Crossover(SBX)[2], [1] operator for crossover andpolynomial mutation[2], [4]. Binary binary crossover simulates the bi-nary crossover observed in nature and is give as ,k=12[(1 k)p1,k+ (1 + k)p2,k]c2,k=12[(1 + k)p1,k+ (1 k)p2,k]whereci,kis theithchild withkthcomponent,pi,kis the selected parent and k( 0) is a sample from a random number generated having the densityp( ) =12( c+ 1) c,if 0 1p( ) =12( c+ 1)1 c+2,if > distribution can be obtained from a uniformly sampled random numberubetween (0,1). cis the distribution index for crossover3.

7 That is (u) =(2u)1( +1) (u) =1[2(1 u)]1( +1)3 This determine how well spread the children will be from their + (puk plk) kwhereckis the child andpkis the parent withpukbeing the upper bound4onthe parent component,plkis the lower bound and kis small variation which iscalculated from a polynomial distribution by using k=(2rk)1 m+ 1 1,ifrk< k=1 [2(1 rk)]1 m+ 1ifrk an uniformly sampled random number between (0,1) and mis mutationdistribution and offspring population is combined withthe current generation population and selection is performed to set the individualsof the next generation. Since all the previous and current best individuals areadded in the population, elitism is ensured. Population is now sorted based onnon-domination. The new generation is filled by each front subsequently until thepopulation size exceeds the current population size.

8 If by adding all the individualsin frontFjthe population exceedsNthen individuals in frontFjare selected basedon their crowding distance in the descending order until the population size hence the process repeats to generate the subsequent the functionPretty much everything is explained while you execute the code but the mainarguments to get the function running are population and number of these arguments are entered the user would be prompted for number of ob-jective functions and number of decision variables. Also the range for the decisionvariables will have to be entered. Once preliminary data is obtained, the user isprompted to modify theobjective fun and feel free to modify the code to suit your need!References[1]Hans-Georg Beyer and Kalyanmoy Deb. On Self-Adaptive Features in Real-Parameter Evo-lutionary Trabsactions on Evolutionary Computation, 5(3):250 270, June2001.

9 [2]Kalyanmoy Deb and R. B. Agarwal. Simulated Binary Crossover for Continuous Search Systems, 9:115 148, April 1995.[3]Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. A Fast ELITIST Multi-objective GENETIC Algorithm: Transactions on Evolutionary Computation,6(2):182 197, April 2002.[4]M. M. Raghuwanshi and O. G. Kakde. Survey on MULTIOBJECTIVE evolutionary and real codedgenetic algorithms. InProceedings of the 8th Asia Pacific Symposium on Intelligent and Evo-lutionasy Systems, pages 150 161, 2004.[5]N. Srinivas and Kalyanmoy Deb. MULTIOBJECTIVE optimization Using Nondominated Sortingin GENETIC Computation, 2(3):221 248, decision space upper bound and lower bound for that particular component.