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

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

Генетический алгоритм перезапуска базы -

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

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

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

Другой способ думать об этом состоит в том, что мы выполняем «k» параллельных операций скрещивания и мутации во время традиционного генетического алгоритма. Это дает нам больше разнообразия на этапах эволюции алгоритма.

Теперь давайте перейдем к главному моменту этой статьи, т.е. …..

Модифицированный генетический алгоритм -

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

Чтобы лучше понять подход, давайте попробуем понять это с помощью изображения ниже:

График выше имеет несколько локальных минимумов, которые представляют угрозу для традиционного подхода. Чтобы решить эту проблему, мы сначала разделим ось X графика (т. е. пространство поиска) на «M» подмножеств, каждое из которых имеет размер популяции «subM». Затем мы запускаем «M» параллельных генетических алгоритмов над каждым подмножеством. Это дает нам локальные минимумы для каждого из подмножества «M». Затем мы используем этих победителей «M» в качестве нашей популяции и запускаем внешний генетический алгоритм над этой «высшей популяцией», чтобы найти глобальные минимумы.

Основная цель этой статьи состоит в том, чтобы преодолеть два основных ограничения генетического алгоритма, а именно:

  • Высокая временная сложность
  • Неспособность избежать локальных оптимумов

Предлагаемый алгоритм устраняет эти проблемы, реализуя следующее:

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

Теперь давайте сравним модифицированную версию с традиционным алгоритмом, сравнив их соответствующие псевдокоды:

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

Вы можете найти реализации Python для каждого из вышеупомянутых вариантов генетических алгоритмов в разделе Генетический алгоритм перезапуска базы, ​​Генетический алгоритм острова и Модифицированный генетический алгоритм. Если вы нашли эту статью полезной, подпишитесь на меня в Medium и GitHub и отметьте Репозиторий проектов.

Обязательно ознакомьтесь с другими частями этой серии статей —