Исследование модификаций турнирного отбора при решения неоднородной минимаксной задачи модифицированной моделью Голдберга

Исследование модификаций турнирного отбора при решения неоднородной минимаксной задачи модифицированной моделью

Голдберга

1 2 1 В.Г. Кобак , А.Г. Жуковский , А.П. Кузин

1 Донской государственный технический университет, Ростов-на-Дону 2Московского технического университета связи и информатики, Ростов-на-Дону

1

Аннотация: В данной работе впервые подробно рассматривается множество способов формирования нового поколения турнирным отбором при использовании модифицированной модели Голдберга с применением наиболее распространенного кроссовера с оригинальной мутацией. Был проведен вычислительный эксперимент, который выявил доминирующее преимущество использования стратегии «левая особь и мутации» при решении неоднородной минимаксной задачи. Было экспериментально установлено что повышение количества особей и повторов приводит к повышению времени получения решения неоднородной минимаксной задачи при использовании любой стратегии, но в тоже время и к повышению точности решения. Ключевые слова: одноточечный кроссовер, генетический алгоритм, модифицированная модель Голдберга, мутация, минимаксная задача, теория расписаний, элитная особь, особь, поколение.

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

Введение

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

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

При решении задач планирования возникает необходимость в методах, сочетающих в себе следующие противоречивые свойства: полиноминальная зависимость времени счета от размерности задачи; близкая к оптимальной точность решения (по крайне мере значительно лучшей, чем у списочных методов решения).

К такому классу методов относятся эволюционно-генетические алгоритмы (ЭГА), которые являются на сегодняшний момент наиболее гибкими и эффективными из всех известных приближенных алгоритмов. В данной работе исследуется одна из популярных моделей генетического алгоритма - модифицированная модель Голдберга. Математическая постановка задачи приведена в работе [1,2].

Описание метода

Модифицированную модель Голдберга можно описать в виде последовательности следующих шагов [3]:

Шаг 1. Формируется начальное поколение, состоящее из заданного числа особей [3,9,10].

Шаг 2. Турнирный отбор особей и применение операторов кроссовера и мутации с заданной вероятностью для создания нового поколения.

Шаг 3. Проверка условия конца работы алгоритма, которая обычно заключается в неизменности лучшего решения в течение заданного числа поколений. Если решение не меняется в течении определенного количества поколений, то переход на шаг 4, иначе возврат на шаг 2.

N

Шаг 4. Лучшая особь выбирается как найденное решение [3].

Графически функционирование модифицированной модели Годберга можно изобразить на рис. 1. Лучшая особь выбирается и переходит в следующее поколение и занимает место в следующем поколении ьтой особи. Процесс повторяется до тех пор, пока лучшая особь в поколении не повторится заданное количество раз. Такой критерий остановки генетического алгоритма использовался в работах [3,5,7].

Рис. 1 - Схема функционирования модифицированной модели Голдберга.

Различные подходы к формированию нового поколения при использовании модели Голдберга изображены на рис. 2-9.

Рис.2 - Левая особь и мутации

Рис.3 - Правая особь и мутации

И

Текущее поколение

Лучшая особь е поколении

Особи участвующие в кроссовере Особь 1

К

Особь 2

Резу льтат кроссовера Потомок 1

Мутация потомке Мутация 1

Лучшая

Отбор особь после

отбора

Рис.4 - Левая особь, правая особь и мутации

Рис.5 - Левая особь, правая особь, потомки и мутации

Рис.6 - Левая особь, лучшая в поколении и мутации

Рис.7 - Правая особь, лучшая в поколении и мутации

Рис.8 - Левая особь, правая особь, лучшая в поколении и мутации

N

Рис.9 - Левая особь, правая особь, лучшая в поколении, потомки и мутации

В данной работе [4,6] рассматривался наиболее распространенный одноточечный кроссовер изображенный на рис. 10.

Рис.10 - Простой одноточечный кроссвер

В работе [5,8] были исследованы различные модификации мутаций, из всего спектра которых была выбрана наиболее перспективная, а именно простая мутация, схематически изображенная на рисунке 11.

Рис.11 - Пример простой мутации.

Экспериментальное сравнение модификаций

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

Для проведения вычислительного эксперимента был использован компьютер под управлением Windows 10 Pro x64. В качестве аппаратного обеспечения использовался компьютер со следующей конфигурацией: четырех ядерный процессор Intel Core i7-7700k, 16 гигабайт оперативной памяти формата DDR4, жесткий диск SSD формата M2. Данная аппаратная система была выбрана связи с тем, что процессор поддерживает одновременно 8 потоков обработки данных и в связи с этим позволяет проводить параллельные вычисления для задач как малых, так и больших размерностей. Для проведения вычислительного эксперимента было написано программное средства на современном языке программирования C# в среде разработки Microsoft Visual Studio 2017.

Для каждой модификации метода получения поколения проводилось 50 экспериментов. Во время проведения этих экспериментов учитывались такие параметры как: минимальное полученное значение; среднее значение за 50 экспериментов; время получения решения. Результаты экспериментов приведены в таблице 1. Время, представленное в таблице, измеряется в секундах и представляет собой общую продолжительность 50 экспериментов.

Таблица №1

Результаты эксперимента

N * М Мод. тур. отб. 1 2 3 4 5 6 7 8

2*7 3 500*500

Мин 1047 1047 1048 1047 1072 1074 1073 1076

Сред. 1047,0 6 1048,58 1050,22 1049,64 1084,68 1084,76 1084,38 1084,26

Врем я 121 116 115 113 100 100 117 114

1000*100 0

Мин 1047 1047 1047 1047 1073 1072 1074 1071

Сред. 1047 1047,66 1048,5 1048,36 1082,52 1081,42 1082,68 1082,08

Врем я 375 397 435 428 400 402 498 529

3*7 3 500*500

Мин 652 654 654 657 697 696 694 703

Сред. 653,3 660,84 673,48 672,22 710,24 711,68 713,06 712,6

Врем я 159 145 124 125 110 109 132 134

1000*100 0

Мин 651 652 656 654 691 688 696 695

Сред. 652,22 655,8 663,98 665,08 710,06 709,68 711,12 708,52

Врем я 506 528 485 504 447 444 513 483

4*7 3 500*500

Мин 491 501 514 504 530 536 528 530

Сред. 494,5 511,8 526,36 524,26 543,78 545,32 545,18 545,42

Врем я 264 176 135 130 120 120 142 130

1000*100 0

Мин 489 496 504 502 526 527 532 533

Сред. 492,04 504 520,08 516,82 544,4 544,18 544,16 543,26

Врем я 745 601 497 622 479 475 561 527

5*7 3 500*500

Мин 397 407 420 417 432 430 432 436

Сред. 401,18 418,5 431,28 432,72 446,12 445,92 445,96 446,12

Врем я 315 209 140 132 125 125 146 136

1000*100 0

Мин 394 402 415 412 436 434 435 432

Сред. 397,9 412,92 428,52 425,1 444,68 444,1 444,26 444,14

Врем я 937 677 522 596 496 493 574 538

6*7 3 500*500

Мин 330 336 350 346 357 358 353 359

Сред. 333,02 348,66 358,38 357,24 367,9 369,34 369,94 369,36

Врем я 420 225 146 146 139 137 162 150

1000*100 0

Мин 330 335 347 343 349 357 357 353

Сред. 330,92 343,82 355,36 355,24 367,58 368,64 368,12 368,72

Врем я 1135 747 558 548 546 541 637 592

Соответствие между номером модификации и способом формирования нового поколения отражено в таблице№2.

Таблица №2

Соответствие между номером модификации и способом формирования

нового поколения

№ модификации Тип

1 Левая особь и мутации

2 Правая особь и мутации

3 Левая особь, правая особь и мутации

4 Левая особь, правая особь, кроссоверы и мутации

5 Левая особь, элита и мутации

6 Правая особь, элита и мутации

7 Левая особь, правая особь, элита и мутации

8 Левая особь, правая особь, элита, кроссоверы и мутации

Таким образом, обобщив результаты, приведенные в таблице 1, можно сделать несколько выводов:

1) Для стратегии «Левая особь и мутации» практически нет никакой альтернативы среди других стратегий по точности решения неоднородной минимаксной задачи.

2) Повышение количества особей и повторов приводит к повышению времени получения решения неоднородной минимаксной задачи при использовании любой стратегии.

3) При использовании стратегии «Левая особь и мутации» временные характеристики получения решения неоднородной минимаксной задачи немного большие, чем при использовании других.

4) Повышение количества особей и повторов приводит к повышению точности решения неоднородной минимаксной задачи при использовании любой стратегии.

Литература

1. Алексеев О. Т. Комплексное применение методов дискретной оптимизации - М.: Наука, 1987. с. 220.

2. Коффман Э.Г. (ред.) Теория расписаний и вычислительные машины. -M.: Наука, 1984. с. 158-177.

3. Титов Д.В., Кобак В.Г. Анализ подходов к улучшению результатов работы генетического алгоритма при решении однородной минимаксной задачи. // Проблемы информатики в образовании, управлении, экономике и технике: Сб. статей Всерос. научно-техн. конф.- Пенза: ПДЗ, 2008, с. 76-78.

4. Каширина, И.Л. Введение в эволюционное моделирование / И.Л. Каширина. - Воронеж: Изд-во ВГУ, 2007. с. 3-12.

5. Кобак В.Г., Поркшеян В.М. и Кузин А.П. Использование различных вариантов мутации при решении неоднородной минимаксной задачи модифицированной моделью Голдберга // Научно практический журнал «Аспирант», 2017, №10, с. 26-29.

6. Кобак В.Г., Жуковский А.Г. и Кузин А.П. Исследование применения одноточечного кроссовера при решении неоднородной минимаксной задачи //Инженерный вестник Дона, 2018, №1, URL: ivdon.ru/ru/magazine/archive/n1y2018/4714/.

7. Кобак В. Г. Методический подход к улучшению работы генетического алгоритма в однородной минимаксной задаче // Вестник Дон. гос. техн. университета. — Т. 10, 2010, № 4 (47), с. 474-479.

8. Кобак В. Г. Повышение эффективности генетического алгоритма на базе модели Голденберга за счет применения элиты // Известия вузов. Северо-кавказский регион. — Технические науки, 2016, № 1, с. 41-46.

9. Аль-Хулайди А.А., Чернышев Ю.О. Разработка параллельного алгоритма нахождения оптимального решения транспортной задачи на кластере // Инженерный вестник Дона, 2011, №2, URL: ivdon.ru/ru/magazine/archive/n2y2011/445/.

10. Нетёсов А.С. Эволюционно-генетический подход к решению задач оптимизации. Сравнительный анализ генетических алгоритмов с традиционными методами оптимизации // Инженерный вестник Дона, 2011, №3 URL: ivdon.ru/ru/magazine/archive/n3y2011/459/.

11. Holland J.H. Adaptation in natural and artificial systems. An introductory analysis with application to biology. Control, and artificial intelligence, 1994, pp. 89-120.

12. Muhlenbein H. Parallel genetic algorithm, population dynamics and combinatorial optimization, 1989, pp. 416-421.

References

1. Alekseyev O.T. Kompleksnoye primeneniye metodov diskretnoy optimizatsii. [Complex application of discrete optimization methods]. M.: Nauka. 1987. p. 220.

2. Koffman E.G. Teoriya raspisaniy i vychislitel'nyye mashiny. [Computer and job-shop scheduling theory]. M.: Nauka. 1984. pp. 158-177.

3. Titov D.V., Kobak V.G. Problemy informatiki v obrazovanii, upravlenii, ekonomike i tekhnike: Sb. statey Vseros. nauchno-tekhn. konf. Penza: PDZ. 2008. pp. 76-78.

4. Kashirina, I.L. Vvedeniye v evolyutsionnoye modelirovaniye. [Introduction to evolutionary modeling]. Voronezh: Izd-vo VGU. 2007. pp. 3-12.

5. Kobak V.G., Porksheyan V.M. i Kuzin A.P. Nauchno prakticheskiy zhurnal «Aspirant». 2017. №10. pp. 26-29.

6. Kobak V.G., Zhukovskiy A.G. i Kuzin A.P., Inzenernyj vestnik Dona (Rus), 2018. №1. URL: ivdon.ru/ru/magazine/archive/n1y2018/4714/.

7. Kobak V. G. Vestnik Don. gos. tekhn. universiteta. T. 10. 2010. № 4 (47). pp. 474-479.

8. Kobak V. G. Izvestiya vuzov. Severo-kavkazskiy region. Tekhnicheskiye nauki. 2016. № 1. pp. 41-46.

9. Al'-Khulaydi A.A., Chernyshev YU.O. Inzenernyj vestnik Dona (Rus). 2011. №2. URL: ivdon.ru/ru/magazine/archive/n2y2011/445/.

10. Netosov A.S., Inzenernyj vestnik Dona (Rus). 2011. №3. URL: ivdon.ru/ru/magazine/archive/n3y2011/459/.

11. Holland J.H. Adaptation in natural and artificial systems. An introductory analysis with application to biology. Control, and artificial intelligence, 1994. pp. 89-120.

12. Muhlenbein H. Parallel genetic algorithm, population dynamics and combinatorial optimization. 1989. pp. 416-421.