Complejidad computacional y metaheuristica

UNIVERSIDA DE PAMPLONA

TEMA:

COMPLEJIDAD COMPUTACIONAL Y HEURÍSTICAS.

MATERIA:

ANÁLISIS DE ALGORITMOS GRUPO: A

PRESENTA:

JOHAN SEBASTIAN QUINTERO ROJAS

CC.1094283053

DOCENTE:

JORGE OMAR PORTILLA JAIMES

PAMPLONA 27 DE MAYO DEL 2020

RESUMEN

El objetivo fundamental de la Complejidad Computacional es clasificar los problemas de acuerdo a su tratabilidad, tomando el o los algoritmos más eficientes para resolverlos, para resolver estos problemas se necesita una mejora en los algoritmos, pero no una pequeña mejora sino una mejora en órdenes de magnitud por ejemplo, una búsqueda secuencial en un arreglo ordenado es de Θ (n) en el peor caso y una búsqueda binaria es de Θ (logn). Para instancias pequeñas la diferencia puede no ser notable, pero a mayores valores de n esta diferencia es más visible y es más razonable pensar él porque es tan importante determinar y afirmar la eficiencia de un algoritmo.

INTRODUCCIÓN

La clasificación de los problemas se determina por un modelo matemático denominado Máquina de Turing(MT), esta puede ser determinista(MTD) y no determinista(MTND). La diferencia entre las dos es que una puede para cada estado tener como máximo una transición a otro estado y la otra puede tener más de una transición a estados diferentes respectivamente.

De la máquina de Turing  surgen los problemas de decisión que son aquellos problemas que se pueden solucionar y ejecutar en una computadora, y que se pueden demostrar matemáticamente por medio de este modelo. Considerando la complejidad computacional un problema de decisión puede ser de clase  P, NP y NP-Completo, los cuales definen como: Clase P: Subconjunto de problemas NP que una MT determinista puede resolver en tiempo polinómico; Clase NP: Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico en una MT no determinista; NP-Completo: es un subconjunto de NP característico  por ser problemas sumamente difíciles de resolver para una maquina en un tiempo razonable.

Otro tipo de problemas son los no decidibles, que es un conjunto de problemas ajeno a los decidibles (como se ilustra la imagen 1) y que se pueden describir pero no se pueden representar o resolver.

[pic 1]

[pic 2]

Con el pasar del tiempo siguen apareciendo nuevos problemas del tipo NP-completo, lo que ha dado lugar a que se hayan realizado muchas propuestas de algoritmos para tratar de solucionarlos. Las técnicas existentes se pueden clasificar básicamente en algoritmos exactos o aproximados. Los algoritmos exactos intentan encontrar una solución óptima y demostrar que la solución obtenida es de hecho la óptima global. Debido a que los algoritmos exactos muestran un rendimiento pobre para muchos problemas se han desarrollado múltiples tipos de algoritmos aproximados que proporcionan soluciones de alta calidad para estos problemas. Los algoritmos aproximados se pueden clasificar en dos tipos principales: algoritmos constructivos y algoritmos de búsqueda local. Los primeros se basan en generar soluciones desde cero añadiendo componentes a cada solución paso a paso. Los algoritmos de búsqueda local intentan repetidamente mejorar la solución actual con movimientos a soluciones vecinas, el caso más simple son los algoritmos de mejora iterativos.

Metaheuristica.

Los algoritmos metaheurísticos son algoritmos aproximados de optimización combinatoria y búsqueda de propósito general. Son procedimientos iterativos que guían una heurística subordinada combinando de forma inteligente distintos conceptos para explorar y explotar adecuadamente el espacio de búsqueda. Un método metaheuristico muy conocido es el de optimización basada en colonia de hormigas 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. Estos insectos cuando están en búsqueda de la comida inicialmente exploran el área alrededor de su nido de una forma aleatoria. Tan pronto encuentran fuentes de alimentos, evalúan su cantidad y calidad, y llevan alguna parte de esta comida para su nido. Durante el regreso al nido, las hormigas depositan una sustancia química llamada feromona sobre el camino, la cual servirá de guía futura para que las demás encuentren los alimentos.

[pic 3]

[pic 4]

El caso más práctico de comprender es cuando las hormigas tienen dos caminos a escoger (imagen 2). Donde en A un grupo de hormigas debe decidir ir por arriba y el otro por abajo aleatoriamente, porque aún no hay presencia de feromona en los dos caminos. Observando en B se sabe que el camino superior es más corto y por eso el grupo de hormigas de ese camino llega primero a la comida con respecto al grupo del camino inferior. Lo que conlleva a que las hormigas elijan dejar más feromona en el camino superior (por ser más corto) en comparación con el inferior.

Basándose en este comportamiento natural. Marco Dorigo en 1992 propuso un algoritmo de optimización que de forma iterativa. El algoritmo se basa en emular una hormiga k en un punto x para que deje rastros de feromona  desde este punto a un punto y de forma probabilística, y dependiendo de la intensidad de esta sustancia, se llega a una solución del problema. La probabilidad de que tiene la hormiga de trasladarse de un punto x a un punto y está definido por la siguiente expresión.

[pic 5]

[pic 6]

Donde  representa la cantidad de feromona depositada en un punto de la matriz de feromona y  es la característica que interviene en la selección del recorrido (visibilidad) que se está construyendo y se denota como:[pic 7][pic 8]

...