Статья

Название статьи ПАРАЛЛЕЛЬНЫЙ ПОПУЛЯЦИОННЫЙ АЛГОРИТМ
Автор Д. Ю. Запорожец, Д. В. Заруба
Рубрика РАЗДЕЛ III. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ И БИОИНСПИРИРОВАННЫЕ АЛГОРИТМЫ
Месяц, год 04, 2018
Индекс УДК 681.3.06
DOI
Аннотация Предложена архитектура параллельного поиска. Выделены три уровня распараллеливания: микроуровень – распараллеливание задач на уровне выполнения операторов генерации новых альтернативных решений; макроуровень – распараллеливание поиска на уровне генераций; метауровень – распараллеливание процесса поиска на уровне изолированного множества альтернативных решений. В качестве примера, в данной работе предложена реализация параллельного генетического алгоритма с распараллеливанием на микроуровне. Предложена обобщенная архитектура и описаны основные шаги нового параллельного генетического алгоритма с распараллеливанием на микроуровне. Основной идеей данного подхода является инициализация N потоков, в каждом из которых выполняется оператор кроссинговера и, с заданной долей вероятности, операторы мутации и инверсии. Для всех новых решений производится расчет целевой функции в том потоке, в котором данное решение было получено. Алгоритм ожидает окончания всех потоков. Далее производится объединение всех новых сгенерированных решений в одну популяцию и выполняется оператор селекции. Процесс продолжается итерационно по достижению заданного числа итераций. Для подтверждения эффективности предложенного подхода была разработана программная реализация параллельного генетического алгоритма. В качестве прикладной задачи была выбрана одна из классических оптимизационных задач – нахождение Гамильтонова цикла в графе. Целью проведения экспериментальных исследований является скорость работы реализованного генетического алгоритма, а также сравнение его с классическим «последовательным» генетическим алгоритмом. Исследования проводились на двух различных платформах с процессорами: Intel I7 – 4 ядра, 2.7 ГГц и AMD 6000 – 2 ядра 2.5 ГГц. Проведены экспериментальные исследования, которое показали значительный прирост в скорости работы алгоритма при количестве вершин в графе более 250. Скорость работы алгоритма выросла на 100 – 200 % по сравнению с классической реализацией в зависимости от используемого процессора. Таким образом экспериментально было доказано, что при использовании одного и того аппаратного обеспечения, предлагаемый параллельный подход позволяет сократить время работы алгоритма оптимизации в несколько раз по сравнению с его классической последовательной реализацией.

Скачать в PDF

Ключевые слова Генетические алгоритмы; параллельный поиск; популяционные алгоритмы; задача коммивояжера; гамильтонов цикл.
Библиографический список 1. Курейчик В.М., Писаренко В.И., Кравченко Ю.А. Технология многоаспектного аналитического исследования как метод машинного обучения // Открытое образование.
– 2008. – № 2. – С. 11-17.
2. Kurejchik V.V., Kurejchik V.M. On genetic-based control // Автоматика и телемеханика.
– 2001. – № 10. – С. 174-187.
3. Курейчик В.М., Курейчик В.В., Родзин С.И., Гладков Л.А. Основы теории эволюционных вычислений. – Ростов-на-Дону: ЮФУ, 2010. – 222 c.
4. Курейчик В.В., Курейчик В.М., Зинченко Л.А. и др. Бионические информационные системы и их практические применения. – М.: Физматлит, 2011. – 288 c.
5. Родзин С.И., Курейчик В.В. Состояние, проблемы и перспективы развития биоэвристик // Программные системы и вычислительные методы. – 2016. – № 2. – С. 158-172.
6. Родзин С.И., Курейчик В.В. Теоретические вопросы и современные проблемы развития когнитивных биоинспирированных алгоритмов оптимизации // Кибернетика и программирование. – 2017. – № 3. – С. 51-79.
7. Zaporozhets D., Zaruba D. Bacterial foraging optimization for VLSI fragments placement // Advances in Intelligent Systems and Computing. – 2018. – 679. – P. 341-348.
8. Kureichik V.M., Lebedev B.K., Lebedev O.B. Channel routing based on ant colony adaptive behavior model // Journal of Computer and Systems Sciences International. – 2015. – Vol. 54 (2). – P. 278-293.
9. Kureichik V.V., Kravchenko Y.A. Bioinspired algorithm applied to solve the travelling salesman problem // World Applied Sciences Journal. – 2013. – Vol. 22, No. 12. – P. 1789-1797.
10. Курейчик В.В., Заруба Д.В., Запорожец Д.Ю. Алгоритм параметрической оптимизации на основе модели поведения роя светлячков // Известия ЮФУ. Технические науки.
– 2015. – № 6 (167). – С. 6-15.
11. Курейчик В.В., Заруба Д.В., Запорожец Д.Ю. Иерархический подход при размещении компонентов СБИС // Известия ЮФУ. Технические науки. – 2014. – № 7 (156). – С. 75-84.
12. Кулиев Э.В., Курейчик В.В., Курситыс И.О. Принятие решений в задаче размещения компонентов СБИС на основе модели поведения стаи волков // Международная конференция по мягким вычислениям и измерениям. – 2018. – Т. 1. – С. 712-715.
13. Кулиев Э.В., Кравченко Ю.А., Логинов О.А., Запорожец Д.Ю. Метод интеллектуального принятия эффективных решений на основе биоинспирированного подхода // Известия Кабардино-Балкарского научного центра РАН. – 2017. – № 6-2 (80). – С. 162-169.
14. Knysh D.S., Kureichik V.M. Genetic algorithm for routing switching units // Russian Microelectronics. – 2011. – Vol. 40 (7). – P. 486-490.
15. Курейчик В.М., Курейчик В.В., Родзин С.И. Модели параллелизма эволюционных вычислений // Вестник Ростовского государственного университета путей сообщения.
– 2011. – № 3 (43). – С. 93-97.
16. Knysh D.S., Kureichik V.M. Parallel genetic algorithms: A survey and problem state of the art // Journal of Computer and Systems Sciences International. – 2010. – Vol. 49 (4). – P. 579-589.
17. Kacprzyk J., Kureichik V.M., Malioukov S.P., Kureichik V.V., Malioukov A.S. Experimental investigation of algorithms developed // Studies in Computational Intelligence. – 2009.
– Vol. 212. – P. 211-223+227-236.
18. Gladkov L.A., Kureichik V.V., Kravchenko Y.A. Evolutionary algorithm for extremal subsets comprehension in graphs // World Applied Sciences Journal. – 2013. – Vol. 27, No. 9.
– P. 1212-1217.
19. Polkovnikova N.A., Kureichik V.M. Hybrid Expert System Development Using Computer-Aided Software Engineering Tools // Communications in Computer and Information Science. – 466 CCIS. – 2014. – P. 433-445.
20. Gudilov V., Kureichik V. Evolutional synthesis with incomplete information // Life Science Journal, 11 (10 SPEC. ISSUE), art. no. 68. – 2014. – P. 359-363.

Comments are closed.