Cooperative Simulated Annealing

Allgemein

Das Cooperative Simulated Annealing (COSA) ist eine hybride Heuristik, die sich aus einem Genetischen Algorithmus und Simulated Annealing zusammensetzt. COSA übernimmt von Genetischen Algorithmus die Idee der Population sowie das „Kooperationsprinzip“ des Informationsaustauschs von Individuen. Durch das Simulated Annealing erhält die Heuristik die ausschließliche Nutzung der Mutationsnachbarschaft, d.h. es gibt keine Kreuzung / Crossover im Sinne des Genetischen Algorithmus, und die Akzeptanz der Transition anhand der Metropolis-Wahrscheinlichkeit.

Phasen

Die Phasen des COSA, welche während der Laufzeit wiederholt werden sind:

• Transition: Veränderung eines Individuum durch Mutation
• Akzeptanz: Transition wird bei Verbesserung oder über die Metropolis-Wahrscheilichkeit akzeptiert
• Abkühlung: Bei Bedarf Absenkung der Temperatur

Vorteile

• Lösungsqualität
• Flexibilität

Nachteile

• Zeitaufwand
• Parallelisierung
• Speicherkomplexität