Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

=======201

В этом разделе обсуждаются эвристики, которые полезны при решении многих сложных задач. Программа Heur демонстрирует каждую из эвристик. Она также позволяет сравнить результаты, полученные при помощи эвристик и методов полного перебора и ветвей и границ. Введите значения минимальной и максимальной стоимости и дохода, а также число позиций и полную стоимость портфеля в соответствующих полях области Parameters (Параметры), чтобы задать параметры создаваемых данных. Затем выберите алгоритмы, которые вы хотите протестировать, и нажмите на кнопку Go. Программа выведет полную стоимость и доход для наилучшего решения, найденного при помощи каждого из алгоритмов. Она также сортирует решения по максимальному полученному доходу и выводит время выполнения для каждого из алгоритмов. Используйте метод ветвей и границ только для небольших задач, а метод полного перебора только для задач еще меньшего объема.

На рис. 8.8 показано окно программы Heur после решения задачи формирования портфеля для 20 позиций. Эвристики Fixed1, Fixed2 и No Changes 1, которые будут вскоре описаны, дали наилучшие эвристические решения. Заметьте, что эти решения немного хуже, чем точные решения, которые получены при использовании метода ветвей и границ.

Восхождение на холм

Эвристика восхождения на холм (hill‑climbing) вносит изменения в текущее решение, чтобы максимально приблизить его к цели. Этот процесс называется восхождением на холм, так как он похож на то, как заблудившийся путешественник пытается ночью добраться до вершины горы. Даже если уже слишком темно, чтобы еще можно было разглядеть что‑то вдали, путешественник может попытаться добраться до вершины горы, постоянно двигаясь вверх.

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

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

@Рис. 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

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

    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

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33