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.