Inteligencia Artificial
2.2 Métodos de Búsqueda
Respaldados con Información
Métodos

Búsqueda Preferente por lo Mejor



Búsqueda limitada por la capacidad de la memoria



Búsqueda Avara
Búsqueda A*
Búsqueda A* por profundización iterativa (A*PI)
Búsqueda A*SRM (Acotada por memoria simplificada)
Algoritmos de Mejoramiento Iterativo


Búsqueda por ascenso de cima (Hill-Climbing)
Endurecimiento simulado (Simulated Annealing)
Búsqueda preferente
por lo mejor


El conocimiento en base al cual se apoya la
decisión del nodo que toca expandirse es
obtenido desde una función de evaluación.
La función de evaluación produce un número
que sirve para representar lo deseable (o
indeseable) que sería la expansión de un nodo.
Búsqueda preferente
por lo mejor

Si los nodos se ordenan de tal manera que se
expande primero aquél con mejor evaluación,
entonces la estrategia es llamada búsqueda
preferente por lo mejor.
Búsqueda preferente
por lo mejor
función BUSQUEDA-PREFERENTE-POR-LO-MEJOR
(problema, FUNCION-EVALUACION) responde con una
secuencia de solución
entradas: problema, un problema
Función-Eval, una función de evaluación
Función-lista-de-espera  una función que ordena los nodos
mediante FUNCIÓN-EVAL
responde con BUSQUEDA-GENERAL (Problema, Funciónlista-de-espera)
Búsqueda preferente
por lo mejor

Así como es existe una familia de algoritmos
BUSQUEDA-GENERAL, con distintas
funciones de ordenamiento, también existe una
familia de algoritmos BUSQUEDAPREFERENTE-POR-LO-MEJOR, que varían
la función de evaluación.
Búsqueda preferente por lo
mejor




En el método de costo uniforme, se empleaba el costo
de ruta (g) para decidir qué ruta ampliar.
g(n) es, entonces, el costo acumulado desde el nodo
inicio hasta el nodo en que nos encontramos, n.
Esta medida no es una búsqueda directa dirigida a la
meta
Si se quiere enfocar la búsqueda hacia la meta, en
esa medida debe figurar algún tipo de cálculo del
costo de ruta del estado actual (n) a la meta.
Búsqueda preferente por lo
mejor

Búsqueda Avara (Greedy Search)


Es una de las más sencillas estrategias en la
BPPLM, que consiste en reducir al mínimo el
costo estimado para lograr una meta.
En otras palabras, el nodo cuyo estado se considere
más cercano a la meta en términos de costo de ruta
se expande primero.
Búsqueda preferente
por lo mejor

Búsqueda Avara (Greedy Search)



Aunque casi siempre es posible calcular el costo
aproximado hasta la meta, es difícil hacerlo con
precisión.
La función utilizada para dicho estimado del costo
se llama función heurística, simbolizada por h.
h(n) = costo estimado de la ruta más barata que
une el estado del nodo n con un estado meta
Búsqueda preferente
por lo mejor

Búsqueda Avara (Greedy Search)


h puede ser cualquier función. El único requisito es
que h(n) = 0 cuando n es una meta.
Cuando los problemas son de determinación de
rutas en el mundo real (ejemplo, Rumania), una
buena función heurística es la distancia en línea
recta a la meta:

hDLR (n) = distancia en línea recta entre n y la meta
Búsqueda preferente
por lo mejor
Neamt
87
Oradea
71
75
Iasi
92
151
Zerind
Sibiu
ARAD 140
118
80
Timisoara
97
70
75
Dobreta
Lugoj
Mehadia
120
142
211
Rimnicu
Vilcea
111
Vaslui
Fagaras
99
Urziceni
85
Pitesti
101
146
138
Craiova
98
BUCHAREST
90
Giurgiu
Hirsova
86
Eforie
DLR de
Bucarest a:
Arad:
366
Bucarest: 0
Craiova: 160
Dobreta: 242
Eforie:
161
Fagaras: 178
Giurgiu: 77
Hirsova: 151
Iasi:
226
Lugoj:
244
Mehadia: 241
Neamt: 234
Oradea: 380
Pitesti:
98
Rimnicu
Vilcea:
193
Sibiu:
253
Timisoara:329
Urziceni: 80
Vaslui:
199
Zerind: 374
Búsqueda preferente por lo
mejor

Búsqueda Avara (Greedy Search)


Para calcular los valores de hDLR se requieren las
coordenadas de las ciudades de Rumania.
Esta función heurística es útil porque la carretera
que va de A a B tiende a dirigirse más o menos en
la dirección correcta.
Ejercicio

Utilizar el método de búsqueda avara para
solucionar el problema de Rumania. Mostrar el
desarrollo con árboles de búsqueda.
Búsqueda preferente por lo
mejor
Neamt
87
Oradea
71
75
Iasi
92
151
Zerind
Sibiu
ARAD 140
118
80
Timisoara
97
70
75
Dobreta
Lugoj
Mehadia
120
142
211
Rimnicu
Vilcea
111
Vaslui
Fagaras
99
Urziceni
85
Pitesti
101
146
138
Craiova
98
BUCHAREST
90
Giurgiu
Hirsova
86
Eforie
DLR de
Bucarest a:
Arad:
366
Bucarest: 0
Craiova: 160
Dobreta: 242
Eforie:
161
Fagaras: 178
Giurgiu: 77
Hirsova: 151
Iasi:
226
Lugoj:
244
Mehadia: 241
Neamt: 234
Oradea: 380
Pitesti:
98
Rimnicu
Vilcea:
193
Sibiu:
253
Timisoara:329
Urziceni: 80
Vaslui:
199
Zerind: 374
Búsqueda preferente por lo
mejor

Búsqueda Avara
Arad
h=366
Búsqueda preferente por lo
mejor

Búsqueda Avara
Arad
h=366
Sibiu
h=253
Timisoara
h=329
Zerind
h=374
Búsqueda preferente por lo
mejor

Búsqueda Avara
Arad
h=366
Sibiu
h=253
Arad
h=366
Fagaras
h=178
Timisoara
h=329
Oradea
h=380
Rimnicu
h=193
Zerind
h=374
Búsqueda preferente por lo
mejor

Búsqueda Avara
Arad
h=366
Sibiu
h=253
Arad
h=366
Fagaras
h=178
Sibiu
h=253
Timisoara
h=329
Oradea
h=380
Zerind
h=374
Rimnicu
h=193
Bucharest
h=0
Es una solución, pero no es la óptima
Búsqueda preferente por lo
mejor

Búsqueda Avara



Esta búsqueda usualmente produce resultados
buenos
Tienden a producir soluciones rápidamente,
aunque no siempre la solución encontrada es la
óptima.
Ejemplo, tratar de llegar de Iasi a Fagaras.
Búsqueda preferente por lo
mejor

Búsqueda Avara
Iasi
h=160
Búsqueda preferente por lo
mejor

Búsqueda Avara
Iasi
h=160
Neamt
h=150
Vaslui
h=170
Búsqueda preferente por lo
mejor

Búsqueda Avara
Iasi
h=160
Neamt
h=150
Iasi
h=160
Vaslui
h=170
Búsqueda preferente por lo
mejor

Búsqueda Avara
Iasi
h=160
Neamt
h=150
Vaslui
h=170
Iasi
h=160
Neamt
h=150
Búsqueda preferente por lo
mejor

Búsqueda Avara



Se asemeja a la búsqueda preferente por profundidad, ya
que se “atora” al toparse con un callejón sin salida.
Tiene sus mismas deficiencias: no es óptima, es
incompleta, puede recorrer una ruta infinita.
Su complejidad es espacial es tan grande como su
temporal: O(bm), donde m es la profundidad máxima del
espacio de búsqueda. Una buena función heurística permite
disminuir notablemente la complejidad tanto de espacio
como de tiempo.
Búsqueda preferente por lo
mejor

Búsqueda A*



La búsqueda avara reduce h(n), el costo hacia la
meta, pero no es óptima ni completa.
La búsqueda de costo uniforme reduce g(n), el
costo de ruta, es óptima y completa, pero puede ser
ineficiente.
Las dos funciones se podrían combinar mediante
una suma:

f(n) = g(n) + h(n)
Búsqueda preferente por lo
mejor

Búsqueda A*



f(n) puede llamarse el costo estimado de la
solución más barata, pasando por n.
Es posible demostrar que esta estrategia es
completa y óptima, dada una restricción de h.
La restricción es escoger una función h que nunca
sobreestime el costo que implica alcanzar la meta.
Búsqueda preferente por lo
mejor

Búsqueda A*


A dicha función h se le llama heurística
admisible.
A la búsqueda preferente por lo mejor que usa f
como función de evaluación y una función h
aceptable se le conoce como búsqueda A*.
Búsqueda preferente por lo
mejor

Búsqueda A*

En el ejemplo de Rumania, la distancia en línea
recta es una heurística aceptable, ya que la ruta
más corta entre dos puntos es la línea recta (por lo
tanto, siempre será menor que la distancia real,
nunca la sobreestimará).
Búsqueda preferente por lo
mejor

Búsqueda A*
Arad
f=0+366
f=366
Búsqueda preferente por lo
mejor
Búsqueda A*
Arad
Sibiu
f=140+253
f=393
Timisoara
f=118+329
f= 447
Zerind
f=75+374
f=449
Búsqueda preferente por lo
mejor
Búsqueda A*
Arad
Sibiu
f=140+253
f=393
Arad
f=280+366
f=646
Timisoara
f=118+329
f= 447
Fagaras
f=239+178
f=417
Oradea
f=146+380
f=526
Zerind
f=75+374
f=449
Rimnicu
f=220+193
f=413
Búsqueda preferente por lo
mejor

Búsqueda A*. (Comportamiento)
Se puede observar que a lo largo de las rutas
originadas en la raíz, el costo f nunca
disminuye.
 En toda heurística donde esto ocurre, se dice
que muestra monotonicidad.

Búsqueda preferente por lo
mejor

Búsqueda A*

Si la heurística fuera no monotónica, debe usarse
la fórmula
f(n’) = max f(n),g(n’) + h(n’)
Donde n’ es el nodo actual y n es el padre de n’

A esta fórmula se le llama ecuación de ruta
máxima.
Búsqueda preferente por lo
mejor

Búsqueda A*

Si f no disminuye, es posible dibujar contornos en
el espacio de estados.
Neamt
Iasi
Oradea
Zerind
Sibiu
ARAD
f  380
f  400
Timisoara
Lugoj
Rimnicu
Vilcea
Urziceni
Pitesti
Mehadia
f  420
Dobreta
Vaslui
Fagaras
Hirsova
BUCHAREST
Giurgiu
Craiova
Eforie
Búsqueda preferente por lo
mejor

Búsqueda A*



Conforme va avanzando, la búsqueda A* dibuja
bandas concéntricas, e incluyendo nodos.
En la búsqueda de costo uniforme (A* con h = 0)
las bandas son circulares alrededor del estado
inicial.
Si la heurística es buena, las bandas tienden al
estado meta y se concentran apretadamente sobre
la ruta óptima.
Búsqueda preferente por lo
mejor

Búsqueda A*



Este método es óptimamente eficiente para
cualquier función heurística.
El problema con el A* es que, para la mayoría de
los problemas, la cantidad de nodos en el contorno
de la meta sigue siendo exponencial.
El principal problema es el espacio, ya que
usualmente se agota la memoria primero (guarda
todos los nodos generados).
Funciones Heurísticas

Problema de las ocho placas
Funciones Heurísticas

Problema de las ocho placas




Una solución típica tiene 20 pasos (depende del
estado inicial).
El factor de ramificación es aproximadamente 3
Una búsqueda exhaustiva de profundidad 20
examinaría 320 estados.
Aún si se evitan estados repetidos, habría 362,880
arreglos diferentes.
Funciones Heurísticas

Problema de las ocho placas


La función heurística no debe sobreestimar la
cantidad de pasos necesarios para la meta.
Ejemplos:


h1 = cantidad de placas en lugar incorrecto
h2 = suma de las distancias (horizontales y verticales)
que separan a las placas de sus posiciones meta
(distancia Manhattan).
Funciones Heurísticas

Problema de las ocho placas: Heurística de la
cantidad de placas en lugar incorrecto.
h1 = 8
h1 = 0
Funciones Heurísticas

Problema de las ocho placas: Heurística de la
distancia Manhattan
h2 = 15
h2 = 0
Funciones Heurísticas

Efectos de la exactitud heurística en el desempeño


Una forma de medir la calidad de una heurística es
mediante el factor de ramificación efectiva b*.
Si la cantidad de nodos expandidos por A* para un
problema determinado es N, y la profundidad de la solución
es d, entonces b* es el factor de ramificación que deberá
tener un árbol uniforme de profundidad d para que pueda
contener N nodos, por lo que
N = 1 + b* + (b*)2 + ... + (b*)d
Funciones Heurísticas

Efectos de la Exactitud Heurística

Un árbol como este tiene un factor de ramificación
efectiva de 2
G
N=7
d=2
b* = 2
1 + 2+ 22 = 7
Funciones Heurísticas

Efectos de la Exactitud Heurística

Porque equivale a un árbol uniforme como este:
G
N=7
d=2
b* = 2
1 + 2+ 22 = 7
Funciones Heurísticas

Efectos de la exactitud heurística en el
desempeño



Por ejemplo, si A* encuentra una solución en la
profundidad cinco, y utilizando 52 nodos, el factor
de ramificación efectiva es de 1.91.
Por lo general, el b* correspondiente a una
heurística determinada permanece constante a
través de un amplia gama de problemas.
En una heurística bien diseñada, b* se aproxima a
1.
Funciones Heurísticas
Costo de Búsqueda
d
BPPI
A*(h1)
Factor de Ramificación Efectivo
A*(h2)
BPPI
A*(h1)
A*(h2)
2
10
6
6
2.45
1.79
1.79
4
112
13
12
2.87
1.48
1.45
6
680
20
18
2.73
1.34
1.30
8
6,384
39
25
2.80
1.33
1.24
10
47,127
93
39
2.79
1.38
1.22
12
364,404
227
73
2.78
1.42
1.24
14
3,473,941
539
113
2.83
1.44
1.23
16
-----
1,301
211
-----
1.45
1.25
18
-----
3,056
363
-----
1.46
1.26
20
-----
7,276
676
-----
1.47
1.27
22
-----
18,094
1,219
-----
1.48
1.28
24
-----
39,135
1,641
-----
1.48
1.26
Funciones Heurísticas

Efectos de la Exactitud Heurística



Comparando los factores de ramificación efectiva,
h2 es mejor que h1.
Si para todo nodo n, h2(n)  h1(n), se dice que h2
domina a h1.
En general, siempre conviene más emplear una
función heurística con valores más altos, siempre
cuando no dé lugar a una sobreestimación.
Funciones Heurísticas

Invención de Heurísticas


A los problemas en que se imponen menos
restricciones a los operadores se les llama
problemas relajados.
Es frecuente que el costo de la solución de un
problema relajado constituya una buena heurística
del problema general.
Funciones Heurísticas

Invención de Heurísticas

Operador del Problema de las ocho placas (normal)


“Una placa puede pasar del cuadro A al B si A está junto a B y B
está vacío”
Operadores relajados para el problema de las ocho placas



“Una placa se puede mover del cuadro A al B si A está junto a B”
“Una placa se puede mover del cuadro A al B si B está vacío”
“Una placa se puede mover del cuadro A al B”
Funciones Heurísticas

Invención de Heurísticas

Si para un problema determinado existe un grupo
de heurísticas aceptables, h1,..., hm, y ninguna
domina a las demás, se puede usar:


h(n) = max(h1(n), ..., hm(n)).
Otra forma de inventar heurísticas es mediante
información estadística. Se pueden hacer
búsquedas sobre una gran cantidad de problemas
de adiestramiento y se obtienen las estadísticas
correspondientes.
Búsqueda limitada por la
capacidad de la memoria


La capacidad de memoria es uno de los
principales obstáculos a los que se enfrentan
los algoritmos anteriores.
Algoritmos de BLCM


A* por profundización iterativa (A*PI)
A* acotado por memoria simplificada (A*SRM)
Búsqueda limitada por la
capacidad de la memoria

A*PI



Es algo similar a lo que se hizo con la búsqueda preferente
por profundidad, al hacerla iterativamente (profundización
iterativa), sólo que ahora se hace con la búsqueda A*.
En esta algoritmo cada iteración es una búsqueda preferente
por profundidad, exactamente como en la PI, pero ahora se
usa un límite de costo f en vez de un límite de profundidad.
Así, en cada iteración se expanden los nodos que están
dentro del contorno del costo f actual.
Búsqueda limitada por la
capacidad de la memoria

A*PI



Una vez concluida la búsqueda dentro de un
contorno determinado, se procede a efectuar una
nueva iteración usando un nuevo costo f para el
contorno siguiente.
A*PI es un método completo y óptimo, con las
ventajas y desventajas del A*
Como es preferente por profundidad, sólo necesita
un espacio proporcional con la ruta más larga que
explore.
Búsqueda limitada por la
capacidad de la memoria

A*PI


Si δ es el mínimo costo de operador y f* es el costo
de la solución óptima, en el peor de los casos se
necesitan bf* / δ nodos de almacenamiento.
En la mayoría de los casos, bd es un estimado
bastante bueno de la capacidad de memoria
necesaria.
Búsqueda limitada por la
capacidad de la memoria

A*PI


(ver algoritmo en el libro de texto)
Tiene desventajas en dominios complejos.
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria
Simplificada)




A*PI utiliza muy poca memoria
Entre iteraciones, sólo guarda un número: el límite
actual del costo f.
Como no puede recordar su historia, puede
repetirla.
El método A*SRM emplea más memoria que el
A*PI, para mejorar la eficiencia de la búsqueda.
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria Simplificada)





Hace uso de toda la memoria de la que pueda disponer
En la medida que se lo facilite la memoria, evitará estados
repetidos
Es completo, si la memoria es suficiente para guardar la
ruta de solución mas cercana
Es óptimo, si dispone de suficiente memoria para guardar
la ruta de solución óptima más cercana.
Si se dispone de suficiente memoria para todo el árbol de
búsqueda, éste resultará óptimamente eficiente.
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria Simplificada)




Si hay que generar un sucesor, pero ya no hay memoria, se
requiere espacio en la lista de espera
Es necesario excluir un nodo de la lista de espera. A estos
nodos se les llama nodos olvidados, con un elevado f.
Se conserva la información de los nodos ancestros sobre la
calidad de la mejor ruta en el subárbol olvidado.
Así sólo se tendrá que regenerar el subárbol si las demás
rutas ofrecen peores perspectivas que la ruta olvidada.
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria Simplificada)
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria Simplificada)
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria Simplificada)
En cada una de las etapas se añade
un sucesor nodo de menor costo f
más profundo cuyos sucesores no
estén actualmente en el árbol. El hijo
izquierdo B se añade a la raíz A.
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria Simplificada)
Ahora, f(A) es todavía 12, por lo que
se añade el hijo que está a la derecha,
G (f = 13). Ahora que ya se vieron
todos los hijos de A, es posible
actualizar su costo f al mínimo de sus
hijos, es decir, 13. La memoria ya se
llenó.
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria Simplificada)
G se escoge para efectuar una expansión, pero primero
hay que excluir un nodo para hacer espacio. Se excluye
la hoja de mayor costo f más próxima, es decir, B.
Ahora notaremos que el mejor descendiente olvidado
de A tiene f =15, como se muestra entre paréntesis.
Se procede a añadir H, cuya f(H) = 18.
Desafortunadamente, H no es un nodo meta, y la ruta a
H consume toda la memoria disponible (solo tenemos
espacio para tres nodos en memoria). Es decir, es
imposible encontrar una solución a través de H, por lo
que se define que f(H) = . (si quisiéramos seguir,
tendríamos que olvidar al nodo inicial, y no es posible).
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria Simplificada)
Se expande de nuevo G, se excluye H, se incluye
I, con f(I) = 24. (esto debido a que I sí es un nodo
meta, en caso contrario se le asignaría valor ).
Se han visto ya los dos sucesores de G, con
valores de  y 24, por lo que f(G) se convierte en
24. f(A) se convierte en 15, el mínimo de 15
(valor del sucesor olvidado) y 24.
Hay que notar que a pesar de que I es un nodo
meta, quizás no sea la mejor solución debido a
que el costo de f(A) es solamente 15
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria Simplificada)
Otra vez, A es el nodo más
prometedor, por lo que se genera por
segunda vez B. Nos hemos dado
cuenta que, después de todo, la ruta a
través de G no resultó ser tan buena.
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria Simplificada)
C, el primer sucesor de B, es un
nodo no meta que está a máxima
profundidad, por lo que f(C) = .
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria Simplificada)
Para examinar al segundo sucesor, D,
primero hay que excluir C. Entonces
f(D)=20, valor que heredan tanto B como A.
Ahora el nodo de menor costo f más
profundo es D, por lo que se le escoge.
Puesto que se trata de un nodo meta,
concluye la búsqueda.
Búsqueda limitada por la
capacidad de la memoria

A*SRM (A* Acotado por Memoria Simplificada)



(Ver el algoritmo en el libro de texto)
Las cosas se complican aun más so hay que incluir la
verificación de nodos repetidos . A*SRM es el algoritmo
más complicado visto hasta el momento.
Cuando cuenta con suficiente memoria, A*SRM resuelve
probelmas mucho más difíciles que A* sin excesos
considerables en la generación de nodos adicionales.
Algoritmos de búsqueda local y
problemas de optimización


Hay problemas (como el de las 8 reinas, o la
distribución de áreas en un chip VLSI) que se
caracterizan porque la misma descripción del
estado contiene toda la información necesaria
para encontrar una solución, y la ruta para
obtenerla es irrelevante.
En estos casos, los algoritmos de búsqueda
local son el método de solución más práctico.
Algoritmos de búsqueda local y
problemas de optimización


Los algoritmos de búsqueda local operan
usando un simple estado actual (en vez de
múltiples rutas) y generalmente se mueven a
los vecinos de dicho estado.
Sus ventajas son:


Usan muy poca memoria (usualmente constante)
Pueden encontrar a menudo soluciones razonables
en espacios de estados muy grandes o infinitos en
los cuales los algoritmos sistemáticos no son
adecuados.
Algoritmos de búsqueda local y
problemas de optimización

Además de encontrar metas, los algoritmos de
búsqueda local son útiles para resolver
problemas de optimización, en los cuales el
objetivo es encontrar el mejor estado de
acuerdo con una función objetivo.
Algoritmos de búsqueda local y
problemas de optimización


La idea básica consiste en empezar con una
configuración completa y efectuar
modificaciones para mejorar la calidad.
Los ABL “imaginan” que los estados están
sobre la superficie de un paisaje, y la altura de
cada uno corresponde a la función de
evaluación del estado en ese punto.
Algoritmos de búsqueda local y
problemas
de
optimización
Evaluación
Estado
Actual
Algoritmos de búsqueda local y
problemas de optimización
Algoritmos de búsqueda local y
problemas de optimización



Si la elevación corresponde al costo, el objetivo es
encontrar el valle más bajo (un mínimo global).
Si la elevación corresponde a una función objetivo,
entonces el objetivo es encontrar el pico más alto (un
máximo global).
Los algoritmos de búsqueda local exploran este
paisaje. Una ABL completo siempre encuentra una
meta si existe; un algoritmo óptimo siempre
encuentra un máximo/mínimo global.
Algoritmos de búsqueda local y
problemas de optimización


Normalmente, los ABL se fijan sólo en el
estado actual, sin mirar mas allá de los vecinos
inmediatos de tal estado.
Tienen varias aplicaciones, en especial, en el
aprendizaje de redes neuronales.
Algoritmos de búsqueda local y
problemas de optimización




Búsqueda por ascenso de cima
Recocido simulado
Búsqueda local en haz
Algoritmos Genéticos
Algoritmos de búsqueda local y
problemas de optimización

Búsqueda por ascenso de cima
Función Ascenso-de-cima(problema) responde con un estado de solución
entradas: problema, un problema
estático: actual, un nodo
siguiente, un nodo
actual  Hacer-nodo(Estado Inicial[problema])
hacer ciclo
siguiente  el sucesor de actual de más alto valor
si Valor[siguiente] < Valor[actual] entonces responde con actual
actual  siguiente
fin
Algoritmos de búsqueda local y
problemas de optimización

Búsqueda por ascenso de cima




“Es como intentar buscar la cima del monte Everest en una
densa niebla y con amnesia”.
El algoritmo es un ciclo que constantemente se desplaza en
la dirección de un valor ascendente.
Como el algoritmo no mantiene un árbol de búsqueda, la
estructura de datos del nodo sólo tiene que registrar el
estado y su evaluación, denominado VALOR.
Cuando existe más de un sucesor idóneo que escoger, el
algoritmo selecciona uno de ellos al azar.
Algoritmos de búsqueda local y
problemas de optimización

Búsqueda por ascenso
de cima
h = 17
h=1
Algoritmos de búsqueda local y
problemas de optimización

Búsqueda por ascenso de cima

Desventajas:



Máximos locales: al contrario de un máximo global, es una cima
cuya altura es inferior a la cima más alta de todo el espacio de
estados.
Planicies: Son áreas del espacio de estados donde la función de
evaluación básicamente es plana. La búsqueda realiza movimientos
al azar.
Riscos: Las laderas de algunos riscos tienen pendientes muy
pronunciadas, por lo que es fácil para una búsqueda llegar a la cima
del risco; sin embargo, puede suceder que la pendiente de tal cima
se aproxime demasiado gradualmente a un pico. Ña búsqueda
puede oscilar de un lado al otro obteniendo muy poco avance.
Algoritmos de búsqueda local y
problemas de optimización

Búsqueda por ascenso de cima



En los casos anteriores, se llega a un punto más
allá del cual no se logra ningún avance, ys se debe
empezar nuevamente en otro punto.
Esto se logra mediante el ascenso de cima con
reinicio aleatorio.
El éxito de este algoritmo depende en gran medida
de la forma que tenga la “superficie” del espacio
de estados (usualmente puede parecerse a un
“puerco espín”).
Algoritmos de búsqueda local y
problemas de optimización
Función Recocido-Simulado(problema, programa) responde con un estado de solución
entradas: problema, un problema
programa, un mapeo para pasar de tiempo a “temperatura”
estático: actual, un nodo
siguiente, un nodo
T, una “temperatura” que controla la posibilidad de dar pasos
descendentes.
actual  Hacer-nodo(Estado Inicial[problema])
para t  1 a  hacer
T  programa[t]
si T = 0, entonces responde con actual
siguiente  un sucesor de actual escogido aleatoriamente
E  Valor[siguiente] - Valor[actual]
si E > 0, entonces actual  siguiente
o bien actual  siguiente con probabilidad eE/T
fin
Algoritmos de búsqueda local y
problemas de optimización

Recocido simulado




En vez de empezar otra vez al azar luego de quedarse
atorado en un máximo local, sería conveniente descender
unos cuantos pasos y así escapar del máximo local en
cuestión.
Esta es la base del recocido simulado.
En vez de optar por la mejor acción, se escoge una al azar.
Siempre que mediante alguna acción se logre mejorar la
situación, dicha acción se ejecuta. De lo contrario, el
algoritmo realizará cierta acción con cierta probabilidad
menor a uno. La probabilidad disminuye exponencialmente
con lo “malo” de la acción.
Algoritmos de búsqueda local y
problemas de optimización

Recocido simulado




Para determinar la probabilidad se utiliza un segundo
parámetro, T.
Cuando los valores de T son elevados, hay más
probabilidad de que se acepten las acciones “malas”.
Conforme T tiende a cero, es menos probable su
aceptación, hasta que el algoritmo se comporte más o
menos como el ascenso de cima.
El programa es una función que define el valor de T en
base a la cantidad de ciclos que se hayan realizado.
Algoritmos de búsqueda local y
problemas de optimización

Recocido simulado



El término “recocido simulado”, y el nombre de los parámetros E
y T obedece a que el algoritmo se creó a partir de una analogía con
el recocido, un proceso que consiste en enfriar un líquido hasta que
se congele (o un metal fundido hasta que se solidifique).
La función VALOR corresponde a la energía total de los átomos del
material y T corresponde a la temperatura. El programa define la
velocidad de descenso de temperatura. Las acciones individuales
del espacio de estados corresponden a fluctuaciones aleatorias
producidas por ruido térmico.
Es posible demostrar que si la temperatura se baja con suficiente
lentitud, el material adoptará la configuración de la energía más
baja (de ordenamiento perfecto). Esto equivale a decir que si el
programa baja a T con la suficiente lentitud, el algoritmo encontrará
un óptimo global.
Algoritmos de búsqueda local y
problemas de optimización

Búsqueda local en haz




El algoritmo de búsqueda local en haz (local beam
search) mantiene registro de k estados en vez de sólo
uno.
Comienza con k estados generados aleatoriamente.
En cada paso, todos los sucesores de los k estados son
generados.
Si uno de ellos es la meta, el algoritmo se detiene. De
otra manera, se selecciona los k mejores sucesores de la
lista completa y el proceso se repite.
Algoritmos de búsqueda local y
problemas de optimización

Búsqueda local en haz




A primera vista, la búsqueda local en haz con k estados
parece no más que correr k ascensos independientes de
cima en paralelo, en vez de hacerlo en secuencia.
Sin embargo, en la búsqueda local en haz se transmite
información útil entre las k búsquedas paralelas.
Es decir, si un estado genera varios buenos sucesores, y
los k – 1 estados restantes generan todos malos
sucesores, el efecto es que el primer estado le dice a los
otros “vengan aquí, el pasto es más verde!”.
El algoritmo abandona rápidamente búsquedas
infructuosas y mueve sus recursos donde se pueda hacer
más progresos.
Algoritmos de búsqueda local y
problemas de optimización

Búsqueda local en haz


Una variante llamada búsqueda en haz
estocástica evita la falta de diversidad entre los k
estados y evita concentrarse en una pequeña
región del espacio de estados.
En vez de elegir los mejores k del grupo de
sucesores candidatos, se eligen k sucesores al
azar, con la probabilidad de elegir un sucesor
dado como una función incremental de su valor.
Algoritmos de búsqueda local y
problemas de optimización

Algoritmos genéticos


Un algoritmo genético (AG) es una variante de la
búsqueda en haz estocástica, en la cual los estados
sucesores son generados combinando dos estados
padres, más que modificando un solo estado.
La analogía a la selección natural es la siguiente:
Los sucesores (descendientes) de dos estados
(organismos) padres, conforman la siguiente
generación, de acuerdo a su valor (aptitud).
Algoritmos de búsqueda local y
problemas de optimización

Algoritmos genéticos



Los AGs comienzan con un conjunto de k estados
generados aleatoriamente, llamados la población.
Cada estado, o individuo, se representa como una
cadena (string) tomada de un alfabeto finito
(comúmente, una cadena de 0’s y 1’s).
En el problema de las 8 reinas, se podrían
especificar las posiciones de cada una de las 8
reinas en cada columa mediante 24 bits, o
mediante dígitos entre 1 y 8.
Algoritmos de búsqueda local y
problemas de optimización

Algoritmos genéticos
Algoritmos de búsqueda local y
problemas de optimización

Algoritmos genéticos



Cada estado es “calificado” meduante la función de
evalación, llamada función de aptitud.
Una función de aptitud debe regresar valores más altos para
mejores estados. En el problema de las 8 reinas se usa la
cantidad de pares de reinas que no se atacan entre sí. Una
solución debe tener un valor de aptitud de 28.
Las aptitudes de los 4 estados son 24, 23, 20 y 11 y se
calculan las probabilidades de ser elegidos en forma
proporcional a la aptitud.
Algoritmos de búsqueda local y
problemas de optimización

Algoritmos genéticos



Se eligieron dos pares para reproducción, de
acuerdo a las probabilidades en (b). Para cada par a
ser apareado, se elige un punto de cruza al azar, a
partir de las posiciones en la cadena.
En (d), los descendientes son creados al cruzar las
cadenas padres en los puntos de cruza.
Finalmente, en (e), cada posición es sujeta a una
mutación aleatoria con una pequeña probabilidad
independiente.
Algoritmos de búsqueda local y
problemas de optimización

Algoritmos genéticos



Los algoritmos genéticos combinan una tendencia de
ascenso de cima con exploración aleatoria e intercambio de
información entre búsquedas paralelas.
La principal ventaja, si la hay, de los algoritmos genéticos
viene de la operación de cruza.
La ventaja viene de la habilidad de la cruza para combinar
grandes bloques de caracteres que han evolucionado
independientemente para desempeñar funciones exitosas,
elevando el nivel de granularidad en el que opera la
búsqueda.
Algoritmos de búsqueda local y
problemas de optimización

Algoritmos genéticos



La teoría de los algoritmos genéticos explica como trabajan
usando la idea de un esquema, el cual es una subcadena en
la cual algunas de las posiciones se dejan sin especificar.
Por ejemplo, el esquema 246***** describe todos los
estados del problema de las 8 reinas donde las tres primeras
reinas están en las posiciones 2, 4 y 6 respectivamente.
Las cadenas que concuerdan con el esquema (como
24613578) son llamadas instancias del esquema.
Algoritmos de búsqueda local y
problemas de optimización

Algoritmos genéticos




Se puede mostrar que, si la aptitud promedio de las
instancias de un esquema está sobre la media, entonces el
número de instancias del esquema dentro de la población
crecerá con el tiempo.
Los algoritmos genéticos trabajan mejor cuando los
esquemas corresponden a componentes significativos de la
solución.
Esto sugiere que el uso exitoso de los algoritmos genéticos
requiere una ingeniería cuidadosa de la representación.
En la práctica, los AGs tienen un amplio impacto en
problemas de optimización, tales como distribución en
circuitos y programación de actividades.
Descargar

Inteligencia Artificial