Случайный поиск в задаче о назначениях

В данной работе рассматривалось два основных подхода к решению задачи синтеза, описанной в работе [3]. Первый — изученный подход, представленный в третьей
главе работы, заключается в детерминированном поиске отображения �. Второй подход — менее изученный, рассмотренный в четвертой главе, использует случайный поиск
для нахождения оптимального отображения �. Первый и второй подходы могут иметь
множество вариаций. Причём если для первого различные вариации могут повлиять
только на скорость вычисления минимума, а не на его точность, то у второго могут
меняться обе эти характеристики. Вариация подхода решения задачи, рассмотренного
в 4 главе, осуществляется за счёт разного задания отображения �. В данной работе для
этого подхода было предложено три способа задания отображения �: метод 1, метод 2
и метод 3.
Из рассмотренных способов метод 1, описанный в главе 4, оказался более эффективным с точки зрения выбранного критерия — вероятности получения значения минимума с заданной точностью. Для этого способа были представлены результаты вычисления минимума для некоторых примеров целевых функций. Результаты показали, что
в случае, когда � ≈ �2 , стоит увеличивать количество общих шагов случайного поиска
по сравнению с граничными значениями � (когда � = 1 и � = �). Также количество
общих шагов стоит увеличивать и в случае, когда функции �� имеют сложный многоэкстремальный характер. При этом количество шагов на каждом этапе случайного поиска
выгоднее брать одинаковым для всех этапов и равным 1.
В целом подход из 4 главы уступает в точности подходу, рассмотренному в 3 главе
работы. Это происходит из-за того, что он ищет отображение � с некоторой погрешностью в то время, как подход 3 главы всегда находит точное �, которое минимизирует
целевую функцию в заданной точке. Преимущество подходов из главы 4 заключается в
более универсальном их применении и более быстрой работе. Такие алгоритмы можно
использовать в том случае, когда для поставленной задачи не применимы методы 3
главы или точность получаемого результата менее важна, чем скорость его получения.

Купить