LÓGICA DIFUSA

Fecha: 30 de Enero del 2014

OBJETIVO DE CLASE E INTRODUCCIÓN

El objetivo de clase era las exposiciones de temas de investigación designadas a mis compañeros y al escritor de esta entrada al blog.

La fuzzy logic fue el tema que desee investigar para compartir con mis compañeros. Uno de los aspectos que más me llamo la atención fue la cantidad de aplicaciones que llego a tener y hablo de ello porque dicha fue aprovechada por primera instancia por los Japonés creo que esa parte les hará llegar a un razonamiento simple relacionado al porque Japón ahora es potencia mundial. El padre de los conjuntos difusos Zadeh matemático ruso hizo su investigación en los años de 1965 llegando así a descubrir inferencias que se acoplaban a nuestra realidad basándose a la lógica de conjuntos convencionales.

MARCO TEÓRICO

DEFINICIÓN

La lógica difusa es una forma de multi-valuada lógica que trata con el razonamiento de que es aproximada y no fijo y exacto. En comparación con los conjuntos binarios tradicionales (donde las variables pueden tomar valores verdaderos o falsos), variables lógicas difusas pueden tener un valor de verdad que va en grados entre 0 y 1. La lógica difusa se ha ampliado para manejar el concepto de verdad parcial, donde la verdad valor puede oscilar entre completamente cierto y completamente falsa(Novák etall. 1999), cuando se utilizan variables lingüísticas, estos títulos pueden ser gestionados por funciones específicas (Ahlawat etall. 2014)

El término «lógica difusa» se introdujo con la propuesta de 1965 de la teoría de conjuntos difusos por( Lotfi & Zadeh. 1965 )La lógica difusa se ha aplicado a muchos campos, desde la teoría de control a la inteligencia artificial. La lógica difusa había, sin embargo, ha estudiado desde los años 1920, como infinito con valores lógica particular (Łukasiewicz & Tarski .2012 )
Ningún sistema busca la verdad absoluta ni la falsedad total
Descripción

La lógica clásica sólo permite proposiciones que tienen un valor de verdad o falsedad. La noción de que 1 + 1 = 2 es una, inmutable, la verdad matemática absoluta. Sin embargo, existen ciertas proposiciones con respuestas variables, como pedir a varias personas para identificar un color. La noción de la verdad no se quedan en el camino, sino un medio de representar y razonar sobre el conocimiento parcial se produjo, mediante la agregación de todos los resultados posibles en un espectro dimensional.

La lógica difusa tiene dos significados diferentes. En un sentido estricto, la lógica difusa es un sistema lógico, que es una extensión de la lógica de varios valores. Sin embargo, en un sentido más amplio, la lógica difusa (FL) es casi sinónimo de la teoría de conjuntos difusos, una teoría que se refiere a las clases de objetos con límites poco definidos en los que el ingreso es una cuestión de grado. En esta perspectiva, la lógica difusa en su sentido estricto es una rama de la FL. Incluso en su definición más estrecha, la lógica difusa se diferencia tanto en concepto como sustancia de sistemas lógicos de varios valores tradicionales.

CONCLUSIÓN

La lógica difusa está a un nivel superior de la lógica convencional, además este tipo de lógica permite resolver problemas complejos debido a su vaguedad a su propiedad de majar todo lo observado como un ente relativo.
En cuanto respecta al porque la lógica difusa es un punto de vista a que algo no es totalmente cierto no totalmente falso se puede consensar que es simple la respuesta ya que la conclusión más está dada a que se basa en moverse de forma continua en la lógica binario.

REFERENCIAS

Novák, V., Perfilieva, I. and Močkoř, J. 1999 Mathematical principles of fuzzy logic Dodrecht: Kluwer Academic. ISBN 0-7923-8595-0

Ahlawat, Nishant, Ashu Gautam, and Nidhi Sharma International Research Publications

House 2014. «Use of Logic Gates to Make Edge Avoider Robot.» International Journal of Information & Computation Technology (Volume 4, Issue 6; page 630) ISSN 0974-2239 (Retrieved 27 April 2014)

Zadeh, L. 1965. «Fuzzy sets». Information and Control 8 (3): 338–353. doi:10.1016/s0019-9958(65)90241-x.

Tsitolovsky, L; Sandler, U. 2008. Neural Cell Behavior and Fuzzy Logic. Springer. ISBN 978-0-387-09542-4.

Matlab. 2012. Logica Difusa. Consultado 30 Enero . Formato HTML. Disponible en: http://www.mathworks.com/help/fuzzy/what-is-fuzzy-logic.html

ALFA – BETA

Fecha: 16  Enero 2015

La clase de la fecha Enero 16 del 15 fue muy intuitiva e interesante, el docente planteo que debíamos hacer un pequeño resumen de  búsquedas entre adversarios  y plantear nuestras  ideas en una diapositiva para compartir información en clases entre compañeros.

Una pequeña introducción al algoritmo que se documentara a continuación es que es la evolución de un método que recorría todo un árbol de juego o árbol binario, este algoritmo se llama min Max.

.

MARCO TEÓRICO

DEFINICIÓN

alfa-beta es un algoritmo de búsqueda que busca reducir el número de nodos que se evalúan por el algoritmo minimax en su árbol de búsqueda. Se trata de un algoritmo de búsqueda de confrontación de uso común para la máquina de juego de juegos de dos jugadores (Tic-tac-toe, Ajedrez, Go, etc.). Deja de evaluar completamente un movimiento cuando se haya encontrado al menos una posibilidad de que demuestra el paso a ser peor que un movimiento ya examinada. Estos movimientos no tienen que ser evaluados más. Cuando se aplica a un árbol min max estándar, devuelve el mismo movimiento como min – max haría, pero ciruelas distancia ramas que no es posible influir en la decisión final. (Russel & Norvig. 2010)

Allen Newell y Herbert A. Simon, que utiliza lo que John McCarthy llama una «aproximación” (McCarthy.2006) en 1958 escribió que «parece que se ha reinventado varias veces» alfa-beta.( Newell & Herbert. 1976)Arthur Samuel tuvo una primera versión y Richards , Hart, Levine y / o Edwards encontraron alfa-beta de forma independiente en los Estados Unidos. (Edwards & Hart. 1963)McCarthy propusieron ideas similares durante la Conferencia de Dartmouth en 1956 y sugirió a un grupo de sus estudiantes, incluyendo Alan Kotok en el MIT en 1961 (Kotok.2014).

Al igual que el procedimiento minimax es un proceso en profundidad, existe el problema de que el número de estados del juego que tiene que examinar es exponencial en el número de movimientos.

Desafortunadamente, no podemos eliminar el exponente, pero en realidad se puede reducir a la mitad. El dispositivo es capaz de calcular la decisión minimax correcta sin tener en cuenta todos los nodos en el árbol de juego. Es decir, mejorar su eficiencia mediante el uso de técnicas de poda, en los que las soluciones parciales claramente peor que las soluciones conocidas pueden ser inmediatamente abandonada. Hay, por tanto, considerar una gran parte del árbol.

Cuando se aplica a un árbol minimax estándar, devuelve el mismo movimiento que el regreso minimax, para podar las ramas que no tienen una posible influencia en la decisión final.

Considerando de nuevo el juego trivial de la Figura 19 como ejemplo de las etapas del cálculo de la decisión de la alfa-beta para el árbol de juego.

La primera hoja B tiene valor 3. En consecuencia, B, que es un nodo Min tiene un valor máximo de 3. La segunda hoja 12 en B tiene un valor, MIN evitar que este movimiento, por lo que B se encuentra todavía en la mayoría de 3. La tercera hoja en B tiene un valor 8, por lo que el valor de B es exactamente 3. Ahora, podemos deducir que el valor de la raíz es por lo menos 3, ya que MAX tiene una opción de valor 3 en la raíz,

CONCLUSIÓN

Poda alfa-beta es un algoritmo que limita la profundidad de búsqueda en juego no estocástico donde se conocen las reglas y se dominan las acciones. La compresión de este algoritmo de búsqueda avanzada lleva a un nivel de compresión alto en cuanto a las matemáticas respectas si deseas aplicarlo debes saberles. La clase fue muy didacta en el aspecto de compartir información entre los compañeros de manera espontánea.

REFERENCIAS

Russel,. S; Norvig, P .2010. Artificial Intelligence: A Modern Approach (3 ed.). Prentice Hall. ISBN 978-0-13-604259-4.

McCarthy, J 2006. «Human Level AI Is Harder Than It Seemed in 1955». Retrieved 2006-12-1

Newell, A & Herbert A. 1976.  «Computer Science as Empirical Inquiry: Symbols and Search» (PDF). Communications of the ACM 19 (3). Retrieved 2006-12-21.

Edwards, D & Hart, T. 1963. «The Alpha–beta Heuristic (AIM-030)». Massachusetts Institute of Technology. Retrieved 2006-12-21.

Kotok, A.  2004. «MIT Artificial Intelligence Memo 41». Retrieved 2006-07-01.

Marsland, T. 1987.  «Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)» (PDF). J. Wiley & Sons. pp. 159–171. Retrieved2006-12-21.

PROLOG

Fecha: 12 de Diciembre del 2014

OBJETIVO DE CLASE E INTRODUCCIÓN

La clase se base en un trabajo de investigación dentro del aula de clase, el objetivo a seguir por parte de los estudiantes era de investigar acerca del lenguaje de programación Prolog con el fin de entender la sintaxis , para que serbia que solucionaba y otras características que eran necesarias saber para entender Prolog .
La metodología aplicada por la docente fue la de realizar después de la investigación un debate de los que habíamos investigado y posterior a ello visualizamos unas diapositivas que la doncete iba a socializar con la clase

MARCO TEÓRICO

DEFINICIÓN

Prolog es un lenguaje de programación lógica de propósito general asociado con la inteligencia artificial y la lingüística computacional(Clocksin & Mellish. 2003)( Bratko. 2001 )( Covington. 1994 ). Prolog tiene sus raíces en la lógica de primer orden, una lógica formal, ya diferencia de muchos otros lenguajes de programación, Prolog es declarativo: la lógica del programa se expresa en términos de relaciones, representada como hechos y reglas. Un cómputo se inicia mediante la ejecución de una consulta sobre estas relaciones (Lloyd. 1984)

El idioma fue concebido por un grupo alrededor de Alain Colmerauer en Marsella, Francia, a principios de 1970 y el primer sistema Prolog fue desarrollado en 1972 por Colmerauer con Philippe Roussel. (Kowalski. 1998)( Colmerauer & Roussel. 1993)

Prolog fue uno de los lenguajes de programación de primera lógica, (Stickel. 1988) y sigue siendo el más popular entre estas lenguas hoy, con muchas implementaciones libres y comerciales disponibles. El lenguaje se ha utilizado para la demostración de teoremas los sistemas expertos ( Merritt. 1989) y otros.
Elementos de un programa PROLOG.
2.1 HECHOS.
Expresan relaciones entre objetos. Supongamos que queremos expresar el hecho de que «un coche tiene ruedas». Este hecho, consta de dos objetos, «coche» y «ruedas», y de una relación llamada «tiene». La forma de representarlo en PROLOG es:
tiene(coche,ruedas).
• Los nombres de objetos y relaciones deben comenzar con una letra minúscula.
• Primero se escribe la relación, y luego los objetos separados por comas y encerrados entre paréntesis.
• Al final de un hecho debe ir un punto (el carácter «.»).

