В задаче о формировании портфеля, цель заключается в том, чтобы подобрать набор позиций, полная стоимость которых не превышает заданного предела, а общая цена максимальна. На каждом шаге эвристика восхождения на холм будет выбирать позицию, которая приносит наибольшую прибыль. При этом решение будет все лучше соответствовать цели — получению максимальной прибыли.
@Рис. 8.8. Программа Heur
========202
Вначале программа добавляет к решению позицию с максимальной прибылью. Затем она добавляет следующую позицию с максимальной прибылью, если при этом полная цена еще остается в допустимых пределах. Она продолжает добавлять позиции с максимальной прибылью до тех пор, пока не останется позиций, удовлетворяющих условиям.
Для списка инвестиций из табл. 8.3, программа вначале выбирает позицию A, так как она дает максимальную прибыль — 9 миллионов долларов. Затем программа выбирает следующую позицию C, которая дает прибыль 8 миллионов. В этот момент потрачены уже 93 миллиона из 100, и программа не может приобрести больше позиций. Решение, полученное при помощи эвристики, включает позиции A и C, имеет стоимость 93 миллиона, и приносит 17 миллионов прибыли.
@Таблица 8.3. Возможные инвестиции
Эвристика восхождения на холм заполняет портфель очень быстро. Если позиции изначально были отсортированы в порядке убывания приносимой прибыли, то сложность этого алгоритма порядка O(N). Программа просто перемещается по списку, добавляя каждую позицию, если под нее есть место. Даже если список не упорядочен, то это алгоритм со сложностью порядка O(N2). Это намного лучше, чем O(2N) шагов, которые требуются для полного перебора всех узлов в дереве. Для 20 позиций эта эвристика требует всего около 400 шагов, метод ветвей и границ — несколько тысяч, а полный перебор — более чем 2 миллиона.
Public Sub HillClimbing()
Dim i As Integer
Dim j As Integer
Dim big_value As Integer
Dim big_j As Integer
' Многократный обход списка и поиск следующей
' позиции, приносящей наибольшую прибыль,
' стоимость которой не превышает верхней границы.
For i = 1 To NumItems
big_value = 0
big_j = -1
For j = 1 To NumItems
' Проверить, не находится ли он уже
' в решении.
If (Not test_solution(j)) And _
(test_cost + Items(j).Cost <= ToSpend) And _
(big_value < Items(j).Profit)
Then
big_value = Items(j).Profit
big_j = j
End If
Next j
' Остановиться, если не найдена позиция,
' удовлетворяющая условиям.
If big_j < 0 Then Exit For
test_cost = test_cost + Items(big_j).Cost
test_solution(big_j) = True
test_profit = test_profit + Items(big_j).Profit
Next i
End Sub
Стратегия, которая в каком‑то смысле противоположна стратегии восхождения на холм, называется стратегией наименьшей стоимости (least‑cost). Вместо того чтобы на каждом шаге пытаться максимально приблизить решение к цели, можно попытаться уменьшить стоимость решения, насколько это возможно. В примере с формированием портфеля, на каждом шаге к решению добавляется позиция с минимальной стоимостью.
Эта стратегия пытается поместить в решение максимально возможное число позиций. Это будет неплохим решением, если все позиции имеют примерно одинаковую стоимость. Если дорогая позиция приносит большую прибыль, то эта стратегия может упустить эту возможность, давая не лучший из возможных результатов.
Для инвестиций, показанных в табл. 8.3, алгоритм наименьшей стоимости начинает с добавления к решению позиции E со стоимостью 23 миллиона долларов. Затем он выбирает позицию D, стоящую 27 миллионов, и затем позицию C со стоимостью 30 миллионов. В этой точке алгоритм уже потратил 80 миллионов из 100 возможных, поэтому больше он не может выбрать ни одной позиции.
Это решение имеет стоимость 80 миллионов и дает 18 миллионов прибыли. Это на миллион лучше, чем решение для эвристики восхождения на холм, но стратегия наименьшей стоимости не всегда дает лучшее решение, чем восхождение на холм. Какая из эвристик дает лучшие результаты, зависит от значений входных данных.
Структура программы, реализующей эвристику наименьшей стоимости, почти идентична структуре программы для эвристики восхождения на холм. Единственное различие между ними заключается в выборе следующей позиции для добавления к решению. Эвристика наименьшей стоимости выбирает позицию с минимальной ценой; метод восхождения на холм выбирает позицию с максимальной прибылью. Так как эти два метода очень похожи, они выполняются за одинаковое время. Если позиции упорядочены соответствующим образом, то оба алгоритма выполняются за время порядка O(N). Если позиции расположены случайным образом, то оба выполняются за время порядка O(N2).
========203-204
Так как код на языке Visual Basic для этих двух эвристик очень похож, то мы приводим только строки, в которых происходит выбор очередной позиции.
If (Not test_solution(j)) And _
(test_cost + Items(j).Cost <= ToSpend) And _
(small_cost > Items(j).Cost)
Then
small_cost = Items(j).Cost
small_j = j
End If
Стратегия восхождения на холм не учитывает стоимость добавляемых позиций. Она выбирает позиции с максимальной прибылью, даже если их стоимость велика. Стратегия наименьшей стоимости не учитывает приносимую позицией прибыль. Она выбирает позиции с низкой стоимостью, даже если они приносят мало прибыли.
Эвристика сбалансированной прибыли (balanced profit) сравнивает при выборе стоимость позиций и приносимую ими прибыль. На каждом шаге эвристика выбирает позицию с наибольшим отношением прибыль‑стоимость.
В табл. 8.4 приведены те же данные, что и в табл. 8.3, но в ней добавлена еще одна колонка с отношением прибыль‑стоимость. При этом подходе вначале выбирается позиция C, так как она имеет максимальное соотношение прибыль‑стоимость — 0,27. Затем к решению добавляется позиция D с отношением 0,26, и позиция B с отношением 0,20. В этой точке, будет потрачено 92 миллиона из 100 возможных, и в решение нельзя будет добавить больше ни одной позиции.
Решение будет иметь стоимость 92 миллиона и давать 22 миллиона прибыли. Это на 4 миллиона лучше, чем решение с наименьшей стоимостью и на 5 миллионов лучше, чем решение методом восхождения на холм. В этом случае, это будет также наилучшим возможным решением, и его также можно найти полным перебором или методом ветвей и границ. Метод сбалансированной прибыли тем не менее, является эвристическим, поэтому он не обязательно находит наилучшее возможное решение. Он часто находит лучшее решение, чем методы наименьшей стоимости и восхождения на холм, но это не обязательно так.
@Таблица 8.4. Возможные инвестиции с соотношением прибыль‑стоимость
=========205
Структура программы, реализующей эвристику сбалансированной прибыли, почти идентична структуре программ для восхождения на холм и наименьшей стоимости. Единственное отличие заключается в методе выбора следующей позиции, которая добавляется к решению:
If (Not test_solution(j)) And _
(test_cost + Items(j).Cost <= ToSpend) And _
(good_ratio < Items(j).Profit / CDbl(Items(j).Cost)) _
Then
good_ratio = Items(j).Profit / CDbl(Items(j).Cost)
good_j = j
End If
Случайный поиск (random search) выполняется в соответствии со своим названием. На каждом шаге алгоритм добавляет случайную позицию, которая удовлетворяет верхнему ограничению на суммарную стоимость позиций в портфеле. Этот метод поиска также называется методом Монте‑Карло (Monte Carlo search или Monte Carlo simulation).
Так как маловероятно, что случайно выбранное решение окажется наилучшим, необходимо многократно повторять этот поиск, чтобы получить приемлемый результат. Хотя может показаться, что вероятность нахождения хорошего решения при этом мала, этот метод иногда дает удивительно хорошие результаты. В зависимости от значений данных и числа проверенных случайных решений результат, полученный при помощи этой эвристики, часто оказывается лучше, чем в случае применения методов восхождения на холм или наименьшей стоимости.
Преимущество случайного поиска состоит также и в том, что этот метод легок в понимании и реализации. Иногда сложно представить, как реализовать решение задачи при помощи эвристик восхождения на холм, наименьшей стоимости, или сбалансированного дохода, но всегда просто выбирать решения случайным образом. Даже для очень сложных проблем, случайный поиск является простым эвристическим методом.
Подпрограмма RandomSearch в программе Heur использует функцию AddToSolution для добавления к решению случайной позиции. Эта функция возвращает значение True, если она не может найти позицию, которая удовлетворяет условиям, и False в другом случае. Подпрограмма RandomSearch вызывает функцию AddToSolution до тех пор, пока больше нельзя добавить ни одной позиции.
Public Sub RandomSearch()
Dim num_trials As Integer
Dim trial As Integer
Dim i As Integer
' Сделать несколько попыток и выбрать наилучший результат.
num_trials = NumItems ' Использовать N попыток.
For trial = 1 To num_trials
' Случайный выбор позиций, пока это возможно.
Do While AddToSolution()
' Всю работу выполняет функция AddToSolution.
Loop
' Определить, лучше ли это решение, чем предыдущее.
If test_profit > best_profit Then
best_profit = test_profit
best_cost = test_cost
For i = 1 To NumItems
best_solution(i) = test_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 Function AddToSolution() As Boolean
Dim num_left As Integer
Dim j As Integer
Dim selection As Integer
' Определить, сколько осталось позиций, которые
' удовлетворяют ограничению максимальной стоимости.
num_left = 0
For j = 1 To NumItems
If (Not test_solution(j)) And _
(test_cost + Items(j).Cost <= ToSpend) _
Then num_left = num_left + 1
Next j
' Остановиться, если нельзя найти новую позицию.
If num_left < 1 Then
AddToSolution = False
Exit Function
End If
' Выбрать случайную позицию.