Исследование оптимальности применения параллелизации генетического алгоритма
Бесплатный доступ
В данной работе представлен результат исследований оптимизации генетического алгоритма решающего задачу минимизации функции Швефеля с применением параллелизации вычислений.
Генетический алгоритм, функция швефеля, параллелизация, параллелизация генетического алгоритма
Короткий адрес: https://sciup.org/140297392
IDR: 140297392
Текст научной статьи Исследование оптимальности применения параллелизации генетического алгоритма
В данной работе была предпринята попытка оптимизации работы генетического алгоритма (ГА) поиска минимума функции Швефеля при помощи применения параллелизации. Рассматриваемый в рамках исследования ГА, реализован на платформе .NET, с применением методов классов Task и Parallel [1] для реализации параллельных вычислений, и производит решение задачи минимизации многомерной функции Швефеля.
Основываясь на данных, полученных в ходе эксперимента, была сформирована таблица, отображающая время исполнения каждого метода реализованного ГА. Самыми затратными по времени, являются методы формирования популяции, метод выборки родителей и функция определения приспособленности потомков. Поэтому в первую очередь параллелизация применялась к обозначенным методам.
Таблица 1
Усредненные показатели времени вычисления методов ГА
|
Название метода |
Имя |
Последовательный ГА, мс |
Параллельный ГА, мс |
|
Популяция |
T1 |
36,336 |
22,292 |
|
Средняя ФП |
T2 |
0,742 |
0,455 |
|
Родители |
T3 |
147,532 |
90,510 |
|
Скрещивание |
T4 |
1,327 |
0,814 |
|
Мутация |
T5 |
0,926 |
0,568 |
|
Функция |
T6 |
2,442 |
1,498 |
|
Репродукция |
T7 |
0,567 |
0,348 |
|
Эпоха |
Tepoh |
190,447 |
116,839 |
Как итог время «эпохи» сократилось, что видно из результатов в столбце «Параллельный ГА» и теперь составляет 116,839 мс. Из отношения полученных данных при последовательном и параллельных вычислениях, можем найти коэффициент прироста производительности алгоритма: 190,447 / 116,839 = 1,63. Что является подтверждением оптимальности применения параллелизации в качестве решения проблемы быстродействия ГА.
