-
VENTAJAS, LIMITACIONES Y APLICACIONES DEL
ALGORTIMO GENTICO
Jersey Samanta Castro Espinosa
Jersey Samanta Castro Espinosa, Estudiante de Ingeniera
Industrial VIII Semestre, Corporacin Universitaria del Meta,
B13 Apto 402 Multifamiliares los Centauros, Villavicencio, 318
514 9165, [email protected].
INTRODUCCIN
El algoritmo gentico, al igual que las redes
neuronales, funciona como una caja negra
que recibe ciertas entradas y produce (tras
una cantidad de tiempo indeterminada) las
salidas deseadas. Sin embargo, a diferencia
de stas, los algoritmos genticos no
necesitan entrenarse con ejemplos de ningn
tipo, sino que son capaces de generar sus
propios ejemplos y contraejemplos que
guen la evolucin a partir de poblaciones
inciales totalmente aleatorias.
Las expectativas son que la aptitud media de
la poblacin se incrementar en cada ronda
y, por tanto, repitiendo este proceso cientos
o miles de rondas, pueden descubrirse
soluciones muy buenas del problema.
LA IMPORTANCIA DEL ALGORTIMO
GENTICO EN LA SOLUCIN DE
PROBLEMAS1
Los Algoritmos genticos son un mtodo
para resolver problemas de optimizacin, por
tanto nos ayudan a tomar una decisin a la
hora de actuar. Gracias a la base matemtica
de los Algoritmos genticos obtenemos
valores resolutivos que aportan luz a la
incgnita propuesta en una funcin.
Lo interesante del mecanismo de los
Algoritmos genticos es que simula el
comportamiento de los seres vivos en su
proceso evolutivo.
Un algoritmo gentico es una tcnica de
programacin que imita a la evolucin
biolgica como estrategia para resolver
1 La Importancia del Algoritmo Gentico en la Solucin de
Problemas. Disponible en:
http://inteligenciaartificial802.wikispaces.com/ALGORITMOS+G
ENETICOS
-
problemas. Dado un problema especfico a
resolver, la entrada del algoritmo gentico es
un conjunto de soluciones potenciales a ese
problema, codificadas de alguna manera, y
una mtrica llamada funcin de aptitud que
permite evaluar cuantitativamente a cada
candidata. Estas candidatas pueden ser
soluciones que ya se sabe que funcionan, con
el objetivo de que el algoritmo gentico las
mejore, pero se suelen generar
aleatoriamente.
VENTAJAS DE LOS ALGORITMOS
GENETICOS 2
El primer y ms importante punto es que los
algoritmos genticos son intrnsecamente
paralelos. La mayora de los otros algoritmos
son en serie y slo pueden explorar el
espacio de soluciones hacia una solucin en
una direccin al mismo tiempo, y si la
solucin que descubren resulta subptima,
no se puede hacer otra cosa que abandonar
todo el trabajo hecho y empezar de nuevo.
Sin embargo, ya que los algoritmos
genticos tienen descendencia mltiple,
pueden explorar el espacio de soluciones en
mltiples direcciones a la vez. Si un camino
2 P. Brucker, S. Heitmann y J. Hurink, Scheduling of Trains on a
Single-Track Railway-Line. Ventajas de los Algoritmos Genticos,
Facultad de Informtica. Universidad Politcnica de Valencia.
Curso 2003-04.
resulta ser un callejn sin salida, pueden
eliminarlo fcilmente y continuar el trabajo
en avenidas ms prometedoras, dndoles una
mayor probabilidad en cada ejecucin de
encontrar la solucin.
Debido al paralelismo que les permite
evaluar implcitamente muchos esquemas a
la vez, los algoritmos genticos funcionan
particularmente bien resolviendo problemas
cuyo espacio de soluciones potenciales es
realmente grande demasiado vasto para
hacer una bsqueda exhaustiva en un tiempo
razonable. La mayora de los problemas que
caen en esta categora se conocen como no
lineales. En un problema lineal, la aptitud de
cada componente es independiente, por lo
que cualquier mejora en alguna parte dar
como resultado una mejora en el sistema
completo. No es necesario decir que hay
pocos problemas como ste en la vida real.
La no linealidad es la norma, donde cambiar
un componente puede tener efectos en
cadena en todo el sistema, y donde cambios
mltiples que, individualmente, son
perjudiciales, en combinacin pueden
conducir hacia mejoras en la aptitud mucho
mayores.
Otra ventaja notable de los algoritmos
genticos es que se desenvuelven bien en
-
problemas con un paisaje adaptativo
complejo -aqullos en los que la funcin de
aptitud es discontinua, ruidosa, cambia con
el tiempo, o tiene muchos ptimos locales.
LIMITACIONES DE LOS
ALGORITMOS GENETICOS3
Los algoritmos genticos tienen ciertas
limitaciones; sin embargo, se demostrar que
todas ellas pueden superarse y que ninguna
de ellas afecta a la validez de la evolucin
biolgica.
La primera y ms importante consideracin
al crear un algoritmo gentico es definir una
representacin del problema. El lenguaje
utilizado para especificar soluciones
candidatas debe ser robusto; es decir, debe
ser capaz de tolerar cambios aleatorios que
no produzcan constantemente errores fatales
o resultados sin sentido.
El problema de cmo escribir la funcin de
aptitud debe considerarse cuidadosamente
para que se pueda alcanzar una mayor
aptitud y verdaderamente signifique una
solucin mejor para el problema dado. Si se
elige mal una funcin de aptitud o se define
3 Ninoska Maneiro, Limitaciones de los Algoritmos Geneticos,
Tesis de Maestra. Facultad de Ingeniera. Universidad de
Carabobo, 2001.
de manera inexacta, puede que el algoritmo
gentico sea incapaz de encontrar una
solucin al problema, o puede acabar
resolviendo el problema equivocado. Esta
ltima situacin se describe a veces como la
tendencia del algoritmo gentico a engaar,
aunque en realidad lo que est pasando es
que el algoritmo gentico est haciendo lo
que se le pidi hacer, no lo que sus creadores
pretendan que hiciera.
FUNCIONAMIENTO DE UN
ALGORITMO GENTICO BSICO4
Un algoritmo gentico puede presentar
diversas variaciones, dependiendo de cmo
se aplican los operadores genticos
(cruzamiento, mutacin), de cmo se realiza
la seleccin y de cmo se decide el
reemplazo de los individuos para formar la
nueva poblacin. En general, el
pseudocdigo consiste de los siguientes
pasos:
INICIALIZACIN: Se genera
aleatoriamente la poblacin inicial, que
est constituida por un conjunto de
cromosomas los cuales representan las
posibles soluciones del problema. En caso
4 Ochoa Garca Sandra (2008). Funcionamiento de un Algoritmo
Gentico Bsico. Instituto Politcnico Nacional Mexico D.F. Fecha
de consulta: 8 de Setiembre 2013.
-
de no hacerlo aleatoriamente, es
importante garantizar que dentro de la
poblacin inicial, se tenga la diversidad
estructural de estas soluciones para tener
una representacin de la mayor parte de la
poblacin posible o al menos evitar la
convergencia prematura.
EVALUACIN: A cada uno de los
cromosomas de esta poblacin se aplicar
la funcin de aptitud para saber qu tan
"buena" es la solucin que se est
codificando.
CONDICIN DE TRMINO: El
algoritmo gentico se deber detener
cuando se alcance la solucin ptima,
pero sta generalmente se desconoce, por
lo que se deben utilizar otros criterios de
detencin. Normalmente se usan dos
criterios: correr el algoritmo gentico un
nmero mximo de iteraciones
(generaciones) o detenerlo cuando no
haya cambios en la poblacin.
APLICACIN DE TCNICAS
EVOLUTIVAS A PROBLEMAS DE
SCHEDULING FERROVIARIO5
Una de las tareas ms complicadas que las
compaas de ferrocarriles afrontan es la
5 Aplicacin de Tcnicas Evolutivas a Problemas de Scheduling
Ferroviario, Bella Sanjun, Antonio Valencia, septiembre 2004,
PFC: II - DEIO - B - 01/03
construccin de horarios para el trfico
ferroviario. Hasta hace poco estas tareas se
realizaban mayormente a mano. Durante los
ltimos aos los ordenadores han sido
equipados para realizar el proceso de
construccin de los horarios usando bases de
datos apropiadas y sistemas grficos
interactivos.
Lo ideal sera construir un sistema capaz de
crear automticamente el horario de
cualquier lnea ferroviaria, pero esta es una
tarea muy complicada, dada la gran
diversidad de trazados ferroviarios que nos
podemos encontrar. As que en vez de
abordar la construccin de una herramienta
general, la mayora de los trabajos se centran
en buscar soluciones especficas para lneas
concretas que presentan una tipologa
determinada.
APLICACIONES DE LA
INTELIGENCIA ARTIFICIAL EN
PROBLEMAS DE PRODUCCIN6
Se considera que la produccin en nuestros
das puede estar muy apoyada en las nuevas
tecnologas, como es la inteligencia artificial
6 Alejandro Vargas Lpez, Aplicaciones de la Inteligencia
Artificial en Problemas de Produccin, Gestin del conocimiento.
01-2004 Disponible en:
http://www.gestiopolis.com/recursos/documentos/fulldocs/ger1/apli
intarti.htm
-
ya sea como soporte para una toma de
decisiones ms eficaz o en la ayuda de
labores, tareas, que exijan gran demanda de
tiempo o representen un alto grado de
peligrosidad al ser humano.
Son muchos los estudios y aplicaciones que
se han logrado con el desarrollo de esta
ciencia , entre las cuales tenemos redes
neuronales aplicadas al control de la calidad
donde la red evala si determinado producto
cumple o no con las especificaciones
demandadas, control del proceso qumico en
el grado de acidez, algoritmos genticos
aplicados al problema cuadrtico de
asignacin de facilidades que trata de la
asignacin de N trabajos en M mquinas, los
autmatas programables que se usan para la
optimizacin de sistemas de produccin, en
fin, todava queda mucho por descubrir con
respecto a las aplicaciones de esta ciencia.
TRENDS OF ARTIFICIAL
INTELLIGENCE SYSTEMS7
Se determina que todos estos desarrollos
acortan bastante el proceso de decisiones y
optimizan las mismas, pero ah que tener
7 Francisco Herrera Fernndez Ph. D. Profesor del departamento de
Control Automtico Universidad Central de las Villas Santa
Clara, Cuba. Trends Of Artificial Intelligence Systems. Pag 42
-
44
mucho cuidado ya que hay que analizar los
diferentes impactos ya sean ambientales,
sociales, polticos y econmicos.
Se han venido destacando otros paradigmas
como lo son los agentes de decisin
inteligente y autmatas programables, con
respecto a estos ltimos se suelen emplear en
gran medida en procesos industriales de
acuerdo a necesidades a satisfacer como,
espacio reducido, procesos de produccin
peridicamente cambiantes, procesos
secuenciales, maquinaria de procesos
variables, etc.
APPLICATION OF ARTIFICIAL
INTELLIGENCE IN PRODUCTION
SYSTEMS8
La incorporacin de agentes de decisin
inteligente, redes neuronales, sistemas
expertos, algoritmos genticos y autmatas
programables para optimizacin de sistemas
de produccin es una tendencia activa en el
ambiente industrial de pases con alto
desarrollo tecnolgico y con una gran
inversin en investigacin y desarrollo.
Dichos componentes de la Inteligencia
Artificial tienen como funcin principal
8 Marr D.C. Artificial Intelligence: a Personal View, Artificial
Intelligence. EEUU 1977. Rolston W. David. Application Of
Artificial Intelligence In Production Systems. Mc Graw Hill.
Mxico 1992.
-
controlar de manera independiente, y en
coordinacin con otros agentes,
componentes industriales tales como celdas
de manufactura o ensamblaje, y operaciones
de mantenimiento, entre otras.
Existe una tendencia creciente a la
implementacin de sistemas de
manufactura/ensamblaje ms autnomos e
inteligentes, debido a las exigencias del
mercado por obtener productos con niveles
muy altos de calidad; lo cual con
operaciones manuales se hace complicada y
hace que los pases subdesarrollados como el
nuestro no alcance niveles competitivos a
nivel mundial. Al disear un sistema de
produccin integrado por computadora se
debe dar importancia a la supervisin,
planificacin, secuenciacin cooperacin y
ejecucin de las tareas de operacin en
centros de trabajo, agregado al control de los
niveles de inventario y caractersticas de
calidad y confiabilidad del sistema. Los
factores mencionados determinan la
estructura del sistema y su coordinacin
representa una de las funciones ms
importantes en el manejo y control de la
produccin.
ANTECEDENTES EN EL ARTE
GENTICO9
La naturaleza utiliza potentes medios para
impulsar la evolucin satisfactoria de los
organismos. Los organismos que son poco
aptos para un determinado ambiente mueren,
en tanto que los que estn bien adaptados
para vivir, se reproducen. Los hijos son
semejantes a sus padres, por lo que cada
nueva generacin tiene organismos
semejantes a los miembros bien dotados de
la generacin anterior." (Russel y Norvig,
1996) Los algoritmos genticos son una
tcnica de la Inteligencia Artificial, que
simula el proceso evolutivo de los seres
vivos y lo aplica a la bsqueda de soluciones
y optimizacin, en la resolucin de
problemas.
El arte gentico es generado por
computadora a partir de algoritmos
genticos. Genetic Images de Karl Sims, "es
una instalacin multimedia en la que los
visitantes pueden interactuar en el proceso
evolutivo de imgenes abstractas. Una
supercomputadora genera y muestra
imgenes en 16 pantallas situadas en el
espacio en forma de arco. Los visitantes se
paran sobre sensores frente a las imgenes
9 Macchi, Carlos.:2000, Antecedentes en el Arte Gentico, Ars
e
verse, http://www.arseverse.com/
-
que les resultan de mayor belleza, y as
seleccionan las imgenes que sobrevivirn y
se reproducir en una nueva generacin"
(Sims,1993). "Genetic Images, Particle
Dreams y Panspermia, obras de Karl Sims,
junto con The Process Of The Evolution de
Will Lantham o Mutations de Yoichiro
Kawaguchi" (Macchi, 2002), son obras de
arte gentico expuestas en el Centro Georges
Pompidou durante la Revue Virtuelle de
1993.
LA COMPOSICIN DE LOS GENES
De qu se componen los genes? Cuando
trabajamos con Algoritmos Genticos los
genes de los "sujetos" que cruzamos estn
compuestos de los valores de las variables
que permiten construir al sujeto en cuestin.
Es decir, los valores de las variables que
caracterizan al sujeto. Pero cuando
aplicamos Algoritmos Genticos a un
fenmeno esttico, como un cuadro con la
esttica de Vasarely, es importante que los
genes reflejen propiedades perceptibles. Los
cinco genes elegidos en nuestro ejemplo,
responden a caractersticas que pueden ser
"vistas". Para esto, fue necesario englobar
varias variables en cada uno de los genes. Si
se hubiera hecho una asociacin de un gen
por variable, seguramente la cantidad de
genes superara los treinta, y la cantidad de
combinaciones posibles sera altsima, pero
dado que no todas las variables representan
caractersticas que son perceptibles por s
mismas, seguramente en la reproduccin se
perdera la herencia de las caractersticas
percibidas de los progenitores. Y es que se
puede distinguir entre las caractersticas
constructivas y las perceptibles, es decir, las
variables aisladas definen la forma en que se
construye el cuadro, pero para poder definir
una caracterstica perceptible, es necesario
reunir varias de estas en un slo gen.
CONCLUSIONES
Los grandes avances de I.A aplicada a
sistemas de produccin han hecho que da a
da la industria en su constante bsqueda por
mejorar su competitividad logren dicho
objetivo, pero en muchos de los casos
desplazar gran cantidad de mano de obra que
llevan consigo un deterioro social que se ve
reflejado en los indicadores globales de
desempleo y niveles de pobreza.
Los algoritmos genticos son una tcnica
muy potente que permite simular ciertos
aspectos de la reproduccin de los seres
vivos y aplicarla a diferentes problemticas,
-
como es el caso del arte, nuestro objeto de
discusin en el presente texto. A la hora de
aplicar esta tcnica a la produccin esttica,
es importante tener en cuenta que el
principal inters en su uso radica en la
herencia de caracteres y que por tanto, dicha
herencia debe ser notable (perceptible) ya
que sino la tcnica slo funcionar como una
configuracin al azar. Si la aplicacin de los
algoritmos genticos se dan sobre procesos
generativos, como han sido los ejemplos
expuestos, entonces es necesario extraer
cuales son los parmetros que definen la
configuracin final del fenmeno y luego
agrupar estos parmetros de forma que
representen caractersticas perceptibles del
fenmeno.
-
REFERENCIAS BIBLIOGRFICAS
[1] La Importancia del Algortimo Gentico
en la Solucin de Problemas.
Disponible en:
http://inteligenciaartificial802.wikispaces.co
m/ALGORITMOS+GENETICOS
[2] P. Brucker, S. Heitmann y J. Hurink,
Scheduling of Trains on a Single-Track
Railway-Line. Ventajas de los Algoritmos
Genticos, Facultad de Informtica.
Universidad Politcnica de Valencia. Curso
2003-04.
[3] Ninoska Maneiro, Limitaciones de los
Algoritmos Geneticos, Tesis de Maestra.
Facultad de Ingeniera. Universidad de
Carabobo, 2001.
[4] Ochoa Garca Sandra (2008).
Funcionamiento de un Algoritmo Gentico
Bsico. Instituto Politcnico Nacional
Mexico D.F. Fecha de consulta: 8 de
Setiembre 2013.
[5] Aplicacin de Tcnicas Evolutivas a
Problemas de Scheduling Ferroviario, Bella
Sanjun, Antonio Valencia, septiembre
2004, PFC: II - DEIO - B - 01/03
[6] Alejandro Vargas Lpez, Aplicaciones
de la Inteligencia Artificial en Problemas de
Produccin, Gestin del conocimiento. 01-
2004
Disponible en:
http://www.gestiopolis.com/recursos/docum
entos/fulldocs/ger1/apliintarti.htm
[7] Francisco Herrera Fernndez Ph. D.
Profesor del departamento de Control
Automtico Universidad Central de las
Villas Santa Clara, Cuba. Trends Of
Artificial Intelligence Systems. Pag 42 - 44
[8] Marr D.C. Artificial Intelligence: a
Personal View, Artificial Intelligence.
EEUU 1977. Rolston W. David. Application
Of Artificial Intelligence In Production
Systems. Mc Graw Hill. Mxico 1992.
[9] Macchi, Carlos.:2000, Antecedentes en el
Arte Gentico, Ars e verse,
http://www.arseverse.com/
[10] Russel Stuart y Norvig Peter.: 1996, La
Composicin de los Genes, Prentice Hall,
Mxico, pp. 653-654.
