IA_L7

Inteligencia Artificial

Heurísticas y cómputo evolutivo

INICIAR

Identifica los métodos de optimización y búsqueda de soluciones para hacer frente a problemas complejos a partir de la descripción de sus características.

En esta Lección analizaremos los siguientes temas:

Búsquedas heurísticas.

Satisfacción de restricciones.

Cómputo evolutivo.

Un poco de historia

El cómputo evolutivo tiene su origen en las teorías del origen de las especies de Darwin. Donde se asegura que, la evolución se da por selección natural y la herencia.

Además, afirma que las especies mejor adaptadas a su ambiente y a los cambios que se dan en él son los que tienen mayores probabilidades de sobrevivir.

El científico Alemán August Weismann propuso la Teoría del seleccionismo y el monje austriaco Johann Gregor Mendel la teorías sobre la genética, ambos conforman con sus aportes el Neo-Darwinismo.

Ésta establece que, la evolución de la vida en la tierra se entiende por medio de procesos que influyen en las especies: La reproducción, la mutación, la competencia y la selección (Santana y Coello, 2006).

Cómputo Evolutivo

En los 60’s y 70’s se propusieron tres enfoques dentro del Cómputo evolutivo.

Los tres iniciativas eran muy parecidas entre ellas pero cambian en particularidades que las convirtieron en la base del cómputo evolutivo (Santana y Coello, 2006).

Pulsa en cada recuadro para conocer la información

Programación evolutiva

Estrategias evolutivas

Algoritmos genéticos

Búsquedas

Las búsquedas en IA son: una de las metodologías mas usadas para resolución de problemáticas de planificación, de búsqueda de caminos o soluciones para aplicaciones de navegación o para encontrar un estado dentro de un conjunto de estados.

Los primeros algoritmos que bajo esta metodología, se diseñaron, sirvieron para poder estimar la distancia y el mejor camino entre dos puntos (más corto).

Podemos contemplar dos casos:

Búsquedas informadas​

Cuando contamos con información del medio​

Búsquedas no informadas​

Cuando no se cuenta con la información completa del medio​

Para poder determinar las soluciones de éstos casos, debemos contar con información del conjunto de estados del entorno. Se pueden representar con una estructura de árbol o grafo. Cada nodo del grafo representa un estado.

Los métodos para realizar búsquedas recorren el grafo con toma de decisiones en casi su totalidad dependiendo del diseño del algoritmo. Los primeros algoritmos realizaban el recorrido del árbol haciendo que las búsquedas no fueran óptimas.

Árbol o Grafo

Estado inicial (punto de partida)

Acción, es la decisión de realizar el recorrido de una rama se debe de asignar un costo por recorrido: g(n)

Nodo padre es: un estado que tiene estados subsecuentes y tiene un valor

Nodo hijo que a su vez, puede ser padre de otros nodos

Profundidad es el número de pasos del camino desde el estado inicial

Grafo

Nodo hoja es el nodo que ya no tiene nodos hijo

Expandir el estado es: aplicar una función que indique que camino se debe seguir hacia un estado sucesor para generar un nuevo conjunto de estados en el siguiente nivel. Así se descubrirá si al avanzar al siguiente nodo se llega a una solución o no. Y así sucesivamente avanzando.

Las complejidad de las búsquedas en IA radica en que se pueden quedar en búsquedas de ciclo infinito o en costos muy altos de procesamiento para encontrar la solución.

Hablamos del costo de procesamiento a que la búsqueda no sea óptima por que puede llegar a una solución que no necesariamente sea la mejor o no llegar nunca a la solución, o incluso tardar demasiado tiempo en lograrla.

Otro problema a considerar son las búsquedas no informadas, éstas no cuentan con toda la información necesaria para poder determinar un resultado puesto que no existe más información que la dada por el problema mismo y los estados inicial y final.

A continuación, mencionaremos 6 métodos para realizar búsquedas no informadas o a ciegas.

Pulsa sobre cada botón para conocer la información.

Primero en profundidad con profundidad iterativa

Primero en profundidad

Primero en anchura

Bidireccional

Profundidad limitada

Costo uniforme

¿Qué es heurística?

heurístico, caDel gr. εὑρίσκειν heurískein 'hallar', 'inventar' y ‒́tico.1. adj. Perteneciente o relativo a la heurística.2. f. Técnica de la indagación y del descubrimiento.3. f. Búsqueda o investigación de documentos o fuentes históricas.4. f. En algunas ciencias, manera de buscar la solución de un problema mediante métodos no rigurosos, como por tanteo, reglas empíricas, etc. (RAE, 2020).

¿Qué es la heurística desde el punto de vista computacional de la IA?

Pulsa en el botón para conocer la información.

Búsquedas heurísticas

Una vez revisadas las búsquedas en la IA, entraremos a ver las búsqueda heurística. Algunos autores le llaman búsqueda informada, para que se le pueda llamar así, la búsqueda usa conocimiento más amplio que el dado en la explicación del problema planteado. Estos métodos encuentran mejor información de manera más competente que los algoritmos vistos anteriormente.

Las búsquedas (voraz)** primero el mejor son: un tipo de algoritmo (Russell y Norving, 2004 y 2008, p. 108) que selecciona el nodo evaluando una prioridad haciendo uso de una función de evaluación. La función selecciona lo que al parecer es el mejor y si es correcta dicha evaluación, la solución del camino se optimiza, pero no siempre puede suceder esto, ya que selecciona el que "parece" mejor.

Los métodos de búsqueda heurística están orientados a reducir la cantidad de búsquedas requeridas para encontrar una solución (Russell y Norving, 2004 y 2008).

Las búsquedas antes de las heurísticas se llegaron para optimizar los resultados de las búsquedas.

Los algoritmos que funcionan de esta manera son los que cuentan con la función heurística conocida como h(n) que es el costo estimado del camino menos costoso desde un nodo n a un nodo objetivo. Así, las funciones heurísticas se han vuelto en una manera general de comunicar la información agregada al algoritmo de búsqueda.

**En el libro de Inteligencia artificial un enfoque moderno, de Russell y Norving del 2008, se introduce la siguiente nota en el nombre de está búsqueda heurística: Se sigue el término de Pearl de 1984 (Russell y Norving, 2008, p. 108).

Métodos de búsquedas heurísticas

Pulsa en cada recuadro para conocer la información

Búsqueda (voraz) primero el mejor

Búsqueda A* de profundidad iterativa (A*PI)

Búsqueda Recursiva del Primero Mejor (BRPM)

Búsqueda A*

Así como los algoritmos mencionados que realizan la búsquedas heurísticas, existen algunos otros, derivados de los anteriores que optimizan aún más las rutas de búsqueda como los costos de procesamiento.

Cuando en las búsquedas, aparecen problemas de exploración el agente no tiene forma de conocer la información de la situación de los estados y los hechos del mundo. Para ambientes factiblemente explorables, los agentes que realizan exploración en línea pueden crear mapas para localizar objetivos, si es que existen.

En las heurísticas al enfrentar problemas que afecten en árboles de búsqueda, la visión heurística trata de minimizar el tamaño del árbol eliminando nodos poco esperanzadores. No significa que se elija habitualmente la vía correcta, por lo tanto aunque la óptica no sea óptima, es eficiente. (Russell y Norving, 2004 y 2008).

Satisfacción de restricciones

El modelo que ha tenido relativo éxito para el cómputo evolutivo desde hace 50 años es el conocido como Satisfacción de restricciones, el cual consiste en el planteamiento de variables relacionadas con conjuntos finitos de valores que cubren grupos de restricciones.

Ya que el conjunto se define como finito, el problema se resuelve con un algoritmo de búsqueda profunda, donde un árbol de nodos es recorrido, confirmando que las restricciones definidas sean cumplidas por el algoritmo en cada nodo analizado.

Los algoritmos de este tipo se les nombra de BackTracking (López de Mántaras y Meseguer, 2017).

Las predicciones que inicialmente se realizaron en los años 60’s sobre el avance de la IA fueron muy optimistas.

Sobre todo cuando se empezaron a lograr soluciones para problemas no complejos, pero al introducir la IA a problemas complejos o de dificultad mayor, se dieron fracasos que crearon la necesidad de investigar más sobre algoritmos que lograran soluciones a los problemas complejos. Por eso se crea el análisis de complejidad que estudia los problemas.

Para entender un poco los problemas que se enfrentaron se realizó la siguiente clasificación (Russell y Norving, 2004 y 2008):

Problemas intratables

Problemas Clase NP

Pulsa en cada recuadro para conocer la información

Problemas Clase Completos NP

Problemas Clase P

Los problemas que pueden ser resueltos con la satisfacción de restricciones en la Inteligencia artificial, pertenecen a muchas disciplinas y áreas de conocimiento. Entre estas se pueden contar con: de investigación operativa, de lenguaje natural de reconocimiento, Bases de datos, entre otras.

Para todos estos casos, se debe considerar usar técnicas de simplificación para encontrar soluciones eficaces.

Entre las técnicas, están los algoritmos de propagación de restricciones, para lograr nodo-consistencia, arco consistencia y k-consistencia. También tenemos algoritmos de búsqueda como Generate and Test: GT, Backtracking BT, Backjumping BJ, Conflict-directed backjumpinng CBJ, y algoritmos híbridos como Forward Checking FC, y Maintaining arc consistency. Los algoritmos incluyen la propagación de restricciones en los de búsqueda, y son de los más usados en la búsqueda de soluciones a problemas difíciles (Manyá y Gomes, 2003).

Los problemas de satisfacción de restricciones se definen por tres conjuntos de elementos: X, D, R, donde:X es el conjunto finito de variables {X1, X2, .. Xn} D es el conjunto finito de dominios {D1, D2, .. Dn}R es el conjunto finito de restricciones {R1, R2, .. Rn}

Ejemplo

Ejemplo tomado del artículo de Manyá, y Gomes, (2003).

Ejemplo tomado del artículo de Manyá, y Gomes, (2003).

Ejemplo

Ejemplo tomado del artículo de Manyá, y Gomes, (2003).

*En el libro de Inteligencia artificial un enfoque moderno, de Russell y Norving del 2008, se introduce la siguiente nota en el nombre de está búsqueda heurística: Se sigue el término de Pearl de 1984 (Russell y Norving, 2008, p. 108).

Ejemplo tomado del artículo de Manyá, y Gomes, (2003).

Ejemplo

Ejemplo tomado del artículo de Manyá, y Gomes, (2003).

*En el libro de Inteligencia artificial un enfoque moderno, de Russell y Norving del 2008, se introduce la siguiente nota en el nombre de está búsqueda heurística: Se sigue el término de Pearl de 1984 (Russell y Norving, 2008, p. 108).

Cómputo evolutivo

La computación evolutiva incluye varias técnicas que, como ya se comentó, han sido inspiradas en la evolución biológica de la teoría Neo-Darwiniana de la evolución natural de las especies. Para lograr el proceso evolutivo en las computadoras, es necesario contar con los siguientes puntos:

Programar estructuras a replicar

Realizar operaciones que influyan o afecten a los individuos.

Contar con función de aptitud.

Un proceso o método de selección.

Es complicado encontrar la frontera que divide los tipos de algoritmos hasta ahorita diseñados, pero se pueden contar 3 paradigmas principales:

Programación evolutiva

Estrategias evolutivas.

Algoritmos genéticos.

Los tres tuvieron orígenes diferentes y objetivos diferentes (Coello, 2020).

La programación evolutiva señala la relación de conducta padres/hijos en lugar de emular operadores específicos genéticos. Los elementos base que necesita la programación evolutiva son:

Generación aleatoria de poblaciones principales.

Aplicación de una mutación.

Cálculo de la aptitud de los hijos resultantes aplicando un proceso de selección para elegir las soluciones que permanecerán.

No requiere de un operador de recombinación.

Las selecciones son probabilísticas.

Este paradigma tiene aplicación en: predicciones, generalizaciones, juegos, controles automáticos, planeación de rutas, entrenamiento de redes neuronales, reconocimiento de patrones (Coello 2020).

*En el libro de Inteligencia artificial un enfoque moderno, de Russell y Norving del 2008, se introduce la siguiente nota en el nombre de está búsqueda heurística: Se sigue el término de Pearl de 1984 (Russell y Norving, 2008, p. 108).

Estrategias evolutivas

Fueron desarrolladas en Alemania para solucionar problemas hidrodinámicos.

Las primeras versiones usaban un solo padre y se generaba un solo hijo, si el hijo era mejor que el padre, se mantenía, de lo contrario era eliminado, así los individuos malos obtenían probabilidad de cero para ser seleccionados.

El algoritmo fue mejorado agregando la Regla del éxito 1/5, donde se ajusta la desviación estándar determinsticamente, para que el procedimiento se dirigiera hacia lo óptimo.

Así mismo si el resultado generaba un hijo con una evaluación superior al padre, el hijo reemplaza al padre.

Aplicaciones de las estrategias evolutivas son las siguientes: Problemas de ruteo y redes, bioquímica, óptica, diseño en ingeniería y magnetismo (Coello 2020).

Las estrategias evolutivas se entienden como la abstracción de la evolución al nivel del individuo, por lo que la recombinación es posible.

En los algoritmos genéticos, el tratamiento de los datos se realiza de dos formas:

Pulsa sobre cada botón para conocer la información.

Por mutación de datos

Por recombinación de datos

¿Que son los algoritmos evolutivos?

Los algoritmos evolutivos (AEs) fundamentan su funcionamiento empleando números aleatorios y por consiguiente, no siempre crean un el mismo resultado cuando se ejecutan.

Desde su invención, se han creado al menos dos tipos de AEs basados en el modelo de problemas que buscan solucionar:

Diseñados para resolver problemas de optimización (no lineales y combinatorias).

Diseñados para resolver problemas de aprendizaje máquina (sobre todo de clasificación).

No obstante, la exploración en computación evolutiva va más allá del desarrollo de nuevos algoritmos. Va al diseño de nuevos operadores, métodos de selección y representación. Además del modelado matemático de los AEs, analiza el origen de dificultad en el campo de búsqueda y su correlación entre operadores de un AE y la cruza técnicas de los AEs con otro tipo de técnicas (Coello et al., 2017).

En resumen:

El cómputo evolutivo en la Inteligencia artificial se encarga de analizar y proponer técnicas de solución de problemas por medio de algoritmos heurísticos. Como ya se mencionó, estos algoritmos no garantizan encontrar una solución concluyente , pero se aproximan bastante a las soluciones. Sobre todo por que pueden llegar a soluciones sin contar con mucha información.

El cómputo evolutivo se ha basado en la teoría de la evolución natural de las especies, con el objetivo de solucionar problemas de búsqueda y mejora.

En esta rama de la IA se desarrollan los algoritmos genéticos y evolutivos, métodos de búsqueda apoyados en la teoría de la evolución de las especies, y buscan igualar el funcionamiento biológico de la selección natural y la genética (Coello et al., 2017).

Para cerrar el tema…

Para los temas vistos en la Lección y ahondar más, revisa los capítulos en los libros:

Enlaces

Título: Inteligencia Artificial, un enfoque moderno

Autores: Stuart Russell y Peter NorvigSección a consultar: Sección 4.1 De la página 107 a la 118

Título: La computación en México por especialidades académicas(267-299).

Autor:Carlos Artemio Coello Coello, Carlos Alberto Brizuela Rodríguez, Nareli Cruz Cortés, Arturo Hernández Aguirre, Efrén Mezura Montes, Alicia Morales-Reyes, Diego Alberto Oliva Navarro, Katya Rodríguez Vázquez, Hugo Terashima Marín y Edgar Emmanuel Vallejo Clemente.Sección a consultar: Capítulo No. 8 Computación evolutiva. De la página 267 a al 299.URL:Cap 8.pdf (amexcomp.mx).

¡FELICIDADES!

HAS CONCLUIDO SATISFACTORIAMENTELA LECCIÓN

Referencias

Para conocer más del tema te invito a revisar las siguientes referencias.

Coello, C. (2020). Introducción a la Computación Evolutiva (Notas de Curso). CINVESTAV-IPN. Recuperado 5 de marzo del 2021 en: http://delta.cs.cinvestav.mx/~ccoello/compevol/apuntes.pdfCoello, C., Brizuela, N., Cruz, A., Hernández, E., Mezura, A., Morales-Reyes, D., Oliva, K., Rodríguez, H., Terashima, E., y Vallejo, H. (2017). Capítulo 8 - Computación Evolutiva. En Coello, C. (Editor). La computación en México por especialidades académicas(267-299). México: Academia Mexicana de Computación AC. Recuperado de: Cap 8.pdf (amexcomp.mx).Manyá, F. y Gomes, C. (2003). Técnicas de resolución de problemas de satisfacción de restricciones. Revista Iberoamericana de Inteligencia Artificial, Año/Vol. 7, No. 19. Recuperado de: https://www.redalyc.org/pdf/925/92571911.pdf López de Mántaras, B. y Meseguer, P. (2017). Inteligencia artificial. España: Consejo Superior de Investigaciones Científicas y Los Libros de la Catarata.

Referencias

Para conocer más del tema te invito a revisar las siguientes referencias.

REAL ACADEMIA ESPAÑOLA. (2020). Diccionario de la lengua española, 23.ª ed., [versión en línea]. Recuperado 4 de marzo del 2021 en: https://dle.rae.es Russell, S. y Norvig, P.(2004).Inteligencia Artificial. Un Enfoque Moderno. España: Pearson Educación.Russell, S. y Norvig, P. (2008). Inteligencia artificial: un enfoque moderno (2a. ed.). Pearson Educación. Recuperado de: https://elibro-net.ezproxy.uveg.edu.mx:2048/es/lc/bibliotecauveg/titulos/45310Santana Quintero, L. y Coello, C. (2006). Una introducción a la computación evolutiva y algunas de sus aplicaciones en Economía y Finanzas. Vol. 2, diciembre. España: Universidad Pablo de Olavide. Recuperado 3 de marzo del 2021 en: https://www.redalyc.org/pdf/2331/233117243001.pdf

Créditos

Autor: Ricardo Contreras Velázquez. © UVEG. Derechos reservados. El contenido de este formato está sujeto a las disposiciones aplicables en materia de Propiedad Intelectual, por lo que no puede ser distribuido, ni transmitido, parcial o totalmente, mediante cualquier medio, método o sistema impreso, electrónico, magnético, incluyendo el fotocopiado, la fotografía, la grabación o un sistema de recuperación de la información, sin la autorización por escrito de la Universidad Virtual del Estado de Guanajuato. Algunos recursos visuales y/o audiovisuales fueron tomados total y/o parcialmente de www.freepik.es.