Algorytm genetyczny - tworzenie chromosomu

0

Cześć, mam problem ze stwarzaniem chromosomu w problemie Komiwojażera. Jako input mam listę z miastami List<City>

public class City {

    private double x;
    private double y;
}

Teraz chcę zakodować je w ten sposób żeby indeks danego miasta wskazywał na miasto w liście o konkretnym indeksie. Moja klasa Chromosome:

public class Chromosome {

    private List<Integer> listOfCities = new ArrayList<>();
    private double distance = 0;
    private double fitness = 0;
}

Wygląda to mniej więcej tak:
Mając listę z indeksami (7 5 1 6 9 2 8 4 3) zaczynając od indeksu w tej liście nr 0:

  • 7 -> 8
  • teraz 8 -> 4
  • potem 4 -> 6
    .
    .
    .
    Tak że powstaje nam ścieżka 7-8-4-6-2-5-9-3-1.
    Potem na podstawie takiej listy liczę sumaryczny dystans miedzy miastami i na tej podstawie obliczam funkcję przystosowania.
    Nie wiem jednak jak, stworzyć Chromosom aby nie powstały cykle lub po wpisaniu do tablicy kolejnych indeksów zrobić potem Collections.shuffle(lista).
    Macie jakieś dobre podpowiedzi jak powinienem to zrobić?
0

Mając listę z indeksami (7 5 1 6 9 2 8 4 3)

Potraktuj to jak ścieżkę 7->5->1->...

0
  1. Generalnie generujesz sobie kolekcję zawierającą indeksy po kolei od 0 do N (gdzie N - liczba miast).
  2. Następnie robisz Collection.shuffle, w wyniku mamy losowo te elementy w kolekcji i jest to nasz chromosom należący do populacji wejściowej. Tych chromosomów (osobników, bo w tym kodowaniu chromosom = osobnik) mamy X - ile sobie założymy.
  3. W ramach iteracji dokonujesz mutacji/krzyżowania - zależnie od implementacji to może wyglądać różnorodnie szczególnie kryżowanie.
  4. Funkcja dopasowania oblicza dystans pomiędzy każdymi elemntami + dodaje dystans pomiędzy pierwszym i ostatnim elementem kolekcji.
0

Ogólnie u mnie wygląda to tak:

  1. Wybieram wielkość populacji i długość chromosomu(List<Ciyt>)
  2. Generuje chromosom poprzez mechanizm wskazany przez @mariano901229(w jego poście pkt 1 i 2) i obliczam odległość pomiędzy miastami.
  3. Tak generuje N razy chromosomy do mojej populacji
  4. Wybieram pomiędzy selekcjami:
  • ruletkową
  • rangową
  • turniejową
  1. Z wylosowanych chromosomów z populacji pierwotnej wybrałem 2 najlepiej przystosowane chromosomy do procesu krzyżowania
  • jednopunktowego
  • dwupunktowego
  1. Robię mutację
  2. powyższe kroki powtarzam N razy w zależności od ilości generacji populacji
  3. porównuje wynik z populacji początkowej z najlepiej przystosowanym osobnikiem w n generacjach.

Teraz mam pytanie, program ten piszę w spring boocie, pytanie czy do generowania grafu jest jakaś fajna biblioteka czy trzeba się jakoś przebić i zrobić to w js/html?

0

Skoro chromosom jest permutacją to jak możesz stosować krzyżowanie punktowe? W takich sytuacjach stosuje się krzyżowanie ox, pmx, ex, cx.

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