Более простой подход к пониманию генетического алгоритма на примере в увлекательной игровой форме.

Прежде чем понять генетический алгоритм, давайте разберемся, что такое метод оптимизации?

Техника оптимизации:

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

Теперь поймите 'Генетический алгоритм':

Генетический алгоритм — это один из таких алгоритмов оптимизации, построенный на основе естественного эволюционного процесса нашей природы.

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

Основа генетического алгоритма:

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

Жизненный цикл генетического алгоритма:

  1. Инициализация населения:

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

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

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

3. Выбор:

Основная цель этого этапа — найти регион, где шансов получить наилучшее решение больше.

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

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

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

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

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

Итак, генетический алгоритм работает следующим образом:

  1. Алгоритм начинается с создания случайной начальной популяции.

2. Затем алгоритм создает последовательность новых популяций. На каждом этапе алгоритм использует особей текущего поколения для создания следующей популяции. Для создания новой популяции алгоритм выполняет следующие шаги:

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

3. Алгоритм останавливается, когда выполняется один из критериев остановки.

Чтобы конкретизировать наше понимание, давайте разберемся с ним более реалистично:

Откройте эту ссылку ниже и потратьте 30 секунд, чтобы просто посмотреть ее:

http://boxcar2d.com/

В этом приложении мы должны
построить простую модель автомобиля для передвижения по этой местности.

Поместите на него где-нибудь несколько колес, добавьте набор треугольников в качестве шасси, и вперед. Чем дальше, тем лучше машина, и цель состоит в том, чтобы спроектировать лучшую машину, которую вы только можете.

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

Он соблюдает правило, которое мы называем: выживает сильнейший. Это означает, что лучшие из существующих решений берутся и смешиваются друг с другом для создания новых решений, которые, как ожидается, также будут работать хорошо. Как и в случае эволюции в природе, мутации
также могут происходить, что означает, что в ДНК-код решения вносятся случайные изменения. Мы знаем из природы, что эволюция работает чрезвычайно
хорошо, и чем больше мы запускаем эту программу генетической оптимизации, тем лучше получаются решения.

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

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

2. Нейронные сети. ГА также используются для обучения нейронных сетей, особенно рекуррентных нейронных сетей.

3. Обработка изображений. GA используются для различных задач цифровой обработки изображений (DIP), а также для плотного сопоставления пикселей.

4. Генерация траектории робота. ГА использовались для планирования пути, по которому движется рука робота, перемещаясь из одной точки в другую.

5. Проблемы маршрутизации транспортных средств — с несколькими временными окнами, несколькими депо и разнородным парком.

Ограничения :

  1. Генетические алгоритмы плохо масштабируются со сложностью.

2. «Лучшее» решение только по сравнению с другими решениями. В результате критерий остановки не во всех задачах ясен.

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

4. ГА не могут эффективно решать проблемы, в которых единственной мерой пригодности является одна мера правильности/неправильности (например, проблемы принятия решений), поскольку нет способа сойтись в решении.

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

ВЫВОД :

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

ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА :

ВИКИПЕДИЯ

ПОИСК ГУГЛ

GOOGLE КАРТИНКИ

YOUTUBE