Имитация - отжиг
Cтраница 2
Необходимо, однако, указать на одно отличие. Метод имитации отжига позволяет, в принципе, находить решение с любой степенью точности, но для этого охлаждение необходимо производить все медленнее и медленнее, что требует растущих затрат машинного времени. Точность детерминированных алгоритмов фиксирована. [16]
В последнее время предложено несколько аналоговых методов решения задач комбинаторной оптимизации, для которых приближенный поиск решения осуществляется в ходе прямой эволюции определенной нелинейной системы. Наиболее популярен метод имитации отжига, выдвинутый в работе С. [17]
Тепловые флуктуации, заложенные в алгоритм, дают возможность избегать локальных минимумов. Показано, что алгоритм имитации отжига может быть использован для поиска глобального оптимума адаптивного рельефа нейронной сети. [18]
Как видно из ( 17), время выхода на асимптотику ( 16) не зависит от размера барьеров, разделяющих минимумы функции U ( x), а следовательно, высота подобных барьеров не будет отражаться и на длительности процесса поиска оптимума. Напомним, что в методе имитации отжига длительность поиска растет с увеличением высоты потенциальных барьеров. [19]
Если в область абсолютного минимума попадают другие локальные минимумы, отделенные от него потенциальным барьером А / 0, то при наличии флуктуации динамическая система не может отличить их от абсолютного минимума. Чтобы избежать этого, используют имитацию отжига системы [4], постепенно понижая температуру J и устремляя ее к нулю. Чтобы длительность отжига, гарантирующего правильное отыскание глобального минимума J, не была экспоненциально велика, его нужно начинать с температуры J / тах. [20]
Если в область абсолютного минимума попадают другие локальные минимумы, отделенные от него потенциальным барьером Л J 9, то при наличии флюктуации динамическая система не может отличить их от абсолютного минимума. Чтобы избежать этого, используют имитацию отжига системы [87], постепенно понижая температуру J и устремляя ее к нулю. [21]
 |
Сравнение результатов решения задачи коммивояжера с 30 городами. [22] |
При практическом применении нейросетевых подходов к решению задач оптимизации, однако, главное значение имеет не столько близость решения к глобальному оптимуму, сколько эффективность его получения. В этом смысле сеть Кохонена значительно эффективнее имитации отжига. [23]
 |
Изменения вероятности активности нейрона в зависимости от параметра t. [24] |
Мысль об использовании теплового шума для выхода из локальных минимумов и для повышения вероятности попадания в более глубокие минимумы принадлежит С. Он показал, что при решении сложных задач, когда финансовые затраты на решение задачи оптимизации аналогичны энергии шарика, перемещающегося по поверхности, поиск более дешевых решений разумно начинать в ситуации с высоким уровнем теплового шума, в дальнейшем постепенно уменьшая его; этот процесс Кирпатрик назвал имитацией отжига. Введем некоторый параметр t - аналог уровня теплового шума. [25]
Один из способов получить более однородное распределение заключается в случайном расположении антенн вдоль окружности. В этом случае точки на плоскости uv не находятся более на сетке радиальных линий и окружностей, и на рис. 5.19 б показан пример, в котором частичная оптимизация была выполнена с использованием вычислений по алгоритму нейронных сетей. В этом случае была использована программа, основанная на методе имитации отжига, и расположение антенн относительно окружности проявляло некоторую степень симметрии, вследствие чего заполнение плоскости uv было похоже на кристаллическую структуру. [26]
Недостатком сетей Хопфилда является их тенденция стабилизироваться в локальном, а не глобальном минимуме функции энергии. Эта трудность преодолевается в основном с помощью класса сетей, известных под названием машин Больцмана, в которых изменения состояний нейронов обусловлены статистическими, а не детерминированными закономерностями. Существует тесная аналогия между этими методами и отжигом металла, поэтому и сами методы часто называют имитацией отжига. [27]
 |
Время достижения одинаковой точности алгоритмов A3 ( 1 и Монте-Карло ( 2. [28] |
Хотя метод Монте-Карло, описанный в предыдущем пункте, и оказался пригодным к решению больших задач отображения алгоритмов на мультитранспьютерные ВС, его слабым местом является достаточно медленная сходимость. Попытки увеличить скорость сходимости за счет увеличения начальной температуры приводят к ухудшению стационарного решения. В силу этого был разработан новый стохастический алгоритм наискорейшего спуска. В этом методе, так же как и в методе Монте-Карло, используется процедура имитации отжига, чтобы гарантировать сходимость метода. [29]
Типы входных и выходных сигналов - любые. Емкость сети в общем случае не определена. Тип передаточной функции - любая, ограниченная по области значений. Количество синапсов и смещений сети ограничено скоростью обучения. Для сетей с числом синапсов порядка нескольких сотен алгоритм имитации отжига очень эффективен. Для программно реализованных на персональном компьютере сетей с десятками тысяч настраиваемых параметров процесс обучения по методу отжига длится катастрофически долго. [30]
Страницы: 1 2 3