Случайный поиск

Случайный поиск (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