Page 8 - Tlahuizcalli CB-31_Neat
P. 8
I. Introducción cíclica con pesos. Por último, en las aplicaciones es
generalmente el tiempo de cómputo o el de
Uno de los problemas más populares y estudiados realización de un proceso tecnológico concreto.
en el campo de la optimización, es el problema del Existen otros enfoques y modelos para plantear y
vendedor viajero o TSP (Travelling Salesman resolver el TSP que no se mencionan en este
Problem), el cual consiste en encontrar la ruta más trabajo porque se optó por dar una visión
corta posible o de menor costo entre un conjunto panorámica de una sola técnica, consistente en el
de ciudades dadas, tal que cada ciudad sea algoritmo del recocido simulado para resolver el
visitada exactamente una vez, regresando al final TSP, y que además fuera accesible a estudiantes
a la ciudad de origen. de nivel licenciatura.
Un modelo probabilístico, dado por una Brevemente, se pueden mencionar algunas
variable aleatoria, se obtiene a través de un aplicaciones del problema del vendedor viajero,
método computacional, consistente en los en donde el concepto de ciudad se sustituye por
algoritmos de recocido simulado y Metrópolis, los cualquier cosa que se corresponda con un punto
cuales se pueden deducir de manera natural una o parada de un proceso, desde los obvios como
vez que se estudian a detalle como analogías de clientes en un itinerario; estrellas y otros lugares en
un fenómeno termodinámico conocido el cielo en Astronomía Observacional;
comúnmente como recocido. Precisamente, esta perforaciones en la manufactura de
solución dada por dichos algoritmos es la que semiconductores; puntos de soldadura y de
resuelve de forma aproximada el problema de inspección en placas de circuitos impresos; puntos
optimización que se plantea en el TSP. En este de medición de densidad electrónica en
sentido, se debe resaltar que debido a la cantidad difractómetros usados en cristalografía de rayos X;
de cálculos involucrados en la mayoría de las fragmentos de ADN, en la secuenciación del
aplicaciones interesantes del TSP (lo que se refleja mismo, etc. En todos estos casos se busca
directamente como tiempo de cómputo) es encontrar trayectorias cercanas a la óptima que
mucho más conveniente encontrar una buena minimicen el tiempo de trabajo, debido al gran
aproximación que buscar la solución exacta del número de paradas en dichos procesos. Para más
problema. La solución dada por los algoritmos del información ver (Ancau, 2008), (Bland, 1989),
recocido simulado y Metrópolis garantizan la (Katagiri, 2016)
convergencia de la solución aproximada a la
exacta, dado a que satisfacen lo se conoce como Este trabajo está escrito de la siguiente manera.
el principio del balance detallado o reversibilidad En la sección 2 se describen de manera general
microscópica, lo cual fue demostrado en un algunos algoritmos, entre ellos el de recocido
contexto más general por Tierney en 1994, ver simulado, que son ampliamente utilizados para
(Tierney, 1994), () por lo tanto, la única restricción encontrar la solución al problema del viajero. En la
para su uso tiene que ver con que se encuentren sección 3 se desarrolla un modelo de la Física
buenas aproximaciones en tiempos razonables, lo Estadística para deducir los algoritmos de
que depende solamente del número de ciudades, Recocido Simulado y Metrópolis, este último es un
por lo que en los casos donde el tamaño del método del tipo Montecarlo utilizado para generar
problema a optimizar es muy grande, el muestras de estados de un sistema
desempeño promedio del algoritmo utilizado (en termodinámico. En la sección 4 se muestra la
este caso el recocido simulado) ha justificado su implementación computacional y resultados del
uso por encima de consideraciones como la del problema de optimización para calcular el camino
peor escenario posible. Para más detalles, ver óptico óptimo, en un sistema de percolación 3D,
(Kirkpatrick, 1983). donde se realizan los cálculos para el número de
lugares antes y después de la percolación bajo
Existe un sinfín de aplicaciones en Ciencia y distintos tamaños de sistema 3D. Finalmente se
Tecnología, dependiendo de cuál sea la función muestran las conclusiones en la sección 5.
de costo que se desea minimizar en promedio.
Para la Física Estadística dicha función es
generalmente la Energía Potencial; en tanto que la
función objetivo es la suma de los pesos si
consideramos la trayectoria como una gráfica
7
Tlahuizcalli ISSN: 2448-7260 Año 11 Núm. 31 enero-abril 2024
