Задача формування зон відповідальності на множині об’єктів площини за критерієм мінімізації різниці сумарних ваг

Автор(и)

  • O. Жданова КПІ ім. Ігоря Сікорського, Україна
  • О. Папка КПІ ім. Ігоря Сікорського, Україна
  • Л. Рибачук КПІ ім. Ігоря Сікорського, Україна
  • О. Савчук КПІ ім. Ігоря Сікорського, Україна
  • Г. Соболевський КПІ ім. Ігоря Сікорського, Україна

DOI:

https://doi.org/10.20535/1560-8956.44.2024.302419

Ключові слова:

задача розбиття множини на підмножини, зони відповідальності, евристичний алгоритм, генетичний алгоритм

Анотація

Робота присвячена дослідженню оптимізаційної задачі, у якій необхідно розбити множину об’єктів, для яких відомі вага та координати розміщення, на дві підмножини (зони), кожна з яких закріплена за заданими об’єктами–базами (з відомими координатами). Необхідно побудувати розмежувальну лінію, що ділить ділянку на дві зони так, щоб одна зона відповідала одній базі, друга – іншій, і при цьому різниця між зваженими кількостями об’єктів, що попали в різні зони, була мінімальною. Досліджувана задача відноситься до класу задача розбиття множини на підмножини, що має широке застосування на практиці. Побудована математична модель задачі, представлені достатні умови оптимальності. Розроблені чотири алгоритми розв’язання задачі: два евристичних і два генетичних. Перший евристичний алгоритм будує деяку множину розмежувальних прямих, які проходять через середину відрізку, що з’єднує бази. Другий евристичний алгоритм є рекурсивною процедурою виклику першого евристичного алгоритму.
Розроблено також два генетичних алгоритми, що відрізняються умовами завершення. Проведена серія експериментів, метою яких був порівняльний аналіз розроблених алгоритмів за часом роботи та точністю.

Бібл. 14, іл. 6

Посилання

Papadimitriou C.H. Computational Complexity. – Massachusetts: AddisonWesley, 1994. – 523 p.

Parque V. Tackling the Subset Sum Problem with Fixed Size using an Integer Representation Scheme // IEEE Congress on Evolutionary Computation (CEC), Poland, 2021, pp. 1447-1453.

Müller T. Solving Set Partitioning Problems with Constraint Programming // Computer Science, 2009, pp.313-332.

Ozerov I. Combinatorial Algorithms for Subset Sum Problems. – RuhrUniversität Bochum, Diss., 2016. – 128 p.

Aarts E., Lenstra J.K. Local search in combinatorial optimization. – Princeton University Press, 2003. – 528 p.

Madugula M.K., S.K. Majhi, Panda N. An Efficient Arithmetic Optimization Algorithm for Solving Subset-sum Problem // International Conference on Connected Systems & Intelligence (CSI), 31 August 2022 - 02 September 2022, India. – IEEE. DOI: 10.1109/CSI54720.2022.9923996

Wang R.L. A genetic algorithm for subset sum problem // Neurocomputing, vol. 57, 2004, pp. 463-468.

Ghosh D., Chakravarti N. A competitive local search heuristic for the subset sum problem // Computers & Operations Research, vol. 26, Issue 3, 1999, pp. 271-279.

Curtis V.V., Sanches C.A.A. An improved balanced algorithm for the subset-sum problem // European Journal of Operational Research, vol. 275, no. 2, 2019, pp. 460-466.

Harsha K., Jeyakumar S.G. Comparison of Dynamic Programming and Genetic Algorithm Approaches for Solving Subset Sum Problems // Computational Vision and BioInspired Computing, 2020, pp. 472-479.

Gao X., Yu W. An algorithm for subset sum problem on molecular computation// 7th IEEE International Conference on Software Engineering and Service Science (ICSESS), 2016, pp. 1072-1076.

Singh S., Srivastava S. Review of Clustering Techniques in Control System: Review of Clustering Techniques in Control System // Procedia Computer Science, vol. 173, 2020, pp. 272-280.

Дубови В.П., Юри І.І. Вища математика: навч. посібн. – К.: “А.С.К.”, 2006. – 648 с.

Гуляниць ий Л.Ф. Мулеса О.Ю. Прикладні методи комбінаторної оптимізації: навч. посібн. – Київ: ВПЦ “Київський університет”, 2016. – 142 с.

##submission.downloads##

Опубліковано

2024-04-23

Номер

Розділ

Статті