Algoritmos Gen Ticos Aplicaci N En MatLAB

Algoritmos gen´eticos: aplicaci´on en MATLAB
Mat´ıas Ison, Jacobo Sitt, Marcos Trevisan
Gu´ıa de la materia Sistemas Complejos
disponible en www.df.uba.ar/users/mison/genetico.tar.gz
November 25, 2005

Abstract
Esta gu´ıa contiene una introducci´
on a los elementos b´
asicos de los algoritmos gen´eticos y su adaptaci´
on
a un problema simple de minimizaci´
on de funciones de dos variables usandoc´
odigo en matlab. Se
describe el c´
odigo con un instructivo b´
asico de su sintaxis y funcionamiento. Se propone una serie
de pr´
acticas num´ericas ejecutando variaciones del algoritmo. En la u
´ltima secci´
on se describe una
aplicaci´
on de los algoritmos gen´eticos al ajuste de par´
ametros en el modelado de la voz humana, junto
con algunas nociones de paralelizaci´
on.

1

Algoritmos gen´eticos

Los algoritmos gen´eticos corresponden a la clase de m´etodos estoc´asticos de b´
usqueda. Mientras la
mayor´ıa de estos m´etodos operan sobre una u
´nica soluci´on, estos algoritmos operan en una poblaci´on de
soluciones. La idea b´asica, inspirada en los procesos evolutivos en biolog´ıa, es que el contenido gen´etico
de una poblaci´on contiene potencialmente la soluci´on, o una soluci´onmejor, a un dado problema de
adaptaci´on. Esta soluci´on puede estar inactiva porque la combinaci´on gen´etica adecuada est´a diseminada entre varios sujetos. S´olo la asociaci´on de genomas distintos puede llevar a la activaci´on de la
soluci´on.
Crudamente, el mecanismo evolutivo procede as´ı: sobre una poblaci´on, algunos individuos son seleccionados para la reproducci´on, con m´asoportunidades para los mejor adaptados al ambiente. Durante
la reproducci´on, los nuevos individuos de la poblaci´on resultan de modificaciones e intercambio gen´etico
de los padres. Una vez que se renueva la poblaci´on, el proceso recomienza. Es decir que hay dos espacios
donde opera la evoluci´on. Por una parte, a nivel de los individuos f´ısicos (fenotipo), que deben adaptarse
para ser seleccionados. Yluego, a nivel de la informaci´on gen´etica (genotipo), a trav´es de los operadores
que intercambian y var´ıan la informaci´on gen´etica.
La informaci´on gen´etica est´a codificada en los cromosomas, que son secuencias de genes, cada uno de los
cuales codifica una caracter´ıstica particular del individuo. Estas secuencias est´an escritas en t´erminos
de cuatro bases nitrogenadas: adenocina, timina,citocina y guanina. En este alfabeto de base cuatro,
[A, T, C, G], est´a escrita toda la informaci´on gen´etica de un individuo.
Hay esencialmente dos operadores gen´eticos. El operador de mutaci´
on introduce cierta aleatoriedad en
la b´
usqueda simplemente cambiando unos genes por otros, contribuyendo a una exploraci´on ‘azarosa’
en el espacio gen´etico. El operador de crossover, en cambio, esuna recombinaci´on de la informaci´on
durante la reproducci´on de los individuos seleccionados.
El proceso de evoluci´on, puesto en estos t´erminos, es adaptable a una enorme familia de problemas,
incluso ajenos al ´ambito biol´ogico. En la pr´oxima secci´on se describe la adaptaci´on de este esquema de
b´
usqueda de soluciones a un problema matem´atico sencillo.

1

2

Adaptaci´
on a un problemade optimizaci´
on de funciones

En esta secci´on ilustraremos la adaptaci´on de un algoritmo gen´etico a un problema sencillo de minimizaci´on de funciones bidimensionales f (x, y). La interpretaci´on f´ısica del problema es, en este caso,
casi trivial: haciendo corresponder la funci´on f a la ‘energ´ıa’ E asociada al estado (x, y), la evoluci´on
del sistema tender´a a minimizarla. A lo largo deesta gu´ıa nos referiremos m´as o menos indistintamente,
a la funci´on o al ‘paisaje energ´etico’.

12

9
8

10
7
8

6
5

6
4
4

3
2

2
1
0
2

0
2
2

1
1

0

2

1
1

0

0
−1

0
−1

−1
−2

−1
−2

−2

−2

Figura 1: ejemplo de paisaje energ´etico complejo (izquierda) y simple (derecha).
En t´erminos crudos, la meta de la exploraci´on gen´etica es encontrar los individuos mejor adaptados a su...