Tema 1
Optimización II
Introducción a la
computación bioinspirada
Índice
Esquema 3
Ideas clave 4
© Universidad Internacional de La Rioja (UNIR)
1.1. Introducción y objetivos 4
1.2. Introducción a la computación bioinspirada 5
1.3. Problemas mono-objetivo vs multiobjetivo 11
1.4. Clases de algoritmos bioinspirados 13
1.5. Cuaderno de ejercicios 17
1.6. Referencias bibliográficas 21
© Universidad Internacional de La Rioja (UNIR)
Tema 1. Esquema
Optimización II
Esquema
3
Ideas clave
1.1. Introducción y objetivos
Muchos de los problemas a los que debemos hacer frente pueden ser formulados
matemáticamente en forma de problemas de optimización, en los cuales se busca
encontrar la mejor solución posible a este entre todas sus soluciones disponibles.
Inicialmente, dar respuesta a este tipo de problemas hacía uso de métodos analíticos
deterministas (es decir, métodos que no usan la probabilidad). Sin embargo, el
esfuerzo computacional requerido por estos métodos aumenta excesivamente
conforme aumenta la complejidad del problema, incrementándose también el
número de errores y, por tanto, estos se hacen inadecuados para la resolución de los
más complejos.
Este es justamente el motivo principal por el que se están buscando métodos
alternativos a los deterministas y que resulten más eficientes y ofrezcan buenas
soluciones. Los algoritmos bioinspirados son un tipo de algoritmos que se inspiran
en los procesos y patrones que podemos encontrar en la naturaleza, por ejemplo: al
estudiar cómo vuelan los pájaros, podemos desarrollar algoritmos que ayuden a los
aviones a volar de manera más eficiente y segura. Es como si la naturaleza nos
brindara ideas para mejorar la tecnología. Por ello, en este tema realizaremos una
breve introducción a los algoritmos de computación bioinspirada.
El objetivo principal de este tema es que se comprendan y afiancen los siguientes
puntos:
Definición y utilidad de los algoritmos de computación bioinspirada.
Características principales.
Problemas de optimización y su resolución mediante algoritmos de computación
bioinspirada.
Optimización II
4
Tema 1. Ideas clave
Clases de algoritmos bioinspirados más utilizados.
Diferencias entre problemas mono y multiobjetivo.
1.2. Introducción a la computación bioinspirada
Definición de algoritmos bioinspirados: los algoritmos de computación bioinspirada
son un conjunto de algoritmos cuyo objetivo es resolver una serie de problemas. Para
ello, se usan analogías que podemos encontrar en la naturaleza. De esta manera,
estos algoritmos simulan el funcionamiento de los sistemas naturales a los que imitan
y, gracias a ello, resuelven el problema de forma lo suficientemente eficaz.
Por lo general, este tipo de algoritmos se utilizan para resolver problemas tales como:
Búsqueda: suponga que dispone de un conjunto enorme de información y se
quiere encontrar, dentro de él, un subconjunto de datos que cumplan una serie
de requisitos previamente especificados. Dentro de esta categoría también
entrarían aquellos problemas en los que, a partir de una función matemática
específica, se desea buscar el valor máximo o mínimo que esa función puede
alcanzar.
Figura 1. Gráfica de 𝑓(𝑥, 𝑦) = sen 𝑥 ∙ cos 𝑦 en [0,2𝜋] × [0,2𝜋]. Fuente: elaboración propia.
Optimización II
5
Tema 1. Ideas clave
Aprendizaje: suponga que se tiene una serie de valores de entrada y otros de
salida, pero no se sabe cuál es la función que, a partir de esos valores de entrada,
genera los valores de salida. Podemos aplicar algoritmos de computación
bioinspirada para encontrar una función que aproxime la función original y nos
permita encontrar nuevos valores de salida a partir de nuevos valores de entrada.
Dentro del aprendizaje se encuentran también los problemas de clasificación en
los que, dada una serie de datos de entrada, debemos encontrar la manera de
clasificarlos en diferentes clases.
Figura 2. Clasificación de datos – Clustering. Fuente: Pham, 2016.
Comportamiento: también es posible aplicar este tipo de algoritmos para simular
una serie de comportamientos naturales mediante computador. De esta forma,
sería posible predecir reacciones dentro de ese medio a partir de ciertas variables
del entorno y, además, simular el comportamiento natural mediante computador.
Optimización II
6
Tema 1. Ideas clave
Figura 3. Robótica. Fuente: File:RunBot biped walking robot by Tao Geng.jpg, 2020.
Nota: es importante indicar que los algoritmos bioinspirados pueden resolver
cualquier problema siempre que se pueda expresar de tal forma que sea
posible aplicar este tipo de algoritmos.
El uso de los algoritmos bioinspirados está pensado para encontrar soluciones
aceptables a problemas que no tienen fácil solución por los métodos convencionales.
Siempre que un método heurístico tradicional sea capaz de dar solución a nuestro
problema, la mejor opción es utilizar dicho método. Sin embargo, hay problemas que,
por su gran envergadura, no son abarcables por algoritmos tradicionales. En este
caso, lo mejor es usar algoritmos de computación bioinspirada.
Por lo general, la computación bioinspirada permite realizar una búsqueda en el
posible espacio de soluciones de forma inteligente y obtener mejores soluciones que
mediante fuerza bruta.
La fuerza bruta consiste en probar todas las soluciones posibles para resolver
determinado problema. En la mayoría de los casos, esto no es posible debido a la alta
cantidad de posibles soluciones. Por ello, necesitamos llevar a cabo búsquedas en el
espacio de soluciones de forma más adecuada.
Optimización II
7
Tema 1. Ideas clave
Características
Por lo general, los algoritmos de computación bioinspirada tienen las siguientes
características:
No determinísticos: significa que, en distintas ejecuciones del algoritmo, los
resultados obtenidos son distintos. Esta es una característica deseable debido a
que nos puede interesar lanzar el mismo algoritmo varias veces para encontrar
diferentes resultados óptimos.
Figura 4. Representación genérica de algoritmos determinísticos. Fuente: elaboración propia.
Paralelos: la mayor parte de los algoritmos de computación bioinspirada están
pensados para su ejecución en clústeres y grandes máquinas con multitud de
procesadores. Tal y como hemos explicado, en la mayoría de los casos, vamos a
tener que tratar con una gran cantidad de datos. Por tanto, es deseable que los
algoritmos de computación bioinspirada puedan tratarse vía computación
paralela para poder tratar con la mayor cantidad de información posible al mismo
tiempo.
Figura 5. Esquema computación paralela. Fuente: elaboración propia.
Optimización II
8
Tema 1. Ideas clave
Adaptativos: los algoritmos de computación bioinspirada son capaces de
adaptarse al entorno y al problema en el que se están ejecutando. De esta forma,
estos algoritmos son capaces de modificar su conducta durante su ejecución con
el objetivo de adaptarse a ciertos cambios que se produzcan en torno al problema.
Figura 6. Esquema de algoritmos adaptativos. Fuente: elaboración propia.
Problemas de optimización: para resolver un problema específico con este tipo
de algoritmos, la mayor parte de las veces definiremos un problema de
optimización. Matemáticamente, podemos definir un problema de optimización
de la siguiente forma (Yang, Cui, Xiago, Gandomi y Karamanoglu, 2013):
minimizar 𝑓 (𝒙) , 𝑖 = 1,2, … , 𝑁 (1)
De forma que se cumplan las siguientes restricciones:
ℎ (𝒙) = 𝟎 , 𝑗 = 1,2, … , 𝐽
𝑔 (𝒙) ≤ 𝟎 , 𝑘 = 1, 2, 3, … , 𝐾
Donde tanto 𝑓 como ℎ y 𝑔 son funciones no lineales y el vector 𝒙 = (𝑥 , 𝑥 , … , 𝑥 )
puede ser continuo, discreto o de una dimensión determinada. Las funciones 𝑓
representan los objetivos y ℎ y 𝑔 son restricciones que deben darse para que los
valores de 𝒙 sean válidos.
Optimización II
9
Tema 1. Ideas clave
Ejemplo 1
Encontrar el mínimo valor para la función 𝑥 dentro del rango [−5,5]. Los
diferentes elementos que podemos identificar para formular nuestro problema
de optimización son los siguientes:
La función 𝑓 objetivo es 𝑥 . En concreto, se trata de encontrar la 𝑥 que
produce el menor valor posible.
Las restricciones son que 𝑥 debe ser un valor comprendido entre −5 y 5.
El vector 𝑥 contendría un único valor, el valor numérico que le pasamos a la
función objetivo para evaluarla.
Figura 7. Gráfica de 𝑓(𝑥) = 𝑥 en [−5,5]. Fuente: elaboración propia.
Podemos ver que la solución que nos da el mínimo valor es 𝑥 = 0, ya que el
valor obtenido al evaluar la función es 0, que es el mínimo posible dentro de
ese rango.
Optimización II
10
Tema 1. Ideas clave
1.3. Problemas mono-objetivo vs multiobjetivo
Cuando, en un problema de optimización, nos encontramos con que 𝑖 > 1 en (1),
significa que hay más de una función objetivo que debemos optimizar. En este
sentido, es posible diferenciarlos. En consecuencia:
Problemas mono-objetivo: en este tipo de problemas se optimiza una única
función objetivo. Por tanto, los algoritmos de computación evolutiva que se
encargan de resolver este tipo de problemas centran todos sus esfuerzos en
encontrar los valores que optimizan dicha función objetivo. El problema de
optimización mostrado en el «Ejemplo 1» es un problema mono-objetivo.
Problemas multiobjetivo: los algoritmos deben de optimizar varias funciones a la
vez. Los problemas multiobjetivo son muy complejos ya que, por lo general, al
conseguir mejorar el valor encontrado en una cierta función objetivo, podemos
hacer que el de otra disminuya.
Por tanto, es necesario encontrar cierto consenso entre las funciones objetivo a
optimizar. Por lo general, no nos interesará que el valor de una función objetivo
mejore a costa de empeorar mucho otra, pero sí que nos interesará ganar mucho en
una función a costa de empeorar solo un poco el resultado en otra.
Si se conoce la importancia de cada una de las funciones multiobjetivo y son
independientes entre sí, el problema pasa a ser un problema mono-objetivo. Esto se
debe a que podríamos simplemente agregar los valores conforme a su importancia,
convirtiendo todas las funciones objetivo en una única función objetivo, bajo alguna
regla establecida:
𝐹 = 𝑓 ∗ 𝑓 ∗ 𝑓 ∗ ⋯∗ 𝑓
Optimización II
11
Tema 1. Ideas clave
Y llevar a cabo la operación de agregación de las funciones cada vez que evaluemos
las funciones objetivo. Cuando las funciones están relacionadas entre sí, no podemos
realizar este proceso, puesto que podríamos estar despreciando el valor de alguna
de ellas a cambio de mejorar el valor del resto.
Enunciación del problema
Un problema de optimización requiere de la definición de los siguientes elementos
para poder ser tratado de manera correcta por cualquier algoritmo bioinspirado:
Representación del problema: debemos proporcionar una representación del
problema que queremos resolver, adecuada al algoritmo que queremos usar. Por
lo general, cada algoritmo requiere un tipo de representación específica. Por lo
que lo más lógico es utilizar el algoritmo de computación bioinspirada que mejor
se adapte a los tipos de datos con los que tenemos que tratar. Por ejemplo, un
problema de optimización de grafos es más sencillo de resolver utilizando
algoritmos de colonias de hormigas que utilizando métodos de computación
evolutiva.
Función objetivo: la función objetivo nos ayuda a determinar lo buena que es una
solución obtenida. Dependiendo del problema, la función objetivo puede definirse
de diferentes maneras. Por ejemplo, si estamos tratando de encontrar el camino
mínimo dentro de un grafo, la función objetivo puede ser el camino mínimo ya
conocido dentro de ese grafo o, en caso de no conocerse, la función objetivo se
define como el mínimo camino posible. En el caso de encontrar el valor mínimo o
máximo de una función, la función objetivo sería el valor mínimo o máximo de esa
función (si es conocido) o, paralelamente al ejemplo anterior, se establece como
función objetivo el mínimo o máximo valor posible que se pueda obtener dentro
de los posibles valores de esa función.
Optimización II
12
Tema 1. Ideas clave
Representación de los datos de entrada: la representación de los datos de
entrada que utilizará el algoritmo de computación bioinspirada depende
directamente de la representación del problema elegido y el algoritmo
seleccionado.
En el siguiente enlace podrás encontrar una introducción a los algoritmos
bioinspirados.
1.4. Clases de algoritmos bioinspirados
Dentro de los algoritmos de computación evolutiva hay muchos tipos de algoritmos,
cada uno de los cuales emula distintos eventos que ocurren en la naturaleza. Entre
los más utilizados encontramos los siguientes:
Redes neuronales: imitan el funcionamiento del cerebro humano. Contienen
varios nodos, llamados neuronas, ordenados por capas que modifican los datos
de entrada para generar unos de salida. Se usan principalmente para aprendizaje
y clasificación.
Optimización II
13
Tema 1. Ideas clave
Figura 8. Esquema de una red neuronal. Fuente: Gidahatari, 2014.
Es importante destacar que, aunque estos algoritmos pueden resultar de vital
importancia en estos días, no serán abordados en este curso. La idea era mostrar su
existencia y pertinencia sin ahondar mucho en su accionar. Nuestros intereses se
dirigirán a otros espacios.
Algoritmos evolutivos: estos algoritmos están basados en la reproducción animal
y tienen como base el proceso genético de reproducción de dos individuos y las
operaciones que se llevan a cabo a nivel de genes (cruce y mutación). Por lo
general, tienen en cuenta a una población de miembros que va reproduciéndose
entre sí con el objetivo de generar nuevos miembros que son mejores que los
padres. Se establece una función objetivo (fitness) que evalúa a cada miembro
para determinar su valía dentro del grupo.
Optimización II
14
Tema 1. Ideas clave
Figura 9. Replicación del ADN con doble cadena. Fuente: File:DNA replication pt.svg, 2023.
Algoritmos de adaptación social: son aquellos que imitan el comportamiento de
sociedades de animales. Nos centraremos en estudiar las dos técnicas más
conocidas:
• Algoritmos de enjambre: estos algoritmos imitan el comportamiento social
que se observa en bandadas de peces o aves cuando vuelan hacia un lugar
específico. Por lo general, el objetivo de estos algoritmos es rastrear un espacio
determinado en busca de la solución óptima concentrando esfuerzos en
aquellas zonas más prometedoras.
• Existen otro tipo de algoritmos que podrían entrar en estudios como este, tal
es el caso de los algoritmos inmunológicos. Estos están basados en el
funcionamiento del sistema inmunológico humano. Consigue diferenciar los
elementos que son propios al problema de los que no. El algoritmo más famoso
dentro de esta categoría es el algoritmo de selección negativa de Forrest.
• Algoritmos basados en colonias de hormigas: imitan el proceso por el cual las
hormigas buscan comida y la traen al hormiguero. Está demostrado que las
hormigas son capaces de trazar caminos óptimos entre su hormiguero y la
comida con el objetivo de, entre varias de ellas, despedazarla en pequeños
trocitos y llevarla al hormiguero.
Optimización II
15
Tema 1. Ideas clave
Figura 10. Etapas del algoritmo de colonia de hormigas. Fuente: Archivo:Aco branches.svg, 2006.
Dentro de los comportamientos animales, existen múltiples algoritmos posibles de
considerar, por ejemplo, algoritmos basados en lógica difusa. Estos algoritmos
permiten introducir la posibilidad de verdades parciales para, por ejemplo, tratar de
emular el sistema de comunicación lingüista humano.
Observación: resulta importante destacar que, dependiendo del interés de cada
estudiante, siempre es posible encontrar información sobre procesos distintos para
afrontar una diversidad de problemas cotidianos. En este sentido, para más
información, se puede siempre indagar dentro de los distintos medios en redes para
acceder a información privilegiada, desde la posibilidad de indagar en internet, bien
sea con vídeos o documentos, o bien pensar en iniciar un proceso investigativo con
artículos académicos que permitan generar un ambiente de interés e investigación.
Optimización II
16
Tema 1. Ideas clave
1.5. Cuaderno de ejercicios
Ejercicio 1
En pocas palabras, trataremos de explicar lo que es un algoritmo no determinístico,
y se tratará de explicar en qué forma un sistema puede ser no determinístico
utilizando ejemplos.
Solución
La característica principal de un algoritmo no determinístico es justamente el hecho
de que, en cada ejecución del algoritmo, no necesariamente se reproduce el mismo
resultado. Es decir, la variable de salida de un algoritmo no determinista es
esencialmente una variable estocástica. Esta cualidad es, de hecho, una copia fiel de
la característica estocástica intrínseca en la naturaleza.
Dos individuos de una especie no son jamás idénticos. Incluso un experimento tan
sencillo como dejar caer una piedra para observar su trayectoria, por mínimas que
sean, posee variaciones no controlables por el observador, es decir, que no siempre
el resultado es el mismo.
Ejercicio 2
Una modelo debe probarse prendas en diferentes combinaciones. Tiene disponibles
diez tipos de sombreros, diecinueve tipos de blusas, veinticinco tipos de pantalones
o faldas, once tipos de zapatos, nueve tipos de abrigos y doce tipos de bolsos. Para
probar y evaluar cada combinación tarda cinco minutos en promedio, ¿cuánto
tardaría en probarse el total de combinaciones posibles sin atender a su gusto o algún
tipo de selección? ¿Qué tiene que ver esto con la fuerza bruta?
Optimización II
17
Tema 1. Ideas clave
Solución
El número total de combinaciones es simplemente el producto de posibilidades de
cada prenda, o sea, 𝑁 = 10 × 19 × 25 × 11 × 9 × 12 ≈ 5.6 × 10 . Por lo que el tiempo
empleado sería, 𝑁 × (3 min) ≈ 17 × 10 min ≈ 32 años. Está por demás decir que es
una cosa imposible de realizar, por lo que sabemos que sería una locura que alguien
intentara probarse todos los posibles atuendos con las prendas que puede encontrar
en una tienda.
La razón por la que una persona no tarda eso es simplemente porque cuenta con un
gusto determinado y posee herramientas de selección (que técnicamente son
llamadas métodos heurísticos) que le permiten evaluar solo un subconjunto de
prendas determinadas. ¿Será la combinación que escoja la mejor para una reunión
formal? No se puede saber, pero seguro le funcionará en cierta medida y no
necesariamente será lo que pudo haber elegido un día antes. Tratar de probarse
todas las combinaciones para encontrar la mejor sería lo que significa aplicar fuerza
bruta.
Ejercicio 3
Tratando de llevar a un nivel más técnico la situación del ejercicio anterior, mencione
métodos que crea que la modelo emplea para encontrar lo que considera el mejor
atuendo, ¿podría resultar de ello técnicas formales de optimización?
Solución
Algunos de los métodos que podemos mencionar son:
Utilización de información previa de anteriores búsquedas.
Selección ordenada o prioritaria, ya sea por color, por ofertas, etc.
Exploración de la tienda con diferentes refinamientos, es decir, regresando a
aquellos lugares que fueron más llamativos, etc.
Optimización II
18
Tema 1. Ideas clave
El proceder de la modelo puede capturarse en una metodología ya que cada método
mencionado en realidad sí puede ser implementado como un paso algorítmico. De
hecho, podría encontrarse una variedad de metodologías, pues se puede aprender
de diversos compradores.
Ejercicio 4
Plantee, en forma de pseudocódigo, la metodología que le sirve para estudiar un
tema con el fin de obtener la mejor nota posible.
Solución
Una posibilidad para este pseudocódigo podría ser la siguiente:
Inicialización
Definición del tema
Lista de fuentes disponibles
Mientras (esquema conceptual asimilado)
Análisis exploratorio destacando conceptos e ideas
A través de los índices
A través de las introducciones
Desarrollo de mapa conceptual y de ruta
Fin
Ordenamiento de subtemas por prioridad
Mientras (marca de test > umbral)
Exploración de cada tema
Fin
Autoevaluación
Optimización II
19
Tema 1. Ideas clave
Ejercicio 5
Un nuevo repartidor debe hacer compras dentro de un supermercado, dado el
tamaño de la tienda y los pocos minutos que tiene para cumplir con los pedidos, tiene
que hacerlo de la manera más eficiente posible. Sus clientes asiduos piden lo mismo
cada día de la semana, por lo que ha llegado a definir un trayecto óptimo con la
experiencia. Hipotetice sobre las razones por las que se desarrolló esta trayectoria
óptima. ¿Tiene esto que ver con los algoritmos bioinspirados?
Solución
Por supuesto, al cabo de intentar diferentes trayectorias, pudo identificar aquellas
que le resultaba recorrer más ágilmente gracias a la memoria relacionada a la
identificación de artículos por sectores y los tiempos de recorrido de pasillos. Por otro
lado, se dio cuenta del tipo de eventualidades con las que podía encontrarse y
desarrolló estrategias de respuesta, lo que le permitió prevenir dilaciones. Sabía, por
ejemplo, a qué hora y en qué día había más gente en el supermercado, si la mercancía
que buscaba para cierta hora podía ya haberse agotado e incluso en qué días se
abastecía la tienda con nuevos productos. Pudo determinar los tiempos promedio de
atención en el área de cárnicos o en los cajeros de cobro. Ajustó su paso para no ser
tan rápido que pudiera olvidar algo o tan lento que perdiera tiempo.
Esto tiene que ver todo con los algoritmos bioinspirados, ya que la naturaleza halla
constantemente formas de darle cause a la subsistencia. Por supuesto, el humano es
un ejemplo por excelencia del desarrollo de estrategias de supervivencia. Ante una
determinada decisión, este considerará sus recursos, desde los más primitivos, hasta
los más avanzados tecnológicamente. Sin embargo, a pesar de todo, no se puede
garantizar que los resultados sean los mismos en cada ocasión o que siempre sean
los mejores posibles.
Optimización II
20
Tema 1. Ideas clave
1.6. Referencias bibliográficas
Archivo:Aco branches.svg. (2006, mayo 27). En Wikipedia.
https://es.wikipedia.org/wiki/Archivo:Aco_branches.svg
Facultad de ingeniería - Universidad Nacional de Colombia. (2014, octubre 10).
Optimización Bioinspirada – Ingenios [Vídeo]. YouTube.
https://www.youtube.com/watch?v=9SV_u9R13zs
File:RunBot biped walking robot by Tao Geng.jpg. (2020, octubre 15). En Wikipedia.
https://commons.wikimedia.org/wiki/File:RunBot_biped_walking_robot_by_Tao_G
eng.jpg
Gidahatari. (2014, enero 2). Redes Neurales Artificiales: ¿cómo cuantificar los
impactos ambientales sobre el recurso hídrico? Iagua.
https://www.iagua.es/blogs/gidahatari/redes-neurales-artificiales-%C2%BFcomo-
cuantificar-los-impactos-ambientales-sobre-el-recurso-hidrico
File:DNA replication pt.svg. (2023, agosto 28). En Wikipedia.
https://commons.wikimedia.org/wiki/File:DNA_replication_pt.svg
Pham, T. T. (2016, octubre 18). Clustering key terms, explained. KD nuggets.
https://www.kdnuggets.com/2016/10/clustering-key-terms-explained.html
Yang, X. S., Cui, Z., Xiago, R., Gandomi, A. H. y Karamanoglu, M. (eds.). (2013). Swarm
intellicence and bio-inspired computation: theory and applications. Elsevier.
Optimización II
21
Tema 1. Ideas clave
