ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
6
рассматриваемого нейрона и разность между ними
Δ
i
Q =
(
1)
(
0)
i
i
Q x = Q x =
=
−
c вероятностью
1
[
1]
1 exp( Δ / )
i
i
P x =
+
Q T
=
−
,
T
— «температура» сети. Будем переводить нейрон в возбужденное
состояние.
Отметим, что возможность выбирать состояния, в которых целе-
вой функционал возрастает, позволяет сети выходить из локальных
минимумов.
Результаты вычислительного эксперимента.
Описанный выше
алгоритм был реализован на языке Scala (объектно-функциональное
расширение Java). Оценка эффективности предложенного алгоритма
проведена на тестовых задачах из набора OR Library. Набор включает
в себя 65 задач различной размерности.
Поскольку результат применения алгоритма зависит от случайно-
го начального состояния нейронной сети, для каждой задачи прово-
дили пять запусков и результаты усредняли. Результаты расчетов
приведены в табл. 1.
Для задач классов E—H оптимальные решения неизвестны из-за
большой размерности задач. Для оценки были использованы предпо-
лагаемые решения, указанные в [8]. Результаты расчетов приведены в
табл. 2.
В 57 задачах из 65 предложенный нейросетевой алгоритм показал
результат лучше, чем алгоритм Хватала. Средняя цена решения алго-
ритмом Хватала — 207,6, предложенным алгоритмом — 204,3. Сред-
няя предполагаемая оптимальная цена — 196,6. Среднее время рас-
четов — 14 с на задачу.
Построение иерархического представления.
Используя решение
SCP, можно создать алгоритм построения иерархического представле-
ния. Принцип работы заключается в итерационном решении SCP.
Алгоритм 2.
Построение иерархического представления на осно-
ве SCP.
Вход
: граф
G
= (
V
,
E
), цены вершин
c
.
Выход
:
N
= ((
G
1
,
A
1
), (
G
2
,
A
2
), …, (
G
L
,
A
L
)), где
A
i
— данные о
принадлежности вершин.
N
: = () — сначала слоев нет
V
c
: =
V
E
c
: =
E
while
|
V
c
| > 1: — формируем новые слои, пока не получим одну
вершину в слое.
S
: = SolveSCP(
V
c
,
E
c
) —
S
является подмножеством
V
c
A
: = {}
V
c
: = {}
E
c
: = {}
head : = {} — отображение множества эквивалентных вершин в
представителя
1,2,3,4,5 7,8,9,10