Inteligencia artificial: algoritmos genéticos

Mi investigación gira alrededor del modelado, simulación y optimización. Y en principio, en la universidad, la docencia suele ir alineada con la investigación. Así, pertenezco al equipo docente de Computación e Inteligencia Artificial (IA). Pero curiosamente, una de las asignaturas de las que soy responsable* es Biología Molecular (BM). Realmente es una coincidencia interesante porque si bien es cierto que como informático nunca tendré los conocimientos en Biología Molecular que tiene un biólogo, difícilmente no habré oído hablar de Algoritmos Genéticos (AG). Pero ¿qué son y de dónde vienen? Uno de los campos más interesantes y estudiados de la BM es la genética. A todos nos suenan científicos como Darwin, Mendel, McClintock y conceptos como genoma, mutación, adaptación, etc. Todos ellos, de manera más o menos directa están relacionados con la genética. Pero ¿por qué nos puede interesar a l@s informátic@s? Pues, por la misma razón que observamos a las hormigas, el cerebro humano, o las abejas: todos ellos son sistemas/procesos/… capaces de solucionar problemas complejos. En el caso concreto de la genética nos fijamos en qué mecanismos utiliza la naturaleza para seleccionar individuos y asegurar la persistencia (o no de las especies que conforman). Dándole la vuelta y simplificando, l@s informátic@s recogemos de ésta una serie de mecanismos que evolucionan un conjunto de soluciones, mejorando iteración tras iteración, hasta encontrar las mejores posibles. La implementación de la idea de John H. Holland (en los años 70) no es excesivamente compleja: Partimos de una población de individuos, en que cada uno representa una solución factible del problema que se quiere resolver. Cada solución tiene una calidad asociada (fitness) y evidentemente, debe...

¿Cómo pueden las metaheurísticas ayudarnos a conseguir un mundo más inteligente?

Las metaheurísticas, de las que ya se ha hablado en anteriores entradas en este blog, son algoritmos de optimización que se encuentran en la frontera entre la computación, la inteligencia artificial, y la investigación operativa. Algunos de estos algoritmos tienen nombres y orígenes bien curiosos (e.g. colonias de hormigas, algoritmos genéticos, búsqueda tabú, recocido simulado, etc.), y la mayoría de ellos usan estrategias de búsqueda que permiten hallar soluciones óptimas (o, como mínimo, de gran calidad) a complejos problemas de optimización. Hasta aquí, se podría pensar que estos algoritmos pertenecen sólo al ámbito teórico. Pero nada más lejos de la realidad: en casi todos los ámbitos de la vida nos encontramos con este tipo de problemas de optimización, que surgen normalmente para dar apoyo a la toma de decisiones en áreas tan diversas como los sistemas informáticos distribuidos (e.g., sobre qué nodos conviene desplegar servicios a fin de lograr una determinada disponibilidad al mínimo coste posible), los sistemas de transporte (e.g., qué plan de rutas proporciona una distribución más eficiente), los sistemas de producción (e.g., cómo programar la producción para lograr finalizarla en el menor tiempo posible), los sistemas financieros (e.g., qué productos debo incluir en un portafolio –y en qué cantidad– a fin de minimizar el riesgo a la vez que garantizo un retorno mínimo), los sistemas de telecomunicaciones (e.g., dónde debo ubicar las antenas a fin de lograr la calidad de servicio deseada al menor coste posible), y en casi cualquier otra área imaginable. De hecho, es fácil sostener la hipótesis de que nos encontramos en un mundo cada vez más complejo (por ser más global y...

Inteligencia Artificial: Colonias de hormigas

Este verano he tenido (y tengo) una plaga de hormigas en casa (no es broma). Es curioso el comportamiento comunitario de estos seres, que no dependen de un individuo en concreto, sino que basan su existencia en el funcionamiento coordinado de todo el equipo. Así, “acabar” con unos cuantos individuos no es, ni mucho menos, algo que afecte al día a día del grupo. Curiosamente, a la vez, he estado programando -en Prolog- (soy de los que piensan que “real men/women program Prolog”) una metaheurística basada en el comportamiento de las hormigas para la optimización de problemas combinatorios. Por si alguien quiere curiosear un poco, podéis encontrar, criticar, contribuir, hacer seguimiento, etc. de lo que llevo hasta ahora (ya funciona, parcialmente), que forma parte de un proyecto más ambicioso, aquí. El código se ejecuta sobre un lenguaje de programación lógica con restricciones llamado ECLiPSe y que podéis descargar aquí. Hace poco os hablé de la existencia de algoritmos bioinspirados, basados en el “conocimiento” observado en ciertos procesos naturales a la hora de resolver problemas concretos. En dicha entrada, uno de los que os comentaba era el basado en colonias de hormigas. Pero, ¿qué hacen las hormigas que nos pueda interesar a los informáticos/as? y ¿cómo lo trasladamos a un algoritmo? Pues bien, el interés que podemos tener en dichos seres viene de su manera de construir colaborativamente soluciones a partir de agentes muy simples. Así, la gracia de las hormigas no es que una sola sea capaz de encontrar el camino más corto entre dos puntos. La gracia, de hecho, es que es totalmente incapaz. Pero en cambio, un...

Inteligencia Artificial: Imitando a la naturaleza

En el área de computación uno de los temas más investigados es la resolución de problemas combinatorios. Pecando de simplista, podría decir que éstos son los problemas en que el número de posibles soluciones a explorar crece de manera no lineal respecto al tamaño de los datos de entrada. Esto hace que, a la que una cierta instancia del problema alcanza una cierta dimensión, sea imposible revisar todo el espacio de soluciones para decidir cuál es la mejor (dado un cierto criterio de búsqueda). Aunque lo dicho hasta ahora pueda sonar un poco abstracto, lo cierto es que estamos rodeados de problemas combinatorios: rutas óptimas de vehículos, minimización de impactos medioambientales, diseño de soluciones de todo tipo y tamaño (desde cómo posicionar los componentes en un circuito electrónico hasta cómo organizar sensores y actuadores en una ciudad para hacerla más smart). En todos estos casos, las soluciones proporcionadas se aplican directamente o bien ayudan en la toma de decisiones a los responsables. Este tipo de problemas se encara desde diferentes disciplinas (e.g. matemáticas, investigación operativa, etc.) pero en este post me centraré en presentar algunos enfoques propuestos por la Computación, y más concretamente, la Inteligencia Artificial, que me parecen especialmente interesantes por el paralelismo con el modo de buscar soluciones que tiene la propia naturaleza. Debido precisamente a esto, hablaremos de algoritmos basados/inspirados en la naturaleza (nature-based/inspired algorithms). La idea principal detrás de este grupo de algoritmos es: observar cómo funciona la naturaleza ante ciertos “problemas” y simular el proceso para aplicarlo al que queremos resolver nosotros. Seguidamente os introduciré algunas de estas “soluciones” y en futuros posts, iremos revisando cómo funciona cada uno, de manera más profunda: Colonias de hormigas (Ant colony...

El fractalista: Benoît Mandelbrot

La suerte (buena o mala) de tener un buen amigo que en estos tiempos que corren se arriesga a poner una librería, y que este amigo conozca las debilidades de uno, es que acabas acumulando demasiados libros pendientes de leer en la mesilla de noche. Entre mis debilidades (en todas sus acepciones) están la informática (por supuesto), la física (frontera, si es posible y si me es posible) y la historia de la ciencia y l@s que la dictan. Es así como cayó en mis manos la autobiografía del matemático Benoît Mandelbrot, conocido principalmente por acuñar (y trabajar en) el concepto de fractal. Como informático, de los recuerdos que me quedan de la carrera, los fractales me traen a la cabeza los gráficos por ordenador y la compresión de datos. Supongo que si fuese “teleco” me sonaría también a antenas. Y si fuese matemático, incluso los entendería. 😉 Antes de hablar del libro, eso sí, permítanme una pequeña (extremadamente divulgativa ausente de notación matemática) aproximación al concepto, para saber de qué estamos hablando. Los fractales son objetos geométricos que muestran la misma estructura a diferentes escalas de “zoom”. En la naturaleza, son frecuentes, y de hecho, antes que Mandelbrot los “nombrase” por primera vez, ya se habían identificado varios. Un ejemplo claro, para visualizar el concepto, es la imagen que acompaña a esta entrada: el brócoli. Dejando de lado otras características de este vegetal, si observamos su geometría, nos damos cuenta que al aproximarnos y aislar una de las partes, volvemos a tener una estructura similar a la original,… Una vez tenemos una ligera idea de qué es un...