algorytym genetyczny - funkcja oceniająca

0

Witam, mam za zadanie napisać program wykorzystujący algorytm genetyczny dla problemu komiwojażera, mam problem z funkcją oceniającą. Jedyne co przychodzi mi do głowy i to posortowanie elementów według odległości, wyrzucenie powiedzmy z 10% najgorszych i zastąpienie ich najlepszymi. Wystarczy coś takiego, czy muszę użyć bardziej skomplikowanej metody ?

0

Zależy od przypadku. Najlepiej korzystać z najlepszych metod. Zainteresuj się metodą eliminacji wykorzystywaną do losowania liczb o dowolnym rozkładzie. Można troszeczkę ją zmodyfikować i zrobić z niej ruletkę. To jest chyba najłatwiejsze w implementacji rozwiązanie. Zapewne są lepsze.

0

Wyrzucenie 10% najgorszych i zastąpienie ich najlepszymi to nie jest stricte algorytm genetyczny(!). To strategia ewolucyjna. Często mylone są te dwa podejścia; wszystko, co ma jakieś osobniki, populacje, krzyżowania wrzucane jest do worka z napisem "algorytmy genetyczne". Tymczasem w obu podejściach, mimo że ogólna zasada jest podobna, występują istotne różnice. Najważniejsze z nich:

  1. Reprodukcja: w algorytmach genetycznych N osobników produkuje N potomków, które są następnym pokoleniem. W strategiach ewolucyjnych N osobników produkuje M potomków. Spośród rodziców i potomków (albo samych potomków, ale wtedy M > N) wybierane jest N najlepszych osobników do następnego pokolenia.
  2. Selekcja: w AG selekcja dokonywana jest przed reprodukcją (najlepsze osobniki się reprodukują); w SE selekcja jest po reprodukcji (krzyżują się wszyscy, najlepsi przechodzą do następnego pokolenia)
  3. Mutacje i krzyżowanie: w AG zazwyczaj wszystkie osobniki mają takie samo prawdopodobieństwo krzyżowania i mutacji; w SE prawdopodobieństwo to jest zapisane w chromosomie osobnika, więc każdy ma inne.
  4. Nieprawidłowe rozwiązania (niedopuszczalne, pozadziedzinowe itp.): w AG na takie osobniki nakłada się wysokie kary, tak by nie miały potomstwa i się nie "rozprzestrzeniały", jednak dalej są obecne w populacji; w SE są zwyczajnie usuwane.
    Oczywiście możliwe są odstępstwa od tych założeń, mieszanie ich itp., ale wówczas jest to rozwiązanie hybrydowe. Z doświadczenia wiem, ze SE cieszą się trochę większą popularnością.

1 użytkowników online, w tym zalogowanych: 0, gości: 1