Robots

CAPÍTULO 2

TÉCNICAS DE COMPUTACIÓN EVOLUTIVA
"Evolution is cleverer than you are."
FRANCIS CRICK
Elbow Room: the varieties of free will worth wanting, D. Dennett, 1984

2.1.

Introducción

Las técnicas de computación evolutiva constituyen un conjunto de heurísticas emergentes, utilizadas exitosamente para la resolución de una variada gama de problemas en las áreas de optimizacióncombinatoria, diseño de artefactos, búsqueda de información, control de dispositivos y aprendizaje automático, entre otros. Estas técnicas basan su operativa en la emulación de los mecanismos de la evolución natural, identificados por Charles Darwin en su célebre obra El Origen de las Especies por medio de la Selección Natural: la selección natural, la reproducción y la diversidad genética deindividuos (Darwin, 1859). Las técnicas de computación evolutiva trabajan sobre una población compuesta por un conjunto de codificaciones de soluciones candidatas para el problema a resolver. Estas soluciones interactúan entre sí, siguiendo los principios darwinianos de la evolución natural con la idea de producir iterativamente mejores soluciones al problema. Las soluciones potenciales se evalúanmediante una función de adecuación o función de fitness, que toma en cuenta el problema que se plantea resolver. En la naturaleza, durante el proceso evolutivo los seres vivos tratan de resolver los problemas relacionados con la supervivencia para garantizar la perpetuación de la especie. Mediante el mecanismo comentado, las técnicas de computación evolutiva emulan el proceso biológico de adaptación delos organismos vivos al entorno y las condiciones del medio, aplicándolo a la resolución de problemas en variadas áreas. Este capítulo presenta a las técnicas de computación evolutiva en general, y a los algoritmos genéticos en particular, como mecanismos de resolución de problemas de optimización combinatoria, y problemas análogos en otras áreas de aplicación. El capítulo comienza con unaintroducción a las técnicas de computación evolutiva que presenta sus principales características. A continuación se ofrece un panorama histórico del desarrollo de las técnicas algorítmicas basadas en la emulación de los procesos de la evolución natural, presentando globalmente los modelos más populares de técnicas evolutivas: las Estrategias de Evolución, la Programación Genética y los AlgoritmosGenéticos. Las características de los algoritmos genéticos son presentadas en la sección siguiente, explicando los detalles de su funcionamiento y sus ventajas y desventajas respecto a otros métodos exactos y heurísticos de resolución de problemas de optimización.

5

CAPÍTULO 2

TÉCNICAS DE COMPUTACIÓN EVOLUTIVA

2.2.

Técnicas de Computación Evolutiva

La expresión genérica computaciónevolutiva designa a un amplio conjunto de técnicas heurísticas de resolución de problemas complejos que basan su funcionamiento en un mecanismo análogo a los procesos de la evolución natural. Trabajando sobre un conjunto de soluciones a un problema determinado, la metodología utilizada por estas técnicas se fundamenta en el uso de mecanismos de selección de las mejores soluciones potenciales y deconstrucción de nuevas soluciones candidatas mediante recombinación de características de las soluciones seleccionadas. Varios esquemas algorítmicos han sido propuestos para los algoritmos evolutivos. La idea más generalizada sobre el mecanismo de un algoritmo evolutivo que trabaja sobre una población P se presenta en la Figura 2.1. Inicializar(P(0)) generación=0; mientras (no CriterioParada) hacerEvaluar(P(generación)) Padres = Seleccionar(P(generación)) Hijos = Aplicar Operadores Evolutivos (Padres) NuevaPoblacion = Reemplazar(Hijos, P(generación)) generación ++ P(generación) = NuevaPoblacion fin retornar Mejor Solución Encontrada Figura 2.1: Esquema algorítmico genérico de un algoritmo evolutivo. El algoritmo evolutivo trabaja sobre individuos que representan potenciales soluciones al...