Practica 2 Sistemas Complejos

Introducción

Existen problemas de optimización combinatoria complejos en diversos campos como la economía, el comercio, la ingeniería, la industria o la medicina. Sin embargo, a menudo estos problemas son muy difíciles de resolver en la práctica. El estudio de esta dificultad inherente para resolver dichos problemas tiene cabida en el campo de la teoría de las Ciencias de la Computación, ya que muchos de ellos pertenecen a la clase de problemas NP-duros, lo que significa que no existe un algoritmo conocido que los resuelva en un tiempo polinomial

Las metaheurísticas incorporan conceptos de muchos y diversos campos como la genética, la biología, la inteligencia artificial, las matemáticas, la física y la neurología, entre otras. Algunos ejemplos de metaheurísticas son: Enfriamiento simulado [1, 64], búsqueda tabú [49], búsqueda local iterativa (“iterated local search”)[66], algoritmos de búsqueda local con vecindario variable (“variable neighborhood search”)[57], GRASP (“greedy randomized adaptative search procedures”) [39, 40] y algoritmos evolutivos [5, 6, 60]. Una metaheurística relativamente reciente es la Optimización basada en Colonias de Hormigas (OCH)(“Ant Colony Optimization”, ACO en inglés), la cual se inspira en el comportamiento que rige a las hormigas de diversas especies para encontrar los caminos más cortos entre las fuentes de comida y el hormiguero.

Las hormigas son insectos sociales que viven en colonias y que, debido a su colaboración mutua, son capaces de mostrar comportamientos complejos y realizar tareas difíciles desde el punto de vista de una hormiga individual. Un aspecto interesante del comportamiento de muchas especies de hormigas es su habilidad para encontrar los caminos más cortos entre su hormiguero y las fuentes de alimento.

Mientras que se mueven entre el hormiguero y la fuente de alimento, algunas especies de hormigas depositan una sustancia química denominada feromona (una sustancia que puede “olerse”). Si no se encuentra ningún rastro de feromona, las hormigas se mueven de manera básicamente aleatoria, pero cuando existe feromona depositada, tienen mayor tendencia a seguir el rastro

Pese a que la OCH es una metaheurística reciente se han desarrollado muchos heurísticas basándose en ella. Aún así es un campo al que le resta bastante tiempo de vida ya que siguen presentándose día a día nuevas tendencias que pretenden mejorar la eficacia de los algoritmos de OCH o mejorar sus tiempos de ejecución.

Objetivo

Con esta practica queremos conocer las implementaciones de estos algoritmos en aplicaciones de software con metaheurísticas que ayuden a la humanidad en alguna porción pequeña de las miles o millones de implementaciones que se dan a diario con la finalidad de avanzar tecnológicamente. Nos proporciona herramientas para nuestra formación profesional, y la manera en que podemos plantearnos soluciones a problemas complejos que nos encontremos en el camino de nuestras labores cotidianas como desarrolladores, arquitectos y por que no, dueños de empresas enfocadas a dar soluciones mediante implementaciones de software

Justificación

La elaboración de la presente práctica es para conocer los diversos algoritmos existentes en la vida cotidiana; que ademas han sido implementados bajo la observación de actividades de elementos en la naturaleza, insectos, mamíferos, etc. Que tienden a tener conductas iterativas o repetitivas que les ayudan como colonia o como manada a superar las dificultades en el trayecto hacia su alimento o hacia un punto de migración; o simplemente para defenderse.

Bajo ese precepto la practica que implementamos ocupa realizar un algoritmo ACO por sus siglas en Ingles, y que pretende retroalimentar lo anteriormente mencionado sobre las colonias de hormigas

Librerias Implementadas para el ejercicio

#include hormigas.h
#include cairomm/context.h
#include gdkmm/general.h
#include glibmm/fileutils.h
#include glibmm/main.h
#include iostream
#include sstream

Clase La hormiga

