Последовательное приближение

Еще одна стратегия заключается в том, чтобы начать со случайного решения и затем делать последовательные приближения (incremental improvements). Начав со случайно выбранного решения, программа делает случайный выбор. Если новое решение лучше предыдущего, программа закрепляет изменения и продолжает проверку других случайных изменений. Если изменение не улучшает решение, программа отбрасывает его и делает новую попытку.

Для задачи формирования портфеля особенно просто порождать случайные изменения. Программа просто выбирает случайную позицию из пробного решения, и удаляет ее из текущего решения. Она затем снова добавляет случайные позиции в решение до тех пор, пока они помещаются. Если удаленная позиция имела очень высокую стоимость, то на ее место программа может поместить несколько позиций.

Момент остановки

Есть несколько хороших способов определить момент, когда следует прекратить случайные изменения. Для проблемы с N позициями, можно выполнить N или N² случайных изменений, перед тем, как остановиться.

 

=====206-208

 

В программе Heur этот подход реализован в процедуре MakeChangesFixed. Она выполняет определенное число случайных изменений с рядом случайных пробных решений:

 

Public Sub MakeChangesFixed(K As Integer, num_trials As Integer, num_changes As Integer)

Dim trial As Integer

Dim change As Integer

Dim i As Integer

Dim removal As Integer

 

For trial = 1 To num_trials

   ' Найти случайное пробное решение и использовать его

   ' в качестве начальной точки.

   Do While AddToSolution()

      ' All the work is done by AddToSolution.

   Loop

 

   ' Начать с этого пробного решения.

   trial_profit = test_profit

   trial_cost = test_cost

   For i = 1 To NumItems

      trial_solution(i) = test_solution(i)

   Next i

 

   For change = 1 To num_changes

      ' Удалить K случайных позиций.

      For removal = 1 To K

          RemoveFromSolution

      Next removal

 

      ' Добавить максимально возможное

      ' число позиций.

      Do While AddToSolution()

          ' All the work is done by AddToSolution.

      Loop

 

      ' Если это улучшает пробное решение, сохранить его.

      ' Иначе вернуть прежнее значение пробного решения.

      If test_profit > trial_profit Then

          ' Сохранить изменения.

          trial_profit = test_profit

          trial_cost = test_cost

          For i = 1 To NumItems

              trial_solution(i) = test_solution(i)

          Next i

      Else

          ' Сбросить пробное решение.

          test_profit = trial_profit

          test_cost = trial_cost

          For i = 1 To NumItems

              test_solution(i) = trial_solution(i)

          Next i

      End If

   Next change

 

   ' Если пробное решение лучше предыдущего

   ' наилучшего решения, сохранить его.

   If trial_profit > best_profit Then

      best_profit = trial_profit

      best_cost = trial_cost

      For i = 1 To NumItems

          best_solution(i) = trial_solution(i)

      Next i

   End If

 

   ' Сбросить пробное решение для

   ' следующей попытки.

   test_profit = 0

   test_cost = 0

   For i = 1 To NumItems

      test_solution(i) = False

   Next i

Next trial

End Sub

 

Private Sub RemoveFromSolution()

Dim num_in_solution As Integer

Dim j As Integer

Dim selection As Integer

 

' Определить число позиций в решении.

num_in_solution = 0

For j = 1 To NumItems

   If test_solution(j) Then num_in_solution = num_in_solution + 1

Next j

If num_in_solution < 1 Then Exit Sub

   

' Выбрать случайную позицию.

selection = Int((num_in_solution) * Rnd + 1)

   

' Найти случайно выбранную позицию.

For j = 1 To NumItems

   If test_solution(j) Then

      selection = selection - 1

      If selection < 1 Then Exit For

   End If

Next j

 

' Удалить позицию из решения.

test_profit = test_profit - Items(j).Profit

test_cost = test_cost - Items(j).Cost

test_solution(j) = False

End Sub

 

 

======209-210

 

Другая стратегия заключается в том, чтобы вносить изменения до тех пор, пока несколько последовательных изменений не приносят улучшений. Для задачи с N позициями, программа может вносить изменения до тех пор, пока в течение N изменений подряд улучшений не будет.

Эта стратегия реализована в подпрограмме MakeChangesNoChange программы Heur. Она повторяет попытки до тех пор, пока определенное число последовательных попыток не даст никаких улучшений. Для каждой попытки она вносит случайные изменения в пробное решение до тех пор, пока после определенного числа изменений не наступит никаких улучшений.

 

