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

Ширинкина Дарья Андреевна

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

Ширинкина Дарья Андреевна. Случайный поиск в задаче о назначениях. Научный руководитель: Сушков Юрий Акимович. Направление математика, механика, профиль вычислительная стохастика и статистические модели. В работе рассматривается два подхода к решению задач синтеза систем. Один из них основан на преобразовании начальной задачи к такому представлению, к которому применим алгоритм случайного поиска. Для этого подхода предложено три таких варианта преобразования задачи. Также на некоторых примерах приведены результаты работы рассмотренных способов решения поставленной задачи. Количество использованных источников: 8. Ширинкина, Д. А. Случайный поиск в задаче о назначениях: бакалаврская работа / Ширинкина Дарья Андреевна. – СПб., 2016. – 31 с. – Библиогр.: с. 31.

Математика

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36545f1be77c40d58cca

UUID: e13ba338-e2eb-437c-b82e-603e72da0425

Язык: Русский

Опубликовано: почти 8 лет назад

Просмотры: 13

Ширинкина Дарья Андреевна

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 1921925 bytes

Поделиться работой

Санкт-Петербургский государственный университет Прикладная математика и информатика Вычислительная стохастика и статистические модели Ширинкина Дарья Андреевна Случайный поиск в задаче о назначениях Бакалаврская работа Научный руководитель: д. ф.-м. н., профессор Ю. А. Сушков Рецензент: д. ф.-м. н., профессор Н. К. Кривулин Санкт-Петербург 2016

Saint Petersburg State University Applied Mathematics and Computer Science Computational Stochastics and Statistical Models Shirinkina Daria Andreevna Random search in the assignment problem Bachelor’s Thesis Scientific Supervisor: Professor Y. A. Sushkov Reviewer: Professor N. K. Krivulin Saint Petersburg 2016

Содержание Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Глава 1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Глава 2. Случайный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1. Описание алгоритма случайного поиска . . . . . . . . . . . . . . . . . . . 7 2.2. Случайный поиск с использованием логистической кривой . . . . . . . . 9 Глава 3. Методы детерминированного поиска оптимального отображе ния . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1. 12 Детерминированное определение оптимального отображения . . . . . . . Глава 4. Методы нахождения оптимального отображения случайным по иском . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.1. Метод 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2. Метод 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3. Метод с использованием факториальной системы счисления (метод 3) . 18 Глава 5. 5.1. Результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Случай совпадения количества функций и количества значений дискрет ных величин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. 20 22 Случай несовпадения количества функций и количества значений дис кретных величин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3

Введение В жизни возникает множество оптимизационных задач. Одни из них имеют доста точно простые условия и решение, к другим необходим особый подход, своеобразные методы. Как правило, на практике возникают нетривиальные задачи, которые подразу мевают под собой большое число параметров, сложный характер поведения целевой функции. К примеру, функции имеющие разрывы, недифференцируемые, многоэкс тремальные и т.д. Все эти условия усложняют поиск наименьшего или наибольшего значения. Для решения подобных задач можно использовать различные алгоритмы стохастической оптимизации. Некоторые задачи синтеза систем сводятся к поиску минимума сложной многоэкс тремальной функции, заданной на дискретно-непрерывном множестве. В данной работе исследуется применение алгоритма случайного поиска, описанного в работах [1] и [2], для нахождения минимума, возникающих в подобных задачах, функций, которые зави сят от числового аргумента и от дискретного отображения. В текущей работе рассмотрено несколько способов решения поставленной зада чи и их сравнение на некоторых примерах. Работа состоит из пяти глав. В первой главе работы описывается постановка задачи. Во второй главе рассматривается метод случайного поиска и его модификация с использованием логистической кривой. В тре тьей главе приведены известные сведения о решении поставленной задачи с помощью случайного поиска и алгоритмов, решающих задачу о назначениях. В четвертой гла ве сформулирована идея применения случайного поиска для отыскания оптимальных числового аргумента и дискретного отображения. В пятой главе приведены результаты моделирования для сравнения методов. 4

Глава 1 Постановка задачи Будем рассматривать задачу синтеза системы (МРС), описанную в работе [3]. Положим, что у нас есть набор функций 𝑓1 (𝑥[1 : 𝑑]), 𝑓2 (𝑥[1 : 𝑑]) . . . 𝑓𝑛 (𝑥[1 : 𝑑]), где 𝑓𝑖 : 𝐷 → R и 𝐷 ⊂ R𝑑 — ограниченная область, а 𝑥[1 : 𝑑] ∈ 𝐷. При этом 𝑖 ∈ 𝐼 = {1, 2, . . . , 𝑛}. В задаче синтеза системы вектор {𝑓1 , . . . , 𝑓𝑛 } называется вектором-функ цией значений выходных сигналов размерности 𝑛. За 𝑔[1 : 𝑚] будем принимать вектор, состоящий из заранее заданных значений 𝑔[𝑗] ∈ R, где 𝑗 ∈ 𝐽 = {1, 2, . . . , 𝑚}. Будем пред полагать, что 𝑛 > 𝑚. Требуется, чтобы значения некоторого подмножества функций 𝑓𝑖 были как можно ближе к значениям вектора 𝑔[1 : 𝑚]. Пусть инъективное отображение 𝜙 : 𝐽 → 𝐼, (1.1) ставит в соответствие индексам значений 𝑔[𝑗] индексы функций 𝑓𝑖 . Также пусть имеется функция свертки 𝐶(𝑥[1 : 𝑑], 𝜙), (1.2) отвечающая за точность приближения 𝑓𝑖 (𝑥[1 : 𝑑]) к значениям 𝑔[𝑗]. Далее будем назы вать эту функцию целевой. Данная функция зависит от отображения 𝜙 и от аргумента 𝑥[1 : 𝑑]. Таким образом, итоговая задача заключается в нахождении такого инъективно го отображения 𝜙 и такого значения аргумента 𝑥[1 : 𝑑], на которых будет достигаться минимум целевой функции (1.2). На практике в задачах синтеза часто используются следующие представления це левой функции (1.2), рассмотренные в работе [3]: ∑︁ (𝑓𝜙(𝑗) (𝑥[1 : 𝑑]) − 𝑔[𝑗])2 , (1.3) 𝐶(𝑥[1 : 𝑑], 𝜙) = max(𝑓𝜙(𝑗) (𝑥[1 : 𝑑]) − 𝑔[𝑗])2 , (1.4) ⃒ ⃒ ⃒ 𝑓𝜙(𝑗) (𝑥[1 : 𝑑]) ⃒ 𝐶(𝑥[1 : 𝑑], 𝜙) = max ⃒⃒ − 1⃒⃒. 𝑗∈𝐽 𝑔[𝑗] (1.5) 𝐶(𝑥[1 : 𝑑], 𝜙) = 𝑗∈𝐽 𝑗∈𝐽 Прямой способ решения данной задачи заключается в переборе всех возможных отображений 𝜙 вида (1.1), число которых 𝑛! . (𝑛−𝑚)! 5 Далее для каждого отображения 𝜙

находится минимум целевой функции (1.2). Часто целевая функция имеет достаточ но сложное поведение: многоэкстремальность, недифференцируемость. В таких случа ях для поиска минимума (1.2) при фиксированном отображении 𝜙 часто используется метод случайного поиска. При больших 𝑛 и 𝑚 время вычисления минимума целевой функции с помощью прямого способа решения достаточно большое. Чтобы увеличить скорость поиска минимума целевой функции можно использовать алгоритм из работы [3], в котором к целевой функции по аргументу 𝑥[1 : 𝑑] применяется случайный поиск и на каждом шаге для вычисления значения целевой функции при некотором значении 𝑥[1 : 𝑑] находится оптимальное отображение 𝜙. Другой подход к решению данной задачи заключается в применении случайно го поиска не только для отыскания оптимального аргумента 𝑥[1 : 𝑑], но и для поиска оптимального отображения 𝜙. Для этого отображение 𝜙 заменяется на отображение 𝜓(𝑦[1 : 𝑟]), аргумент которого — вектор размерности 𝑟, лежащий в области [0; 1]𝑟 , а множество значений — множество всех отображений 𝜙. При этом целевую функцию можно записать следующим образом: 𝐶(𝑥[1 : 𝑑], 𝜙) = 𝐶(𝑥[1 : 𝑑], 𝜓(𝑦[1 : 𝑟])). Такая заме на позволит применить случайный поиск по аргументу 𝑦 для отыскания оптимального отображения 𝜙. Цель данной работы заключается в изучении способов задания отображения 𝜓(𝑦[1 : 𝑟]) и анализе результатов нахождения минимума целевой функции (1.2) разными способа ми с использованием случайного поиска. 6

Глава 2 Случайный поиск 2.1. Описание алгоритма случайного поиска Рассмотрим алгоритм случайного поиска, описанный в работах [1] и [2]. Этот метод позволяет с некоторой вероятностью найти глобальный экстремум функций нескольких переменных. Принцип работы данного метода заключается в изменении начального рас пределения таким образом, чтобы при случайном выбрасывании точек с измененным распределением возрастала вероятность попадания в 𝜀-окрестность экстремального зна чения целевой функции. На первом шаге поиск происходит на всей области определения функции. На последующих шагах учитывается информация предыдущих и происходит ограничение окрестности, в которой наиболее ожидаемо содержание точки экстремума, за счёт уменьшения дисперсии распределения случайных точек. Далее в этой окрест ности поиск идет с большей интенсивностью. Пусть имеется целевая функция 𝐶(𝑥[1 : 𝑑]), где 𝑥[1 : 𝑑] — вектор аргументов размерности 𝑑. Будем считать, что компоненты 𝑥[𝑘], где 𝑘 ∈ 1 : 𝑑, лежат в интервале [0; 1], так как остальные ограничения можно учесть при построении функции 𝐶(𝑥), например, с помощью штрафных функций, рассмотренных в работе [2]. Рассмотрим поиск минимума целевой функции. Случайный поиск состоит из 𝑛𝑠𝑡𝑎𝑔𝑒 этапов, в свою очередь каждый этап делится на 𝑚𝑠𝑡𝑒𝑝 [𝑖] шагов, где 𝑖 — номер этапа. На каждом этапе задаётся определённый закон, по которому случайным образом выбираются значения аргументов 𝑥[1 : 𝑑]. Обозначим за 𝑥𝑗 [1 : 𝑑] случайные значения аргументов, выбранные на шаге 𝑗. Тогда 𝐶 𝑗 = 𝐶(𝑥𝑗 [1 : 𝑑]) — значение целевой функции, вычисленное в точке 𝑥𝑗 [1 : 𝑑]. Далее вычисляется минимум из всех значений 𝐶 𝑗 , полученных на одном этапе, по формуле 𝑗 𝑗−1 𝐶min = 𝐶(𝑥*𝑗 [1 : 𝑑]) = min{𝐶 𝑗 ; 𝐶min }, где 𝑥*𝑗 [1 : 𝑑] — значение аргумента 𝑥[1 : 𝑑], при котором целевая функция принимает наименьшее значение за 𝑗 шагов. После выполнения 𝑚𝑠𝑡𝑒𝑝 [𝑖] шагов на 𝑖-ом этапе изменя ется закон выбора случайных параметров 𝑥[1 : 𝑑] таким образом, чтобы на следующем этапе по нашим предположениям увеличить вероятность попадания в окрестность гло 7

бального минимума целевой функции. Предполагается, что в начале каждого этапа для параметров 𝑥[𝑘] выделяется ин тервал 𝐼[𝑘, 𝑖] 6 [0; 1] (𝑖 — номер этапа, 𝑘 ∈ 1 : 𝑑), в котором предполагается наиболее вероятное нахождение оптимального значения аргумента 𝑥[𝑘]. Ширина интервала 𝐼[𝑘, 𝑖] равна 2𝑞[𝑖]. Она одинакова для любых 𝑘 и зависит от номера этапа 𝑖. После каждого уменьшения значения целевой функции пересчитываются координаты центра интерва ла 𝐼[𝑘, 𝑖] по формуле 𝑥0𝑗 [𝑘] = max{𝑞[𝑖]; min{𝑥*𝑗 [𝑘]; 1 − 𝑞[𝑖]}}. С целью упрощения процесса моделирования параметры 𝑥[𝑘] выбираются с рав номерным распределением внутри и снаружи интервала 𝐼[𝑘, 𝑖]. Их плотности записы ваются соответствующим образом: 𝐻[𝑖] = 𝑝[𝑖]/𝑠[𝑖], ℎ[𝑖] = (1 − 𝑝[𝑖])/(1 − 𝑠[𝑖]), где 𝑝[𝑖] — вероятность того, что значение 𝑥[𝑘] ∈ 𝐼[𝑘, 𝑖], а 𝑠[𝑖] = (2𝑞[𝑖])𝑑 — 𝑑-мерный объём сужаемой области. На первом этапе поиск происходит равномерно на всём промежутке [0; 1] для каж дого параметра 𝑥[𝑘], так как нет никакой начальной информации о поведении целевой функции. Поэтому будем считать, что 𝑝[1] = 1 𝑞[1] = 1/2. и (2.1.1) Поиск минимума ведётся как внутри интервала 𝐼[𝑘, 𝑖], так и снаружи его. На прак тике в процессе поиска cужение интервала 𝐼[𝑘, 𝑖] происходит до заданной величины 𝜀. Пусть 𝑖 — номер этапа, тогда можно полагать, что lim 𝑝[𝑖] = 1 𝑖→∞ и lim 𝑞[𝑖] = 0. 𝑖→∞ (2.1.2) Из предположений (2.1.1) и (2.1.2) следует, что 𝑝[𝑖] достигает своего минимума на некотором этапе с номером 𝑖min , то есть 𝑝min = 𝑝[𝑖min ]. Внутри интервала 𝐼[𝑘, 𝑖] поиск проходит интенсивнее, так как там с большей ве роятностью ожидается оптимальное значение параметра 𝑥[𝑘]. Поэтому справедливы соотношения 8

1/2 6 𝑝[𝑖] 6 1 ℎ[𝑖] 6 1 6 𝐻[𝑖]. и (2.1.3) В качестве функции 𝑝[𝑖], будем использовать вариант, рассмотренный в работе [4]. 𝑝[𝑖] = ⎧ ⎪ ⎨ 𝑠[𝑖](𝑝min −1) + 1 𝑠min ⎪ ⎩ 𝑠[𝑖](1−𝑝min ) + 1−𝑠min если 0 6 𝑠[𝑖] 6 𝑠min , 𝑝min −𝑠min 1−𝑠min (2.1.4) если 𝑠min 6 𝑠[𝑖] 6 1. Функция 𝑝[𝑖] удовлетворяет всем необходимым условиям (2.1.1) – (2.1.3) и про ста для моделирования. За 𝑠min будем принимать 𝑑-мерный объём перспективной обла сти на этапе, которому соответствует минимальному значению вероятности 𝑝[𝑖]. Тогда 𝑠min = (2𝑞min )𝑑 , где 𝑞min = 𝑞[𝑖min ] и 𝑖min — номер этапа, на котором достигается минимум вероятности 𝑝[𝑖min ] = 𝑝min . При данном представлении вероятности 𝑝[𝑖] 𝐻[𝑖] и ℎ[𝑖] будут иметь вид: 𝐻[𝑖] = ⎧ ⎪ ⎨ 𝑝min −1 + 𝑠min 1 𝑠[𝑖] если 0 6 𝑠[𝑖] 6 𝑠min , ⎪ ⎩ 1−𝑝min + 𝑝min −𝑠min если 𝑠min 6 𝑠[𝑖] 6 1. 1−𝑠min 𝑠[𝑖](1−𝑠min ) ⎧ ⎪ ⎨ (1−𝑝min )𝑠[𝑖] + 1 если 0 6 𝑠[𝑖] 6 𝑠min , (1−𝑠[𝑖])𝑠min 𝑠[𝑖] ℎ[𝑖] = ⎪ ⎩ 1−𝑝min если 𝑠min 6 𝑠[𝑖] 6 1. 1−𝑠min 2.2. Случайный поиск с использованием логистической кривой Рассмотрим модификацию [4], [5], [6] алгоритма случайного поиска, в которой при меняется способ сужения перспективной области 𝐼[𝑘, 𝑖], основанный на логистическом уравнении: 𝑑𝑣(𝑡) 𝑣(𝑡) = 𝜇(1 − )𝑣(𝑡). 𝑑𝑡 𝑉∞ (2.2.1) Для случайного поиска в этом уравнении в качестве 𝑣 рассматривается объём перспективной области. То есть 𝑣 = (2𝑞)𝑑 , 𝑑 — размерность аргумента, принимаемого целевой функцией. Параметр 𝜇 отвечает за скорость изменения перспективной области, lim𝑡→∞ 𝑣(𝑡) = 𝑉∞ . Функция 𝑣(𝑡), являющаяся решением уравнения (2.2.1), имеет вид: 𝑣(𝑡) = 1 𝑉∞ + ( 𝑉10 9 1 − , 1 )𝑒−𝜇𝑡 𝑉∞

где 𝑉0 = 𝑣(0). Так как в процессе поиска ширина перспективного интервала 𝐼[𝑘, 𝑖] для 𝑘-ой компоненты вектора 𝑥[1 : 𝑑] изменяется от 1 до 0, то 𝑞[𝑖] принимает значения от 1 2 до 0. Поэтому будем полагать, что 𝑉∞ = 1 и 0 6 𝑉0 6 𝑉∞ . Тогда 𝑞[𝑖] можно записать в виде: 1 𝑞[𝑖] = 2 (︃ 1− 1 + ( 𝑉10 1 − 1)𝑒−𝜇𝑖/𝑛𝑠𝑡𝑎𝑔𝑒 )︃ . (2.2.2) Здесь 𝑛𝑠𝑡𝑎𝑔𝑒 — количество этапов случайного поиска, 𝑖 — текущий этап, 𝑖 ∈ 1 : 𝑛𝑠𝑡𝑎𝑔𝑒 . Параметр 𝑉0 зависит от 𝜇 и 𝜀, в свою очередь параметр 𝜇 зависит от 𝑉0 и 𝜀. При условии, что ширина перспективного интервала достигнет 𝜀 за фиксированное число этапов 𝑛𝑠𝑡𝑎𝑔𝑒 , то есть 2𝑞[𝑖] = 𝜀, параметры 𝑉0 и 𝜇 можно записать следующим образом: 𝑉0 = 𝜇 = − ln( 1 𝜀 𝑒𝜇 1−𝜀 +1 , 𝜀 𝑉0 ). 1 − 𝜀 1 − 𝑉0 10

Глава 3 Методы детерминированного поиска оптимального отображения Первый метод решения поставленной задачи состоит в полном переборе 𝑛!/(𝑛−𝑚)! отображений 𝜙. Далее для каждого полученного из перебора отображения 𝜙 находит ся минимум целевой функции (1.1), например, случайным поиском. Затем выбирается лучший результат (минимум) из 𝑛!/(𝑛−𝑚)! найденных значений. Использование такого прямого перебора достаточно трудоёмко, так как возникает необходимость минимизи ровать 𝑛!/(𝑛 − 𝑚)! функций. Второй подход решения задачи позволяет уменьшить трудоёмкость поиска опти мального отображения 𝜙. Рассмотрим идею такого подхода, приведённую в работе [3]. Идея заключается в том, чтобы применить случайный поиск по аргументу 𝑥[1 : 𝑑] к функции 𝐶(𝑥[1 : 𝑑]) = min(𝐶(𝑥[1 : 𝑑], 𝜙)). 𝜙 (3.1) Для вычисления функции (3.1) на каждом шаге случайного поиска находится отоб ражение 𝜙, которое будет минимизировать функцию 𝐶(˜ 𝑥[1 : 𝑑], 𝜙), где 𝑥˜[1 : 𝑑] некоторое фиксированное значение аргумента 𝑥[1 : 𝑑]. Таким образом, в отличие от предыдуще го метода, где происходит поиск оптимального аргумента 𝑥[1 : 𝑑] при фиксированном отображении 𝜙, в этом методе, наоборот, фиксируется аргумент 𝑥[1 : 𝑑], при котором уже ищется оптимальное отображение 𝜙. Так как случайный поиск в определённом смысле не критичен к сложным много экстремальным функциям, которые часто встречаются на практике, то при достаточно большом числе этапов результат, полученный с помощью рассмотренного подхода будет близким к точному решению. Для того чтобы найти отображение, на котором будет достигаться минимум целе вой функции при некотором фиксированном аргументе 𝑥[1 : 𝑑], нужно решить задачу о назначениях. Далее будем рассматривать различные способы решения этой задачи, в частности, такие, как алгоритм сдвига и венгерский алгоритм. 11

3.1. Детерминированное определение оптимального отображения Рассмотрим способ нахождения отображения 𝜙, которое минимизирует функцию 𝐶(˜ 𝑥[1 : 𝑑], 𝜙), где 𝑥˜[1 : 𝑑] — фиксированное значение аргумента. Сначала приведём идею алгоритма сдвига из работы [3], так как он лучше подходит для решения поставленной задачи. В работе [3] процесс поиска 𝜙 основывается на выделении некоторого подмноже ства отображений, в котором содержится оптимальное. Таким образом, перебор отоб ражений можно осуществлять только по этому подмножеству. Данный подход значи тельно сокращает время поиска минимума целевой функции. В этой работе было рассмотрено три вида целевой функции (1.2), которые наибо лее часто встречаются в задачах синтеза систем: (1.3), (1.4) и (1.5). Для этих функций в работе [3] доказана теорема, позволяющая сузить множество отображений, в котором содержится оптимальное. В этой теореме используется следующее понятие. Определение 1. Пусть имеется два конечных множества 𝐴 = {𝑎1 , . . . , 𝑎𝑛 } и 𝐵 = {𝑏1 , . . . , 𝑏𝑚 }. Тогда отображение 𝜙 из 𝐴 в 𝐵 называется монотонным, если для любых 𝑎𝑖1 и 𝑎𝑖2 , таких что 𝑎𝑖1 6 𝑎𝑖2 , выполняется 𝜙(𝑎𝑖1 ) 6 𝜙(𝑎𝑖2 ). Так как аргумент 𝑥[1 : 𝑑] фиксирован и его значение равно 𝑥˜[1 : 𝑑], то можем вы числить 𝑓𝑖 (˜ 𝑥[1 : 𝑑]) при 𝑖 ∈ 𝐼 = {1, 2, . . . , 𝑛}. Обозначим за 𝑧𝑖 полученные значения, то есть 𝑧𝑖 = 𝑓𝑖 (˜ 𝑥[1 : 𝑑]), где 𝑖 ∈ 𝐼. Будем предполагать, что значения 𝑧𝑖 и 𝑔[𝑗] упорядочены по возрастанию. Это значит, что для любого 𝑖 ∈ 𝐼 и для любого 𝑗 ∈ 𝐽 = {1, 2, . . . , 𝑚} выполняются соотношения 𝑧𝑖 6 𝑧𝑖+1 и 𝑔[𝑗] 6 𝑔[𝑗 + 1]. При невыполнении этого предпо ложения можно перенумеровать значения 𝑧𝑖 и 𝑔[𝑗]. Также пусть 𝐺 = {𝑔[1], . . . , 𝑔[𝑚]} и 𝑍 = {𝑧1 , . . . , 𝑧𝑛 } — упорядоченные по возрастанию наборы. Тогда для целевых функций вида (1.3), (1.4) и (1.5) верна следующая теорема из работы [3]. Теорема 1. Пусть задано множество требуемых значений для передаточных функ ций режимов системы 𝑆, 𝐺 = {𝑔[1], . . . , 𝑔[𝑚]}. Пусть также значения передаточных функций режимов системы 𝑆 описывается множеством 𝑍 = {𝑧1 , . . . , 𝑧𝑛 }, 𝑚 6 𝑛. Тогда минимум функций (1.3), (1.4) и (1.5) достигается на множестве монотонных отображений 𝜙, 𝜙 : 𝐺 → 𝑍. 12

Таким образом, при фиксированном аргументе 𝑥˜[1 : 𝑑] поиск минимального зна чения функции (3.1) сводится к перебору всех монотонных отображений 𝜙 и выбора того из них, на котором достигается минимум (3.1). Алгоритм, перебирающий такие отображения, представленный в работе [3], называется алгоритмом сдвига. Заметим, что при условии равенства 𝑚 = 𝑛 в теореме (1) монотонное отображение 𝜙 будет единственным. Для нахождения отображения 𝜙 при фиксированном аргументе 𝑥 можно пользо ваться и другими алгоритмами. Например, в случае 𝑛 = 𝑚 и для целевой функции вида (1.3) можно применить венгерский алгоритм, описанный в [7], для поиска отоб ражения 𝜙. Данный метод позволяет находить оптимальное назначение 𝜙 при условии минимизации целевой функции, в нашем примере это функция вида (1.3), с трудоёмко стью 𝑂(𝑛3 ). Однако для рассмотренных целевых функций (1.3), (1.4) и (1.5) выгоднее использовать алгоритм сдвига, так как он менее трудоёмкий. 13

Глава 4 Методы нахождения оптимального отображения случайным поиском В данном разделе будем рассматривать методы, которые позволяют с некоторой вероятностью найти аргумент 𝑥[1 : 𝑑] и отображение 𝜙, минимизирующие целевую функцию (1.2). Для нахождения решения будем использовать случайный поиск, при этом не только для отыскания оптимального аргумента 𝑥[1 : 𝑑], но и для поиска опти мального отображения 𝜙. Чтобы можно было применить случайный поиск для нахождения 𝜙, введём до полнительное отображение, переводящее аргумент из единичного куба в одно из все возможных отображений 𝜙. Запишем это отображение следующим образом: 𝜓(𝑦[1 : 𝑟]), (4.1) где 𝑦 ∈ [0; 1]𝑟 , а 𝑟 — размерность аргумента 𝑦. Значение размерности 𝑦 будет изменяться в зависимости от представления отображения 𝜓. Так как множество значений 𝜓 — это все возможные отображения 𝜙, то в целевой функции (1.2) отображение 𝜙 можно заменить на 𝜓. Также обозначим за 𝜓(𝑦, 𝑗) значение отображения 𝜙, полученного при некотором значении 𝑦, в точке 𝑗 ∈ 𝐽 = {1, 2, . . . , 𝑚}. Таким образом, можно записать, что 𝜓(˜ 𝑦 , 𝑗) = 𝜙(𝑗) ˜ при условии 𝜓(˜ 𝑦 ) = 𝜙, ˜ где 𝑦˜ и 𝜙˜ — фиксированные. Тогда, заменив отображение 𝜙 на 𝜓, целевую функцию (1.2) можно привести к виду 𝐶(𝑥[1 : 𝑑], 𝜓(𝑦[1 : 𝑟])) = 𝐶(𝑥[1 : 𝑑], 𝜙) = ∑︁ (𝑓𝜓(𝑦[1:𝑟],𝑗) (𝑥[1 : 𝑑]) − 𝑔[𝑗])2 . (4.2) 𝑗∈𝐽 К новому представлению целевой функции (4.2) можно применить случайный по иск одновременно по аргументам 𝑥[1 : 𝑑] и 𝑦[1 : 𝑟]. Таким образом, с помощью слу чайного поиска с некоторой вероятностью может быть найдено решение с заданной точностью. Далее будем рассматривать три варианта представления отображения 𝜓: метод 1, метод 2 и метод с использованием факториальной системы счисления (метод 3). Для первого случая опишем общую ситуацию, когда 𝑚 6 𝑛, так как этот способ лучше 14

всего показал себя для простого случая, когда 𝑚 = 𝑛. Для двух других ограничимся описанием алгоритма при 𝑚 = 𝑛 и 𝐽 = 𝐼 (в этом случае отображение 𝜙 является биекцией). 4.1. Метод 1 Рассмотрим первый способ задания отображения 𝜓(𝑦[1 : 𝑟]). В этом подходе бу дем полагать, что размерность 𝑟 аргумента 𝑦 равна количеству значений 𝑔[𝑗], то есть 𝑟 = 𝑚. Тогда пусть 𝑗-ая компонента вектора 𝑦 отвечает за получение значения 𝜙(𝑗), где 𝑗 ∈ 𝐽 = {1, 2, . . . , 𝑚}. Опишем подробнее данную идею. Пусть 𝑦[𝑗] — это 𝑗-ая компонента вектора 𝑦[1 : 𝑟]. Зададим вспомогательную функцию ˆ 𝜓(𝑦[1 : 𝑚], 𝑗) = ⌈(𝑛 − 𝑗 + 1) · 𝑦[𝑗]⌉, где ⌈(𝑛 − 𝑗 + 1) · 𝑦[𝑗]⌉ означает округление вверх числа (𝑛 − 𝑗 + 1) · 𝑦[𝑗], а 𝑗 ∈ 𝐽 = ˆ {1, 2, . . . , 𝑚}. Получим, что 𝜓(𝑦[1 : 𝑚], 𝑗) принимает целые значения от 1 до 𝑛 − 𝑗 + 1 в зависимости от значения 𝑦[𝑗]. ˆ Данная функция 𝜓(𝑦[1 : 𝑚], 𝑗) может принимать одинаковые значения при раз личных 𝑗, чего не должно быть для 𝜙(𝑗), значения которых хотим получить в ито ˆ ге. Чтобы избежать повторения принимаемых значений функции 𝜓(𝑦[1 : 𝑚], 𝑗), будем каждому полученному номеру от 1 до 𝑛 − 𝑗 + 1 ставить в соответствие ещё не ис пользуемый номер от 1 до 𝑛 при меньших значениях 𝑗 следующим образом. Пусть N = N1 = 𝐼 = {1, 2, . . . , 𝑛} — упорядоченный набор. Будем задавать не само отобра жение 𝜓(𝑦), а значения 𝜓(𝑦, 𝑗), соответствующие получаемым элементам 𝜙(𝑗). Таким образом, зная значения 𝜓(𝑦, 𝑗), можно однозначно восстановить получаемое отображе ние 𝜙. Тогда зададим 𝜓(𝑦[1 : 𝑚], 𝑗) по следующему алгоритму, начиная с 𝑗 = 1 и 𝑗 ∈ 𝐽: ˆ 1) 𝜓(𝑦[1 : 𝑚], 𝑗) равно числу из упорядоченного множества N𝑗 с номером 𝜓(𝑦[1 : 𝑚], 𝑗), обозначим это число за 𝛼𝑗 ; 2) пусть 𝜓(𝑦[1 : 𝑚], 𝑗) = 𝛼𝑗 — выбранное число, тогда исключим это значение из множества N𝑗 : N𝑗+1 = N𝑗 ∖ 𝛼𝑗 ; переходим к пункту 1, приняв 𝑗 ← 𝑗 + 1, если 𝑗 < 𝑚. 15

Таким образом, область [0; 1]𝑚 , в которой принимает свое значение параметр 𝑦[1 : 𝑚], поделится на 𝑛!/(𝑛 − 𝑚)! равных по объёму областей. Каждой такой области будет со ответствовать некоторый набор значений {𝜓(𝑦, 1), 𝜓(𝑦, 2), . . . , 𝜓(𝑦, 𝑚)}, то есть какое-то отображение 𝜙. В этом способе задания отображения 𝜓(𝑦) размерность добавляемого аргумента 𝑦 зависит от задачи и растёт с увеличением 𝑚. Так как добавление аргумен та 𝑦 может сильно увеличивать размерность общей задачи, а чем больше размерность задачи, тем хуже случайный поиск справляется с нахождением решения, то это может потребовать задания большего числа этапов для повышения точности. Выпишем общий алгоритм вычисления значений 𝜓(𝑦, 𝑗). Он принимает следую щий вид: 1) получаем 𝑚 значений 0 6 𝑦[𝑗] 6 1, 𝑗 ∈ 𝐽, где 𝐽 = {1, 2, . . . , 𝑚}; ˆ 2) вычисляем значения 𝜓(𝑦[1 : 𝑚], 𝑗) = ⌈(𝑛 − 𝑗 + 1) · 𝑦[𝑗]⌉, 𝑗 ∈ 𝐽; 3) N1 = 𝐼 = {1, 2, . . . , 𝑛} — упорядоченный набор, начальное значение индекса 𝑗 — 𝑗 ← 1; ˆ 4) 𝜓(𝑦[1 : 𝑚], 𝑗) = 𝛼𝑗 — число из N𝑗 с номером 𝜓(𝑦[1 : 𝑚], 𝑗); 5) N𝑗+1 = N𝑗 ∖ 𝛼𝑗 ; 6) если 𝑗 < 𝑚, то 𝑗 ← 𝑗 + 1 и переходим к пункту 4, иначе конец. 4.2. Метод 2 Рассмотрим второй алгоритм задания отображения 𝜓(𝑦), но только при случае, когда 𝑛 = 𝑚. В данном способе так же, как и в предыдущем, будем задавать не само отображение 𝜓(𝑦), а значения 𝜓(𝑦, 𝑗), из которых уже можно однозначно восстановить получаемое отображение 𝜙. Для этого способа будем полагать, что размерность аргу мента 𝑦 не зависит от 𝑚 и 𝑛 и будет равна 1, то есть 𝑦 ∈ [0; 1]. Чтобы получить 𝑚 целых значений 𝜓(𝑦, 𝑗) из одного числа 𝑦 ∈ [0; 1], воспользуемся ˆ 𝑗 , 𝑗), где 𝑗 ∈ 𝐼 = 𝐽 = {1, 2, . . . , 𝑚}. Пусть 𝑦1 = 𝑦. Тогда вспомогательной функцией 𝜓(𝑦 ˆ 𝑗 , 𝑗) = ⌈(𝑛 − 𝑗 + 1) · 𝑦𝑗 ⌉, 𝜓(𝑦 16

при этом 𝑦𝑗+1 = {(𝑛 − 𝑗 + 1) · 𝑦𝑗 }. Здесь ⌈(𝑛−𝑗+1)·𝑦𝑗 ⌉ — это округление вверх числа (𝑛−𝑗+1)·𝑦𝑗 , а {(𝑛 − 𝑗 + 1) · 𝑦𝑗−1 } ˆ 𝑗 , 𝑗) принимает — дробная часть числа (𝑛 − 𝑗 + 1) · 𝑦𝑗−1 . Таким образом, функция 𝜓(𝑦 целые значения от 1 до 𝑛 − 𝑗 + 1. Далее аналогично первому методу будем ставить в ˆ 𝑗 , 𝑗) такое целое число от 1 до 𝑛, которое для меньших значе соответствие значению 𝜓(𝑦 ний 𝑗 ещё не было использовано. Опишем эту процедуру. Пусть имеются вычисленные ˆ 𝑗 , 𝑗) для 𝑗 ∈ 𝐽. Обозначим за N = N1 = {1, 2, . . . , 𝑛} — упорядоченный значения 𝜓(𝑦 набор. Тогда зададим 𝜓(𝑦, 𝑗) по следующему алгоритму, считая, что вначале 𝑗 = 1: ˆ 𝑗 , 𝑗), обозначим это число за 𝛼𝑗 ; 1) 𝜓(𝑦, 𝑗) равно числу из N𝑗 с номером 𝜓(𝑦 2) пусть 𝜓(𝑦, 𝑗) = 𝛼𝑗 — выбранное число, тогда исключим это число из N𝑗 : N𝑗+1 = N𝑗 ∖ 𝛼𝑗 ; если 𝑗 < 𝑚, переходим к пункту 1, увеличивая значение 𝑗 на 1 (𝑗 ← 𝑗 + 1). По сравнению с первым методом данный способ добавляет аргумент 𝑦 фиксиро ванной размерности, не зависящей от параметров в задаче, что даёт преимущество для вычисления случайным поиском. Пусть 𝐽 = {1, 2, . . . , 𝑚}. Рассмотрим общий алгоритм метода вычисления 𝜓(𝑦, 𝑗): 1) получаем 𝑦 ∈ [0; 1], пусть 𝑦1 = 𝑦; 2) вычисляем для каждого 𝑗 ∈ 𝐽 и 𝑗 > 2 значения 𝑦𝑗 = {(𝑛 − 𝑗 + 1) · 𝑦𝑗−1 }; ˆ 𝑗 , 𝑗) = ⌈(𝑛 − 𝑗 + 1) · 𝑦𝑗 ⌉; 3) для всех 𝑗 ∈ 𝐽 получаем значения 𝜓(𝑦 4) N1 = 𝐼 = {1, 2, . . . , 𝑛} — упорядоченный набор, 𝑗 ← 1; ˆ 𝑗 , 𝑗); 5) 𝜓(𝑦, 𝑗) = 𝛼𝑗 — число из Nj с номером 𝜓(𝑦 6) Nj+1 = Nj ∖ 𝛼𝑗 ; 7) если 𝑗 < 𝑚, то 𝑗 ← 𝑗 + 1 и переходим к пункту 5, иначе конец. 17

4.3. Метод с использованием факториальной системы счисления (метод 3) В первом методе добавляется аргумент 𝑦 размерности 𝑚, что сильно увеличивает размерность задачи. В этом способе рассмотрим случай 𝑛 = 𝑚 и вариант с добавлени ем одномерного дополнительного аргумента 𝑦, то есть 𝑟 = 1. Воспользуемся тем, что количество всех возможных отображений 𝜙 при 𝑛 = 𝑚 равняется 𝑛!. Идея, как и в первом методе, заключается в разделении множества принимаемых значений дополни тельной переменной 𝑦 на 𝑛! равных частей. Каждая такая часть будет соответствовать некоторому отображению 𝜙. Так как аргумент 𝑦 имеет единичную размерность, то его множество принимаемых значений — это отрезок [0; 1]. Разделим отрезок [0; 1] на 𝑛! равных частей и пронумеруем их. Сделаем это следующим образом: первая часть — [︀ )︀ [︀ )︀ это полуинтервал 0; 𝑛!1 , вторая часть — полуинтервал 𝑛!1 ; 𝑛!2 , и так далее, последняя [︀ ]︀ часть с номером 𝑛! — это отрезок 𝑛!−1 ; 1 . Так как число таких отрезков 𝑛! и равно 𝑛! количеству отображений 𝜙, то между ними можно установить взаимно однозначное соответствие. Тогда для получения номера одного из 𝑛! равных отрезков, лежащего в [0; 1], достаточно умножить 𝑦 ∈ [0; 1] на 𝑛! и взять целую часть. Далее возникает необходимость полученному номеру отрезка поставить в соответ ствие отображение 𝜙. Так как отображение 𝜙 можно представить как перестановку порядка 𝑛, то воспользуемся утверждениями из [8] о том, что: 1) для произвольного целого неотрицательного числа существует единственное 𝑛-факториальное представление; 2) по 𝑛-факториальному представлению индекса перестановки несложно восстанав ливается сама перестановка. Индекс перестановки — это номер перестановки, принимающий целое значение от 1 до 𝑛!. Пусть имеется 𝑦 ∈ [0; 1] и 𝐼 = {1, 2, . . . , 𝑛}. Тогда запишем подробный алгоритм: 1) вычисляем значение 𝜈 = ⌈𝑦 · 𝑛!⌉ — это индекс перестановки; 2) записываем 𝜈 в факториальной системе счисления, то есть 𝜈 = ∑︀𝑛−1 𝑘=1 𝜈𝑘 · 𝑘!; 3) далее рассмотрим множество {𝜈1 , 𝜈2 , . . . , 𝜈𝑛−1 }, построим по этому множеству пе рестановку 𝜙, при этом 𝜓(𝑦, 𝑖) — 𝑖-ый элемент получаемой из 𝑦 перестановки 𝜙; 18

коэффициент 𝜈𝑘 обозначает число инверсий для элемента 𝑘 + 1, исходя из этого можем записать: ∙ пусть 𝑘 = 𝑛−1, тогда для числа 𝑛 в перестановке находится 𝜈𝑛−1 меньших эле ментов, стоящих правее него; так как 𝑛 — максимальный элемент перестанов ки, значит номер его места в перестановке равен 𝑛 − 𝜈𝑛−1 и 𝜓(𝑦, 𝑛 − 𝜈𝑛−1 ) = 𝑛; ∙ пусть 1 6 𝑘 < 𝑛 − 1, тогда для числа 𝑘 + 1 в перестановке находится 𝜈𝑘 меньших элементов, стоящих правее него; в данном случае нужно с конца перестановки отсчитать 𝜈𝑘 свободных мест; тогда номер места элемента 𝑘 + 1 в перестановке равен 𝑛 − (𝜈𝑘 + 𝑙) и 𝜓(𝑦, 𝑛 − (𝜈𝑘 + 𝑙)) = 𝑘 + 1, где 𝑙 — число уже записанных элементов в перестановку 𝜓(𝑦), оказавшихся правее найденного свободного места; ∙ последний элемент перестановки записывается на последнее оставшееся ме сто. При больших 𝑛 данный подход задания отображения 𝜓(𝑦) может работать неточ но, так как длина отрезков, соответствующих отображениям 𝜙, сильно уменьшается. Чтобы верно распознавать нужный номер отрезка, необходима более высокая точность значения аргумента 𝑦. 19

