Wybieranie tylko górnego x% do selekcji w algorytmie genetycznym

Question

Obecnie pracuję nad StringEvolver i nie jestem do końca pewny co do konkretnego terminu, który może być użyty w GA.

W algorytmach genetycznych, elitaryzm odnosi się do tego podzbioru populacji, które są bezpośrednio promowane do następnego pokolenia; poprawny?

Ale czy istnieje konkretny termin użycia tylko, na przykład, górnego 75% obecnej populacji dla procesu selekcji, krzyżowania i mutacji zamiast całej populacji? Zasadniczo, co to jest stawka x%?

Chodzi mi o to, że zamiast używać całą populację na powiedzmy, proces ruletki wyboru, używam tylko wierzchołek x% (tj rozmnażać tylko wśród najlepszych x% populacji)

---

Powodem, dla którego pytam, jest fakt, że zauważyłem znaczną poprawę wydajności (szybszą konwergencję) przy użyciu, na przykład, 10-25% populacji do selekcji, crossover i procesów mutacji dla postępu pokolenia zamiast używania pełnego populacja.

Answer 1

Strategia selekcji naiwnych, w której po prostu odrzucamy słabszych kandydatów, jest czasami nazywana Wybór skracania. W przypadku wielu problemów prowadzi to do przedwczesnej konwergencji, choć stwierdziłem, że działa całkiem dobrze dla problemu Travelling Salesman.

Wygląda na to, że masz strategię dwufazową, po pierwsze używając selekcji skracania, aby wyeliminować słabych kandydatów, a następnie zastosować bardziej wyrafinowaną strategię (koło ruletki?), Aby sfinalizować selekcję.

Zamiast całkowicie wyeliminować szansę na przetrwanie słabych kandydatów, lepiej jest wybrać strategię selekcji, która pozwoli ci poprawić to prawdopodobieństwo. Na przykład przy wyborze turnieju można dostosować próg, aby określić, jak prawdopodobne jest, że słabe kandydat przeżyje, zamiast silniejszego.

Answer 2

Wygląda na to, że mówisz tylko o konkretnej metodologii selekcji. Można zrobić z grubsza to samo, skalując swoją funkcję fitness, aby zwiększać się przy wyższych stawkach, a nie liniowo.

Powiedziałbym, że powinienem zachować ostrożność, aby za każdym razem nie wyrzucać dolnych części twojej populacji. W przypadku mniejszych GA pozwoli to na szybsze zbieganie się, ale w przypadku problemów w świecie rzeczywistym często będzie to powodować lokalne minimalne wartości, pogarszając jakość twoich rozwiązań.

To powiedziawszy, istnieje pojęcie zwane dziesiątkowaniem. Dzieje się tak, gdy wyrzucisz dolne X% swojej populacji przed przejściem i mutacją. Zazwyczaj nie jest to wykonywane w każdym pokoleniu. Zazwyczaj zaczynasz od nieprzyjemnie dużej populacji, aby pokryć większą przestrzeń poszukiwań, a następnie dziesiątkować po X pokoleniach, ponieważ GA często osiągają największe zyski w pierwszych 100 rodzajach. Następnie należy przejść do mniejszej, łatwiejszej do obsługi populacji.

Mam nadzieję, że to pomoże.

Answer 3

Nie ma określonego terminu na ograniczenie wyboru do górnych elementów x%, to tylko jeden z czynników, które należy ustawić podczas wdrażania strategii selekcji.

Możesz uzyskać szybszą konwergencję w niektórych przypadkach ograniczając tę ​​liczbę x%, ale sugerowałbym próbę z ciągami o różnej długości i zobacz, jak wpływa to na zbieżność. Zrobiłem to wcześniej (zobacz projekty this i this, zarówno na ewoluujących łańcuchach), a jeśli sprawisz, że pula genów będzie zbyt mała przy wybieraniu osób, prawdopodobieństwo utknięcia może wzrosnąć w stosunku do długości struny, powodem jest że poważnie narażasz różnorodność.