Control Systems and Computers, N3, 2019, Статья 1
https://doi.org/10.15407/csc.2019.03.003
Тимофієва Н.К. Про деякі підходи до оцінки оптимального розв’язку задач комбінаторної оптимізації. Control Systems and Computers. 2019. № 3. C. 3-14.
УДК 519.816
Тимофеева Надежда Константиновна, д.т.н., вед.н.с., Международный научно-учебный центр информационных технологий и систем НАН и МОН Украины, просп. Глушкова, 40, Киев 03187, Украина, E-mail: tymnad@gmail.com
О некоторых подходах к оценке оптимального решения задач комбинаторной оптимизации
Введение. В комбинаторной оптимизации входные данные, по которым оценивается результат решения задачи, представляют собой случайные величины, имеющие беспорядочную структуру. Для адекватной оценки используются различные методы анализа данных, имеющие место в математической статистике.
Постановка задачи. Для оценки результата решения задач комбинаторной оптимизации распознается структура входной информации, представляющая собой случайные величины с беспорядочной структурой, или на основе этой информации моделируется целевая функция. Для получения адекватной оценки важно выбрать такие подходы анализа данных, при которых можно получить оптимальный результат в реальном времени.
Предлагаемый подход. Для решения поставленной проблемы проведен анализ задач комбинаторной оптимизации и выделены такие, в которых оценка результата проводится с использованием корреляционных методов и в которых нахождение оптимального результата проводится путем распознавания структуры входной информации.
Задачи комбинаторной оптимизации разделяются на такие, в которых аргумент целевой функции (комбинаторная конфигурация) находится не с учетом структуры входной информации, а определяется на конкретной итерации случайно или по определенным правилам. В этом случае оценка результата проводится по выражению, в котором вычисляется суммарное произведение значений двух конечных последовательностей случайных величин, которыми задается входная информация. Соответственно устанавливается их зависимость от комбинаторной конфигурации . такой подход назван корреляционным, а метод решения задач — итерационным.
Во втором случае в процессе решения задачи путем анализа структуры входной информации последовательно строится комбинаторная конфигурация (аргумент целевой функции), т .е . путем распознавания структуры данных находится оптимальное (или глобальное) решение. Этот метод основывается на распознавании структуры входной информации. также существуют методы, в которых аргумент целевой функции строится в процессе распознавания входной информации, а полученный результат оценивается по целевой функции корреляцией заданных случайных величин и аргументом целевой функции . В задачах распознавания вводятся меры сходства, с помощью которых вычисляются величины (элементарные меры сходства), числовые значения которых образуют последовательность входных данных. По суммарному произведению значений этих последовательностей (интегральной степени сходства) оценивается результат.
Выводы. различные подходы анализа входной информации влияют на точность результата и на быстродействие алгоритма . Глобальное решение для задач больших размерностей достаточно часто находится полиномиальными методами, основанными на распознавании структуры входных данных, в сравнении с итерационными, в которых оценка результата проводится корреляционным подходом.
Загрузить полный текст в PDF (на украинском).
Ключевые слова: комбинаторная оптимизация, корреляционный подход оценки результата, распознавание структуры входной информации, комбинаторная конфигурация, целевая функция.
Поступила 27.02.19
