Scribd
Cargar
41 vistas5 páginas

Programación Lineal

Este documento resume 10 métodos heurísticos y metaheurísticos para la resolución de problemas de optimización combinatoria: 1) Algoritmo genético, 2) Método de CLARKE AND WRIGHT, 3) Recorrido simulado, 4) Algoritmo colina de hormiga, 5) Búsqueda tabú, 6) Método húngaro, 7) Partícula de swarm, 8) Procedimiento de búsqueda adaptativa aleatorizada avariciosa (GRASP), 9) Búsqueda intensiva, y 10) Métodos metaheurísticos

Cargado por

dayan Toloza
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
41 vistas5 páginas

Programación Lineal

Este documento resume 10 métodos heurísticos y metaheurísticos para la resolución de problemas de optimización combinatoria: 1) Algoritmo genético, 2) Método de CLARKE AND WRIGHT, 3) Recorrido simulado, 4) Algoritmo colina de hormiga, 5) Búsqueda tabú, 6) Método húngaro, 7) Partícula de swarm, 8) Procedimiento de búsqueda adaptativa aleatorizada avariciosa (GRASP), 9) Búsqueda intensiva, y 10) Métodos metaheurísticos

Cargado por

dayan Toloza
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
Está en la página 1/ 5

Exposiciones programación lineal - heurísticas y metaheurísticas

1. Algoritmo genético
2. Método de CLARKE AND WRIGHT
3. Recorrido simulado
4. Algoritmo colina de hormiga
5. Búsqueda tabú
6. Método húngaro
7. Partícula de swarm
8. Procedimiento de búsqueda adaptativa aleatorizada avariciosa (grasp)
9. Búsqueda intensiva (búsqueda local,…)
10. Métodos metaheurísticos
Algoritmo genético
Un algoritmo es una serie de pasos que describen el proceso de búsqueda de una
solución a un problema concreto. Y un algoritmo genético es cuando se usan
mecanismos que simulan los de la evolución de las especies de la biología para
formular esos pasos. Es una técnica de inteligencia artificial inspirada en la idea de
que el que sobrevive es el que está mejor adaptado al medio, es decir la misma
que subyace a la teoría de la evolución que formuló Charles Darwin y que combina
esa idea de la evolución con la genética. Pero claro, ¿cómo se implementa esto
con fórmulas matemáticas? Pues lo que haces es transformar la resolución de
cualquier problema en un conjunto de soluciones en el que cada una de ellas
funciona como si fuera un individuo. Abordas los problemas de manera que
puedas decir, este conjunto de soluciones es como una población, una población
de soluciones. Imagina que tu problema a resolver es que quieres saber cuál es el
camino más corto para ir de Madrid a San Petersburgo y tienes miles de
soluciones. Cada camino que encuentres podría ser una opción, si le aplicas un
algoritmo genético, cada camino que encuentres sería un individuo. Para
poder aplicar algoritmos genéticos debes ser capaz de convertir las soluciones a
tu problema en vectores matemáticos, entonces, un vector para ir de aquí a San
Petersburgo puede ser uno que enumere las ciudades por las que vas pasando.
Puede haber muchos recorridos: unos más largos y otros más cortos, unos
tendrán más tráfico, otros tendrán menos tráfico…
Algoritmo de ahorros de Clark & Wright
El Algoritmo de ahorros de Clark & Wright, es una de las técnicas más populares
para resolver VRP (Problema de enrutamiento de vehículos) a través de
heurísticas, consiste en el principio de combinar una solución de dos rutas
diferentes para formar una nueva ruta donde se validen los ahorros. El ahorro en
la combinación de soluciones es obtenido con la siguiente fórmula (Benito
Quintanilla, 2015):
𝑠𝑖𝑗 = 𝑑𝑖0 + 𝑑0𝑗 − 𝑑𝑖𝑗 (1)
Los procedimientos propuestos en este PFC consisten, básicamente, en asignar
clientes a días y, para cada día, generar una ruta de visitas. Una vez llegados a
este punto, el programa se encuentra delante del problema del viajante de
comercio (TSP). Para resolver los TSP’s, en este proyecto se ha optado por el
algoritmo de ahorros de Clarke and Wright, en su versión en serie, que se
introduce a continuación. El algoritmo se basa en el concepto de ahorro de una
cadena de arcos respecto a la residencia del comercial(X). En la figura 2 se puede
apreciar la representación del concepto ahorro entre dos clientes. Este concepto
se entiende como la distancia o el tiempo ganado al evitar tener que volver a la
residencia del comercial para llegar de un cliente a otro.
El algoritmo de recocido simulado
El algoritmo de recocido simulado (SA) es un método iterativo que inicia con un
cierto estado s. Mediante un proceso particular genera un estado vecino s ′ al
estado actual. Si la energía, o evaluación, del estado s ′ es menor que la del
estado s, se cambia el estado s por s ′ . Si la evaluación de s ′ es mayor que la de
s entonces se puede empeorar eligiendo s ′ en lugar de s con una cierta
probabilidad que depende de las diferencias de las evaluaciones ∆f = f(s) − f(s ′ ) y
de temperatura actual del sistema T. La posibilidad de elegir un estado peor al
actual es lo que le permite a SA salir de óptimos locales para poder llegar a los
óptimos globales. La probabilidad de aceptar elegir un peor estado normalmente
se calcula por la fórmula
P(∆f, T) = e ∆f/T
Colonia de hormigas
En la disciplina de la Investigación Operativa, el algoritmo de optimización por
colonia de hormigas (Ant Colony Optimisation – ACO) es una técnica para resolver
problemas combinatorios complejos inspirada por el comportamiento que
muestran las hormigas en la naturaleza, la inteligencia de enjambre. Este
algoritmo fue propuesto por Marco Dorigo en 1992.
Una colonia de hormigas es capaz de encontrar la ruta más corta desde su
hormiguero a una fuente de comida gracias a las feromonas que desprenden.
Cuando una hormiga encuentra comida, regresa a su hormiguero mientras secreta
feromonas muy atractivas para las otras hormigas. Estas feromonas funcionan a
todos los efectos como un rastro de señales que el resto de la colonia tenderá a
seguir.Esta técnica se aplica para encontrar soluciones alternativas a problemas
clásicos como el Travelling Salesman y presenta la ventaja de adaptarse
dinámicamente a cambios en las condiciones del problema. ACO puede ser
utilizado en problemas reales relacionados con enrutamiento, muy útil por ejemplo
para empresas de paquetería

