Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

HEURISTICLAB: ESTUDIO DE UN FAMEWORK METAHEURÍSTICO

No description
by

Pilar Castillo

on 22 September 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of HEURISTICLAB: ESTUDIO DE UN FAMEWORK METAHEURÍSTICO

HEURISTICLAB: ESTUDIO DE UN FAMEWORK METAHEURÍSTICO
Autor: María del Pilar Castillo Rubio
Director: Luis de Marcos Ortega
INTRODUCCIÓN
En la vida es bastante frecuente la necesidad de encontrar soluciones que maximicen o minimicen algún recurso escaso. Cuando nos encontramos ante una situación sencilla somos capaces de resolverla directamente, pero a medida que aumenta la complejidad del problema, es necesario disponer de herramientas adicionales.

Hay una gran variedad de técnicas que nos ayudan ante esta situación. Podemos clasificarlas en dos grupos: exactas y aproximadas.
EXACTAS
Aseguran poder obtener una solución óptima para todo tipo de problema, pero también requieren un alto coste computacional. Además, un algoritmo exacto es totalmente dependiente del problema que resuelve, por lo tanto si por alguna razón se modifica el problema, el algoritmo exacto debe ser rediseñado.
APROXIMADAS
Permiten obtener una solución lo mas cercana posible a la más óptima en un tiempo razonable. Por esta razón, las técnicas aproximadas o heurísticas van tomando fuerza hoy en día.
HEURÍSTICA
"Una serie de procedimientos simples, a menudo basados en el sentido común, que se supone que obtendrán una buena solución (no necesariamente óptima) a problemas difíciles de un modo sencillo y rápido."

Ahora es el turno de conocer el concepto de metaheurística, en torno al cual va a girar nuestra herramienta HeuristicLab.
METAHEURÍSTICA
La metaheurística “es un procedimiento iterativo maestro que guía y modifica las operaciones de una heurística subordinada para producir eficientemente soluciones de alta calidad. Los procedimientos metaheurísticos se sitúan conceptualmente “encima” de los heurísticos, guiando el comportamiento de los heurísticos.”

Desventajas
Ventajas
Estrategias que guían un proceso de búsqueda.
Técnicas para un problema específico.
Se pueden describir con un alto nivel de abstracción.
Se extienden desde algoritmo de búsqueda local de baja complejidad hasta procesos de aprendizaje.
Para guiar los pasos futuros en la resolución de un problema, hacen uso de la “memoria” de la búsqueda.

No se calcula una solución exacta.
Son algoritmos probabilísticos.
No siempre existe una base teórica establecida.
TIPOS DE METAHEURÍSTICAS
TRAYECTORIA
POBLACIONAL
Establecen estrategias basadas en conjuntos de soluciones, denominadas poblaciones, que evolucionan en el espacio de búsqueda utilizando aquellos elementos que sobreviven en las continuas generaciones de poblaciones con el objetivo de aproximarse a una solución óptima.

ALGORITMO EVOLUTIVO
Los algoritmos evolutivos (EA) surgieron en el año 1960 de la mano de John Holland, quien incorporó los métodos de selección natural y supervivencia a la resolución de problemas de inteligencia artificial.
Los algoritmos evolutivos están basados en la Teoría de evolución de Darwin y en el desarrollo de la computación evolutiva. Estos algoritmos permiten solucionar problemas no lineales donde intervienen un gran número de variables de búsquedas en problemas complejos.

BÚSQUEDA DISPERSA
La Búsqueda Dispersa (SS) tiene como objetivo principal mantener un conjunto de referencia. Un conjunto de referencia es un grupo relativamente pequeño de soluciones que contiene tanto las óptimas como otras soluciones diversas. En los distintos subconjuntos de soluciones se realizan operaciones de recombinación y mejora.


Sistemas basados en Colonias de Hormigas (ACO)

Algoritmos Basados en Nubes de Partículas (PSO)

