algorym genetyczny ilość osobników i pokoleń

Szybkie pytanie dotyczące algorytmów genetycznych:
Jak dobrać ilość pokoleń i wielkość populacji w rozwiązywanym problemie?

Rozumiem że musi być uzależnione od ilości wszystkich możliwych rozwiązań jako że nie ma sensu prowadzić algorytmu genetycznego z liczbą kroków większą niż ilość kroków w algorytmie przeglądającym całą przestrzeń rozwiązań stąd ilość pokoleń*ilość osobników < ilość wszystkich możliwych rozwiązań. Jednakże przeszukałem sporo materiałów na ten temat i nie widze jednoznacznej odpowiedzi jak dobrać te parametry.

Z jednej strony:

możliwe że:
ilość pokoleń*ilość osobników > ilość wszystkich możliwych rozwiązań
(ponieważ nie każdy osobnik jest inny)

z drugiej strony algorytm powinien być efektywny i szukać tylko tam gdzie jest coś interesującego.

Możesz uzależnić wielkość populacji od rozmiaru przestrzeni, poziom mutacji od numeru pokolenia, liczbę pokoleń do 50 lub do 100, lub też w jakiś sposób zgrubnie zależną od przestrzeni rozwiązań.

Możesz badać efektywność algorytmu jako:
rozmiar przestrzeni / (rozmiar przestrzeni - liczbę wykonanych wyliczeń funkcji celu)

1.0 dla minimalnej liczby wyliczeń
0.0 dla maksymalnej sensownej liczby wyliczeń
< 0.0 dla algorytmu nieefektywnego.

Dzięki za szybką odpowiedź.
Rozwiązania mogą się powtarzać - fakt i z tego chociażby powodu nie ma sensu wykonywać algorytmu genetycznego gdy ilość kroków genetyka przekracza ilość wszystkich możliwych rozwiązań i tak wiem że nie tylko mogę ale i muszę uzależnić wielkość populacji i ilość pokoleń od ilości wszystkich możliwych rozwiązań i wiem że mogę ustalić stałą liczbę pokoleń i osobników i spodziewam się że ilość populacji * ilość pokoleń powinna dać kilka procent z max ilości rozwiązań.

Przykład: problem pakowania. 4 elementy, złożoność obliczeniowa 2^4 * 4! = 384
Jeżeli damy 50 pokoleń i powiedzmy 6 osobników to mamy conajmniej 300 kroków (mutacja itd) z czego bardzo dużo kroków zadziała na osobnikach powtarzających się przez co zrobimy podobną ilość kroków do przeglądu zupełnego a ilość przeglądniętych rozwiązań będzie sporo mniejsza. Co prawda wynik z dużym prawdopodobieństwem będzie optymalny ale...

Interesuje mnie zatem najlepiej jakaś reguła matematyczna odpowiadająca za ilość pokoleń i osobników najlepiej wzięta z literatury jak ktoś się już z tym problemem spotkał.

Pytanie zasadnicze: po co robić genetyka o podobnej licznie kroków co zwykły brut? Przecież to mija się z celem. Genetyków się używa do znalezienia względnie dobrego rozwiązania, gdy przestrzeń parametrów jest nie do ogarnięcia brutem. W ogólności pierwszorzędnym celem nie jest znalezienie globalnie optymalnego rozwiązania, tylko znalezienie rozwiązania jak najlepszego przy założonym okresie poszukiwań.

Tak rozumiem że szybkość działania tego algorytmu i bruta to milisekundy w wypadku małych przestrzeni rozwiązań. Ale pytanie jest następujące: Jak dobrać ilość osobników i ilość pokoleń do rozwiązania problemu. Przykład przedstawiłem w oparciu o małą liczbę elementów żeby było wiadomo o co chodzi. Ale przecież nawet dla dużych przestrzeni rozwiązań możesz przekroczyć liczbę maksymalnych ilości kroków bruta. Możesz dać np 2000 osobników i 10000 pokoleń dla 9 czy 10 elementów czy jakieś inne liczby. Więc chodzi o konkret bo piszemy duże przestrzenie albo małe przestrzenie co dokładnie nie wiadomo co znaczy. Potrzebny jest sposób który sprosta każdej liczbie elementów a nie wybranym przykładom.

Więc powtarzam pytanie czy istnieje jakaś formuła matematyczna z literatury która określi liczbę osobników i pokoleń (np.: dla algorytmu genetycznego może być w tym przypadku problem pakowania) dla wyznaczonej ilości elementów?

Moim zdaniem trudno jest podać jakikolwiek zbiór, ponieważ problemy optymalizacyjne mogą się drastycznie różnić. Np dla szukania najniższego punktu w paraboli wystarczyłoby kilka elementów i kilkanaście pokoleń. Natomiast dla jakiegoś problemu, który jest wybitnie niekompatybilny z genetykami, np łamanie hasza, w zasadzie optymalnie byłoby w ogóle nie robić pokoleń tylko zrobić jak największe losowanie osobników - czyli efektywnie zrobić bruta.

Jednak jeżeli liczba obliczeń funkcji celu w algorytmie genetycznym będzie zbliżać się do liczby obliczeń funkcji celu w brucie, to na pewno zabawa w genetyka traci sens. Obojętnie jaki byłby problem.

Fakt dobrze jest doprecyzować pytanie: Na myśli mam wspomniany już problem pakowania gdzie na danej płaszczyźnie umieszczamy prostokąty różnych wymiarów. Osobnikami są tutaj zbiory danych prostokątów z przestawioną kolejnością czyli permutacje zbioru danych prostokątów. Dodatkowo jest tutaj potrzebna funkcja układająca prostokąty na zadanej płaszczyźnie w tym wypadku bottom-left algorithm. Po ustawieniu prostokątów każdego osobnika obliczana jest wysokość ułożonych elementów. Funkcja oceny sprawdza tutaj właśnie wysokość ułożonych elementów i te z mniejszą wysokością osobniki są uznawane za lepsze. Jak widać problem nadaje się do algorytmów genetycznych bo możemy tutaj szukać lepszych rozwiązań. Wiem że trudno jest dobrać ilość osobników i pokoleń żeby algorytm działał optymalnie, ale głównie od tego doboru wartości zależy czy algorytm będzie przeszukiwał podobną przestrzeń rozwiązań jak brute lub czy będzie przeszukiwał mniejszą przestrzeń z wieloma powtarzającymi się elementami co da podobną ilość kroków jak brute lub też przeszuka wąską część lepszych rozwiązań i z nich wyłoni prawie optymalne rozwiązanie w rozsądnym czasie.

Jednym słowem (a właściwie trzema) mogę powtórzyć pytanie. Czy istnieje reguła określająca ilość pokoleń i osobników dla optymalnego działania genetyka?

Minęło już troche czasu i myśle że z braku jakkolwiek pomocnych odpowiedzi temat można zamknąć. Do zamknięcia.

Tutaj zamyka się tematy za brak kultury, a nie na żądanie autora ;]

Jak znajdziesz trochę owych "jakkolwiek pomocnych odpowiedzi" to wklej tutaj przynajmniej linka. Przyda się innym szukającym. Niemniej sądzę, że nie ma żadnego całkowicie ogólnego wzoru dającego odpowiedź wprost.

Jak coś znajde dam znać.

Jest chyba logiczne, że im operator krzyżowania jest mniej efektywny i im bardziej agresywny jest operator mutacji to tym większa musi być populacja by skutecznie zwalczać pojawiające się "choroby".
Populację musi się dobierać doświadczalnie. Pytanie jak mierzyć, że jest już dobrze?
IMO powinieneś mierzyć standardowe odchylenie dostosowania osobników oraz ogólne dostosowanie populacji i obserwować jak te wartości zmieniają się wraz z pokoleniami.
Uruchamiając algorytm z różnymi parametrami powinieneś być w stanie dobrać te parametry (nie tylko wielkość populacji, ale też prawdopodobieństwo i siłę mutacji).

Jaka ma być ilość pokoleń? Najlepiej nieokreślona, symulacje kończysz, gdy populacja przestaje się rozwijać efektywnie od powiedzmy 10 pokoleń (czyli nadal obserwujesz wspomniane parametry).