2022, випуск 2, c. 31-37
Одержано 01.09.2022; Виправлено 13.09.2022; Прийнято 29.09.2022
Надруковано 30.09.2022; Вперше Online 05.10.2022
https://doi.org/10.34229/2707-451X.22.2.3
Попередня | ПОВНИЙ ТЕКСТ | Наступна
УДК 519.711: 519.711.3: 519.81
Про вибір числа процесорів для паралельного багатопопуляційного генетичного алгоритму
І.О. Лук'янов, Ф.А. Литвиненко
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її., Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. У роботі розглянуто деякі особливості паралельної реалізації багатопопуляційного генетичного алгоритму, а також підходи до його оптимізації. Наведено результати експериментів з використанням різного числа процесорів і різними способами генерації початкових популяцій з метою оптимізації алгоритму за декількома критеріями (оцінки використання обчислювальних і часових ресурсів). На прикладі конкретної тестової задачі наведено оцінку вибору оптимальної кількості процесорів для отримання необхідного результату.
Мета роботи. Проведення експериментів із заданою тестовою задачею з різним числом процесорів та альтернативними способами генерації початкової популяції з метою оцінки ефективності алгоритму.
Результати. Для даної тестової задачі для отримання результату в 90 – 94 % від оптимуму найбільш ефективним за критерієм обчислювальних ресурсів є використання 4 процесорів з алгоритмом рівномірного сканування простору значень факторів. Для досягнення результату, що перевищує 94 % і оптимізації К1 (обчислювальні ресурси), найкращий результат показали 8 процесорів і алгоритм рівномірного сканування простору значень факторів. Якщо враховувати також і критерій тимчасових ресурсів К2, то для досягнення 90–98 % оптимуму необхідно використовувати 8 процесорів, для 99–100 % 12 або 16 процесів, залежно від С1 і С2 (вартість обчислювальних ресурсів і часу) .
Висновки. Проведені експерименти показують, що алгоритм рівномірного сканування простору значень факторів є ефективнішим за випадковий спосіб генерації початкової популяції. Також експерименти показали, що для досягнення максимальної ефективності ПБГА кількість процесорів необхідно обирати в залежності від точності необхідного результату.
Ключові слова: паралельний генетичний алгоритм, генерація початкової популяції, вибір числа процесорів (популяцій), оптимізація алгоритму.
Цитувати так: Лук'янов І.О., Литвиненко Ф.А. Про вибір числа процесорів для паралельного багатопопуляційного генетичного алгоритму. Cybernetics and Computer Technologies. 2022. 2. С. 31–37. https://doi.org/10.34229/2707-451X.22.2.3
Список літератури
1. Литвиненко Ф.А., Лук’янов І.О., Криковлюк О.А. Особливості реалізації паралельної версії багатопопуляційного генетичного алгоритму. Комп'ютерна математика. 2018. № 2. С. 21–29. http://dspace.nbuv.gov.ua/handle/123456789/161882
2. Лук’янов І.О., Литвиненко Ф.А., Криковлюк О.А. Про підвищення ефективності паралельної версії багатопопуляційного генетичного алгоритму. Теорія оптимальних рішень. 2019. № 18. С. 116–122. http://dspace.nbuv.gov.ua/handle/123456789/161683
3. Литвиненко Ф.А., Лук’янов И.О., Криковлюк О.А. Використання різноманітності початкової популяції у багатопопуляційному генетичному алгоритмі. Комп'ютерна математика. 2019. № 1. С. 116–123. http://dspace.nbuv.gov.ua/handle/123456789/161941
4. Horne G.E., Meyer T.E. Data Farming: Discovering Surprise. Proc. of the Winter Simulation Conference. 2005. P. 1082–1087.
5. Horne G.E., Schwierz K.-P. Data Farming around the world overview. Proc. of the Winter Simulation Conference. 2008. P. 1442–1447.
6. Пепеляєв В.А., Чорний Ю.М. Про можливості застосування генетичних алгоритмів в оптимізаційно-імітаційних експериментах. Теорія оптимальних рішень. 2019. № 18. С. 69–77. http://dspace.nbuv.gov.ua/handle/123456789/161681
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна