W referacie omówione zostaną algorytmy genetyczne i ewolucyjne oraz uzasadnienie
dlaczego są stosowane w problemach grafowych.
Związane jest to z ogólną tendencją stosowania algorytmów tzw. sztucznej inteligencji
np. 'tabu search', symulowane wyżarzania, mrówkowych i innych.
Zaletą algorytmów ewolucyjnych jest to, że są ogólne i można je adaptować do rozwiązywania
problemów z różnych dziedzin.
Wadą, że nie uwzględniają istotnych własności teorio-grafowych.
Istnieją propozycje algorytmów hybrydowych.
W referacie omówione będą dwa problemy:
podziału grafu (2-podział, k-podział) oraz
komiwojażera
(kolorowanie omówiono w nowej książce pod red. Kubale: 'Optymalizacja Dyskretna' 2002).
Zostaną przedstawione:
- algorytmy ze specjalizowanymi operacjami ewolucyjnymi,
- przykładowe grafy,
- wyniki obliczeń, w tym analiza wpływu parametrów takich jak:
* rozmiaru populacji,
* prawdopodobieństw mutacji i krzyżowania,
* warunku stopu,
* selekcji elitarnej i innych.
Referat zakończą uwagi i wnioski.
|
|
