Parte II

Algoritmos genéticos

Los Algoritmos Genéticos fueron introducidos por John H. Holland en 1975 inspirándose en el proceso observado en la evolución natural de los seres vivos.
Los Algoritmos Genéticos son métodos estocásticos de búsqueda ciega. En estos, se mantiene a una población que representa a un conjunto de posibles soluciones, la cual es sometida a ciertas transformaciones y a un proceso de selección a favor de los mejores candidatos.
El objetivo principal de un Algoritmo Genético, es evolucionar a partir de una población de soluciones para un determinado problema, intentando producir nuevas generaciones de soluciones que sean mejores que la anterior.
Los algoritmos desarrollados por Holland inicialmente eran sencillos pero dieron buenos resultados en problemas considerados difíciles.

Para llevar a la práctica estos algoritmos hay que especificar los siguientes elementos: 

• Generación: El primer paso es la generación de la población inicial, la cual es creada de forma aleatoria. Generalmente se representan mediante cadenas binarias de longitud L que codifican el problema. Cada cadena es llamada genotipo o cromosoma.
• Evaluación: Cada cadena es evaluada y se le asigna un valor de aptitud (fitness).
  La función de evaluación cuantifica la performace respecto a ciertos parámetros y la función de aptitud transforma el resultado en la posibilidad de reproducción de esa cadena.
• Selección: Son muestreos estocásticos, en los cuales se asigna una probabilidad a cada individuo que se cruzará en la siguiente generación, basándose en el valor de aptitud (fitness). Los criterios más usados en la práctica son: por ruleta, universal y por ranking.
• Selección por ruleta: Cada cadena es representada por un espacio que se corresponde proporcionalmente a su valor de aptitud (fitness). Haciendo "girar la ruleta" repetidas veces las cadenas son seleccionadas utilizando "muestreo estocástico con repeticiones" para completar la población intermedia.
• Selección Universal: La población se ubica en un orden aleatorio, representado por un espacio proporcional a su valor de aptitud, luego se toma una "ruleta" con N cantidad de punteros separados por espacios iguales. Haciendo "girar la ruleta" una sola vez, se obtienen los N miembros de la población intermedia.
• Selección por Ranking: Muchos tipos de selección pueden tener problemas cuando existen grandes diferencias entre los valores de aptitud (fitness). Por ejemplo, si el mejor cromosoma tiene un fitness igual al 90% de la suma de todos los fitness, los otros cromosomas tienen muy poca probabilidad de ser elegidos.
  Se realiza un ranking de la población y se le da al peor cromosoma el valor de fitness 1, al segundo 2, etc. Ahora, todos los cromosomas tiene una oportunidad de ser seleccionados; sin embargo, este método produce una convergencia lenta, ya que los mejores cromosomas no se diferencian mucho del resto.

Cruzamiento

1 #  # 0   |  1 0 1 #                        = #0#1  | # 0 1 1 1

# 0 1 1 1 | #  0 # 1                          = 1 0 1 # |  1 # # 0

Cruzamiento simple: un punto de cruce es seleccionado, desde el principio hasta el punto de cruce es copiado del primer padre, y el resto es copiado del otro padre.

11001011+11011111 = 11001111

Dos puntos de cruzamiento: dos puntos son seleccionados, desde el principio del cromosoma hasta el primer punto de cruce es copiado del primer padre, de ahí hasta el segundo punto de cruce es copiado del segundo padre, y copia lo que le queda (desde el segundo punto de cruce hasta el final) de primer cromosoma.

11001011 + 11011111 = 11011111

Cruzamiento Uniforme: copia bits al azar del primer padre y del segundo.

11001011 + 11011101 = 11011111 

Cruzamiento Aritmético: alguna operación aritmética es empleada para obtener al nuevo descendiente.

11001011 + 11011111 = 11001001 (AND)

Mutación
Inversión de bits: selecciona bits y estos son invertidos (si era un 0 se transforman en 1)

11001001 =>  10001001

Etilismo: consiste en mantener intacto a través de las generaciones al individuo más apto, por lo que no se cruza sino hasta que surge otro individuo mejor que él.

Algoritmos genéticos paralelos

La función de evaluación debe ser relativamente rápida, pero en mucho casos, requiere un tiempo considerable. Se debe evaluar cada cromosoma. La evaluación se puede realizar de manera concurrente para varios cromosomas si se dispone de múltiples procesadores y un canal de comunicación.

Maestro/esclavo

Los cromosomas a evaluar se reparten entre el número de procesadores disponibles. 
Los resultados se reportan al procesador maestro que realiza todas las otras operaciones del algoritmo genético. 
Sólo la evaluación se distribuye entre los diferentes procesadores, las operaciones restantes se efectúan de manera centralizada. 
Esta implementación de algoritmos genéticos paralelos tiene la desventaja de hacer uso intensivo del canal de comunicación.

Algoritmos genéticos paralelos de grano fino/grueso

En este tipo de algoritmos genéticos existen múltiples poblaciones, tantas como procesadores se emplean, donde cada procesador implementa el algoritmo completo sobre una población ubicada en su espacio de memoria.
Las poblaciones evolucionan de manera independiente, hasta que un evento preestablecido acontece, y los mejores cromosomas de cada población emigran hacia las poblaciones
vecinas y substituyen algunos de sus cromosomas.

Grano grueso	Grano fino

Ventajas

• No necesitan conocimientos específicos sobre el problema que intentan resolver.
• Operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales.
• Resulta fácil ejecutarlos en las modernas arquitecturas masivas en paralelo.
• Usan operadores probabilísticos.
• En problemas de optimización, se afectan menos por los máximos locales (falsas soluciones).

Desventajas

• Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen (tamaño de la población, número de generaciones, etc.)
• Pueden converger prematuramente debido a una serie de problemas de diversa índole.

Usos

• Parametrización de sistemas.
• Búsqueda de reglas en juegos.
• Enrutamientos.
• Resolución de sistemas de ecuaciones no lineales.
• Optimización (estructural, de topologías, numérica, combinatoria, etc.).
• Aprendizaje de máquina.
• Bases de datos (optimización de consultas).
• Reconocimiento de patrones.
• Planeación de movimientos de robots.