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.