LaHormiga::LaHormiga() {
Glib::signal_timeout().connect( sigc::mem_fun(*this, &LaHormiga::on_timeout), 2000);

#ifndef GLIBMM_DEFAULT_SIGNAL_HANDLERS_ENABLED signal_draw().connect
(sigc::mem_fun(*this, &Clock::on_draw), false);
#endif
  try {
    fondo = Gdk::Pixbuf::create_from_file("./texturas/graph.png");
//implementamos el escenario
    hormiga = Gdk::Pixbuf::create_from_file("./texturas/hormiga.png");
  }
catch(const Glib::FileError& ex) 
{std::cerr << "FileError: " << ex.what() << std::endl;
  }
catch(const Gdk::PixbufError& ex) 
{std::cerr << "PixbufError: " << ex.what() << std::endl;
  }
  for(int indice = 0; indice < 100; indice++) {
    feromona[indice] = -1;
    mejorCamino[indice] = -1;
  }

Implementación de los "caminos" y sus pesos

pH[w][0] = 18; // a
  pH[w][1] = 49;
  pN[w][0] = 30;
  pN[w++][1] = 71;

  pH[w][0] = 17; // b
  pH[w][1] = 166;
  pN[w][0] = 30;
  pN[w++][1] = 185;

  pH[w][0] = 17; // c
  pH[w][1] = 281;
  pN[w][0] = 30;
  pN[w++][1] = 300;//y para cada uno de los puntos del camino

Basándonos en lo anterior las decisiones que toma la hormiga se programan de aquí hacia adelante

bool LaHormiga::on_draw(const Cairo::RefPtrCairo::Context& cr) {
  Gtk::Allocation allocation = get_allocation();
  const int width = allocation.get_width();
  const int height = allocation.get_height();
  const int lesser = MIN(width, height);
  cr->set_line_width(lesser * 0.02);
  drawEverything(cr);
  return true;
}

cr->set_source_rgba(0.0, 0.0, 1.0, 0.5);
  for(int ii = 0; ii <= indice; ii++) {
    cr->arc(pN[feromona[ii]][0], pN[feromona[ii]][1], 10.5, 0.0, 2.0 * 3.1416);
    cr->fill_preserve();
    cr->stroke();
  }

  if(end) {
    for(int w = 0; mejorCamino[w] != -1; w++) {
      cr->save();
      cr->set_source_rgb(0.0, 1.0, 0.0);
      cr->arc(pN[mejorCamino[w]][0], pN[mejorCamino[w]][1], 10.5, 0.0, 2.0 * 3.1416);
      cr->fill_preserve();
      cr->stroke();
      cr->restore();
    }
    Gdk::Cairo::set_source_pixbuf(cr, hormiga, pH[elMenor][0], pH[elMenor][1]);
    cr->paint();
  }
  if(feromona[indice] != elMenor) {
    Gdk::Cairo::set_source_pixbuf(cr, hormiga, pH[feromona[indice]][0], pH[feromona[indice]][1]);
    cr->paint();
    std::cout << feromona[indice++] << ", ";
    std::cout.flush();
  } else if(start) {
    Gdk::Cairo::set_source_pixbuf(cr, hormiga, pH[feromona[indice]][0], pH[feromona[indice]][1]);
    cr->paint();
    std::cout << elMenor;
    std::cout.flush();
    start = false;
    end = true;
  }
  drawText(cr);
}

Finalmente dejaría un rastro que las demás hormigas deberían en su momento identificar, por lo que el camino quedaría marcado por las feromonas, determinando así el camino mas corto y con menor desgaste

Por ultimo este "ultimo" código es para la implementación de esta practica de manera gráfica con su GUI, en la cual se muestran las decisiones finales, donde obtiene el mejor camino a seguir, las variantes de los caminos, la cantidad de salidas disponibles, ademas de cada una de los pesos de cada uno de los puntos evaluados, el menor de los pesos definidos

void LaHormiga::drawText(const Cairo::RefPtrCairo::Context& cr) {
  Pango::FontDescription font;
  font.set_family("Monospace");
  font.set_weight(Pango::WEIGHT_BOLD);
  std::string someText = "Practicando con algoritmos ACO";
  Glib::RefPtrPango::Layout layout = create_pango_layout(someText);
  Pango::FontDescription font_descr("sans bold 8");
  Glib::RefPtrPango::Layout pesos[39];

  cr->set_source_rgb(1.0, 0.0, 0.0);
  for(int i = 0; i < 38; i++) {
    pesos[i] = create_pango_layout(losPesos[i]);
    pesos[i]->set_font_description(font_descr);
    cr->move_to(pE[i][0], pE[i][1]);
    pesos[i]->show_in_cairo_context(cr);
  }
  //layout->set_text("test...");
  layout->set_font_description(font);
  //int text_width, text_height;
  //layout->get_pixel_size(text_width, text_height);
  cr->set_source_rgb(0.0, 0.0, 0.0);
  cr->move_to(440, 350);
  layout->show_in_cairo_context(cr);
}

void LaHormiga::setElMenor(int menor) {
  elMenor = menor;
}
void LaHormiga::setLosPesos(int *pesos) {
  std::stringstream aux[40];
  for(int i = 0; i < 40; i++) {
    aux[i] << pesos[i];
    losPesos[i] = aux[i].str();
  }
}

