Эволюциялық алгоритмдерде ерте конвергенция мәселесі – жақсы нәтижеге жетпеуге алып келетін популяцияның тым ерте тоқтауы. Аллельдер жоғалуы іздеуді қиындатады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Эволюциялық алгоритмдерде (ЭА) ерте конвергенция дегеніміз – оптимизациялау мәселесі үшін популяция тым ерте конвергенцияға ұшырап, нәтижесінде субоптималды шешімге келуі. Мұндай жағдайда, ата-аналық шешімдер генетикалық операторлардың көмегімен ата-аналарынан жақсырақ немесе олардан жоғары нәтиже беретін ұрпақтарды өндіре алмайды. Ерте конвергенция – эволюциялық алгоритмдердің және әсіресе генетикалық алгоритмдердің көпте орын алатын кең таралған мәселе, себебі ол көптеген аллельдердің жоғалуына немесе конвергенциясына алып келеді, соның салдарынан аллельдері бар нақты генді табу өте қиын болады. Егер популяциядағы барлық жеке тұлғалар бір ген үшін бірдей мәнді бөлісетін болса, онда аллель жоғалған деп есептеледі. Де Йонг анықтағандай, егер белгілі бір ген үшін популяцияның 95% бірдей мәнді бөлісетін болса, онда ол аллель конвергентті аллель деп саналады (конвергенцияға да қараңыз).
In evolutionary algorithms (EA), the term of premature convergence means that a population for an optimization problem converged too early, resulting in being suboptimal. In this context, the parental solutions, through the aid of genetic operators, are not able to generate offspring that are superior to, or outperform, their parents. Premature convergence is a common problem found in evolutionary algorithms in general and genetic algorithms in particular, as it leads to a loss, or convergence of, a large number of alleles, subsequently making it very difficult to search for a specific gene in which the alleles were present. An allele is considered lost if, in a population, a gene is present, where all individuals are sharing the same value for that particular gene. An allele is, as defined by De Jong, considered to be a converged allele, when 95% of a population share the same value for a certain gene (see also convergence).
Ертерек конвергенцияның пайда болуын анықтау
Ертерек конвергенция қашан пайда болғанын анықтау қиын, және оның болашақта болатынын болжау да оңай емес. Халықтың әртүрлілігі – ертерек конвергенцияны өлшеу үшін зерттеулерде жиі қолданылатын тағы бір көрсеткіш. Дегенмен, халықтың әртүрлілігінің төмендеуі тікелей ертерек конвергенцияға алып келеді деген кең тараған пікірге қарамастан, халықтың әртүрлілігін талдауға арналған зерттеулер аз. Яғни, «халықтың әртүрлілігі» терминін пайдаланғанда, ертерек конвергенцияның алдын алу зерттеуінің негізділігі олардың халықтың әртүрлілігін қалай түсінетіні нақтыланбаса, жеткіліксіз болып қалады.
It is hard to determine when premature convergence has occurred, and it is equally hard to predict its presence in the future. Population diversity is another measure which has been extensively used in studies to measure premature convergence. However, although it has been widely accepted that a decrease in the population diversity directly leads to premature convergence, there have been little studies done on the analysis of population diversity. In other words, by using the term population diversity, the argument for a study in preventing premature convergence lacks robustness, unless specified what their definition of population diversity is.
Ертерек конвергенцияның себептері
Ертерек конвергенцияның пайда болуына бірнеше болжанған немесе гипотезаланған себептер бар.
There are a number of presumed or hypothesized causes for the occurrence of premature convergence.
Өзін-өзі бейімделетін мутациялар
Реченберг эволюциялық стратегияларда мутация таралуының өзіндік бейімделу идеясын енгізді. Реченбергтің сөзінше, осы мутация таралуларының бақылау параметрлері алдын ала анықталудың орнына, ішкі бейімделу арқылы дамыды. Ол мұны эволюциялық стратегиялардың 1/5 табыстылық ережесі деп атады (1 + 1) ЭС: Белгілі бір кезеңде оң мутациялардың салыстырмалы жиілігі 1/5-тен жоғары болса, қадамдық өлшемді бақылау параметрі белгілі бір фактормен ұлғаяды, ал егер 1/5-тен төмен болса, керісінше кемейтеді. Өзін-өзі бейімдейтін мутациялар ерте конвергенцияның себебі болуы мүмкін. Бұл нөлдік емес өлшемдердің шектелген төменгі деңгейлерін қамтитын жиынтарға ие, дөңес емес мақсаттық функциялар үшін дұрыс. Рудольф жасаған зерттеу элиталық эволюциялық стратегиялардағы өзін-өзі бейімдеу механизмдері 1/5 табыстылық ережесіне ұқсас екенін, және оң ықтималдыққа ие жергілікті оптимумға түсіп қалуы мүмкін екенін көрсетеді. Осылайша, тек сәл жақсырақ жеке тұлғаның генетикалық ақпараты, егер осы уақыт ішінде одан жақсы ұрпақ тумаса, бірнеше буын ішінде популяцияға таралуы мүмкін. Әсіресе салыстырмалы түрде кішкентай популяцияларда, бұл генотиптік әртүрліліктің жоғалуына және осылайша ерте конвергенцияға тез әкелуі мүмкін. Бұл генотиптік әртүрлілікті ұзақ мерзімге сақтап, ерте конвергенцияға қарсы тұруға мүмкіндік береді. Мұндай нәтиже генетикалық алгоритмдер, басқа ЭА немесе меметикалық алгоритмдер сияқты әртүрлі ЭА үшін көрсетілген.
Rechenberg introduced the idea of self adaptation of mutation distributions in evolution strategies. According to Rechenberg, the control parameters for these mutation distributions evolved internally through self adaptation, rather than predetermination. He called it the 1/5 success rule of evolution strategies (1 + 1) ES: The step size control parameter would be increased by some factor if the relative frequency of positive mutations through a determined period of time is larger than 1/5, vice versa if it is smaller than 1/5. Self adaptive mutations may very well be one of the causes for premature convergence. This is for non convex objective functions with sets that include bounded lower levels of non zero measurements. A study by Rudolph suggests that self adaption mechanisms among elitist evolution strategies do resemble the 1/5 success rule, and could very well get caught by a local optimum that include a positive probability. Thus, The genetic information of an only slightly better individual can spread in a population within a few generations, provided that no better other offspring is produced during this time. Especially in comparatively small populations, this can quickly lead to a loss of genotypic diversity and thus to premature convergence. that preserve genotypic diversity over a longer period of time and thus counteract the tendency towards premature convergence. This has been shown for various EAs such as genetic algorithms, other EAs or memetic algorithms.