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

Программа 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

При медленном остывании металла, соседние кристаллы сливаются друг с

другом. Молекулы в одном из кристаллов покидают состояние с минимальной

энергией и принимают порядок молекул в другом кристалле. Энергия

получившегося кристалла большего размера будет меньше, чем сумма энергий

двух исходных кристаллов. Если охлаждение происходит достаточно медленно,

то кристаллы становятся очень большими. Окончательное распределение молекул

представляет состояние с очень низкой энергией, и металл при этом будет

очень твердым.

Начиная с состояния с высокой энергией, молекулы в конце концов достигают

состояния с очень низкой энергией. На пути к конечному положению, они

проходят множество локальных минимумов энергии. Каждое сочетание кристаллов

образует локальный минимум. Кристаллы могут объединяться друг с другом

только за счет временного повышения энергии системы, чтобы затем перейти к

состоянию с меньшей энергией.

Метод отжига использует аналогичный подход для поиска наилучшего решения

задачи. Во время поиска решения программой, она может застрять в локальном

оптимуме. Чтобы избежать этого, программа время от времени вносит в решение

случайные изменения, даже если очередное изменение и не приводит к

мгновенному улучшению результата. Это может помочь программе выйти из

локального оптимума и отыскать лучшее решение. Если это изменение не ведет

к лучшему решению, то вероятно, через некоторое время программа его

отбросит.

Чтобы эти изменения не возникали постоянно, алгоритм изменяет вероятность

возникновения случайных изменений со временем. Вероятность P возникновения

одного из подобных изменений определяется формулой P = 1 / Exp(E / (k *

T)), где E — увеличение «энергии» системы, k — некоторая постоянная, и T —

переменная, соответствующая «температуре».

Вначале температура должна быть высокой, поэтому и вероятность изменений

P = 1 / Exp(E / (k * T)) также достаточно велика. Иначе случайные изменения

могли бы никогда не возникнуть. С течением времени значение переменной T

постепенно снижается, и вероятность случайных изменений также уменьшается.

После того, как модель дойдет до точки, в которой она никакие изменения не

смогут улучшить решение, и температура T станет достаточно низкой, чтобы

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

Для задачи о формирования портфеля, в качестве прибавки «энергии» E

выступает уменьшение прибыли решения. Например, при удалении позиции,

которая дает прибыль 10 миллионов, и замене ее на позицию, которая приносит

7 миллионов прибыли, энергия, добавленная к системе, будет равна 3.

Заметьте, что если энергия велика, то вероятность изменений P = 1 / Exp(E /

(k * T)) мала, поэтому вероятность больших изменений ниже.

Алгоритм отжига в программе Heur устанавливает значение постоянной k равным

разнице между наибольшей и наименьшей прибылью возможных инвестиций.

Начальная температура T задается равной 0,75. После выполнения

определенного числа случайных изменений, температура T уменьшается

умножением на постоянную 0,95.

=========215

Public Sub AnnealTrial(K As Integer, max_non_changes As Integer, _

max_back_slips As Integer)

Const TFACTOR = 0.95

Dim i As Integer

Dim non_changes As Integer

Dim t As Double

Dim max_profit As Integer

Dim min_profit As Integer

Dim doit As Boolean

Dim back_slips As Integer

' Найти позицию с минимальной и максимальной прибылью.

max_profit = Items(1).Profit

min_profit = max_profit

For i = 2 To NumItems

If max_profit < Items(i).Profit Then max_profit =

Items(i).Profit

If min_profit > Items(i).Profit Then min_profit =

Items(i).Profit

Next i

t = 0.75 * (max_profit - min_profit)

back_slips = 0

' Выбрать случайное пробное решение

' в качестве начальной точки.

Do While AddToSolution()

' Вся работа выполняется в процедуре AddToSolution.

Loop

' Использовать в качестве пробного решения.

best_profit = test_profit

best_cost = test_cost

For i = 1 To NumItems

best_solution(i) = test_solution(i)

Next i

' Повторять, пока в течение max_non_changes изменений

' подряд не будет улучшений.

non_changes = 0

Do While non_changes < max_non_changes

' Удалить случайную позицию.

For i = 1 To K

RemoveFromSolution

Next i

' Добавить максимально возможное число позиций.

Do While AddToSolution()

' Вся работа выполняется в процедуре AddToSolution.

Loop

' Если изменение улучшает пробное решение, сохранить его.

' Иначе вернуть прежнее значение решения.

If test_profit > best_profit Then

doit = True

ElseIf test_profit < best_profit Then

doit = (Rnd < Exp((test_profit - best_profit) / t))

back_slips = back_slips + 1

If back_slips > max_back_slips Then

back_slips = 0

t = t * TFACTOR

End If

Else

doit = False

End If

If doit Then

' Сохранить улучшение.

best_profit = test_profit

best_cost = test_cost

For i = 1 To NumItems

best_solution(i) = test_solution(i)

Next i

non_changes = 0 ' Хорошее изменение.

Else

' Reset the trial.

test_profit = best_profit

test_cost = best_cost

For i = 1 To NumItems

test_solution(i) = best_solution(i)

Next i

non_changes = non_changes + 1 ' Плохое изменение.

End If

Loop ' Продолжить проверку случайных изменений.

End Sub

Сравнение эвристик

Различные эвристики по-разному ведут себя в различных задачах. Для задачи о

формировании портфеля, эвристика сбалансированной прибыли работает

достаточно хорошо, учитывая ее простоту. Стратегии последовательного

приближения обычно дают сравнимые результаты, но для больших задач их

выполнение занимает намного больше времени. Для других задач наилучшей

может быть какая-либо другая эвристика, в том числе из тех, которые не

обсуждались в этой главе.

========216-217

Эвристические методы обычно выполняются быстрее, чем метод ветвей и границ.

Некоторые из них, например методы восхождения на холм, наименьшей стоимости

и сбалансированной прибыли, выполняются очень быстро, так как они

рассматривают только одно возможное решение. Они выполняются настолько

быстро, что имеет смысл выполнить их все по очереди, и затем выбрать

наилучшее из трех полученных решений. Это не гарантирует того, что это

решение будет наилучшим, но дает некоторую уверенность, что оно окажется

достаточно хорошим.

Другие сложные задачи

Существует множество очень сложных задач, большинство из которых не имеет

решений с полиномиальной вычислительной сложностью. Другими словами, не

существует алгоритмов, которые решали бы эти задачи за время порядка O(NC)

для любых постоянных C, даже за O(N1000).

В следующих разделах кратко описаны некоторые из этих задач. В них также

показано, почему они являются сложными в общем случае и насколько большим

может оказаться дерево решений задачи. Вы можете попробовать применить

метод ветвей и границ или эвристики для решения некоторых из этих задач.

Задача о выполнимости

Если имеется логическое утверждение, например “(A And Not B) Or C”, то

существуют ли значения переменных A, B и C, при которых это утверждение

истинно? В данном примере легко увидеть, что утверждение истинно, если A =

true, B = false и C = false. Для более сложных утверждений, содержащих

сотни переменных, бывает достаточно сложно определить, может ли быть

утверждение истинным.

При помощи метода, похожего на тот, который использовался при решении

задачи о формировании портфеля, можно простроить дерево решений для задачи

о выполнимости (satisfiability problem). Каждая ветвь дерева будет

соответствовать решению о присвоении переменной значения true или false.

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

переменной true.

Если в логическом выражении N переменных, то дерево решений представляет

собой двоичное дерево высотой N + 1. Это дерево имеет 2N листьев, каждый из

которых соответствует разной комбинации значений переменных.

В задаче о формировании портфеля можно было использовать метод ветвей и

границ для того, чтобы избежать поиска в большей части дерева. В задаче о

выполнимости выражение либо истинно, либо ложно. При этом нельзя получить

частичное решение, которое можно использовать для отсечения путей в дереве.

Нельзя также использовать эвристики для поиска приблизительного решения для

задачи о выполнимости. Любое значение переменных, полученное при помощи

эвристики, будет делать выражение истинным или ложным. В математической

логике не существует такого понятия, как приближенное решение.

Из-за неприменимости эвристик и меньшей эффективности метода ветвей и

границ, задача о выполнимости обычно является очень сложной и решается

только в случае небольшого размера задачи.

Задача о разбиении

Если задано множество элементов со значениями X1, X2, … , XN, то существует

ли способ разбить его на два подмножества, так чтобы сумма значений всех

элементов в каждом из подмножеств была одинаковой? Например, если элементы

имеют значения 3, 4, 5 и 6, то их можно разбить на два подмножества {3, 6}

и {4, 5}, сумма значений элементов в каждом из которых равна 9.

Чтобы смоделировать эту задачу при помощи дерева, предположим, что ветвям

соответствует помещение элемента в одно из двух подмножеств. Левая ветвь,

выходящая из корневого узла, соответствует помещению первого элемента в

первое подмножество, а правая ветвь — во второе подмножество.

Если всего существует N элементов, то дерево решение будет представлять

собой двоичное дерево высотой N + 1. Оно будет содержать 2N листьев и 2N+1

узлов. Каждый лист соответствует одному из вариантов размещения элементов в

двух подмножествах.

При решении этой задачи можно применить метод ветвей и границ. При

рассмотрении частичных решений задачи можно отслеживать, насколько

различаются суммарные значения элементов в двух подмножествах. Если в какой-

то момент суммарное значение элементов для одного из подмножеств настолько

меньше, чем для другого, что добавление всех оставшихся элементов не

позволяет изменить это соотношение, то нет смысла продолжать движение вниз

по этой ветви.

Так же, как и в случае с задачей о выполнимости, для задачи о разбиении

(partition problem) нельзя получить приближенное решение. В результате

всегда должно получиться два подмножества, суммарное значение элементов в

которых будет или не будет одинаковым. Это означает, что для решения этой

