Gran parte de las metaheurísticas y heurísticas tienen el paso «Elegir un nuevo vecino/solución» pero no entran mucho en detalle de cómo elegirlo. La papeleta generalmente se resuelve eligiendo el vecino con el mejor fitness o uno aleatorio. Pero no son las únicas estrategias y dependiendo el tipo de espacio de búsqueda tampoco son las mejores. Vamos a ver algunas alternativas.

¿Qué es un vecino? La respuesta depende del espacio de búsqueda y el tipo de problema y la función usada para «generar» a los vecinos. La forma más generica de definirlo que se me ocurre seria: «Son vecinos de una solución S todas aquellas soluciones que se pueden alcanzar desde S». En algunos casos queda claro quienes son los vecinos, por ejemplo en un grafo. En otros la definición de que es un vecino se va a tener que ajustar como un parámetro más del algoritmo. Por ejemplo cuando definimos el vecino de una solución como todas aquellas soluciones que estén a una distancia igual o menor que d. En este caso d se convierte en un parámetro más a tener en cuenta.

Hay que distinguir entre dos tipos de vecindarios:

• Poco poblados: cuando el número de vecinos es limitado y podemos calcular el fitness de todos. Suelen ser los vecindarios asociados a problemas combinacionales o a valores discretos. Eso no quiere decir que este tipo de problemas no puedan crecer tanto que se conviertan en el siguiente tipo de vecindario. Ojo al detalle de poder calcular el fitness, si la función que lo calcula es muy costosa puede resultar más rentable tratarlos como si fueran vecindarios muy poblados.
• Muy poblados: cuando el número de vecinos es infinito o tan grande que es imposible (o su coste en tiempo es demasiado alto) recorrerlos todos. Generalmente corresponde a espacios de soluciones continuos.

Antes de empezar con estrategias  complicadas empecemos por la  y más simple y menos costosa que además funciona en ambos tipos de vecindarios. Elegir un vecino cualquiera al azar. El problema es que puede retrasar mucho la convergencia a un óptimo.

Las estrategias son distintas dependiendo del tipo de vecindario. Vamos a empezar por los vecindarios poco poblados. En este caso las estrategias más simple que se nos puede ocurrir es la de escoger el mejor: de todas las opciones buscamos la que tiene mejor fitness y la elegimos. El problema de asta estrategia es que dificulta la exploración. Pero  por otro lado reduce el tiempo que cuesta llegar al óptimo, aunque aumenta el riesgo que sea un óptimo local. Un pequeño cambio puede solucionarlo. Elegimos una al azar pero no todas tienen la misma probabilidad sino que la probabilidad de seleccionar una solución es proporcional a su fitness.

Para los vecindarios muy poblados podemos hacer un truco para seleccionar los vecinos como si fueran vecindarios poco poblados, elegimos n vecinos al azar y luego aplicamos la selección sobre esos n vecinos como si fueran los únicos del vecindario.

En el caso de espacios de soluciones continuas se suelen elegir como vecinos cualquier solución que esté a una distancia D o menor. Pero esta es la versión más simple, en lugar de elegir todos los vecinos a una distancia D con igual probabilidad podemos hacer que sea más probable seleccionar los que más cerca están o los más lejanos o los que estén a una distancia intermedia. Incluso fijar una distancia mínima. Jugando con estos valores podemos alterar el comportamiento del algoritmo (exploración/convergencia) sin modificar sus valores.

Otra forma de mejorar la selección de vecinos puede ser priorizar la dirección en la que antes ya has encontrado una buena solución esperando que sigamos mejorando en esa dirección. Por ejemplo supongamos que hemos ido del punto (5, 5) al (6, 8). Eso significa que hemos sumado el vector (1, 3). Lo primero que podríamos hacer es mirar el punto (7, 11) = (6, 8)+(1, 3). Es decir repetir el mismo paso y a partir de ahí mirar cerca de ese punto. El problema de hacerlo así es que acabamos repitiendo pasos iguales cuando realmente lo que nos interesa es solo la dirección. ¿Cómo extraerla?. Dividimos cada componente del vector por la distancia recorrida. El vector que hemos sumado ha sido (1,3). La distancia es la raíz cuadrada de la suma del cuadrado de cada elemento. SQRT(1^2+3^2) = 3.1622… Así que la dirección sería (1/3.1622, 3/1622) = (0.31, 0.93). Ya lo tenemos. Ahora podemos avanzar la distancia que queramos en esa dirección. Solo hemos de multiplicar la distancia por cada uno de los valores del vector dirección. Podemos avanzar en esta dirección hasta que deje de mejorar.

Pero estos cálculos pueden ser usados de otra manera. Si elegimos varios vecinos al azar y dividimos lo que mejora la solución entre la distancia del paso tendremos una manera de estimar en qué dirección las soluciones mejoran más rápido. Estamos calculando una aproximación del gradiante. En este caso podemos priorizar los que más rápido varíen.

Hay una versión de esta selección que se usaba originalmente para la metaheurística hill climbing que no requiere cálculos. Si tenemos una solución con múltiples coordenadas modificamos una a una hasta que deje de mejorar en esa coordenada. En el ejemplo anterior sería el caso de usar el vector dirección (1,0) hasta que deje de mejorar y luego usar (0,1). Tiene la desventaja de que puede quedarse atrapado cuando los mejores vecinos están en las diagonales.

Una última mejora es guardar un histórico de soluciones ya seleccionadas para evitar elegir una ya elegida o muy cercana (lo que sería el equivalente a andar en círculos). Según el coste en memoria de almacenarlas y en tiempo de compararlas puede ser mejor almacenar solo las últimas. Esta opción solo es válida cuando la selección del siguiente vecino es determinista, por ejemplo eligiendo el de mayor gradiante o cuando se inspeccionan todas las opciones y lo más probable es que se elija el mismo vecino la última vez que se «visitó» esa solución. Guardar información de los vecinos ya visitados no puede ahorrar «dar vueltas» y reducir el coste computacional.