path: root/si/n4.lyx

#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\begin_preamble
\usepackage{amssymb}
\end_preamble
\use_default_options true
\begin_modules
algorithm2e
\end_modules
\maintain_unincluded_children false
\language spanish
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style french
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Section
Búsqueda local
\end_layout

\begin_layout Standard
En muchos problemas, como el diseño de circuitos o la optimización de redes,
 solo importa el estado objetivo, no cómo se llega a él.
\end_layout

\begin_layout Standard
Los métodos que veremos operan con un único estado actual, no suelen recordar
 los caminos, usan muy poca memoria y pueden encontrar soluciones razonables
 en espacios de estados grandes o continuos en los que los algoritmos clásicos
 no son adecuados.
\end_layout

\begin_layout Standard
Podemos considerar el espacio de estados como un paisaje donde la posición
 es un estado y la elevación viene dada por una función objetivo a maximizar
 o minimizar; supondremos que a maximizar.
\end_layout

\begin_layout Standard
Para el 
\series bold
problema de las 8 reinas
\series default
, consistente en situar 8 reinas en un tablero de ajedrez de forma que ninguna
 esté en jaque, como cada reina debe estar en una columna, podemos representar
 los estados como una tupla con la fila en la que está cada reina; cada
 estado tendría 56 vecinos correspondientes a cambiar la posición de una
 reina y la función a minimizar sería el número de jaques, que habría que
 bajar a 0.
\end_layout

\begin_layout Subsection
Búsqueda local avara o ascensión de colinas
\end_layout

\begin_layout Standard
Se mueve en cada paso al vecino del estado actual con el valor objetivo
 más alto.
 A menudo se atasca en máximos locales; 
\series bold
crestas
\series default
, secuencias de máximos locales que dificultan mucho la navegación, y sobre
 todo en 
\series bold
mesetas
\series default
 o 
\series bold
terrazas
\series default
, áreas donde la función objetivo es plana.
\end_layout

\begin_layout Standard
Para evitar que se atasque en terrazas, se puede permitir un movimiento
 lateral aleatorio cuando no hay ningún movimiento ascendente.
 Esto lleva a un bucle infinito si el método alcanza un máximo local plano,
 por lo que se suele limitar el número de movimientos laterales consecutivos.
\end_layout

\begin_layout Standard
La 
\series bold
ascensión de colinas de reinicio aleatorio
\series default
 consiste en ejecutar la ascensión de colinas repetidamente con distintos
 estados iniciales.
 En espacios de estados finitos
\begin_inset Foot
status open

\begin_layout Plain Layout
En general cuando caer en un estado final tiene probabilidad no nula y ascender
 infinitamente tiene probabilidad nula.
\end_layout

\end_inset

, es completa con probabilidad 1, aunque no garantiza terminar, y es muy
 eficaz.
\end_layout

\begin_layout Subsection
Temple simulado
\end_layout

\begin_layout Standard
Para templar metal, este se calienta mucho para favorecer el movimiento
 de las partículas y se enfría gradualmente para que estas se estabilicen
 en estructuras cristalinas de baja energía.
 Para tratar de colar una bola en el hueco más profundo de una superficie
 con agujeros, esta se agita mucho para favorecer escapar de depresiones
 locales y se reduce gradualmente la fuerza para que la bola se estabilice
 en huecos profundos.
\end_layout

\begin_layout Standard
Esta idea la usa el algoritmo 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:sim-annealing"
plural "false"
caps "false"
noprefix "false"

\end_inset

 para resolver problemas.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
Entrada{Problema de espacio de estados sin costes $(V,A,s,F)$, función objetivo
 $f:V
\backslash
to
\backslash
mathbb R$ y {
\backslash
bf esquema} de temperaturas $e:
\backslash
mathbb N
\backslash
to
\backslash
mathbb{R}^{
\backslash
geq0}$ monótono decreciente.}
\end_layout

\begin_layout Plain Layout


\backslash
Salida{Solución $s
\backslash
in V$.}
\end_layout

\begin_layout Plain Layout


\backslash
SetKwFunction{rand}{rand}
\end_layout

\begin_layout Plain Layout


\backslash
Para{$t
\backslash
gets1$ en adelante}{
\end_layout

\begin_layout Plain Layout

	$T
\backslash
gets e(t)$
\backslash
;
\end_layout

\begin_layout Plain Layout

	
\backslash
lSSi{$T=0$}{
\backslash
Devolver $s$}
\end_layout

\begin_layout Plain Layout

	$
\backslash
{n_0,
\backslash
dots,n_{k-1}
\backslash
}
\backslash
gets
\backslash
{v
\backslash
in V:(s,v)
\backslash
in A
\backslash
}$
\backslash
;
\end_layout

\begin_layout Plain Layout

	
\backslash
Para{$i
\backslash
gets0$ 
\backslash
KwA $k-1$}{
\end_layout

\begin_layout Plain Layout

		$c
\backslash
gets n_{
\backslash
lfloor k
\backslash
rand{}
\backslash
rfloor}$
\backslash
;
\end_layout

\begin_layout Plain Layout

		$
\backslash
Delta E
\backslash
gets f(c)-f(e)$
\backslash
;
\end_layout

\begin_layout Plain Layout

		
\backslash
lSSi{$
\backslash
Delta E>0
\backslash
lor
\backslash
rand{}<e^{
\backslash
Delta E/T}$}{$s
\backslash
gets c$}
\end_layout

\begin_layout Plain Layout

	}
\end_layout

\begin_layout Plain Layout

}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "alg:sim-annealing"

\end_inset

Temple simulado.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Haz local
\end_layout

\begin_layout Standard
Se empieza con 
\begin_inset Formula $k$
\end_inset

 estados elegidos aleatoriamente y, en cada paso, se generan los sucesores
 de cada estado, se comprueba si alguno es objetivo para terminar y, si
 ninguno lo es, se toman los 
\begin_inset Formula $k$
\end_inset

 mejores sucesores de entre todos.
 Si hay poca diversidad entre los 
\begin_inset Formula $k$
\end_inset

 estados, esto no es mucho mejor que la ascensión de colinas, por lo que
 los nuevos estados se suelen elegir de forma estocástica.
\end_layout

\begin_layout Subsection
Algoritmos genéticos
\end_layout

\begin_layout Standard
Son una variante de la búsqueda de haz local estocástica.
 Cada estado, 
\series bold
individuo
\series default
 o 
\series bold
cromosoma
\series default
 se codifica como una cadena, normalmente de longitud finita, de un alfabeto
 finito, en la que cada símbolo es un 
\series bold
gen
\series default
.
 Las codificaciones más usadas son 
\series bold
binaria
\series default
 mediante cadenas de dígitos binarios, 
\series bold
entera
\series default
 mediante cadenas de enteros de algún conjunto finito, y 
\series bold
de orden
\series default
, en que la cadena es una permutación.
\end_layout

\begin_layout Standard
En cada paso hay una 
\series bold
población
\series default
 de 
\begin_inset Formula $k$
\end_inset

 estados generados aleatoriamente.
 Mediante un algoritmo de 
\series bold
selección
\series default
, se escogen 
\begin_inset Formula $k$
\end_inset

 individuos de la población, posiblemente repetidos, que podrán reproducirse.
 Estos se emparejan y cada pareja, con una probabilidad 
\begin_inset Formula $p_{c}$
\end_inset

, se sustituye por dos individuos hijos mediante un algoritmo de 
\series bold
cruce
\series default
.
 Finalmente, se usa un algoritmo de 
\series bold
mutación
\series default
 para mutar cada gen de cada individuo con una probabilidad 
\begin_inset Formula $p_{m}$
\end_inset

, y el resultado es la nueva población.
 Esto se repite hasta que haya un individuo en la población suficientemente
 bueno o pase bastante tiempo.
\end_layout

\begin_layout Standard
Los 
\series bold
operadores genéticos
\series default
 son los algoritmos de selección, cruce y mutación.
 Algunos algoritmos de selección:
\end_layout

\begin_layout Itemize

\series bold
Ruleta
\series default
: Para cada uno de los 
\begin_inset Formula $k$
\end_inset

 puestos, se elige un individuo con probabilidad proporcional a su valor
 por la función objetivo, su 
\series bold
idoneidad
\series default
 o 
\series bold
\emph on
\lang english
fitness
\series default
\emph default
\lang spanish
.
\end_layout

\begin_layout Itemize

\series bold
Torneo
\series default
: Se eligen 
\begin_inset Formula $2k$
\end_inset

 parejas por un algoritmo como la ruleta y se toma el de mayor idoneidad
 en cada una.
\end_layout

\begin_layout Standard
Algunos algoritmos de cruce:
\end_layout

\begin_layout Itemize

\series bold
Por un punto
\series default
: Se elige una posición al azar de las cadenas de los padres.
 Un hijo adopta la parte a la izquierda de un padre y la parte a la derecha
 del otro y el otro hijo al revés.
\end_layout

\begin_layout Itemize

\series bold
Por dos puntos
\series default
: Se eligen dos posiciones.
 Un hijo adopta los extremos de un padre y el centro del otro y el otro
 hijo al revés.
\end_layout

\begin_layout Standard
Algunos de mutación:
\end_layout

\begin_layout Itemize
Cambio de un gen aleatorio de un individuo por otro valor.
\end_layout

\begin_layout Itemize
Intercambio de dos genes del individuo.
\end_layout

\begin_layout Section
Búsqueda entre adversarios
\end_layout

\begin_layout Standard
Un 
\series bold
juego
\series default
 o 
\series bold
problema de búsqueda entre adversarios
\series default
 es un entorno competitivo en que los objetivos de distintos agentes están
 en conflicto.
 Se deben considerar las decisiones de los otros agentes, pero su imprevisibilid
ad puede generar muchas contingencias.
\end_layout

\begin_layout Standard
Consideramos juegos de suma cero (la suma del valor objetivo de cada agente
 es 0), de dos jugadores, por turnos, determinista y de información perfecta
 (entorno totalmente observable).
 Los jugadores son 
\family typewriter
max
\family default
, que mueve primero e intenta maximizar una cierta función utilidad 
\begin_inset Formula $u$
\end_inset

 de los estados terminales, y 
\family typewriter
min
\family default
, que intenta minimizar 
\begin_inset Formula $u$
\end_inset


\end_layout

\begin_layout Standard
Podemos representar un juego por una tupla 
\begin_inset Formula $(V,A,M,s,F,u)$
\end_inset

, donde 
\begin_inset Formula $(V,A)$
\end_inset

 es un grafo como el de la búsqueda clásica de espacios de estados pero
 en el que todos los nodos hoja son terminales; 
\begin_inset Formula $M\subseteq V$
\end_inset

 es un conjunto computable de 
\series bold
estados 
\family typewriter
max
\family default
\series default
 (en los que el turno es de 
\family typewriter
max
\family default
), cuyo complementario es el conjunto de 
\series bold
estados 
\family typewriter
min
\family default
\series default
 y tal que los sucesores de un estado 
\family typewriter
max
\family default
 son estados 
\family typewriter
min
\family default
 y viceversa; 
\begin_inset Formula $s\in M$
\end_inset

 es el estado inicial; 
\begin_inset Formula $F\subseteq V$
\end_inset

 es un conjunto computable de estados finales, y 
\begin_inset Formula $u:F\to\mathbb{R}$
\end_inset

 es una función de utilidad.
\end_layout

\begin_layout Subsection
Minimax
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
Entrada{Juego $(V,A,M,s,F,u)$.}
\end_layout

\begin_layout Plain Layout


\backslash
Salida{Sucesor $s'$ óptimo.}
\end_layout

\begin_layout Plain Layout


\backslash
SetKwProg{Fn}{función}{}{fin}
\end_layout

\begin_layout Plain Layout


\backslash
SetKwFunction{minimax}{minimax}
\end_layout

\begin_layout Plain Layout


\backslash
Fn{
\backslash
minimax{$n$}}{
\end_layout

\begin_layout Plain Layout

	
\backslash
lSSi{$n
\backslash
in F$}{
\backslash
Devolver $u(n)$}
\end_layout

\begin_layout Plain Layout

	
\backslash
lEnOtroCasoSi{$n
\backslash
in M$}{
\backslash
Devolver$
\backslash
max
\backslash
{
\backslash
minimax{v}
\backslash
}_{(n,v)
\backslash
in A}$}
\end_layout

\begin_layout Plain Layout

	
\backslash
lEnOtroCaso{
\backslash
Devolver$
\backslash
min
\backslash
{
\backslash
minimax{v}
\backslash
}_{(n,v)
\backslash
in A}$}
\end_layout

\begin_layout Plain Layout

}
\end_layout

\begin_layout Plain Layout


\backslash
Devolver $s'$ con $(s,s')
\backslash
in A$ y $
\backslash
minimax{s'}$ máximo
\backslash
;
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "alg:minimax"

\end_inset

Algoritmo minimax.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
El 
\series bold
minimax
\series default
 (algoritmo 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:minimax"
plural "false"
caps "false"
noprefix "false"

\end_inset

) intenta maximizar el valor final de 
\begin_inset Formula $u$
\end_inset

 anticipándose a que el oponente intentará minimizarlo, y es óptimo.
 Su complejidad en tiempo es 
\begin_inset Formula $O(b^{m})$
\end_inset

, y su complejidad en espacio es 
\begin_inset Formula $O(bm)$
\end_inset

 si se generan todos los sucesores de un nodo a la vez u 
\begin_inset Formula $O(m)$
\end_inset

 si se generan uno a uno, donde 
\begin_inset Formula $b$
\end_inset

 es el factor de ramificación y 
\begin_inset Formula $m$
\end_inset

 es la profundidad máxima del árbol de búsqueda.
\end_layout

\begin_layout Standard
El algoritmo se puede extender a juegos de más de dos jugadores; en este
 caso la utilidad sería de la forma 
\begin_inset Formula $V\to\mathbb{R}^{n}$
\end_inset

, donde 
\begin_inset Formula $n$
\end_inset

 es el número de jugadores y 
\begin_inset Formula $u(n_{i})$
\end_inset

 es el valor objetivo del nodo 
\begin_inset Formula $u$
\end_inset

 para el jugador 
\begin_inset Formula $i$
\end_inset

, y en vez de 
\begin_inset Formula $M$
\end_inset

 tendríamos una función computable 
\begin_inset Formula $J:V\to\{1,\dots,n\}$
\end_inset

 que indica de quién es el turno y tal que para 
\begin_inset Formula $(i,j)\in A$
\end_inset

, 
\begin_inset Formula $J(j)\equiv J(i)+1\bmod n$
\end_inset

.
 Entonces, en cada nodo 
\begin_inset Formula $u$
\end_inset

 no terminal, nos quedaríamos con el valor minimax de los sucesores con
 coordenada 
\begin_inset Formula $J(u)$
\end_inset

-ésima máxima, y el algoritmo seguiría siendo óptimo aun cuando el juego
 no fuera de suma cero.
\end_layout

\begin_layout Subsection
Poda alfa-beta
\end_layout

\begin_layout Standard
Es posible acelerar el algoritmo minimax con 
\series bold
poda alfa-beta
\series default
 (algoritmo 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:alpha-beta"
plural "false"
caps "false"
noprefix "false"

\end_inset

).
 La idea es que 
\begin_inset Formula $\alpha$
\end_inset

 es el mayor valor encontrado para 
\family typewriter
max
\family default
 y 
\begin_inset Formula $\beta$
\end_inset

 es el menor valor encontrado para 
\family typewriter
min
\family default
.
 Entonces, si 
\family typewriter
MinValor
\family default
 encuentra un 
\begin_inset Formula $v\leq\alpha$
\end_inset

, el valor que devuelva será no mayor a 
\begin_inset Formula $\alpha$
\end_inset

 porque está minimizando, y no merece la pena seguir porque 
\family typewriter
MaxValor
\family default
, que llamó a 
\family typewriter
MinValor
\family default
, descartaría el valor.
 Del mismo modo, si 
\family typewriter
MaxValor
\family default
 encuentra un 
\begin_inset Formula $v\geq\beta$
\end_inset

, termina porque su valor de retorno sería descartado por 
\family typewriter
MinValor
\family default
.
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
Entrada{Juego $(V,A,M,s,F,u)$.}
\end_layout

\begin_layout Plain Layout


\backslash
Salida{Sucesor $s'$ óptimo.}
\end_layout

\begin_layout Plain Layout


\backslash
SetKwProg{Fn}{función}{}{fin}
\end_layout

\begin_layout Plain Layout


\backslash
SetKwFunction{MaxValor}{MaxValor}
\end_layout

\begin_layout Plain Layout


\backslash
SetKwFunction{MinValor}{MinValor}
\end_layout

\begin_layout Plain Layout


\backslash
Fn{
\backslash
MaxValor{$n,
\backslash
alpha,
\backslash
beta$}}{
\end_layout

\begin_layout Plain Layout

	
\backslash
lSSi{$n
\backslash
in F$}{
\backslash
Devolver $u(n)$}
\end_layout

\begin_layout Plain Layout

	$v
\backslash
gets-
\backslash
infty$
\backslash
;
\end_layout

\begin_layout Plain Layout

	
\backslash
Para{$i:(n,i)
\backslash
in A$}{
\end_layout

\begin_layout Plain Layout

		$v
\backslash
gets
\backslash
max
\backslash
{v,
\backslash
MinValor{$i,
\backslash
alpha,
\backslash
beta$}
\backslash
}$
\backslash
;
\end_layout

\begin_layout Plain Layout

		
\backslash
lSSi{$v
\backslash
geq
\backslash
beta$}{
\backslash
Devolver $v$}
\end_layout

\begin_layout Plain Layout

		$
\backslash
alpha
\backslash
gets
\backslash
max
\backslash
{
\backslash
alpha,v
\backslash
}$
\backslash
;
\end_layout

\begin_layout Plain Layout

	}
\end_layout

\begin_layout Plain Layout

	
\backslash
Devolver $v$
\backslash
;
\end_layout

\begin_layout Plain Layout

}
\end_layout

\begin_layout Plain Layout


\backslash
Fn{
\backslash
MinValor{$n,
\backslash
alpha,
\backslash
beta$}}{
\end_layout

\begin_layout Plain Layout

	
\backslash
lSSi{$n
\backslash
in F$}{
\backslash
Devolver $u(n)$}
\end_layout

\begin_layout Plain Layout

	$v
\backslash
gets+
\backslash
infty$
\backslash
;
\end_layout

\begin_layout Plain Layout

	
\backslash
Para{$i:(n,i)
\backslash
in A$}{
\end_layout

\begin_layout Plain Layout

		$v
\backslash
gets
\backslash
min
\backslash
{v,
\backslash
MaxValor{$i,
\backslash
alpha,
\backslash
beta$}
\backslash
}$
\backslash
;
\end_layout

\begin_layout Plain Layout

		
\backslash
lSSi{$v
\backslash
leq
\backslash
alpha$}{
\backslash
Devolver $v$}
\end_layout

\begin_layout Plain Layout

		$
\backslash
beta
\backslash
gets
\backslash
min
\backslash
{
\backslash
beta,v
\backslash
}$
\backslash
;
\end_layout

\begin_layout Plain Layout

	}
\end_layout

\begin_layout Plain Layout

	
\backslash
Devolver $v$
\backslash
;
\end_layout

\begin_layout Plain Layout

}
\end_layout

\begin_layout Plain Layout

Tomar el sucesor $s'$ de $s$ asociado al resultado de 
\backslash
MaxValor{$n,-
\backslash
infty,+
\backslash
infty$}
\backslash
;
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "alg:alpha-beta"

\end_inset

Minimax con poda alfa-beta.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
La eficiencia de minimax con poda alfa-beta es 
\begin_inset Formula $O(b^{m/2})$
\end_inset

 en el caso mejor y 
\begin_inset Formula $O(b^{m})$
\end_inset

 en el caso peor, y la diferencia es muy dependiente del orden en que se
 examinan los sucesores de cada nodo.
 En el caso medio tenemos 
\begin_inset Formula $O(b^{3m/4})$
\end_inset

.
\end_layout

\begin_layout Subsection
Heurísticas
\end_layout

\begin_layout Standard
Buscar hasta los estados terminales no suele ser práctico porque los movimientos
 deben hacerse en una cantidad razonable de tiempo, por lo que se usan heurístic
as 
\begin_inset Formula $h:V\to\mathbb{R}$
\end_inset

 para sustituir a 
\begin_inset Formula $u$
\end_inset

 y un test de corte 
\begin_inset Formula $D\subseteq V\times\mathbb{N}$
\end_inset

 (computable) que decide cuándo parar la búsqueda y aplicar 
\begin_inset Formula $h$
\end_inset

 según el estado y la profundidad.
 
\end_layout

\begin_layout Standard
Una opción es parar a una profundidad fija, elegida para que el tiempo usado
 no exceda lo permitido por las reglas del juego.
 Un test más sofisticado solo para cuando encuentra una posición suficientemente
 estable, en la que sea de esperar que la heurística sea buena.
\end_layout

\begin_layout Subsection
Juegos estocásticos
\end_layout

\begin_layout Standard
Muchos juegos incluyen un elemento aleatorio.
 Esto se puede modelar como que entre un nivel de nodos 
\family typewriter
max
\family default
 y uno de nodos 
\family typewriter
min
\family default
, y viceversa, hay un nivel de nodos de posibilidad cuyos sucesores son
 posibles alternativas, y en minimax, en esos nodos, en vez de tomar el
 máximo o el mínimo, tomamos la media ponderada a la probabilidad de cada
 suceso.
\end_layout

\end_body
\end_document