5.3: Computación social

Última actualización
Guardar como PDF

Page ID: 143714

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

El problema del vendedor ambulante es un problema vital de optimización (Gutin & Punnen, 2002; Lawler, 1985). Se trata de determinar el orden en que un vendedor debe visitar una secuencia de ciudades, deteniéndose en cada ciudad una sola vez, de tal manera que se recorra la distancia total más corta. El problema es tremendamente importante: una bibliografía moderna cita 500 estudios sobre cómo resolverlo (Laporte & Osman, 1995).

Una de las razones de la enorme cantidad de investigación sobre el problema del vendedor ambulante es que su solución se puede aplicar a una vertiginosa variedad de problemas y situaciones del mundo real (Punnen, 2002), incluyendo la programación de tareas, minimizando la interferencia entre una red de transmisores, análisis de datos en psicología, rayos X cristalografía, revisión de motores de turbina de gas, problemas de recolección de pedidos de almacén y corte de papel tapiz. También ha atraído tanto la atención porque es difícil. El problema del vendedor ambulante es un problema NP-completo (Kirkpatrick, Gelatt, & Vecchi, 1983), lo que significa que a medida que aumenta linealmente el número de ciudades involucradas en el recorrido del vendedor, el esfuerzo computacional para encontrar la ruta más corta aumenta exponencialmente.

Debido a su importancia y dificultad, se han explorado varios enfoques diferentes para resolver el problema del vendedor ambulante. Estos incluyen una variedad de algoritmos de optimización numérica (Bellmore & Nemhauser, 1968). Algunos otros algoritmos, como el recocido simulado, se derivan de metáforas físicas (Kirkpatrick, Gelatt, & Vecchi, 1983). Otros enfoques están inspirados biológicamente e incluyen redes neuronales (Hopfield & Tank, 1985; Siqueira, Steiner y Scheer, 2007), algoritmos genéticos (Braun, 1991; Fogel, 1988) y computadoras moleculares construidas usando moléculas de ADN (Lee et al., 2004).

Dada la dificultad del problema del vendedor ambulante, puede parecer una tontería suponer que agentes cognitivamente simples son capaces de resolverlo. No obstante, la evidencia muestra que una colonia de hormigas es capaz de resolver una versión de este problema, lo que ha inspirado nuevos algoritmos para resolver el problema del vendedor ambulante (¡Dorigo & Gambardella, 1997)!

Un estudio de la hormiga argentina Iridomyrmex humilis utilizó un sistema de puentes para vincular el nido de la colonia con un suministro de alimento (Goss et al., 1989). Las hormigas tuvieron que elegir entre dos rutas diferentes en dos ubicaciones diferentes en la red de puentes; algunas de estas rutas eran más cortas que otras. Cuando inicialmente se descubrió comida, las hormigas recorrieron todas las rutas con igual probabilidad. Sin embargo, poco después, surgió una fuerte preferencia: casi todas las hormigas eligieron el camino que produjo el viaje más corto entre el nido y la comida.

La solución de hormigas al problema de los vendedores ambulantes implicó una interacción entre el mundo y un comportamiento básico: a medida que Iridomyrmex humilis se mueve, deposita un rastro de feromonas; la potencia de este rastro se desvanece con el tiempo. Una hormiga que por casualidad elija el camino más corto se sumará al rastro de feromonas en los puntos de decisión antes que lo hará una hormiga que haya tomado una ruta más larga. Esto significa que a medida que otras hormigas lleguen a un punto de decisión encontrarán un rastro de feromonas más fuerte en la dirección más corta, será más probable que elijan esta dirección, y también se sumarán a la señal de feromonas.

Cada hormiga que pasa el punto de elección modifica la probabilidad de la siguiente hormiga de elegir izquierda o derecha agregando a la feromona en el camino elegido. Este sistema de retroalimentación positiva, después de la fluctuación inicial, conduce rápidamente a que una rama sea 'seleccionada'. (Goss et al., 1989, p. 581)

La capacidad de las hormigas para elegir rutas más cortas no requiere mucho poder computacional individual. La solución al problema del vendedor ambulante surge de las acciones de la colonia de hormigas en su conjunto.

La selección de la rama más corta no es el resultado de hormigas individuales comparando las diferentes longitudes de cada rama, sino que es un proceso colectivo y autoorganizativo, resultante de las interacciones entre las hormigas marcando en ambas direcciones. (Goss et al., 1989, p. 581)