Fecha de Clase: 8 - 12 de Junio 2015
INTRODUCCIÓN
INTRODUCCIÓN
En esta clase se hizo referencia a la búsqueda local en espacios
continuos, conociendo con anterioridad la diferencia entre espacios discretos y continuos. Puesto que
los espacios continuos son los que más se asemejan a la realidad que se
presentan en el mundo real. Es por esto que el estudio de los espacios
continuos se hace cada vez más importante para encontrar soluciones a problemas
que se presentan en estos entornos a través de técnicas y búsquedas. Cabe
recalcar que este tipo de búsqueda, se realiza a cualquier acontecimiento que
trate del mundo real, para dar soluciones óptimas. Son los más utilizados y es
por estos que se han desarrollado técnicas como el gradiente, gradiente
empírico, línea de búsqueda, Newton-Raphson.
OBJETIVO
Identificar la búsqueda local en espacios continuos, para conocer cuál
es su importancia en la inteligencia artificial.
MARCO
TEÓRICO
BÚSQUEDA
LOCAL
En la búsqueda local, se empieza de una configuración
inicial (generalmente aleatoria) y se hacen pequeños cambios (a través de
operadores) hasta alcanzar un estado desde el cual no se puede alcanzar ningún
estado mejor. Las técnicas de búsqueda local son propensas a encontrar óptimos
locales que no son la mejor solución posible. El óptimo global es generalmente
imposible de alcanzar en un tiempo limitado, por el tamaño del espacio de
soluciones. (Ceccaroni, L. 2007)
ESPACIOS
CONTINUOS
Si existe una cantidad infinita de percepciones y acciones
distintas y discernibles, se dice que el ambiente es continuo. Los espacios
continuos son los que más se asemejan a la realidad del mundo y los problemas más
frecuentes.
EJEMPLO
DE BÚSQUEDA LOCAL EN ESPACIOS CONTINUOS
Supongamos que queremos colocar tres nuevos aeropuertos en
cualquier lugar de Rumania, de forma tal que la suma de las distancias al cuadrado
de cada ciudad sobre el mapa imagen1
su aeropuerto más cercano sea mínima. Entonces el espacio de estados está
definido por las coordenadas de los aeropuertos: (x1, y1), (x2, y2), y (x3, y3).
Es un espacio seis dimensional, también decimos que los estados están definidos
por seis variables (en general, los estados están definidos por un vector n-dimensional
de variables, x). Moverse sobre este espacio se corresponde a movimientos de
uno o varios de los aeropuertos sobre el mapa La función objetivo f(x1,y1,x2,y2,x3,y3) es relativamente
fácil calcularla para cualquier estado particular una vez que tenemos las
ciudades más cercanas, pero bastante complicado anotar en general. (
 |
| Imagen1. Mapa de carreteras simplificados de las carreteras de Rumania |
TÉCNICAS
DE BÚSQUEDA LOCAL EN ESPACIOS CONTINUOS
GRADIENTE: El gradiente es una operación vectorial, que opera sobre una
función escalar, para producir un vector cuya magnitud es la máxima razón de
cambio de la función en el punto del gradiente y que apunta en la dirección de
ese máximo. (Olmo, M y Nave, R. 2010?)
GRADIENTE EMPIRICO:
Se puede determinar evaluando la respuesta a pequeños incrementos
y decrecimientos en cada coordenada. El gradiente impirico se crea por la
necesidad de mejorar la técnica del gradiente. Donde alfa es una pequeña
constante.
LÍNEA DE BÚSQUEDA: trata de vencer el dilema amplia la dirección de gradiente actual
(que por lo general duplica repetidamente alfa) hasta que comience a disminuir
otra vez, el cual llega un punto en el que se crean nuevos estados. (Russell, S. y Norvig, P. 2004)
NEWTON-RAPHSON: esta técnica es muy utilizada para encontrar las raíces de una función,
procurando que la solución de una ecuaciones sean de la forma g(x)=0, y calculando
estimaciones de la raíz.
Aunque esta técnica ha evolucionado implementando la
matriz Hesiana, lo cual ayuda a Newthon-Raphson a hacer más
barata en espacios dimensionales.
OPTIMIZACIÓN CON
RESTRICCIONES Y PROGRAMACION LINEAL
La programación lineal resuelve problemas donde todas las
relaciones entre las variables son lineales, tanto en las restricciones como en
la función objetivo, la presencia de una única función no lineal hace que el
problema no pueda clasificarse como problema de programación lineal; ésta
evidencia su aplicación en diversos campos, como la ingeniería, la economía, la
gestión, y muchas otras áreas de la ciencia, la técnica y la industria. El
objeto de la programación lineal es optimizar (minimizar o maximizar) una función
lineal de n variables sujeto a restricciones lineales de igualdad o
desigualdad, denominada función objetivo. (Ornelas,
C y Marchenas, W. 2007)
Con esto se han estudiado problemas con tipos diferentes de
restricciones y funciones objetivo:
·
Programación cuadrática
·
Programación cónica de
segundo orden.
CONCLUSIÓN
Como conclusión puedo decir que el estudio de estas búsquedas
locales en espacios continuos son importantes e indispensable si queremos
introducirnos a la inteligencia artificial, puesto que este tipo de búsqueda en
entornos continuos son los que más se presentan en el mundo, son problemas
reales con los que hay que lidiar día a día. Las técnicas que se han
desarrollado para que estas búsquedas locales en espacios continuos, para
obtener soluciones óptimas a problemas que se presentan en el mundo real;
cada vez estas técnicas van
evolucionando y son más eficaces, la técnica principal es el gradiente de esta han ido surgiendo
otras técnicas como lo es el gradiente empírico, línea de búsqueda y Newton
Raphson.
BIBLIOGRAFÍA
Russell, S. y Norvig, P. 2004. INTELIGENCIA
ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.
Ceccaroni, L. 2007. Inteligencia
Artificial: Búsqueda local. Formato HTML. Disponible en: http://www.cs.upc.edu/
Olmos, I. 2008. Estructura de un Agente. Formato PDF. Disponible en: http://www.cs.buap.mx/
Olmo, M y Nave, R. 2010?. El Gradiente. Formato HTML. Disponible en: http://hyperphysics.phy-astr.gsu.edu/
Ornelas, C y Marchenas, W. 2007. Optimizacion y la programación lineal:
Una Introduccion. Formato PDF. Disponible en: http://fglongatt.org/
No hay comentarios.:
Publicar un comentario