2023, випуск 2, c. 32-45
Одержано 17.07.2023; Виправлено 24.07.2023; Прийнято 25.07.2023
Надруковано 28.07.2023; Вперше Online 18.08.2023
https://doi.org/10.34229/2707-451X.23.2.4
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Про покращення евристичного алгоритму упаковки кругів в круг мінімального радіусу
Б.О. Задорожний 1 *,
О.В. Міца 1 
, П.І. Стецюк 2
1 Ужгородський національний університет, Ужгород
2 Інститут кібернетики імені В.М. Глушкова НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Стаття присвячена дослідженню евристичного алгоритму для розв’язання конкурсної задачі «Щільна упаковка кругів в круг мінімального радіусу» та розробці його покращеного варіанту за допомогою r-алгоритму Шора з дихотомією кроку. Евристичний алгоритм розроблений студентом третього курсу Ужгородського національного університету Богданом Задорожним. Реалізована на його основі програма посіла друге місце у змаганні та використовувала менше часу за максимальний час, який за умовою змагання відводився на одноразовий запуск програми для 50 конкурсних задач. У статті описано результати дослідження як за допомогою r-алгоритму Шора можна покращити ефективність роботи евристичного алгоритму.
Алгоритм для покращення евристичного розв’язку реалізовано за наступною схемою. Стартуємо з найкращого розміщення кругів, знайденого евристичним алгоритмом. Далі виконуємо наступні чотири етапи алгоритму. Етап 1. Встановимо доволі велике значення початкового кроку (визначаємо його в залежності від вхідних даних або ж просто обираємо як великий крок). Етап 2. Запускаємо r-алгоритм зі стартової точки і знаходимо локальний мінімум відповідної задачі нелінійного програмування. Етап 3. Якщо знайдений локальний мінімум: гарантує менший радіус зовнішнього круга, то точка локального мінімуму стає стартовою точкою; якщо ж знайдений локальний мінімум не гарантує меншого радіуса зовнішнього круга, то величину кроку h зменшуємо вдвічі. Етап 4. Якщо величина кроку більша за задане значення, то переходимо до Етапу 2. Інакше закінчуємо роботу алгоритму з покращення розв’язку.
Для програмної реалізації обох алгоритмів використовувались мова програмування Python 3.9.5 та бібліотека NumPy 1.24.2. Для 50 конкурсних тестів та різної кількості ітерацій евристичного алгоритму (10, 20, 30, 40 та 50 ітерацій) проведено аналіз отриманих результатів за трьома параметрами: кількість отриманих балів, час виконання програми та кількість обмінів кругів на одній ітерації евристичного алгоритму. Для більшої частини конкурсних тестів алгоритм з уточненням дозволяє отримати кращі результати в балах, так у більшості випадків покращення становлять до 2 балів, а у деяких випадках – від 3 до 6 балів. Найбільші покращення (6 балів) помітні у тестах, де круги мають однакові або близькі радіуси. Тут евристичний алгоритм показує себе не так ефективно, тому для таких тестів завдяки алгоритму з уточненням можна значно покращити результати конкурсних задач в балах.
Ключові слова: пакування кругів, евристика, r-алгоритм, Python 3.9.5, NumPy 1.24.2.
Цитувати так: Задорожний Б.О., Міца О.В., Стецюк П.І. Про покращення евристичного алгоритму упаковки кругів в круг мінімального радіусу. Cybernetics and Computer Technologies. 2023. 2. С. 32–45. https://doi.org/10.34229/2707-451X.23.2.4
Список літератури
1. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. 200 с.
2. Shor N.Z. Non-Differentiable Optimization and Polуnomial Problems. Kluwer Academic Publishers, Boston, Dordrecht, London. 1998. 412 p.
3. Стецюк П.И. Теория и программные реализации r-алгоритмов Шора. Кибернетика и системный анализ. 2017. № 5. С. 43–57.
4. Stetsyuk P., Romanova T., Scheithauer G. On the global minimum in a balanced circular packing problem. Optimization Letters. 2016. No. 10. P. 1347–1360.
5. Стецюк П.І., Пилиповський О.В., Хом’як О.М. GNU Octave та Python реалізації r-алгоритму Шора з адаптивним регулюванням кроку. Cybernetics and Computer Technologies. 2022. 3. С. 98–112.
6. Python 3.9.5:https://www.python.org/downloads/release/python-395 (звернення: 09.08.2023)
7. NumPy 1.24.2 Release Notes https://numpy.org/devdocs/release/1.24.2-notes.html (звернення: 09.08.2023)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна