Обзор генетического алгоритма

Методы оптимизации - это методы, которые используются для поиска наилучшего решения из всех возможных решений, доступных при существующих ограничениях. Таким образом, Генетический алгоритм является одним из таких алгоритмов оптимизации, который построен на основе естественного эволюционного процесса нашей природы. Идея естественного отбора и генетического наследования используется здесь. В отличие от других алгоритмов он использует управляемый случайный поиск, т. Е. Находит оптимальное решение, начиная со случайной функции начальной стоимости, а затем выполняя поиск только в пространстве, которое имело наименьшую стоимость (в управляемом направлении). Подходит, когда вы работаете с огромными и сложными наборами данных.

Что такое генетический алгоритм?

Генетический алгоритм основан на генетической структуре и поведении хромосомы популяции. Следующие вещи являются основой генетических алгоритмов.

  • Каждая хромосома указывает на возможное решение. Таким образом, популяция представляет собой коллекцию хромосом.
  • Каждый человек в популяции характеризуется фитнес-функцией. Лучшее фитнес лучше решение.
  • Из доступных особей в популяции лучшие особи используются для размножения потомков следующего поколения.
  • Произведенное потомство будет иметь черты обоих родителей и является результатом мутации. Мутация - это небольшое изменение в структуре гена.

Фазы генетического алгоритма

Ниже приведены различные фазы генетического алгоритма:

1. Инициализация населения (кодирование)

  • Каждый ген представляет параметр (переменную) в решении. Этот набор параметров, который формирует решение, является хромосомой. Популяция представляет собой коллекцию хромосом.
  • Порядок генов на хромосоме имеет значение.
  • В большинстве случаев хромосомы отображаются в двоичном виде как 0 и 1, но возможны и другие кодировки.

2. Фитнес-функция

  • Из доступных хромосом мы должны выбрать лучшие для размножения потомков, поэтому каждой хромосоме присваивается значение пригодности.
  • Оценка пригодности помогает выбрать особей, которые будут использоваться для размножения.

3. Выбор

  • Основная цель этого этапа - найти регион, в котором больше шансов найти лучшее решение.
  • Вдохновение для этого от выживания сильнейшего.
  • Это должен быть баланс между исследованием и эксплуатацией пространства поиска.
  • Г.А. пытается переместить генотип в область поиска с большей приспособленностью.
  • Слишком сильный уклон выбора пригодности может привести к неоптимальным решениям.
  • Слишком маленький выбор фитнес-смещения приводит к несфокусированному поиску.
  • Таким образом, используется пропорциональный отбор Фитнес, который также известен как выбор колеса рулетки, является генетическим оператором, используемым в генетических алгоритмах для выбора потенциально полезных решений для рекомбинации.

4. Воспроизведение

Генерация потомков происходит двумя способами:

  • Кроссовер
  • перегласовка

а) кроссовер

Кроссовер является наиболее важной стадией в генетическом алгоритме. Во время кроссовера случайная точка выбирается при спаривании пары родителей для генерации потомков.

Есть 3 основных типа кроссовера.

  • Одиночное пересечение: точка на хромосомах обоих родителей выбирается случайным образом и обозначается как «точка пересечения». Биты справа от этой точки обмениваются между двумя родительскими хромосомами.
  • Двухточечный кроссовер: две точки кроссовера выбираются случайным образом из родительских хромосом. Биты между двумя точками меняются местами между родительскими организмами.
  • Унифицированный кроссовер: В равномерном кроссовере, как правило, каждый бит выбирается из любого из родителей с равной вероятностью.

Новое потомство добавлено к населению.

б) мутация

У нескольких новых потомков некоторые из их генов могут подвергаться мутации с низкой случайной вероятностью. Это указывает на то, что некоторые биты в битовой хромосоме можно перевернуть. Мутация, случается, заботится о разнообразии среди населения и останавливает преждевременную конвергенцию.

5. Конвергенция (когда остановиться)

Несколько правил, которые следуют, которые говорят, когда остановиться, следующие:

  • Когда нет улучшения качества решения после завершения определенного количества поколений, заданных заранее.
  • Когда достигнут жесткий и быстрый диапазон поколений и времени.
  • До приемлемого решения получается.

Применение генетического алгоритма

В этом разделе мы обсудим некоторые области, в которых часто применяется генетический алгоритм.

1. Путешествия и отправление

Задача коммивояжера - одно из основных применений генетического алгоритма. Например, когда планировщика поездки просят спланировать поездку, он воспользуется генетическим алгоритмом, который помогает не только снизить общую стоимость поездки, но и сократить время. Кроме того, GE используется для планирования доставки. продуктов с места на место лучшим эффективным способом.

2. Робототехника

Генетический алгоритм широко используется в области робототехники. Роботы отличаются друг от друга целью, для которой они созданы. Например, немногие созданы для задачи по приготовлению пищи, немногие созданы для учебных задач и т. Д.

  • Выбор важных функций в данном наборе данных.
  • В традиционном методе важные элементы в наборе данных выбираются с использованием следующего метода. То есть вы смотрите на важность этой модели, затем устанавливаете пороговое значение для объектов, и, если функция имеет значение важности, превышающее пороговое значение, это считается.
  • Но здесь мы используем метод, называемый проблемой ранца.
  • Мы снова начнем с популяции хромосомы, где каждая хромосома будет двоичной строкой. 1 будет означать «включение» элемента в модель, а 0 будет означать «исключение» элемента в модели.
  • Фитнес-функция здесь будет нашей метрикой точности соревнования. Чем более точен наш набор хромосом в прогнозировании, тем больше он будет соответствовать.
  • Есть много других приложений генетических алгоритмов, таких как анализ ДНК, планирование приложений, инженерное проектирование.

Вывод

В текущем сценарии GE используется в крупных производственных компаниях, таких как авиация и т. Д., Для оптимизации использования времени и ресурсов. Дальнейшие ученые работают над поиском новых способов объединения генетических алгоритмов с другими методами оптимизации.

Рекомендуемые статьи

Это руководство к Что такое генетический алгоритм? Здесь мы обсуждаем введение, фазы и применения генетического алгоритма. Вы также можете просмотреть наши другие предлагаемые статьи -

  1. Алгоритмы маршрутизации
  2. Типы алгоритмов
  3. Алгоритмы нейронной сети
  4. Алгоритмы интеллектуального анализа данных
  5. руководство к примерам алгоритмов C ++

Категория:

Большое количество данных