Diferencia entre revisiones de «Michigan-versus-Pittsburg»

De Grupo de Inteligencia Computacional (GIC)
Sin resumen de edición
 
Sin resumen de edición
 
Línea 13: Línea 13:
las mejores soluciones.
las mejores soluciones.


AProx. Michingan: cada individuo contiene la codificación deun
AProx. Michingan: cada individuo contiene la codificación de un
elemento de la solución al problema. La población en su conjunto es
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
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
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
mutación son parciales. La función de fitness  de un individiuo es una
Línea 36: Línea 36:
elitista (y los operadores de cruce y mutación garantizan la
elitista (y los operadores de cruce y mutación garantizan la
exploración de todo el espacio) la convergencia  al óptimo global está
exploración de todo el espacio) la convergencia  al óptimo global está
garantizaada.
garantizada.

Revisión actual - 08:53 4 mar 2009

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.