bool LaHormiga::on_timeout() {
  Glib::RefPtrGdk::Window win = get_window();
  if (win) {
    Gdk::Rectangle r(0, 0, get_allocation().get_width(), get_allocation().get_height());
    win->invalidate_rect(r, false);
  }
  return true;
}

Resultados

Video de la practica donde se aplican el algoritmo

-------------------------------------------------------------------------------------

Video generado por EfrenMorales.

------------------------------------------------------------------------------------

Bibliografía Consultada

1. Ángel Cobo Ortega, Ana María Serrano Bedia Un algoritmo híbrido basado en colonias de hormigas para la resolución de problemas de distribución en planta orientados a procesos. Universidad de Cantabria. XIII Jornadas de ASEPUMA.
2. Cobo, A. y Serrano, A. (2001). Algoritmos genéticos para la resolución de problemas de distribución en planta con restricciones espaciales. 5º Congreso CAIP. Campos do Jordao (Brasil).
3. G. Brassard y P. Bratley. Fundamentals of Algorithmics. Prentice Hall, Englewood Cliffs, NJ, 1996.
4. McKendall, A. R. y Shang, J. (2004): Hybrid ant systems for the dynamic facility layout problem, Computers and Operations Research, article in press.
5. Sergio Alonso, Oscar Cordón, Iñaki Fernández de Viana, Francisco Herrera. La Metaheurística de Optimización Basada en Colonias de Hormigas: Modelos y Nuevos Enfoques Departamento de Ciencias de la Computación e Inteligencia Artificial, E.T.S. Ingeniería Informática, C/ Periodista Daniel Saucedo Aranda s/n,18071 Granada(España)

Imágenes de http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms

Imagenes personales incluidas en el reporte generadas por el programa

Practica 1 "Semáforos"[Laboratorio]

Practica 1 Manejo de Clases en la practica

Métodos Utilizados

Métodos que generan todos los datos de carril y define la cantidad de veces que la simulación se ejecutará. Parámetros que ejecutan los valores que se le pasaran al metodo de simulación; determina el numero de veces que la simulación se ejecutará.

    public void Iniciar(String Corridas) {
        generadordeDatosCarril();
        simulaciones(Corridas);

    }

