2 Orígenes

Si algo funciona bien, ¿por qué no imitarlo?. La respuesta a esta pregunta nos lleva directamente a los orígenes de la computación evolutiva. Durante millones de años las diferentes especies se han adaptado para poder sobrevivir en un medio cambiante. De la misma manera se podría tener una población de potenciales soluciones a un problema de las que se irían seleccionando las mejores hasta que se adaptasen perfectamente al medio, en este caso el problema a resolver. En términos muy generales se podría definir la computación evolutiva como una familia de modelos computacionales inspirados en la evolución.

Más formalmente el término de computación evolutiva se refiere al estudio de los fundamentos y aplicaciones de ciertas técnicas heurísticas basadas en los principios de la evolución natural [Tomassini, 1995]. Estas técnicas heurísticas podrían clasificarse en 3 categorías principales dando lugar a la ecuación evolutiva (Fig. 1).

Figura 1: Ecuación Evolutiva

A continuación se detallarán un poco más los orígenes de cada una de las disciplinas participantes en dicha ecuación.

El desarrollo de los Algoritmos Genéticos se debe en gran medida a John Holland, investigador de la Universidad de Michigan. A finales de la década de los 60 desarrolló una técnica que imitaba en su funcionamiento a la selección natural. Aunque originalmente esta técnica recibió el nombre de planes reproductivos, a raíz de la publicación en 1975 de su libro ``Adaptation in Natural and Artificial Systems'' [Holland, 1975] se conoce principalmente con el nombre de Algoritmos Genéticos.

A grandes rasgos un Algoritmo Genético consiste en una población de soluciones codificadas de forma similar a cromosomas. Cada uno de estos cromosomas tendrá asociado un ajuste, valor de bondad, ajuste o fitness, que cuantifica su validez como solución al problema. En función de este valor se le darán más o menos oportunidades de reproducción. Además, con cierta probabilidad se realizarán mutaciones de estos cromosomas.

Las bases de las Estrategias de Evolución fueron apuntadas en 1973 por Rechemberg en su obra ``Evolutionsstrategie: Optimierung Technisher Systeme nach Prinzipien der Biologischen Evolution'' [Rechenberg, 1973]. Las dos Estrategias de Evolución más empleadas son la ( $\mu+\lambda$)-ES y la ( $\mu,\lambda$)-ES. En la primera de ellas un total de $\mu$ producen $\lambda$ descendientes reduciéndose nuevamente la población a $\mu$ individuos (los padres de la siguiente generación) por selección de los mejores individuos. De esta manera los padres sobreviven hasta que son reemplazados por hijos mejores que ellos. En la ( $\mu+\lambda$)-ES la descendencia reemplaza directamente a los padres, sin hacer ningún tipo de comprobación.

La Programación Evolutiva surge principalmente a raíz del trabajo ``Artificial Intelligence Through Simulated Evolution'' de Fogel, Owens y Walsh, publicado en 1966 [Fogel et al., 1966]. En este caso los individuos, conocidos aquí como organismos, son máquinas de estado finito. Los organismos que mejor resuelven alguna de las funciones objetivo obtienen la oportunidad de reproducirse. Antes de producirse los cruces para generar la descendencia se realiza una mutación sobre los padres.

A su vez la computación evolutiva puede verse como uno de los campos de investigación de lo que se ha dado en llamar Soft Computing (Fig. 2).

Figura 2: Soft Computing

Como se ha comentado anteriormente la computación evolutiva tiene una fuerte base biológica. En sus orígenes los algoritmos evolutivos consistieron en copiar procesos que tienen lugar en la selección natural. Este último concepto había sido introducido, rodeado de mucha polémica, por Charles Darwin [Darwin, 1859]. A pesar de que aún hoy en día no todos los detalles de la evolución biológica son completamente conocidos, existen algunos hechos apoyados sobre una fuerte evidencia experimental:

• La evolución es un proceso que opera, más que sobre los propios organismos, sobre los cromosomas. Estos cromosomas pueden ser considerados como herramientas orgánicas que codifican la vida, o visto al revés, una criatura es creada decodificando la información contenida en los cromosomas.

• La selección natural es el mecanismo que relaciona los cromosomas con la eficiencia respecto al medio de la entidad que representan. Otorga a los individuos más adaptados al medio un mayor número de oportunidades de reproducirse.

• Los procesos evolutivos tienen lugar durante la etapa de reproducción. Aunque existe una larga serie de mecanismos que afectan a la reproducción los más comunes son la mutación, causante de que los cromosomas de la descendencia sean diferentes a los de los padres, y el cruce o recombinación, que combina los cromosomas de los padres para producir la descendencia.