ED-4.2-m11-1.0-Slajd10
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ń.
