Laboratorium 6

Algorytmy optymalizacji globalnej

    Ćwiczenie ma na celu zapoznanie się z algorytmami heurystycznymi optymalizacji globalnej. Zadaniem optymalizacyjnym będzie problem podziału grafu (ang. graph partitioning) zdefiniowany następująco: zbiór wierzchołków grafu G należy podzielić na dwa równoliczne podzbiory w taki sposób, by suma wag krawędzi łączących te podzbiory była minimalna.
    Zaprezentowane zostaną dwa algorytmy: Kernighana-Lina oraz algorytm oparty na symulowanym odprężanu (ang. simulated annealing). Pierwszy z nich jest dedykowany do rozwiązywania problemu podziału grafu. Natomiast symulowane odprężanie jest jedną z najpopularniejszych metod heurystycznych ogólnego zastosowania. W ćwiczeniu badany będzie wpływ parametrów algorytmu wykorzystującego symulowane odprężanie na jakość znalezionego rozwiązania. Eksperymenty będą obejmować m.in. przebieg temperatury w czasie.

    Zakłada się znajomość: Przed przystąpieniem do ćwiczenia należy obowiązkowo zapoznać się z instrukcją do ćwiczenia i kodami źródłowymi. Przed przystąpieniem do pisania sprawozdania należy się zapoznać z informacjami_dodatkowymi.
Instrukcja do ćwiczenia Źródła


Wyślij sprawozdanie: