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

ESCUELA SUPERIOR POLITÉCNICA AGROPECUARIA DE MANABÍ

MANUEL FÉLIX LÓPEZ

CARRERA INFORMÁTICA

    SEMESTRE  SÉPTIMO           PERIODO  ABR 2015/SEP 2015

TEMA:

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

MATERIA:

INTELIGENCIA ARTIFICIAL II

AUTOR:

CARLOS A. ZAMBRANO VIDAL

FACILITADORA:

ING. HIRAIDA SANTANA

CALCETA,  JULIO 2015

INTRODUCCIÓN

La clase impartida en este día ayudo a despejar muchas dudas ya que notamos que los algoritmos de búsquedas se han diseñado para explorar los espacios de búsquedas esta se consigue manteniendo uno o más caminos en memoria y registrando que alternativas se van explorando en cada punto. También los algoritmos de búsqueda local deciden cual es el mejor camino a escoger o la mejor opción para resolver el problema.

MARCO TEÓRICO

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

Los algoritmos de búsqueda que hemos visto hasta ahora se diseñan para explorar sistemáticamente Espacios de búsqueda. Esta forma sistemática se alcanza manteniendo uno o más caminos en memoria y registrando que alternativas se han explorado en cada punto a lo largo del camino y cuáles no. Cuando se encuentra un objetivo, el camino a ese objetivo también constituye una solución al problema. En muchos problemas.

Aun ninguno de los algoritmos descritos puede manejar espacios de estados continuos, la función sucesor en la mayor parte de casos devuelve infinitamente muchos estados las técnicas de búsqueda local para encontrar soluciones óptimas en espacios continuos.

Un modo de evitar problemas continuos es simplemente discretizar la vecindad de cada estado. Podemos aplicar entonces cualquiera de los algoritmos de búsqueda local descritos anteriormente. Uno puede aplicar también la ascensión de colinas estocástica y el temple simulado directamente, sin discretizar el espacio. Estos algoritmos eligen a los sucesores aleatoriamente, que pueden hacerse por la generación de vectores aleatorios de longitud.

Los métodos locales de búsqueda sufren de máximos locales, crestas, y mesetas tanto en espacios de estados continuos como en espacios discretos. Se pueden utilizar el reinicio aleatorio y el temple simulado y son a menudo provechosos. Los espacios continuos dimensionalmente altos son, sin embargo, lugares grandes en los que es fácil perderse.

Un problema de optimización está restringido si las soluciones debieran satisfacer algunas restricciones sobre los valores de cada variable. La dificultad de los problemas de optimización con restricciones depende de la naturaleza de las restricciones y la función objetivo. La categoría más conocida es la de los problemas de programación lineal en los cuales las restricciones deben ser desigualdades lineales formando una región convexa y la función objetiva es también lineal. Los problemas de programación lineal pueden resolverse en tiempo polinomial en el número de variables. También se han estudiado problemas con tipos diferentes de restricciones y funciones objetivo (programación cuadrática, programación cónica de segundo orden, etcetera).

CONCLUSIÓN

Después de haber analizado esta temática concluimos que estos algoritmos de búsqueda son  simplemente algoritmos de búsquedas se han diseñado para explorar los espacios de búsquedas que se continúan manteniendo uno o más caminos en memoria y registrando que alternativas se van explorando en cada punto. Estos algoritmos son los que deciden cual es la mejor opción para resolver el problema que se quiera solucionar.

BIBLIOGRAFÍA

Ruiz, j. 2012. Algoritmo de búsqueda local. (En línea). Disponible en: http://www.cs.us.es/cursos/ia1/temas/tema-06.pdf

Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.