Функция приспособленности

Функция приспособленности (англ. fitness function) — вещественная, или целочисленная функция одной или нескольких переменных, подлежащая оптимизации в результате работы генетического алгоритма. Направляет эволюцию в сторону оптимального решения. Она является одним из частных случаев целевой функции.

История возникновения термина

Термин функция приспособленности получила свое название из генетики. Позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие максимальные значения функции приспособленности) в соответствии с эволюционным принципом выживания наиболее приспособленных.

Генетическое программирование и генетические алгоритмы

В области генетического программирования и генетических алгоритмов каждое исследуемое решение обычно представлено в виде строки чисел или символов (называемой хромосомой). Основная идея состоит в том, чтобы после каждого раунда тестирования или моделирования удалить n наихудших исследуемых решений(хромосом) и ввести в популяцию n новых решений(хромосом). Для реализации данного метода каждому исследуемому решению должно соответствовать определенное значение, которое указывает насколько близко решение подходит к искомому значению, указанное значение получается путем применения функции приспособленности. Несмотря на то, что поиском оптимального решения занимается алгоритм, основное направление в поиске задается человеком, который должен определить функцию приспособленности. Если она плохо спроектирована, алгоритм либо будет сходиться на не оптимальном решении, либо будет с трудом сходиться к решению вообще.

Функция приспособленности должна не только тесно коррелировать с искомым решением, но и быстро вычисляться. Скорость выполнения очень важна, так как типичный генетический алгоритм должен повторяться многократно (от 1000 итераций(поколений)), чтобы найти решение для нетривиальной задачи.

Применение в математике

Функция приспособленности оказывает сильное влияние на работу генетических алгоритмов и должна иметь точное и корректное определение. В задачах оптимизации функция приспособленности, как правило, оптимизируется (максимизируется) и называется целевой функцией. В задачах минимизации целевая функция преобразуется, и проблема сводится к максимизации.

В теории управления — может принимать вид функции погрешности, а в теории игр — стоимостной функции. При каждой итерации генетического алгоритма приспособленность каждой особи данной популяции оценивается при помощи функции приспособленности, и на основе этой оценки создается следующая популяция, составляющих множество потенциальных решений.

Условия работы функции

1. Функция должна быть адекватно заданной. Это означает, что для успешного поиска необходимо, чтобы распределение значений совпадало с распределением реального качества решений.
2. Функция должна иметь разнообразный рельеф, без больших «плоских» участков. То есть, несмотря на то что решение различаются, они имеют одинаковую оценку, а значит алгоритм не имеет возможности выбрать лучшее решение, выбрать направление дальнейшего развития. Эта проблема еще упоминается как «проблема поля для гольфа», где все пространство абсолютно одинаково, за исключением лишь одной точки, и является оптимальным решением - в этом случае алгоритм просто остановится или будет блуждать совершенно случайно.
3. Функция приспособленности должна требовать минимум ресурсов. Поскольку это наиболее часто используемая деталь алгоритма, она оказывает существенное влияние на его скорость работы.

Функция приспособленности превращает пространство состояний в фитнес пейзаж (адаптивный ландшафт)^{[неизвестный термин]}, где каждая точка пространства имеет определенную «высоту», в соответствии со значением ее фитнеса.

См. также

• Генетический алгоритм