Student: A
ukasz Rychter Warszawa, 25.01.2010
Nr indeksu: 218882
Grupa studencka: 3M2
Data lab. 22.01.2010 14.15-16.15
Prowadzący: dr inż. Dominik Kasprowicz
Laboratorium AISDE
Sprawozdanie z dwiczenia 6:
Algorytmy optymalizacji globalnej
1) Zadanie i cel ćwiczenia
Ćwiczenie ma na celu zapoznanie studenta z algorytmami heurystycznymi optymalizacji globalnej. Analizowanym zadaniem optymalizacyjnym jest problem podziału grafu.
W dwiczeniu badane są 2 algorytmy  dedykowany do tego zadania algorytm Kernighana-Lina oraz algorytm heurystyczny ogólnego zastosowania  symulowanego
odprężania.
2) Wykonanie poleceń
Do moich zadao należało wykonanie zadania 6 lub 7. Wybrałem zadanie 7:
Zad 7)  Dla grafu o kilkudziesięciu/kilkuset wierzchołkach i kilku/kilkunastu tysiącach krawędzi dokonujemy podziału algorytmem Kernighana-Lina, a następnie
algorytmem symulowanego odprężania z takimi wartościami parametrów (p, N, s, rodzaj funkcji schładzania, ewentualne własne adaptacje itp.), jakie wydają nam się
najlepsze.)
Do badao użyłem grafu o 300 wierzchołkach i 40000 krawędziach.
A) Wykreślamy wartośd funkcji celu w kolejnych krokach algorytmu Kernighana-Lina. Ile było kroków? W którym kroku zostało wyznaczone optimum? Czy pracę
algorytmu można było przerwad w momencie, gdy wartośd funkcji celu zaczęła rosnąd?
Funkcja celu
1610000
1600000
1590000
1580000
1570000
1560000
1550000
1540000
1530000
1520000
1510000
0 20 40 60 80 100 120 140
Algorytm wykonał 150 kroków. Optimum zostało wyznaczone w 55 kroku. Funkcja celu zaczęła rosnąd w 50 kroku. Gdybyśmy wtedy przerwali obliczenia i za optimum
przyjęli wartośd z 49 kroku uzyskalibyśmy wynik o 1475 gorszy od optimum (około 0,1% co w wielu przypadkach może byd akceptowalną niedokładnością, biorąc pod
uwagę, że uzyskalibyśmy wynik w ciągu 3 krotnie niższej liczby iteracji).
B) Porównujemy wartośd funkcji celu w optimach znalezionych przez oba algorytmy oraz czas pracy każdego z nich. Co można powiedzied o obu algorytmach?
Dla algorytmu symulowanego schładzania użyłem parametrów bliskich domyślnie ustawionych w programie, ponieważ dawały najlepsze wyniki.
T 1.0
a 0.9
p 1
N 400
s 50
oraz domyślna funkcja schładzająca.
Algorytm Kernighana-Lina:
Koszt ostatecznego podziału: 1514969
Obliczenia trwały 47 ms
Algorytm Symulowanego Schładzania:
Koszt ostatecznego podziału 1505493
Obliczenia trwały 9234 ms (!)
Jak widad algorytmem Symulowanego Schładzania możemy uzyskad wyniki nawet lepsze niż dedykowanym do rozważanego problemu podziału grafu algorytmem
Kernighana-Lina. Czas obliczeo dla algorytmu Symulowanego Schładzania jest jednak wielokrotnie większy i ponadto aby uzyskad optymalne wyniki należy dobrad
odpowiednie parametry konfiguracyjne algorytmu, które w sposób inny niż doświadczalny trudno przewidzied. Strata w jakości wyniku alg. K-L jest rzędu 1% lub nawet
mniejsza (ok. 0.6% w powyższym przykładzie). Tak więc biorąc pod uwagę jego znacznie krótszy czas działania (oraz jak zostanie pokazane w dalszym podpunkcie możliwośd
istotnego poprawiania własnego wyniku) jest on zazwyczaj lepszym wyborem dla rozwiązywania problemu podziału grafu.
C) Graf po podziale algorytmem Kernighana-Lina poddajemy dalszej optymalizacji  tym samym algorytmem lub metodą symulowanego odprężania. Czy funkcja
celu uległa poprawie?
Po pierwszym wywołaniu algorytmu Kernighana-Lina uzyskujemy wynik: 1514969
Po kolejnej optymalizacji:
- algorytmem Kernighana-Lina: 1506813
- algorytmem Symulowanego Odprężania(dla T=1): 1519756
- algorytmem Symulowanego Odprężania(dla T=0.1): 1504105
Jak widad kolejne wywołania algorytmu Kernighana-Lina mogą poprawiad swój własny wynik. Również Symulowane odprężanie może poprawiad wynik uzyskany z
algorytmu Kernighana-Lina, należy jednak dobrad odpowiednie parametry, gdyż dla nieodpowiednich wynik może byd także pogarszany (w przypadku jak wyżej zbyt wysoka
temperatura początkowa może powodowad wyskakiwanie ze znalezionego minimum, natomiast obniżenie temperatury  poprawianie wyniku w zakresie lokalnym
znalezionego minimum. Zbyt niska wartośd początkowej temperatury jednakże też powoduje oddalanie się od optimum).
3) Tabele danych
Dane do wykresu z podpunktu a)
Funkcja Funkcja Funkcja Funkcja Funkcja
Krok Krok Krok Krok Krok
celu celu celu celu celu
1 1604792 36 1525742 71 1517216 106 1545649 141 1584794
2 1599441 37 1524760 72 1517829 107 1546755 142 1585810
3 1594775 38 1524178 73 1518396 108 1547984 143 1587372
4 1590733 39 1523163 74 1518817 109 1549327 144 1588952
5 1587167 40 1522441 75 1519293 110 1550609 145 1590336
6 1583530 41 1521793 76 1519749 111 1551888 146 1591659
7 1579893 42 1521126 77 1520170 112 1552978 147 1593913
8 1576528 43 1520485 78 1520793 113 1554102 148 1596183
9 1573006 44 1519630 79 1521523 114 1555453 149 1598851
10 1569763 45 1519045 80 1522041 115 1556487 150 1601882
11 1566733 46 1518247 81 1522674 116 1557355
12 1563904 47 1517572 82 1523449 117 1557948
13 1561452 48 1516884 83 1524306 118 1558400
14 1559090 49 1516444 84 1525468 119 1558714
15 1556562 50 1516524 85 1526317 120 1559523
16 1553845 51 1516209 86 1527328 121 1560296
17 1551786 52 1516065 87 1528273 122 1561092
18 1549865 53 1515840 88 1529385 123 1561860
19 1548036 54 1515308 89 1530575 124 1563166
20 1546071 55 1514969 90 1531502 125 1564328
21 1544325 56 1515189 91 1532536 126 1565537
22 1542715 57 1515327 92 1533294 127 1566706
23 1541200 58 1515477 93 1534203 128 1567990
24 1539792 59 1515494 94 1535220 129 1569415
25 1538352 60 1515461 95 1536064 130 1570647
26 1536519 61 1515331 96 1536748 131 1571714
27 1534998 62 1515200 97 1537582 132 1573063
28 1533718 63 1515368 98 1538452 133 1574290
29 1532350 64 1515662 99 1539584 134 1575357
30 1531114 65 1516014 100 1540610 135 1576748
31 1530381 66 1516330 101 1541382 136 1577929
32 1529409 67 1516792 102 1542513 137 1579448
33 1528612 68 1516998 103 1543241 138 1580712
34 1527935 69 1516523 104 1543956 139 1581970
35 1526912 70 1516747 105 1544950 140 1583475