Метод визначення функції оглядовості у задачі оптимального розподілу глядацьких місць

Abstract

У тезах розглянуто задачу оптимального розподілу глядацьких місць за критерієм оглядовості як складну комбінаторну задачу оптимізації. Обґрунтовано доцільність використання генетичного алгоритму для пошуку ефективних розподілів у великому просторі можливих рішень. Запропоновано два методи визначення функції оглядовості — прямий та обернений, для оцінювання пристосованості хромосом у процесі еволюційної оптимізації. Для кожного методу наведено математичні співвідношення та описано алгоритм їх реалізації. Проведено порівняльний аналіз методів за критеріями точності, обчислювальної складності та потреби в додатковій інформації. За результатами аналізу обрано обернений метод як більш доцільний для застосування у генетичних алгоритмах при задачах великої розмірності. Отримані результати можуть бути використані при розробленні інтелектуальних систем автоматизованого планування розподілу місць у залах різного призначення.

The theses consider the problem of optimal spectator seat allocation according to the visibility criterion as a complex combinatorial optimization task. The feasibility of applying a genetic algorithm to search for efficient allocations within a large solution space is substantiated. Two methods for determining the visibility function — direct and inverse — are proposed for evaluating chromosome fitness in the process of evolutionary optimization. Mathematical relationships for each method are presented, and the algorithms for their implementation are described. A comparative analysis of the methods is carried out in terms of accuracy, computational complexity, and the need for additional information. Based on the analysis, the inverse method is selected as more appropriate for application in genetic algorithms when solving large-scale problems. The obtained results can be used in the development of intelligent automated seat allocation systems for halls of various purposes.