lunes, 25 de febrero de 2013

Evidencia 5 > Algoritmo Genético (mochila)


El estudio de los procesos naturales puede aplicarse al desarrollo de métodos computacionales que sirvan para resolver problemas.

Los métodos inspirados en la naturaleza buscan crear sistemas artificiales
con propiedades de sistemas naturales:

  • Inteligencia
  • Robustez
  • Tolerancia a falla
  • Degradación gradual
  • Manejo de situaciones imprevistas
Es un método estocástico de búsqueda (diseño, optimización) basado en la mecánica de la selección natural y la idea darwiniana de la superviviencia de acuerdo a la aptitud.
En un algoritmo genético, las posibles soluciones a un problema son codificadas en forma de tiras de caracteres de un alfabeto reducido (generalmente binario) que asemejan los cromosomas de seres vivos.
El algoritmo genético evoluciona una población de estos individuos aplicando operadores genéticos como selección, cruce, y mutación.

A continuación se propone los siguiente para realizar un algoritmo genético


La codificación fue creado con el lenguaje de programación Python, el paradigma utilizado: programación orientada a objetos. Nuestro objeto será el individuo que posee un cromosoma, éste compuesto por una cantidad de genes (binarios), además de poseer una cualidad (variable booleana) indicadora de sí es seleccionado para cruzarse con otro individuo, por defecto es False; recurrimos a métodos de instancia para obtener los genes: getCromo; setSeleccion y getSeleccion, establece seleccionado para cruza y obtiene el valor para saber si fue seleccionado, respectivamente. Métodos estáticos: genX (mutación de genes), elmejor(busca al individuo con mejores cualidades), combinar(toma a dos individuos los cruza y se obtienen los nuevos cromosomas), aptitud(calcula las cualidades de cada individuo de acuerdo a sus genes).



Empezamos creando los cromosomas de la población inicial, y posteriormente los individuos o instancias de la clase. Se decide guardar los cromosomas en una lista, para posterior manejo; indicamos las cualidades para determinar el "valor de cada individuo", por tratarse del Problema de la mochila: los pesos y las ganancias. La ganancia total servirá para determinar la probabilidad de seleccionar un individuo de acuerdo a su valor en ganancia.



Calculamos a ganancia por cromosoma, una vez obtenidas las ganancias buscamos al mejor cromosoma

Procedemos a seleccionar los mejores individuos para posterior cruza, para esto usamos la ganancia total y calculamos la probabilidad de que cierto individuo sea seleccionado arrojando un número pseudoaleatorio del 1 - 100; se agregan a una lista de padres. Debemos procurar que dependiendo de la población un individuo puede seleccionarse n veces, en este caso 2 veces como máximo, ya que de lo contrario el resto no podría cruzarse.





Determinados los padres, creamos la generación siguiente. Como la población inicial fue de 4 individuos, de los cuales el mejor fue seleccionado 2 veces, y otros dos individuos que se cruzaran con el mejor. No olvidemos mutar un gen del cromosoma, con el método correspondiente, cuya probabilidad es relativamente baja.


Una vez generada la generación nueva, calculamos la ganancia que producen los cromosomas nuevos, y nuevamente buscamos al mejor de los individuos resultantes, mostramos al exitoso.



Video que muestra la ejecución del Algoritmo


Como podemos apreciar la programación de algoritmos genéticos resulta muy interesante, sobre todo a sabiendas de las aplicaciones que la vida ofrece a la programación. Este algoritmo no garantiza que el resultado obtenido sea el mejor, esto es porque solamente evalúa los datos que proporcionamos (arroja las mejores soluciones en base a estos solamente), más no todas las posibles combinaciones.

martes, 19 de febrero de 2013

Evidencia 6 > Inteligencia de Enjambre


En la mayoría de los usos de ingeniería los problemas de optimización, de naturaleza continua o discreta, se presentan muy a menudo, lo que le da mucha importancia a las técnicas de optimización. Un esfuerzo enorme se ha realizado para crear técnicas de optimización, analíticas y numéricas. Entre las más recientes técnicas inspiradas en biología se encuentran Optimización por Colonia de Hormigas, en  ingles Ant Colony Optimization y Optimizacion por Enjambre de Partículas, en  ingles Particle Swarm Optimization.




