Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






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




а) Решение задачи коммивояжера, сеть Хопфилда. Рассмотрим задачу коммивояжера для городов. Известны расстояния между каждой парой городов ; коммивояжер, выходя из одного города, должен посетить других городов, заходя по одному разу в каждый, и вернуться в исходный. Требуется определить порядок обхода городов, при котором общее пройденное расстояние минимально. Данная задача позволяет минимизировать потери при проектировании сетей, при нахождении оптимальных маршрутов.

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

1) должна поддерживать устойчивое состояние в форме матрицы

 

, (11.10)

 

в которой строки соответствуют городам, столбцы – их номерам в маршруте; в каждой строке и каждом столбце только одна единица, остальные нули;

2) из всех решений вида (11.10) функция энергии должна поддерживать те, которые соответствуют коротким маршрутам.

Таким требованиям удовлетворяет функция энергии в виде:

 

(11.11)

 

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

 

. (11.12)

 

Из (11.11) и (11.12) получаем веса сети Хопфилда:

, .

 

Здесь - символ Кронекера.

Моделирование работы сети Хопфилда показало, что лучшее по качеству решение дает сеть, нейроны корой имеют сигмовидную характеристику, а сеть, в которой нейроны имеют ступенчатые переходы, приходила к финальным состояниям, соответствующим маршрутам немного лучшим, чем случайные. Многочисленные исследования показывают, что качество решения задачи минимизации функции энергии (11.11) существенно зависит от выбора производственной сигмовидной униполярной функции активации нейрона в окрестности нуля. При малой величине производной минимумы энергии оказываются в центре гиперкуба решений (некорректное решение), при большой величине производной сеть Хопфилда попадает в вершину гиперкуба, соответствующую локальному минимуму энергии. Кроме того, на качество решения существенное влияние оказывает выбор коэффициентов . Поиск методов оптимального выбора этих коэффициентов является в настоящее время предметом интенсивных исследований.

б) Машина Больцмана. Математической основой для решения комбинаторных оптимизационных задач на машине Больцмана является алгоритм, моделирующий затвердевание жидкостей или расплавов (алгоритм имитации отжига). Он базируется на идеях из двух различных областей: статистической физики и комбинаторной оптимизации. Данная задача может быть интерпретирована также для назначения задач в распределенной вычислительной или телекоммуникационной системе. Машина Больцмана (МБ) способна реализовать этот алгоритм параллельно и асинхронно. МБ задается четверкой , - число нейронов, - множество связей между нейронами, при этом все автосвязи принадлежат этому множеству, т.е. . Каждый нейрон может иметь состояние 0 или 1. состояние МБ определяется состояниями нейронов , - начальное состояние. Каждая связь имеет вес - вещественное число, множество связей - . Связь называется активной в состоянии , если . Вес связи интерпретируется как количественная мера желательности, чтобы эта связь была активной. При - активность очень желательна, при - активность очень нежелательна. Как и в модели Хопфилда, связи в МБ симметричны, т.е. .

в) Функция консенсуса. Для состояния МБ вводится понятие консенсуса

 

. (11.13)

 

Консенсус интерпретируется как количественная мера желательности, чтобы все связи в состоянии были активны. В частности данную меру уместно использовать в задачах проектирования телекоммуникационных сетей в качестве функции прибыльности бизнеса. Каждая связь в этой сумме учитывается один раз. Для состояния определяется множество соседей . Соседнее состояние получается из при изменении состояния нейрона ,

 

 

Разница консенсусов соседних состояний и равна

 

, (11.14)

 

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

г) Максимизация консенсуса. Переход МБ из одного состояния в другое с максимизацией консенсуса происходит путем выполнения пошаговой процедуры. На каждом ее шаге выполняется испытание, состоящее из двух частей:

1) для данного состояния генерируется соседнее ,

2) оценивается, может ли быть принято состояние , если может, то результат испытания - , иначе . Состояние принимается с вероятностью

 

, (11.15)

 

где - управляющий параметр («время, затраты, температура»).

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

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

 

.

 

2. Правило понижения

.

 

где - положительное число, близкое, но меньше ее.

 

3. Число испытаний, которые проводятся без изменения ( - функция от ).

4. Число последовательных испытаний, не приводящих к изменению состояния машин ( - функция от ), как критерий завершения процесса.

 

д) Решение задачи коммивояжера машиной Больцмана.

Общий подход к программированию комбинаторных оптимизационных задач состоит в следующем:

каждое решение представляется набором , , - число нейронов в сети, - состояние нейрона. Структура связей и веса выбираются так, что:

. Все локальные максимумы функции консенсуса соответствуют приемлемым решениям задачи;

. Чем лучше приемлемое решение, тем больше консенсус соответствующего состояния машины Больцмана.

Перефразируем для МБ задачу коммивояжера.

. Состояние МБ соответствует локальному максимуму функции консенсуса, если и только если это состояние соответствует приемлемому маршруту.

. Чем короче маршрут, тем выше консенсус соответствующего состояния МБ.

Каждый нейрон соответствует элементу матрицы , состояния нейронов обозначаются ( - число городов). Функция консенсуса

 

.

 

Множество связей в сети определяется как объединение трех непересекающихся подмножеств:

- множество связей, несущих информацию о расстояниях между городами (узлами сети),

 

;

 

- множество ингибиторных (запретительных) связей,

 

;

 

- множество связей смещений,

 

.

 

Здесь . Общее число связей равно .

Ингибиторные связи гарантируют, что в конце концов, ни в одной строке и ни в одном столбце не будет более одной единицы. Связи смещений гарантируют, что хотя бы по одной единице есть в каждом столбце и в каждой строке. Таким образом, связи и гарантируют выполнение ограничений в задаче веса их дают одинаковые вклады в консенсусы для всех приемлемых маршрутов.

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

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

 

 

где

.

 

При , , было проведено 100 испытаний для и 25 испытаний для при различных начальных состояний МБ. Для получено решение на 14% хуже оптимума. Вероятностный механизм функционирования МБ дает возможность получать на ней несколько лучшие результаты, чем на модели Хопфилда.

 






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных