Portal para Investigadores y Profesionales

Encuentra más Cursos o Publica tu Contenido en ElPrisma.com



Algoritmos Genéticos


Enlaces Patrocinados




Navigation bar
  Start Previous page
 1 of 11 
 Next page End 1 2 3 4 5 6  

ALGORITMOS GENETICOS
NATYHELEM GIL LONDOÑO
<e-mail:nggil[en]unal.edu.co>
Universidad Nacional de Colombia
Escuela de Estadística
ÍNDICE
2
Índice
1.   GENERALIDADES
5
1.1.  
INTRODUCCIÓN
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
5
1.1.1.
Reseña Historica   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
5
1.1.2.
¿Que son los Algoritmos Genéticos?
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
6
1.1.3.
¿Por qué utilizar Algoritmos Genéticos en la
Optimización?
7
1.1.4.
Ventajas
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
8
1.1.5.
Desventajas  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
13
1.1.6.
¿Cómo Saber si es Posible usar un
Algoritmo
Genético?   .
17
1.1.7.
Algunas Aplicaciones de los Algoritmos Genéticos  .  .  .  .
18
2.   ALGORITMOS GENÉTICOS
20
2.1.  
ALGORITMOS
GENÉTICOS
SIMPLES   .  .  .  .  .  .  .  .  .  .  .  .  .
20
2.1.1.
Tipos de
Representación   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
20
2.1.2.
Tamaño de la Población
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
22
2.1.3.
Población Inicial   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
22
2.1.4.
Función Objetivo  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
22
2.1.5.
Operador de Selección   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
25
2.1.6.
Operador de Cruce   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
26
2.1.7.
Operador de
Mutación   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
27
2.1.8.
Reemplazo de la Población y Condición de Parada   .  .  .  .
28
2.1.9.
Otros
Operadores  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
30
2.1.10.  Aplicando Operadores Genéticos
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
32
2.2.  
ALGORITMOS
GENÉTICOS
PARALELOS   .  .  .  .  .  .  .  .  .  .  .
37
2.3.  
COMPARACIÓN
DE
LOS
ALGORITMOS
GENÉTICOS
CON
OTRAS
TÉCNICAS
DE OPTIMIZACIÓN  
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
40
ÍNDICE
3
3.   ALGORITMOS GENÉTICOS: CÓDIGO EN R
43
3.1.  
PROGRAMA EN
R: ALGORITMOS
GENÈTICOS
. 
. 
. 
. 
. 
. 
.
43
3.2.  
ALGORITMO GENÉTICO DE BÚSQUEDA ÓPTIMA: UN SUB-
CONJUNTO
DE
K-VARIABLES  
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
49
3.2.1.
Descripción  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
49
3.2.2.
Uso   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
49
3.2.3.
Argumentos
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
49
3.2.4.
Detalles  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
50
3.2.5.
Ejemplo
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
51
3.3.  
FUNCIÓN
PLOT  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
52
3.3.1.
Descripción  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
52
3.3.2.
Uso   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
52
3.3.3.
Argumentos
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
52
3.3.4.
Ejemplos   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
53
3.4.  
CROMOSOMA FLOTANTE  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
53
3.4.1.
Descripción  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
53
3.4.2.
Uso   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
53
3.4.3.
Argumentos
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
54
3.4.4.
Ejemplos   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
54
3.5.  
CROMOSOMA
BINARIO 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
55
3.5.1.
Descripción  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
55
3.5.2.
Uso   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
55
3.5.3.
Argumentos
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
. 
.
56
3.5.4.
Ejemplos   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
56
3.6.  
FUNCIÓN
SUMMARY
. 
. 
. 
.
.  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
59
3.6.1.
Descripción  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
59
3.6.2.
Uso   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
59
ÍNDICE
4
3.6.3.
Argumentos
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
59
3.6.4.
Ejemplos   .  .
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
. 
.
59
4.
APLICACIÓN
60
5.
CONCLUSIONES
64
1.
GENERALIDADES
1.1.
INTRODUCCIÓN
1.1.1.
Reseña Historica
Los
algoritmos
genéticos
(AG),
fueron
inventados
en
1975
por
John
Holland,
de
la
Universidad
de
Michigan.
Los
AG
son,
simplificando,
algoritmos
de
optimiza-
ción,
es
decir,
tratan
de
encontrar
la
mejor
solución
a
un
problema
dado
entre
un
conjunto de soluciones posibles. Los
mecanismos de los que se valen los
AG para
llevar
a
cabo
esa
búsqueda
pueden
verse
como
una
metáfora
de
los
procesos
de
evolución biológica.
John
Holland
desde
pequeño,
se
preguntaba
cómo
logra
la
naturaleza,
crear
seres
cada
vez
más
perfectos.
No
sabía
la
respuesta,
pero
tenía
una
cierta
idea
de
co-
mo
hallarla:
tratando
de
hacer
pequeños
modelos
de
la
naturaleza,
que
tuvieran
alguna
de
sus
características,
y
ver
cómo
funcionaban,
para
luego
extrapolar
sus
conclusiones a la totalidad.
Fue
a
principios
de
los
60,
en
la
Universidad
de
Michigan
en
Ann
Arbor,
donde,
dentro
del
grupo
Logic
of
Computers,
sus
ideas
comenzaron
a
desarrollarse
y
a
dar
frutos.
Y
fue,
además,
leyendo
un
libro
escrito
por
un
biólogo
evolucionista,
R.
A.
Fisher,
titulado
La
teoría
genética
de
la
selección
natural,
como
comenzó
a
descubrir
los
medios
de
llevar
a
cabo
sus
propósitos
de
comprensión
de
la
natu-
raleza.
De
ese
libro
aprendió
que
la
evolución
era
una
forma
de
adaptación
más
potente
que
el
simple
aprendizaje,
y
tomó
la
decisión
de
aplicar
estas
ideas
para
desarrollar programas bien adaptados para un fin determinado.
En esa universidad, Holland impartía un curso titulado Teoría de sistemas adapta-
tivos.
Dentro
de
este
curso,
y
con
una
participación
activa
por
parte
de
sus
estu-
diantes, fue donde se crearon las ideas que
más tarde se convertirían en los AG.
Por tanto, cuando Holland se enfrentó a los
AG, los objetivos de su investigación
fueron dos:
imitar los procesos adaptativos de los sistemas naturales, y
diseñar sistemas artificiales (normalmente programas) que retengan los me-
canismos importantes de los sistemas naturales.
Unos
15
años
más
adelante,
David
Goldberg,
actual
delfín
de
los
AG,
conoció
a
Holland, y se convirtió en su estudiante. Goldberg era un ingeniero industrial tra-
bajando
en diseño
de pipelines,
y
fue uno de los
primeros que
trató de
aplicar los
AG a problemas industriales. Aunque Holland trató de disuadirle, porque pensaba
que
el
problema
era
excesivamente
complicado
como
para
aplicarle
AG,
Gold-
berg consiguió lo que quería, escribiendo un
AG en un ordenador personal Apple
II.
Estas
y
otras
aplicaciones
creadas
por
estudiantes
de
Holland
convirtieron
a
los
AG
en
un
campo
con
bases
suficientemente
aceptables
como
para
celebrar
la
primera conferencia en 1985, ICGA´85.
1.1.2.
¿Que son los Algoritmos Genéticos?
Los
AG
son
métodos
adaptativos
que
pueden
usarse
para
resolver
problemas
de
búsqueda y optimización. Están basados en el proceso genético de los organismos
vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza
de acorde
con los principios
de la selección
natural
y
la supervivencia
de los mas
fuertes, postulados
por
Darwin (1859). Por imitación de este proceso, los
AG son
capaces de ir creando soluciones para
problemas del
mundo real. La evolución
de
dichas
soluciones
hacia
valores
óptimos
del
problema
depende
en
buena
medida
de una adecuada codificación de las mismas.
En  la  naturaleza  los  individuos  de  una  población  compiten  entre  si  en  la  bús-
queda
de
recursos
tales
como
comida,
agua
y
refugio.
Incluso
los
miembros
de
una
misma
especie
compiten
a
menudo
en
la
búsqueda
de
un
compañero.
Aque-
llos
individuos
que
tienen
mas
éxito
en
sobrevivir
y
en
atraer
compañeros
tienen
mayor
probabilidad
de
generar
un
gran
numero
de
descendientes.
Por
el
contra-
rio
individuos
poco
dotados
producirán
un
menor
numero
de
descendientes.
Esto
significa
que
los
genes
de
los
individuos
mejor
adaptados
se
propagaran
en
suce-
sivas
generaciones
hacia
un
número
de
individuos
creciente.
La
combinación
de
buenas características provenientes
de diferentes ancestros, puede a veces
produ-
cir
descendientes
"superindividuos",
cuya
adaptación
es
mucho
mayor
que
la
de
cualquiera
de
sus
ancestros.
De
esta
manera,
las
especies
evolucionan
logrando
unas características cada vez
mejor adaptadas al entorno en el que viven.
El
poder
de
los
AG
proviene
del
hecho
de
que
se
trata
de
una
técnica
robusta,
y
pueden tratar con éxito una gran variedad de problemas provenientes de diferentes
áreas,
incluyendo
aquellos
en
los
que
otros
métodos
encuentran
dificultades.
Si
bien no se garantiza que el
AG encuentre la solución optima del problema, existe
Previous page Top Next page
Comparte ElPrisma.com en:   Tweet     Mister Wong 

Es política de El Prisma.com cumplir con las leyes nacionales y tratados internacionales que protegen la propiedad intelectual y los Derechos de Autor (Copyright). Los textos mostrados en esta página han sido enviados por nuestros usuarios que han declarado ser los autores de los mismos y han permitido su uso por parte de www.elprisma.com, si usted considera que la información contenida en esta página viola sus derechos de autor, por favor envíenos su notificación de infracción a sugerencias1[en]elprisma.com y removeremos los textos de nuestros servidores. Condiciones de Uso.
Administración de Empresas y Negocios, Economía y Finanzas, Mercadeo y Publicidad, Arquitectura, Diseño Gráfico, Diseño Industrial, Teología, Pedagogía, Ciencias Políticas, Derecho, Historia, Bellas Artes, Comunicación y Periodismo, Español y Literatura, Filosofía, Ingeniería Civil, Ingeniería de Minas y Petróleos, Ingeniería de Sistemas e Informática, Ingeniería Eléctrica y Electrónica, Ingeniería Industrial, Ingeniería Mecánica, Ingeniería Química, Biología, Física, Geografía, Matemáticas, Química, Medicina, Odontología, Psicología, Agronomía, Veterinaria, Zootecnia.