viernes, 15 de febrero de 2013

Práctica 1 > Simulación de Semáforos "Inteligentes" - Laboratorio


En esta práctica,  se implementa un sistema que simula calles congestionadas  por autos y regula automáticamente la duración de las luces verdes de los semáforos. Al principio la práctica la iniciamos en Java pero nos enfrentamos con problemas y nos cambiamos a C++  ya que la mayor parte del equipo estaba familiarizado con el lenguaje y aparte este tardaba menos en correr así que solo utilizamos la lógica que habíamos implementado en java. El cruce de la calle es en forma de “T” y a continuación se muestra en la figura el diseño del cruce:



Desarrollo:
Para empezar a familiarizarse con la práctica describiremos los componentes del diseño para entender la lógica del programa:
·         Utilizamos 3 semáforos que dirige la vialidad vehicular para que no ocurra un embotellamiento, lo cual se describe con las letras A, B, C. para poder crearlos utilizamos un ciclo de while para que  se ejecutara infinitamente hasta que se cierre la aplicación. Para poder saber a cuál semáforo se le da la prioridad se utilizó un sensor en el cual detectaría  la cantidad de vehículos en cada calle dando el máximo y el mínimo.  Otro punto es de que se analizó todas las posibles combinaciones o estados en los que podían funcionar  sin que se provocara choques en los carros. El tiempo del semáforo que se utiliza en forma normal es de 28 segundos y cuando haya más vialidad se le aumenta 15 segundos y en caso contrario si es poca la vialidad se disminuyen 15 segundos.



·         Los carriles por donde viajan los vehículos se representan como colas Circulares, y a cada carril se le ha diseñado una ruta predeterminada y se representa con líneas; línea 1, linea2, linea3, linea4, linea5, linea6. En la lógica se manejó que cada línea se encuentra condiciona da en un ciclo de “for” para saber cuál debe estar activada y cual no.


       Aquí buscamos la calle mas congestionada y también la menos congestionada

·         Los carros se creen de forma aleatoria con un random cada dos segundos este congestionada la calle se crean dos carros.



*Se agrego un switch para controlar el flujo del trafico,                                                                                                             
* al estar ON se crean 2 carros cada segundo,                                                                                                                     
* al estar OFF se crean 2 carros cada 2 segundos,                                                                                                                    
* considerar el uso de 2 hilos. Todo lo necesario                                                                                                                    
* se ha dejado un hilo creado, listo para su uso...   
                                                                                                                
En la línea 5 y 6 se utilizó un factor sorpresa llamados peatones, lo cual dura 13 segundos.





Conclusiones: 

En esta practica aprendimos a manejar hilos o Thread  para poder iniciar varias tareas a la vez dentro del mismo proyecto, al mismo tiempo usamos colas para poder mantener los carros introduciendo números aleatorios(stdlib), y usamos estatutos condicionales (if, if-else, while)para poder dirigir y controlar los carros para que no chocaran. Para crear la interfaz grafica se utilizo la biblioteca gtk ya que esta es de codigo libre. otra blioteca que usamos es pthread para crear los hilos. Se recomenda iniciar con logica y dejar al final la parte grafica y llevar a cabo una investigacion de acerca de colas, hilos y un manejo exelente de estatutos condicionales, investigacion de graficos en C++, GTK o la otra opcion es QT.

Integrantes del equipo:


  • Juan David Carrillo López
  • Esaul Marquez Garcia
  • Fernando Campos Benitez 
  • Julio Alejandro Valdez Salazar



Referencias:

Java Threads(Hilos en Java)Inmaculada González Pérez, Antonio Juan Sánchez Martín, David Vicente Hernández, Departamento de Informática y Automática, Universidad de Salamanca


Libro: Algoritmos en c++

Sobre GTK

Sobre Hilos