Кіріспе
Фитнеске пропорционалды таңдау, сондай-ақ рулетка дөңгелегі таңдауы деп те аталады, генетикалық алгоритмдерде рекомбинация үшін потенциалды пайдалы шешімдерді таңдауға қолданылатын генетикалық оператор. Фитнеске пропорционалды таңдауда, барлық таңдау әдістеріндегідей, жарамдылық функциясы мүмкін шешімдерге немесе хромосомаларға жарамдылық деңгейін береді. Бұл жарамдылық деңгейі әрбір жеке хромосоманың таңдалу ықтималдығымен байланыстырылады. Егер популяциядағы жеке тұлғаның жарамдылығы болса, оның таңдалу ықтималдығы популяциядағы жеке тұлғалардың санына тең. Бұл ойын казинодағы рулетка дөңгелегіне ұқсас. Әдетте, дөңгелектің бір бөлігі олардың жарамдылық мәніне пропорционалды түрде әрбір мүмкін таңдауға бөлінеді. Бұл таңдаудың жарамдылығын барлық таңдаулардың жалпы жарамдылығына бөлу арқылы, осылайша оларды 1-ге нормалдау арқылы жүзеге асырылуы мүмкін. Содан кейін рулетка дөңгелегін айналдыру сияқты кездейсоқ таңдау жасалады. Жоғары жарамдылыққа ие кандидат шешімдердің жойылуы аз болса да, олардың таңдалу ықтималдығы 1-ден (немесе 100%) кем болғандықтан, жойылу мүмкіндігі бар. Бұл, мысалы, кесу таңдауы сияқты, аз күрделі таңдау алгоритмінен өзгеше, ол ең нашар үміткерлердің белгілі бір пайызын жояды. Фитнеске пропорционалды таңдау кезінде кейбір нашар шешімдер таңдау процесінен өтуі мүмкін. Бұл нашар шешімдердің тірі қалу ықтималдығы төмен болса да, ол нөл емес, яғни олардың тірі қалуы әлі де мүмкін; бұл артықшылық, өйткені нашар шешімдердің де рекомбинация процесінен кейін пайдалы болатын кейбір ерекшеліктері немесе қасиеттері болуы мүмкін. Рулетка дөңгелегіне ұқсастықты әрбір кандидат шешім дөңгелектің қалтасын білдіретін рулетка дөңгелегін елестету арқылы қарастыруға болады; қалталардың мөлшері шешімді таңдау ықтималдығына пропорционалды. Популяциядан N хромосоманы таңдау рулетка дөңгелегінде N ойын ойнауға тең, өйткені әрбір кандидат тәуелсіз түрде тартады. Практикада басқа таңдау техникалары, мысалы, стохастикалық жалпыға бірдей үлгі алу немесе турнирлік таңдау жиі қолданылады. Бұл олардың аз стохастикалық шуы бар немесе олар жылдам, оңай іске асырылады және тұрақты таңдау қысымына ие болғандықтан. Наивті іске асыру алдымен жеке тұлғаның жарамдылығына пропорционалды ықтималдықты пайдалана отырып, жеке тұлғалар тізімі бойынша жиынтық ықтималдық үлестірімін (CDF) құру арқылы жүзеге асырылады. [0,1] диапазонынан біркелкі кездейсоқ сан таңдалады және сол сан үшін CDF-тың керісі жеке тұлғаны береді. Бұл рулетка доптың бір жеке тұлғаның ұясына, оның еніне пропорционалды ықтималдықпен түсуіне сәйкес келеді. Біркелкі кездейсоқ санның кері мәніне сәйкес келетін "ұяны" CDF элементтері бойынша екілік іздеуді пайдалану арқылы ең жылдам табуға болады. Жеке тұлғаны таңдау үшін O(log n) уақыт қажет. O(1) уақытында жеке тұлғаларды өндіретін жылдам балама – псевдоним әдісін пайдалану. 2011 жылы "стохастикалық қабылдауға" негізделген өте қарапайым алгоритм енгізілді. Алгоритм кездейсоқ түрде бір жеке тұлғаны (айталық ) таңдайды және оны жарамдылықтың максималды мәні болған жағдайда қабылдайды. Кейбір талдаулар стохастикалық қабылдау нұсқасы сызықтық немесе екілік іздеуге негізделген нұсқаларға қарағанда, әсіресе жарамдылық мәндері жүгіру кезінде өзгеруі мүмкін жағдайларда айтарлықтай жақсы жұмыс істейтінін көрсетеді. Бұл алгоритмнің мінез-құлқы әдетте жылдам болса да, кейбір жарамдылық үлестірімдері (мысалы, экспоненциалдық үлестірімдер) ең нашар жағдайда итерацияларды қажет етуі мүмкін. Бұл алгоритмге екілік іздеуге қарағанда көбірек кездейсоқ сандар қажет.
where is the number of individuals in the population. This could be imagined similar to a Roulette wheel in a casino. Usually a proportion of the wheel is assigned to each of the possible selections based on their fitness value. This could be achieved by dividing the fitness of a selection by the total fitness of all the selections, thereby normalizing them to 1. Then a random selection is made similar to how the roulette wheel is rotated. While candidate solutions with a higher fitness will be less likely to be eliminated, there is still a chance that they may be eliminated because their probability of selection is less than 1 (or 100%). Contrast this with a less sophisticated selection algorithm, such as truncation selection, which will eliminate a fixed percentage of the weakest candidates. With fitness proportionate selection there is a chance some weaker solutions may survive the selection process. This is because even though the probability that the weaker solutions will survive is low, it is not zero which means it is still possible they will survive; this is an advantage, because there is a chance that even weak solutions may have some features or characteristics which could prove useful following the recombination process. The analogy to a roulette wheel can be envisaged by imagining a roulette wheel in which each candidate solution represents a pocket on the wheel; the size of the pockets are proportionate to the probability of selection of the solution. Selecting N chromosomes from the population is equivalent to playing N games on the roulette wheel, as each candidate is drawn independently. Other selection techniques, such as stochastic universal sampling or tournament selection, are often used in practice. This is because they have less stochastic noise, or are fast, easy to implement and have a constant selection pressure. The naive implementation is carried out by first generating the cumulative probability distribution (CDF) over the list of individuals using a probability proportional to the fitness of the individual. A uniform random number from the range [0,1) is chosen and the inverse of the CDF for that number gives an individual. This corresponds to the roulette ball falling in the bin of an individual with a probability proportional to its width. The "bin" corresponding to the inverse of the uniform random number can be found most quickly by using a binary search over the elements of the CDF. It takes in the O(log n) time to choose an individual. A faster alternative that generates individuals in O(1) time will be to use the alias method. In 2011, a very simple algorithm was introduced that is based on "stochastic acceptance". The algorithm randomly selects an individual (say ) and accepts the selection with probability , where is the maximum fitness in the population. Certain analysis indicates that the stochastic acceptance version has a considerably better performance than versions based on linear or binary search, especially in applications where fitness values might change during the run. While the behavior of this algorithm is typically fast, some fitness distributions (such as exponential distributions) may require iterations in the worst case. This algorithm also requires more random numbers than binary search.