Diseño de heurística de path relinking

Solo disponible en BuenasTareas
  • Páginas : 4 (755 palabras )
  • Descarga(s) : 0
  • Publicado : 24 de mayo de 2011
Leer documento completo
Vista previa del texto
Diseñe una heurística de path relinking1

Para utilizar la heurística de path relinking en el modelo de asignación, lo primero que se hace es declarar constante ‘Y’ en la problema principal, quees el vector que contiene las plantas que se abren y las plantas que no y declarar que se carga a través de un archivo “DatOut.txt” que se obtendrá del resultado de la heurística.
La heurísticadiseñada tiene como objetivo general explorar las posibles soluciones que se encuentran entre dos soluciones específicas, normalmente son soluciones sobresalientes obtenidas por medio de algún algoritmo debúsqueda local como Tabu Search o algoritmos Greedy. La idea de path relinking es explorar el camino entre una solución y otra, pasando a través de soluciones que resultan de cambiar algún parámetro dela solución actual para que se parezca más a la solución final. A cada una de las soluciones encontradas se les llama nodos y el camino entre un nodo de origen y uno de destino, es el que define elespacio en donde se buscará la mejor solución. Para poder cambiar de un nodo a otro es necesario definir un vecindario, en nuestro caso son todas las posibles soluciones que impliquen un único cambio enel vector de plantas ‘Y’, es decir, agregar una planta o quitar alguna.
Por último, para tomar la decisión hacia cuál nodo moverse se define una medida de distancia; nosotros, como lo muestran enResende et al, utilizamos la distancia de Hamming, que es el número de cambios que requiere un número binario para convertirse en otro. De esta manera el algoritmo se mueve hacia otro nodo, en suvecindario, que tenga un valor de esta distancia (con el nodo final), menor al nodo actual. Esto se hace iterativamente, actualizando el nodo de origen, hasta que se llegue al nodo final.
Para laimplementación de esta heurística se plantean dos programas de optimización. El primero decide el siguiente nodo dentro del vecindario, minimizando la distancia de Hamming entre éste y el nodo de...
tracking img