Algorytm genetyczny selekcja ruletkowa

Odpowiedz Nowy wątek
2013-03-11 21:54
0

Witam
Chciałbym dla przedstawionego tutaj (http://www.theprojectspot.com[...]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?

Pozostało 580 znaków

2013-03-12 17:39
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?

Pozostało 580 znaków

2013-03-16 14:25
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

edytowany 1x, ostatnio: górek, 2013-03-16 14:27
Oś x iteracje, oś y długość trasy dla najlepszego osobnika w populacji(im krótsza tym lepszy osobnik) - górek 2013-03-16 18:14

Pozostało 580 znaków

2013-03-16 15:12
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?

edytowany 2x, ostatnio: chodnik, 2013-03-16 15:23

Pozostało 580 znaków

2013-03-17 12:04
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ś.

  • log.txt (0 MB) - ściągnięć: 83

Pozostało 580 znaków

2013-03-17 12:18
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.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 2x, ostatnio: MarekR22, 2013-03-17 12:20

Pozostało 580 znaków

2013-03-17 14:33
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.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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