задачи неприменимы эвристики, которые использовались для решения задачи о

формировании портфеля.

Задачу о разбиении можно обобщить следующим образом: если имеется множество

элементов со значениями X1, X2, … , XN, как разбить его на два

подмножества, чтобы разница суммы значений элементов в двух подмножествах

была минимальной?

Получить точное решение этой задачи труднее, чем для исходной задачи о

разбиении. Если бы существовал простой способ решения задачи в общем

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

этом случае можно было бы просто найти два подмножества, удовлетворяющих

условиям, а затем проверить, совпадают ли суммы значений элементов в них.

Для решения общего случая задачи можно использовать метод ветвей и границ,

примерно так же, как он использовался для решения частного случая задачи,

чтобы избежать поиска по всему дереву. Можно также использовать при этом

эвристический подход. Например, можно проверять элементы в порядке убывания

их значения, помещая очередной элемент в подмножество с меньшей суммой

значений элементов. Также можно было бы легко использовать случайный поиск,

метод последовательных приближений, или метод отжига для поиска

приближенного решения этого общего случая задачи.

Задача поиска Гамильтонова пути

Если задана сеть, то Гамильтоновым путем (Hamiltonian path) для нее

называется путь, обходящий все узлы в сети только один раз и затем

возвращающийся в начальную точку.

На рис. 8.9 показана небольшая сеть и Гамильтонов путь для нее,

нарисованный жирной линией.

Задача поиска Гамильтонова пути формулируется так: если задана сеть,

существует ли для нее Гамильтонов путь?

==============219

@Рис. 8.9. Гамильтонов путь

Так как Гамильтонов путь обходит все узлы в сети, то не нужно определять,

какие из узлов попадают в него, а какие нет. Необходимо установить только

порядок, в котором их нужно обойти для создания Гамильтонова пути.

Для моделирования этой задачи при помощи дерева, предположим, что ветви

соответствуют выбору следующего узла в пути. Корневой узел тогда будет

содержать N ветвей, соответствующих началу пути в каждом из N узлов. Каждый

из узлов первого уровня будет иметь N – 1 ветвей, по одной ветви для

каждого из оставшихся N – 1 узлов. Узлы на следующем уровне дерева будут

иметь N – 2 ветвей, и так далее. Нижний уровень дерева будет содержать N!

листьев, соответствующих N! возможных путей. Всего в дереве будет

находиться порядка O(N!) узлов.

Каждый лист соответствует Гамильтонову пути, но число листьев может быть

разным для различных сетей. Если два узла в сети не связаны друг с другом,

то в дереве будут отсутствовать ветви, которые соответствуют переходам

между этими двумя узлами. Это уменьшает число путей в дереве и

соответственно, число листьев.

Так же, как и в задачах о выполнимости и о разбиении, для задачи поиска

Гамильтонова пути нельзя получить приближенное решение. Путь может либо

являться Гамильтоновым, либо нет. Это означает, что эвристический подход и

метод ветвей и границ не помогут при поиске Гамильтонова пути. Что еще

хуже, дерево решений для задачи поиска Гамильтонова пути содержит порядка

O(N!) узлов. Это намного больше, чем порядка O(2N) узлов, которые содержат

деревья решений для задач о выполнимости и разбиении. Например, 220

примерно равно 1 * 10 6, тогда как 20! составляет около 2,4 * 1018 — в

миллион раз больше. Из-за очень большого размера дерева решений задачи

нахождения Гамильтонова пути, поиск в нем можно выполнить только для задач

очень небольшого размера.

Задача коммивояжера

Задача коммивояжера (traveling salesman problem) тесно связана с задачей

поиска Гамильтонова пути. Она формулируется так: найти самый короткий

Гамильтонов путь для сети.

========220

Эта задача имеет примерно такое же отношение к задаче поиска Гамильтонова

пути, как обобщенный случай задачи о разбиении к простой задаче о

разбиении. В первом случае возникает вопрос о существовании решения. Во

втором — какое приближенное решение будет наилучшим. Если бы существовало

простое решение второй задачи, то его можно было бы использовать для

решения первого варианта задачи.

Обычно задача коммивояжера возникает только в сетях, содержащих большое

число Гамильтоновых путей. В типичном примере, коммивояжеру требуется

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

сети улиц, любые две точки в сети связаны между собой, поэтому любой

маршрут представляет собой Гамильтонов путь. Задача заключается в том,

чтобы найти самый короткий из них.

Так же как и в случае поиска Гамильтонова пути, дерево решений для этой

задачи содержит порядка O(N!) узлов. Так же, как и в обобщенной задаче о

разбиении, для отсечения ветвей дерева и ускорения поиска решения задач

средних размеров можно использовать метод ветвей и границ.

Существует также несколько хороших эвристических методов последовательных

приближений для задачи коммивояжера. Например, использование стратегии пар

путей, при которой перебираются пары отрезков маршрута. Программа

проверяет, станет ли маршрут короче, если удалить пару отрезков и заменить

Страницы: 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