ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
3
min
0
решение корректное
Π
( ).
x,s.t.
Q x
(2)
Решение
X
называется корректным, если оно покрывает все эле-
менты множества
M
, т. е.
.
i
S
i
M = S
X
∈
∑
Нейросетевой метод решения.
Задача (1) — эквивалентная за-
дача о покрытии множества. Подробный обзор методов решения
приведен в [16]. Можно выделить точные алгоритмы, жадные алго-
ритмы (Хватал), генетические, нейросетевые. Здесь подробнее оста-
новимся на последних.
Исторически применение нейронных сетей для решения задач
комбинаторной оптимизации было направлено в основном на задачу
коммивояжера [17]. Подробный обзор нейросетевых методов комби-
наторной оптимизации дан в [15].
Рассмотрим дискретную нейронную сеть Хопфилда из
n
{–1,+1}-
нейронов.
Состояния нейронов кодируются {–1, +1}-вектором
1
( , , ).
n
y = y … y
Решение кодируется {0, 1}-вектором
( 1) / 2.
x = y +
Нейроны обрабаты-
ваются асинхронно и в случайном порядке (условие отсутствия осцил-
ляций в динамике сети). Начальное состояние нейронов выбирается
случайным образом.
Учет ограничений
в нейронных сетях при комбинаторной опти-
мизации заключается в модификации выражения энергии сети. Об-
щий подход разработан в [18] для двухслойной модели Extended
Hopfield Model (EHM). Также может быть модифицирован механизм
активации нейронов [19].
Для получения корректного решения (т. е. покрывающего все
элементы
M
) модифицируем целевой функционал
Q
0
так, чтобы он
включал дополнительный штраф за непокрытые вершины:
1
2
3
1
( ) (
)
( ),
n
i
i=
Q x = K c + K s x + K h a x
∑
(3)
где
h
(
u
) — функция штрафа за покрытие элемента
u
раз, например:
h
(
u
) =
c
0
[
u
= 0] или
h
(
u
) =
c
0
(
u
– 1)
2
. Далее рассмотрим эти варианты
подробнее.
Для определения значений коэффициентов используется следу-
ющая эвристика: в результате решения задачи алгоритмом (1) стои-
мость выбранного подмножества должна быть равна выигрышу от
покрытия вершин. Коэффициенты
K
1
и
K
2
приравнивают 1 и 0 соот-
ветственно и определяется
K
3
.
Несмотря на
пост-обработку решения
, некорректные решения
появляются часто [15]. Для того чтобы решить эту проблему, прихо-
дится применять дополнительные шаги пост-обработки на основе
жадного алгоритма Хватала [20, 21]
1,2 4,5,6,7,8,9,10