Что означает термин мутация алгоритма в контексте генетических алгоритмов
Генетический алгоритм
Материал из MachineLearning.
Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
Содержание
Постановка задачи
Для функции приспособленности в пространстве поиска требуется найти (или ).
Описание алгоритма
В процессе селекции выживают отбирают только несколько лучших пробных решений, остальные далее не используются. Скрещивание за место пары решений создаёт другую, элементы которой перемешаны каким-то особым образом. Мутация случайным образом меняет какую-нибудь компоненту пробного решения на иную.
Иные обозначения
Несмотря на внушительный возраст, в генетических алгоритма до сих пор используют различную терминологию, проистекающей как из генетики, так и из кибернетики.
Встречаются такие обозначения:
Применение генетических алгоритмов
Генетические алгоритмы применяются для решения следующих задач:
Подробное описание алгоритма
Кодирование пространства поиска
В ГА часто используют следующие типы кодирования компонент пространства поиска:
Начальная популяция
Оценка приспособленности
Оператор отбора (селекции)
На этом этапе отбирается оптимальная популяция для дальнейшего размножения. Обычно берут определённое число лучших по приспособленности. Имеет смысл также отбрасывать «клонов», т.е. особей с одинаковым набором генов.
Оператор скрещивания
Оператор мутаций
Критерии останова
Эвристики
Генетические алгоритмы богаты возможностями встраивания различных эвристик. До сих пор не существует (и не будет!) точных критериев оптимального размера популяции, способов мутаций и скрещивания, выбора начальной популяции и т.п.
Плоидность
Мета ГА
Простейший пример ГА
Подбор ключа 2048 бит
Эффективность генетических алгоритмов
Холланд недвусмысленно пишет[1], что при прочих равных условиях ГА будет работать хуже, чем специальный алгоритм, рассчитанный на конкретную задачу (тип признаков, целевую функцию). Например, полный перебор конечного небольшого пространства или любой эффективных алгоритм спуска будет всегда эффективнее чем ГА. Тем не менее, в ситуации, когда о задаче ничего a priori не известно, можно полагаться на результат работы простейшего генетического алгоритма как некого приближения.
Существуют некоторый класс функций (Hyperplane-defined functions, Holland), с которым за приемлемое время[2] справляются только генетические алгоритмы.
Тестовые функции
В процессе разработки эффективной реализации генетического алгоритма появляется необходимость простой тестовой функции, которая
Мнения
Конвергенция с генетикой и синтетической теории эволюции
Прообраз генетического алгоритма пришёл из биологии и, несомненно, продолжает «подсматривать» оттуда ответы на многие вопросы, возникающие при проектированию эффективных реализаций генетических алгоритмов. Более того, идеи по оптимизации ГА находят подтверждение и у биологов. Например, такие явления как га- ди- и квадру- плоидные наборы хромосом, инцест, удвоение гена, управление скоростью мутаций, триггеры и т.п. Тем не менее, математика и кибернетика позволяет выйти за пределы химической реальности клетки и представить n-плоидный набор хромосом, объектные сущности вместо генов и т.п.
Нейронные сети и эволюционное моделирование
ИНС и ГА часто пытаются применять в тандеме, т.к. и те и другие имеют корни из биологии. Тем не менее (см. выше об эффективности ), во-первых алгоритм обратного распространения ошибки настройки ИНС работает значительно (на порядок) быстрее в простых случаях. А во-вторых, настройка нейронной сети в биологии происходит методом, который, скорее всего, значительно разнится с генетическим подходом.
Аналогия с другими алгоритмами
В случае отключённого кроссинговера ГА начинает вести себя по образу случайного поиска. Также у ГА есть аналогия со случайным поиском с адаптацией. Во многих стохастических алгоритмах можно найти аналогию с ГА.
Играем с генетическими алгоритмами
Одним субботним декабрьским вечером сидел я над книгой The Blind Watchmaker (Слепой Часовщик), как на глаза мне попался невероятно интересный эксперимент: возьмём любое предложение, например Шекспировскую строку: Methinks it is like a weasel и случайную строку такой же длины: wdltmnlt dtjbkwirzrezlmqco p и начнем вносить в неё случайные изменения. Через сколько поколений эта случайная строка превратится в Шекспировскую строку, если выживать будут лишь потомки более похожие на Шекспировскую?
Сегодня мы повторим этот эксперимент, но в уже совершенно другом масштабе.
Что такое генетический алгоритм
В области искусственного интеллекта под генетическим алгоритмом подразумевается эвристика поиска решений, основанная на естественном отборе. Как правило применяется для задач, где пространство поиска насколько огромно, что точное решение найти невозможно и эвристическое решение удовлетворяет требованиям. Сама задача имеет некоторую функцию качества решения, которую необходимо максимизировать.
В самом простом виде генетический алгоритм имеет следующую структуру (см. схему): начинаем с некоторым решением, в нашем случае, это случайная строка; вносим мутации, например, меняем случайно выбранную букву в строке на случайно выбранную букву и получаем новый набор строк (k мутаций на строку); из них отбираем только те, которые ближе к шекспировской (по количеству совпадающих символом), например 10 таких строк, если шекспировской среди них нет, то запускаем процесс заново.
Почему это работает
Во многом генетические алгоритмы похожи на классические методы оптимизации, популяция — это набор текущих точек, мутации — это исследование соседних точек, отбор — это выбор новых точек для поиска решения в условиях ограниченных вычислительных ресурсов.
Популяция всегда стремится к ближайшему максимуму, так как мы отбираем текущие точки поиска, как имеющие максимальное значение (все остальные точки «умрут», не выдержат конкуренции с ближайшим максимумом). Так как размер популяции значительный, а значит вероятность сделать хотя бы один шаг в направлении максимума не пренебрежимо мала, то через некоторое количество шагов популяция сместится в сторону локального максимума. А потомки точки, смещенной ближе к максимуму, имеют большую «выживаемость». Значит через достаточное количество шагов, потомки этой точки начнут доминировать в популяции и вся она сместится к максимуму.
Визуализация популяции стремящейся к локальному максимуму:
(due to Randy Olson)
Формализуем задачу со случайной строкой
Входные данные: строка S
Выходные данные: натуральное число N, равное количеству поколений необходимых для преобразования случайной строки длины len(S) в строку S
Что в нашем случае мутация? Под мутацией строки S мы понимаем замену одного случайно выбранного символа из строки S на другой произвольный символ алфавита. В данной задаче мы используем только символы нижнего регистра латиницы и пробел.
Что такое изначальная популяция (initial population в схеме)? Это случайная строка равная по длине входной строке S.
Что такое потомки (offsprings)? Пусть мы зафиксировали количество мутаций одной строки на константу k, тогда потомки — это k мутаций каждой строки текущего поколения.
Что такое выжившие (survivors)? Пусть мы зафиксировали размер популяции на константу h, тогда выжившие — это h строк максимально похожих на входную строку S.
В псевдокоде (подозрительно похожем на python) это выглядит следующим образом:
Пример работы алгоритма
Рассмотрим следующую строку: The quick brown fox jumps over the lazy dog и воспроизведём для неё вывод нашей программы:
Рассмотрим цепочку изменений (слева номер поколения):
Как мы видим каждое поколение отличается не более, чем на один символ друг от друга. Всего потребовалось 46 поколений, чтобы добраться от rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopyk до the quick brown fox jumps over the lazy dog с помощью мутаций и отбора.
Эксперименты с классикой
Отдельные примеры, шекспировской строка или английская панграмма про лису, интересны, но не слишком убедительны. Поэтому и решил рассмотреть более интересный вопрос: что будет если взять пару классических произведений, разбить их на предложения и посчитать число поколений для каждого из них? Какой будет характер зависимости количества поколений от строки (например, от её длины)?
В качестве классических произведений выбрал To Kill a Mocking Bird by Harper Lee (Убить Пересмешника, Харпер Ли) и Catcher in the Rye by J.D. Salinger (Над Пропастью во Ржи, Джей Ди Сэлинджер). Мы будем измерять два параметра — распределение количества поколений по предложениям и зависимость количества поколений от длины строки (есть ли корреляция?).
Параметры были следующие: количество потомков у строки: 100; количество выживших в поколении: 10.
Результаты
Как мы видим, для большинства предложений получилось достичь строку достаточно быстро, требуются менее 100 итераций, практически для всех предложений достаточно 200 итераций (среди всех предложений было только одно, которому потребовалось 1135 итераций, судя по предложению алгоритм разбивки ошибся и склеил несколько предложений в одно):
Корреляция между длиной строки и количеством поколений идеальная. Это означает, что практически в каждом поколении удавалось продвинуться на шаг ближе к целевой строке.
R^2 равен 0.996 и 0.997 соответственно.
Таким образом экспериментально установили, что в условиях нашей задачи для любой входной строки S, количество поколений линейно зависит от длины строки, что согласуется с исходными предположениями.
Код и данные
Весь код, python — генетический алгоритм\обработка текста и R — визуализация, доступен в github:
github.com/SergeyParamonov/genetics-experiments
Выводы
Мы разобрались с базовой структурой генетических алгоритмов и применили для решения задачи о мутации строки. В результате экспериментов с классическими текстами мы обнаружили, что в наших условиях существуют линейная зависимость между длиной строки и количеством поколений необходимых для достижения входной строки.
Так же мы отметили, что базовая структура поиска может быть модифицирована (например, с помощью сrossover — использования несколько членов поколения для создания потомков) для решения широкого класса задач оптимизации, где слишком сложно искать точное решение.
Генетические алгоритмы — Краткое руководство
Введение в оптимизацию
Оптимизация относится к нахождению значений входных данных таким образом, что мы получаем «наилучшие» выходные значения. Определение «наилучшего» варьируется от проблемы к проблеме, но в математических терминах оно относится к максимизации или минимизации одной или нескольких целевых функций путем изменения входных параметров.
Множество всех возможных решений или значений, которые могут принимать входные данные, составляют пространство поиска. В этом пространстве поиска лежит точка или набор точек, которые дают оптимальное решение. Цель оптимизации — найти эту точку или набор точек в пространстве поиска.
Что такое генетические алгоритмы?
GA были разработаны Джоном Холландом и его студентами и коллегами из Мичиганского университета, прежде всего Дэвидом Э. Голдбергом, и с тех пор пробовали решать различные задачи оптимизации с высокой степенью успеха.
В ГА у нас есть пул или совокупность возможных решений данной проблемы. Эти решения затем подвергаются рекомбинации и мутации (как в естественной генетике), порождая новых детей, и процесс повторяется на протяжении разных поколений. Каждому индивидууму (или подходящему решению) присваивается значение пригодности (в зависимости от значения его целевой функции), и более подходящие индивидуумы получают более высокий шанс на спаривание и получают больше «более подходящих» индивидуумов. Это соответствует дарвиновской теории выживания наиболее приспособленных.
Таким образом, мы продолжаем «развивать» лучших людей или решения из поколения в поколение, пока не достигнем критерия остановки.
Генетические алгоритмы по своей природе достаточно рандомизированы, но они выполняют намного лучше, чем случайный локальный поиск (в котором мы просто пробуем различные случайные решения, отслеживая лучшие на данный момент), поскольку они также используют историческую информацию.
Преимущества ГА
У GA есть различные преимущества, которые сделали их чрезвычайно популярными. К ним относятся —
Не требует никакой производной информации (которая может быть недоступна для многих реальных проблем).
Это быстрее и эффективнее по сравнению с традиционными методами.
Имеет очень хорошие параллельные возможности.
Оптимизирует как непрерывные, так и дискретные функции, а также многоцелевые задачи.
Предоставляет список «хороших» решений, а не просто одно решение.
Всегда получает ответ на проблему, которая со временем становится лучше.
Полезно, когда пространство поиска очень велико и задействовано большое количество параметров.
Не требует никакой производной информации (которая может быть недоступна для многих реальных проблем).
Это быстрее и эффективнее по сравнению с традиционными методами.
Имеет очень хорошие параллельные возможности.
Оптимизирует как непрерывные, так и дискретные функции, а также многоцелевые задачи.
Предоставляет список «хороших» решений, а не просто одно решение.
Всегда получает ответ на проблему, которая со временем становится лучше.
Полезно, когда пространство поиска очень велико и задействовано большое количество параметров.
Ограничения ГА
Как и любая техника, ГА также страдают от нескольких ограничений. К ним относятся —
GA не подходят для всех проблем, особенно для задач, которые просты и для которых доступна производная информация.
Значение пригодности рассчитывается многократно, что может быть вычислительно дорогостоящим для некоторых задач.
Будучи стохастическим, нет никаких гарантий относительно оптимальности или качества решения.
Если не реализовано должным образом, GA может не сходиться к оптимальному решению.
GA не подходят для всех проблем, особенно для задач, которые просты и для которых доступна производная информация.
Значение пригодности рассчитывается многократно, что может быть вычислительно дорогостоящим для некоторых задач.
Будучи стохастическим, нет никаких гарантий относительно оптимальности или качества решения.
Если не реализовано должным образом, GA может не сходиться к оптимальному решению.
GA — Мотивация
Генетические алгоритмы обладают способностью предоставлять «достаточно хорошее» решение «достаточно быстро». Это делает генетические алгоритмы привлекательными для использования при решении задач оптимизации. Причины, по которым нужны ГА, следующие:
Решение сложных проблем
Отказ градиентных методов
Традиционные методы, основанные на исчислении, работают, начиная со случайной точки и двигаясь в направлении градиента, пока мы не достигнем вершины холма. Этот метод эффективен и очень хорошо работает для однопиковых целевых функций, таких как функция стоимости в линейной регрессии. Но в большинстве реальных ситуаций у нас есть очень сложная проблема, называемая ландшафтами, которые состоят из множества вершин и долин, что приводит к сбою таких методов, поскольку они страдают от присущей им тенденции застревания в локальных оптимальных условиях. как показано на следующем рисунке.
Быстрое получение хорошего решения
У некоторых сложных проблем, таких как Задача коммивояжера (TSP), есть реальные приложения, такие как поиск пути и VLSI Design. Теперь представьте, что вы используете свою систему GPS-навигации, и для расчета «оптимального» пути от источника до пункта назначения требуется несколько минут (или даже нескольких часов). Задержка в таких реальных приложениях неприемлема, и поэтому требуется «достаточно хорошее» решение, которое доставляется «быстро».
Генетические алгоритмы — основы
Основная терминология
Прежде чем начать обсуждение генетических алгоритмов, важно ознакомиться с некоторой базовой терминологией, которая будет использоваться в этом учебном пособии.
Население — это подмножество всех возможных (закодированных) решений данной проблемы. Население для ГА аналогично населению для людей, за исключением того, что вместо людей у нас есть кандидатские решения, представляющие людей.
Ген — ген является одним из элементов хромосомы.
Аллель — это значение, которое ген принимает для конкретной хромосомы.
Население — это подмножество всех возможных (закодированных) решений данной проблемы. Население для ГА аналогично населению для людей, за исключением того, что вместо людей у нас есть кандидатские решения, представляющие людей.
Ген — ген является одним из элементов хромосомы.
Аллель — это значение, которое ген принимает для конкретной хромосомы.
Генотип — генотип — популяция в вычислительном пространстве. В вычислительном пространстве решения представлены таким способом, который можно легко понять и манипулировать с помощью вычислительной системы.
Фенотип. Фенотип — это совокупность в реальном пространстве решений реального мира, в которой решения представлены так, как они представлены в ситуациях реального мира.
Декодирование и кодирование — Для простых задач фенотип и пространство генотипа одинаковы. Однако в большинстве случаев пространства фенотипа и генотипа различны. Декодирование — это процесс преобразования решения из генотипа в пространство фенотипа, в то время как кодирование — это процесс преобразования из фенотипа в пространство генотипа. Декодирование должно быть быстрым, поскольку оно выполняется многократно в GA во время вычисления значения пригодности.
Например, рассмотрим проблему ранца 0/1. Пространство фенотипа состоит из решений, которые просто содержат номера предметов для выбора.
Однако в пространстве генотипа его можно представить в виде двоичной строки длиной n (где n — количество элементов). 0 в позиции x означает, что x- й элемент выбран, а 1 — наоборот. Это тот случай, когда генотип и фенотип пространства различаются.
Генотип — генотип — популяция в вычислительном пространстве. В вычислительном пространстве решения представлены таким способом, который можно легко понять и манипулировать с помощью вычислительной системы.
Фенотип. Фенотип — это совокупность в реальном пространстве решений реального мира, в которой решения представлены так, как они представлены в ситуациях реального мира.
Декодирование и кодирование — Для простых задач фенотип и пространство генотипа одинаковы. Однако в большинстве случаев пространства фенотипа и генотипа различны. Декодирование — это процесс преобразования решения из генотипа в пространство фенотипа, в то время как кодирование — это процесс преобразования из фенотипа в пространство генотипа. Декодирование должно быть быстрым, поскольку оно выполняется многократно в GA во время вычисления значения пригодности.
Например, рассмотрим проблему ранца 0/1. Пространство фенотипа состоит из решений, которые просто содержат номера предметов для выбора.
Однако в пространстве генотипа его можно представить в виде двоичной строки длиной n (где n — количество элементов). 0 в позиции x означает, что x- й элемент выбран, а 1 — наоборот. Это тот случай, когда генотип и фенотип пространства различаются.
Функция пригодности — просто определенная функция пригодности — это функция, которая принимает решение в качестве входных данных и выдает пригодность решения в качестве выходных данных. В некоторых случаях фитнес-функция и целевая функция могут быть одинаковыми, в то время как в других они могут различаться в зависимости от проблемы.
Генетические операторы — Они изменяют генетический состав потомства. К ним относятся кроссовер, мутация, отбор и т. Д.
Функция пригодности — просто определенная функция пригодности — это функция, которая принимает решение в качестве входных данных и выдает пригодность решения в качестве выходных данных. В некоторых случаях фитнес-функция и целевая функция могут быть одинаковыми, в то время как в других они могут различаться в зависимости от проблемы.
Генетические операторы — Они изменяют генетический состав потомства. К ним относятся кроссовер, мутация, отбор и т. Д.
Базовая структура
Основная структура ГА выглядит следующим образом —
Мы начнем с начальной популяции (которая может быть сгенерирована случайным образом или посеяна другими эвристиками), выбираем родителей из этой популяции для спаривания. Примените кроссовер и операторы мутации на родителях, чтобы произвести новых потомков. И, наконец, эти потомки заменяют существующих людей в популяции, и процесс повторяется. Таким образом, генетические алгоритмы в некоторой степени пытаются имитировать эволюцию человека.
Каждый из следующих шагов рассматривается в отдельной главе далее в этом руководстве.
Обобщенный псевдокод для GA объясняется в следующей программе:
Представление генотипа
Одним из наиболее важных решений, которые необходимо принять при реализации генетического алгоритма, является определение представления, которое мы будем использовать для представления наших решений. Было отмечено, что неправильное представление может привести к плохой производительности ГА.
Следовательно, выбор правильного представления, правильное определение отображений между фенотипом и пространством генотипа имеет важное значение для успеха ГА.
В этом разделе мы представляем некоторые из наиболее часто используемых представлений для генетических алгоритмов. Тем не менее, представление в значительной степени зависит от проблемы, и читатель может обнаружить, что другое представление или сочетание представлений, упомянутых здесь, могут лучше удовлетворить его / ее проблему.
Бинарное Представление
Это одно из самых простых и широко используемых представлений в ГА. В этом типе представления генотип состоит из битовых строк.
Для некоторых задач, когда пространство решений состоит из логических переменных решения — да или нет, двоичное представление является естественным. Возьмем, к примеру, проблему ранца 0/1. Если есть n элементов, мы можем представить решение в виде двоичной строки из n элементов, где x- й элемент сообщает, выбран ли элемент x (1) или нет (0).
Для других задач, в частности тех, которые касаются чисел, мы можем представить числа с их двоичным представлением. Проблема с этим типом кодирования состоит в том, что разные биты имеют разное значение, и поэтому операторы мутации и кроссовера могут иметь нежелательные последствия. Эту проблему можно решить в некоторой степени, используя кодирование Грея, поскольку изменение в один бит не оказывает существенного влияния на решение.
Реальное представление
Для задач, где мы хотим определить гены, используя непрерывные, а не дискретные переменные, реальное представление является наиболее естественным. Точность этих вещественных чисел или чисел с плавающей точкой, однако, ограничена компьютером.
Целочисленное представление
Для дискретных генов мы не всегда можем ограничить пространство решения бинарным «да» или «нет». Например, если мы хотим кодировать четыре расстояния — север, юг, восток и запад, мы можем кодировать их как . В таких случаях желательно целочисленное представление.
Представление перестановки
Во многих задачах решение представлено порядком элементов. В таких случаях представление перестановки является наиболее подходящим.
Классическим примером этого представления является проблема коммивояжера (TSP). При этом продавец должен совершить экскурсию по всем городам, посетить каждый город ровно один раз и вернуться в стартовый город. Общая дистанция тура должна быть минимизирована. Решением этого TSP является, естественно, упорядочение или перестановка всех городов, и поэтому использование перестановочного представления имеет смысл для этой проблемы.
Генетические Алгоритмы — Население
Население является подмножеством решений в нынешнем поколении. Он также может быть определен как набор хромосом. Есть несколько вещей, которые следует иметь в виду при работе с населением ГА —
Разнообразие населения должно быть сохранено, иначе это может привести к преждевременной конвергенции.
Размер популяции не должен быть очень большим, так как это может привести к замедлению ГА, в то время как меньшая популяция может оказаться недостаточной для хорошего спаривания. Следовательно, оптимальный размер популяции должен решаться методом проб и ошибок.
Разнообразие населения должно быть сохранено, иначе это может привести к преждевременной конвергенции.
Размер популяции не должен быть очень большим, так как это может привести к замедлению ГА, в то время как меньшая популяция может оказаться недостаточной для хорошего спаривания. Следовательно, оптимальный размер популяции должен решаться методом проб и ошибок.
Инициализация населения
Существует два основных метода инициализации населения в GA. Они —
Случайная инициализация — заполнить начальную популяцию совершенно случайными решениями.
Эвристическая инициализация — Заполните начальную популяцию, используя известную эвристику для задачи.
Случайная инициализация — заполнить начальную популяцию совершенно случайными решениями.
Эвристическая инициализация — Заполните начальную популяцию, используя известную эвристику для задачи.
Наблюдалось, что вся популяция не должна быть инициализирована с использованием эвристики, поскольку это может привести к тому, что популяция будет иметь схожие решения и очень небольшое разнообразие. Экспериментально наблюдалось, что случайные решения — те, которые приводят население к оптимальности. Следовательно, с помощью эвристической инициализации мы просто заполняем популяцию парой хороших решений, заполняя остальные случайными решениями, а не заполняем все население эвристическими решениями.
Также было отмечено, что эвристическая инициализация в некоторых случаях влияет только на начальную приспособленность населения, но, в конце концов, именно разнообразие решений приводит к оптимальности.
Модели народонаселения
Есть две широко используемые модели населения —
Устойчивое состояние
Generational
В модели поколений мы генерируем «n» потомков, где n — это размер популяции, а вся популяция заменяется новой в конце итерации.
Генетические алгоритмы — Фитнес-функция
Просто определенная фитнес-функция — это функция, которая принимает в качестве входных данных возможное решение проблемы и выдает в качестве выходных данных то, насколько «соответствует» нашему, насколько «хорошим» является решение по отношению к рассматриваемой проблеме.
Расчет значения пригодности проводится повторно в GA, и поэтому он должен быть достаточно быстрым. Медленное вычисление значения пригодности может отрицательно повлиять на GA и сделать его исключительно медленным.
В большинстве случаев фитнес-функция и целевая функция совпадают с целью — максимизировать или минимизировать данную целевую функцию. Однако для более сложных задач с несколькими целями и ограничениями конструктор алгоритмов может выбрать другую пригодную функцию.
Фитнес-функция должна обладать следующими характеристиками —
Фитнес-функция должна быть достаточно быстрой для вычисления.
Он должен количественно измерить, насколько подходит данное решение или как индивидуумы могут быть получены из данного решения.
Фитнес-функция должна быть достаточно быстрой для вычисления.
Он должен количественно измерить, насколько подходит данное решение или как индивидуумы могут быть получены из данного решения.
В некоторых случаях непосредственный расчет фитнес-функции может оказаться невозможным из-за сложностей, присущих данной проблеме. В таких случаях мы выполняем фитнес-аппроксимацию в соответствии с нашими потребностями.
На следующем рисунке показан расчет пригодности для решения рюкзака 0/1. Это простая фитнес-функция, которая просто суммирует значения прибыли выбранных предметов (которые имеют 1), сканируя элементы слева направо, пока рюкзак не заполнится.
Генетические алгоритмы — выбор родителей
Выбор родителей — это процесс выбора родителей, которые спариваются и рекомбинируют, чтобы создать потомство для следующего поколения. Выбор родителей очень важен для скорости конвергенции ГА, поскольку хорошие родители подталкивают людей к лучшим и более подходящим решениям.
Однако следует позаботиться о том, чтобы одно чрезвычайно подходящее решение не охватило всю совокупность в течение нескольких поколений, поскольку это приводит к тому, что решения в пространстве решений находятся близко друг к другу, что приводит к потере разнообразия. Поддержание хорошего разнообразия в популяции чрезвычайно важно для успеха ГА. Это поглощение всей совокупности одним чрезвычайно подходящим решением известно как преждевременная конвергенция и является нежелательным условием в GA.
Фитнес пропорциональный выбор
Фитнес пропорциональный отбор является одним из самых популярных способов родительского отбора. В этом каждый человек может стать родителем с вероятностью, которая пропорциональна его пригодности. Таким образом, у людей, имеющих более крепкие шансы, больше шансов на спаривание и распространение своих возможностей для следующего поколения. Таким образом, такая стратегия отбора оказывает давление отбора на более подходящих людей в популяции, развивая лучших людей с течением времени.
Возможны две реализации пропорционального выбора фитнеса —
Выбор колеса рулетки
При выборе колеса рулетки круговое колесо делится, как описано выше. Фиксированная точка выбирается на окружности колеса, как показано, и колесо вращается. Область колеса, которая находится перед фиксированной точкой, выбирается в качестве родительской. Для второго родителя тот же процесс повторяется.