|
||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[30] и в каждом столбце; во-вторых, должна оказывать предпочтение решениям с короткой длиной маршрута. Первое требование удовлетворяется введением следующей, состоящей из трех сумм, функции энергии: Т £ £ ZOUTXIOUTXJ +1 £ £ £ OUTXIOUTyi + Z£OUTXi где A,B и C- некоторые константы. Этим достигается выполнение следующих условий: 1.Первая тройная сумма равна нулю в том и только в том случае, если каждая строка (город) содержит не более одной единицы. 2.Вторая тройная сумма равна нулю в том и только в том случае, если каждый столбец (порядковый номер посещения) содержит не более одной единицы. 3.Третья сумма равна нулю в том и только в том случае, если матрица содержит ровно п единиц.
Рис. 6.6. Маршрут коммивояжера Второе требование - предпочтение коротким маршрутам помощью добавления следующего члена к функции энергии: удовлетворяется с E = D£ £ £<yOUTxi(OUTy,i+1 + OUTyi-1), x x I Заметим, что этот член представляет собой длину любого допустимого маршрута. Для удобства индексы определяются по модулю n, т. е. OUTn+j = OUTj, a D -некоторая константа. При достаточно больших значениях A, B и C низкоэнергетические состояния будут представлять допустимые маршруты, а большие значения D гарантируют, что будет найден короткий маршрут. Теперь зададим значения весов, т. е. установим соответствие между членами в функции энергии и членами общей формы (см. уравнение 6.2)). Получаем -A5xy(1 - 5ij) (не допускает более одной единицы в строке) -B5ij(1 - 5xy) (не допускает более одной единицы в столбце) (глобальное ограничение) -Ddxy(5j,i+1 + 5j,i-1) (член, отвечающий за длину цикла), где 5ij = 1, если i = j, в противном случае 5ij = 0. Кроме того, каждый нейрон имеет смещающий вес хь соединенный с +1 и равный Сп. В работе [8] сообщается об эксперименте, в котором задача коммивояжера была решена для 10 городов. В этом случае возбуждающая функция была равна Как показали результаты, 16 из 20 прогонов сошлись к допустимому маршруту и около 50% решений оказались кратчайшими маршрутами, как это было установлено с помощью полного перебора. Этот результат станет более впечатляющим, если осознать, что имеется 181440 допустимых маршрутов. Сообщалось, что сходимость решений, полученных по методу Хопфилда для задачи коммивояжера, в сильной степени зависит от коэффициентов, и не имеется систематического метода определения их значений [11]. В этой работе предложена другая функция энергии с единственным коэффициентом, значение которого легко определяется. В дополнение предложен новый сходящийся алгоритм. Можно ожидать, что новые более совершенные методы будут разрабатываться, так как полностью удовлетворительное решение нашло бы массу применений. ОБСУЖДЕНИЕ Локальные минимумы Сеть, выполняющая аналого-цифровое преобразование, всегда находит единственное оптимальное решение. Это обусловлено простой природой поверхности энергии в этой задаче. В задаче коммивояжера поверхность энергии сильно изрезана, изобилует склонами, долинами и локальными минимумами и нет гарантии, что будет найдено глобальное оптимальное решение и что полученное решение будет допустимым. При этом воникают серьезные вопросы относительно надежности сети и доверия к ее решениям. Эти недостатки сети смягчаются тем обстоятельством, что нахождение глобальных минимумов для NP-полных задач является очень трудной задачей, которая не может быть решена в приемлемое время никаким другим методом. Другие методы значительно более медленны и дают не лучшие результаты. OUT = У2 [1 + th(NET/U0)]. Скорость Способность сети быстро производить вычисления является ее главным достоинством. Она обусловлена высокой степенью распараллеливания вычислительного процесса. Если сеть реализована на аналоговой электронике, то решение редко занимает промежуток времени, больший нескольких постоянных времени сети. Более того, время сходимости слабо зависит от размерности задачи. Это резко контрастирует с более чем экспоненциальным ростом времени решения при использовании обычных подходов. Моделирование с помощью однопроцессорных систем не позволяет использовать преимущества параллельной архитектуры, но современные мультипроцессорные системы типа Connection Machine (65536 процессоров!) весьма многообещающи для решения трудных задач. Функция энергии Определение функции энергии сети в зависимости от задачи не является тривиальным. Существующие решения были получены с помощью изобретательности, математического опыта и таланта, которые не разбросаны в изобилии. Для некоторых задач существуют систематические методы нахождения весов сети. Эти методы излагаются в гл. 7. Емкость сети Актуальным предметом исследований является максимальное количество запоминаемой информации, которое может храниться в сети Хопфилда. Так как сеть из n двоичных нейронов может иметь 2 состояний, то исследователи были удивлены, обнаружив, что максимальная емкость памяти оказалась значительно меньшей. Если бы могло запоминаться большое количество информационных единиц, то сеть не стабилизировалась бы на некоторых из них. Более того, она могла бы помнить то, чему ее не учили, т. е. могла стабилизироваться на решении, не являющемся требуемым вектором. Эти свойства ставили в тупик первых исследователей, которые не имели математических методов для предварительной оценки емкости памяти сети. Последние исследования пролили свет на эту проблему. Например, предполагалось, что максимальное количество запоминаемой информации, которое может храниться в сети из N нейронов и безошибочно извлекаться, меньше чем cN, где c - положительная константа, большая единицы. Хотя этот предел и достигается в некоторых случаях, в общем случае он оказался слишком оптимистическим. В работе [4] было экспериментально показано, что в общем случае предельное значение емкости ближе к 0,15N. В работе [1] было показано, что число таких состояний не может |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||||||||||