НАУКОЕМКИЕ ТЕХНОЛОГИИ
В КОСМИЧЕСКИХ ИССЛЕДОВАНИЯХ ЗЕМЛИ

Маршрутизация на графе, теоретико-числовые целевые функции и генетический алгоритм

Аллилуева Н.В., Руденко Э.М., Семикина Е.В.

Рассматривается математический подход к расчету маршрутов беспилотных летательных аппаратов на Эйлеровом графе реперных точек на местности. Проводится сравнение методов построения целевой функции графа на основе алгебраического и теоретико-числового подхода.

Целевая функция графа в виде многочлена от нескольких переменных минимальное нулевое значение достигает на наборах номеров вершин графа, которые являются замкнутыми маршрутами на графе.  Алгебраический подход приводит к целевой функции в виде суммы нескольких многочленов. Первое слагаемое учитывает информацию о постоянстве минимальной длины замкнутого маршрута Эйлерова графа, проходящего по всем ребрам один раз. Другие слагаемые отражают комбинаторную повторяемость номеров вершин Эйлерова графа в оптимальных замкнутых маршрутах минимальной длины, равной половине их кратности. Анализ алгебраической целевой функций в виде суммы многочленов показывает на примере конкретного графа возможность нахождения замкнутых маршрутов на различных Эйлеровых моделях данного графа. Теоретико-числовой подход приводит к построению целевой функции в виде одного многочлена. Теоретической основой построения целевой функции при данном подходе являются теоремы об однозначности представления целых чисел в виде суммы в s-ической системе счисления и однозначности представления рационального числа в виде несократимого отношения произведений степеней различных простых чисел. Математическая модель расчета маршрутов на графе основана на минимизации генетическим алгоритмом построенных s-ических и р-мультипликативных целевых функций графа. Исследована эффективность вычисления маршрутов с помощью построенных целевых функций графа. Минимальные временные затраты достигаются при вычислении маршрутов с помощью целой s-ической целевой функции. Теоретико-числовой подход дает возможность построения целевых функций для сверхбольших графов и указывает на связь с распределением простых чисел и с теорией р-адических чисел. Все построенные теоретико-числовые целевые функции обладают особенностью достижения минимума равного нулю только на оптимальных замкнутых маршрутах графа минимальной длины. Показана взаимосвязь прикладной задачи маршрутизации беспилотных летательных аппаратов на местности с математической задачей оптимизации на графах средствами теории чисел и генетического алгоритма.

Редакционная коллегия

Бобровский В.И.
(д.т.н., доцент, начальник отдела ОАО "ИНТЕЛТЕХ")

Борисов В.В.
(д.т.н., профессор, Действительный член Академии военных наук РФ, профессор кафедры вычислительной техники МЭИ)

Будко П.А.
(д.т.н., профессор, профессор кафедры технического
обеспечения связи и автоматизации ВАС)

Будников С.А.
(д.т.н., доцент, действительный член Академии информатизации
образования, начальник кафедры автоматизированных
систем управления ВУНЦ ВВС "ВВА")

Верхова Г.В.
(д.т.н., профессор, заведующая кафедрой автоматизации
предприятий связи СПб ГУТ им. профессора М.А.Бонч-Бруевича)

Гончаревский В.С.
(д.т.н., профессор, заслуженный деятель науки и техники
РФ, профессор кафедры технологий и средств технического
обеспечения и эксплуатации автоматизированных систем
управления ВКА имени А.Ф.Можайского)

Комашинский В.И.
(д.т.н., профессор, профессор кафедры обработки и передачи
дискретных сообщений СПб ГУТ им. профессора
М.А.Бонч-Бруевича)

Кирпанев А.В.
(д.т.н., доцент, начальник отдела ОАО «НПП «РАДАР ММС»)

Курносов В.И.
(д.т.н., профессор, академик Арктической академии наук,
академик Международной академии информатизации,
академик Международной академии обороны, безопасности
и правопорядка, член-корреспондент РАЕН, главный научный
сотрудник ОАО "НИИ "Рубин")

Мануйлов Ю.С.
(д.т.н., профессор, профессор кафедры автоматизированных
систем управления космических комплексов ВКА имени
А.Ф.Можайского)

Морозов А.В.
(д.т.н., профессор, действительный член Академии военных наук РФ, начальник кафедры автоматизированных систем боевого управления ВА ВПВО ВС РФ)

Мошак Н.Н.
(д.т.н., доцент, начальник отдела ОАО "ИНТЕЛТЕХ")

Пророк В.Я.
(д.т.н., профессор, профессор кафедры автоматизированных
систем управления ВКА имени А.Ф.Можайского)

Семенов С.С.
(д.т.н., доцент, профессор кафедры технического
обеспечения связи и автоматизации ВАС)

Синицын Е.А.
(д.т.н., профессор, начальник НИО ОАО "ВНИИРА")

Шатраков Ю.Г.
(д.т.н., профессор, заслуженный деятель науки РФ, ученый
секретарь ОАО "ВНИИРА")