Глава 5 Результаты В предыдущих разделах рассматривались способы решения поставленной задачи. В этом разделе приведены некоторые примеры, на которых сравнивались ранее рас смотренные методы. Для сравнения методов, рассмотренных в третьей и четвертой главе, в качестве на бора 𝑓1 (𝑥[1 : 𝑑]), 𝑓2 (𝑥[1 : 𝑑]) . . . 𝑓𝑛 (𝑥[1 : 𝑑]) сначала использовались несложные функции, а именно квадратичные функции вида: 𝑓𝑖 (𝑥[1 : 𝑑]) = 1 ⟨𝐴𝑖 𝑥, 𝑥⟩ + ⟨𝑏𝑖 , 𝑥⟩ + 𝑐𝑖 , 2 (5.1) где для каждого 𝑖 ∈ 𝐼 = {1, 2, . . . , 𝑛} задаётся 𝐴𝑖 — матрица порядка 𝑑×𝑑, симметричная и неотрицательно определенная, 𝑏𝑖 — вектор размерности 𝑑, 𝑐𝑖 — произвольное значение. За ⟨, ⟩ обозначается скалярное произведение. Для определения точности вычисления нужно знать точку минимума целевой функции. Для этого произвольным образом задавалась точка 𝑥* [1 : 𝑑] — аргумент, на котором достигается минимум (1.2). Далее находились значения 𝑓𝑖 (𝑥* ), 𝑖 ∈ 𝐼. Также случайным образом задавалось отображение 𝜙. Тогда при таком наборе значений 𝑔[𝑗], что 𝑔[𝑗] = 𝑓𝜙(𝑗) (𝑥* ), где 𝑗 ∈ 𝐽 = {1, 2, . . . , 𝑚}, целевая функция (1.2) достигала своего минимума, равного 0, в точке 𝑥* [1 : 𝑑]. Программа для сравнения методов была реализована в среде MATLAB. Для поис ка минимума целевой функции с помощью одного из рассмотренных методов запуска лась главная функция gmain, принимающая в качестве аргумента строку с названием метода. В этой же функции задавались параметры случайного поиска, количество за пусков 𝑁 исследуемого метода для нахождения минимума целевой функции. Также в функции gmain прописывались параметры задачи: вид функций 𝑓𝑖 (𝑥[1 : 𝑑]), значения 𝑔[𝑗], размерность аргумента 𝑥. При 𝑁 = 1 (один запуск метода для поиска минимума целевой функции) выво дилось значение аргумента 𝑥[1 : 𝑑], на котором предполагалось достижение минимума целевой функции, также полученное значение целевой функции в этой точке и отобра жение 𝜙 в виде перестановки. Для 𝑛 6 3 и размерности аргумента 𝑥 𝑑 = 1 и 𝑑 = 2 строились графики целевых функций при фиксированных отображениях 𝜙 и отмеча 20

лась найденная точка предполагаемого минимума (рис. 5.1). При 𝑁 > 1 вычислялось выборочное среднее, выборочное стандартное отклонение, оценка вероятности 𝑃 на хождения глобального минимума. В качестве оценки вероятности 𝑃 нахождения гло бального минимума было рассмотрено отношение числа найденных значений целевой функции, отличающихся от глобального минимума не более, чем на 0, 02, к общему числу случаев. В методе случайного поиска для вероятности попадания в перспективную область использовалось соотношение (2.1.4). Для сужения перспективной области использова лась модификация случайного поиска на базе логистической кривой (2.2.2). При этом количество шагов бралось равным на каждом этапе, обозначим это число за 𝑚𝑠𝑡𝑒𝑝 . Па раметр 𝜀 = 0, 01. Для выбора оптимальных 𝑞min , 𝑝min и 𝜇 использовались результаты из работы [4] для многоэкстремальных функций, где оптимальное значение 𝑝min ле жит в интервале [0, 8; 1], оптимальное 𝑞min находится в [0, 02; 0, 07] ∪ [0, 4; 0, 5], а 𝜇 > 6. Таким образом, в алгоритме случайного поиска использовались значения 𝑝min = 0, 8, 𝑞min = 0, 45 и 𝜇 = 6. Значение 𝑞min было выбрано из промежутка [0, 4; 0, 5], так как это общий интервал всех трёх видов функций, рассмотренных в работе [4], таким обра зом, он более универсальный. Параметры поиска подбирались для многоэкстремальных функций, так как даже при унимодальном виде функций 𝑓𝑖 (𝑥) общее представление це левой функции скорее всего будет иметь несколько локальных минимумов, что можно увидеть на рис. 5.1. За общее число шагов случайного поиска будем понимать величину 𝑛𝑠𝑡𝑎𝑔𝑒 · 𝑚𝑠𝑡𝑒𝑝 , где 𝑛𝑠𝑡𝑎𝑔𝑒 — количество этапов, а 𝑚𝑠𝑡𝑒𝑝 — фиксированное количество шагов одинаковое для каждого этапа. Для каждого метода вычислялся минимум целевой функции 𝑁 = 1000 раз. При этом 𝑥* [1 : 𝑑] выбирался случайным образом в заданной области для каждого следую щего подсчёта целевой функции. Так же для функций 𝑓𝑖 (𝑥[1 : 𝑑]) вида (5.1) случайным образом в некотором диапазоне видоизменялись значения 𝑐𝑖 , элементы в матрице 𝐴𝑖 и векторе 𝑏𝑖 . Пример построения графика при запуске программы для вычисления минимума целевой функции вида (1.3) при 𝑛 = 𝑚 = 3, 𝑑 = 2 отображён на рис. 5.1. Функции 𝑓𝑖 вида (5.1). Точное значение точки минимума: 𝑥* [1] = −0, 9 и 𝑥* [2] = 0, 85. Целевая функция отображена на графике для каждого фиксированного отображения 𝜙. Каж дому отображению 𝜙 соответствует один цвет. Центр красных кругов — найденный 21

90 80 C (x[1 : 2], ϕ) 70 60 50 40 30 20 10 0.5 0 0 0.5 0 −0.5 −0.5 −1 −1 x[1] x[2] Рис. 5.1. Целевая функция и предполагаемый минимум, найденный программой с помо щью метода 1 при 𝑛 = 𝑚 = 3 и 𝑑 = 2. Каждый цвет соответствует некоторому фиксированному отображению 𝜙 в целевой функции. предполагаемый глобальный минимум целевой функции. 5.1. Случай совпадения количества функций и количества значений дискретных величин Для сравнения методов сначала рассмотрим частный случай, когда число функ ций 𝑓𝑖 и число значений 𝑔[𝑗] одинаково, то есть 𝑚 = 𝑛. Для этой ситуации был рассмотрен случай размерности аргумента 𝑥[1 : 𝑑]: 𝑑 = 2. Количество функций 𝑓𝑖 и значений 𝑔𝑗 бралось равным 𝑛 = 𝑚 = 9, такое значение параметра часто встречается на практике. Функции 𝑓𝑖 рассматривались вида (5.1). Для методов из третьей главы, основанных на поиске оптимального отображения 𝜙 детерминированным путём, вероятность нахождения минимума целевой функции ви да (1.3),(1.4) и (1.5) равнялась 1 при 𝑛𝑠𝑡𝑎𝑔𝑒 = 100 и 𝑚𝑠𝑡𝑒𝑝 = 100. Такие точные результа ты обусловлены тем, что данный метод сводится к случайному поиску, применённого 22

к функции, зависящей только от аргумента 𝑥[1 : 𝑑]. Используя данные методы, для любого значения аргумента 𝑥 мы можем узнать такое отображение 𝜙, на котором по лучится минимум целевой функции. Таким образом, решения подобными способами будут всегда точнее методов, рассмотренных в четвёртой главе. Моделирование метода 2 и метода с использованием факториальной системы счис ления показало достаточно схожие результаты (рис. 5.2) при 𝑚𝑠𝑡𝑒𝑝 = 100. Для этих под ходов вероятность нахождения минимума целевой функции (1.3) небольшая, но растёт с увеличением общего количества шагов случайного поиска. Таким образом, для по вышения точности вычислений необходимо увеличивать параметр 𝑛𝑠𝑡𝑎𝑔𝑒 или 𝑚𝑠𝑡𝑒𝑝 , что значительно будет сказываться на скорости поиска минимума. 0.28 0.26 Method 2 Method 3 0.24 0.22 P 0.2 0.18 0.16 0.14 0.12 0.1 0.08 1000 1500 2000 2500 3000 n stage Рис. 5.2. Зависимость вероятности нахождения минимума целевой функции от количества этапов случайного поиска для метода 2 и метода с использованием факториальной системы счисления (метод 3). Вид целевой функции (1.3). Параметр 𝑚𝑠𝑡𝑒𝑝 = 100. Точность первого метода также уступает методам, в которых на каждом шаге случайного поиска находится отображение 𝜙, минимизирующее целевую функцию. Это происходит за счёт добавления дополнительного аргумента, по которому также должен производиться поиск. В следствие этого происходит большее накопление ошибки, чем в случае, когда мы можем точно вычислить оптимальное значение по этому аргумен ту. Зависимость вероятности нахождения минимума целевой функции вида (1.3), (1.4) и (1.5) с заданной точностью от количества этапов 𝑛𝑠𝑡𝑎𝑔𝑒 для первого метода отобра жена на рис. 5.3. Здесь также количество шагов случайного поиска бралось равным 23

𝑚𝑠𝑡𝑒𝑝 = 100. 1 function (1.3) function (1.4) 0.9 function (1.5) 0.8 P 0.7 0.6 0.5 0.4 0 100 500 1000 1500 n stage Рис. 5.3. Зависимость вероятности нахождения минимума целевой функции от количества этапов случайного поиска для метода 1. Целевые функции вида (1.3), (1.4) и (1.5). Параметр 𝑚𝑠𝑡𝑒𝑝 = 100. Данный подход показывает лучшие результаты, чем два предыдущих рассмотрен ных метода с использованием случайного поиска для получения оптимального отоб ражения 𝜙. Здесь также прослеживается увеличение вероятности 𝑃 при возрастании 𝑛𝑠𝑡𝑎𝑔𝑒 . С ростом 𝑛𝑠𝑡𝑎𝑔𝑒 происходит и уменьшение стандартного отклонения (рис. 5.4). Для целевых функций вида (1.3) и (1.4) были посчитаны вероятности нахождения минимума для параметра 𝑚𝑠𝑡𝑒𝑝 случайного поиска равного 1. Для сравнения с вариан том, когда 𝑚𝑠𝑡𝑒𝑝 = 100, количество обращений к целевой функции для её вычисления сохранялось постоянным. Таким образом, значение 𝑛𝑠𝑡𝑎𝑔𝑒 выбиралось так, чтобы про изведение 𝑛𝑠𝑡𝑎𝑔𝑒 · 𝑚𝑠𝑡𝑒𝑝 оказывалось равным для 𝑚𝑠𝑡𝑒𝑝 = 1 и 𝑚𝑠𝑡𝑒𝑝 = 100. Результаты вычислений приведены в таблице 5.1. Результаты, представленные в таблице 5.1, почти не отличаются для значений 𝑚𝑠𝑡𝑒𝑝 = 1 и 𝑚𝑠𝑡𝑒𝑝 = 100, однако в некоторых случаях вероятность нахождения минимума целевой функции при 𝑚𝑠𝑡𝑒𝑝 = 1 немного превосходит значения, полученные для 𝑚𝑠𝑡𝑒𝑝 = 100. Данные результаты можно объяснить тем, что при уменьшении 𝑚𝑠𝑡𝑒𝑝 увеличивается 𝑛𝑠𝑡𝑎𝑔𝑒 при условии, что значение 𝑛𝑠𝑡𝑎𝑔𝑒 · 𝑚𝑠𝑡𝑒𝑝 зафиксировано. При этом чем больше 24

2.5 function (1.3) function (1.4) function (1.5) 2 Sd 1.5 1 0.5 0 0 100 500 1000 1500 n stage Рис. 5.4. Зависимость стандартного отклонения от количества этапов случайного поиска для метода 1. Целевые функции вида (1.3), (1.4) и (1.5). Параметр 𝑚𝑠𝑡𝑒𝑝 = 100. Таблица 5.1. Вероятность нахождения минимума целевой функции с помощью метода 1 при разных значениях параметров 𝑛𝑠𝑡𝑎𝑔𝑒 и 𝑚𝑠𝑡𝑒𝑝 случайного поиска. Функции 𝑓𝑖 вида (5.1). б) Вид целевой функции (1.4). а) Вид целевой функции (1.3). 𝑛𝑠𝑡𝑎𝑔𝑒 · 𝑚𝑠𝑡𝑒𝑝 𝑛𝑠𝑡𝑎𝑔𝑒 · 𝑚𝑠𝑡𝑒𝑝 𝑚𝑠𝑡𝑒𝑝 = 100 𝑚𝑠𝑡𝑒𝑝 = 1 𝑚𝑠𝑡𝑒𝑝 = 100 𝑚𝑠𝑡𝑒𝑝 = 1 10000 0, 57 0, 59 10000 0, 52 0, 57 50000 0, 78 0, 78 50000 0, 78 0, 78 100000 0, 82 0, 83 100000 0, 81 0, 81 150000 0, 88 0, 90 150000 0, 84 0, 85 параметр 𝑛𝑠𝑡𝑎𝑔𝑒 , тем медленнее происходит сужение перспективной области в алгоритме случайного поиска, что даёт больше времени, чтобы понять в каком направлении нужно искать интенсивнее. Данное преимущество должно быть более заметно, когда целевая функция имеет острые минимумы. Так как при функциях 𝑓𝑖 вида (5.1) целевая функция имеет не очень сложное поведение и не имеет острых минимумов, то замена количества шагов случайного поиска с 𝑚𝑠𝑡𝑒𝑝 = 100 на 𝑚𝑠𝑡𝑒𝑝 = 1 практически не ощутима. Для метода 1 и методов из третьей главы в качестве примера был рассмотрен бо лее сложный вид функций 𝑓𝑖 при 𝑛 = 𝑚 = 9. Как и ранее часть функций 𝑓𝑖 оставались 25

квадратичными вида (5.1), оставшиеся функции имели сложный многоэкстремальный характер. Варианты сложных функций были взяты из работы [4]. Для каждого нового подсчёта минимума целевой функции случайным образом из вариантов многоэкстре мальных функций, представленных в [4], выбиралось нужное количество.Таким обра зом, при общем числе функций 𝑓𝑖 равным 9 (𝑛 = 9) от 1 до 5 из них рассматривались многоэкстремального характера, остальные по-прежнему имели вид (5.1). В данном случае вычисления производились для вида целевой функции (1.3) и фиксированного количества шагов 𝑚𝑠𝑡𝑒𝑝 = 100 и этапов 𝑛𝑠𝑡𝑎𝑔𝑒 = 1000 случайного поиска. Результаты моделирования для целевой функции вида (1.3) представлены на рис. 5.5. 1 Shift algorithm (nstage = 1000) 0.9 Method 1 (nstage = 1000) Method 1 (nstage = 2000) 0.8 0.7 P 0.6 0.5 0.4 0.3 0.2 0.1 0 1 1.5 2 2.5 3 3.5 4 4.5 5 num of multiextr. fun. Рис. 5.5. Зависимость вероятности нахождения минимума целевой функции от количества многоэкстремальных функций среди набора {𝑓1 , . . . , 𝑓𝑛 } (остальные функции вида (5.1)) для метода 1 и метода, использующего алгоритм сдвига. Целевая функция вида (1.3). Параметр 𝑚𝑠𝑡𝑒𝑝 = 100. Так как методы решения из третьей главы отличаются только способом нахожде ния отображения 𝜙, то они будут иметь одинаковые результаты. Поэтому в качестве сравнения метода 1 с методами из третьей главы на рис. 5.5 отображены результаты для метода, использующего алгоритм сдвига. Добавление многоэксремальных функций 𝑓𝑖 значительно усложняет поведение це левой функции, что сказывается на точности вычисления минимума. Для методов де терминированного поиска оптимального отображения, как и для методов, использую 26

щих случайный поиск для нахождения оптимального отображения, вероятность отыс кания минимума уменьшается с увеличением количества многоэкстремальных функций в наборе {𝑓1 , . . . , 𝑓𝑛 }. Таблица 5.2. Вероятность нахождения минимума целевой функции вида (1.3) с помо щью метода 1 при разных значениях параметра 𝑚𝑠𝑡𝑒𝑝 случайного поиска и условии, что 𝑛𝑠𝑡𝑎𝑔𝑒 · 𝑚𝑠𝑡𝑒𝑝 = 100000. 𝑛𝑚𝑢𝑙𝑡 — количество многоэкстремальных функций среди 𝑓𝑖 (𝑥) из ра боты [4], 𝑛 − 𝑛𝑚𝑢𝑙𝑡 — количество функций 𝑓𝑖 (𝑥) вида (5.1). 𝑛𝑚𝑢𝑙𝑡 𝑚𝑠𝑡𝑒𝑝 = 100 𝑚𝑠𝑡𝑒𝑝 = 1 1 0, 64 0, 67 2 0, 39 0, 45 3 0, 11 0, 31 4 0, 14 0, 19 5 0, 14 0, 14 Для набора {𝑓1 , . . . , 𝑓𝑛 }, в котором часть функций имеют сложный многоэкстре мальный характер, также сравнивались результаты для разного количества шагов в случайном поиске: 𝑚𝑠𝑡𝑒𝑝 = 1 и 𝑚𝑠𝑡𝑒𝑝 = 100. В таблице 5.2 представлены полученные вероятности нахождения минимума целевой функции для разного количества много экстремальных функций. Данные результаты для 𝑚𝑠𝑡𝑒𝑝 = 1 и 𝑚𝑠𝑡𝑒𝑝 = 100 различаются уже существеннее, чем в случае (5.1), когда все 𝑓𝑖 имели вид (5.1). Таким образом, если функции 𝑓𝑖 имеют сложное представление, то лучше использовать случайный поиск с параметром 𝑚𝑠𝑡𝑒𝑝 = 1. 27

5.2. Случай несовпадения количества функций и количества значений дискретных величин В этом разделе рассмотрим общий случай, когда 𝑚 6 𝑛. Так как первый метод из всех способов четвёртой главы оказался более точным, то покажем некоторые резуль таты, полученные с его использованием. В результатах этого раздела использовалась размерность аргумента 𝑥[1 : 𝑑] 𝑑 = 2. Количество функций 𝑓𝑖 бралось равным 𝑛 = 5, 𝑛 = 9 и 𝑛 = 13, а количество значений 𝑔[𝑗] — от 1 до 𝑛, то есть 1 6 𝑚 6 𝑛. Функции 𝑓𝑖 рассматривались вида (5.1). На графике (рис. 5.6) представлена зависимость вероятности нахождения миниму ма целевой функции от 𝑚, полученные для первого метода четвёртой главы. Результаты получены для 𝑛 = 5, 𝑛 = 9 и 𝑛 = 13, целевой функции вида (1.3). Для всех 𝑚 и 𝑛 ко личество шагов в случайном поиске бралось 𝑚𝑠𝑡𝑒𝑝 = 1, а 𝑛𝑠𝑡𝑎𝑔𝑒 = 100000. В таблице 5.3 представлены аналогичные результаты для целевой функции вида (1.4). У полученных результатов для всех трёх значений 𝑛 и для целевых функций вида (1.3) и (1.4) наблюдается увеличение вероятности нахождения минимума при крайних значениях 𝑚, то есть при 𝑚 близких к 1 и к 𝑛. При 𝑚 ≈ 𝑛 2 вероятность принима ет наименьшее значение. Такое поведение некоторым образом может быть связано с количеством монотонных отображений. Так как их количество равно 𝑚(𝑛 − 𝑚) и их максимальное количество достигается при 𝑚 = 𝑛 2 ([3]). Если рассматривать получен ные вероятности относительно среднего значения 𝑚, то в половине, где 𝑚 6 𝑛 , 2 они оказываются больше, чем при 𝑚 > 𝑛2 . Это можно объяснить тем, что при уменьшении 𝑚 уменьшается число всех возможных отображений 𝜙, число которых 𝑛!/(𝑛 − 𝑚)!. При уменьшении 𝑚 также уменьшается размерность 𝑦 — дополнительного аргумента, то есть уменьшается размерность общей задачи. Таким образом, случайному поиску легче найти оптимальное отображение. Методы с точным нахождением оптимального отображения 𝜙 на каждом шаге случайного поиска при аналогичных параметрах с заданной точностью 0, 01 решают задачу с вероятностью 1. Однако здесь изменение параметра 𝑚 влияет не на точность, а на скорость работы алгоритма. Так как для алгоритма сдвига из работы [3] при уменьшении 𝑚 до 𝑛 2 количество монотонных отображений увеличивается, то будет уве личиваться и время поиска минимума. При дальнейшем уменьшении 𝑚 до 1 количество 28

монотонных отображений, по которым необходимо делать перебор, будет уменьшаться, соответственно время работы алгоритма тоже будет уменьшаться. 1 n = 13 n=9 n=5 0.9 0.8 0.7 P 0.6 0.5 0.4 0.3 0.2 0.1 0 1 2 3 4 5 6 7 m 8 9 10 11 12 13 Рис. 5.6. Зависимость вероятности нахождения минимума целевой функции вида (1.3) от 𝑚 для метода 1. Параметры случайного поиска: 𝑚𝑠𝑡𝑒𝑝 = 1 и 𝑛𝑠𝑡𝑎𝑔𝑒 = 100000. Таблица 5.3. Вероятность нахождения минимума целевой функции вида (1.4) с помощью метода 1 при разных значениях параметра 𝑚 и 𝑛 для параметров случайного поиска: 𝑚𝑠𝑡𝑒𝑝 = 1 и 𝑛𝑠𝑡𝑎𝑔𝑒 = 100000. 𝑚 @ 1 2 3 4 5 6 7 8 9 10 11 12 13 5 0, 92 0, 78 0, 72 0, 77 0, 97 — — — — — — — — 9 0, 88 0, 70 0, 24 0, 15 0, 09 0, 16 0, 23 0, 42 0.84 — — — — 13 0, 90 0, 54 0, 21 0, 09 0, 02 0, 01 0, 01 0, 01 0, 01 0, 01 0, 04 0, 14 0, 53 @ 𝑛 @ @ @ 29

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

Литература 1. Сушков Ю. А. Об одном способе организации случайного поиска // Исследование операций и статистическое моделирование. — Л : Издательство Ленинградского го сударственного университета, 1972. — Т. 1. — 180-185 с. 2. Сушков Ю. А. Метод, алгоритм и программа случайного поиска для определения оптимальных значений функции цели. — Л. : ВНИИТМ, 1969. 3. Сушков Ю. А. Структурно управляемые системы : дис. на соискание уч. степ. д-ра физ.-мат. наук : 05.13.18 / Ю. А. Сушков ; С.-Петербург. гос. ун-т. — Санкт-Петер бург, 2000. — 227 с. 4. Кушербаева В. Т. Теоретическое и статистическое исследование методов принятия решений с использованием алгоритма случайного поиска : дис. на соискание уч. степ. канд. физ.-мат. наук : 05.13.18 / В. Т. Кушербаева ; С.-Петербург. гос. ун-т. — Санкт-Петербург, 2012. — 135 с. 5. Абакаров А. С., Сушков Ю. А. Адаптация случайного поиска с использованием ло гистической кривой. — СПб. : СПбГУ, 2005. — 67-75 с. 6. Статистическое исследование алгоритма случайного поиска : Отчет / С.-Петербург. гос. ун-т. ; исполн.: В. Т. Кушербаева, Ю. А. Сушков. — Санкт-Петербург : 2007. — 16 с. 7. Романовский И. В. Дискретный анализ: Учебное пособие для студентов, специализи рующихся по прикладной математике и информатике. — 4-е изд. — СПб. : Невский Диалект; БХВ-Петербург, 2008. — 336 с. 8. Комбинаторные алгоритмы : Учебное пособие / Новосиб. гос. ун-т. ; исполн.: Т. И. Фе доряева. — Новосибирск : Новосиб. гос. ун-т., 2011. — 118 с. 31

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв