Оптимизация занимает достаточно большую часть в жизни людей. Порой мы даже не задумываемся о том, что мы что-то оптимизируем. Так, к примеру, мы отправляемся в путешествие и нам необходимо собрать много вещей, а чемодан средних размеров. (Мы тоже имеем физические ограничения) Если мы пойдем на пляж, то взять шорты, очки и крем от загара будет значительно лучшим решением, если бы возьмем с собой зимнюю куртку, то есть опираясь на приоритет вещей мы делаем свой выбор, чтобы суммарная ценность груза была максимальной.
Делаем вывод, что оптимизация необходима нам для нахождения позитивного решения, оно может быть не самым лучшим, но точно будет хорошим.
Более строгим будет определение, что оптимизация – это инструмент, который находит оптимальное решение.
Математически «оптимизация» - представляет собой, нахождение MAX и MIN функции [1].
Наконец разобравшись с тем, что такое оптимизация и, что она делает.
Попробуем разобраться – «How does it work?!» (Как это работает?)
Представим на секунду, что наш чемодан превратился в корабль, а в котором множество отсеков, задача которого переправить товар в точку доставки (наша задача осталась неизменна – привести суммарную ценность к ее максимуму), целевой функцией будет сумма стоимости продукции. Теперь, нам понадобиться значительно больше времени для нахождения оптимального решения.
Взяв случайное решение, мы не сможем быть уверенны, что оно хоть сколько-нибудь будет приближенно к искомому экстремуму. Существует большое количество методов, которые помогут решить данную задачу [2]. Их такое количество, что их разделяют на классы.
Одним из них является метод имитации отжига (или просто метод отжига.), он входит в класс стохастических.(то-есть который может угадывать) Зачем же здесь вероятность? Ответим на это дальше. Но для начала приведем примеры прикладного применения глобальной оптимизации.
Где используем?
Существует множество применений методов глобальной оптимизации [3]. Используется для реконструкции изображений, глобальной маршрутизации, назначение задач и планирование, и многое другое.
К примеру, попробуем решить задачу коммивояжера двумя разными методами: «Венгерский метод» и «метод ветвей и границ». Данная статья посвящена сравнению двух этих алгоритмов. Эта задача представляет собой поиск самого выгодного маршрута, проходящего через указанные города.
Начнем с метода «ветвей и границ»:
Шаг 1: Построение исходной матрицы
Представим длины дорог соединяющих города:
|
City |
1 |
2 |
3 |
4 |
|
1 |
M |
5 |
11 |
9 |
|
2 |
10 |
M |
8 |
7 |
|
3 |
7 |
14 |
M |
8 |
|
4 |
12 |
6 |
15 |
M |
Шаг 2: Нахождение min по строкам
Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец [4].
|
City |
1 |
2 |
3 |
4 |
di |
|
1 |
М |
5 |
11 |
9 |
5 |
|
2 |
10 |
М |
8 |
7 |
7 |
|
3 |
7 |
14 |
М |
8 |
7 |
|
4 |
12 |
6 |
15 |
М |
6 |
Шаг 3: Редукция строк
Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).
|
City |
1 |
2 |
3 |
4 |
di |
|
1 |
M |
0 |
6 |
4 |
5 |
|
2 |
3 |
M |
1 |
0 |
7 |
|
3 |
0 |
7 |
M |
1 |
7 |
|
4 |
6 |
0 |
9 |
M |
6 |
Шаг 4: Нахождение min по столбцам
Теперь, находим минимальные значения в каждом столбце (dj)
|
City |
1 |
2 |
3 |
4 |
di |
|
1 |
M |
0 |
6 |
4 |
5 |
|
2 |
3 |
M |
1 |
0 |
7 |
|
3 |
0 |
7 |
M |
1 |
7 |
|
4 |
6 |
0 |
9 |
M |
6 |
|
dj |
0 |
0 |
1 |
0 |
|||||||||||||||||||||||| |
Шаг 5: Редукция столбцов
Вычитаем из каждого элемента матрицы соответствующее ему dj.
|
City |
1 |
2 |
3 |
4 |
di |
|
1 |
M |
0 |
5 |
4 |
5 |
|
2 |
3 |
M |
0 |
0 |
7 |
|
3 |
0 |
7 |
M |
1 |
7 |
|
4 |
6 |
0 |
8 |
M |
6 |
|
dj |
0 |
0 |
1 |
0 |
|||||||||||||||||||||||| |
Шаг 6: Вычисление оценок нулевых клеток
Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка [5]. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.
|
City |
1 |
2 |
3 |
4 |
|
1 |
M |
0 (4) |
5 |
4 |
|
2 |
3 |
M |
0 (5) |
0 (1) |
|
3 |
0 (4) |
7 |
M |
1 |
|
4 |
6 |
0 (6) |
8 |
M |
Шаг 7: Редукция матрицы
Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).
|
City |
1 |
2 |
3 |
4 |
|
1 |
M |
0 (4) |
5 |
4 |
|
2 |
3 |
M |
0 (5) |
M |
|
3 |
0 (4) |
7 |
M |
1 |
|
4 |
6 |
M |
8 |
M |
Шаг 8: Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9
Если мы еще не нашли все отрезки пути, то возвращаемся ко 2-му пункту и вновь ищем минимумы по строкам и столбцам, проводим их редукцию, считаем оценки нулевых клеток и т.д.
Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9.
Шаг 9: Вычисление итоговой длины пути и построение маршрута
Найдя все отрезки пути, остается только соединить их между собой и рассчитать общую длину пути (стоимость поездки по этому маршруту, затраченное время и т.д.) [6]. Длины дорог соединяющих города берем из самой первой таблицы с исходными данными. Общая длина пути: L = 30.
А теперь «венгерский метод», исходная матрица принимает вид:
|
M |
3 |
4 |
2 |
7 |
|
5 |
M |
8 |
4 |
3 |
|
2 |
3 |
M |
7 |
5 |
|
3 |
2 |
9 |
M |
1 |
|
1 |
2 |
3 |
5 |
M |
Шаг 1: Проводим редукцию матрицы по строкам. В новой матрице в каждой строке будет ка минимум 1 ноль.
|
М |
1 |
2 |
0 |
5 |
2 |
|
2 |
М |
5 |
1 |
0 |
3 |
|
0 |
1 |
М |
5 |
3 |
2 |
|
2 |
1 |
8 |
М |
0 |
1 |
|
0 |
1 |
2 |
4 |
М |
1 |
Теперь, по столбцам:
|
М |
0 |
0 |
0 |
5 |
|
2 |
М |
3 |
1 |
0 |
|
0 |
0 |
М |
5 |
3 |
|
2 |
0 |
6 |
М |
0 |
|
0 |
0 |
0 |
4 |
М |
|
0 |
1 |
2 |
0 |
0 |
После вычитания минимальных элементов получим полностью редуцированную матрицу [7].
Шаг 2: Методом проб и ошибок осуществим поиск допустимого решения, для которого все значения имеют нулевую стоимость.
|
M |
[-0-] |
[-0-] |
[0] |
5 |
|
2 |
M |
3 |
1 |
[0] |
|
[0] |
[-0-] |
M |
5 |
3 |
|
2 |
[0] |
6 |
M |
[-0-] |
|
[-0-] |
[-0-] |
[0] |
4 |
M |
Получим эквивалентную матрицу Сэ:
|
M |
0 |
0 |
0 |
5 |
|
2 |
M |
3 |
1 |
0 |
|
0 |
0 |
M |
5 |
3 |
|
2 |
0 |
6 |
M |
0 |
|
0 |
0 |
0 |
4 |
M |
Шаг 3: Методом проб и ошибок определяем матрицу назначения Х, которая позволит по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения [8].
|
M |
[-0-] |
[-0-] |
[0] |
5 |
|
2 |
M |
3 |
1 |
[0] |
|
[0] |
[-0-] |
M |
5 |
3 |
|
2 |
[0] |
6 |
M |
[-0-] |
|
[-0-] |
[-0-] |
[0] |
4 |
M |
Заключение
Ответ на вопрос, «Какой же из алгоритмов лучше?» достаточно прост и очевиден. Так как метод ветвей и границ является вариацией полного перебора, и для большого объема входных данных он слабо или абсолютно не подходит - вычисления будут не красивые и громоздкие. Для решения крупных задач больше подойдет венгерский метод в силу того, что он значительно сокращает вычисления и считается более точным.