• Author / Uploaded
• Stephanie Conforme

Citation preview

INTRODUCCIÓN Los diferentes métodos de búsquedas que se ha mencionado en los otros capítulos han sido de mucha ayuda para encontrar soluciones a un problema determinado, los técnicas de búsquedas son encontradas día a día, y hasta en momentos existen un cien número de estas técnicas, entre ellas está la búsqueda local. Pero que es la búsqueda local, cuál es su significado, la metodología que utiliza, estos y otros temas se mencionaran a continuación.

MARCO TEORICO 2.1.

BÚSQUEDA LOCAL

La idea básica de los algoritmos de búsqueda local (BL) es que inicia con una solución inicial, es decir; es generada aleatoriamente, y halla con algún otro algoritmo, si este no es factible. Aplica la solución actual una transformación de algún conjunto para mejorar la solución. Repite lo anterior hasta que ninguna transformación del conjunto mejore la solución actual, va escalando soluciones, comparando sus vecinos. Los métodos usados en BL son conocidos como meta heurísticas u optimización local.

Figura. 1. Búsqueda de Colinas

La búsqueda local estudia otros sub-búsquedas que son:

Búsqueda de ascensión de colinas

Enfriamiento simulado.

Algoritmos genéticos

2.1.1. ASCENSIÓN DE COLINAS En la búsqueda de ascensión de colinas es también reconocida como escalada por lo que se mencionó en el punto 2.1. Estas búsquedas se sub divide en ascensión simple y de máxima pendiente. 2.1.1.1.

ASCENSIÓN SIMPLE

Se busca cualquier operación que suponga una mejora respecto al padre, es decir, busca una mejora respecto al estado actual. Ejemplo: “Como subir al Everest con una niebla espesa y amnesia”

Figura. 2. Colinas Simples

2.1.1.2.

ASCENSIÓN MÁXIMA PENDIENTE

Se selecciona el mejor movimiento (no el primero de ellos) que suponga mejora respecto al estado actual. Ejemplo: “Como subir al Everest con una niebla espesa y amnesia”

Figura. 3. Ascensión Máxima Pendiente

Observaciones de ejemplo. El proceso se repite hasta que se encuentre una solución, hasta no podamos avanzar más o hasta que todos los hijos sean peores que el padre del que provienen. 2.1.1.3.

ASCENSIÓN DE COLINAS - CARACTERISTICAS

Las características de la función heurística determinan la calidad del resultado y la rapidez de la búsqueda, de las cuales son: 

Máximo local. Todos los vecinos tienen función heurística peor.



Meseta. Todos los vecinos tienen la misma función heurística que el nodo actual.



Crestas: Las crestas causan una secuencia de máximos locales que hace muy difícil la navegación para los algoritmos avaros.

2.1.1.4.

ASCENSIÓN DE COLINAS - PROCESO

Vuelve a un nodo anterior y seguir el proceso en otra dirección, reinicia la búsqueda en otro punto, aplica dos o más operadores antes de decidir el camino.

Figura. 4. Ascensión De Colinas

2.1.2. ENFRIAMIENTO SIMULADO Este algoritmo se basa en la ascensión de colinas estocásticas inspirada en el proceso de enfriamiento de metales, La idea básica es escapar de los máximos local permitiendo movimientos malos, Gradualmente, tales movimientos decrecen en tamaño y frecuencia.

2.1.2.1.

ELEMENTOS DEL ENFRIAMIENTO SIMULADO

Se debe identificar los elementos de esta búsqueda que son: 

Temperatura: parámetro de control



Energía: Calidad de la solución f(n)



Función de aceptación: permite decidir si escoger un nodo sucesor.



Estrategia de enfriamiento: números de iteraciones a realizar.

2.1.2.2.

PROCESO DE ENFRIAMIENTO SIMULADO

El proceso de enfriamiento simulado es: 

Elegimos un sucesor de entre todos los posibles según una distribución de probabilidad.



El sucesor puede ser peor.



Se hacen pasos aleatorios por el espacio de soluciones

Busca la temperatura más baja

2.1.3. ALGORITMOS GENÉTICOS Son una variante de la búsqueda de haz estocástica en que se combinan dos estados padres. La Analogía entre búsqueda local y evolución por selección natural: 

Los estados corresponden a individuos



Una función de idoneidad mide la calidad de los estados.



Combinando buenos estados se obtiene estados mejores.

Ejemplo del Problema de N Reinas. La función de evaluación es número de parejas de reinas que no se atacan. Operador de cruce.

Figura. 5. Problema de N Reinas.

Proceso de ejecución 1. Se escogen N individuos de la población actual para la población intermedia. 2. Se emparejan los individuos y para cada pareja 3. Estos individuos forman la nueva población.

CONCLUSIÓN Los algoritmos de búsqueda local nos permiten examinar una mejor solución a un problema dado, mediante ascensión de colinas, que trata de buscar cuál es su sucesor factible; el enfriamiento simulado, que es quien mediante temperatura analiza las iteraciones que se generan del problema; Algoritmo genéticos, este último utiliza la termología de la vida y la mutación para localizar y encontrar una salida factible. Todas las antes mencionado, son muy importante porque nos permiten encontrar una mejor solución, cabe recalcar que no son los únicos métodos de búsqueda.

BIBLIOGRAFÍA Ceccaroni, L. 2013, Inteligencia Artificial, Búsqueda Local. (En Línea). Consultado, 12 de jun. 2015. Formato PDF. Disponible en: http://www.cs.upc.edu/~luigi/II/IA-2007-fall/2c-Busqueda-local-(es).pdf Díaz, A. s.f. Búsqueda local. MEX. (En Línea). Consultado, 12 de jun. 2015. Formato PDF. Disponible en: http://delta.cs.cinvestav.mx/~adiaz/anadis/LocalSearch.pdf Béjar, J. 2013. Búsqueda local. Cataluña, ESP. (En línea). Consultado, 12 de jun. 2015. Formato PDF. Disponible en: http://www.cs.upc.edu/~bejar/ia/transpas/teoria/2-BH3Busqueda_local.pdf Berzal, F. s.f. Búsqueda Local. ESP. (En Línea). Consultado, 12 de jun. 2015. Formato PDF. Disponible en: http://elvex.ugr.es/decsai/iaio/slides/A7%20Local%20Search.pdf Russell, S y Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. 2 ed. España. Pearson Education. 124. ISBN 978-84-205-4003-0