El orden de los objetos dentro de la relación es arbitrario, pero debemos ser coherentes a lo largo de la base de hechos.

2.2. VARIABLES.

Representan objetos que el mismo PROLOG determinará. Una variable puede estar instanciada ó no instanciada. Estará instanciada cuando existe un objeto determinado representado por la variable. De este modo, cuando preguntamos «¿Un coche tiene X?», PROLOG busca en los hechos cosas que tiene un coche y respondería:
X = ruedas.

instanciando la variable X con el objeto ruedas.

• Los nombres de variables comienzan siempre por una letra mayúscula.

Un caso particular es la variable anónima, representada por el carácter subrayado («_»). Es una especie de comodín que utilizaremos en aquellos lugares que debería aparecer una variable, pero no nos interesa darle un nombre concreto ya que no vamos a utilizarla posteriormente.

2.3. REGLAS.

Las reglas se utilizan en PROLOG para significar que un hecho depende de uno ó mas hechos. Son la representación de

las implicaciones lógicas del tipo p —> q (p implica q).

• Una regla consiste en una cabeza y un cuerpo, unidos por el signo «:-«.
• La cabeza está formada por un único hecho.
• El cuerpo puede ser uno ó mas hechos (conjunción de hechos), separados por una coma («,»), que actúa como el «y» lógico.
• Las reglas finalizan con un punto («.»).
CONCLUSIÓN

Prolog es un leguaje de alto nivel que sirve para generar conocimiento y reglas para ese conocimiento.
La forma más eficiente de aprender prolog es practicando contextos de entornos y hechos. La característica más importante de prolog es la pseudo copulación de hechos y reglas.
Las consultas de prolog son las bases de tus preguntas a tus reglas y hechos programados.
Prolog es una potentete herramienta en la inteligencia artificial debido a su programación basada en predicados

REFERENCIAS

Clocksin, F.; Mellish, S. 2003. Programming in Prolog. Berlin ; New York: Springer-Verlag. ISBN 978-3-540-00678-7.

Bratko, I. 2001. Prolog programming for artificial intelligence. Harlow, England ; New York: Addison Wesley. ISBN 0-201-40375-7.

Covington, A. 1994. Natural language processing for Prolog programmers. Englewood Cliffs, N.J.: Prentice Hall. ISBN 978-0-13-629213-5.

Lloyd, J. 1984. Foundations of logic programming. Berlin: Springer-Verlag.ISBN 3-540-13299-6.

Kowalski, R.1988. «The early years of logic programming». Communications of the ACM 31: 38. doi:10.1145/35043.35046.

Colmerauer, A.; Roussel, P. 1993. «The birth of Prolog». ACM SIGPLAN Notices 28 (3): 37. doi:10.1145/155360.155362.

Stickel, M. 1988. «A prolog technology theorem prover: Implementation by an extended prolog compiler». Journal of Automated Reasoning 4 (4): 353–380.doi:10.1007/BF00297245. edit

Merritt, D. 1989. Building expert systems in Prolog. Berlin: Springer-Verlag.ISBN 0-387-97016-9.

ALGORITMOS GENÉTICOS

Fecha:  20  Noviembre  2014

OBJETIVO DE CLASE E INTRODUCCIÓN

El objetivo de la clase era analizar agentes de búsquedas desconocidas. La forma por la cual la docente llego a los estudiantes fue a través de diapositivas con exposición del tema seguidamente se procedía a seguir compartiendo información.

Para entender cómo funciona un algoritmo genético solo vale pensar en Charles Darwin y sus escritos, si desean que sea más explícito puedo argumentar que los algoritmos genéticos están plasmados en lo que conforma nuestra vida real y además comparten el concepto de que si no te adaptas sencillamente desaparece.

MARCO TEORÍCO

Definición

Los Algoritmos Genéticos (AGs) son procesos 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 (Reeves. 1993).  En la naturaleza los individuos de una población compiten entre sí en la búsqueda de recursos tales como comida, agua y refugio (Goldberg. 1989). Incluso los miembros de una misma especie compiten a menudo en la búsqueda  de un compañero. Los Algoritmos Genéticos usan una analogía directa con el comportamiento natural. (Davis, 1991) ( Michalewicz. 1992). Lo curioso era que todo se lleva a cabo a base de interacciones locales entre individuos, y entre estos y lo que les rodea. Los algoritmos genéticos son un logro más de la Inteligencia Artificial en su intento de replicar comportamientos biológicos ( Rodríguez. P)

El poder de los Algoritmos Genéticos proviene del hecho de que se trata de una técnica robusta, y pueden tratar con ´éxito una gran variedad de problemas provenientes de diferentes áreas, ´ incluyendo aquellos en los que otros métodos encuentran dificultades. Si bien no se garantiza que el Algoritmo Gen ético encuentre la solución optima  del problema, existe evidencia empírica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimización combinatoria. En el caso de que existan técnicas especializadas para resolver un determinado problema, lo más probable es que superen al Algoritmo Genético, tanto en rapidez como en eficacia. El gran campo de aplicación de los Algoritmos Genéticos se relaciona con aquellos problemas para los cuales no existen técnicas especializadas. Incluso en el caso en que dichas técnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas hibridándolas con los Algoritmos Genéticos.

Algoritmo genetivo simple

Codificación

Se presume que los individuos (posibles recursos del problema), pueden simbolizar como un conjunto de parámetros (que denominaremos genes), los cuales agrupados forman una arista de valores (a menudo referida como cromosoma). Si bien el alfabeto utilizado para representar los individuos no debe necesariamente estar constituido por el {0, 1}  (Jong. 1975)

 

