Эволюциялық есептеудегі жұптасу қорының қалыптасуы және таңдау әдістері
Mating pool
Эволюциялық есептеудегі «жұптасу қоры» – ең жақсы шешімдерді таңдап, жаңа, тиімдірек нұсқаулар құруға арналған алгоритм. Оптимизация, іздеу мәселелері үшін пайдалы.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жұптасу бассейні – эволюциялық есептеулерде қолданылатын түсінік, ол оңтайландыру және іздеу мәселелерін шешуге арналған алгоритмдер жиынтығын білдіреді. Жұптасу бассейні қазіргі популяциядағы ең жоғары жарамдылыққа ие деп саналатын кандидаттық шешімдер арқылы құрылады, оларды іріктеу операторлары анықтайды. Жұптасу бассейніне кіретін шешімдер ата-аналар деп аталады. Жеке шешімдер бірнеше рет жұптасу бассейніне енгізілуі мүмкін, мұнда жарамдылық деңгейі жоғарырақ шешімдердің бірнеше рет енгізілу ықтималдығы артады. Содан кейін ата-аналарға кроссовер операторлары қолданылады, нәтижесінде жоғары сапалы деп танылған гендердің рекомбинациясы жүзеге асырылады. Соңында, мутация операторлары арқылы гендерге кездейсоқ өзгерістер енгізіліп, гендік қордағы генетикалық әртүрлілік артады. Бұл екі оператор жаңа, жақсырақ шешімдер жасау мүмкіндігін жақсартады. Осылайша, жаңа ұрпақ шешімдер – балалар пайда болады, олар келесі популяцияны құрайды. Іріктеу әдісіне байланысты, жұптасу бассейніндегі ата-аналардың жалпы саны бастапқы популяцияның мөлшерінен өзгеше болуы мүмкін, нәтижесінде жаңа популяция кішірек болады. Алгоритмді бірдей мөлшердегі популяциямен жалғастыру үшін, ескі популяциялардан кездейсоқ шешімдер таңдалып, жаңа популяцияға қосылуы мүмкін. Бұл кезде жаңа шешімдердің жарамдылығы бағаланады. Егер тоқтату шарттары орындалса, процестер аяқталады. Әйтпесе, олар қайталанады. Қадамдарды қайталау нәтижесінде кандидаттық шешімдер уақыт өте келе ең оңтайлы шешімге қарай эволюциялайды. Гендер ең оңтайлы генге қарай біртекті болып келеді, бұл процесс конвергенция деп аталады. Егер популяцияның 95%-ы бір геннің бірдей нұсқасын бөліссе, онда ген конвергенцияға жеткен болады. Барлық жеке жарамдылық мәндері ең жақсы жеке тұлғаның мәніне жеткенде, яғни барлық гендер конвергенцияланғанда, популяция конвергенциясына қол жеткізіледі.
A mating pool is a concept used in evolutionary computation, which refers to a family of algorithms used to solve optimization and search problems. The mating pool is formed by candidate solutions that the selection operators deem to have the highest fitness in the current population. Solutions that are included in the mating pool are referred to as parents. Individual solutions can be repeatedly included in the mating pool, with individuals of higher fitness values having a higher chance of being included multiple times. Crossover operators are then applied to the parents, resulting in recombination of genes recognized as superior. Lastly, random changes in the genes are introduced through mutation operators, increasing the genetic variation in the gene pool. Those two operators improve the chance of creating new, superior solutions. A new generation of solutions is thereby created, the children, who will constitute the next population. Depending on the selection method, the total number of parents in the mating pool can be different to the size of the initial population, resulting in a new population that’s smaller. To continue the algorithm with an equally sized population, random individuals from the old populations can be chosen and added to the new population. At this point, the fitness value of the new solutions is evaluated. If the termination conditions are fulfilled, processes come to an end. Otherwise, they are repeated. The repetition of the steps result in candidate solutions that evolve towards the most optimal solution over time. The genes will become increasingly uniform towards the most optimal gene, a process called convergence. If 95% of the population share the same version of a gene, the gene has converged. When all the individual fitness values have reached the value of the best individual, i. e. all the genes have converged, population convergence is achieved.
Жұптасу тобын құру
Жұптасу тобын құру үшін бірнеше әдіс қолданылуы мүмкін. Бұл процестердің бәрінде популяция ішіндегі белгілі бір мөлшердегі жекелеген организмдерді таңдап көбейту жүзеге асырылады. Жұптасу тобына қай организмдердің ілігіп, қайлары қалатынын анықтау үшін түрлі критерийлер пайдаланылуы мүмкін. Таңдау әдістерін үш негізгі түрге бөлуге болады: физикалық қабілетке пропорционалды таңдау, реттік таңдау және шекті таңдау.
Several methods can be applied to create a mating pool. All of these processes involve the selective breeding of a particular number of individuals within a population. There are multiple criteria that can be employed to determine which individuals make it into the mating pool and which are left behind. The selection methods can be split into three general types: fitness proportionate selection, ordinal based selection and threshold based selection.
Дене шынықтыру жағдайына сай таңдау
Сәйкестік пропорционалды таңдау жағдайында, популяцияға кіру үшін кездейсоқ жеке тұлғалар таңдалады. Дегенмен, жоғарырақ сәйкестік деңгейіне ие болғандары таңдалуы мүмкін, сондықтан олардың қасиеттерін келесі буынға жеткізу ықтималдығы артық.
In the case of fitness proportionate selection, random individuals are selected to enter the pool. However, the ones with a higher level of fitness are more likely to be picked and therefore have a greater chance of passing on their features to the next generation.
Тәртіптік негіздегі таңдау
Ординарлық негіздегі іріктеу әдістері турнирлік және рейтингтік іріктеуді қамтиды. Турнирлік іріктеуде популяциядан жеке тұлғалар кездейсоқ түрде таңдалып, олардың сәйкестік деңгейі (fitness) салыстырылады. Бұл "турнирлердің" жеңімпаздары ең жоғары мәнге ие болып, жұптасу резервіне (mating pool) ата-ана ретінде қосылады. Рейтингтік іріктеуде барлық жеке тұлғалар олардың сәйкестік деңгейіне қарай сұрыпталады. Ата-аналарды таңдау үміткерлердің орнына қарай жасалады. Әрбір жеке тұлғаның таңдалу мүмкіндігі бар, бірақ жоғары орналасқандарға басымдық беріледі.
The ordinal based selection methods include the tournament and ranking selection. Tournament selection involves the random selection of individuals of a population and the subsequent comparison of their fitness levels. The winners of these “tournaments” are the ones with the highest values and will be put into the mating pool as parents. In ranking selection all the individuals are sorted based on their fitness values. Then, the selection of the parents is made according to the rank of the candidates. Every individual has a chance of being chosen, but higher ranked ones are favored