PROLOG

Fecha de Clase: 29 de Junio al  3 de Julio 2015
INTRODUCCIÓN

En esta clase aprendimos sobre prolog es uno de los primeros lenguaje de programación, también es el más conocidos y utilizados en la ingeniería informática para el estudio de la inteligencia artificial. Prolog es muy antiguo, y está formado por un conjunto de reglas y hechos,  que se ejecutan normalmente. Este lenguaje de programación almacena una base de conocimiento que luego estas pueden ser consultadas, basadas en lógica de predicados de primer orden, ya que este programa esta descrito en un lenguaje declarativo, este lenguaje implica objetos y relaciones.

OBJETIVO

Obtener conocimientos basicos de prolog y presentar ejemplos prácticos de este lenguaje de programación.

MARCO TEÓRICO

PROLOG

Prolog ha sido diseñado e implementado de tal manera que puede ser fácilmente modificado para experimentos con la programación lógica y la relación entre la programación lógica y otros paradigmas de programación. Prolog tiene un rico conjunto de predicados incorporados y un rendimiento razonable, lo que hace posible el desarrollo de las aplicaciones importantes en el mismo. La versión actual ofrece un sistema de módulos, recolección de basura y una interfaz para el lenguaje C.

PROLOG está orientado a la resolución de problemas mediante el cálculo de predicados, basado en (Aedo, G. 2004)

·         Base de datos a las que se realiza preguntas.

·         Pruebas matemáticas y lógicas (and, or, not).

·       Especificaciones cómo debe ser la solución, en vez de dar el algoritmo para su resolución. La solución se obtiene mediante búsqueda aplicando la lógica de predicados.

ELEMENTOS DEL LENGUAJE:

Hechos (átomos).

Reglas (cláusulas de Horn).

Preguntas u objetivos (conjunciones ó disyunciones de átomos).

HECHOS

Para explicar los fundamentos de PROLOG vamos a utilizar el típico ejemplo de las relaciones familiares. Para decir que María es madre de Jesús, podríamos declarar el siguiente hecho PROLOG:

madre(maria, jesus).

“madre” es el nombre de la relación o nombre de predicado y “maria” y “jesus” son los argumentos. Los hechos acaban siempre con punto. Nosotros interpretaremos que María, primer argumento de la relación, es la madre de Jesús, segundo argumento de la relación. Sin embargo, este orden es arbitrario  y cada programador puede darle su propio significado. Los nombres de las relaciones y los argumentos que se refieren a objetos o personas concretas se escribirán con minúscula.

Otros ejemplos de hechos pueden ser los siguientes:

le_gusta_a(juan,maria).

valioso(oro).

tiene(juan,libro).

da(juan,libro,maria).

Los nombres también son arbitrarios y el programador decidirá la interpretación que haga de ellos. La relación le_gusta_a(juan,maria) es equivalente a la relación a(b,c), aunque para que la interpretación sea más sencilla, se recomienda que los nombres se elijan de forma que ayuden a su interpretación.

Los hechos no tienen que reflejar el mundo real necesariamente, pero será única y exclusivamente lo que PROLOG tomará como verdadero. Un conjunto de hechos (también llamados cláusulas), junto con un conjunto de reglas, forman lo que se llama una base de datos. (Toledo, F.et al.., 2001)

REGLAS

El verdadero poder de cualquier lenguaje de programación está en su mecanismo de abstracción. En Prolog la norma establece el mecanismo de abstracción. Cuando un hecho sólo se puede especificar que una tupla de valores satisface un predicado, una regla puede especificar en qué condiciones una tupla de valores satisface un predicado.

El bloque básico de una regla edificio se llama un átomo: un predicado seguido de una tupla de términos, donde ambas constantes y variables son términos (veremos que un término puede realmente tener más estructura). Vemos inmediatamente que cada hecho es un átomo. Cuando la tupla satisface el predicado del átomo decimos el átomo es cierto. Cada regla está dividida en dos partes por el símbolo ': -': la parte izquierda se llama el jefe de la gobernar, mientras que el lado derecho es el cuerpo de la regla.

Ejemplo:

predecesor(X,Y):-progenitor(X,Y).

predecesor(X,Y):-progenitor(X,Z), progenitor(Z,Y).

predecesor(X,Y):-progenitor(X,Z), progenitor(Z,V), progenitor(V,Y).

PREGUNTAS U OBJETIVOS

En tiempo de ejecución, aparece el prompt ?- y el intérprete de PROLOG espera que el usuario introduzca un objetivo en forma de predicado, con o sin variables. (Cubero, C; y Berzal, F. 2010)

Para realizar preguntas más interesantes, como por ejemplo, qué le gusta a María o cuáles son los padres de Damián, se usarán las variables. En PROLOG las variables empiezan por mayúscula. Por ejemplo:

 ?-le_gusta_a(maria,X).

?-progenitor(Y,damian).

   

EJEMPLO PRACTICO

ARBOL DE FAMILIA

CODIGO PROLOG

hijo(ramona,pedro).

hijo(roberty,pedro).

hijo(genoveva,pedro).

hijo(eddy,ramona).

hijo(loly,ramona).

hijo(paola,ramona).

hijo(edward,roberty).

hijo(douglas,roberty).

hijo(xavier,genoveva).

primo(eddy,edward).

primo(eddy,douglas).

primo(eddy,xavier).

primo(loly,edward).

primo(loly,douglas).

primo(loly,xavier).

primo(paola,edward).

primo(paola,douglas).

primo(douglas,eddy).

primo(douglas,paola).

primo(douglas,loly).

primo(douglas,xavier).

primo(edward,loly).

primo(edward,paola).

primo(edward,eddy).

primo(edward,xavier).

primo(xavier,paola).

primo(xavier,eddy).

primo(xavier,loly).

primo(xavier,edward).

primo(xavier,douglas).

primo(paola,xavier).

hermano(eddy,paola).

hermano(eddy,loly).

hermano(paola,eddy).

hermano(paola,loly).

hermano(loly,eddy).

hermano(loly,paola).

hermano(douglas,edward).

CONSULTA PROLOG

CONCLUSIÓN

Prolog es el lenguaje de programación que es muy utilizado para aprender los principios básicos de la inteligencia artificial, este lenguaje utiliza una base de conocimiento llamada bases de datos, en donde se almacena un conjunto de reglas y hechos, que sirven para realizar preguntas o consultas. También prolog trabaja con relaciones y objetos, asi que es recomendable utilizar prolog para las personas que quieran indagar sobre la IA y sus principios basicos. Para estos hay que conocer claramente los elementos de Prolog como lo son las reglas, los hechos y las consultas, y su utilizacion para su correcta aplicación.

BIBLIOGRAFÍA

Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.

Wielemaker, J. 1996. SWI-Prolog 2.7-Reference Manual.

Aedo, G. 2004. Estudiaremos un caso de lenguaje orientado a la programación lógica (cálculo de predicados): Prolog. Formato HTML. Disponible en: http://www.desarrolloweb.com/

Toledo, F; Pacheco, J y Escrig, M. 2001. Lenguaje de programación PROLOG.

Cubero, C; y Berzal, F. 2010. Sistemas inteligentes de gestion. Disponible en: http://elvex.ugr.es/

BÚSQUEDA LOCAL EN ESPACIOS CONTINUOS

Fecha de Clase: 8 - 12 de Junio 2015
INTRODUCCIÓN

En esta clase se hizo referencia a la búsqueda local en espacios continuos, conociendo con anterioridad la diferencia entre  espacios discretos y continuos. Puesto que los espacios continuos son los que más se asemejan a la realidad que se presentan en el mundo real. Es por esto que el estudio de los espacios continuos se hace cada vez más importante para encontrar soluciones a problemas que se presentan en estos entornos a través de técnicas y búsquedas. Cabe recalcar que este tipo de búsqueda, se realiza a cualquier acontecimiento que trate del mundo real, para dar soluciones óptimas. Son los más utilizados y es por estos que se han desarrollado técnicas como el gradiente, gradiente empírico, línea de búsqueda, Newton-Raphson.

OBJETIVO

Identificar la búsqueda local en espacios continuos, para conocer cuál es su importancia en la inteligencia artificial.

MARCO TEÓRICO

BÚSQUEDA LOCAL

En la búsqueda local, se empieza de una configuración inicial (generalmente aleatoria) y se hacen pequeños cambios (a través de operadores) hasta alcanzar un estado desde el cual no se puede alcanzar ningún estado mejor. Las técnicas de búsqueda local son propensas a encontrar óptimos locales que no son la mejor solución posible. El óptimo global es generalmente imposible de alcanzar en un tiempo limitado, por el tamaño del espacio de soluciones. (Ceccaroni, L. 2007)

ESPACIOS CONTINUOS

Si existe una cantidad infinita de percepciones y acciones distintas y discernibles, se dice que el ambiente es continuo. Los espacios continuos son los que más se asemejan a la realidad del mundo y los problemas más frecuentes.

EJEMPLO DE BÚSQUEDA LOCAL EN ESPACIOS CONTINUOS

Supongamos que queremos colocar tres nuevos aeropuertos en cualquier lugar de Rumania, de forma tal que la suma de las distancias al cuadrado de cada ciudad sobre el mapa imagen1 su aeropuerto más cercano sea mínima. Entonces el espacio de estados está definido por las coordenadas de los aeropuertos: (x1, y1), (x2, y2), y (x3, y3). Es un espacio seis dimensional, también decimos que los estados están definidos por seis variables (en general, los estados están definidos por un vector n-dimensional de variables, x). Moverse sobre este espacio se corresponde a movimientos de uno o varios de los aeropuertos sobre el mapa La función objetivo f(x1,y1,x2,y2,x3,y3) es relativamente fácil calcularla para cualquier estado particular una vez que tenemos las ciudades más cercanas, pero bastante complicado anotar en general. (Russell, S. y Norvig, P. 2004)

Imagen1. Mapa de carreteras simplificados de las carreteras de Rumania

TÉCNICAS DE BÚSQUEDA LOCAL EN ESPACIOS CONTINUOS

GRADIENTE: El gradiente es una operación vectorial, que opera sobre una función escalar, para producir un vector cuya magnitud es la máxima razón de cambio de la función en el punto del gradiente y que apunta en la dirección de ese máximo. (Olmo, M y  Nave, R. 2010?)

 GRADIENTE EMPIRICO: Se puede determinar evaluando la respuesta a pequeños incrementos y decrecimientos en cada coordenada. El gradiente impirico se crea por la necesidad de mejorar la técnica del gradiente. Donde alfa es una pequeña constante.

LÍNEA DE BÚSQUEDA: trata de vencer el dilema amplia la dirección de gradiente actual (que por lo general duplica repetidamente alfa) hasta que comience a disminuir otra vez, el cual llega un punto en el que se crean nuevos estados. (Russell, S. y Norvig, P. 2004)

NEWTON-RAPHSON: esta técnica es muy utilizada para encontrar las raíces de una función, procurando que la solución de una ecuaciones sean de la forma g(x)=0, y calculando estimaciones de la raíz.

Aunque esta técnica ha evolucionado implementando la matriz Hesiana,  lo cual ayuda a Newthon-Raphson a hacer más barata en espacios dimensionales.

OPTIMIZACIÓN CON RESTRICCIONES Y PROGRAMACION LINEAL

La programación lineal resuelve problemas donde todas las relaciones entre las variables son lineales, tanto en las restricciones como en la función objetivo, la presencia de una única función no lineal hace que el problema no pueda clasificarse como problema de programación lineal; ésta evidencia su aplicación en diversos campos, como la ingeniería, la economía, la gestión, y muchas otras áreas de la ciencia, la técnica y la industria. El objeto de la programación lineal es optimizar (minimizar o maximizar) una función lineal de n variables sujeto a restricciones lineales de igualdad o desigualdad, denominada función objetivo. (Ornelas, C y Marchenas, W. 2007)

Con esto se han estudiado problemas con tipos diferentes de restricciones y funciones objetivo:

·         Programación cuadrática

·         Programación cónica de segundo orden.

CONCLUSIÓN

Como conclusión puedo decir que el estudio de estas búsquedas locales en espacios continuos son importantes e indispensable si queremos introducirnos a la inteligencia artificial, puesto que este tipo de búsqueda en entornos continuos son los que más se presentan en el mundo, son problemas reales con los que hay que lidiar día a día. Las técnicas que se han desarrollado para que estas búsquedas locales en espacios continuos, para obtener soluciones óptimas a problemas que se presentan en el mundo real; cada  vez estas técnicas van evolucionando y son más eficaces, la técnica principal  es el gradiente de esta han ido surgiendo otras técnicas como lo es el gradiente empírico, línea de búsqueda y Newton Raphson.

BIBLIOGRAFÍA

Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.

Ceccaroni, L. 2007. Inteligencia Artificial: Búsqueda local. Formato HTML. Disponible en: http://www.cs.upc.edu/

Olmos, I. 2008. Estructura de un Agente. Formato PDF. Disponible en: http://www.cs.buap.mx/

Olmo, M y  Nave, R. 2010?. El Gradiente. Formato HTML. Disponible en: http://hyperphysics.phy-astr.gsu.edu/

Ornelas, C y Marchenas, W. 2007. Optimizacion y la programación lineal: Una Introduccion. Formato PDF. Disponible en: http://fglongatt.org/

ALGORITMOS DE BÚSQUEDA LOCAL Y PROBLEMAS DE OPTIMIZACIÓN

Fecha de Clase: 1 - 5 de Junio 2015
INTRODUCCIÓN

En este documento se va a escribir sobre los algoritmos de búsqueda, hasta el momento en documentos anteriores se ha descrito búsquedas que solo realizan una exploración sistemática, es decir que estas tienen almacenado en memoria uno o más caminos y se exploran hasta encontrar una solución al problemas. Pero en algunos caso esto se vuelve innecesario, es ahí donde nacen las búsquedas locales, estas trabajan únicamente con el estado actual y solo se mueve a sus estados vecinos. Estas búsquedas son más eficaces y presentan ventajas que antes no se habían conseguido con otro tipo de búsquedas, y los algoritmo que se han desarrollado son búsqueda de ascensión de colinas, temple simulado, por haz local y genéticos, a continuación en este documento se detallara los conceptos de estos algoritmos.

OBJETIVO

Conocer la importancia de la búsqueda local y los algoritmos que se han desarrollado.

MARCO TEÓRICO

Las búsquedas locales solo utilizan el estado actual y se mueve hasta sus estados vecinos y sus principales características y ventajas es:

•  Utilizan poca memoria.
•  Encuentran soluciones razonables en espacios infinitos.

Para comprender las busquedas locales necesitamos conocer el paisaje de espacios de estados, que nos permiten conocer las posición (definido por el estado) y la elevación (definido por la función objetivo).

La principal función de los algoritmos de búsquedas locales son muy utilizados para encontrar soluciones óptimas, a continuación los se describirán los algoritmos más conocidos:

BÚSQUEDA DE ASCENSIÓN DE COLINA

Algoritmo de ascensión en colina es una técnica de optimización matemática que pertenece a la familia de búsqueda local. Es un algoritmo iterativo que se inicia con una solución arbitraria a un problema, a continuación, intenta encontrar una solución mejor por incrementalmente el cambio de un solo elemento de la solución. Si el cambio produce una mejor solución, se hace un cambio incremental a la nueva solución, repitiendo hasta que no mejoras adicionales se pueden encontrar, Es bueno para encontrar un óptimo local (una solución que no se puede mejorar teniendo en cuenta una configuración de vecino) pero no es necesariamente garantía de encontrar la mejor solución posible (el óptimo global) de todas las posibles soluciones (el espacio de búsqueda). En problemas convexos, en ascenso   es óptima. Ejemplos de algoritmos que resuelven problemas convexos por bajada incluyen el algoritmo simplex para programación lineal y búsqueda binaria (Skiena. 2010)

La ascensión de colinas también conocidos como búsqueda local voraz porque toma un estado vecino bueno sin pensar hacia dónde ir después. Aunque la ascensión de colinas a menudo suele presentar problemas por los siguientes motivos:

• Máximo local: es el pico más alto que todos sus vecinos pero menos que el máximo global.
•  Cresta: cuando hay una secuencia de máximos locales, se vuelve un poco dificultoso la exploración del algoritmo.
• Meseta: cuando el máximo local plano, no tiene ninguna salida o una terraza y no puede avanzar en la búsqueda.

BUSQUEDA DE TEMPLE SIMULADO

Un algoritmo de ascensión de colinas que nunca hace movimientos cuesta abajo hacia estados con un valor inferior (o coste más alto) garantiza ser incompleto, porque puede estancarse en un máximo local. En contraste, un camino puramente aleatorio, es decir moviéndose a un sucesor elegido uniformemente aleatorio de un conjunto de sucesores, es completo, pero sumamente ineficaz. Por lo tanto, parece razonable intentar combinar la ascensión de colinas con un camino aleatorio de algún modo que produzca tanto eficacia como completitud. (Russell, S. y Norvig, P. 2004)

BÚSQUEDA POR HAZ LOCAL

No garantiza solución óptima y mejor comportamiento que escalada con reinicio aleatorio k veces, se comparte información útil entre los elementos de la población. ( _____. 2009.)

• Mejora la búsqueda en haz estocástico
• Se eligen k sucesores aleatoriamente con probabilidad creciente con la heurística
• Cierta similitud con la evolución natural de poblaciones.

Imagen 1. Busqueda haz local

ALGORITMOS GENÉTICOS

Los Algoritmos Genéticos  son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas. Un algoritmo genético consiste en una función matemática o una rutina de software que toma como entradas a los ejemplares y retorna como salidas cuáles de ellos deben generar descendencia para la nueva generación. (Alfaro, E. 2011?)

CONCLUSIÓN

Puedo concluir que la búsqueda local es muy eficaces a diferencia de otras búsquedas, ya que estas encuentran soluciones utilizando menos memoria, y en espacios que son grande y en ocasiones infinitos. Como estas búsquedas presentan muchas ventajas se han desarrollados algoritmos que se ajusten a estas búsquedas. La búsqueda en ascensión de colinas una de las más populares que busca la cumbre más alta entre todos los estados. Otro de los algoritmos más usados es el genético ya que este se basa en la reproducción sexual a diferencia de otros algoritmos. Es por esto que los algoritmos han sido de gran aporte a la inteligencia artificial, para realizar búsquedas que cada vez ahorren más recursos y se obtengan mejores resultados.

BIBLIOGRAFÍA

Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.

Skiena, S. 2010. The Algorithm Design Manual 2nd ed. Springer.

______. 2009. Búsqueda Informada. Formato HTML. Disponible en: http://www.infor.uva.es/

Alfaro, E. 2011?. ALGORITMOS GENETICOS. Disponible en: http://eddyalfaro.galeon.com/geneticos.html

Dowsland, K y Adenso, B. 2003. Diseño de Heurísticas y Fundamentos del Recocido Simulado. Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial.