» ГЛАВНАЯ > К содержанию номера
 » Все публикации автора

Журнал научных публикаций
«Наука через призму времени»

Апрель, 2018 / Международный научный журнал
«Наука через призму времени» №4 (13) 2018

Автор: Киреева Екатерина Валентиновна, Магистрант
Рубрика: Технические науки
Название статьи: Сравнительный анализ моделей генетического алгоритма

Статья просмотрена: 1379 раз
Дата публикации: 09.04.2018

УДК 519

Сравнительный анализ моделей генетического алгоритма

Екатерина Валентиновна Киреева

магистр 2 курса обучения

Екатерина Викторовна Борисова

кандидат технических наук, доцент

Донской Государственный Технический университет, г.Ростов-на-Дону

 

Аннотация. Различные виды генетических алгоритмов получили широкое распространение, ведь они используются для решения задач оптимизации, моделирования путем случайного подбора и комбинирования. В статье проведен сравнительный анализ наиболее популярных моделей генетического алгоритма: модель Холланда, модель Голберга, модель Уитли, Гибридная и Островная модели. Генетические алгоритмы получили развитие относительно недавно и являются малоизученной областью эволюционных вычислений.

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

 

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

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

Часто генетические алгоритмы используются для интерактивного управления процессом, например, на заводе или для балансирования нагрузки на многопроцессорном компьютере [1, 2].

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

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

Стандартный генетический алгоритм был впервые подробно описан и предложен в работе ученого Джонга. В 1975 году Джона Холланда и его коллеги представили первую схему работы генетического алгоритма.

Предпосылками стали работы Дарвина и исследования других ученых: А. Дж. Оуэнса, Л. Дж. Фогеля по эволюции простых автоматов в 1966 году. Идеи Холланда были доработаны его последователями: Кеннет Де Йонг и Дэвид Голдберг.

На основе их работ был создан классический генетический алгоритм и появилось описание всех операторов. Зная об истории генетических алгоритмов, необходимо понять, что отличает их от классических методов оптимизации [3].

Описание генетического алгоритма заключается в том, что они представляют собой совокупности особей (популяции), с которыми происходят различные операции. Особи – это наборы решений задачи. В отличие от других алгоритмов оптимизации в рассматриваемых алгоритмах перебираются совокупности различных решений [4-5]. На рисунке 1 представлена схема работы простейшего генетического алгоритма.

C:\Users\Екатерина\YandexDisk\Скриншоты\2016-05-18_23-55-03.png

Рисунок 1. Схема работы простейшего алгоритма

Из схемы, представленной на рисунке 1 видно, что алгоритм состоит из повторяющихся стадий: создание популяции на первом шаге, а в дальнейшем генерация промежуточных популяций, отбор лучших особей, скрещивание между особями популяции, мутация [1, 6].

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

Таблица 1. Сравнение моделей генетического алгоритма

Название

Особенности

Отбор

Кроссовер

Мутация

Модель Холланда

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

Пропорциональный

Одноточечный

Одноточечная

Модель Голберга

 

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

Турнирный

Одноточечный

Одноточечная

Модель Уитли

 

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

Специфичный – замена

Ограничения отсутствуют

Ограничения отсутствуют

Гибридная модель

 

Гибридная модель совмещает в себе генетический алгоритм и классические методы. Она объединяет в себе преимущества каждого из алгоритмов. Сначала используется генетический алгоритм. Потом берется одна лучшая особь и применяется «классический» метод оптимизации.

Ограничения отсутствуют

Ограничения отсутствуют

Ограничения отсутствуют

Островная модель

Суть данной модели состоит в разбиение популяции на некоторое количество подпопуляций. Используются Генетический оператор миграции (обмен различными особями между островами).

Ограничения отсутствуют

Ограничения отсутствуют

Ограничения отсутствуют

Стоит отметить, что генетические алгоритмы стремительно развиваются, используются не сами модели, а их модификации. Наиболее популярными становятся параллельные генетические алгоритмы.

Был проведен теоретический обзор и сравнительный анализ следующих моделей: модели Холланда, модели Голдберга, модели Уитли, Гибридной модели и Островной модели. 

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

 



Список литературы:

  1. Рутковская, Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская, М. Пилиньский, Л. Рутковская. – М.: Горячая Линия-Телеком, 2006. – 452 с.
  2. Каширина, И. Л. Введение в эволюционное программирование: учебное пособие / И. Л. Каширина – Воронеж: ВГУ, 2007. – 40 с.
  3. Кобак, В. Г. Основные алгоритмы решения однородной минимаксной задачи в различных системах обработки информации: монография / В. Г. Кобак, Д. В. Титов, О. А. Золотых, Д. В. Плешаков; под научной ред. В. Н. Землянухина – Ростов н/Д: Издательский центр ДГТУ, 2013. – 185 с.
  4. Емельянов, В. В. Теория и практика эволюционного моделирования / В. В. Емельянов, В. М. Курейчик, В. В. Курейчик; под общ. ред. – В.М. Курейчика – М: Физматлит, 2006. – 431 с.
  5. Головкин Б. А. Расчет характеристик и планирование параллельных вычислительных процессов / Б.А. Головкин. - М.: Радио и Связь, 2002. - 272 с.
  6. Батищев, Д.И. Применение генетических алгоритмов к решению задач дискретной оптимизации: учебное пособие / Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин; под общ. ред. Д.И. Батищева – Нижний Новгород, 2007. – 85 с.
  7. Еремеев, А.В. Генетические алгоритмы и оптимизация: учебное пособие / А.В. Еремеев – Астрахань: Издательский дом «Астраханский университет», 2007. – 87 с.

 

Комментарии:

Фамилия Имя Отчество:
Комментарий: