Algorytm genetyczny selekcja ruletkowa

0

Witam
Chciałbym dla przedstawionego tutaj (http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5) kodu dopisać selekcję metodą koła ruletki.
Jadnak to co napisałem nie dziala poprawnie gdyż dostaja trase najdłuższą :(

 public Individual rouletteSelection(Population pop){
  Individual un = null;
  int i=0;
  double p=Math.random(),s=0;
  do{
	un=pop.getIndividual(i);
	s+=un.getProbability();
	i++;
  }while(s<=p);
  return un;	
  }

Suma prawdopodobienstw dla całej populacj daje jeden wiec prawdopodobieństwa są dobrze liczone.
W jaki sposoób zaimplementować tą selekcje zeby wyniki były poprawne?

0

Dodaj sobie wypisywanie wartości s i p w pętli, to może zobaczysz coś oczywistego. Poza tym dość ryzykowne jak dla mnie to while jest. Masz pewność, że nie przekraczasz zakresu populacji?

0

chodnik co to tego while to masz racje przebudowalem to troche żeby nie wykraczać poza zakres populacji.
Nowa funkcjawyglada tak

 public Individual rouletteSelection(Population pop){
  Individual un = pop.getIndividual(0);
  double p=Math.random(),s=0;
  for(int i=0;i<pop.populationSize();i++){
	un=pop.getIndividual(i);
	s+=un.getProbability();
	if(p < s)
		break;
        }
  return un;	
  }

Dodalem jak kazales wypisywanie tego s i p jednak nic "oczywistego" nie widzę, to znaczy może i widze ale to nie jest dla mnie takie oczywiste ;)
Zauwazylem ze wykres najlepszych osobników(najkródsza trasa) w danej populacji jest dość dziwny
1823072095514471e0ae372.png
jezeli tylko zmienę typ selekcji na turniejową to ten wykres pieknie maleje(dla tych samych danych wejściowych).
W dalszym ciagu nie wiem jak mam zaimplementowac tą selekcje :/

pomocy

0

Zacznę od tego, że ten wykres jest zły. Nie ma opisanych osi, a więc nie prezentuje żadnej informacji.
Przedtem miałeś s<=p a teraz masz p<s. Według mnie było dobrze a zmieniłeś na źle.
Z tego zdania powyżej się wycofuję, jeszcze chwilka na przemyślenie :)

Pokaż jakie masz te wartości s i p wypisywane jak wywołujesz funkcję. Nie wiem jaki masz tam rozmiar populacji i ile tych osobników losujesz, ale powiedzmy taki log z 10 wywołań.
Jeszcze zastanawia mnie metoda getIndividual. Czy jak osobnik zostanie wybrany to jest usuwany z populacji? I czy ta metoda zawsze zwraca osobniki w tej samej kolejności?

0

Co do metody getIndividual to zwraca ona osobnika o indeksie podanym w parametrze(populacja to zwyczajna tablica objektów) wiec jezeli wywolasz w ramach jednej populacji kilka razy funkcje z tym samym parametrem to uzyskasz tego samego sobnika i osobnik po wyborze nie jest usuwany.

W zalaczniku log o który prosileś.

0

Zrób to tak.
Najpierw policz sumę wszystkich przystosowań poszczególnych osobników (chyba to jest suma un.getProbability() dla wszystkich osobników).
Potem wybierasz osobnika w następujący sposób:

public Individual rouletteSelection(Population pop, double sum) {
// sum możesz trzymać jako pole bieżącej klasy lub funkcje dla Population
  Individual un;
  double s=Math.random()*sum;
  for(int i=0;i<pop.populationSize();i++){
        un=pop.getIndividual(i);
        s-=un.getProbability();
        if(s<=0)
                break;
        }
  return un; 
}

Źle nazwałeś funkcję getProbability, to nie jest prawdopodobieństwo, ale funkcją przystosowania, która nie jest (bo nie musi) unormowana.

0

Jest taki fragment:
p=0.9430321219043825 s=0.08689478557154999
p=0.9430321219043825 s=0.18224849727777168
p=0.9430321219043825 s=0.2816337314779179
p=0.9430321219043825 s=0.3833076770893761
p=0.9430321219043825 s=0.5081156696673308
p=0.9430321219043825 s=0.5956850960888708
p=0.9430321219043825 s=0.7007445746216591
p=0.9430321219043825 s=0.7977260417113864
p=0.9430321219043825 s=0.8989340787066898
p=0.9430321219043825 s=1.0
Czytam z tego, że w populacji masz 10 osobników. Współczynnik przystosowania każdego z nich jest w granicach od 0.08 do 0.12. Ogólnie rzecz biorąc osobniki mają zbliżony stopień przystosowania, a więc funkcja nie będzie preferować jakoś szczególnie kilku osobników. Na 100 prób dostaniesz wszystkie 10 osobników z liczbą powtórzeń każdego od 8 do 12. Jeżeli to nie jest oczekiwany wynik, to błąd jest raczej gdzieś w wyliczaniu tego przystosowania niż w metodzie ruletkowej.

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