Vimos en búsqueda local que podemos definir pozos de atracción.
El problema con búsqueda local es que queda atrapada en mínimos locales y volver a empezar desde varios puntos aleatorios no soluciona el problema.
En realidad lo que se necesita es que se haga un muestreo sesgado, guiando la búsqueda de forma más efectiva.
La idea principal de búsqueda local iterativa es tratar de generar vecinos que nos generen pozos de atracción vecinos (o al menos diferentes).
Una posibilidad es generar un camino de vecinos seleccionados
aleatoriamente,
, donde 
es vecino de
.
Determinar entonces, el primer vecino que pertenece a otro pozo de atracción. Con esto, podríamos ir generando pozos de atracción vecinos. Sin embargo, es un proceso computacionalmente muy costoso, por la cantidad de llamadas a búsqueda local que se requieren.
En lugar de la noción de vecinos en pozos locales, podemos tomar una noción de vecinos más débil.
Dado un mínimo local, se crea una perturbación que pertenezca al espacio de estados legales y que nos genere un nuevo estado.
En ese nuevo estado se aplica búsqueda local. Si el óptimo local encontrado pasa una prueba de aceptación (es mejor), entonces, se acepta, si no se regresa al punto anterior (ver table 4.7).
Búsqueda local iteractiva produce un muestreo con un sesgo adecuado, siempre y cuando las perturbaciones no sean ni muy grandes ni muy pequeñas.
Perturbaciones grandes nos regresan a random restart, mientras que perturbaciones pequeñas no nos sacan del pozo de atracción.
Normalmente búsqueda local iteractiva no es reversible (no regresamos a los mismos sub-espacios explorados antes), sin embargo, si se siguen perturbaciones determinísticas se pueden seguir ciclos cortos.
Por lo mismo a las perturbaciones se les deben incluir aspectos aleatorios o ser adaptivas para evitar ciclarse.
El algoritmo de ILS tiene varios componentes que pueden afinarse.
Solución Inicial: puede ser aleatoria o ser la obtenida con un algoritmo greedy o glotón (normalmente dá mejores resultados).
Criterio de Aceptación: Si no mantemos historia de lo
ocurrido, el criterio de aceptación simplemente considera la
diferencia en costos entre 
y 
.
El criterio de aceptación en tal caso puede ser determinístico o se puede ajustar empíricamente conforme se soluciona el problema (por ejemplo, como se usa en recocido simulado).
El criterio de aceptación se usa para establecer un balance entre explotación (intensificación) y exploración (diversificación).
Se favorece la explotación si sólo se aceptan mejores soluciones.
Se favorece la exploración si siempre se hacen perturbaciones independientemente de su costo.
Si después de un cierto tiempo no se han logrado mejores resultados, se pueden empezar ILS desde una nueva solución.
Método de Perturbación: puede contener tanta información dependiente del dominio como se quiera/tenga.
El criterio básico es que el punto inicial obtenido a partir de la perturbación debe de ser un excelente punto inicial para búsqueda local.
La perturbación es el esquema que tiene ILS para escapar de mínimos locales.
La fuerza de la perturbación está definida por el número de cambios realizados sobre la solución.
Por ejemplo en TSP es el número de ligas que se cambian en un tour.
Muchas veces un movimiento aleatorio sobre un nivel superior usado en la estructura de la vecindad es suficiente.
Como no se sabe de antemano cuál puede ser una buena perturbación, se podría tratar de explotar la historia, ya sea en el contexto de Tabu search o de VNS (visto en la sección 4.3).
Velocidad: Se ha visto que el tiempo empleado en 
búsquedas locales dentro de búsqueda local iterativa, es mucho
menor que hacer búsquedas locales con re-inicios aleatorios.
Búsqueda Local: El método usado de búsqueda local en general puede ser cambiado por prácticamente cualquiera de los que estamos viendo y vamos a ver.
