DesignBuilder Fundamentos técnicos de la optimización
Cómo funciona
DesignBuilder utiliza un algoritmo genético (GA), también llamado algoritmo evolutivo (EA), basado en el método NSGA2 (NSGA-II), Deb et al. 2002. Es un método multiobjetivo rápido y elitista ampliamente utilizado que ofrece un buen equilibrio entre convergencia y distribución de las soluciones. NSGA2 emplea ordenación no dominada, eficaz para clasificar objetivos contrapuestos. Una limitación del NSGA2 original es que no gestiona eficientemente las restricciones. JEA la aborda mediante clasificación estocástica, que funciona así:
- Primero se inicializa la población aleatoriamente.
- Los cromosomas, o variantes de diseño, se ordenan y agrupan en frentes según conjuntos no dominados de Pareto. Dentro de un frente se clasifican por distancias euclídeas entre soluciones o I-dist, término de NSGA2. En general se prefieren soluciones alejadas de otras para crear un conjunto diverso y evitar la concentración.
- Se seleccionan los mejores diseños de la población actual y se colocan en un grupo de reproducción.
- En el grupo de reproducción se realizan la selección por torneo, el cruce y el apareamiento.
- Se combinan el grupo de reproducción y la población actual. Se ordena el conjunto resultante y los mejores cromosomas pasan a la nueva población.
- Vuelve al paso 2 salvo que se haya alcanzado la convergencia.
- El conjunto de soluciones es el conjunto no dominado de Pareto mejor clasificado de todas las poblaciones.
Restricciones
Implementación de restricciones en JEA
La gestión de restricciones recibe mucha atención de los diseñadores de algoritmos. Su eficiencia se mide tanto por la rapidez con que se encuentran soluciones viables como por su calidad. Una presión excesiva para cumplir restricciones puede dificultar la búsqueda de mejores valores objetivo; una presión demasiado débil puede desperdiciar tiempo en soluciones no viables. El equilibrio depende del problema, por lo que puede no existir una estrategia perfecta. JEA utiliza una estrategia robusta y adaptable llamada clasificación estocástica (Runarsson y Yao, 2000).
La clasificación estocástica es una estrategia probabilística para ordenar soluciones con distintos valores de objetivos y restricciones. Su forma original está diseñada para un objetivo frente a una restricción. Para utilizarla con NSGA-II se siguen estos pasos:
- Todas las restricciones se normalizan y agregan para medir la inviabilidad o incumplimiento como un valor en [0, 1].
- La inviabilidad se utiliza como objetivo adicional y se ordena con los demás objetivos mediante clasificación no dominada. Esto produce un orden inicial de todas las soluciones.
- La clasificación estocástica se aplica a la posición inicial de cada solución, tratada como su valor objetivo, y a su inviabilidad agregada. Así se obtiene la clasificación final.
La ventaja de este sistema es que funciona con cualquier número de objetivos, incluido uno solo, y restricciones, así como con problemas sin restricciones. Puedes utilizar el parámetro de sesgo de objetivo para controlar la presión hacia la viabilidad.
Dos parámetros de configuración afectan directamente al comportamiento de NSGA2 con clasificación estocástica. Sesgo de objetivos controla el sesgo entre la clasificación de Pareto y las puntuaciones de inviabilidad. Un valor de cero significa que se prefiere una solución con menor inviabilidad independientemente de su clasificación de Pareto. Tolerancia de elitismo controla si las soluciones no viables pueden seleccionarse como élite, véase más abajo. Un valor positivo, por ejemplo 0.1, permite seleccionar soluciones con puntuaciones de inviabilidad de hasta 0.1 como élite.
Implementación de restricciones en Open Beagle
Los márgenes inferior y superior se utilizan en el método de gestión de restricciones de DesignBuilder, basado en una función de penalización genérica. Durante una optimización con restricciones, cada alternativa se comprueba frente a las restricciones y se genera una penalización según sea viable o no. Si el valor de la función está dentro del rango viable no se aplica penalización; fuera de él sí. Entre las regiones viable y no viable hay un margen con una penalización linealmente creciente. Los márgenes superior e inferior del cuadro Opciones de cálculo definen estas regiones como se muestra en el gráfico.
Elitismo con archivo de Pareto
Los algoritmos evolutivos son estocásticos. El usuario tiene poco control sobre la dirección o las soluciones que se exploran a continuación. Con frecuencia pueden aparecer soluciones prometedoras en una generación y desaparecer definitivamente en las siguientes. El elitismo conserva buenas soluciones seleccionándolas de un conjunto de soluciones óptimas conocidas y reinsertándolas en la población de trabajo.
En el elitismo con archivo de Pareto se almacenan todas las soluciones conocidas del frente global de Pareto. Forman el conjunto del que el operador de elitismo selecciona las «élites». En JEA pueden controlarse el número máximo de élites y si pueden incluir soluciones no viables. Elitismo global controla el conjunto del que se seleccionan las soluciones de élite. Si es verdadero, valor predeterminado, la selección se realiza en el archivo global; en caso contrario se limita a la población actual. Tolerancia de elitismo explicada anteriormente también afecta al funcionamiento del elitismo.
Bibliografía
- Introducción a los algoritmos genéticos:
- Sean Luke, 2009, Essentials of Metaheuristics, Lulu, disponible gratuitamente en https://cs.gmu.edu/~sean/book/metaheuristics/
- A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing, Springer, Natural Computing Series, Corr. 2nd printing, 2007, ISBN: 978-3-540-40184-1 https://www.cs.vu.nl/~gusz/ecbook/Eiben-Smith-Intro2EC-Ch2.pdf
- Deb, K., Pratap. A, Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transaction on Evolutionary Computation, 6(2), 181-197.