HEURÍSTICAS
Y EL PROBLEMA DEL AGENTE VIAJERO.
HEURÍSTICAS.
Las heurísticas son métodos inteligentes que buscan una buena solución en un
tiempo de cómputo razonable, pero sin garantizar que ésta sea la óptima
(Johnson et al., 2002).
Existen diferentes tipos de heurísticas (Glover, Gutin, Yeo y
Zverovich, 2001):
· Heurísticas constructivas.
Procedimientos que se encargan de obtener una solución a partir de un criterio
inicial, esto es, construyen una solución factible.
· Heurísticas de búsqueda local.
Procedimientos para mejorar soluciones ya encontradas. Tratan de optimizar
localmente alrededor de una solución, ubicando mínimos locales.
· Heurísticas combinadas: Procedimientos
que constan de una heurística constructiva y una heurística de búsqueda local.
Algunas heurísticas para el Problema del Agente Viajero Asimétrico
son las siguientes (Cirasella, Lyle, McGeoch y Zhang, 2000):
· *El vecino más cercano (heurística constructiva).
Esta heurística se basa en la idea de moverse de
una ciudad a la siguiente.
· * Inserción aleatorizada (heurística constructiva).
La
idea central de esta heurística está basada en el algoritmo de inserción
aleatorizada, y consiste en crear una ruta inicial de la forma más económica
posible.
· *Búsqueda local (2-opt).
El
movimiento 2-Opt consiste en eliminar dos aristas rompiendo una ruta inicial en
dos caminos.
· * Experimentación computacional
Los
algoritmos de las heurísticas descritas se implementaron computacionalmente, y
se resolvieron tanto instancias pequeñas como de la librería electrónica
TSPLIB4.
La palabra «heurística» aparece en más de una
categoría gramatical.
Cuando se usa como sustantivo,
identifica el arte o la ciencia del descubrimiento, una disciplina susceptible
de ser investigada formalmente.
Cuando aparece como adjetivo, se refiere a cosas más concretas, como estrategias
heurísticas, reglas
heurísticas o silogismos y conclusiones heurísticas.
Claro está que estos dos usos están íntimamente
relacionados ya que la heurística usualmente propone estrategias heurísticas
que guían el descubrimiento.
El término fue utilizado por Albert Einstein en
la publicación sobre efecto fotoeléctrico (1905), con el cual obtuvo el premio
Nobel en Física en el año 1921 y cuyo título traducido al idioma español es:
“Heurística
de la generación y conversión de la luz”
Actualmente se han hecho adaptaciones al término en diferentes
áreas, así definen la Heurística como un arte, técnica o procedimiento práctico o informal, para resolver problemas.
Según el matemático George Pólya la
base de la heurística está en la experiencia de resolver problemas y en ver
cómo otros lo hacen. Consecuentemente se dice que hay búsquedas ciegas,
búsquedas heurísticas (basadas en la experiencia) y búsquedas racionales.
Una heurística es un algoritmo que abandona uno o
ambos objetivos; por ejemplo, normalmente encuentran buenas soluciones, aunque
no hay pruebas de que la solución no pueda ser arbitrariamente errónea en
algunos casos; o se ejecuta razonablemente rápido, aunque no existe tampoco
prueba de que siempre será así.
En computación, dos
objetivos fundamentales son encontrar algoritmos con buenos tiempos de
ejecución y buenas soluciones, usualmente las óptimas.
*Heurísticas en la
inteligencia artificial.
Muchos algoritmos en la inteligencia artificial son heurísticos por
naturaleza, o usan reglas heurísticas.
Un ejemplo reciente es SpamAssassin que usa una amplia
variedad de reglas heurísticas para determinar cuando un correo electrónico es spam.
Cualquiera de las reglas usadas de forma
independiente pueden llevar a errores de clasificación, pero cuando se unen
múltiples reglas heurísticas, la solución es más robusta y creíble.
Esto se llama alta credibilidad en el
reconocimiento de patrones (extraído de las estadísticas en las que se basa).
Cuando se usa la palabra heurística en el procesamiento del lenguaje basado en
reglas, el reconocimiento de patrones o el procesamiento de imágenes, es usada
para referirse a las reglas.
Heurísticas en
antivirus.
En los productos antivirus se conoce como heurística a
las técnicas que emplean para reconocer códigos maliciosos (virus, gusanos, troyanos, etc.)
EL PROBLEMA DEL AGENTE VIAJERO.
El Problema del Agente Viajero (Traveling Salesman Problem, TSP, por sus siglas en inglés)
es quizá el más estudiado de los problemas de optimización combinatoria.
Su
popularidad se debe a que es fácil de plantear, pero difícil de resolver.
Se puede describir de la siguiente forma:
Dadas n ciudades y el costo Cij que
se tiene al viajar de una ciudad a otra, se debe encontrar la ruta de costo
mínimo para visitarlas todas pasando sólo una vez por cada una de ellas, y
regresando a la de partida. A cada ruta se le llama tour o ciclo hamiltoniano.
Entre sus
amplias aplicaciones (Applegate, Bixby, Chvatal y Cook, 2007), se encuentran:
· Reparto de productos. Donde se puede mejorar una ruta
de entrega para seguir la más corta.
de entrega para seguir la más corta.
· Transporte. Mejorando la distribución del camino seguido usando el de
menor longitud.
· Robótica. Permite resolver problemas de fabricación para minimizar el
número de desplazamientos al realizar una serie de perforaciones en una plancha
o en un circuito impreso.
· Turismo y agencias de viajes. Aun cuando los agentes de viajes no
tienen un conocimiento explícito del Problema del Agente Viajero, las compañías
dedicadas a este giro utilizan un software que hace todo el trabajo.
· Horarios de
transportes laborales y/o escolares. Estandarizar los horarios de los
transportes es claramente una de sus aplicaciones, tanto que existen empresas
que se especializan en ayudar a las escuelas a programarlos para optimizarlos
en base a una solución del TSP.
·
Inspecciones a sitios remotos. .
· Secuencias.
Donde se refiere al orden en el cual n trabajos tienen que ser procesados de
tal forma que se minimice el costo total de producción.
En el Problema del Agente Viajero, la solución es una permutación de las
N ciudades dadas, y se divide en dos tipos:
· TSP asimétrico (ATSP): En este caso, la matriz
de costos Cij no es simétrica, es decir, el costo que se
genera de viajar de la ciudad i a la ciudad j, en general, no es el
mismo que el que se tiene de viajar de la ciudad j a la ciudad i.
· TSP
simétrico (STSP): En este caso, la matriz de costos Cij es
simétrica, es decir, el costo que genera viajar de la iudad i a la ciudad j es
el mismo que el que se tiene al viajar de la ciudad j a la ciudad i.
El Problema del Agente Viajero en
su forma asimétrica tiene (n-1)! rutas posibles, esto es, (n-1)! posible
soluciones. La forma simétrica tiene tours, porque al cambiar la dirección de
la ruta ésta no cambia y sigue siendo la misma.
En general, la parte simétrica ha
sido más explorada en cuanto a investigación y desarrollo de algoritmos para
resolver el TSP.
Modelo matemático
Si se considera una matriz de distancias Cij, un grafo G=(V,A) completo y las variables de decisión Xij como variables binarias,
donde
BIBLIOGRAFIA:
http://www.postgradoeinvestigacion.uadec.mx/CienciaCierta/CC30/3.html
Applegate, D., Bixby,R., Chvatal V., Cook,W. “On the solution of the Traveling Salesman Problem”. DocumentaMathematica-Extra Volume ICM III. 1998. 645-656.
Applegate, D., Bixby,R., Chvatal V., Cook,W. “On the solution of the Traveling Salesman Problem”. DocumentaMathematica-Extra Volume ICM III. 1998. 645-656.
0 comentarios:
Publicar un comentario