Función Objetivo

Idealmente nos interesaría construir funciones objetivo con “ciertas regularidades”, es decir funciones objetivo que verifiquen que para dos individuos que se encuentren cercanos en el espacio de búsqueda,  sus respectivos valores en las funciones objetivo sean similares. ( Goldberg & Richardson 1987)

 

Ejemplo

Como ilustración de los diferentes componentes del Algoritmo Genético Simple, supongamos el problema – adaptado de  (Goldberg. 1989) – de encontrar el máximo de la función f(x) = x^2 sobre los enteros {1, 2, . . . , 32}. Evidentemente para lograr dicho optimo,  bastaría actuar por búsqueda  exhaustiva, dada la baja carnalidad del espacio de búsqueda.

 

CONCLUSIONES

En conclusión los algoritmos genéticos se basan en la construcción de nuevas reglas que se consideran  como  un ser vivo que comparte rasgos con los seres vivos progenitores. En cuanto respecta a la clase impartida se cumplió el objetivo definido.

En fin un AG es el medio más rápido para optimizar funciones matemáticas o cualquier tipo de problema que no tenga bien definido su modelo matemático.

REFERENCIAS

Reeves, C. 1993. Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publications. ISBN:0-470-22079-1

Goldberg, D. 1989. Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA. ISBN:0201157675

Davis, L.1991. Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York. ISBN-13

Michalewicz, Z. 1992. Genetic Algorithms + Data Structures = Evolution Programs, SpringerVerlag, Berlin Heidelberg. ISBN 3-540-60676-9

De Jong, K. 1975. An analysis of the behaviour of a class of genetic adaptive systems. Tesis doctoral, University of Michigan  ISBN 84-2913-49-8-4

Goldberg, D,; Richardson, D. 1987). Genetic algorithms with sharing for multimodal function optimization. Genetic Algorithms and their Applications: Proceedings of the Second International Conference on Genetic Algorithms and Their Applications, 41-49

ALGORITMO DE ASCENSIÓN EN COLINA

Fecha: 7  Noviembre  2014

OBJETIVO DE CLASE E INTRODUCCIÓN

La clase de la fecha mencionada anteriormente estaba basada en el análisis de un grupo de algoritmos que resolvían problemas basándose en un objetivo.

EL algoritmo que se mencionara a continuación no tuvo ningún interés en clase  pero en lo personal parce interesante debido a que se base en una nueva forma de iterar con opciones arbitrarios.  El objetivo de la clase era socializar a las búsquedas informadas o búsquedas basadas en objetivos. La idea principal de estos algoritmos realizar en una asunción optima los problemas convexos.

MARCO TEÓRICO

DEFINICIÓN

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).

COMPLEJIDAD COMPUTACIONAL

Dado que la evaluación que se utiliza sólo se fija en el estado actual, en escalada no sufre de problemas de espacio computacionales. La fuente de su complejidad computacional surge del tiempo necesario para explorar el espacio del problema. Aleatorio-reinicio de escalada puede llegar a soluciones óptimas polinómica para la mayoría de los espacios de problemas. Sin embargo, para algunos problemas NP-completos, el número de máximos locales pueden ser la causa de tiempo computacional exponencial. Para hacer frente a estos problemas, algunos investigadores han examinado el uso de la teoría de probabilidad y muestreo local para dirigir el reinicio de algoritmos bajadas. (Cohen, Greiner, y Schuurmans, 1994).

 

APLICACIONES

Colina de escalada puede aplicarse a cualquier problema donde el estado actual permite una función de evaluación precisa. Por ejemplo, el problema del viajante de comercio, el problema de ocho reinas, diseño de circuitos, y una variedad de otros problemas del mundo real. Colina Escalada se ha utilizado en los modelos de aprendizaje inductivo. Un ejemplo es PALO, un sistema de subida de pendientes probabilístico que los modelos inductivos y el aprendizaje de aceleración. Algunas aplicaciones de este sistema han sido encajar en «sistemas de aprendizaje basados en la explicación», y modelos de análisis de «utilidad». (Cohen, Greiner, y Schuurmans, 1994). Colina Escalada también se ha utilizado en la robótica para gestionar los equipos de múltiples robots. Un ejemplo es el algoritmo de Parish, que permite la coordinación escalable y eficiente en sistemas multi-robot. El grupo de investigadores diseñó «un equipo de robots que deben coordinar sus acciones con el fin de garantizar la ubicación de un evasor de expertos.» (Gerkey, Thrun, y Gordon, 2005).

 

Su algoritmo permite robots para elegir si trabajar solo o en equipo mediante el uso de escalada. Robots ejecutoras Parroquia están, por tanto, «colectivamente bajadas de acuerdo con gradientes de progreso local, pero estocásticamente hacer movimientos laterales o hacia abajo para ayudar al escape del sistema de máximos locales.» (Gerkey, Thrun, y Gordon. 2005)

 

CONCLUSIÓN

En cuanto respecta al objetivo de la docente hacia  los alumnos puedo concluir que todo siguió su orden y las presentaciones de Power Point  cumplieron su objetivo. El algoritmo de ascenso por colinas aplica en muchos campos de las matemáticas y la inteligencia artificial. Uno de los principales problemas de ese algoritmo es la restauración de su funcionamiento.

Se puede utilizar para analizar y actuar en ambientes estocásticos.

REFERENCIAS

Skiena, S. 2010. The Algorithm Design Manual 2nd ed. Springer Science+Business Media ISBN 1-849-96720-2″>1-849-96720-2

Russell, S. J., & Norvig, P. 2004. Inteligencia Artificial, Un époque practico . Upper Saddle River, NJ: Prentice Hall.

