Algoritmos de Búsqueda Local y Problemas de Optimización

1.1.       INTRODUCCIÓN

En anteriores publicaciones hable sobre las búsquedas informadas y diversas estrategias que se utilizan para este tipo de búsquedas generando una secuencia de posibles estados de manera sistemática, en las búsquedas locales lo importantes es alcanzar al estado objetivo más que como se hizo para poder llegar, si bien es conocido las búsquedas informadas son efectivas al momento de encontrar un resultado, aunque este no sea el más óptimo.

En vista de que existen problemas en los que se deben satisfacer ciertas restricciones para llegar al mejor de todos los objetivos, surgen algunos algoritmos de búsqueda local y problemas de optimización en los cuales el camino hacia la solución del problema es irrelevante y lo que importa es simplemente la solución.

En esta publicación les hablare de aquellos algoritmos de búsqueda local y de cómo funcionan.

1.2.       OBJETIVO 

Conocer la importancia de los algoritmos de búsqueda local y problemas de optimización para comprender su funcionamiento y uso en la solución de problemas de agentes.

MARCO TEÓRICO

Como ya he mencionado estos algoritmos de búsqueda local no se preocupan por los caminos que se puedan tomar para llegar a un estado óptimo, si no que se enfocan en su gran parte en el estado actual y se mueve de un estado vecino hacia otro, este tipo de algoritmos tienen algunas ventajas que los vuelven importantes en comparación con otros algoritmos como son:

·         Son ahorrativos: No usan mucha memoria ya que no almacenan la secuencia de estados.

·         Razonables: Ofrecen soluciones posibles a un problema cuando el espacio de estados es infinito.  

·         Óptimos: Capaces de encontrar el mejor estado en base a su función objetivo. 

2.1.       Búsqueda Por Ascensión En Colina

Este algoritmo es una de las estrategias de las búsquedas locales, el cual no mantiene un árbol de búsqueda si no que solo la representación del estado actual y el valor de la función objetivo, se basa en iteraciones que intentan dar solución a un problema localizando la mejor solución a través de la modificación de un elemento incremental. El nombre de este algoritmo se debe gracias a que realiza una búsqueda hacia arriba y termina cuando alcanza el lugar más alto de ahí surge la similitud con una colina.

Imagen 1: Representación del Algoritmo Ascensión de Colinas

Pese a que es un algoritmo simple y muy conocido en inteligencia artificial por ser bueno para encontrar un óptimo local no garantiza encontrar la solución óptima debido a que pueden existir muchos posibles estados en donde la búsqueda se puede atascar debido a un estado máximo o mínimo local, una meseta y una cresta.

Este algoritmo posee tres variantes diferentes y estas son:

Imagen 2: Variaciones del Algoritmo Ascensión en Colina

2.1.       Búsqueda De Temple Simulado

Este algoritmo surge como alternativa para el algoritmo de ascensión de colinas ya que este no es muy complejo debido a que solo verifica los caminos cuesta arriba y no pasa por estados bajos donde el costo es más alto y se estanca en máximos locales.

El temple simulado es una combinación de la ascensión de colinas y la aleatoriedad que establezca completitud, esta clase de algoritmos no escoge el mejor movimiento si no que más bien lo hace de manera aleatoria y si esta mejora la situación actual entonces es aceptado.

Imagen 3: Algoritmo Temple Simulado

2.1.       Búsqueda Por Haz Local

A diferencia de las otras búsquedas en las cuales los estados expandidos y sus nodos no son guardados en la memoria, la búsqueda por haz local guarda la pista de K estados, y se generan estados sucesores aleatorios para cada uno de ellos, por lo que se seleccionan los mejores sucesores y en caso de ser el objetivo el algoritmo se detiene, en caso de no ser el objetivo se selección los K mejores estados de una lista completa y se repite el proceso.

La gran diferencia con el algoritmo de reinicios aleatorios es que la búsqueda por haz local no es independiente, poniendo un ejemplo tenemos un estado generado aleatoriamente puede generar a su vez muchos otros estados considerados buenos, y otro estado puede generar el mismo número de estados, pero malos y solo uno bueno, esto puede indicar claramente que el estado a elegir sería el primero en la lista.

Imagen 4: Algoritmo Haz Local

2.1.       Algoritmos Genéticos

Estos algoritmos son una variante de los algoritmos de Haz local, estos son métodos adaptativos que pueden ser utilizados para implementar búsquedas y problemas de optimización, se basan en los procesos genéticos de los organismos biológicos, codificando una posible solución a un problema en un "cromosoma" compuesto por una cadena de bits o caracteres. Estos algoritmos se enfocan en la combinación de dos estados padres para formar un nuevo estado sucesor o hijo.

Imagen 5: Algoritmo Genético

CONCLUSIONES

Los algoritmos de búsqueda local y problemas de optimización son una medida de solución arbitraria a un problema, es decir que se trata de maximizar o minimizar un resultado, esto en base a la búsqueda del mejor resultado posible dentro de un espacio de resultados, a travez de un conjunto de restricciones determinados por el tipo de búsqueda local que se realice.

Es clase de algoritmos son muy eficaces en problemas complejos, aplicados al mundo real, como producción y ciertas actividades que requieren precisión y mejora de resultados. Dentro de estos algoritmos, están los mas complejos, que son los algoritmos genéticos, los cuales son muy conocidos pero tienen una utilización compleja.

BIBLIOGRAFIAS

Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España

Funciones Heurísticas

1.1.       INTRODUCCIÓN

Como ya conocemos la inteligencia artificial busca diseñar métodos de búsquedas que permitan encontrar una solución óptima a un problema, es por esto que Newell en el año de 1963 investigo sobre los diferentes tipos de procesos que existen para la resolución de un problema dando, así como resultado la inauguración del primer laboratorio de sistemas expertos dedicado a este tipo de problemas de búsquedas. La función heurística tiene como objetivo encontrar una posible solución a un problema haciendo uso de un conocimiento previo, siguiendo una secuencia de pasos que lo guíen hacia su meta.

A lo largo de esta publicación les daré a conocer que tipos de funciones heurísticas tenemos, como estas funcionan y cuál es el objetivo de las búsquedas informadas que hacen uso de esta función para encontrar una estrategia optima que lo guía hacia una posible solución.

1.2.       OBJETIVO 

Conocer cómo funcionan las funciones heurísticas y en qué tipos de problemas podemos aplicarlas.

MARCO TEÓRICO

Una vez que tenemos en claro que las búsquedas informadas son las más eficientes ya que estas proveen al agente de información previa para encontrar una solución de manera más rápida, tenemos que conocer que hace que este tipo de búsquedas se realizan y esto se debe gracias a la función heurística. 

2.1.       ¿Qué es la Función Heurística?

La función heurística se representa de la siguiente forma h(n), siendo esta función el costo estimado del camino más barato desde el nodo n hasta el nodo objetivo, dependiendo del tipo de búsqueda informada la función heurística se denotara de forma diferente, por ejemplo cuando tenemos un tipo de búsqueda voraz primero el mejor la función heurística será f(n) = h(n) mientras que si tenemos otro tipo de búsqueda por ejemplo búsqueda A* la función heurística será de la siguiente manera f(n) = g(n) + h(n).

Imagen 1: Problema de Puzzle 8

Uno de los primeros problemas en utilizar la función heurística fue el puzzle 8 un juego cuyo objetivo era de deslizar las piezas de manera horizontal y vertical a un espacio vació hasta que se consiga que las piezas queden en el orden establecido. En el puzzle 8 existen 181.440 debido a que el árbol de ramificación de este juego es de 3 debido a que si la ubicación es una esquina existen 2 posibles movimientos, si está en el centro existen 4 posibles movimientos y si se encuentra en el borde de una línea existen 3 posibles movimientos es por eso que se dice que la media será de 3. 

A diferencia del puzzle 8 existen otro tipo de problemas similares entre ellos tenemos al 15 puzzle el cual podemos ver tendrá una cantidad más grande de posibles resultados, pero ¿cómo llevaríamos a cabo un problema como estos? Tendremos que hacer de nuestra función heurística la cual como hemos mencionado es una estrategia para resolver problemas de manera óptima, una posible solución a este problema del 15 puzzle sería contando las piezas que se encuentren en la posición incorrecta y las distancias que tienen se suman hasta llegar a un nodo objetivo.

Imagen 2: Problema de Puzzle 15

2.1.            La Precisión De La Heurística En El Rendimiento

Para conocer si nuestra función heurística es la correcta es necesario evaluar el rendimiento de esta mediante un factor de ramificación eficaz, este factor puede variar según el tipo de problema que encontramos y generalmente es utilizado para problemas de búsquedas complejos, una función heurística adecuada seria aquella que tenga el valor de b* el cual es el factor de ramificación más cerca de uno.

2.2.       Inventar Funciones Heurísticas Admisibles.

Cuando encontramos un problema en donde no tenemos tantas restricciones que le permitan llegar a un estado objetivo se le conoce como un problema relajado, estos problemas cuentan con un costo para la función heurística admisible, en esta ocasión los problemas de 8 puzzle y el 15 puzzle no son de este tipo pese a que estos poseen demasiadas posibles soluciones para llegar a un estado objetivo y que estos cuentan con la restricción de que solo se pueden mover de manera vertical y horizontal dependiendo del espacio que se encuentre vacío.

2.3.       Absolver

Este programa fue diseñado con el fin de generar una función heurística a partir de un problema dado, gracias a este sistema se generó una función heurística para el problema del puzzle 8.

2.4.       Aprendizaje De Heurísticas Desde La Experiencia

Las funciones heurísticas son capaces de percatarse cual será el costo para llegar a una posible solución que comienza desde un nodo n, esto es una forma de aprender que se les presenta a este tipo de problemas ya que gracias a la experiencia que van adquiriendo en cada movimiento los acerca más a una solución óptima, el tipo de aprendizaje de este tipo de problemas heurísticos es inductivo porque solo evalúan el costo de la solución para los estados que pueden surgir a lo largo de la búsqueda de una posible solución. Un ejemplo que podría plantear para entender este tipo de problemas sería el de un agente que se encuentre extraviado y se encuentre un camino con tres posibles soluciones, esa sería una descripción, pero las características de los caminos posibles ya que esta serviría de mucha ayuda para determinar el camino objetivo, permitiéndole analizar la distancia desde donde se encuentra ubicado hasta el final del camino.

CONCLUSIONES
Como podemos comprobar una función heuristica es la que le permite a un agente determinar la secuencia de pasos para llegar a un estado aceptador, estas funciones son de suma importancia en los problemas de búsquedas informadas ya que gracias a estas se puede evaluar el costo de los movimientos de un estado n hacia el objetivo y ademas también del costo del camino.

BIBLIOGRAFIAS

Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España

Búsqueda Informada y Exploración

1.1.       INTRODUCCIÓN
Continuando con la temática de inteligencia artificial de mis anteriores publicaciones conocemos que la inteligencia artificial busca crear agentes capaces de resolver problemas de los cuales no se tenga conocimiento para encontrar una posible solución es por esto que hace uso de las búsquedas informadas, este tipo de búsquedas a diferencia de las búsquedas no informadas son más precisas, ya que poseen de un conocimiento previo del entorno en el que el agente se desenvolverá, aunque en ciertas ocasiones se puede tener información del entorno no siempre se conocerá cual será la solución, es por esta razón que la inteligencia artificial hace uso de este tipo de búsquedas.En esta nueva publicación les hablare sobre las búsquedas informadas, cuales son los principales algoritmos de búsquedas informadas y como aprender a realizar búsquedas más objetivas.1.2.       OBJETIVO
Conocer cómo funcionan las búsquedas informadas y cuáles son los principales algoritmos de este tipo de búsquedas.

MARCO TEÓRICO

2.1.       Estrategias De Búsquedas Informadas Heurísticas

Como ya he venido mencionando las búsquedas informadas son aquellas que poseen un conocimiento previo para ¿que el agente pueda conocer el entorno en el que se desenvolverá pero que hace especial a este tipo de búsquedas? A diferencia de las búsquedas no informadas las informadas hacen uso de estrategias para poder encontrar soluciones de manera más eficiente que las no informadas, una de ellas es la utilización de la búsqueda primero el mejor la cual es un caso particular de las búsquedas de árboles en donde se tenía que expandir un nodo basado en una función de evaluación. Este tipo de búsqueda hace uso de una función de evaluación en donde f(n) será el costo estimado del camino más barato desde el nodo n hacia el nodo objetivo.

2.1.       Búsqueda Voraz Primero El Mejor

Esta búsqueda es una derivación de la búsqueda primero el mejor, la cual trata de expandir el nodo más cercano al objetivo para poder encontrar una solución que lo conduzca hacia un estado objetivo, esta búsqueda evalúa los nodos mediante una función heurística f(n)=h(n) la cual es un componente clave de este tipo de algoritmos. La función de evaluación es la encargada de devolver los valores de la expansión de los nodos en donde se escoge el nodo que posea una mejor evaluación. Un defecto de este tipo de búsqueda es que no tiene en cuenta el costo que tendrá n hasta llegar a su objetivo.

Imagen 1: Búsqueda Voraz Primero el Mejor

2.1.       Búsqueda A*

La búsqueda A* o búsqueda en estrella como se le conoce es una de las estrategias de búsqueda más conocidas de la búsqueda primero el mejor, esta trata de minimizar el costo total entre el nodo origen y el nodo objetivo, a diferencia de la búsqueda voraz primero el mejor esta búsqueda trata de buscar el costo del camino más barato de la solución mediante la función de evaluación, la cual se representa de la siguiente manera f(n) = g(n) + h(n) en donde g(n) será el costo del camino desde el nodo inicio hasta el nodo n  y h(n) será el costo estimado del camino hacia el nodo objetivo. Esta estrategia de búsqueda en A* es óptima si la función heurística cumple con las condiciones de admisibilidad y consistencia.

Imagen 2: Búsqueda A*

2.1.       Búsqueda Heurística Con Memoria Acotada

También conocida como búsqueda con memoria simplificada, este tipo de búsqueda lo que busca es expandir los nodos de la misma forma que lo hace la búsqueda en A* hasta el punto en que la memoria disponible se llene, el objetivo de esto es hacer que no se puedan ingresar más nodos al árbol, lo que hace este algoritmo es eliminar el peor nodo hoja, para de esta manera volver hacia atrás el valor del nodo olvidado de forma que el antepasado sepa cuál es la calidad del mejor camino en ese subárbol, si todos los nodos descendientes de un nodo n son olvidados no sabremos porque camino ir pero lo que si sabremos es el costo de ese camino. Este algoritmo es óptimo si la solución es alcanzable si no devolverá la mejor solución.

CONCLUSIONES
Este tipo de búsquedas informadas nos han demostrado que son muy utiles encontrando una solución optimas en problemas de búsqueda, se pueden aplicar a agentes para que estos puedan desenvolverse en un ambiente conocido y como ya se conoce estas búsquedas usan una función de evaluación heurística que se encarga de devolver los valores de los nodos de expansión.

BIBLIOGRAFIAS

Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España

Silabo de I.A 2

Silabo IA2 by GermánicoVélez

Caratula de I.A 2

ESCUELA SUPERIOR POLITÉCNICA AGROPECUARIA DE MANABÍ MANUEL FÉLIX LÓPEZ

CARRERA INFORMÁTICA

SEMESTRE: SÉPTIMO                 PERIODO: OCT 2015/MAR 2015

  

PORTAFOLIO

  

TEMA:

INTELIGENCIA ARTIFICIAL II

AUTOR:

GERMÁNICO E. VÉLEZ PINTO 

FACILITADORA:

ING. HIRAIDA SANTANA CEDEÑO

CALCETA, OCTUBRE 2015

Red Neuronal Adaline

INTRODUCCIÓN

La inteligencia artificial en su desarrollo a tratado de cumplir con su objetivo primordial que es creación de entiendades que piensen y actúen como los seres humanos, para ha hecho de las redes neuronales artificiales que han sido a gran avance ya que son capaces de resolver problemas complejos y tienen la capacidad de auto aprendizaje, estas redes neuronales artificiales están inspiradas en las redes neuronales biológicas de los seres humanos, gracias a esto han desarrollado diversos modelos de redes neuronales entre estos las redes Adaline que son capaces de resolver problemas mas complejos y es una de los muchos avances de la inteligencia artificial.

OBJETIVO

El objetivo de esta publicación es dar conocer como funciona la red Adaline, cuales son sus principales ventajas, en que tipo de aplicaciones podemos utilizar a esta red neuronal artificial y genera su aprendizaje.

MARCO TEÓRICO

Las redes neuronales ADALINE fueron desarrolladas en el año 1960  por el profesor Bernie Widrow y su alumno Tedd Hoff de la Universidad de Standford California, el objetivo de este tipo de red neuronal era la de crear una red adaptiva  en el sentido de que exista un procedimiento definido en donde se modifiquen los pesos de los objetivos para hacer posible que la red proporcione la señal  de salida correcta para cada tipo de entrada dada.

Características

Entre las características que posee esta red artificial tenemos que su aprendizaje es de tipo Off-Line el cual requiere de un conjunto de datos de entrenamiento y datos de prueba que ajusten los pesos de las conexiones de la red neuronal en función de las diferencias que existen entre los valores deseados y los obtenidos en las señales de salida. Este tipo de red neuronal tiene un aprendizaje supervisado que se caracteriza porque determina la respuesta que se debería generar a partir de una entrada determinada. 

Aprendizaje

El aprendizaje de la red Adaline a diferencia de los perceptrones es que a la hora de modificar los pesos de ambos valores durante el entrenamiento, la red Adaline tiene en cuenta el grado de la corrección de la salida obtenida con respecto a la estimada, esto se consigue gracias a que la aplicación de la regla Delta que es definido por un patron de entrada que tiene una salida estimada y una salida deseada.

Ventajas de la red Adaline

 Entre las ventajas que posee este tipo de red neuronal artificial tenemos es que su gráfica de error es una hipérbole un único valor mínimo global o de mejor manera una recta de valores mínimos todos ellos globales que a diferencia de los perceptrones esto evita la gran cantidad de problemas que tienen los perceptrones durante el entrenamiento ya que sus valores mínimos son locales.

Aplicaciones de la red Adaline

Entre las aplicaciones que tenemos para este tipo de red neuronal artificial tenemos las siguientes:

• Asociación de patrones: Este tipo de aplicación puede ser útil para resolver problemas en donde los patrones siempre sean linealmente separables.D

Dentro del campo del procesamiento de señales la red Adeline puede ser utiliza como: 

• Filtros de ruido: Sirven para limpiar los ruidos de las señales que transmiten la información.
• Filtros adaptivos: Una red Adeline es capaz de predecir los valores de una señal en un instante si se conoce el valor del mismo en instantes anteriores. El error de prediccion de la red sera mayor o menor dependiendo del tipo de señal que queremos predecir.

La union de varias redes artificial Adeline se conoce como redes Madeline.

CONCLUSIONES
Las redes Adaline tienen un sin números de usos dentro del campo de la inteligencia artificial que van desde el reconocimiento de patrones hasta la traducción de textos para personas problemas de lenguaje.
La inteligencia artificial sigue avanzando y las redes Adaline son unos de los avances que hacen que esta ciencia siga en evolución.
BIBLIOGRÁFIA

Isasi, P. y Galván, I. 2004. Redes Neuronales Artificiales: Un enfoque Práctico. Madrid, Esp. pág 34.

Perceptrón Multicapa

INTRODUCCIÓN

Este tipo de red artificial nació de la unión de varios perceptrones simples, estas redes neuronales multicapa se pueden clasificar de manera que que se conectan sus capas, este tipo de neuronas dio paso a la resolución de problemas mas complejos como los no lineales. Esta idea fue propuesta por los cientificos Rumelhart, Hinton y Williams en el año 1986 cuya hipotesis era la de retro propagar los errores medidos en las señales de salida de la red neuronal artificial hacia las neuronas que se encuentran en la capa oculta.

OBJETIVO

El objetivo de esta publicación es la de conocer como funcionan estas redes neuronales multicapa  y como hacen paras resolver problemas mas complejos basandose en los principios propuestos por Frank Rosenblatt en su modelo de perceptrón simple.

MARCO TEÓRICO

Las redes multicapa como ya hemos mencionado anteriormente son un modelo de redes neuronales artificial compuestos por varios perceptrones simples, estas redes neuronales multicapa están compuestas por tres capas que son:

• Capa de entrada: Esta capa esta formada por las neuronas encargadas de transmitir los patrones de entrada en la red neuronal.

• Capa oculta: En esta capa pueden existar mas de una sola, esta formada por aquellas neuronas cuyas capas de entrada provienen de las capas anteriores y cuyas salidas pasan a las neuronas de las capas posteriores.

• Capa de salida: Esta capa esta formada por las neuronas encargadas de emitir los valores de salida que corresponden a todas las salidas de la red neuronal.

Usualmente las capas de este tipo de redes neuronales se encuentran ordenadas de la manera en que reciben las señales de entrada hasta las señales de salida y se encuentran unidas en ese orden. A este tipo de conexiones se les denomina como conexiones hacia adelante aunque también existen redes con conexiones hacia atrás.

Redes neuronales conexiones hacia adelante

Como hemos mencionada este tipo de redes contienen conexiones entre sus capas hacia adelante, esto quiere decir que una capa no puede recibir ninguna señal antes que ella, en la dinámica de la computación. 

Como ejemplos de este tipo de redes neuronales tenemos a los perceptrones, las redes Adaline, los algoritmos de retro-programación y los modelos de redes Kohonen.

Redes neuronales conexiones hacia atras

A este tipo de redes neuronales artificiales se las diferencia de las de conexiones hacia adelante porque en este tipo de redes si pueden existir conexiones entre capas hacia atras, esto quiere decir que la informacion pueden retornar entre las capas anteriores dentro de la dinamica de la red.

Como ejemplos de este tipo de redes neuronales tenemos a las redes BAM y ART.

CONCLUSIONES

Los perceptrones multicapa han demostrado ser de gran ayuda en el avance de las redes neuronales artificiales ya que estos a diferencia de los perceptrones simples pueden resolver problemas mas complejos, formados por diversas capas que le permiten el proceso de entrada, almacenamiento, procesamiento y análisis de la información que hacen de estas redes uno de los avances mas grandes de la inteligencia artificial.

BIBLIOGRAFÍA

Isasi, P. y Galván, I. 2004. Redes Neuronales Artificiales: Un enfoque Práctico. Madrid, Esp. pág. 45.