Algoritmos bioinspirados y computación evolutiva - Oviedo - primera P.L.

Entorno disponible en sala E.A.O.

• Ubuntu 12.4
• Octave 3.2
• QtOctave 0.10
• R 2.14
• Rcmdr
• genalg

N reinas

Descripción

Planteamiento

• Codificación: véanse páginas 6 y 10 de la construcción de algoritmos genéticos y página 8 de la búsqueda local.
• Sobrecruce.
• Mutación: pág. 17 de la construcción de algoritmos genéticos.
• Evaluación: pág. 13 de la construcción de algoritmos genéticos.

Listado de referencia

• Octave: texto puro, html
• R: texto puro, html

Análisis estadístico

1. Obtener vector de tiempos o de número de iteraciones.
2. Resumir tiempos con mean, median, sd (en R) o std (en Octave)...
3. Estudiar la influencia de los parámetros nPob, nCan y pMut en el tiempo de parada.
4. Si hace falta, comprobar si hay diferencias significativas: wilcox.test (en R), u_test, kolmogorov_smirnov_test_2 (en Octave)...
5. Estimar el tiempo de parada para un valor alto de nRei, por ejemplo, mediante lm (en R),ols (en Octave).

Posibles mejoras

• Implementar la máscara para sobrecruce (pág. 22 de la construcción de algoritmos genéticos).
• Implementar una evaluación más rápida. Por ejemplo, considerar un vector con número de reinas en cada diagonal; págs. 3, 11 y 12 (7, 15 y 16 según la numeración explícita) de este artículo. (Posibles versiones en texto puro y html.)
• Implementar una versión del algoritmo que utilice cromosomas binarios y operaciones de manipulaciones de bites (para R véase el paquete bit; para Octave véase la sección 4.5 del manual), o bien usar una biblioteca de R que admita cromosomas binarios (por ejemplo, genalg, como en este listado).

Búsqueda local

• Ver página 7 de la búsqueda local).
• Implementar un criterio de escalada (como en página 8 de la búsqueda local) pero para codificación de orden, y aplicarlo a los hijos del algoritmo genético. (Posible versión en texto puro y html.)

Selección de reproductores

Enunciado

En producción animal es necesario controlar la consanguinidad de los futuros reproductores. Esta matriz indica la relación de parentesco entre parejas de 215 individuos de una generación. Se pretende seleccionar 3 lotes de 30 individuos cada uno, de forma que, en primer lugar, el máximo de las relaciones en los lotes sea lo menor posible y, en segundo lugar, que la media de las relaciones en los lotes sea lo menor posible.

Plantea un algoritmo genético para esa situación e impleméntalo directamente o ayudándote de una biblioteca (p.ej. el paquete genalg de R, usado p.ej. así).