Siguiente: Beneficios en la Optimización Anterior: Sobre el Uso de Arriba: Sobre el Uso de

Beneficios en Escape de Óptimos Locales

En el contexto de FANS, si bien la definición del vecindario operativo es fija, la idea de cambiar el operador de modificación $\mathcal{O}$ es inducir un cambio en las soluciones que se pueden obtener a partir de cierta solución de referencia $s$ dada.

Si pensamos en un problema con soluciones binarias, una solución actual $s$, un operador $\mathcal{A}$ que modifique $k$ variables, y un operador $\mathcal{B}$ que modifique $k+1$ variables, entonces resulta que $\mathcal{N}_{\mathcal{A}}(s)$ $\neq\:$ $\mathcal{N}_{\mathcal{B}}(s)$ . Un ejemplo trivial es el siguiente: supongamos que $s =0000$, $\mathcal{A}$ modifica una variable y $\mathcal{B}$ modifica dos, entonces los vecindarios inducidos son: $\mathcal{N}_{\mathcal{A}}(s) = \{1000,0100,0010,0001\}$ y $\mathcal{N}_{\mathcal{B}}(s) = \{1100,1010,1001,0110, 0101,0011\}$

Si imaginamos el espacio de búsqueda como un grafo, como se propone en [20], la situación se representa en la Fig. 3, donde cada nodo de ambos grafos representa un string binario de cuatro elementos. Ahora siendo el nodo $s =0000$ y $\mathcal{A}$, $\mathcal{B}$, operaciones de modificación como las definidas anteriormente, el grafo de la izquierda representa las soluciones accesibles desde $s$ mediante la operación $\mathcal{A}$. La accesibilidad queda reflejada por la existencia de aristas. Si cambiamos la operación por $\mathcal{B}$, obtenemos el grafo de la derecha, donde se han eliminado las aristas previas y se han dibujado las nuevas que conectan $s$ con aquellos nodos en $\mathcal{N}_{\mathcal{B}}(s)$.

Figura 3: Efecto sobre el espacio de búsqueda ante un cambio de operador

Por lo tanto, se observa que un cambio de operación modifica las aristas del grafo, o espacio de búsqueda, modificando el conjunto de soluciones accesibles. La consecuencia de este enfoque es clara: que una solución sea óptimo local bajo un operador, no implica que lo siga siendo cuando el operador se cambia, y es ésta la razón que justifica la utilización de varios operadores en el proceso de búsqueda.