Michigan-versus-Pittsburg

En algoritmos genéticos se distinguen dos aproximaciones básicas a la representación para la resolución de problemas de optimización combinatoria.

Aprox. Pittsburg: cada individuo contiene una codificación completa de una solución al problema planteado. Una población contiene un conjunto de soluciones (factibles) y los operadores de mutación y cruce tienen que garantizar que el resultado son codificaciones de soluciones (factibles) (cerrados en el espacio de soluciones factibles). La función de fitness evalua una solución y es equivalente/identica a la función de coste a minimizar. La función de selección de los individuos para la siguiente generación es la selección (aleatoria) de las mejores soluciones.

AProx. Michingan: cada individuo contiene la codificación de un elemento de la solución al problema. La población en su conjunto es una codificación de la solución al problema. El tamaño de la población es variable en muchos casos. Los operadores de cruce y mutación son parciales. La función de fitness de un individiuo es una evaluación del impacto que una parte de la solución tiene en la mejora de la solución global. La función de selección tiene que garantizar que la nueva población es una solución al problema. La función de costo a minimizar se evalua sobre toda la población pero no entra en la dinámica del algoritmo, no afecta a los operadores genéticos.

La aproximación Michigan prefiere las representaciones locales y se aproxima a la idea de sistema multiagente con comportamiento colectivo emergente no explícitamente programado. Es mucho más dificil probar la convergencia del algoritmo a soluciones globalmente optimas. Los sistemas de clasificación de Holland originalmente se codificaban de esta manera.

La aproximación Pittsburg es una codificación biologicamente inspirada de un algoritmo de búsqueda global aleatoria. Es posible estudiar su convergencia y se ha probado que si la función de selección es elitista (y los operadores de cruce y mutación garantizan la exploración de todo el espacio) la convergencia al óptimo global está garantizada.