Kolorowanie grafów - algorytm genetyczny

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:

1. Jak duża powinna być populacja początkowa ? Czy to będzie zależeć od rozmiaru grafu(l.wierzchołków) ?

2. 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 ?

3. 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 ?

4. Czy mutacja ma zmieniać każdy kolor w wektorze chromosomu ?

5. 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 ?

Ad 1. Best way to predict future is... to implement it, czyli generalnie rozmiar populacji początkowej dobierzesz sobie empirycznie

Ad 2, 3. Jeżeli przyjmiesz taką reprezentację chromosomów, to postać Twojej funkcji celu wydaje mi się słuszna

Ad 4. Mutacja powinna zmieniać jeden kolor w chromosomie(chociaż można pokusić się tutaj o eksperyment i z niewielkim prawdopodobieństwem zmienić więcej), i powinna występować stosunkowo rzadko(to rzadko należy również wyznaczyć empirycznie). Z moich doświadczeń wynikało, że nie było sensu mutować z prawdopodobieństwem większym niż 0.01.

Ad 5. Nie chodzi o usuwanie najgorszych, ale o stworzenie nowej populacji. Wybierasz rodziców z prawdopodobieństwem wynoszącym wartości funkcji celu(znormalizowanej) i z "crossover probability" ich krzyżujesz(w losowo wybranym miejscu). Te "krzyżówki" tworzą Twoją nową populację.
Od siebie dodam, że można się jeszcze pokusić o losowe "przeniesienie" między pokoleniami, czyli przenosisz losowo wybranych(tutaj losowo mam na myśli rozkład równomierny, chociaż można poeksperymentować też na jakimś innym) rodziców do kolejnego pokolenia - bez żadnych zmian.

Ok, pokombinuje.
Tylko chciałbym jeszcze wiedzieć, czy osobniki z utworzonej populacji początkowej mają być poprawnie pokolorowani.

Jeżeli będą poprawnie pokolorowani to po co stosować algorytm genetyczny?

Masz rację, ale w opisach spotkałem się ze stwierdzeniami, że muszą być poprawni w dziedzinie problemu(za równo przy tworzeniu populacji pocz., jak i po krzyżowaniu i mutacji).
Aczkolwiek moja funkcja celu opiera się na niepoprawnych kolorowaniach, także nie było pytania ;).

Zobaczę jak będzie się ona spisywać, ponieważ mam jeszcze w głowie zliczanie użytych kolorów(wiadomo mniej-lepiej). Obie są minimalizujące, więc można by je połączyć.

Jeżeli będą poprawnie pokolorowani to po co stosować algorytm genetyczny?

Jedyną odpowiedzią, która mi się nasuwa to przypadek z funkcją kosztu, minimalizującą liczbę kolorów. Wtedy poprawnie nie oznacza, że nie można tego zrobić lepiej.