selection = Int((num_left) * Rnd + 1)
' Найти случайно выбранную позицию.
For j = 1 To NumItems
If (Not test_solution(j)) And _
(test_cost + Items(j).Cost <= ToSpend) _
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) = True
AddToSolution = True
End Function
Еще одна стратегия заключается в том, чтобы начать со случайного решения и затем делать последовательные приближения (incremental improvements). Начав со случайно выбранного решения, программа делает случайный выбор. Если новое решение лучше предыдущего, программа закрепляет изменения и продолжает проверку других случайных изменений. Если изменение не улучшает решение, программа отбрасывает его и делает новую попытку.
Для задачи формирования портфеля особенно просто порождать случайные изменения. Программа просто выбирает случайную позицию из пробного решения, и удаляет ее из текущего решения. Она затем снова добавляет случайные позиции в решение до тех пор, пока они помещаются. Если удаленная позиция имела очень высокую стоимость, то на ее место программа может поместить несколько позиций.
Есть несколько хороших способов определить момент, когда следует прекратить случайные изменения. Для проблемы с N позициями, можно выполнить N или N2 случайных изменений, перед тем, как остановиться.
=====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
При медленном остывании металла, соседние кристаллы сливаются друг с другом. Молекулы в одном из кристаллов покидают состояние с минимальной энергией и принимают порядок молекул в другом кристалле. Энергия получившегося кристалла большего размера будет меньше, чем сумма энергий двух исходных кристаллов. Если охлаждение происходит достаточно медленно, то кристаллы становятся очень большими. Окончательное распределение молекул представляет состояние с очень низкой энергией, и металл при этом будет очень твердым.