UNIVERSIDAD TCNICA DE MACHALA
UNI DAD ACADMI CA DE I NGENI ER A CI VI L
CARRERA DE I NGENI ER A DE SI STEMAS
INTELIGENCIA ARTIFICIAL
PROYECTO FINAL
ALGORITMOS GENETICOS
PLANIFICADOR DE RUTAS
CURSO
9no Semestre Paralelo B (PROMOCION# 10)
AUTORES
BERSOZA JIMMY
BONILLA RICARDO
DAVILA CUESTA
MANRIQUE MARCELINO
QUEZADA LEONARDO
DOCENTE
ING. WILMER RIVAS
PERIODO 2014 - 2015
MACHALA EL ORO ECUADOR
INTRODUCCION
Los algoritmos genticos son mecanismos de bsqueda basados en la teora de la
evolucin de Darwin, a alcanzado gran popularidad en la actualidad debido a su relacin
directa con la inteligencia artificial. Se demostrara un ejemplo orientado a la
planificacin de la mejor ruta estableciendo un camino. Adicionalmente, se colocara la
codificacin y la librera utilizada JGAP para la solucin.
La inteligencia artificial busca emular aspectos del comportamiento humano, tales
como: aprendizaje, percepcin, raciocinio, evolucin y adaptacin. Los algoritmos
genticos como parte de esta ciencia, se convierten en un mtodo efectivo de bsqueda
de soluciones y adicionalmente permiten la ampliacin de variables a considerar; factor
importante ya que esto logra una mayor capacidad de prediccin de soluciones
acertadas.
ALGORITMOS GENETICOS
Es un algoritmo matemtico altamente paralelo que transforma un conjunto de objetos
matemticos individuales con respecto al tiempo usando operaciones modeladas de
acuerdo al principio Darwiniano de reproduccin y supervivencia del ms apto, y tras
haberse presentado de forma natural una serie de operaciones genticas de entre las que
destaca la recombinacin de emparejamiento. Cada uno de estos objetos matemticos
suele ser una cadena de caracteres (letras o nmeros) de longitud fija que se ajusta al
modelo de las cadenas de cromosomas, y se les asocia con una cierta funcin
matemtica que refleja su aptitud.
Estos algoritmos hacen evolucionar una poblacin de individuos sometindola a
acciones aleatorias semejantes a las que actan en la evolucin biolgica (mutaciones y
recombinaciones genticas), as como tambin a una Seleccin de acuerdo con algn
criterio, en funcin del cual se decide cules son los individuos ms adaptados, que
sobreviven, y cules los menos aptos, que son descartados
FUNCIONAMIENTO
La aplicacin ms comn de los algoritmos genticos ha sido la solucin de problemas
de optimizacin, en donde han mostrado ser muy eficientes y confiables. Sin embargo,
no todos los problemas pudieran ser apropiados para la tcnica, y se recomienda en
general tomar en cuenta si es posible o no utilizar algoritmos genticos para su
optimizacin.
Desarrollado por John H. Holland, el algoritmo gentico opera entonces a nivel de
genotipo de las soluciones mediante la siguiente secuencia:
1. Comenzar con una poblacin inicial, la cual puede ser generada de manera
aleatoria.
2. Calcular el fitness (aptitud) de cada individuo.
3. Aplicar el operador de seleccin con base en el fitness de la poblacin.
4. Aplicar los operadores genticos de reproduccin, cruce y mutacin a la
poblacin actual para generar a la poblacin de la siguiente generacin.
5. Ir al paso 2 hasta que la condicin de parada se satisfaga.
6. Cuando se cumple la condicin de parada, se devuelve al mejor individuo
encontrado (bien el mejor de todas las generaciones, bien el mejor de la ltima
generacin).
Al igual que en muchas otras heursticas, el comportamiento del algoritmo gentico es
altamente dependiente de los parmetros iniciales (tamao de la poblacin, porcentaje
de cruce, porcentaje de mutacin, nmero de generaciones, etc.), por lo que ser
necesario ajustar esos parmetros para tratar de mejorar la solucin para los objetivos
del problema.
JGAP
JGAP, es un componente de algoritmos genticos y programacin gentica ofrece como
un framework Java. Proporciona mecanismos genticos bsicos que pueden ser
fcilmente utilizados para aplicar los principios evolutivos de soluciones a los
problemas. Vea los ejemplos para una demostracin o ver el rbol grfico que se puede
crear con JGAP de soluciones se encuentran los programas de gentica ha
evolucionado.
DESARROLLO
ALGORITMO PARA RESOLVER LA RUTA MS CORTA
UTILIZANDO ALGORITMOS GENETICOS EN EL LENGUAJE DE
PROGRAMACION JAVA CON EL FRAMEWORK JGAP.
Aplicacin
Ejecutamos la aplicacin y empezara a cargar:
Aparecer el nmero de ciudades o nodos para las rutas.
Tal y como vimos en el mensaje de ayuda anterior debemos hacer clic derecho sobre la
pantalla para que aparezca el nodo en la posicin deseada.
As se observar las ventanas para escribir la distancia entre ciudades o nodos.
Podemos observar que en la parte izquierda del programa se van agregando la distancia entre
las ciudades.
Una vez terminada la asignacin de distancias a las ciudades procederemos a calcular la ruta
ms ptima.
Bien una vez calculado se mostrara una ventana con los resultados.
CONCLUSIONES
El uso de jgap facilita la resolucin de problemas de algoritmos genticos
al implementar ya un algoritmo preestablecido para generar la poblacin.
Al utilizar algoritmos genticos no se podrn resolver todo tipo de
problemas, sino los que cumplan las condiciones necesarias para el uso
de los mismos.
RECOMENDACIONES
Para saber la ruta ms ptima es necesario utilizar un while ya que no
sabemos con exactitud las generaciones que se necesiten.
Antes de resolver cualquier problema debemos identificar que el
problema se pueda resolver mediante algoritmos genticos.
