Znaczenie projektu

Znaczenie projektu. Automatyzacja procesu kompozycji usług sieciowych jest w otatnich latach przedmiotem bardzo intensywnych badań, o czym świadczy znaczna liczba publikacji poświęconych temu zagadnieniu (np. [KGS05], [Rao04], [RKM04], [Rsu04], [RIP07], [SKo03]). Jak dotąd do problemu planowania i kompozycji usług sieciowych stosowano różne metody: od bazujących na algorytmach przeszukiwania przestrzeni stanów (w tym wspieranych przez heurystyki [BGe01]) i wykorzystujących grafy [BFu97], do technik wykorzystujących programowanie w logice [Pfo02].
W kontekście bieżącego projektu należy zwrócić szczególną uwagę na prace wykorzystujące metody znane z dziedziny automatycznej weryfikacji oraz algorytmy ewolucyjne. Ze względu na duże przestrzenie rozwiązań z jakimi mamy do czynienia w dziedzinie planowania i kompozycji usług sieciowych, w pierwszej grupie należy wyróżnić zwłaszcza te prace, które wykorzystują metody symboliczne, jak np. MIPS [EHe00], BDDPLan[HSt00], czy UMOP[JVe00], bazujące na Binarnych Diagramach Decyzyjnych (Binary Decision Diagrams – BDD) [Bry86], a także podejścia wykorzystujące narzędzia do rozwiązywania problemu spełnialności formuł logicznych (Boolean satisfiability problem – SAT)[BCC+99, ESo04, PDa07], np. BLACKBOX[KSe98], czy LPG[GSe02].
Drugą z omawianych grup stanowią procedury planowania bazujące na algorytmach ewolucyjnych. W pracy [BKZ+05] wykorzystano kombinację algorytmu genetycznego oraz metody Tabu Search, dzięki czemu uzyskano zwiększenie różnorodności populacji, a w efekcie zdolność algorytmu hybrydowego do ucieczki z minimum lokalnego. Znaną wadą algorytmów genetycznych jest ich skłonność do utykania w lokalnym minimum. Spowodowane jest to głównie przez operator selekcji
proporcjonalnej, ktorego zadaniem jest wybór osobników z bieżącej populacji z prawdopodobieństwem proporcjonalnym do ich stopni dopasowania. Po wykonaniu pewnej liczby iteracji algorytmu, w populacji będą znajdować się osobniki podobne do siebie, w związku z czym operator krzyżowania wygeneruje osobniki o również podobnym genotypie. Modyfikacja algorytmów genetycznych poprzez wprowadzenie dowolnej techniki zwiekszającej różnorodność populacji, powoduje zwiększenie skuteczności ich działania. Z kolei w pracy [LJB+03] przedstawiono propozycję zastosowania algorytmu genetycznego wykorzystującego binarną reprezentację potencjalnych rozwiązań. Ponieważ wraz ze wzrostem liczby rozważanych usług rosła również długość chromosomu, wydajność metody okazała się niewystarczająca przy
zastosowanym kodowaniu osobników.
Jednak bezpośrednią inspiracją do podjęcia niniejszego projektu jest szereg prac wykorzystujących połączone metody weryfikacji modelowej i algorytmy ewolucyjne. W pracy [KPe08] autorzy posługują się programowaniem genetycznym (Genetic Programming) do generowania programów komputerowych będących rozwiązaniem problemu wzajemnego wykluczania. Następnie potencjalne rozwiązania są ewaluowane przy wykorzystaniu procedur weryfikacji modelowej. Wyniki eksperymentalne pokazują dobrą zbieżność tego podejścia, umożliwiającego nawet znalezienie optymalnego rozwiązania. Praca [KPe11] opisuje zastosowanie podobnej metody do rozwiązania problemu wyboru lidera (the leader election problem). Z kolei w [Joh07] zasugerowano użycie logiki temporalnej do obliczania funkcji dopasowania osobnika, bazując na liczbie własności spełnianych przez potencjalne rozwiązanie problemu. Podsumowując: wierzymy, że nowy, hybrydowy algorytm łączący mocne strony obydwu wymienionych technik będzie jeszcze bardziej skuteczny, niż każda z tych metod zastosowana oddzielnie.