Метод наименьшей стоимости

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

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

Для инвестиций, показанных в табл. 8.3, алгоритм наименьшей стоимости начинает с добавления к решению позиции E со стоимостью 23 миллиона долларов. Затем он выбирает позицию D, стоящую 27 миллионов, и затем позицию C со стоимостью 30 миллионов. В этой точке алгоритм уже потратил 80 миллионов из 100 возможных, поэтому больше он не может выбрать ни одной позиции.

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

Структура программы, реализующей эвристику наименьшей стоимости, почти идентична структуре программы для эвристики восхождения на холм. Единственное различие между ними заключается в выборе следующей позиции для добавления к решению. Эвристика наименьшей стоимости выбирает позицию с минимальной ценой; метод восхождения на холм выбирает позицию с максимальной прибылью. Так как эти два метода очень похожи, они выполняются за одинаковое время. Если позиции упорядочены соответствующим образом, то оба алгоритма выполняются за время порядка O(N). Если позиции расположены случайным образом, то оба выполняются за время порядка O(N²).

 

========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

 

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

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