Public Sub MakeChangesNoChange(K As Integer, _

max_bad_trials As Integer, max_non_changes As Integer)

Dim i As Integer

Dim removal As Integer

Dim bad_trials As Integer    ' Неэффективных попыток подряд.

Dim non_changes As Integer   ' Неэффективных изменений подряд.

 

' Повторять попытки, пока не встретится max_bad_trials

' попыток подряд без улучшений.

bad_trials = 0

Do

   ' Выбрать случайное пробное решение для

   ' использования в качестве начальной точки.

   Do While AddToSolution()

      ' All the work is done by AddToSolution.

   Loop

 

   ' Начать с этого пробного решения.

   trial_profit = test_profit

   trial_cost = test_cost

   For i = 1 To NumItems

      trial_solution(i) = test_solution(i)

   Next i

 

   ' Повторять, пока max_non_changes изменений

   ' подряд не даст улучшений.

   non_changes = 0

   Do While non_changes < max_non_changes

      ' Удалить K случайных позиций.

      For removal = 1 To K

          RemoveFromSolution

      Next removal

 

      ' Вернуть максимально возможное число позиций.

      Do While AddToSolution()

          ' All the work is done by

          ' AddToSolution.

      Loop

 

      ' Если это улучшает пробное значение, сохранить его.

      ' Иначе вернуть прежнее значение пробного решения.

      If test_profit > trial_profit Then

          ' Сохранить улучшение.

          trial_profit = test_profit

          trial_cost = test_cost

          For i = 1 To NumItems

              trial_solution(i) = test_solution(i)

          Next i

          non_changes = 0 ' This was a good change.

      Else

          ' Reset the trial.

          test_profit = trial_profit

          test_cost = trial_cost

          For i = 1 To NumItems

              test_solution(i) = trial_solution(i)

          Next i

          non_changes = non_changes + 1 ' Плохое изменение.

      End If

   Loop ' Продолжить проверку случайных изменений.

 

   ' Если эта попытка лучше, чем предыдущее наилучшее

   ' решение, сохранить его.

   If trial_profit > best_profit Then

      best_profit = trial_profit

      best_cost = trial_cost

      For i = 1 To NumItems

      best_solution(i) = trial_solution(i)

      Next i

      bad_trials = 0   ' Хорошая попытка.

   Else

      bad_trials = bad_trials + 1    ' Плохая попытка.

   End If

 

   ' Сбросить тестовое решение для следующей попытки.

   test_profit = 0

   test_cost = 0

   For i = 1 To NumItems

      test_solution(i) = False

   Next i

Loop While bad_trials < max_bad_trials

End Sub

 

Локальные оптимумы

Если программа заменяет случайно выбранную позицию в пробном решении, то может встретиться решение, которое она не может улучшить, но которое при этом не будет наилучшим из возможных решений. Например, рассмотрим список инвестиций, приведенный в табл. 8.5.

Предположим, что алгоритм случайно выбрал позиции A и B в качестве начального решения. Его стоимость будет равно 90 миллионам долларов, и оно принесет 17 миллионов прибыли.

Если программа удалит позиции A и B, то стоимость решения будет все еще настолько велика, что программа сможет добавить всего лишь одну позицию к решению. Так как наибольшую прибыль приносят позиции A и B, то замена их другими позициями уменьшит суммарную прибыль. Случайное удаление одной позиции из этого решения никогда не приведет к улучшению решения.

Наилучшее решение содержит позиции C, D и E. Его полная стоимость равно 98 миллионам долларов и суммарная прибыль составляет 18 миллионов долларов. Чтобы найти это решение, алгоритму бы понадобилось удалить из решения сразу обе позиции A и B и затем добавить на их место новые позиции.

Решения такого типа, для которых небольшие изменения решения не могут улучшить его, называются локальным оптимумом (local optimum). Можно использовать два способа для того, чтобы программа не застревала в локальном оптимуме, и могла найти глобальный оптимум (global optimum).

 

@Таблица 8.5. Возможные инвестиции

 

=============213

 

Во‑первых, можно изменить программу так, чтобы она удаляла более одной позиции во время случайных изменений. В этом примере, программа могла бы найти правильное решение, если бы она одновременно удаляла бы по две случайно выбранных позиции. Тем не менее, для задач большего размера, удаления двух позиций может быть недостаточно. Программе может понадобиться удалять три, четыре, или больше позиций.

Второй, более простой способ заключается в том, чтобы делать больше попыток, начиная с разных начальных решений. Некоторые из начальных решений будут приводить к локальным оптимумам, но одно из них позволит достичь глобального оптимума.

Программа Heur демонстрирует три стратегии последовательных приближений. При выборе метода Fixed 1 (Фиксированный 1) делается N попыток. Во время каждой попытки выбирается случайно решение, которое программа затем пытается улучшить за 2 * N попыток, случайно удаляя по одной позиции.

При выборе эвристики Fixed 2 (Фиксированный 2)делается всего одна попытка. При этом программа выбирает случайное решение и пытается улучшить его, случайным образом удаляя по одной позиции до тех пор, пока в течение N последовательных изменений не будет никаких улучшений.

При выборе эвристики No Changes 1 (Без изменений 1) программа выполняет попытки до тех пор, пока после N последовательных попыток не будет никаких улучшений. Во время каждой попытки программа выбирает случайное решение и затем пытается улучшить его, случайным образом удаляя по одной позиции до тех пор, пока в течение N последовательных изменений не будет никаких улучшений.

При выборе эвристики No Changes 2 (Без изменений 2)делается одна попытка. При этом программа выбирает случайное решение и пытается улучшить его, случайным образом удаляя по две позиции до тех пор, пока в течение N последовательных изменений не будет никаких улучшений.

Названия эвристик и их описания приведены в табл. 8.6.

Алгоритм «отжига»

Метод отжига (simulated annealing) ведет свое начало из термодинамики. При отжиге металла он нагревается до высокой температуры. Молекулы в нагретом металле совершают быстрые колебания, а при медленном остывании они начинают располагаться упорядоченно, образуя кристаллы. При этом молекулы постепенно переходят в состояние с минимальной энергией.

 

@Таблица 8.6. Стратегии последовательных приближений

 

===========214

 

При медленном остывании металла, соседние кристаллы сливаются друг с другом. Молекулы в одном из кристаллов покидают состояние с минимальной энергией и принимают порядок молекул в другом кристалле. Энергия получившегося кристалла большего размера будет меньше, чем сумма энергий двух исходных кристаллов. Если охлаждение происходит достаточно медленно, то кристаллы становятся очень большими. Окончательное распределение молекул представляет состояние с очень низкой энергией, и металл при этом будет очень твердым.

Начиная с состояния с высокой энергией, молекулы в конце концов достигают состояния с очень низкой энергией. На пути к конечному положению, они проходят множество локальных минимумов энергии. Каждое сочетание кристаллов образует локальный минимум. Кристаллы могут объединяться друг с другом только за счет временного повышения энергии системы, чтобы затем перейти к состоянию с меньшей энергией.

Метод отжига использует аналогичный подход для поиска наилучшего решения задачи. Во время поиска решения программой, она может застрять в локальном оптимуме. Чтобы избежать этого, программа время от времени вносит в решение случайные изменения, даже если очередное изменение и не приводит к мгновенному улучшению результата. Это может помочь программе выйти из локального оптимума и отыскать лучшее решение. Если это изменение не ведет к лучшему решению, то вероятно, через некоторое время программа его отбросит.

Чтобы эти изменения не возникали постоянно, алгоритм изменяет вероятность возникновения случайных изменений со временем. Вероятность P возникновения одного из подобных изменений определяется формулой P = 1 / Exp(E / (k * T)), где E — увеличение «энергии» системы, k — некоторая постоянная, и T — переменная, соответствующая «температуре».

Вначале температура должна быть высокой, поэтому и вероятность изменений P = 1 / Exp(E / (k * T)) также достаточно велика. Иначе случайные изменения могли бы никогда не возникнуть. С течением времени значение переменной T постепенно снижается, и вероятность случайных изменений также уменьшается. После того, как модель дойдет до точки, в которой она никакие изменения не смогут улучшить решение, и температура T станет достаточно низкой, чтобы вероятность случайных изменений была мала, алгоритм заканчивает работу.

Для задачи о формирования портфеля, в качестве прибавки «энергии» E выступает уменьшение прибыли решения. Например, при удалении позиции, которая дает прибыль 10 миллионов, и замене ее на позицию, которая приносит 7 миллионов прибыли, энергия, добавленная к системе, будет равна 3.

Заметьте, что если энергия велика, то вероятность изменений P = 1 / Exp(E / (k * T)) мала, поэтому вероятность больших изменений ниже.

Алгоритм отжига в программе Heur устанавливает значение постоянной k равным разнице между наибольшей и наименьшей прибылью возможных инвестиций. Начальная температура T задается равной 0,75. После выполнения определенного числа случайных изменений, температура T уменьшается умножением на постоянную 0,95.

 

=========215

 

 

Public Sub AnnealTrial(K As Integer, max_non_changes As Integer, _

max_back_slips As Integer)

Const TFACTOR = 0.95

 

Dim i As Integer

Dim non_changes As Integer

Dim t As Double

Dim max_profit As Integer

Dim min_profit As Integer

Dim doit As Boolean

Dim back_slips As Integer

 

' Найти позицию с минимальной и максимальной прибылью.

max_profit = Items(1).Profit

min_profit = max_profit

For i = 2 To NumItems

   If max_profit < Items(i).Profit Then max_profit = Items(i).Profit

   If min_profit > Items(i).Profit Then min_profit = Items(i).Profit

Next i

 

t = 0.75 * (max_profit - min_profit)

back_slips = 0

   

' Выбрать случайное пробное решение

' в качестве начальной точки.

Do While AddToSolution()

   ' Вся работа выполняется в процедуре AddToSolution.

Loop

 

' Использовать в качестве пробного решения.

best_profit = test_profit

best_cost = test_cost

For i = 1 To NumItems

   best_solution(i) = test_solution(i)

Next i

 

' Повторять, пока в течение max_non_changes изменений

' подряд не будет улучшений.

non_changes = 0

Do While non_changes < max_non_changes

   ' Удалить случайную позицию.

   For i = 1 To K

      RemoveFromSolution

   Next i

       

   ' Добавить максимально возможное число позиций.

   Do While AddToSolution()

      ' Вся работа выполняется в процедуре AddToSolution.

   Loop

   

   ' Если изменение улучшает пробное решение, сохранить его.

   ' Иначе вернуть прежнее значение решения.

   If test_profit > best_profit Then

      doit = True

   ElseIf test_profit < best_profit Then

      doit = (Rnd < Exp((test_profit - best_profit) / t))

      back_slips = back_slips + 1

      If back_slips > max_back_slips Then

          back_slips = 0

      t = t * TFACTOR

      End If

   Else

      doit = False

   End If

   If doit Then

      ' Сохранить улучшение.

      best_profit = test_profit

      best_cost = test_cost

      For i = 1 To NumItems

          best_solution(i) = test_solution(i)

      Next i

      non_changes = 0  ' Хорошее изменение.

   Else

      ' Reset the trial.

      test_profit = best_profit

      test_cost = best_cost

      For i = 1 To NumItems

          test_solution(i) = best_solution(i)

      Next i

      non_changes = non_changes + 1  ' Плохое изменение.

   End If

Loop  ' Продолжить проверку случайных изменений.

End Sub

 

Сравнение эвристик

Различные эвристики по‑разному ведут себя в различных задачах. Для задачи о формировании портфеля, эвристика сбалансированной прибыли работает достаточно хорошо, учитывая ее простоту. Стратегии последовательного приближения обычно дают сравнимые результаты, но для больших задач их выполнение занимает намного больше времени. Для других задач наилучшей может быть какая‑либо другая эвристика, в том числе из тех, которые не обсуждались в этой главе.

 

========216-217

 

Эвристические методы обычно выполняются быстрее, чем метод ветвей и границ. Некоторые из них, например методы восхождения на холм, наименьшей стоимости и сбалансированной прибыли, выполняются очень быстро, так как они рассматривают только одно возможное решение. Они выполняются настолько быстро, что имеет смысл выполнить их все по очереди, и затем выбрать наилучшее из трех полученных решений. Это не гарантирует того, что это решение будет наилучшим, но дает некоторую уверенность, что оно окажется достаточно хорошим.

Другие сложные задачи

Существует множество очень сложных задач, большинство из которых не имеет решений с полиномиальной вычислительной сложностью. Другими словами, не существует алгоритмов, которые решали бы эти задачи за время порядка O(N^C) для любых постоянных C, даже за O(N¹⁰⁰⁰).

В следующих разделах кратко описаны некоторые из этих задач. В них также показано, почему они являются сложными в общем случае и насколько большим может оказаться дерево решений задачи. Вы можете попробовать применить метод ветвей и границ или эвристики для решения некоторых из этих задач.

Задача о выполнимости

Если имеется логическое утверждение, например “(A And Not B) Or C”, то существуют ли значения переменных A, B и C, при которых это утверждение истинно? В данном примере легко увидеть, что утверждение истинно, если A = true, B = false и C = false. Для более сложных утверждений, содержащих сотни переменных, бывает достаточно сложно определить, может ли быть утверждение истинным.

При помощи метода, похожего на тот, который использовался при решении задачи о формировании портфеля, можно простроить дерево решений для задачи о выполнимости (satisfiability problem). Каждая ветвь дерева будет соответствовать решению о присвоении переменной значения true или false. Например, левая ветвь, выходящая из корня, соответствует значению первой переменной true.

Если в логическом выражении N переменных, то дерево решений представляет собой двоичное дерево высотой N + 1. Это дерево имеет 2^N листьев, каждый из которых соответствует разной комбинации значений переменных.

В задаче о формировании портфеля можно было использовать метод ветвей и границ для того, чтобы избежать поиска в большей части дерева. В задаче о выполнимости выражение либо истинно, либо ложно. При этом нельзя получить частичное решение, которое можно использовать для отсечения путей в дереве.

Нельзя также использовать эвристики для поиска приблизительного решения для задачи о выполнимости. Любое значение переменных, полученное при помощи эвристики, будет делать выражение истинным или ложным. В математической логике не существует такого понятия, как приближенное решение.

Из‑за неприменимости эвристик и меньшей эффективности метода ветвей и границ, задача о выполнимости обычно является очень сложной и решается только в случае небольшого размера задачи.

Задача о разбиении

Если задано множество элементов со значениями X₁, X₂, … , X_N, то существует ли способ разбить его на два подмножества, так чтобы сумма значений всех элементов в каждом из подмножеств была одинаковой? Например, если элементы имеют значения 3, 4, 5 и 6, то их можно разбить на два подмножества {3, 6} и {4, 5}, сумма значений элементов в каждом из которых равна 9.

Чтобы смоделировать эту задачу при помощи дерева, предположим, что ветвям соответствует помещение элемента в одно из двух подмножеств. Левая ветвь, выходящая из корневого узла, соответствует помещению первого элемента в первое подмножество, а правая ветвь — во второе подмножество.

Если всего существует N элементов, то дерево решение будет представлять собой двоичное дерево высотой N + 1. Оно будет содержать 2^N листьев и 2^N+1 узлов. Каждый лист соответствует одному из вариантов размещения элементов в двух подмножествах.

При решении этой задачи можно применить метод ветвей и границ. При рассмотрении частичных решений задачи можно отслеживать, насколько различаются суммарные значения элементов в двух подмножествах. Если в какой‑то момент суммарное значение элементов для одного из подмножеств настолько меньше, чем для другого, что добавление всех оставшихся элементов не позволяет изменить это соотношение, то нет смысла продолжать движение вниз по этой ветви.

Так же, как и в случае с задачей о выполнимости, для задачи о разбиении (partition problem) нельзя получить приближенное решение. В результате всегда должно получиться два подмножества, суммарное значение элементов в которых будет или не будет одинаковым. Это означает, что для решения этой задачи неприменимы эвристики, которые использовались для решения задачи о формировании портфеля.

Задачу о разбиении можно обобщить следующим образом: если имеется множество элементов со значениями X₁, X₂, … , X_N, как разбить его на два подмножества, чтобы разница суммы значений элементов в двух подмножествах была минимальной?

Получить точное решение этой задачи труднее, чем для исходной задачи о разбиении. Если бы существовал простой способ решения задачи в общем случае, то его можно было бы использовать для решения исходной задачи. В этом случае можно было бы просто найти два подмножества, удовлетворяющих условиям, а затем проверить, совпадают ли суммы значений элементов в них.

Для решения общего случая задачи можно использовать метод ветвей и границ, примерно так же, как он использовался для решения частного случая задачи, чтобы избежать поиска по всему дереву. Можно также использовать при этом эвристический подход. Например, можно проверять элементы в порядке убывания их значения, помещая очередной элемент в подмножество с меньшей суммой значений элементов. Также можно было бы легко использовать случайный поиск, метод последовательных приближений, или метод отжига для поиска приближенного решения этого общего случая задачи.