PROGRAMACIÓN LINEAL – HEURISTICA Y METAHEURISTICA
JOHAN ANDRÉS GALEANO GALVIZ – INGENIERÍA DE SISTEMAS
ALGORITMO GÉNETICO
Es un método para solucionar problemas de optimización con o sin restricciones
basándose en un proceso de selección natural que imita la evolución biológica.
Este algoritmo modifica repetidamente una población de soluciones individuales.
En cada paso, el algoritmo genético selecciona individuos de la población actual
aleatoriamente y los utiliza como padres para producir los hijos de la siguiente
generación. Tras varias generaciones sucesivas, la población "evoluciona" hacia
una solución óptima.
Método de Clarke and Wright
Se basa en determinar las mejores rutas y/o asignaciones para la entrega de
bienes a clientes que se encuentran distribuidos geográficamente.
El ahorro en la combinación de soluciones es obtenido con la siguiente fórmula
donde,
𝑠𝑖𝑗 es el valor del ahorro.
𝑑𝑖0 es el costo del arco 𝑖 al punto 0 o depósito.
𝑑0𝑗 es el costo del arco 0 o depósito al punto 𝑗.
𝑑𝑖𝑗 es el costo del arco 𝑖 al punto 𝑗.
Recocido Simulado
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:
Algoritmo Colonia de Hormigas
Es un método meta heurístico basado en el comportamiento real de este insecto.
Está compuesto por algoritmos utilizados para obtener soluciones a problemas
complejos y de optimización en una cantidad razonable de tiempo de cómputo.
También se deben de tener en cuenta otras características que hacen que las
hormigas artificiales posen capacidades que no tienen las reales, pero que
contribuyen a la resolución del problema, por ejemplo; cada hormiga es capaz de
determinar qué tan lejos está de un estado, poseen información acerca de su
ambiente y la utilizan al tomar decisiones y tienen memoria, la cual es necesaria
para asegurar que se generen sólo soluciones factibles (Mendoza, 2001).
Para aplicar el algoritmo OCH es necesario establecer una secuencia de pasos,
los cuales se indican a continuación.
A. Representar el problema mediante nodos.
B. Definir el significado de los rastros de feromona de una manera adecuada.
C. Poner pesos a la información heurística en cada nodo o arco.
D. Desarrollar algoritmos que permitan realizar optimizaciones locales.
E. Escoger un algoritmo OCH específico.
F. Refinar los parámetros del algoritmo de OCH.
Búsqueda TABU
Es una combinación de búsqueda local con un mecanismo de memoria a corto
plazo. se basa en dos elementos claves: primero se restringe la búsqueda al
clasificar ciertos movimientos como prohibidos (tabú), posteriormente se permite
una búsqueda libre por un período corto, utilizando una función de memoria corta
que provee “estrategias de olvido”, lo que permite utilizar movimientos tabú por un
período corto, si este movimiento mejora cualquier otra solución, esto se conoce
como "el criterio de aspiración". Esto crea el procedimiento básico conocido como
“relación dual” entre las restricciones tabú y el criterio de aspiración para construir
y guiar el proceso de búsqueda.
Método Húngaro
Es un algoritmo que se utiliza en problemas de asignación cuando se quiere
minimizar el costo. Es decir, se usa para encontrar el costo mínimo al asignar
varias personas a diversas actividades basadas en el menor costo. Se debe
asignar cada actividad a una persona diferente.
El método húngaro consta de cuatro pasos. Los primeros dos pasos se ejecutan
una sola vez, mientras que los pasos 3 y 4 se repiten hasta encontrar una
asignación óptima.
Paso 1: restar los mínimos de cada fila
Paso 2: restar los mínimos de cada columna
Paso 3: cubrir todos los ceros con un mínimo número de líneas
Paso 4: crear ceros adicionales
Partícula de Swarm
Es un método de optimización heurística orientado a encontrar mínimos o
máximos globales. Su funcionamiento está inspirado en el comportamiento que
tienen las bandadas de pájaros o bancos de peces en los que, el movimiento de
cada individuo (dirección, velocidad, aceleración…), es el resultado de combinar
las decisiones individuales de cada uno con el comportamiento del resto.
Procedimiento de búsqueda adaptativa aleatorizada avariciosa (GRASP)
Es un procedimiento iterativo donde cada paso consiste en una fase de
construcción y una de mejora. En la fase de construcción se construye
iterativamente una solución factible, añadiendo un elemento en cada paso. En
cada iteración la elección del próximo elemento para ser añadido a la solución
parcial viene determinado por una función greedy. Esta función mide el beneficio
de añadir cada uno de los elementos y se elige la mejor. Es necesario resaltar el
hecho de que esta medida es “miope” en el sentido que no tiene en cuenta qué
ocurrirá en iteraciones sucesivas una vez que se hace una elección, sino
únicamente en la iteración actual.
El funcionamiento del GRASP se puede estructurar de la siguiente manera:
1. Fase Constructiva:
Generar una lista de candidatos mediante la utilización de la función
greedy.
Considerar una lista restringida de los mejores candidatos.
Seleccionar aleatoriamente un elemento de la lista restringida.
Repetir el proceso hasta constituir una solución de partida.
2. Fase de Mejora:
Hacer un proceso de búsqueda local a partir de la solución
construida hasta que no se pueda mejorar más.
3. Actualización:
Si la solución obtenida mejora a la mejor almacenada,
actualizarla.
Búsquedas intensivas (Búsqueda local, …)
Métodos Meta heurísticos
son estas estrategias generales para construir algoritmos, que quedan por encima
de las heurísticas, y van algo más allá, se denominan meta heurísticas
WEBGRAFÍA:
https://la.mathworks.com/discovery/genetic-algorithm.html
http://www.cs.us.es/~fsancho/?e=65
https://imt.mx/archivos/Publicaciones/PublicacionTecnica/pt538.pdf
https://decidesoluciones.es/colonia-de-hormigas-y-calculo-de-rutas /
https://core.ac.uk/download/pdf/20482473.pdf
http://tesis.uson.mx/digital/tesis/docs/18920/Capitulo2.pdf
https://www.lifeder.com/metodo-hungaro/
https://www.cienciadedatos.net/documentos/49_optimizacion_con_particle_
swarm
http://bibing.us.es/proyectos/abreproy/3888/fichero/cap3.pdf
