Nsga Ii

NON-DOMINATED SORTING GENETIC ALGORITHM, NSGA-II Representante de la tercera oleada de MOEAs distinguida por el empleo de elitismo en conjuncion con ranking de Pareto (Coello, 2005), el algoritmoNSGA-II (Non-dominated Sorting Genetic Algorithm, version II) fue presentado por K. Deb y sus colegas del Laboratorio de Algoritmos Geneticos del Instituto Tecnologico Kanpur en India en el ano 2000 (Debet al., 2000). Surgio como una version mejorada del algoritmo NSGA creado por Srinivas y Deb (1994), de quien heredo su estructura principal, pero incluyendo caracteristicas distintivas para resolvertres aspectos fuertemente criticados en la comunidad de investigadores sobre el NSGA: el 43 ordenamiento no dominado, la ausencia de elitismo y la dependencia de un parametro externo para aplicar latecnica de fitness sharing (repartición de aptitud). Ya que en nuestro algoritmo esta basado en NSGA-II es preciso explicar mas profundamente su funcionamiento. Empieza inicializando de maneraaleatoria una poblacion P denominada P0 conteniendo a N individuos. La poblacion es ordenada en diferentes capas o clases (en primer lugar los individuos no dominados); la primera clase C1, por lo generalesta compuesta de las soluciones no dominadas o de menor debilidad de P0. La segunda capa C2 contiene las soluciones no dominadas o de menor debilidad en los individuos de {P0} – {C1} y asisucesivamente hasta clasificar a todos los individuos de P0. A cada solucion se le asigna un rank igual al numero de capa en que estan, considerando que son mejores individuos lo que fueron seleccionadosprimeramente. A Pt (donde t tiene un valor inicial de 0) se le aplican los operadores de seleccion por torneo binario, recombinacion y mutacion para crear una poblacion de hijos Ht de tamano N. Despues laspoblaciones Pt y Ht se unen para formar Pt´ (Pt´ = {Pt} U {Ht}) de tamano 2N. La poblacion Pt´ se ordena en capas de acuerdo a los mismos criterios de clasificacion aplicados a Pt; a partir de este...