Metody reprezentowania permutacji w kontekście algorytmu genetycznego

Filip Turoboś (PŁ)

Wśród dziedzin, w których algorytmika i sztuczna inteligencja często radzą sobie lepiej z problemami niż kartka i papier poczesne miejsce zajmują problemy natury kombinatorycznej. Ów zbiór problemów zawiera takie zagadnienia NP-trudne jak problem komiwojażera czy Quadratic Assignment Problem. Dla tych problemów przestrzeń rozwiązań dopuszczalnych jest niezwykle duża, a dyskretna natura problemów sprawia, że podejścia typu gradientowego stają się często nieefektywne z uwagi na charakter rozwiązań. Istnieje wiele metod sztucznej inteligencji pozwalających rozwiązywać takie problemy. Mało która jednak jest tak elastyczna i wielozadaniowa, jak Algorytm Genetyczny (GA). Kamieniem węgielnym tej metody jest sposób reprezentowania potencjalnych rozwiązań, który determinuje możliwości ich łączenia i sposoby ich modyfikowania. W jaki sposób można przechowywać w pamięci komputera permutacje? Jak z dwóch permutacji wygenerować trzecią? Na jakiej zasadzie działa Algorytm Genetyczny? Dlaczego można zastosować GA do praktycznie dowolnego problemu i w jakich sytuacjach nie powinniśmy z tej możliwości korzystać? Na te pytania postaramy się odpowiedzieć w trakcie referatu.