ED-4.2-m11-1.0-Slajd10

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Grupowanie iteracyjno-optymalizacyjne(1)

Grupowanie iteracyjno-optymalizacyjne(1)


Po zdefiniowaniu funkcji kryterialnej pojawia się problem wyboru algorytmu grupowania, który optymalizowałby przyjętą funkcję kryterialną. Jak już wspominaliśmy kilkakrotnie, w celu znalezienia optimum globalnego funkcji kryterialnej należałoby przejrzeć wszystkie możliwe podziały C obiektów na k klastrów i wybrać ten podział, który jest „optymalny”. Można łatwo pokazać, że liczba możliwych podziałów n obiektów na k klastrów wynosi w przybliżeniu k do potęgi n. Stąd, znalezienie „optimum globalnego” funkcji kryterialnej metodą pełnego przeglądu przestrzeni możliwych rozwiązań jest obliczeniowo zbyt kosztowne. Innym rozwiązaniem, o którym już wspominaliśmy, jest zastosowanie, do penetracji przestrzeni rozwiązań, jednej z wielu technik optymalizacji kombinatorycznej: iterative improvement, tabu search, simulating annealing, genetic algorithms, itp. Niestety, efektywność metod optymalizacji kombinatorycznej silnie zależy od charakterystyki penetrowanej przestrzeni rozwiązań.


<< Poprzedni slajd | Spis treści | Następny slajd >>