Автор работы: Пользователь скрыл имя, 24 Марта 2012 в 20:42, курсовая работа
Комбинаторика – раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.
Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью комбинаторного анализа является изучение комбинаторных конфигураций.
*- ЗК с таким количеством городов методом лексического перебора современный компьютер не смог бы решить даже за всё время существования Вселенной.
Как видим по результатам этой таблицы, алгоритм лексического перебора можно применять лишь в случае с количеством городов 5..12. Метод ветвей и границ, наряду с моим методом, можно применять всегда. Хотя мой метод я отнёс к приближённым алгоритмам, он фактически является точным, так как доказать обратное ещё не удалось.
1.3 Практическое применение задачи коммивояжера
Кроме очевидного применения ЗК на практике, существует ещё ряд задач, сводимых к решению ЗК.
Задача о производстве красок. Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать одним процессором.. Будем считать также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке Поскольку производство циклическое, то краски надо производить в циклическом порядке p=(j1,j2,..,jn,j1). После окончания производства краски i и перед началом производства краски j надо отмыть оборудование от краски i. Для этого требуется время C[i,j]. Очевидно, что C[i,j] зависит как от i, так и от j, и что, вообще говоря,C[i,j]≠C[j,i]. При некотором выбранном порядке придется на цикл производства красок потратить время.
Таким образом, ЗК и задача о минимизации времени переналадки – это просто одна задача, только варианты ее описаны разными словами.
Задача о дыропробивном прессе. Дыропробивной пресс производит большое число одинаковых панелей – металлических листов, в которых последовательно по одному пробиваются отверстия разной формы и величины. Схематически пресс можно представить в виде стола, двигающегося независимо по координатам x, y, и вращающегося над столом диска, по периметру которого расположены дыропробивные инструменты разной формы и величины. Каждый инструмент присутствует в одном экземпляре. Диск может вращаться одинаково в двух направлениях (координата вращения z). Имеется собственно пресс, который надавливает на подвешенный под него инструмент тогда, когда под инструмент подведена нужная точка листа.
Операция пробивки j-того отверстия характеризуется четверкой чисел (xj,yj,zj,tj),, где xj,yj- координаты нужного положения стола, zj - координата нужного положения диска и tj - время пробивки j-того отверстия.
Производство панелей носит циклический характер: в начале и конце обработки каждого листа стол должен находиться в положениях (x0, y0) диск в положении z0 причем в этом положении отверстие не пробивается. Это начальное состояние системы можно считать пробивкой фиктивного нулевого отверстия. С параметрами (x0,y0,z0,0).
Чтобы пробить j-тое отверстие непосредственно после i-того необходимо произвести следующие действия:
1. Переместить стол по оси x из положения xi в положение xj, затрачивая при этом время t(x)(|xi-xj|)=ti,j(x)
Проделать то же самое по оси y, затратив время ti,j(y)
Повернуть головку по кратчайшей из двух дуг из положения zi в положение zj, затратив время ti,j(z) .
Пробить j-тое отверстие, затратив время tj.
Конкретный вид функций t(x), t(y), t(z) зависит от механических свойств пресса и достаточно громоздок. Явно выписывать эти функции нет необходимости
Действия 1-3 (переналадка с i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому
С[i,j] = max(t(x), t(y), t(z))
Теперь, как и в предыдущем случае, задача составления оптимальной программы для дыропробивного пресса сводится к ЗК (здесь - симметричной).
Выводы
Изучены эвристический, приближенный и точный алгоритмы решения ЗК. Точные алгоритмы решения ЗК – это полный перебор или усовершенствованный перебор. Оба они, особенно первый, не эффективны при большом числе вершин графа.
Предложен собственный эффективный метод решения ЗК на основе построения выпуклого многоугольника и включения в него центральных вершин (городов).
Проведён анализ наиболее рациональных методов решения ЗК и определены области их эффективного действия: для малого числа вершин можно использовать точный метод лексического перебора; для большого числа вершин рациональнее применять метод ветвей и границ или метод автора работы (Анищенко Сергея Александровича).
Изучены практические применения ЗК и задачи с переналадками, сводимые к ЗК.
Приведены тексты программ, позволяющие решить ЗК различными методами.
Рекуррентные сети на базе персептрона
Рассматриваемые здесь рекуррентные сети представляют собой развитие однонаправленных персептронных сетей за счет внесения в них обратных связей от выходного или промежуточных слоев на вход. В каждой обратной связи присутствует элемент единичной задержки. За счет этого сеть может рассматриваться как однонаправленная, при этом задержанные сигналы обратной связи просто увеличивают размерность входного вектора. Тем не менее алгоритмы обучения таких сетей более сложны, чем алгоритмы обучения однонаправленных сетей.
Ниже рассматриваются два вида сетей данного типа.
Сеть RMLP
Данные сети получаются из однонаправленного многослойного персептрона MLP введением обратных связей с задержкой с выхода на вход сети, поэтому они получили название RMLP (Recurrent MultiLayer Perceptron). На рисунке дана структурная схема двухуровневой сети с одним входом, одним выходом и L нейронами в первом слое нейронов ("1-L-1").
Входной вектор сети имеет следующий вид:
[1,xk,xk-1, ...,xk-(N-1),yk-1,yk-2, ...,yk-M]T,
где(N-1) - количество задержек входного сигнала, M - количество задержек выходного сигнала.
Пусть все нейроны имеют сигмоидальную функцию активации. Тогда для каждого нейрона первого слоя
ui=sum[j=0:N+M](w(1)ij*xj), vi=f(ui),
а для единственного выходного нейрона
g=sum[i=0:L](w(2)i*vi)=sum[i=
Для обучения сети используется метод градиента, минимизирующий целевую функцию
Ek(W)=(1/2)*(yk-dk)2.
Найдем компоненты градиента целевой функции сначала для выходного слоя
дEk(W)/дw(2)n = (yk-dk)*dyk/dw(2)n
= (yk-dk)*df(gk)/dgk*dgk/dw(2)n
= (yk-dk)*df(gk)/dgk*sum[i=0:L](
Ясно, что производная dw(2)i/dw(2)n равна 1 при n=i и равна 0 во всех остальных случаях. Поэтому
дEk(W)/дw(2)n = (yk-dk)*df(gk)/dgk*(vkn+sum[i=
Причем
dvki/dw(2)n = df(uki)/duki*sum[j=0:N+M](w(1)
= df(uki)/duki*sum[j=1:M](w(1)i,
поскольку первые N компонентов входного вектора от весов сети никак не зависят.
В итоге получаем довольно громоздкие рекуррентные выражения для расчета производной выходного сигнала по любому весу выходного нейрона в момент k по ее значениям в M предыдущих моментов k-1, k-2, ...,k-M.
dyk/dw(2)n = df(gk)/dgk*(vkn+sum[i=0:L](w(
Для расчета производной в первые M моментов от начала обучения полагают
dy0/dw(2)n = dy-1/dw(2)n = ... = dy-M+1/dw(2)n = 0.
Аналогичным образом получается выражение для производной выходного сигнала yk по весу нейрона входного слоя w(1)nm
dyk/dw(1)nm = df(gk)/dgk*sum[i=1:L](w(2)i*
где delthain - дельта Кронекера. Напомним, delthain=1 тогда и только тогда, когда i=n, для всех остальных сочетаний i и n дельта Кронекера равна 0.
После получения выражений для производных алгоритм обучения сети RMLP можно сформулировать следующим образом.
1. Инициализировать все весовые коэффициенты сети, положить k=1.
2. Для текущего момента k рассчитать все сигналы сети.
3. Рассчитать значения dyk/dw(2)n и dyk/dw(1)nm для всех взвешенных связей сети.
4. Уточнить все веса, используя формулы
w(2)n<-w(2)n-nu*(yk-dk)*dyk/dw
и
w(1)nm<-w(1)nm-nu*(yk-dk)*dyk/
где nu - коэффициент обучения.
5. Увеличить k на 1 и перейти к п. 2.
Представленный алгоритм работает в режиме "оффлайн", принимая обучающие пары <xk, dk> и оперативно корректируя значения весов.
Сети RMLP широко используются для построения формальных математических моделей реальных динамических объектов, для чего используется следующая схема обучения.
Деление выходного сигнала реального объекта на масштабный коэффициент S необходимо для приведения диапазона изменения этого сигнала к диапазону выходного сигнала сети -1...1 (при использовании биполярной сигмоидальной функции активации).
Обученная по такой схеме сеть RMLP может использоваться, например, в численных экспериментах по отработке алгоритмов управления динамическим объектом.
Рекуррентная сеть Эльмана
Сеть данного типа характеризуется частичной рекуррентностью, в ней обратной связью с единичной задержкой охвачен только первый слой нейронов. Структурная схема сети представлена ниже.
Здесь vl, l=1, 2, ..., L - выходные сигналы первого слоя. Вектор возмущения для момента k имеет следующий вид:
Xk=[1, xk1, xk2, ...,xkN, vk-11, vk-12, ...,vk-1L]T.
Для нейронов первого слоя
ukl=sum[j=0:N+L](w(1)lj*xkj), vkl=f1(ukl).
Для нейронов выходного слоя
gki=sum[l=0:L](w(2)il*vkl), yki=f2(gki).
Целевая функция имеет стандартный вид
Ek(W)=(1/2)*sum[i=1:M]((yki-dk
Получим выражения для частных производных целевой функции по весовым коэффициентам, необходимые для обучения сети методом градиента. Начнем с выходного слоя.
дEk(W)/дw(2)nm = sum[i=1:M](eki*df2(gki)/dgki*
= sum[i=1:M](eki*df2(gki)/dgki*
= sum[i=1:M](eki*df2(gki)/dgki*
Поскольку в сети Эльмана обратных связей с выходного слоя нет, то dvkl/dw(2)nm=0 и выражение упрощается.
дEk(W)/дw(2)nm = sum[i=1:M](eki*df2(gki)/dgki*
С учетом того, производная dw(2)il/dw(2)nm равна 1 при n=i и m=l, и равна 0 при всех остальных сочетаниях значений i и l, в итоге имеем
дEk(W)/дw(2)nm=ekn*df2(gkn)/dg
Кстати, легко заметить, что это выражение повторяет формулу расчета производной в методе обратного распространения ошибки для выходного слоя многослойного персептрона. Это так и должно быть, т.к. в сети Эльмана последний слой нейронов обратными связями не охвачен.
Вывод выражений для производных целевой функции по весам нейронов первого слоя более громоздок.
дEk(W)/дw(1)nm = sum[i=1:M](eki*df2(gki)/dgki*
Отдельно определим
dvkl/w(1)nm = df1(ukl)/dukl*sum[j=0:N+L](d(w
= df1(ukl)/dukl*sum[j=0:N+L](dw(
Поскольку производная dw(1)lj/dw(1)nm равна 1 при l=n и j=m, а при всех остальных сочетаниях l и j равна 0, то заменим ее дельтой Кронекера delthaln, а произведение delthaln*xkm вынесем из под знака суммирования.
dvkl/dw(1)nm = df1(ukl)/dukl*(delthaln*xkm+
Поскольку во входном векторе сети зависимыми от весов первого слоя нейронов являются только последние L компонент в итоге имеем:
dvkl/dw(1)nm = df1(ukl)/dukl*(delthaln*xkm+
Начальные значения производных для момента k=0 принято выбирать нулевыми.
Алгоритм обучения сети Эльмана можно представить в следующем виде.
1. Присвоить весам начальные значения, положить k=1.
2. Для текущего момента k определить все сигналы сети.
3. Рассчитать значения dvkl/dw(1)nm для всех весов нейронов первого слоя.
4. Рассчитать все компоненты вектора градиента целевой функции.
5. Скорректировать веса нейронов обоих слоев по формулам:
w(2)nm<-w(2)nm-nu*дEk(W)/дw(2)
w(1)nm<-w(1)nm-nu*дEk(W)/дw(1)
где nu - коэффициент обучения.
6. Увеличить k на 1 и перейти к п. 2.
ИНС очень эффективно применяются в OCR-приложениях. Однако, нет убедительных доказательств их превосходства над соответствующими статистическими классификаторами. На первой конференции по OCR-системам в 1992 г. [18] более 40 систем распознавания рукописного текста были сопоставлены для одних и тех же данных. Из них 10 лучших использовали вариант многослойной сети прямого распространения или классификатор "ближайшего соседа". ИНС имеют тенденцию к превосходству по скорости и требуемой памяти по сравнению с методом "ближайшего соседа", в отличие от которого скорость классификации с применением ИНС не зависит от объема обучающей выборки. Точность распознавания лучших OCR-систем на базе данных предварительно сегментированных символов составила около 98% для цифр, 96% для заглавных букв и 87 - для строчных. (Низкая точность для строчных букв вызвана в значительной степени тем, что тестовые данные существенно отличались от тренировочных.) По данным теста можно сделать вывод, что на изолированных символах OCR система близка по точности к человеку. Однако человек опережает системы OCR на свободных от ограничений и рукописных документах.