Кіріспе
Селекция – генетикалық алгоритмнің немесе жалпы эволюциялық алгоритмнің кезеңі, онда жеке геномдар кейінгі көбейту үшін популяциядан таңдалады (мысалы, кроссовер операторын қолдану арқылы). Таңдау механизмдері келесі ұрпаққа үміткер шешімдерді (жеке тұлғаларды) таңдау үшін де пайдаланылады. Бір ұрпақтың ең жақсы тұлғаларын келесі ұрпаққа өзгеріссіз көшіру элитаризм немесе элитаристік таңдау деп аталады. Бұл жаңа популяция құрудың жалпы процесінің табысты (сәл) нұсқасы. Алдымен қолданылатын селекциялық процедураны былай іске асыруға болады: Есептелген жарамдылық мәндері (жарамдылық функциясы) нормаланады, яғни нәтижедегі барлық жарамдылық мәндерінің қосындысы 1-ге тең болады. Жинақталған нормаланған жарамдылық мәндері есептеледі: жеке тұлғаның жинақталған жарамдылық мәні – өзінің жарамдылық мәнінің және барлық алдыңғы тұлғалардың жарамдылық мәндерінің қосындысы; соңғы тұлғаның жинақталған жарамдылық мәні 1-ге тең болуы керек, әйтпесе нормалау кезеңінде қателік болған. 0 мен 1 арасындағы кездейсоқ сан R таңдалады. Таңдалған тұлға – жинақталған нормаланған мәні R-ден үлкен немесе оған тең алғашқы тұлға. Көптеген мәселелер үшін жоғарыдағы алгоритм есептеулерді көп талап етуі мүмкін. Жаңа және жылдам балама – стохастикалық қабылдау. Егер бұл процедура жеткілікті тұлғалар таңдалғанша қайталанса, бұл таңдау әдісі жарамдылыққа пропорционалды таңдау немесе рулетка дөңгелегінің таңдауы деп аталады. Егер бір көрсеткішті бірнеше рет айналдырудың орнына, дөңгелекті бір рет айналдырғанда бірнеше, тең араласқан көрсеткіштер болса, онда бұл стохастикалық әмбебап үлгі алу деп аталады. Кездейсоқ таңдалған топтан үздік тұлғаны қайта-қайта таңдау – турнирлік таңдау. Тұлғалардың ең жақсы жартысын, үштен бірін немесе басқа үлесін алу – бұл қиып тастау таңдауы. Таңдау үшін барлық тұлғаларды емес, тек белгілі бір (еркін) тұрақтыдан жоғары жарамдылық мәніне ие тұлғаларды ғана қарастыратын басқа таңдау алгоритмдері де бар. Басқа алгоритмдер жарамдылық деңгейіне байланысты, тек белгілі бір пайызды ғана қабылдайтын шектеулі топтан таңдайды.
Selection is the stage of a genetic algorithm or more general evolutionary algorithm in which individual genomes are chosen from a population for later breeding (e. g., using the crossover operator). Selection mechanisms are also used to choose candidate solutions (individuals) for the next generation. Retaining the best individuals in a generation unchanged in the next generation, is called elitism or elitist selection. It is a successful (slight) variant of the general process of constructing a new population. A selection procedure for breeding used early on may be implemented as follows:
The fitness values that have been computed (fitness function) are normalized, such that the sum of all resulting fitness values equals 1. Accumulated normalized fitness values are computed: the accumulated fitness value of an individual is the sum of its own fitness value plus the fitness values of all the previous individuals; the accumulated fitness of the last individual should be 1, otherwise something went wrong in the normalization step. A random number R between 0 and 1 is chosen. The selected individual is the first one whose accumulated normalized value is greater than or equal to R.
For many problems the above algorithm might be computationally demanding. A simpler and faster alternative uses the so called stochastic acceptance. If this procedure is repeated until there are enough selected individuals, this selection method is called fitness proportionate selection or roulette wheel selection. If instead of a single pointer spun multiple times, there are multiple, equally spaced pointers on a wheel that is spun once, it is called stochastic universal sampling. Repeatedly selecting the best individual of a randomly chosen subset is tournament selection. Taking the best half, third or another proportion of the individuals is truncation selection. There are other selection algorithms that do not consider all individuals for selection, but only those with a fitness value that is higher than a given (arbitrary) constant. Other algorithms select from a restricted pool where only a certain percentage of the individuals are allowed, based on fitness value.
Таңдау әдістері (эволюциялық алгоритм)
Тізімделген әдістер негізінен таңдау қысымымен ерекшеленеді, ол төменде сипатталған реттік таңдаудағы стратегиялық параметрмен белгіленеді. Таңдау қысымы неғұрлым жоғары болса, популяция белгілі бір шешімге соншалықты жылдам жақындайды және іздеу кеңістігі толыққанды зерттелмеуі мүмкін. Қосымша таңдау әдістері және толық ақпарат үшін қараңыз.
Рулетка дөңгелегін таңдау
Рулетка дөңгелегі арқылы таңдауда, келесі ұрпақты өсіру үшін жеке дараны таңдау ықтималдығы оның жарамдылығына пропорционалды, жарамдылығы жоғары болса, сол дараның таңдалу мүмкіндігі де артады. Дараларды таңдау – қазіргі ұрпақтағы даралар санына тең қалталары бар рулетканы айналдыру арқылы көрсетілуі мүмкін, ал қалталардың мөлшері олардың ықтималдығына байланысты. Дараны таңдау ықтималдығы , мұндағы – дараның жарамдылығы, ал – ағымдағы ұрпақтың мөлшері (осы әдісте бір дара бірнеше рет таңдалуы мүмкін екенін ескеріңіз).
Рангының таңдалуы
Рангты таңдау кезінде таңдау ықтималдығы тікелей дене шынықтыру деңгейіне байланысты емес, бірақ популяция ішіндегі жеке тұлғаның дене шынықтыру деңгейінің орнына байланысты. Бұл үлкен дене шынықтыру деңгейінің айырмашылықтарын салыстыруға мүмкіндік береді; сонымен қатар, нақты дене шынықтыру деңгейінің мәндерінің өзі қажет емес, тек жеке тұлғаларды сапасы бойынша реттеу жеткілікті. Сызықтық реттеу, Бейкерге дейін барған, көбінесе қолданылады. Ол параметр арқылы таңдау қысымын орнатуға мүмкіндік береді, ол 1.0 (таңдау қысымы жоқ) және 2.0 (жоғары таңдау қысымы) арасындағы мәндерді қабылдауы мүмкін. Ранг бойынша орналасудың ықтималдығы келесідей есептеледі:
Реттелетін таңдау қысымынан басқа, рангілік таңдаудың артықшылығы нашаррақ жеке тұлғаларға да көбейіп, осылайша жақсаруға мүмкіндік беруі болып табылады. Бұл шектеулер бар қолданбаларда ерекше пайдалы болуы мүмкін, себебі ол бірнеше аралық қадамдарда, яғни шектеулерді бұзуға байланысты нашар бағаланған бірнеше жеке тұлғалар арқылы шектеуді жеңуді жеңілдетеді.
Тұрақты күйді таңдау
Әрбір ұрпақта жаңа ұрпақ жасау үшін бірнеше хромосома (жақсы, жоғары сәйкестігі бар) іріктеледі. Содан кейін, кейбір (жаман, төмен сәйкестігі бар) хромосомалар алынып тасталады және олардың орнына жаңа ұрпақ қойылады. Халықтың қалған бөлігі келесі ұрпаққа өтеді.
Турнирдің іріктеуі
Турнирлік таңдау – бұл жеке тұлғалар жиынтығынан бір жеке тұлғаны таңдау әдісі. Әр турнирдің жеңімпазы кроссовер жасау үшін іріктеледі.
Элиталық таңдау
Көбінесе жақсы нәтиже алу үшін жартылай көбейту стратегиялары қолданылады. Олардың бірі – элиталық тәсіл, онда өткен буынның ең жақсы жекелерінің шағын бөлігі (ешқандай өзгеріссіз) келесі буынға көшіріледі.
Болцманның таңдау
Болцман таңдауында, үздіксіз өзгеретін температура, алдын ала белгіленген кестеге сәйкес таңдау жылдамдығын реттейді. Температура жоғары мәннен басталады, яғни таңдау қысымы төмен болады. Температура біртіндеп төмендеген сайын, таңдау қысымы да біртіндеп артады, соның арқасында генетикалық алгоритм іздеу кеңістігінің ең жақсы бөлігіне жақындап, қажетті деңгейде әртүрлілікті сақтай алады.