Algoritmos de estimación de la distribución (EDA)
ALGORITMO GENÉTICO
Inicialización
: Se genera aleatoriamente la población inicial, constituida por un conjunto de cromosomas que representan las posibles soluciones del problema.
Evaluación
: A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber cómo de "buena" es la solución que se está codificando.
Condición de parada
: se produce cuando se alcance la solución óptima. Normalmente se usan dos criterios de parada: al recorrer el número máximo de iteraciones (generaciones) o cuando no hay cambios en la población. Mientras se hace:

Selección
: Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados.
Cruzamiento
: La recombinación es el principal operador genético, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.
Mutación
: modifica al azar parte del cromosoma de los individuos.
Reemplazo
: se seleccionan los mejores individuos para conformar la población de la generación siguiente

"Son algoritmos de búsqueda basados en la mecánica de selección natural y de la genética natural. Combina la supervivencia del más apto entre estructuras de secuencias con un intercambio de información estructurado, aunque aleatorizado, para construir así un algoritmo de búsqueda que tenga algo de las genialidades de las búsquedas humanas".
ALGORITMO GENÉTICO
ALGORITMO DE BÚSQUEDA DISPERSA
TRAVELING SALESMAN PROBLEM
El problema del viajante trata de “encontrar entre un conjunto de ciudades, una ruta que partiendo de una ciudad y regresando a ella, recorra todas las ciudades por el camino más corto.”

HEURISTICLAB
HEURISTICLAB
Es un framework de algoritmos heurísticos y evolutivos, con una interfaz gráfica de usuario utilizada para ajustar los algoritmos para resolver un problema particular sin necesidad de tener conocimientos de programación.
HeuristicLab está desarrollado en C# y utiliza Microsoft .NET framework. Se basa en una arquitectura de plugin, de modo que se puede ampliar sin tener que modificar el código fuente original. Los plugins se encuentran muy bien acoplados y de manera bastante simple, todo gracias a las interfaces.
Separa la parte funcional de cualquier interfaz de usuario de los componentes relacionados, lo que hace posible que en el futuro se pueda utilizar el framework para la implementación de un entorno de optimización de paralelismo o para implementar una simple versión de línea de comandos que pueden ser fácil de portar a otras plataformas.
INTERFACE HEURISTICLAB
PARTE PRÁCTICA

5 ciudades
: 9 experimentos con algoritmo genético (96 optimizer) y un experimento con algoritmo de búsqueda dispersa (108 optimizer).

Parámetros de combinación GA: selección, cruce y mutación.
Parámetros de combinación SS: de cruce, ruta de reemplazo y el cálculo de similitud.

50 ciudades
: 1 experimento con 4 optimizer (2 optimizer GA y 2 optimizer de SS).



ALTERNATIVAS HEURISTICLAB

Keel es una herramienta para la evaluación de algoritmos evolutivos para minería de datos, incluyendo la regresión, clasificación y patrón de la minería.

JMetal es una herramienta de experimentación y estudio de metaheurísticas para la resolución de problemas multi-objetivo orientada en un marco basado en Java.

VEAMOS LA HERRAMIENTA

Generación de soluciones diversas
: se generan un conjunto de soluciones inicial que suele ser de un tamaño pequeño.

Conjunto de referencia
: una vez generado ese conjunto de soluciones inicial se aplica un método de mejora, esto forma el conjunto de referencia, compuesto por un conjunto de soluciones menor que el inicial. La mitad de estas soluciones son las de más calidad del conjunto de soluciones inicial y la otra mitad se obtiene seleccionando aquellas que disten más respecto a las ya incluidas en el conjunto de referencia. Por último, las soluciones escogidas se ordenan de mayor a menos respecto a su calidad.

Generación de subconjuntos
: una vez se dispone del conjunto de referencia se generan subconjuntos de éste. Las soluciones en este subconjunto se suelen agrupar de dos o más individuos.

Combinación
: se combinan entre sí las soluciones de cada subconjunto.

Mejora de soluciones
: se trata de obtener soluciones de mayor calidad que las iniciales. Esta mejora se realiza tanto en el conjunto de soluciones inicial como en las soluciones en el conjunto de referencia que se obtienen tras la combinación.
Finalmente el algoritmo se detiene cuando durante un ciclo completo no se logre ninguna solución que se considere que puede formar parte del conjunto de referencia.
Full transcript