public void simulaciones(String Corridas) {
        int Contador = 0;
        while (Contador < Integer.parseInt(Corridas)) {

            Dibujar_Interseccion();
            MovimientoCarroHztal();
            MovimientoCarroVtcal();

            if (Inicio_semaforo == 10) {
                luces_v = "Verde";
            } else if (Inicio_semaforo == 14) {
                luces_v = "Amarillo";
            } else if (Inicio_semaforo == 15) {
                luces_v = "Rojo";
//.............................................

 

Estas clases y métodos implementados nos funcionan como un indicador o switch para la toma de decisiones sobre las demás clases y métodos implementados para indicar si se coloca o no un carro o si se mueve o no de un espacio a otro.

    public void setVProb(Float verticalProb) {
        prob_VCarro = verticalProb;
    }

    public void setHProb(Float horizontalProb) {
        prob_HCarro = horizontalProb;
    }

Ahora bien creamos una tercer clase que se encarga de darle ahora si, vida a nuestro sistema de semáforos, indicándole a los vehículos cuando podrán avanzar, cuando detenerse o en su caso, poder avanzar en sentidos contrarios al mismo tiempo en cruces hacia la izquierda de ambos sentidos, se utilizan mas pero solo mencionaremos estos dos.

//para los "verticales"
public void MovimientoCarroVtcal() {
        for (int i = ArregloVertical.size() - 1; i > -1; i--) {
            for (int j = 0; j < ArregloVertical.get(0).size(); j++) {
                if (ArregloVertical.get(i).get(j).equals("c")) { //si el elemento es igual a "c" entonces...
                    if (i == ArregloVertical.size() - 1) {
                        ArregloVertical.get(i).set(j, " "); //si el actual carro en el arreglo es el ultimo colocar un espacio vacio" "
                    } else if (i == 9 && luces_v.equals("Verde")) {//........
//para los horizontales

public void MovimientoCarroHztal() {
        for (int i = ArregloHorizontal.size() - 1; i > -1; i--) {
            for (int j = ArregloHorizontal.get(0).size() - 1; j > -1; j--) {
                if (ArregloHorizontal.get(i).get(j).equals("C")) { //si el elemento es igual a C entonces
                    if (j == ArregloHorizontal.get(0).size() - 1) {
                        ArregloHorizontal.get(i).set(j, " ");
                    } else if (luces_h.equals("Rojo") && j == 10) {//.........

Implementamos cada uno de los "threads" que correremos para el control de los semáforos, o dicho de otra manera "el flujo del sistema", mediante la implementación de cada una de las clases trabajando en su conjunto.

public class ProcessA extends CircuitoVial implements Runnable {
  public void run() {
    while (true) {
      try {
        Thread.sleep(1 + (int) (random.nextDouble() * 500));
      } catch (InterruptedException e1) {
        e1.printStackTrace();
      }
      System.out.print("A");
      contador.notifyToWakeup();
    }
  }
}

quedaría pendiente la interfaz gráfica...
Observaciones: Modificaciones realizadas, para evitar problemas o aproximaciones de plagio, comentadas y externadas en este espacio. Aclaración para los gúrus del idioma Ingles y las barreras del idioma: Semáforo para San Google y para cualquier diccionario del idioma Inglés ( Semaphore, Traffic Light(semaforos) o Traffic Lights(plural) Así que aclarado el tema... Pendiente temporal: Interfaz Gráfica y Video, de momento lo importante era ver que no se tuvieran problemas por las observaciones arriba mencionadas.

Sistemas de Reconocimiento de Voz

La siguiente información es un extracto pequeño sobre lo que es el funcionamiento de lo que hoy se considera una herramienta indispensable, no solo para las personas con capacidades diferentes, sino para personas sanas y sin problemas de lenguaje, visión o en general capacidades cognitivas.

abstract from thesis of  David Huggins Daines Doctor of Philosophy

In Language and Information Technologies.

This thesis describes MultiSphinx, a concurrent architecture for scalable, low-latency automatic speech recognition. We first consider the problem of constructing a universal “core” speech recognizer on top of which domain and task specific adaptation layers can be constructed. We then show that when this problem is restricted to that of expanding the search space from a “core” vocabulary to a superset of this vocabulary across multiple passes of search, it allows us to effectively “factor” a recognizer into components of roughly equal complexity. We present simple but effective algorithms for constructing the reduced vocabulary and associated statistical language model from an existing system. Finally, we describe the MultiSphinx decoder architecture, which allows multiple passes of recognition to operate concurrently and incrementally, either in multiple threads in the same process, or across multiple processes on separate machines, and which allows the best possible partial results, including confidence scores, to be obtained at any time during the recognition process.

El Dr David Huggins se centra en su tesis en el estudio de la arquitectura de una especie de "procesador", "core" como lo menciona el, que nos permite interactuar con el ordenador de manera que pueda reconocer nuestra voz e interpretar los sonidos que de ella se desprenden. Sin embargo el estudio del doctor va mas alla de lo que requerimos para el proyecto de la materia, nos centraremos en lo especifico que encontramos en la tesis que es, el reconocimiento de voz mediante algoritmos y funciones especificas dentro del lenguaje a utilizar.

 practical systems require that recognition be done faster than real time, or in other words, that it should take less than one second of clock time to recognize one second of input. This implies that that results of recognition should be available either concurrently with the input or as soon as possible after a chunk of input (a sentence, for example) is complete. 

An alternative view of the speech recognition problem is that instead of a decoding task, it constitutes a lossy data compression or source coding task. Here, we view speech as simply a highly redundant encoding of the original message. The goal of speech recognition in this view is to find a compact representation of the speech which jointly minimizes the entropy rate of the output, and the distortion between the original message and the output, as measured by some distortion function.

En este punto Huggins plantea que una alternativa del problema de reconocimiento de voz es que en lugar de ser una tarea de decodificación, se vea el discurso como simplemente una codificación altamente redundante del mensaje original. El objetivo de reconocimiento de voz en este punto de vista es encontrar una representación compacta de la voz que conjuntamente minimice la tasa de entropía de la salida, y la distorsión entre el mensaje original y el mensaje de salida, como se mide por una función de distorsión. Si se elige una secuencia de palabras como la representación, y la acústica negativa de la probabilidad mencionada en la hipótesis, entonces esto es en realidad muy similar a la técnica estándar de decodificación MAP, que se describe al interior del documento

Para nuestro proyecto de la materia de Sistemas Adaptativos esto es un buen comienzo, ya que lo que queremos implementar realmente existe, pero ademas, permite que sea mejorado para poder ser evaluado desde otros puntos de vista.

Mas acerca de este documento Aqui

Mas Acerca de Dr David Huggins

Entrega 1

Miembros de Equipo:

• Adrián Peña Sánchez
• Efren Morales
• Francisco Lumbreras
• Christopher Medina

Detalles del Proyecto:

Equipo Adaptativo [LABORATORIO]

Efren Morales
Daniel Iván Cruz Antiguo equipo Adrián Peña Sánchez
Francisco Lumbreras

Equipo Adaptativo [CLASE]

Adrián Peña Sánchez
Efren Morales
Francisco Lumbreras
Chriztopher Medina