Algoritmos Geneticos

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

Abstract
Esta gu´ contiene una introducci´n a los elementos b´sicos de los algoritmos gen´ticos y su adaptaci´n
ıa
o
a
e
o
a un problema simple de minimizaci´n de funciones dedos variables usando c´digo en matlab. Se
o
o
describe el c´digo con un instructivo b´sico de su sintaxis y funcionamiento. Se propone una serie
o
a
de pr´cticas num´ricas ejecutando variaciones del algoritmo. En la ultima secci´n se describe una
a
e
´
o
aplicaci´n de los algoritmos gen´ticos al ajuste de par´metros en el modelado de la voz humana, junto
o
e
a
con algunas nocionesde paralelizaci´n.
o

1

Algoritmos gen´ticos
e

Los algoritmos gen´ticos corresponden a la clase de m´todos estoc´sticos de b´squeda. Mientras la
e
e
a
u
mayor´ de estos m´todos operan sobre una unica soluci´n, estos algoritmos operan en una poblaci´n de
ıa
e
´
o
o
soluciones. La idea b´sica, inspirada en los procesos evolutivos en biolog´ es que el contenido gen´tico
a
ıa,
ede una poblaci´n contiene potencialmente la soluci´n, o una soluci´n mejor, a un dado problema de
o
o
o
adaptaci´n. Esta soluci´n puede estar inactiva porque la combinaci´n gen´tica adecuada est´ disemo
o
o
e
a
inada entre varios sujetos. S´lo la asociaci´n de genomas distintos puede llevar a la activaci´n de la
o
o
o
soluci´n.
o
Crudamente, el mecanismo evolutivo procede as´sobre una poblaci´n, algunos individuos son selecı:
o
cionados para la reproducci´n, con m´s oportunidades para los mejor adaptados al ambiente. Durante
o
a
la reproducci´n, los nuevos individuos de la poblaci´n resultan de modificaciones e intercambio gen´tico
o
o
e
de los padres. Una vez que se renueva la poblaci´n, el proceso recomienza. Es decir que hay dos espacios
o
donde opera laevoluci´n. Por una parte, a nivel de los individuos f´
o
ısicos (fenotipo), que deben adaptarse
para ser seleccionados. Y luego, a nivel de la informaci´n gen´tica (genotipo), a trav´s de los operadores
o
e
e
que intercambian y var´ la informaci´n gen´tica.
ıan
o
e
La informaci´n gen´tica est´ codificada en los cromosomas, que son secuencias de genes, cada uno de los
o
e
a
cuales codificauna caracter´
ıstica particular del individuo. Estas secuencias est´n escritas en t´rminos
a
e
de cuatro bases nitrogenadas: adenocina, timina, citocina y guanina. En este alfabeto de base cuatro,
[A, T, C, G], est´ escrita toda la informaci´n gen´tica de un individuo.
a
o
e
Hay esencialmente dos operadores gen´ticos. El operador de mutaci´n introduce cierta aleatoriedad en
e
o
lab´squeda simplemente cambiando unos genes por otros, contribuyendo a una exploraci´n ‘azarosa’
u
o
en el espacio gen´tico. El operador de crossover, en cambio, es una recombinaci´n de la informaci´n
e
o
o
durante la reproducci´n de los individuos seleccionados.
o
El proceso de evoluci´n, puesto en estos t´rminos, es adaptable a una enorme familia de problemas,
o
e
incluso ajenos al ´mbitobiol´gico. En la pr´xima secci´n se describe la adaptaci´n de este esquema de
a
o
o
o
o
b´squeda de soluciones a un problema matem´tico sencillo.
u
a

1

2

Adaptaci´n a un problema de optimizaci´n de funciones
o
o

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

12

9
8

10
7
8

6
5

6
4
4

3
2

2
1
0
2...