Uso de la evolución diferencial para la optimización combinatoria: Un enfoque general

El algoritmo de Evolución Diferencial (DE) fue propuesto inicialmente para la optimización numérica continua, pero ha sido aplicado con éxito en muchos problemas de optimización combinatoria, particularmente en problemas combinatorios enteros basados en permutaciones. En este artículo, se propone un nuevo y general enfoque para la optimización combinatoria utilizando el algoritmo de Evolución Diferencial. El enfoque propuesto tiene como objetivo preservar su interesante mecanismo de búsqueda para dominios discretos, definiendo la diferencia entre dos soluciones candidatas como una lista diferencial de movimientos en el espacio de búsqueda. Así, se puede producir un operador de mutación diferencial más significativo y general para el contexto de los problemas de optimización combinatoria. Discutimos tres alternativas para usar la lista diferencial de movimientos dentro de la operación de mutación diferencial. Presentamos resultados sobre instancias del Problema del Viajante (TSP) y el Problema de las N-Reinas (NQP) para ilustrar la adecuación del enfoque propuesto para la optimización combinatoria.