Optymalizacja wielokryterialna - algorytm genetyczny

Będę pisał algorytm genetyczny do optymalizacji wielokryterialnej.
Mam kilka fundamentalnych pytań ale najpierw troszkę wyjaśnienia.
Celem takiej optymalizacji jest odszukanie zbioru optymalnych rozwiązań. Taki zbiór nazywamy FrontPareto i na wykresie jest to czerwony zbiór. Zielone rozwiązania są zdominowane przez czerwone. Zielone punkty są takie same jeśli chodzi o cenę ale gorsze jeśli chodzi o jakość. Algorytm optymalizacji wielokryterialnej ma zbudować taki "czerwony zbiór rozwiązań". Przykład w którym chcę maksymalizować Jakość(Y) a minimalizować Koszt(X)
</img>
Rozwiązanie x jest lepsze (dominuje) od rozwiązania y wtedy, gdy wartość każdego kryterium dla rozwiązania x jest nie niższa niż dla rozwiązania y oraz istnieje przynajmniej jedno kryterium i, którego wartość dla rozwiązania x jest wyższa niż dla y. Czyli x jest niezdominowane, y zdominowane.

Mam wątpliwości co do warunku stopu takiego algorytmu. I nie chodzi mi tu o taki klasyczny warunek stopu bo jak mówi się pół żartem "dobry algorytm genetyczny nigdy się nie kończy", ale o to skąd algorytm będzie wiedział że ma szukać akurat takiego czerwonego FrontPareto jak na wykresie?
Dlaczego nie będzie szukał coraz lepszych i lepszych rozwiązań. Dlaczego nie wyszuka rozwiązań ze zbioru niebieskiego, a następnie z fioletowego i tak dalej...?
</img>
Nie mogę tego sobie wyobrazić, w praktyce mam zbiór kilkudziesięciu samochodów z przypisanymi wartościami liczbowymi cena i jakość. I taki algorytm powinien mi wybrać właśnie rozwiązania najbardziej optymalne, niezdominowane. A nie zasuwać w nieskończoność.
Moje domysły to to że ogranicza się jakoś przestrzeń poszukiwań, czyli czy mam ograniczyć np. cenę 3.0 a jakość do 5.5?
A może muszę mu podać na wstępie zbiór mozliwych rozwiązań? Przecież populację startową się losuje, jak algorytm ustali mi rozwiązania które na prawdę istnieją a nie wskaże takich które nie istnieją?

Na wstępie zaznaczam, że nie pomogę ci w rozwiązaniu tego zadania, bo go nie rozumiem. Jakbyś mi pokazał ostatni wykres i kazał wybrać "Przykład w którym chcę maksymalizować Jakość(Y) a minimalizować Koszt(X)", to wybrałbym fioletowy a nie czerwony, więc algorytm genetyczny który bym zaproponował również próbowałby go znaleźć :)

Mogę ci natomiast podpowiedzieć co się robi, żeby algorytm genetyczny nie generował nieistniejących rozwiązań.

Po pierwsze musisz poszukać specjalizowanych operatorów genetycznych do tego problemu. Przykładowo dla problemu komiwojażera zwykłe krzyżowanie dwóch tras (numery to identyfikatory miast):
3 2 | 1 5 4
5 1 | 2 4 3
utworzy parę potomków niespełniających założeń (niektóre miasta się powtarzają, innych nie ma wcale). Dlatego olewa się zwykłe krzyżowanie i mutację i stosuje bardziej wyszukane operatory (PMX, OX, CX i jeszcze jakieś).

Jeśli nie uda ci się znaleźć takich operatorów, to możesz wykorzystać funkcje kary. Są różne warianty, np. kara śmierci. Sprawdza się, jeśli prawdopodobieństwo wygenerowania nieistniejącego rozwiązania jest małe. Ale na przykład w komiwojażerze ze standardowym krzyżowaniem ubijałby większość potomków i algorytm nie ruszyłby do przodu.
Inny wariant, to kara w postaci odjęcia pewnej wartości w funkcji przystosowania w przypadku rozwiązań nieistniejących. Problem będzie z dopasowaniem tego współczynnika. Zbyt mała kara i świetne rozwiązania nieistniejące będą i tak wypierały dobre istniejące. Zbyt duża i szybko wytracisz różnorodność którą niosą jednak ze sobą rozwiązania nieistniejące i algorytm będzie ci się zbiegał do optimum lokalnego.

Trzeci sposób który mi się przypomina, to funkcja naprawy. Każdego potomka niespełniającego wymagań przepuszczasz przez funkcję, która możliwie niskim kosztem zrobi z niego osobnika mieszczącego się w obszarze rozwiązań. Na przykład dla powyższego komiwojażera po utworzeniu potomka 3 2 2 4 3 naprawiałbym go przechodząc po kolei po jego genach i sprawdzając, czy się powtarzają - jeśli tak, to w ich miejsce wstawiałbym losowe geny z tych, których w chromosomie zabrakło.
Ale uważaj: jeśli algorytm generuje ci sporo niepoprawnych osobników, to ich naprawa znacząco wpłynie na wydajność.

Nie jestem pewien bo po pierwsze nie jestem z wykształcenia informatykiem a po drugie miałem małą przerwę w moim hobby :). Jednak tak się składa, że miałem do czynienia zarówno z AG jak i z problemami optymalizacji i problemem Pareto (chociaż to ostatnie było bardzo dawno na studiach ekonomicznych :)).
Wydaje mi się, że problem jest trochę źle przedstawiony. Mamy dwa kryteria: koszt i jakość. Oczywiste jest, że lepiej, gdy koszt jest mniejszy a jakość większa. Dlatego mamy dwie funkcje: kosztu i jakości (f_k i f_j). Problem w tym, że jedną funkcję się maksymalizuje a drugą minimalizuje. I chyba tu zaczynają się komplikacje.
Trudno będzie mi to wytłumaczyć ale spróbujmy:
Nie jestem pewny ale ten wykres gdzie na osi X jest koszt a na osi Y jakość jest przedstawieniem dopasowania tych dwóch funkcji. Jednak to nie są wyniki tych funkcji! Albo inaczej, żeby łatwiej to zobrazować: załóżmy, że f_k = -f_k => czyli maksymalizujemy obie funkcje. Ehh... nie wiem jak to powiedzieć a nie chcę też wprowadzić w błąd. Po prostu na tych wykresach chodzi o to, żeby oba kryteria były zrównoważone. Natomiast gdy polepszamy jedno kryterium to automatycznie pogarszamy drugie. Dlatego najbardziej optymalnym rozwiązaniem byłaby linia ukośna pod kontem 45 stopni pomiędzy jakość a koszt w przypadku takiego samego wpływu obu kryteriów... W przypadku różnego wpływu kryteriów ta krzywa może być inna (np. tak jak w tym zadaniu - ta czerwona linia).

Niestety trudno mi wyjaśnić to co chodzi mi po głowie - mam nadzieję, że chociaż trochę naprowadziłem na prawidłowe rozwiązanie