Преждевременная сходимость в эволюционных алгоритмах: причины и анализ.
Premature convergence
Преждевременная сходимость в эволюционных алгоритмах: причины, последствия (потеря аллелей) и влияние на поиск оптимальных решений. Генетические алгоритмы.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка 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) ES: параметр управления размером шага увеличивается на определенный фактор, если относительная частота положительных мутаций за определенный период времени превышает 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.