Функции пригодности в эволюционных алгоритмах: принципы и применение.
Fitness function
Функция пригодности в генетических алгоритмах: оценка качества решений для поиска оптимального дизайна. Используется для эволюции и отбора лучших вариантов.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Функция пригодности – это особый тип целевой функции, используемый для обобщения, в виде единой метрики, насколько близко данное проектное решение к достижению поставленных целей. Функции пригодности используются в эволюционных алгоритмах (ЭА), таких как генетическое программирование и генетические алгоритмы, для направления симуляций к оптимальным проектным решениям. В области ЭА каждое проектное решение обычно представляется в виде строки чисел (именуемой хромосомой). После каждого раунда тестирования или моделирования идея заключается в удалении n наихудших проектных решений и создании n новых из лучших проектных решений. Следовательно, каждому проектному решению необходимо присвоить метрику, чтобы указать, насколько близко оно подошло к выполнению общей спецификации, и она генерируется путем применения функции пригодности к результатам тестирования или моделирования, полученным для этого решения. Существуют два основных класса функций пригодности: один, в котором функция пригодности не изменяется, как при оптимизации фиксированной функции или тестировании с фиксированным набором тестовых примеров; и другой, в котором функция пригодности изменяема, как при нишевой дифференциации или совместной эволюции набора тестовых примеров. Другой способ рассмотрения функций пригодности – это с точки зрения ландшафта пригодности, который показывает пригодность для каждой возможной хромосомы. В дальнейшем предполагается, что пригодность определяется на основе оценки, которая остается неизменной в течение процесса оптимизации. Функция пригодности не обязательно должна вычислять абсолютное значение, поскольку иногда достаточно сравнить кандидатов для выбора лучшего. Относительного показателя пригодности (кандидат a лучше, чем b) достаточно в некоторых случаях, таких как турнирный отбор или оптимизация Парето.
A fitness function is a particular type of objective function that is used to summarise, as a single figure of merit, how close a given design solution is to achieving the set aims. Fitness functions are used in evolutionary algorithms (EA), such as genetic programming and genetic algorithms to guide simulations towards optimal design solutions. In the field of EAs, each design solution is commonly represented as a string of numbers (referred to as a chromosome). After each round of testing, or simulation, the idea is to delete the n worst design solutions, and to breed n new ones from the best design solutions. Each design solution, therefore, needs to be awarded a figure of merit, to indicate how close it came to meeting the overall specification, and this is generated by applying the fitness function to the test, or simulation, results obtained from that solution. Two main classes of fitness functions exist: one where the fitness function does not change, as in optimizing a fixed function or testing with a fixed set of test cases; and one where the fitness function is mutable, as in niche differentiation or co evolving the set of test cases. Another way of looking at fitness functions is in terms of a fitness landscape, which shows the fitness for each possible chromosome. In the following, it is assumed that the fitness is determined based on an evaluation that remains unchanged during an optimization run. A fitness function does not necessarily have to be able to calculate an absolute value, as it is sometimes sufficient to compare candidates in order to select the better one. A relative indication of fitness (candidate a is better than b) is sufficient in some cases, such as tournament selection or Pareto optimization.
Требования к оценке и функциональной пригодности
Качество оценки и вычисления функции пригодности (фитнес-функции) имеет фундаментальное значение для успешной оптимизации эволюционного алгоритма (ЭА). Она реализует принцип Дарвина о "выживании наиболее приспособленных". Без механизмов отбора, основанных на пригодности, для выбора партнеров и принятия потомства, поиск ЭА был бы слепым и едва отличимым от метода Монте-Карло. При разработке фитнес-функции всегда следует помнить, что она должна охватывать не только описание желаемого целевого состояния, но и максимально поддерживать эволюционный поиск на пути к оптимуму (см. также раздел о вспомогательных целях), если это еще не реализовано самой фитнес-функцией. Плохо спроектированная фитнес-функция может привести к сходимости алгоритма к нежелательному решению или к затруднениям со сходимостью вообще. Определение фитнес-функции во многих случаях не является тривиальной задачей и часто выполняется итеративно, если получаемые ЭА наиболее приспособленные решения не соответствуют желаемым. Интерактивные генетические алгоритмы решают эту проблему, перекладывая оценку на внешних агентов, обычно людей.
The quality of the evaluation and calculation of a fitness function is fundamental to the success of an EA optimisation. It implements Darwin's principle of "survival of the fittest". Without fitness based selection mechanisms for mate selection and offspring acceptance, EA search would be blind and hardly distinguishable from the Monte Carlo method. When setting up a fitness function, one must always be aware that it is about more than just describing the desired target state. Rather, the evolutionary search on the way to the optimum should also be supported as much as possible (see also section on auxiliary objectives), if and insofar as this is not already done by the fitness function alone. If the fitness function is designed badly, the algorithm will either converge on an inappropriate solution, or will have difficulty converging at all. Definition of the fitness function is not straightforward in many cases and often is performed iteratively if the fittest solutions produced by an EA is not what is desired. Interactive genetic algorithms address this difficulty by outsourcing evaluation to external agents which are normally humans.
Оптимизация для нескольких целей
Практические приложения обычно стремятся к оптимизации нескольких, по крайней мере частично противоречивых целей. Для этого часто используются два принципиально различных подхода: оптимизация по Парето и оптимизация на основе оценки пригодности, вычисляемой как взвешенная сумма.
Practical applications usually aim at optimizing multiple and at least partially conflicting objectives. Two fundamentally different approaches are often used for this purpose, Pareto optimization and optimization based on fitness calculated using the weighted sum.
Функции взвешенной суммы и штрафов
При оптимизации с помощью взвешенной суммы отдельные значения целевых функций сначала нормализуются для обеспечения возможности их сравнения. Это можно сделать с помощью стоимостей или путем задания целевых значений и определения текущего значения как степени достижения цели. Затем стоимости или степени достижения цели могут быть сопоставлены друг с другом и, при необходимости, отображены на единую шкалу пригодности. Без ограничения общности, предполагается, что пригодность представляет собой значение, которое необходимо максимизировать. Каждой целевой функции присваивается вес в виде процентного значения, чтобы общая необработанная пригодность могла быть вычислена как взвешенная сумма: нарушение ограничений может быть учтено в определенной таким образом пригодности в виде штрафных функций. Для этого для каждого ограничения может быть определена функция, возвращающая значение между 0 и 1 в зависимости от степени нарушения, при этом результат равен 0 при отсутствии нарушения. Ранее определенная необработанная пригодность умножается на функцию (функции) штрафа, и результат является окончательной пригодностью:
When optimizing with the weighted sum, the single values of the objectives are first normalized so that they can be compared. This can be done with the help of costs or by specifying target values and determining the current value as the degree of fulfillment. Costs or degrees of fulfillment can then be compared with each other and, if required, can also be mapped to a uniform fitness scale. Without loss of generality, fitness is assumed to represent a value to be maximized. Each objective is assigned a weight in the form of a percentage value so that the overall raw fitness can be calculated as a weighted sum: A violation of restrictions can be included in the fitness determined in this way in the form of penalty functions. For this purpose, a function can be defined for each restriction which returns a value between and depending on the degree of violation, with the result being if there is no violation. The previously determined raw fitness is multiplied by the penalty function(s) and the result is then the final fitness :
Было признано на раннем этапе, что генетические алгоритмы (ГА) с их одновременно рассматриваемым множеством решений хорошо подходят для поиска решений в одном прогоне, которые достаточно хорошо покрывают фронт Парето. Помимо SPEA2, NSGA II и NSGA III зарекомендовали себя как стандартные методы. Преимущество парето-оптимизации заключается в том, что, в отличие от взвешенной суммы, она предоставляет все альтернативы, эквивалентные по целевым функциям, в качестве общего решения. Недостатком является то, что визуализация альтернатив становится проблематичной или даже невозможной при более чем четырех целевых функциях. Кроме того, вычислительные затраты увеличиваются экспоненциально с ростом числа целевых функций. Если целевых функций больше трех или четырех, некоторые из них необходимо объединять с использованием взвешенной суммы или других методов агрегирования. Это иллюстрируется смежным рисунком слева. Точка на зеленом фронте Парето достигается весами α и β, при условии, что ГА сходится к оптимуму. Направление с наибольшим приростом пригодности в множестве решений показано нарисованными стрелками. Однако в случае невыпуклого фронта невыпуклые участки фронта недостижимы с помощью взвешенной суммы. На смежном изображении справа это участок между точками A и B. Это можно частично исправить, используя расширение взвешенной суммы – каскадную взвешенную сумму. В дополнение к основным целевым функциям, вытекающим из самой задачи, может потребоваться включение вспомогательных целевых функций в оценку для поддержки достижения одной или нескольких основных целевых функций. Для иллюстрации используется пример задачи планирования. Цели оптимизации включают не только общее быстрое выполнение всех заказов, но и соблюдение крайнего срока завершения. Последнее особенно важно для планирования срочных заказов. Вторая цель не достигается исходным образцовым расписанием, как показано на смежном рисунке. Последующая мутация не меняет этого, но планирует рабочий шаг d раньше, что является необходимым промежуточным шагом для более раннего начала последнего рабочего шага e заказа. Однако, пока оценивается только крайний срок завершения заказа, пригодность измененного расписания остается неизменной, хотя это и представляет собой важный шаг к достижению цели своевременного выполнения заказа. Это можно исправить, например, путем дополнительной оценки задержки рабочих шагов. Новая целевая функция является вспомогательной, поскольку она была введена в дополнение к фактическим целевым функциям оптимизации для поддержки их достижения. Более подробное описание этого подхода и другой пример можно найти в [ссылка].
It was recognized early on that EAs with their simultaneously considered solution set are well suited to finding solutions in one run that cover the Pareto front sufficiently well. Besides the SPEA2, the NSGA II and NSGA III have established themselves as standard methods. The advantage of Pareto optimization is that, in contrast to the weighted sum, it provides all alternatives that are equivalent in terms of the objectives as an overall solution. The disadvantage is that a visualization of the alternatives becomes problematic or even impossible from four objectives on. Furthermore, the effort increases exponentially with the number of objectives. If there are more than three or four objectives, some have to be combined using the weighted sum or other aggregation methods. This is illustrated by the adjacent picture on the left. The point on the green Pareto front is reached by the weights and , provided that the EA converges to the optimum. The direction with the largest fitness gain in the solution set is shown by the drawn arrows. In case of a non convex front, however, non convex front sections are not reachable by the weighted sum. In the adjacent image on the right, this is the section between points and This can be remedied to a limited extent by using an extension of the weighted sum, the cascaded weighted sum.]] In addition to the primary objectives resulting from the task itself, it may be necessary to include auxiliary objectives in the assessment to support the achievement of one or more primary objectives. An example of a scheduling task is used for illustration purposes. The optimization goals include not only a general fast processing of all orders but also the compliance with a latest completion time. The latter is especially necessary for the scheduling of rush orders. The second goal is not achieved by the exemplary initial schedule, as shown in the adjacent figure. A following mutation does not change this, but schedules the work step d earlier, which is a necessary intermediate step for an earlier start of the last work step e of the order. As long as only the latest completion time is evaluated, however, the fitness of the mutated schedule remains unchanged, even though it represents a relevant step towards the objective of a timely completion of the order. This can be remedied, for example, by an additional evaluation of the delay of work steps. The new objective is an auxiliary one, since it was introduced in addition to the actual optimization objectives to support their achievement. A more detailed description of this approach and another example can be found in.