Komiwojażer Genetycznie

[Daniel.l]

Mam problem ze znalezieniem materiałów (a właściewie implementacji w C++) do problemu komiwojażera rozwiązywanego metodą algorytmów genetycznych. jeśli znacie jakąś stronkę -link mile widziany :P

[mathias79]

Problem komiwojażera i jego rozwiązanie za pomocą alg. gen jest opisanie w książce Z.Michalewicza. Co do implementacji w C++ to już chyba sam musisz pokombinować, bo nie spotkałem się z tego typu publikacjami (choć niewątpliwie istnieją ;-) )

[spicum]

Daniel.l z czystej ciekawości zapytam po co angazowac alg. gen. do komiwojazera ? - alg. gen. zatrudnia sie z tego co pamietam do heurystyk o ktorych niewiele wiemy.

a tutaj istnieja DUZO lepsze algorytmy.

Chocby "Simulated Annealing" czy "Lin-Kernighan Algorithm".

[mathias79]

Moim zdaniem zaangażowanie alg.gen. w komiwojażera nie jest złym pomysłem. Co prawda symulowane wyżarzanie faktycznie jest ok ale czy DUŻO lepsze ? Tego nie wiem. Wiem że alg.gen. się sprawdzają zarówno w rozwiązywaniu tego problemu jak i wiele innych co stawanowi w sumie ich siłę. A co do tego że stosuje się je do heurystyk o których niewiele wiemy to też tak nie do końca. W końcu reprezentacja danych oraz funkcja oceny musi jasno wynikać z właściwości problemu itp ... fakt że dokładnie nie musimy pilnować algorytmu i tego co wyprawia z naszymi danymi - choć i to nie do końca prawda

[spicum]

Robilismy na studiach taki projekt wlasnie. I jakos te robione genetykami (a bylo ich sporo - kolo 30%) plasowaly sie od polowy listy wynikow w dol. SA byly srednio 2 razy szybsze, LK srednio 3 razy szybsze. Nie uwzgledniam wogole tych genetykow ktore dawaly 2-3 rzedy slabsze wyniki ...

[mathias79]

nigdy nie porownywałem tych algorytmów więc nie będę sie spierał. Ja akurat zajmuję się AG i w moich zadaniach sprawują się całkiem fajnie. Oczywiscie AG nie są idealne a ich działanie jest ciagle badane. Ważne są użyte funkcje selekcji, parametry krzyżowania i mutacji oraz wielkość populacji itp ... wiele rzeczy do zbadania. Fakt konieczności przeprowadzania dodatkowych badań czy uzgledniania dodatkowych parametrów (etalitaryzm) moim zdaniem negują zaletę AG polegającą iż nie trzeba niby się wgłębiać w dziedzine problemu ... niby tak bo mutacji czy selekcji jest wszystko jedno na czym pracuje ale coś za coś. Trzeba sprawdzać przy jakich parametrach będzie to działać najbardziej wydajnie.

Pozdrawiam

[spicum]

AG jest rzeczywiscie dosc uniwersalny. Dlatego tez nie jest idealny tam gdzie istnieja bardziej specyficzne, uwarunkowane algorytmy.

Jak pisalem juz wczesniej AG uzywa sie tam gdzie nie wiemy za duzo o temacie.

Co do parametryzacji - oczywiscie prawie zawsze da sie dobrac parametry - niestety na ogol bedzie to dobranie do konkretnego przypadku a nie do calego problemu - tu najczesciej widac skutecznosc algorytmow specyficznych dla problemu.