I. INTRODUCCIÓN
En los anteriores problemas de búsqueda se encuentran soluciones a un problema generando una secuencia de estados de manera sistemática, en este tipo de búsquedas no tan complejas importaba llegar al objetivo más que cómo llegar, si bien es cierto, las búsquedas informadas son efectivas a la hora de encontrar un resultado, nada asegura que este resultado sea el más factible.
En vista de que existen problemas en los que se deben satisfacer restricciones y llegar al mejor de todos los objetivos, surgen los algoritmos de búsqueda local y problemas de optimización en los cuales el camino hacia la solución del problema es irrelevante y lo que importa es la solución final.
II. OBJETIVO
Aprender la importancia de los algoritmos de búsqueda local y problemas de optimización y entender su funcionamiento y uso en la solución de problemas de agentes.
III. MARCO TEÓRICO
Los algoritmos de búsqueda local no se preocupan por los caminos sino que se enfocan en su gran parte en el estado actual y se mueve de un estado vecino hacia otro, este tipo de algoritmos tienen ventajas importantes como:
Son ahorrativos: Ya que usan poca memoria en donde no se guarda la secuencia de estados.
Razonables: Ofrecen buenas soluciones a un problema cuando el espacio de los estados es infinito.
Óptimos: Encuentran el mejor estado posible en base a una función objetivo.
Existen distintos algoritmos que se preocupan por dar una solución arbitraria a un problema y maximizar el objetivo y minimizar los costos, estos algoritmos nombrados en el gráfico 3.1 serán explicados más adelante.
Gráfico 3.1: Algoritmos de búsqueda local y resolución de problemas con restricciones
La forma en la que funcionan los algoritmos de búsqueda local es intentando mejorar una solución ya dada y encontrar la mejor de las soluciones posibles en el menor tiempo, pero para ello se necesitan de operadores, estos pueden maximizar o minimizar la solución combinando también las restricciones del problema.
¿Cuándo se maximiza?
Se maximiza un problema cuando su solución corresponde directamente al objetivo, es decir que para hacer más óptima una respuesta se trata de maximizar el objetivo.
¿Cuándo se minimiza?
Se minimiza un problema cuando su solución se basa en los costos, por lo cual es necesario hacerlos lo más mínimos posibles.
¿Cuáles son las características de la búsqueda local?
Los elementos o características de la búsqueda local son:
Paisaje de estados: es donde se encuentra el conjunto de soluciones y sirve para comprender mejor la búsqueda local, su posición se basa en el estado y la elevación se basa en la función de coste del objetivo o de la heurística.
Estado inicial: es en donde comienza la búsqueda de la solución.
Operadores: La maximización o minimización, si la solución corresponde al costo entonces se intenta encontrar el mínimo global y si corresponde al objetivo se intenta encontrar el máximo global.
Estados finales y soluciones: Es la resolución del problema en sí.
3.1. PROBLEMAS DE OPTIMIZACIÓN
Para definir un problema de manera correcta primero es necesario tener en claro 4 aspectos indicados y explicados en el siguiente gráfico.
Gráfico 3.2: Problemas de optimización
EJEMPLO:
Una mochila pesa 15 Kg y se necesitan meter distintos elementos a ella, con distintos pesos.
Gráfico 3.3: Ejemplo
3.2.BÚSQUEDA DE ASCENSIÓN DE COLINAS
Es un algoritmo basado en iteraciones que intenta dar una solución arbitraria a un problema para encontrar una mejor solución modificando un elemento incrementalmente (Ceccaroni, 2007).
Este tipo de búsquedas tienen este nombre ya que se asemeja a subir una colina o montaña, es decir que se realiza un búsqueda cuesta arriba y termina cuando alcanza el lugar más alto de la montaña, es decir, la cima.
Este tipo de algoritmos tienen una condición para avanzar la cual es que si el cambio propone una solución factible se realiza un cambio incremental a la nueva solución repitiendo esto varias veces como un ciclo.
Pese a que es un algoritmo simple y muy conocido en inteligencia artificial por ser bueno para encontrar un óptimo local no garantiza encontrar la mejor solución entre el sin número de soluciones posibles.(Ceccaroni, 2007).
3.2.1. TIPOS
Los tipos de algoritmos de búsqueda de ascensión de colinas son 3 y se explican en el gráfico 3.3 :
Gráfico 3.4: Tipo de búsqueda ascensión de colinas
3.3. BÚSQUEDA DE TEMPLE SIMULADO
El algoritmo de temple simulado surge como una alternativa al algoritmo de ascensión de colinas ya que este no es muy completo debido a que solo verifica los caminos cuesta arriba y no pasa por estados bajos donde el costo es más alto y se estanca en máximos locales.
El temple simulado es una combinación de la ascensión de colinas y la aleatoriedad que establezca completitud, esta clase de algoritmos no escogen el mejor movimiento si no que más bien hacen un aleatorio y si este mejora la situación actual entonces es aceptado.
3.4. BÚSQUEDA POR HAZ LOCAL
A diferencia de las otras búsquedas en las cuales los estados expandidos y sus nodos no son guardados en la memoria, la búsqueda por haz local guarda la pista de K estados, y se generan sucesores aleatorios para cada uno de ellos, por lo que se seleccionan cuáles son los mejores sucesores y en caso de ser el objetivo el algoritmo se para (Pérez, s.f).
La gran diferencia con el algoritmo de reinicios aleatorios es que la búsqueda por haz local no es independiente, por ejemplo, un estado generado aleatoriamente puede generar a su vez muchos estados considerados buenos, y otro estado puede generar el mismo número de estados pero malos y solo uno bueno, esto puede indicar claramente que el estado a elegir sería el primero.(Pérez, s.f).
3.4.1. BÚSQUEDA DE HAZ ESTOCÁSTICA
Debido a que podría haber pocos estados, la búsqueda de haz estocástica propone escoger a los sucesores aleatoriamente como una función que haga más y más grande su valor.
3.5. ALGORITMOS GENÉTICOS
Es muy parecida a la búsqueda de haz estocástica con la diferencia de que esta trata de una reproducción sexual más que asexual, es decir que hace una combinación de los estados de los nodos padre para generar un nuevo sucesor o hijo (Ruiz, J. 2015).
II. CONCLUSIÓN
Los algoritmos de búsqueda local y problemas de optimización son una medida de solución arbitraria a un problema, es decir que se trata de maximizar o minimizar un resultado, esto en base a la búsqueda del mejor resultado posible dentro de un espacio de resultados, a travez de un conjunto de restricciones determinados por el tipo de búsqueda local que se realice.
Es clase de algoritmos son muy eficaces en problemas complejos, aplicados al mundo real, como producción y ciertas actividades que requieren precisión y mejora de resultados. Dentro de estos algoritmos, están los mas complejos, que son los algoritmos genéticos, los cuales son muy conocidos pero tienen una utilización compleja.
III. BIBLIOGRAFÍA
Ceccaroni, L. 2007. Inteligencia Artificial Búsqueda local. (En línea). ES. Consultado el 9 de Jun. 2015. Formato PDF. Disponible en: http://www.cs.upc.edu/~luigi/II/IA-2007-fall/2c-Busqueda-local-(es).pdf
Pérez, A. s.f. Búsqueda local. (En línea). ME. Consultado el 9 de Jun. 2015. Formato PDF. Disponible en: http://delta.cs.cinvestav.mx/~adiaz/anadis/LocalSearch.pdf
Ruiz, J. 2015. Búsqueda local y algoritmos genéticos. (En línea). ES. Consultado el 9 de Jun. 2015. Formato PDF. Disponible en: http://www.cs.us.es/cursos/iati/temas/tema-05.pdf
Russell, S y Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. 2 ed. España. Pearson Education. p 1242