Chcę rozwiązać problem kolorowania grafów za pomocą algorytmu genetycznego w języku C++.
Poczytałem trochę o tym czym są algorytmy genetyczne, znalazłem ogólny schemat algorytmu genetycznego:
[Start] Generate random population of n chromosomes (suitable solutions for the problem)
[Fitness] Evaluate the fitness f(x) of each chromosome x in the population
[New population] Create a new population by repeating following steps until the new population is complete
[Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
[Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.
[Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).
[Accepting] Place new offspring in a new population
[Replace] Use new generated population for a further run of algorithm
[Test] If the end condition is satisfied, stop, and return the best solution in current population
[Loop] Go to step 2
Mam kilka pytań związanych z tym pseudokodem:
-
Jak duża powinna być populacja początkowa ? Czy to będzie zależeć od rozmiaru grafu(l.wierzchołków) ?
-
Myślę, że dobrą reprezentacją chromosomów będzie wektor liczb całkowitych, gdzie i-ta komórka, będzie reprezentować kolor i-tego wierzchołka.
Zastanawiam się natomiast nad tym jak generować tą populację, dorzucać wierzchołki losowo wybierając kolor i sprawdzać czy krawędź nie łączy dwóch kolorów ? Istotne jest tutaj, żeby operacja ta nie trwała zbyt długo, dlatego myślałem nad tym, żeby było więcej wierzchołków z różnymi kolorami, ale przecież muszą być też osobnicy, którzy zostaną pokolorowani mniejszą liczbą kolorów, dlatego nie wiem jak to rozwiązać.
Czy może nie dbać o poprawność kolorowania w tym momencie ?
-
Funkcja jakości - tutaj myślałem nad tym, żeby tą wartością była liczba kolidujących kolorów, im mniejsza będzie ta wartość tym lepszy osobnik. Czy może wybrać inne kryterium ?
-
Czy mutacja ma zmieniać każdy kolor w wektorze chromosomu ?
-
Ostatnie pytanie dotyczy akceptacji populacji. Wiem, że trzeba usuwać najgorszych, ale ilu ? Jak dodaje dwóch nowych to mogę sobie pozwolić przynajmniej na usunięcie dwóch słabych :) Tego się trzymać ?
Czy może postępować tak jak w tym pseudokodzie i tworzyć nową populację, która zastąpi starą gdy zostanie całkowicie zapełniona nowymi osobnikami ?