El poder silencioso de los algoritmos

Los algoritmos se han convertido en una herramienta de uso frecuente para una buena cantidad de tareas de diferente índole. Hay quienes consideran que los algoritmos son procedimientos matemáticos complicados, pero en realidad un algoritmo no es otra cosa que un conjunto de instrucciones con una secuencia lógica, usado como procedimiento para resolver un problema. Los algoritmos indican una serie de pasos que hay que dar para llegar a la solución deseada, de una forma similar a como seguimos las instrucciones de una receta para preparar una torta.

Es precisamente la claridad de esa secuencia y la monotonía de su ejecución lo que hoy facilita implementar un algoritmo en un computador, con la ayuda de un lenguaje de programación. Además, un algoritmo suele liberarnos de ejecutar operaciones y cálculos de forma repetitiva: dejamos que sean las máquinas las que hagan ese trabajo y entreguen los resultados, evitando así una tarea que, hecha manualmente, resultaría tediosa, larga y propensa a errores.

Un ejemplo sencillo y elegante de algoritmo es el siguiente. Supongamos que queremos calcular la raíz cuadrada de un número positivo $a$, es decir, $\sqrt{a}$. El problema consiste en encontrar el valor positivo $x$ tal que $x^2 = a$, lo cual equivale a decir que 

$x = \frac{a}x$. 

A partir de esta idea, podemos partir de un valor inicial aproximado $x_0$ y observar que el punto medio entre $x_0$ y  $\frac{a}x$  es una mejor aproximación de $\sqrt{a}$ que el propio $x_0$. Si llamamos $x_1$ a ese punto medio, tenemos que: 

$x_1 = \frac{1}{2}\left(x_0 + \frac{a}{x_0}\right)$.

Este nuevo valor $x_1$, está más cerca de $\sqrt{a}$ que $x_0$.

Este proceso se puede repetir indefinidamente, formando así una sucesión $x_n$ donde cada nuevo término $x_{n+1}$ se obtiene calculando el punto medio entre el anterior, $x_n$, y la fracción $\frac{a}{x_n}$; es decir: 

$x_{n+1} = \frac{1}{2}\left(x_n + \frac{a}{x_n}\right), \quad n = 0, 1, 2, \ldots$

Para aproximar la raíz cuadrada de $a$, basta ahora calcular los primeros términos de esa sucesión, $x_0, x_1, x_2, \ldots, x_M,$hasta que la aproximación $x_M$ sea satisfactoria de acuerdo con la precisión deseada; naturalmente, a mayor precisión buscada, mayor deberá ser $M$.

Este es un algoritmo sencillo y de uso común, que puede implementarse fácilmente en un computador para obtener una respuesta aproximada al problema de calcular una raíz cuadrada.

Más recientemente se ha venido investigando el uso de otro tipo de algoritmos: los llamados algoritmos genéticos. Un algoritmo genético simula los mecanismos que sigue la evolución de las especies en la biología. Se trata de una técnica inspirada en la teoría de la evolución que formuló Charles Darwin en su obra fundamental El origen de las especies por medio de la selección natural (1859), según la cual sobrevive el individuo mejor adaptado al medio. Los algoritmos genéticos combinan esa idea de la evolución con los principios de la genética.

La pregunta es cómo traducir esta idea a fórmulas matemáticas. La técnica consiste en considerar, no ya una única solución del problema, sino muchas a la vez, agrupadas en un conjunto donde cada elemento —es decir, cada solución individual— se trata como un individuo dentro de una población.

Uno de los problemas en los que se aplica este tipo de algoritmos es el de la optimización de rutas. Pensemos, por ejemplo, en la búsqueda de la mejor ruta para ir al trabajo en una ciudad como Bogotá. Supongamos que alguien necesita llegar al centro de la ciudad todos los días a las 9 de la mañana, desplazándose desde Chía. Las opciones son numerosas: tomar la autopista norte, con al menos 20 posibilidades de calles y avenidas para completar el trayecto, o tomar la carrera séptima, que ofrece otros 15 caminos alternativos. A esto hay que sumar rutas menos directas, como las que pasan por La Calera o por Cota. Al final, el número de rutas factibles es muy alto, y el camino más corto no siempre resulta ser el más rápido.

En la búsqueda de la ruta óptima hay que tener en cuenta varios factores: la distancia, el tiempo de recorrido, el costo (peajes, combustible), el medio de transporte disponible (bicicleta, moto, automóvil, bus, taxi, Uber) y las restricciones vigentes, como el pico y placa, además de los niveles de tráfico según el horario. Cada una de las posibles rutas se considera como un individuo de la población y se transforma en un vector matemático.

Los algoritmos genéticos funcionan, para este problema, de la siguiente forma: se selecciona aleatoriamente un conjunto de caminos y se compara su eficiencia, de manera que las rutas menos eficientes se descartan y las mejores soluciones se van clasificando para luego reproducirlas, mutarlas o cruzarlas, tal como ocurre en la población de una especie. Al aplicar el mecanismo de la reproducción, surgen las soluciones correspondientes a las rutas más rápidas, mientras que se eliminan aquellas que tardan demasiado. Después puede aplicarse un cruzamiento entre las mejores rutas, combinándolas entre sí, y llevar a cabo mutaciones sobre las rutas resultantes. Al repetir este mecanismo varias veces, la población se va depurando hasta que sobreviven las mejores soluciones.

Aplicaciones como Waze o Google Maps tienen en cuenta el tráfico en tiempo real y son capaces de recalcular la ruta sobre la marcha. Buena parte de esta información proviene de los propios usuarios, quienes reportan datos del camino como el estado de la vía, los controles policiales, los accidentes y los niveles de tráfico. Estas aplicaciones también recurren a promedios estadísticos almacenados para programar y recomendar rutas; sin embargo, la elección de la mejor opción puede verse afectada por errores cuando la información suministrada o los mapas disponibles no son del todo precisos. Este tipo de programas comerciales se basa en algoritmos genéticos, pero su respuesta suele tener una utilidad limitada a un intervalo de tiempo corto, ya que la ruta elegida puede haber empeorado para cuando el usuario la recorre.

Obtener soluciones óptimas en poco tiempo de cómputo es uno de los grandes atractivos de los algoritmos genéticos, y resulta fascinante pensar que problemas complejos y actuales puedan resolverse aplicando las ideas de la evolución que formuló Darwin hace más de siglo y medio.

Como se observa, las matemáticas están en todas partes. Cuando usamos alguna de las aplicaciones con las que ya estamos familiarizados, los algoritmos que hay detrás pueden transformarse en métodos que, como las especies, también evolucionan, logrando dar respuestas cada vez mejor adaptadas al entorno en el que vivimos hoy. Los algoritmos se han propagado de tal forma, y su poder es tan grande, que resulta difícil imaginar la vida moderna sin ellos.

Comprender qué es un algoritmo, aunque sea de manera general, nos ayuda a entender mejor el mundo que nos rodea: desde una simple calculadora hasta las aplicaciones que usamos a diario para movilizarnos por la ciudad. Detrás de cada respuesta rápida y precisa que recibimos hay una secuencia lógica de pasos, muchas veces inspirada, como vimos, en la propia naturaleza. Conocer esa lógica no solo despierta curiosidad, sino que también nos permite valorar —y cuestionar— las herramientas que hoy forman parte inseparable de nuestra vida cotidiana.

@MantillaIgnacio