Monografias.com > Estadística > Matemáticas
Descargar Imprimir Comentar Ver trabajos relacionados

Metaheurística de optimización mediante colonias de hormigas y aplicaciones



    Resumen:

    La mayoría de los Problemas de
    Optimización Combinatoria de interés
    científico o práctico están incluidos en la
    clase NP-completos, ya que no existen algoritmos exactos con
    complejidad polinómica que permitan resolverlos. Debido a
    su intratabilidad, se han diseñado una gran cantidad de
    métodos aproximados, los cuales encuentran buenas
    soluciones en tiempos razonables. Uno de estos métodos es
    la metaheurística de Optimización mediante Colonias
    de Hormigas (ACO); que tiene su fuente de inspiración en
    el comportamiento de las hormigas reales, que minimizan el
    recorrido entre su colonia y cualquier fuente de abastecimiento,
    basándose fundamentalmente en los rastros de feromona que
    van dejando a su paso. Para la metaheurística ACO se han
    propuesto varios algoritmos, que desde su surgimiento han probado
    su amplia aplicabilidad y eficiencia en la solución de
    Problemas de Optimización Combinatoria.

    Palabras Claves:
    Optimización mediante Colonias de Hormigas, Sistema de
    Hormigas, Sistema Colonia de Hormigas, Sistema de Hormigas Max-
    Min, Sistema de Hormigas con Ordenación, Sistema
    Mejor-Peor Hormiga, ACO en Dos Etapas.

    I.
    INTRODUCCIÓN

    La existencia de una gran cantidad y variedad de
    Problemas de Optimización Combinatoria incluidos en la
    clase NP-completos que necesitan ser resueltos de forma
    eficiente, impulsó el desarrollo de procedimientos para
    encontrar buenas soluciones, aunque no fueran óptimas.
    Estos métodos, en los que la rapidez del proceso es tan
    importante como la calidad de la solución obtenida, se
    denominan heurísticos o aproximados. Un método
    heurístico es un procedimiento para resolver
    un problema de optimización bien definido mediante una
    aproximación intuitiva, en la que la estructura del
    problema se utiliza de forma inteligente para obtener una buena
    solución [1]. Luego, con el propósito de obtener
    mejores resultados que los alcanzados por los heurísticos
    tradicionales surgen los denominados procedimientos
    metaheurísticos. Los procedimientos metaheurísticos
    son una clase de métodos aproximados que están
    diseñados para resolver problemas difíciles de
    optimización combinatoria, en los que los
    heurísticos clásicos no son efectivos. Los
    metaheurísticos proporcionan un marco general para crear
    nuevos algoritmos híbridos combinando diferentes conceptos
    derivados de la inteligencia artificial, la evolución
    biológica y los mecanismos estadísticos [2,
    3].

    Se han desarrollado varias metaheurísticas para
    solucionar problemas de optimización, entre ellas se
    encuentran: Búsqueda Tabú [4], Recocido Simulado
    [5], GRASP [6], Algoritmos Genéticos [7],
    Optimización mediante Mallas Dinámicas o Dynamic
    Mesh Optimization (MDO) [8], Optimización basada en
    Enjambre de Partículas o Particle Swarm Optimization (PSO)
    [9, 10] y Optimización basada en Colonias de Hormigas [11,
    12], de esta última incluida en la categoría de los
    algoritmos bioinspirados o de vida artificial e inteligencia
    colectiva [13], trataremos el presente trabajo.

    II.
    METAHEURÍSTICA DE OPTIMIZACIÓN MEDIANTE COLONIAS DE
    HORMIGAS

    La metaheurística Optimización mediante
    Colonias de Hormigas o Ant Colony Optimization [14], propuesta
    para resolver problemas complejos de optimización
    combinatoria, tiene su fuente de inspiración en el
    comportamiento de colonias de hormigas reales. Las hormigas son
    capaces de seguir la ruta más corta en su camino de ida y
    vuelta entre la colonia y una fuente de abastecimiento. Al
    desplazarse cada una va dejando un rastro de una sustancia
    química llamada feromona a lo largo del camino seguido,
    "transmitiéndose información" entre ellas de esta
    forma [15]. Las feromonas forman un sistema indirecto de
    comunicación química entre animales de una misma
    especie, que transmiten información acerca del estado
    fisiológico, reproductivo y social, así como la
    edad, el sexo y el parentesco del animal emisor, las cuales son
    recibidas en el sistema olfativo del animal receptor, quien
    interpreta esas señales, jugando un papel importante en la
    organización y la supervivencia de muchas especies
    [16].

    Al iniciar la búsqueda de alimento, una hormiga
    aislada se mueve a ciegas, es decir, sin ninguna señal que
    pueda guiarla, pero las que le siguen deciden con buena
    probabilidad seguir el camino con mayor cantidad de feromona.
    Considere la Figura 1 donde se observa cómo las hormigas
    establecen el camino más corto. En la figura (a) las
    hormigas llegan a un punto donde tienen que decidir por uno de
    los caminos que se les presenta, lo que resuelven de manera
    aleatoria. En consecuencia, la mitad de las hormigas se
    dirigirán hacia un extremo y la otra mitad hacia el otro
    extremo, como ilustra la figura (b). Ya que las hormigas se
    mueven aproximadamente a una velocidad constante, las que
    eligieron el camino más corto
    alcanzarán el otro extremo más rápido que
    las que tomaron el camino más largo, quedando depositada
    mayor cantidad de feromona por unidad de longitud, como ilustra
    la figura (c). La mayor densidad de feromonas depositadas en el
    trayecto más corto hace que éste sea más
    deseable para las siguientes hormigas y por lo tanto, la
    mayoría elige transitar por él. Considerando que la
    evaporación de la sustancia química hace que los
    caminos menos transitados sean cada vez menos deseables y la
    realimentación positiva en el camino con más
    feromona, resulta claro que al cabo de un tiempo casi todas las
    hormigas transiten por el camino más corto, como se
    ilustra en la figura (d) [16].

    Monografias.com

    Figura 1: Comportamiento de las hormigas
    reales.

    En analogía con el ejemplo biológico, ACO
    se basa en la comunicación indirecta de una colonia de
    agentes simples, llamados hormigas (artificiales), por medio de
    la huella de feromona (artificial). La huella de feromona en ACO
    sirve como información numérica distribuida, que
    las hormigas usan para la construcción
    probabilística de soluciones del problema a resolver y la
    adaptan durante la ejecución del algoritmo para reflejar
    su experiencia de búsqueda [17]. La estructura de un
    algoritmo genérico de la metaheurística ACO es la
    siguiente:

    1 procedimiento metaheurística_ACO()

    2
    inicialización_de_parámetros

    3 mientras
    (criterio_de_terminación_no_satisfecho)

    4 programación_de_actividades

    5 hormigas_y_actividad()

    6 evaporación_de_feromona()

    7 acciones_del_demonio() {opcional}

    8 fin programación_de_actividades

    9 fin mientras

    10 fin procedimiento

     

    1 procedimiento hormigas_y_actividad()

    2 repetir en paralelo desde k=1 hasta
    número_hormigas

    3 nueva_hormiga(k)

    4 fin repetir en paralelo

    5 fin procedimiento

     

    1 procedimiento nueva_hormiga(id_hormiga)

    2 inicializa_hormiga(id_hormiga)

    3 L = actualiza_memoria_hormiga()

    4 mientras (estado_actual ?
    estado_objetivo)

    5 P =
    calcular_probabilidades_de_transición(A,L,W)

    6 siguiente_estado =
    aplicar_política_decisión(P,W)

    7 mover_al_siguiente_estado(siguiente_estado)
    si
    (actualización_feromona_en_línea_paso_a_paso)

    8 depositar_feromona_en_el_arco_vistado()
    fin si

    9 L = actualizar_estado_interno()

    10 fin mientras si
    (actualización_feromona_en_línea_a_posteriori)

    11 para cada arco visitado

    12 depositar_feromona_en_el_arco_visitado()

    13 fin para fin si

    14 liberar_recursos_hormiga(id_Hormiga)

    15 fin Procedimiento

     

    Las hormigas de la colonia se mueven, concurrentemente y
    de manera asíncrona, a través de los estados
    adyacentes de un problema, que puede representarse en forma de
    grafo con pesos. Este movimiento se realiza siguiendo una regla
    de transición basada en la información local
    disponible en las componentes o nodos. Esta información
    incluye una heurística y una memorística (rastros
    de feromona) para guiar la búsqueda. La
    inicialización_de_parámetros
    depende del algoritmo específico, generalmente deben
    tenerse en cuenta parámetros como: el rastro inicial de
    feromona asociado a cada transición o arco, el
    número de hormigas en la colonia, los pesos que definen la
    proporción en la que afectarán la
    información heurística y memorística en la
    regla de transición probabilística. En
    programación_de_actividades se
    controla la planificación de tres componentes: la
    generación y puesta en funcionamiento de
    lashormigas artificiales; la evaporación de
    feromona, que se usa como un mecanismo para evitar el
    estancamiento en la búsqueda y permitir que la hormigas
    busquen y exploren nuevas regiones del espacio; y las acciones
    del demonio, utilizadas para implementar tareas desde una
    perspectiva global que no pueden llevar a cabo las hormigas, por
    ejemplo, observar la calidad de todas las soluciones generadas y
    depositar una nueva cantidad de feromona adicional en las
    transiciones asociadas a algunas soluciones. El
    procedimiento actualiza_memoria_hormiga()
    se encarga de especificar el estado inicial desde el que la
    hormiga comienza su camino y además almacenar la
    componente correspondiente en la memoria de la hormiga
    L. La decisión sobre cuál será el
    nodo inicial depende del algoritmo específico. En los
    procedimientos
    calcular_probabilidades_de_transición
    y
    aplicar_política_decisión se
    tienen en consideración el estado actual de la hormiga y
    el conjunto de arcos del grafo (A), los valores actuales
    de la feromona visibles en dicho nodo y las
    restricciones del problema (W) para establecer el
    proceso de transición probabilístico
    hacia otros estados válidos. La
    actualización_feromona_en_línea_paso_a_paso
    es el procedimiento donde se actualiza el rastro de
    feromona asociado a un arco, cuando la hormiga se mueve entre los
    nodos que este conecta. Una vez que la hormiga ha construido la
    solución puede reconstruir el camino
    recorrido y actualizar los rastros de feromona de
    los arcos visitados mediante el procedimiento
    llamado
    actualización_feromona_en_línea_a_posteriori
    [12, 18].

    Se han propuesto varios modelos de la
    metaheurística ACO, entre ellos se encuentran: Sistema de
    Hormigas o Ant System (AS) [14], Sistema Colonia de Hormigas o
    Ant Colony System (ACS) [11], Sistema de Hormigas Max-Min o
    Max-Min Ant System (MMAS) [19], Sistema de Hormigas con
    Ordenación o Rank-Based Ant System [20], Sistema
    Mejor-Peor Hormiga o Best-Worst Ant System [21, 22] y ACO en Dos
    Etapas o Two-Step Ant Colony Optimization (TS-ACO) [23,
    24].

    EL PRESENTE TEXTO ES SOLO UNA SELECCION DEL TRABAJO
    ORIGINAL.
    PARA CONSULTAR LA MONOGRAFIA COMPLETA SELECCIONAR LA OPCION
    DESCARGAR DEL MENU SUPERIOR.

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter