cluster

CONSTRUCCIÓN DE SOLUCIONES ÁVIDO-ALEATORIAS EN DOS FASES
Las dos fases de este método consiste básicamente en: 1) seleccionar m puntos
(puntos-semilla) de X suficientemente alejados entre sí,que serán considerados los
centroides iniciales y 2) ir asignando los puntos de X a cada uno de los clusters. Cada uno
de estas dos fases se realiza iterativamente, paso a paso, según algúncriterio o función
que ayude a medir la ‘bondad’ de cada elección (punto-semilla en la primera fase, punto y
cluster al que es asignado en la segunda).
Estas funciones de ‘bondad’ nonecesariamente llevan a la mejor solución final,
ya que solo miden la bondad en cada paso concreto. i.e.. a corto plazo. Por tanto.
siguiendo la idea fundamental de los Metaheurísticos GRASP en cadapaso no se va a
elegir necesariamente el mejor elemento según está función,


Por tanto una forma de elección aleatoria pero que tenga en cuenta la función de
‘bondad’, (en este caso H(j)),asegura variedad en las soluciones obtenidas, mantiene
cierto grado de ‘calidad’ en las mismas y en muchas ocasiones superan a la solucion
obtenida por la elección del mejor movimiento (mayorH(j)). Para llevar a cabo esto se
forma una lista de elementos elíte y se elige aleatoriamente uno de esa lista con la misma
probabilidad. Concretamente se forma la lista con los elementos jcuya bondad (H(j))
supera a la máxima (Hmax) por un coeficiente (alfa, que en este caso vale 0’8).


3.2.- Asignación de elementos a clusters
Una vez seleccionados los m puntos semilla estoshacen de centroides iniciales.
La asignación directa de cada punto a su centroide más cercano da lugar a relativas buenas
soluciones iniciales. Sin embargo. se ha creido conveniente mejorardicha asignación
mediante un procedimiento paso a paso que tenga en cuenta la modificación de los
centroides y el aumento real de la función objetivo según se van asignando los elementos.