Cohen, W., Greiner, R., Schuurmans, D. 1994. Probabilistic Hill-Climbing. Computational Learning Theory and Natural Learning Systems, Vol. II. Edited by Hanson, S., Petsche, T., Rivest R., Kearns M. MITCogNet, Boston:1994.

Gerkey, B; Thrun, S., Gordon, G. 2005. Parallel Stochastic Hillclimbing with Small Teams. Multi-Robot Systems: From Swarms to Intelligent Automata, Volume III, 65–77.

 

BÚSQUEDA BIDIRECCIONAL

Fecha: 16 Octubre 2014

OBJETIVO DE CLASE E INTRODUCCIÓN 

La clase impartida la fecha mencionada anteriormente estaba basada en exposiciones por parte de mis compañeros, la búsqueda bidireccional era una pequeña parte que estaba compartiendo un compañero. Esta entrada al blog se basara en Ampliar un poco más el concepto teórico y práctico  de la búsqueda bidireccional.

MARCO TEÓRICO

• DEFINICIÓN

Buscar bidireccionalmente, es  como su nombre lo indica, búsquedas en dos direcciones al mismo tiempo: uno hacia adelante desde el estado inicial y el otro hacia atrás de la parte final. Esto se hace generalmente mediante la expansión de árbol con factor de ramificación b y la distancia desde el principio hasta el objetivo es d. La búsqueda se detiene cuando búsquedas desde ambas direcciones se reúnen en el centro. Búsqueda bidireccional es un algoritmo de búsqueda de fuerza bruta que requiera un estado objetivo explícito en lugar de simplemente una prueba para una condición meta (Robin. 2009)

La idea de una búsqueda bidireccional es reducir el tiempo de búsqueda mediante la búsqueda hacia adelante desde el comienzo y hacia atrás de la estancia simultáneamente. Cuando las dos fronteras de búsqueda se cruzan, el algoritmo puede reconstruir un único camino que se extiende desde el estado de inicio a través de la intersección de frontera a la meta. (Poole. 2010 ) . Una técnica que ha demostrado ser útil en el camino más corto y otra discreta cálculos de optimización ha sido la búsqueda bidireccional. El método tiene  sido bien probado en el de dos nodos problema del camino más corto proporciona sustancial  ahorros computacionales. Un impulso natural es extender sus beneficios a heurística búsqueda (Thomas. sf )

• ENFOQUES PARA BÚSQUEDA BIDIRECCIONAL

Algoritmos bidireccionales pueden ser ampliamente divididas en tres categorías: Front-to-Front, Front-to-Back (o Front-to-End), y Perímetro de la búsqueda (Kaindl Kainz 1997). Estos se diferencian por la función utilizada para calcular la heurística.

Front-to-Back

Algoritmos de adelante hacia atrás calculan el valor h de un nodo n utilizando la estimación heurística entre n y la raíz de lo contrario árbol de búsqueda. Front-to-Back es el investigado más activamente de las tres categorías. La corriente mejor algoritmo (al menos en el dominio Quince rompecabezas) es la Bimax-BS * F algoritmo, creado por Auer y Kaindl (Auer, Kaindl 2004).

Front-to-Front

Algoritmos de frente a frente calculan el valor h de un nodo n utilizando la estimación heurística entre n y algún subconjunto de OPEN_d ‘. El ejemplo canónico es el de la (algoritmo bidireccional heurístico Front-a-Front)  BHFFA  (de Champeaux 1977/1983), donde la función h se define como el mínimo de todas las estimaciones heurísticas entre el nodo actual y los nodos en la parte frontal opuesta. O bien, formalmente:

Donde H (n, o) devuelve un (es decir, no sobrestimar) estimación heurística admisible de la distancia entre los nodos n y o. Frente-a-Frente sufre de ser excesivamente exigentes computacionalmente. Cada vez que un nodo n se pone en la lista abierta, se debe calcular su valor f = g + h. Esto implica calcular una estimación heurística de N a cada nodo de lo opuesto al  conjunto abierto, como se describió anteriormente. Los conjuntos abiertos aumentan de tamaño de forma exponencial para todos los dominios con b> 1

• EJEMPLO DE UNA BÚSQUEDA BIDIRECCIONAL CON EL ALGORITMO DE DIJSKTRA

Algoritmo de Dijkstra, concebida por el informático Edsger Dijkstra en 1956 y publicado en 1959, es un algoritmo de búsqueda gráfica que resuelve la sola fuente problema del camino más corto para un gráfico con costes de ruta borde no negativos, produciendo una menor árbol de ruta. Este algoritmo se utiliza a menudo en el enrutamiento y como una subrutina en otros algoritmos de grafos.

A continuación Existe un video que explica la aplicación de una búsqueda bidereccional aplicada en el algoritmo de Dijkstra

  CONCLUSIÓN

Una búsqueda bidireccional está basado en el criterio exhaustivo de búsqueda, es decir busca su meta en dos direcciones basándose en el concepto de fuerza bruta para llegar a su objetivo.  Este algoritmo de búsqueda es muy investigado para encontrar la ruta más corta, algunos aspectos negativos está en los costes que genera en enrutamiento en sus grafos, pero eso es relativo a la velocidad que aplica para llegar a su meta.

BIBLIOGRAFÍAS 

Robin,  D.2010.  Búsqueda Bidireccional .Consultado 10 de Oct .(En línea).Formato HTML. Disponible en : http://intelligence.worldofcomputing.net/ai-search/bidirectional-search.html#.VKgbgiuG8po

Poole,  D.2010.  Búsqueda Bidireccional .Consultado 10 de Oct .(En línea).Formato HTML. Disponible en : http://artint.info/html/ArtInt_65.html

Thomas,  J. sf .  Búsqueda Bidireccional .Consultado 10 de Oct .(En línea).Formato PDF. Disponible en : http://aitopics.org/sites/default/files/classic/Machine%20Intelligence%206/MI6-Ch9-Pohl.pdf

Kaindl, H. .  networks 2004: 11th International Telecommunications Network Strategy and Planning Symposium, VDE Verlag, 2004, p. 464.

BÚSQUEDA DE COSTO UNIFORME

INTRODUCCIÓN Y OBJETIVO DE LA CLASE

 

Fecha: 16  Octubre 2014

 

El objetivo de la clase fue socializar búsquedas heurísticas. Tres en específico, y una de las cuales más llamo la atención a mí como estudiante fue la de la búsqueda de costo uniforme,   este algoritmo lo elegí como entrada para este blog porque era el más óptimo  según el proceso de socialización de la clase que se  basó en exposiciones y un análisis de fondo por parte de la docente.

Una pequeña explicación de la búsqueda de costo uniforme es aclara que este algoritmo de inteligencia artificial analiza los nodos del árbol o grafo de forma transversal.

MARCO TEÓRICO

DEFINICIÓN

En informática, la búsqueda de costo uniforme (UCS) es un algoritmo de búsqueda árbol utilizado para el desplazamiento o la búsqueda de un árbol ponderado, estructura de árbol, o un grafo. La búsqueda comienza en el nodo raíz. La búsqueda, continúa visitando el siguiente nodo que tiene el menor costo total de la raíz. Los nodos son visitados de esta manera hasta que se alcanza un estado objetivo (Norving & Russel. 2010).

Búsquedas coste uniformes siempre expanden el nodo con el coste de la ruta total más bajo desde el nodo inicial. Por lo tanto, siempre son óptimas (como ya se ha encontrado ninguna solución más barata sería.) Su característica sobresaliente es el hecho de que empiezan desde el nodo de partida inicial en el que calculan el coste de la ruta en la búsqueda(Sirota, etall. 2003) . La idea del algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices, enumerando todos los nodos del espacio de estados por costes (valores de g) crecientes; cuando se obtiene el camino más corto desde el vértice origen, a la estación destino objetivo de la búsqueda, el algoritmo se detiene (Rihawi. 2009).  Se basa en desarrollar el nodo con el menor costo

ALGORITMO

Sea T = (V, E) un árbol con bordes ponderados y sea w (p) sea el peso de la trayectoria p en T. Por conveniencia, sea r la raíz del árbol y t (p) denota el vértice final un camino p en T. [1]. Con esto dicho, vamos K, el conjunto de rutas conocidas que comienzan con r, ser \ {(r) \}. Cabe señalar que el peso de (r) es cero.

Si existe en K p tal que p minimiza w (p) y T (p) es un estado objetivo de T, es decir, una hoja, se detiene. p es el camino de costo mínimo para la meta.

De lo contrario, identificar p K en donde p minimiza w (p) y ampliar t (p). En otras palabras, añadir a K todos los caminos formados mediante la adición de uno de los vértices del niño t (p) (en su caso) a p. Retire p de K; se considera ‘visitado’, y el fracaso para quitar puede resultar en la no terminación de la búsqueda.

Repita primer paso.

CONCLUSIÓN

Las búsquedas UCS o búsquedas de costo uniforme trabaja con árboles y grafos binarios, su principal características es asignarle un costo a su recorrido expandiendo los nodos que son visitados. Este algoritmo está estrechamente relacionado a la búsqueda primero por anchura pero se diferencia porque este tiene un coste total que basa y traza sus decisiones.

Las aplicaciones en la vida real de este algoritmo se realizan en problemas pequeños debido a que existen mejores algoritmos para problemas complejos que tienen el mismo concepto de la búsqueda de costo uniforme pero con una característica adicional que lo hace mejor. Desde mi punto de vista el pasar del tiempo mejora las soluciones algorítmicas de búsqueda para las matemáticas o inteligencia artificial.

REFERENCIAS

Russel,. S; Norvig, P (2010). Artificial Intelligence: A Modern Approach (3 ed.). Prentice Hall. ISBN 978-0-13-604259-4.

Mayefsky, E; Anene, F; Sirota, M .2003.  Búsqueda de costo uniforme .Consultado 10 de Oct .(En línea).Formato HTML. Disponible en : http://web.stanford.edu/~msirota/soco/best.html.

Rihawi, I .2009.  Búsqueda de costo uniforme .Consultado 10 de Oct .(En línea).Formato HTML. Disponible en : https://poiritem.wordpress.com/2009/12/06/6-5-1-busqueda-no-informada-algoritmo-de-coste-uniforme/

Agrawal, A .2012.  ARTIFICIAL INTELLIGENCE – UNIFORM COST SEARCH .Consultado 10 de Oct .(En línea).Formato HTML. Disponible en : https://algorithmicthoughts.wordpress.com/2012/12/15/artificial-intelligence-uniform-cost-searchucs/

 

HEURÍSTICA

Calceta 9 de Octubre del 2014

INTRODUCCIÓN

Las clases comenzaron por una lectura y análisis de búsquedas, las primeras en ser mencionadas y más a conocidas fueron la búsqueda por anchura y profundidad. En resumen se trató un tema llamado como Heurística que definiremos a continuación.

La metodología aplicada el día de clase fue  análisis de compresión lectora que asume la idea de compartir contenido obtenido del libro de trabajo  los compañeros presentes. Se analizó también un slider y se resolvió un puzle de 3*3.

MARCO TEÓRICO

En informática, la inteligencia artificial, y la optimización matemática diseño  una técnica diseñada para resolver un problema más rápidamente cuando los métodos clásicos son demasiado lentos llamada Heurística, o para encontrar una solución aproximada cuando los métodos clásicos no encuentran ninguna solución exacta. (Dechter. 1985).

Una de las aplicaciones más conocidas es el Best-First Search ; este y sus variantes más avanzadas se han utilizado en aplicaciones tales como juegos y rastreadores web. En un rastreador web, cada página web es tratada  como un nodo, y todos los hipervínculos en la página son tratados como nodos sucesores no visitados. Un rastreador que utiliza mejor primera búsqueda generalmente utiliza una función de evaluación que asigna prioridad a los vínculos en función de cómo de cerca el contenido de la página padre se asemejan a la consulta de búsqueda (Menczer, Pant, Ruiz, y Srinivasan, 2001). En los juegos, mejor primera búsqueda se puede usar como un algoritmo de ruta de investigación para los personajes del juego. Por ejemplo, podría ser utilizado por un agente enemigo para encontrar la ubicación del jugador en el mundo del juego. Algunos juegos dividen el terreno en «azulejos» que pueden o bien ser bloqueados o no bloqueados. En tales casos, el algoritmo de búsqueda trata cada azulejo como un nodo, con los vecinos azulejos bloqueados son nodos sucesores, y el nodo objetivo siendo la baldosa de destino (Koenig, 2004).

BUSQUEDA POR ANCHURA

En la teoría de grafos, búsqueda por amplitud  (BFS) es una estrategia para la búsqueda en un grafo  cuando la búsqueda se limita esencialmente a dos operaciones: (a) la visita e inspección de un nodo de un gráfico; (b) tener acceso a visitar los nodos que los vecinos del nodo actualmente visitado. El BFS comienza en un nodo raíz e inspecciona todos los nodos vecinos. Entonces, para cada uno de esos nodos vecinos, a su vez, se inspecciona sus nodos vecinos, que eran no visitado, y así sucesivamente.

BFS se inventó a finales del 1950 por EF Moore y en un principio utilizado para encontrar el camino más corto para salir de un laberinto (Skiena. 2008).

En el análisis de algoritmos, la búsqueda por amplitud  se supone que se lo realiza en un grafo finito, representado explícitamente como una lista de adyacencia o representación similar. Sin embargo, en la aplicación de métodos gráfico de recorrido de la inteligencia artificial en la entrada puede ser una representación implícita de un grafo  infinito. En este contexto, un método de búsqueda se describe como completa si está garantizado para encontrar un estado final, si existiera. Búsqueda en amplitud es completa, pero la búsqueda en profundidad no es: cuando se aplica a los gráficos infinitos  representados implícitamente, puede perderse en algunas partes de la gráfica que no tienen ningún estado de la meta y nunca regresan (Coppin. 2004)

BÚSQUEDA POR PROFUNDIDAD

La búsqueda en profundidad (DFS) es un algoritmo para el desplazamiento o la búsqueda de árboles o estructuras de datos del gráfico. Uno comienza en la raíz (seleccionar algún nodo arbitrario como la raíz en el caso de un gráfico) y explora la medida de lo posible a lo largo de cada rama antes de dar marcha atrás.

Una versión de búsqueda en profundidad se investigó en el siglo 19 por el matemático francés Pierre Charles Tremaux (Public conference. 2010) como una estrategia para resolver laberintos (Even. 2011), (Sedgewick. 2002)

 

CONCLUSIÓN

Las búsquedas que se utilizan en la IA se  tienen que ser necesariamente óptima debido al objetivo que se quieren conseguir, dado que la inteligencia artificial  trata de  mejorar técnicas de Heurística definidas,  para hacer de esta rama un aporte importante de la ciencia.

Existen varios tipos de búsqueda pero en este blog solo analizamos las dos primeras y más conocidas de las cuales se desprenden un sinnúmero de ramas.  La búsqueda por anchura implica analizar un grafo de forma horizontal y por profundidad de forma vertical  no se pude definir cuál es el óptimo porque eso estaría relacionado a la complejidad del problema a resolver.

BIBLIOGRAFÍA

Dechter, R. & Pearl, J. 1985 . Generalized Best-First Search Strategies and the Optimality of A*. Journal of the Association for Computing Machinery, 32, 505-536.

Menczer, F., Pant, G., Ruiz, M.E. & Srinivasan, P.  2001. Evaluating Topic-Driven Web Crawlers. Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval (pp. 241-249). New York: Association for Computing Machinery.

Koenig, S. 2004 . A Comparison of Fast Search Methods for Real-Time Situated Agents. Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems – Volume 2 (pp. 862-871). Washington, DC: IEEE Computer Society.

Skiena, S .  2008. The Algorithm Design Manual. Springer. p. 480

Coppin, B. 2004. Artificial intelligence illuminated. Jones & Bartlett Learning. pp. 79–80.

Charles Pierre Trémaux (1859–1882) École Polytechnique of Paris (X:1876), French engineer of the telegraph

Public conference, December 2, 2010 – by professor Jean Pelletier-Thibert in Académie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – ISSN: 0980-6032)

Even, S . 2011 , Graph Algorithms (2nd ed.), Cambridge University Press, pp. 46–48, ISBN 978-0-521-73653-4.

Sedgewick, R. 2002, Algorithms in C++: Graph Algorithms (3rd ed.), Pearson Education, ISBN 978-0-201-36118-6.

ALGORITMO A ESTRELLA

Fecha: 7  Noviembre  2014

OBJETIVO DE CLASE E INTRODUCCIÓN

El objetivo de la clase era que los alumnos compartan temas de exposición designada a cada uno de ellos. Además antes de iniciar con las clases la docente compartió un avance del contenido que ha futuro se iba a socializar.

Una pequeña introducción de que es el algoritmo de A* podría se argumentar que este tipo de algoritmo es uno de los más utilizados para trazar rutas de un lugar a otro. Por otro lado los sistemas de viajes en la vida real son los más beneficiados gracias a A * estrella.  Además A* se basa en la mejora de características que   de algoritmos creados anterior a este

 

MARCO TEÓRICO

DEFINICIÓN

En ciencias de la computación, A * (pronunciado «Una estrella» (escuchar)) es un algoritmo informático que se utiliza ampliamente en la búsqueda de caminos y el gráfico de recorrido, el proceso de planear una ruta eficiente transitable entre puntos, llamados nodos. Destaca por su rendimiento y precisión, goza de amplio uso. Sin embargo, en los sistemas con los viajes de enrutamiento prácticos, se superó en general por medio de algoritmos que pueden pre-proceso de la gráfica para lograr un mejor rendimiento, (Delling etall. 2009)aunque otros trabajos ha encontrado A * sea superior a otros enfoques(Zeng & Church. 2014)

Peter Hart, Nils Nilsson y Bertram Raphael del Instituto de Investigación de Stanford (ahora SRI International) describieron por primera vez el algoritmo en 1968(Hart, etall. 1968). Se trata de una extensión de 1959 el algoritmo de Edsger Dijkstra. A * logra un mejor rendimiento tiempo usando heurística

 

A * es como el algoritmo de Dijkstra en que se puede utilizar para encontrar un camino más corto. A * es como Greedy Best-First-Búsqueda en que puede utilizar una heurística para guiar a sí mismo. En el caso simple, es tan rápido como Greedy Best-First-Buscar:

 

A * algoritmo de búsqueda

 

La heurística de búsqueda hace uso del hecho de que la mayoría de los espacios de problemas proporcionan alguna información que distingue entre los estados en términos de la probabilidad de que conduce a una meta. Esta información se llama una función de evaluación heurística (Pearl & Korf, 1987). En otras palabras, el objetivo de una búsqueda heurística es reducir el número de nodos buscado en la búsqueda de un objetivo (Kopec y Marsland, 2001).

 

Mejor forma primera búsqueda más utilizado se llama A *, que se pronuncia como una estrella. Se trata de un método de búsqueda heurística, y se utiliza para minimizar el costo de búsqueda en un problema dado (BOLC y Cytowski, 1992). Su objetivo es encontrar la ruta de menor costo desde un nodo inicial dado a la meta específica. Es una forma extendida de primero el mejor algoritmo de búsqueda. Mejor algoritmo de primera búsqueda trata de encontrar una solución para reducir al mínimo el coste total de la ruta de búsqueda, también. Sin embargo, la diferencia de Best-First Search es que A * también tiene en cuenta el costo desde el principio, y no simplemente el costo local del nodo sido anteriormente. Lo mejor primera búsqueda encuentra un estado objetivo en cualquier espacio del problema predeterminado. Sin embargo, no puede garantizar que va a elegir el camino más corto hacia la meta (Pearl & Korf, 1987). Por ejemplo, si hay dos opciones para elegir, uno de los cuales es un largo camino desde el punto inicial, pero tiene una estimación ligeramente más corto de la distancia a la meta, y otro que está muy cerca de su estado inicial, pero tiene un poco más largo estimación de la distancia al objetivo, primero el mejor búsqueda siempre optar por ampliar siguiente el estado con la estimación más corto. El algoritmo A * soluciona este inconveniente particular, la mejor primera de búsqueda (Pearl & Korf, 1987).

En resumen, un algoritmo * busca en todas las rutas posibles desde el punto de partida hasta que encuentra el camino más corto o más barato a un objetivo. Los términos como camino más corto, el más barato el costo aquí se refiere a una noción general. Podría ser algún otro término alternativo dependiendo del problema. Por ejemplo, en un problema mapa el costo se sustituye por la distancia plazo (Cawsey, 1998). Esto puede reducir la necesidad de buscar todas las posibles vías en un espacio de búsqueda, y el resultado en solución más rápida. A * evalúa mediante la combinación de los nodos g (n) y h (n). En la terminología estándar que se utiliza cuando se habla de A *:

CONCLUSIÓN

Según lo analizado anteriormente se puede concluir que A* está catalogado con unos de los mejores algoritmos de búsquedas en grafos o arboles binarios, debido a su forma de como maneja sus costes. Por otro lado la retroalimentación de la docente es un plus muy importante para hacer que los conocimientos adquiridos permanezcan vigentes.

A estrella es la mejora de algoritmos que estaban antes de que este algoritmo haya existido.

 REFERENCIAS

Delling, D; Sanders, P; Schultes, D; Wagner, D. 2009.  «Engineering route planning algorithms». Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation. Springer.  volume 5515

Zeng, W; Church,  L. 2009. «Finding shortest paths on real road networks: the case for A*». International Journal of Geographical Information Science.  Volume 23

Hart, P; Nilsson, N; Raphael, B. 1968.  «A Formal Basis for the Heuristic Determination of Minimum Cost Paths». IEEE Transactions on Systems Science and Cybernetics. Vol 4

Bolc, L; & Cytowski, J. 1992. Search Methods for Artificial Intelligence. London: Academic Press.

Cawsey, A. (1998). The Essence of Artificial Intelligence. Upper Saddle River, NJ: Prentice Hall. ISBN:0135717795

Kopec, D. & Marsland, T.A. 2001. Search. Retrieved October 10 2008, Formato PDF. Disponible en: http://www.cs.ualberta.ca/~tony/RecentPapers/Draft.5.2.pdf

Pearl, J. & Korf, R. 1987. Search techniques. Annual Review of Computer Science, 451-467. Vol 3

Russell, S. J., & Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Upper Saddle River, NJ: Prentice Hall. ISBN:0136042597