6.7 Paralelización

La parte que consume más recursos es la generación de la secuencia de eventos que consiste en 4 partes:

1. Seleccionar una nueva solución.
2. Calcular las diferencias de costo.
3. Decidir si se acepta.
4. Reemplazar la solución nueva.

Los 3 primeros son independientes. El número de veces que se hace el 4$^o$ varía durante la ejecución del algoritmo (de muchas veces con $c_k$ grande a prácticamente 0 con $c_k$ pequeña).

Una idea es dividir el esfuerzo de generar la cadena de Markov en varios procesadores.

Posibilidades:

• Cada procesador genera su propia cadena de Markov independientemente y se escoge la mejor de todas al final.
• Cada procesador genera pequeñas subcadenas y la mejor solución se comunica a los demás cada determinado tiempo.
• Cada procesador genera una muestra nueva y se escoge la mejor de todas.
• Cada procesador está asociado con una vecindad de estados y calcula el nuevo estado independientemente de los demás manteniendo comunicación para que exista compatibilidad en las fronteras.
• Cada estado del espacio de búsqueda está asociado con un procesador y se actualiza su nuevo estado independientemente de los demás (autómata celular).