Metody szukania
Do podstawowych metod szukania minimum funkcji należą między innymi:
Symulowane wyżarzanie - opis pdf
Szukanie optymalnego cyklu komiwojażera:
wyzarz_tsp.m
przykładowe rozmieszczenia miast:
Treść zadania:
1. Przekształcić skrypt wyzarz_tsp.m w ten sposób, żeby służył do szukania minimum funkcji dwóch zmiennych.
2. Uzależnić poprawkę rozwiązania od temperatury.
3. Sporządzić wykres zbieżności algorytmu oraz nanieść na wykres funkcji 2-wymiarowej drogę prowadzącą do rozwiązania końcowego.
4. Dobrać takie wartości paramentrów algorytmu, żeby w co najmniej 4 przypadkach na 5 szukanie kończyło się znalezieniem minimum globalnego.
Zestawy:
Algorytmy genetyczne
Informacje ogólne:
Algorytmy genetyczne służą do szukania optymalnych rozwiązań zadań z różnych dziedzin w oparciu o populację rozwiązań (osobników), funkcję oceny rozwiązań (przystosowania osobników) oraz operacje genetyczne służące do selekcji rozwiązań i manipulowania parametrami zakodowanej (genotypowej) postaci każdego z rozwiązań. Ze względu na funkcję oceny można sprowadzić algorytm genetyczny do zadania optymalizacji funkcji (maksymalizacji oceny). Podstawowe operacje genetyczne:
Reprodukcja ogólnie zwiększa liczebność rozwiązań lepszych kosztem gorszych. Najczęściej stosowane metody reprodukcji to reprodukcja ruletkowa, rangowa i turniejowa.
Krzyżowanie pozwala na znalezienie rozwiązania zawierającego najlepsze cechy innych rozwiązań. W przypadku poszukiwania minimum funkcji można np. wymieniać wartości odpowiedających sobie współrzędnych lub wyznaczaćpunkty leżące na odcinku łączącym rozwiązania rodzicielskie.
Mutacja powinna umożliwiać znajdowanie nowych cech, w przypadku szukania minimum funkcji, nowych wartości współrzędnych, które mogą być nieosiągalne w inny sposób.
Inne modele genetyczne pomagające w zachowaniu najlepszych rozwiązań lub w zachowaniu różnorodności populacji:
Model elitarny - część populacji (najlepsze osobniki) przechodzi bez zmian do populacji potomnej.
Model niszowy - funkcja oceny każdego z rozwiązań jest uzupełniana o człon faworyzujący rozwiązania w dużym stopniu różniące się od pozostałych. To pozwala na utrzymanie większej różnorodności populacji (wypełnienia nisz) w celu zwiększenia szansy znalezienia właściwego obszaru poszukiwań (w niektórych przypadkach) lub pozwala zapobiec utracie istotnych rozwiązań jeśli inne rozwiązania są w jakiś sposób od nich zależne (np. stanowią podrozwiązania).
Model ze ściskiem - w ramach reprodukcji nowe rozwiązania zastępują rozwiązania, które mają jednocześnie małą wartość i są do nich podobne. Cel jest taki sam, co w modelu niszowym
Szukanie minimum funkcji:
wykres_fun.m - wykres funkcji