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