4.2.2 Random Restart y Multistart Methods

Next: 4.2.3 Guided Local Search Up: 4.2 Búsqueda Local (Local Previous: 4.2.1 Fast Local Search

4.2.2 Random Restart y Multistart Methods

La forma más simple para mejorar búsqueda local es repitiendo el proceso varias veces con puntos iniciales aleatorios (random restart).

La idea es lograr diversidad y salir de mínimos locales al volver a empezar en otra zona.

Aunque fácil de implementar su efectividad decrece al aumentar la complejidad del problema.

Estudios empíricos y argumentos generales indican que la probabilidad de encontrar una solución de bajo costo con muestreo aleatorio decrece al aumentar el tamaño de búsqueda.

Para los algoritmos de construcción, podemos hablar de estrategias de re-inicio (multistart). Estas tienen dos fases: (i) generar (construir) una solución y (ii) tratar de mejorar esa solución (ver tabla 4.2).

**Tabla 4.2:** Algoritmo genérico de re-inicio.
$\begin{table} \begin{tabbing} 123\=123\=123\= \kill \textbf{procedimiento} Multi... ...\leftarrow s'$ \\ \textbf{return} Mejor Soluci\a'{o}n \end{tabbing}\end{table}$

Los métodos de re-inicio se pueden sofisticar y en general caracterizar por:

Uso de memoria: se usa para identificar buenas o malas soluciones anteriores.
Aleatoriedad: depende de si las soluciones con las que se empiezan se generan aleatoriamente o no.
Grado de reconstrucción: indica los elementos que permanecen fijos entre una generación y la siguiente.

Varias de las técnicas que vamos a ver podemos clasificarlas como técnicas de re-inicio.

Next: 4.2.3 Guided Local Search Up: 4.2 Búsqueda Local (Local Previous: 4.2.1 Fast Local Search

Eduardo Morales Manzanares 2004-11-02