La búsqueda Tabú

La búsqueda Tabú surge, en un intento de dotar de “inteligencia” a los algoritmos


de búsqueda local. Según Fred Glover, su primer definidor, “la búsqueda tabú guía
un procedimiento de búsqueda local para explorar el espacio de soluciones más
allá del óptimo local”. La búsqueda tabú toma de la Inteligencia Artificial el
concepto de memoria y lo implementa mediante estructuras simples con el
objetivo de dirigir la búsqueda teniendo en cuenta la historia de ésta, es decir, el
procedimiento trata de extraer información de lo sucedido y actuar en
consecuencia. En este sentido puede decirse que hay un cierto aprendizaje y que
la búsqueda es inteligente. La búsqueda tabú permite moverse a una solución
aunque no sea tan buena como la actual, de modo que se pueda escapar de
óptimos locales y continuar estratégicamente la búsqueda de soluciones aún
mejores
El algoritmo Húngaro
es un algoritmo de optimización el cual resuelve problemas de asignación en
tiempo . La primera versión conocida del método húngaro fue inventado y
publicado por Harold W. Kuhn en 1955. Este fue revisado por James Menkes en
1957, y ha sido conocido desde entonces como el algoritmo Húngaro, el algoritmo
de la asignación de Munkres, o el algoritmo de Kuhn-Munkres. El algoritmo
desarrollado por Kuhn está basado fundamentalmente en los primeros trabajos de
otros dos matemáticos Húngaros: Dénes Kőnig y Jenő Egerváry. La gran ventaja
del método de Kuhn es que es fuertemente polinómico (ver Complejidad
computacional para más detalles). El algoritmo húngaro construye una solución
del problema primal partiendo de una solución no admisible (que corresponde a
una solución admisible del dual) haciéndola poco a poco más admisible.
Particula Swarm
El algoritmo Particle Swarm Optimization (PSO) fue propuesto por James Kennedy
y Rusell Eberhart en 1995 [2, 5] como una heurística de búsqueda poblacional
basada en el comportamiento social y cognitivo de ciertas especies. En ella cada
partícula representa una solución potencial dentro del espacio de búsqueda y está
caracterizada por una posición, una velocidad y una memoria de su
comportamiento pasado. En cada ciclo de vuelo, se evalúa la función objetivo para
cada partícula en su posición actual. El valor obtenido mide la calidad de la
partícula para el problema que se esté considerando. En el PSO original las
partículas vuelan a través del espacio de búsqueda influenciadas por dos factores:
a) la mejor posición que la partícula alcanzó hasta ese momento (según está
registrada en su memoria) y b) la mejor posición alcanzada por cualquier partícula
de la población o swarm. La actualización de la posición de cada partícula se
realiza a través de las siguientes dos ecuaciones:
veli,j = veli,j + cl * r1 * (pi,j – partid) + c2 * r2 * (pg,j – partid) (1)
partid = parti,j + veli,j (2)
Procedimiento de búsqueda adaptativa aleatorizada avariciosa (grasp)
Un algoritmo de tipo Greedy Randomized Adaptive Search Procedure (GRASP) es
una metaheurística iterativa multiarranque que en cada iteración realiza dos fases
perfectamente definidas. La primera de ellas construye una solución factible al
problema, adicionando uno a uno los elementos según un criterio de utilidad
asignado a cada elemento. La segunda fase optimiza mediante la exploración del
vecindario de soluciones hasta caer en un óptimo local. Esta metaheurística ha
sido aplicada a la resolución de múltiples problemas combinatorios de alta
complejidad, por ejemplo: empaquetamiento de conjuntos (Delorme, Gandibleux y
Rodríguez, 2004), max-min diversity problem (MMDP) (Resende et al., 2010),
programación de la producción en ambiente Job Shop (Aiex, Binato y Resende,
2003), corte y empaquetado (Álvarez-Valdés, Parreno y Tamarit, 2008),
programación de proyectos con recursos parcialmente renovables (Álvarez-
Valdés et al., 2008), cartero chino mixto (Corberan, Marti y Sanchis, 2002),
recolección y distribución de un producto (Hernández-Pérez, Rodríguez-Martín y
Salazar-González, 2009), entre otros.
Búsqueda intensiva (búsqueda local,…)

