Coevolución cooperativa constructiva

El algoritmo coevolutivo cooperativo constructivo (también llamado C3 ⁾ es un algoritmo de optimización global en inteligencia artificial basado en la arquitectura de arranque múltiple del procedimiento de búsqueda adaptativa aleatoria voraz (GRASP). ^{[ 1 ] [ 2 ]} Incorpora el algoritmo coevolutivo cooperativo existente (CC). ^{[ 3 ]} El problema considerado se descompone en subproblemas. Estos subproblemas se optimizan por separado mientras intercambian información para resolver el problema completo. Un algoritmo de optimización, generalmente pero no necesariamente un algoritmo evolutivo , está integrado en C3 ^para optimizar esos subproblemas. La naturaleza del algoritmo de optimización integrado determina si el comportamiento de ^{C3 es} determinista o estocástico .

El algoritmo de optimización C3 ^fue diseñado originalmente para la optimización basada en simulación ^{[ 4 ] [ 5 ]} , pero puede utilizarse para problemas de optimización global en general. ^{[ 6 ]} Su ventaja sobre otros algoritmos de optimización, en particular la coevolución cooperativa, radica en su mayor capacidad para manejar problemas de optimización no separables. ^{[ 4 ] [ 7 ]}

Posteriormente se propuso una versión mejorada, denominada Evolución Diferencial Coevolutiva Cooperativa Constructiva Mejorada (C ³ⁱ DE), que elimina varias limitaciones de la versión anterior. Un elemento novedoso de C ³ⁱ DE es la inicialización avanzada de las subpoblaciones. C ³ⁱ DE optimiza inicialmente las subpoblaciones de forma parcialmente coadaptativa. Durante la optimización inicial de una subpoblación, solo se considera un subconjunto de los demás subcomponentes para la coadaptación. Este subconjunto aumenta gradualmente hasta que se consideran todos los subcomponentes. Esto hace que C ³ⁱ DE sea muy eficaz en problemas de optimización global a gran escala (hasta 1000 dimensiones) en comparación con el algoritmo coevolutivo cooperativo (CC) y la evolución diferencial . ^{[ 8 ]}

El algoritmo mejorado se ha adaptado posteriormente para la optimización multiobjetivo . ^{[ 9 ]}

Como se muestra en el pseudocódigo a continuación, una iteración de C3 ^consta de dos fases. En la Fase I, la fase constructiva, se construye una solución factible para todo el problema de forma gradual, considerando un subproblema diferente en cada paso. Tras el último paso, se consideran todos los subproblemas y se ha construido una solución para el problema completo. Esta solución construida se utiliza como solución inicial en la Fase II, la fase de mejora local. El algoritmo CC se emplea para optimizar aún más la solución construida. Un ciclo de la Fase II incluye la optimización de los subproblemas por separado, manteniendo los parámetros de los demás subproblemas fijos a una solución central de referencia. Una vez hecho esto para cada subproblema, las soluciones encontradas se combinan durante un paso de "colaboración", y la mejor de las combinaciones producidas se convierte en la solución de referencia para el siguiente ciclo. En el siguiente ciclo, se repite el mismo proceso. La Fase II, y por lo tanto la iteración actual, finaliza cuando la búsqueda del algoritmo CC se estanca y no se encuentran soluciones significativamente mejores. Entonces, se inicia la siguiente iteración. Al inicio de la siguiente iteración, se construye una nueva solución factible, utilizando las soluciones encontradas durante la Fase I de la (s) iteración(es) anterior(es) . Esta solución construida se utiliza como solución inicial en la Fase II, del mismo modo que en la primera iteración. Este proceso se repite hasta que se alcanza alguno de los criterios de finalización de la optimización, por ejemplo, un número máximo de evaluaciones.

{ S fase1 } ← ∅ mientras no se cumplan los criterios de terminación hacer si { S fase1 } = ∅ entonces { S fase1 } ← SubOpt(∅, 1) fin si mientras p fase1 no esté completamente construida hacer p fase1 ← GetBest({ S fase1 }) { S fase1 } ← SubOpt( p fase1 , i siguiente subproblema ) fin mientras p fase2 ← GetBest({ S fase1 }) mientras no estancado hacer { S fase2 } ← ∅ para cada subproblema i hacer { S fase2 } ← SubOpt( p fase2 ,i) fin para { S fase2 } ← Collab({ S fase2 }) p fase2 ← GetBest({ S fase2 }) fin mientras fin mientras

La versión multiobjetivo del algoritmo ^{C3 [ 9 ]} es un algoritmo basado en Pareto que utiliza la misma estrategia de divide y vencerás que el algoritmo de optimización monoobjetivo C3 ^. El algoritmo comienza nuevamente con optimizaciones iniciales constructivas avanzadas de las subpoblaciones, considerando un subconjunto creciente de subproblemas. El subconjunto aumenta hasta incluir el conjunto completo de todos los subproblemas. Durante estas optimizaciones iniciales, la subpoblación del último subproblema incluido evoluciona mediante un algoritmo evolutivo multiobjetivo. Para los cálculos de aptitud de los miembros de la subpoblación, se combinan con una solución colaboradora de cada una de las subpoblaciones optimizadas previamente. Una vez optimizadas inicialmente todas las subpoblaciones de los subproblemas, el algoritmo de optimización multiobjetivo C3 ^continúa optimizando cada subproblema de forma rotativa , pero ahora las soluciones colaboradoras de las subpoblaciones de todos los demás subproblemas se combinan con el miembro de la subpoblación que se está evaluando. La solución colaboradora se selecciona aleatoriamente de entre las soluciones que conforman el frente de Pareto óptimo de la subpoblación. La asignación de aptitud a las soluciones colaboradoras se realiza de forma optimista (es decir, un valor de aptitud "antiguo" se reemplaza cuando el nuevo es mejor).

El algoritmo de coevolución cooperativa constructiva se ha aplicado a diferentes tipos de problemas, por ejemplo, un conjunto de funciones de referencia estándar, ^{[ 4 ] [ 6 ]} optimización de líneas de prensado de chapa metálica ^{[ 4 ] [ 5 ]} y estaciones de producción interactivas. ^{[ 5 ]} El algoritmo C ³ se ha integrado, entre otros, con el algoritmo de evolución diferencial ^{[ 10 ]} y el optimizador de enjambre de partículas ^{[ 11 ]} para las optimizaciones de subproblemas.

• Coevolución cooperativa
• Metaheurística
• Búsqueda estocástica
• Evolución diferencial
• Inteligencia de enjambre
• Algoritmos genéticos
• Hiperheurísticas