РОЗРОБКА ГЕНЕТИЧНОГО АЛГОРИТМУ ДЛЯ ЗНАХОДЖЕННЯ НАБЛИЖЕНИХ РОЗВ’ЯЗКІВ ЗАДАЧІ КОНТАКТНОГО ЧИСЛА

Анотація

Задача контактного числа є однією з актуальних проблем комбінаторної оптимізації та дискретної геометрії, що має важливе теоретично-прикладне значення. У статті визначено актуальність цієї задачі та обґрунтовано необхідність застосування наближених обчислювальних методів для її дослідження в евклідових просторах довільної вимірності. Крім того, геометричне формулювання задачі тісно пов’язане з аналізом взаємного розташування векторів і кутових обмежень між ними, а тому у статті проаналізовано подання задачі контактного числа через α-допустимі системи векторів та встановлено зв’язок між цими системами і конфігураціями дотичних куль.

Обмеженість класичних (традиційних) аналітичних методів зумовлює пошук альтернативних підходів щодо розв’язання обумовленої  задачі. У статті доведено можливість та ефективність використання ε-близьких систем векторів із цілочисловими координатами для знаходження наближених розв’язків. Сучасні поширені еволюційні методи дозволяють ефективно досліджувати великі простори допустимих конфігурацій. У статті запропоновано генетичний алгоритм, у якому критерієм оптимальності є мінімізація максимального косинуса кута між векторами системи. У даному випадку, чималого значення набуває обчислювальна реалізація у практичному застосуванні запропонованого підходу. До того ж, у статті досліджено програмну реалізацію алгоритму та основні механізми еволюції популяції, зокрема репродукцію, мутацію, вимирання та еволюційні стрибки.

Причому, ефективність методу підтверджується результатами чисельних експериментів. У даній статті визначено результати обчислювальних експериментів для просторів малої та середньої вимірності та показано можливість узагальнення підходу для широкого класу комбінаторних задач оптимізації. Видається, що подальший розвиток тематики пов’язаний з підвищенням продуктивності та аналітичних можливостей алгоритму. Через це, у статті окреслено перспективи подальших досліджень, зокрема використання паралельних обчислень, аналізу структури популяцій та засобів візуалізації результатів.