Búsqueda local es la base de muchos de los métodos usados en problemas de


optimización.Se puede ver como un proceso iterativo que empieza en una solución
y la mejora realizando modificaciones locales. Básicamente empieza con una
solución inicial y busca en su vecindad por una mejor solución. Si la encuentra,
reemplaza su solución actual por la nueva y continua con el proceso, hasta que no
se pueda mejorar la solución actual El cómo se busca la vecindad y cuál vecino se
usa en el reemplazo a veces se conoce como la regla de pivoteo (pivoting rule),
que en general puede ser:

 Seleccionar el mejor vecino de todos (best-improvement rule).


 Seleccionar el primer vecino que mejora la solución (first-improvement rule).

Búsqueda local tiene la ventaja de encontrar soluciones muy rápidamente.Su


principal desventaja es que queda atrapada fácilmente en mínimos locales y su
solución final depende fuertemente de la solución inicial. Búsqueda local es un
método determinístico y sin memoria. Dada una misma entrada, regresa la misma
salida.De hecho un conjunto de entradas nos generan la misma salida (mínimo
local). Esto se puede ver como un pozo de atracción. Esto sigue siendo muy
superior a búsqueda aleatoria y el ingrediente principal es la definición de
vecindad que permite moverse de una cierta solución a una mejor solución.

Métodos metaheurísticos
Los algoritmos metaheurísticos son algoritmos aproximados de optimización 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.

También podría gustarte