computación evolutiva

An´lisis de Algoritmos
a
Computacion Evolutiva

Integrantes:

Gustavo Quiroz
Rodrigo Astorga
Jorge Rojas

Talca - 22 de octubre de 2013

´
Indice
1. Introducci´n
o

3

2. Computaci´n Evolutiva
o
2.1. Algoritmos Evolutivos . . . . . . . . . .
2.1.1. Algoritmos Gen´ticos . . . . . . .
e
2.1.2. Poblaci´n . . . . . . . . . . . . .
o
2.2. Operadores Gen´ticos . . . . . . . .. . .
e
2.2.1. Algunas Aplicaciones pr´cticas de
a
2.3. Programaci´n Gen´tica . . . . . . . . . .
o
e
2.3.1. Representaci´n . . . . . . . . . .
o
2.3.2. Algoritmo . . . . . . . . . . . . .
2.3.3. Operadores Gen´ticos . . . . . . .
e
2.4. Estrategias Evolutivas . . . . . . . . . .
3. Conclusi´n
o

. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .. . . . . . . . . . . . . .
la computaci´n Gen´tica
o
e
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

4
4
4
5
6
7
8
8
9
10
10
11

2

1.

Introducci´n
o

La computaci´n evolutiva nace en los a˜os 60 con el fin de promover soluciones que se
o
n
adapten al entorno, es decir, a los problemas y que a su vez fueran optimas. Para ello la in´
terpretaci´n de la naturaleza es crucial, nombrando a este tipo demetodolog´ bio-inspiradas.
o
ıas
Se les llama as´ ya que la soluci´n obtenida se adecua a lo que sucede en la vida, usando como
ı
o
analog´ a las personas en el caso de una soluci´n, a una poblaci´n al conjunto de posibles
ıa
o
o
soluciones y adecuaci´n a la calidad de la soluci´n. Esto ultimo es lo que hace diferenciar a la
o
o
´
computaci´n evolutiva de la tradicional, su capacidad deelecci´n de respuestas, usando exitoo
o
samente metodolog´ heur´
ıas
ısticas.
Existen 4 grandes paradigmas b´sicos para la computaci´n evolutiva:
a
o
-Algoritmos gen´ticos: Emulaci´n de la evoluci´n natural de los seres vivos, tomando una
e
o
o
poblaci´n de soluciones y producto de la interacci´n de estas logra una soluci´n.
o
o
o
-Estrategias de evoluci´n: que enfatiza los cambios decomportamiento a nivel de individuos
o
producto de la interacci´n y adaptabilidad de estos.
o
-Programaci´n evolutiva: a diferencia de los algoritmos gen´ticos la representaci´n de las
o
e
o
soluciones es m´s directa.
a
-Programaci´n gen´tica: utiliza arboles en la confecci´n de sus soluciones.
o
e
o

3

2.
2.1.

Computaci´n Evolutiva
o
Algoritmos Evolutivos

Los algoritmosevolutivos constituyen un m´todo de resoluci´n de problemas de b´squeda
e
o
u
y calidad de respuesta inspirada en la teor´ de la selecci´n natural.
ıa
o
Estos algoritmos abordan problemas complejos que surgen en las ingenier´ y los campos
ıas
cient´
ıficos: problemas de planificaci´n de tareas, b´squeda de caminos optimos (grafos), optio
u
´
mizaci´n de funciones, etc.
o
Los algoritmosevolutivos tienen una estructura general que sirve para distintos problemas,
facilitando as´ enormemente las tareas de dise˜o e implementaci´n. El unico requisito de un
ı
n
o
´
usuario que desee aplicar esta t´cnica para resolver un problema concreto es saber programar
e
en cualquier lenguaje de prop´sito general en el que codificar´ el algoritmo evolutivo.
o
ıa
No obstante, para tenerresultados optimos con estos algoritmos es necesario conocerlos con
´
detalle, ya que dentro del esquema general de un algoritmo evolutivo hay que elegir m´ltiples
u
componentes y par´metros, de los que va a depender la calidad del resultado y la eficiencia del
a
algoritmo.
El conocimiento de la elecci´n m´s adecuada en cada caso, que a menudo depende de detalles
o
a
sutiles del...