В моей предыдущей статье я объяснил основы генетических алгоритмов. После публикации ко мне поступило много запросов о том, чтобы подробнее обсудить функцию фитнеса и стратегии оценки. В этой статье мы обсудим фитнес-функции и то, как придумать фитнес-функцию для данной задачи.
Что такое фитнес-функция?
Функция пригодности (также известная как функция оценки) оценивает, насколько данное решение близко к оптимальному решению желаемой проблемы. Он определяет, насколько подходящим является решение.
Почему мы используем фитнес-функции?
В генетических алгоритмах каждое решение обычно представляется в виде строки двоичных чисел, известной как хромосома. Мы должны протестировать эти решения и предложить лучший набор решений для решения данной проблемы. Следовательно, каждому решению необходимо присвоить балл, чтобы указать, насколько близко оно подошло к общей спецификации желаемого решения. Эта оценка создается путем применения функции пригодности к тесту или результатов, полученных на основе тестируемого решения.
Общие требования к фитнес-функции
Любая фитнес-функция должна удовлетворять следующим требованиям.
- Функция пригодности должна быть четко определена. Читатель должен четко понимать, как рассчитывается оценка пригодности.
- Фитнес-функция должна быть реализована эффективно. Если функция приспособленности становится узким местом алгоритма, то общая эффективность генетического алгоритма будет снижена.
- Функция приспособленности должна количественно измерять, насколько данное решение подходит для решения проблемы.
- Функция фитнеса должна давать интуитивно понятные результаты. Лучшие / худшие кандидаты должны иметь лучший / худший балл.
Как придумать фитнес-функцию для данной задачи?
У каждой задачи своя фитнес-функция. Функция фитнеса, которую следует использовать, зависит от конкретной проблемы. Придумать функцию приспособленности для данной проблемы - самая сложная часть, когда дело доходит до формулировки проблемы с использованием генетических алгоритмов.
Не существует жесткого правила, согласно которому конкретная функция должна использоваться в конкретной задаче. Тем не менее, специалисты по обработке данных приняли определенные функции в отношении определенных типов проблем.
Как правило, для задач классификации, в которых используется контролируемое обучение, в качестве функции пригодности широко используются такие меры ошибок, как евклидово расстояние e и манхэттенское расстояние.
Для задач оптимизации в качестве функции пригодности могут использоваться базовые функции, такие как сумма набора вычисленных параметров, относящихся к проблемной области.
Давайте рассмотрим несколько примеров задач и связанных с ними фитнес-функций.
Пример 1 - Генерация последовательностей
Рассмотрим пример, приведенный ниже. Я использовал этот простой пример в основном для простоты понимания.
Учитывая набор из 5 генов, которые могут содержать одно из двоичных значений 0 и 1, мы должны придумать последовательность, содержащую все единицы. Таким образом, мы должны максимально увеличить количество единиц. Это можно рассматривать как проблему оптимизации. Следовательно, функция пригодности рассматривается как количество единиц в геноме. Если есть пять единиц, значит, он имеет максимальную пригодность и решает нашу проблему. Если нет единиц, то он имеет минимальную пригодность.
Приведенный ниже код показывает, как функция пригодности реализуется для вычисления оценки пригодности.
Пример 2 - Составление расписания
Очень известный сценарий, в котором можно использовать генетические алгоритмы, - это процесс составления расписания или составление расписания.
Представьте, что вы пытаетесь составить еженедельное расписание занятий в колледже для определенной группы. Мы должны организовать занятия и составить расписание, чтобы не было конфликтов между занятиями. Здесь наша задача - поиск оптимального расписания.
Поскольку между классами не должно быть столкновений, мы должны минимизировать количество учащихся, у которых возникают конфликты между классами. Вы можете сформулировать функцию пригодности как обратную величину числа учащихся с конфликтами в классе. Чем меньше учеников с классовыми конфликтами, тем больше подходит класс.
Пример 3. Поиск значений для набора переменных, которые удовлетворяют заданному ограничению.
Рассмотрим три переменные x, y и z. Проблема состоит в том, чтобы найти лучший набор значений для x, y и z, чтобы их общее значение было равно значению t.
x + y + z = t
Мы должны уменьшить сумму x + y + z от отклонения от t, т.е. | x + y + z - t | должно быть равно нулю. Следовательно, фитнес-функцию можно рассматривать как обратную | x + y + z - t |.
Fitness function = 1/|x + y + z - t|
Это несколько примеров приложений, в которых используются генетические алгоритмы и как придумывать их фитнес-функции. Я использовал эти простые примеры для облегчения понимания. При моделировании сложных проблем реального мира мы можем не получить таких простых фитнес-функций.
Заключительное примечание
Фитнес-функция должна измерять, насколько хорошо ваше решение. В частности, он должен уметь обрабатывать любые доступные решения и указывать правильный способ их улучшения.
Например, функция приспособленности, которая равна нулю, если ответ не является правильным, не является хорошей, потому что она не помогает вам понять, насколько близко решение к правильному ответу. Кроме того, фитнес-функция, которая увеличивается по мере того, как решения улучшаются, но не определяет лучшее решение, тоже не так хороша, потому что ваша популяция улучшится до определенного момента, а затем застрянет.
Вы должны поэкспериментировать с проблемой, посмотреть по-разному и подумать, какую функцию вы можете использовать, чтобы проверить, насколько хорошо ваше решение. Вам нужна функция, которая дает низкие значения для плохих решений и высокие значения для хороших решений. Со временем вы научитесь лучше определять фитнес-функцию для конкретной задачи.
Надеюсь, вы получили общее представление о том, как определить функцию приспособленности для данной задачи, для решения которой используются генетические алгоритмы.
Спасибо за прочтение…
