SISTEMAS COOPERATIVOS NATURALES

Este blog corresponde a la actividad de la primera unidad en la asignatura Inteligencia Computacional del tercer semestre de la Maestría en Telecomunicaciones Móviles.

Para el desarrollo de este blog se han tomado como referencia varios artículos, pero en especial se apoya en el artículo ‘’Inteligencia de enjambres: sociedades para la solución de problemas” el cual me pareció muy interesante para entender las características y clasificaciones de las distintas técnicas o algoritmos asociados a los sistemas cooperativos naturales.

INTRODUCCIÓN

Uno de los principales objetivos de la Inteligencia Artificial (IA) consiste en la búsqueda de soluciones optimas a problemas de alta complejidad, tanto para espacios continuos como para espacios discretos. Se dice que un algoritmo de optimización es un método numérico que encuentra un valor en θi ∈ Rn, donde Rⁿ es un espacio n–dimensional de búsqueda, que minimiza o maximiza una función J(θ), por medio de la selección sistemática de valores de la variable θi posiblemente con algunas restricciones. La variable θi puede ser un escalar o un vector de valores discretos o continuos llamados funciones factibles, mientras que J(θ) es llamada función objetivo. Una solución factible que minimiza o maximiza la función objetivo es llamada una solución óptima. Un tipo de problemas de optimización son aquellos que requieren combinaciones de valores, y se le denomina de optimización combinatoria.

De acuerdo con Hertz y Kobler, las técnicas que se utilizan para la resolución de problemas complejos de optimización combinatoria han presentado una evolución progresiva desde métodos constructivos, pasando por métodos de búsqueda local y finalmente llegando a los algoritmos basados en poblaciones. Los métodos basados en poblaciones tienen la gran ventaja de ser capaces de combinar buenas soluciones en orden de obtener unas mejores, lo anterior puesto que se considera que las buenas soluciones comparten componentes con las soluciones óptimas.

A estos métodos se les conoce como algoritmos de computación evolutiva (Evolutionary Computation - EC). Estos algoritmos de EC abarcan un conjunto de técnicas que realizan varias iteraciones para manejar una población de individuos que se modifican o evolucionan de acuerdo a una serie de reglas que han sido definidas claramente. Con cada iteración se dan periodos de autoadaptación y generando cambios en los individuos de la población, adicional se generan también periodos de cooperación con el propósito de realizar intercambio de información entre los individuos.

CARACTERISTICAS

Las siguientes características deberán ser tenidas en cuenta al momento de considerar un nuevo algoritmo de EC que busque dar solución al un problema particular de optimización.

• La existencia de individuos que pueden presentar soluciones de un problema, las soluciones pueden ser factibles o no, parciales o completas, individuales o grupales.
• Un proceso de evolución el cual permite definir los cambios en la población en periodos de cada generación o de manera continua.
• Una definición de vecindad mediante la cual se puede conocer el modo en que los individuos intercambian información. Esta información se puede tratar como estructurada si solo un grupo de la población puede conocer la información de un miembro, o poder ser información a la que todos los miembros tienen acceso.
• Un mecanismo que permita identificar las fuentes de información de un individuo. Lo anterior puesto que una vecindad puede entregar una gran cantidad de información y es conveniente determinar cuál es más conveniente utilizar.
• Una medida de la factibilidad de la solución obtenida con la cual se pueda determinar si la solución es buena, optima o inadecuada.
• Un mecanismo de intensificación. El cual se refiere a uso de métodos con los cuales se puedan generar mejoras significativas durante la fase de autoadaptación. Este mecanismo se enfoca en realizar mejoras en un individuo sin tener en cuenta la información suministrada por otros individuos, permitiendo de esta manera la intensificación de la búsqueda sobre algunas regiones del espacio.
• Un mecanismo de diversificación, con el cual se evita una convergencia hacia puntos óptimos locales. El procedimiento modifica a cada individuo de manera independiente, pero al contrario del mecanismo de intensificación, se obtienen resultados inesperados sobre cada individuo.

      Es así como la EC representa un amplio grupo de técnicas, y que básicamente se dividen en dos grandes grupos diferenciados principalmente en la aplicación de los anteriores conceptos. El primer grupo lo conforman los algoritmos evolutivos (Evolutionary Algorithms – EA) y el segundo grupo es la inteligencia de enjambres (Swarms Intelligence – SI). La siguiente figura muestra como seria la taxonomía de la computación evolutiva.

Algoritmos evolutivos

Los algoritmos evolutivos fueron introducidos por John Holland en el ano 1960 mediante la incorporación de métodos de selección natural y supervivencia a la resolución de problemas no lineales donde se involucran muchas variables. Como resultado se da una optimización estocástica.

Corresponden a un grupo de técnicas estocásticas que manejan los conceptos de la evolución biológica. Estos algoritmos evolutivos operan sobre una población de soluciones potenciales aplicando los conceptos de diversidad de individuo y el de la supervivencia del más fuerte con el objetivo de producir mejores aproximaciones a una solución. En cada generación se crea un nuevo grupo de aproximaciones por el proceso de selección de individuos basado en el nivel de desempeño dentro del dominio del problema, y se cruzan entre sí mediante el uso de operadores que imitan los conceptos genéticos.       Gracias a este proceso se llega a la evolución de las poblaciones de individuos que están mejor adaptados a su ambiente. Dentro de sus principales técnicas se tienen los algoritmos genéticos (Genetic Algorithms – GA), las estrategias evolutivas (Evolutions Strategie - ES), la programación evolutiva (Evolutionary Programming – EP) y la programación genética (Genetic Programming – GP).

En cuanto a la estructura de un Algoritmo Evolutivo se puede decir que esta compuesto por una función con la cual se puede medir la amplitud de las soluciones candidatas que permitirían resolver el problema, Esta amplitud es utilizada por los algoritmos evolutivos como mecanismos de selección que permiten crear nueva soluciones al un problema en particular.

Inteligencia de enjambres

dentro de este grupo se encuentran técnicas las cuales se basan en el estudio del comportamiento colectivo que se da en sistemas auto organizados y descentralizados (distribuidos). Normalmente estos sistemas están conformados por una población de agentes computacionales simples pero capaces de percibir y modificar su ambiente de manera local. Gracias a esta capacidad se hace posible la comunicación entre los individuos, que detectan un cambio en el ambiente generado por el comportamiento de sus semejantes. En estas técnicas normalmente no se identifica una estructura centralizada de control que dictamine como los agentes deben comportarse, solo con las interacciones locales entre los agentes es que generalmente se lleva a una emergencia global. Para este grupo se debe tener en cuenta otra característica adicional relacionada con la existencia de un modelo explicito del ambiente. Dentro de esta rama se encuentran las siguientes técnicas: la optimización por enjambre de partículas (Particle Swarm Optimization - PSO), la optimización por colonia de hormigas (Ant Colony Optimization – ACO), adicional dentro de esta rama se pueden ubicar otros algoritmos como los son: la optimización por enjambre de bacterias (Bacteria Swarm Foraging Optimization – BSFO), la búsqueda por difusión estocástica Stochastic Diffusion Search – SDS) y el algoritmo de colmena de abejas artificiales (Artificial Bee Hive Algorithm – ABHA).

Referencias:

http://www.scielo.org.co/pdf/iei/v28n2/v28n2a15.pdf

https://revistas.utp.ac.pa/index.php/memoutp/article/view/1498/html

https://www.yumpu.com/es/document/read/42075870/introduccian-a-los-algoritmos-evolutivos-icm

https://es.dreamstime.com/ejemplo-del-logotipo-texto-de-la-palabra-inteligencia-enjambre-image105202179