Файл: Программная инженерия, 18. 04. 2013. Красноярск сфу 2013 2.pdf

152 найденное локально оптимальное решение не будет единственным – муравьи будут искать и другие пути. Если мы моделируем процесс такого поведения на некотором графе, ребра которого представляют собой возможные пути перемещения муравьев, в течение определенного времени, то наиболее обогащенный феромоном путь по ребрам этого графа и будет являться решением задачи, полученным с помощью муравьиного алгоритма. Рассмотрим конкретный пример.
7.3.3. Формализация задачи коммивояжера в терминах муравьиного подхода Задача формулируется как задача поиска минимального по стоимости замкнутого маршрута по всем вершинам без повторений на полном взвешенном графе с п вершинами. Содержательно вершины графа являются городами, которые должен посетить коммивояжера веса ребер отражают расстояния (длины) или стоимости проезда. Эта задача является Р- трудной, и точный переборный алгоритм ее решения имеет факториаль- ную сложность. Приводимое здесь описание муравьиного алгоритма для задачи коммивояжера является кратким изложением статьи С.Д. Штовбы. Моделирование поведения муравьев связано с распределением феромона на тропе – ребре графа в задаче коммивояжера. При этом вероятность включения ребра в маршрут отдельного муравья пропорциональна количеству феромона на этом ребре, а количество откладываемого феромона пропорционально длине маршрута. Чем короче маршрут, тем больше феромона будет отложено на его ребрах, следовательно, большее количество муравьев будет включать его в синтез собственных маршрутов. Моделирование такого подхода, использующего только положительную обратную связь, приводит к преждевременной сходимости – большинство муравьев двигается по локально оптимальному маршруту. Избежать этого можно, моделируя отрицательную обратную связь в виде испарения феромона. При этом если феромон испаряется быстро, то это приводит к потере памяти колонии и забыванию хороших решений, с другой стороны, большое время испарения может привести к получению устойчивого локально оптимального решения. Теперь, с учетом особенностей задачи коммивояжера, можно описать локальные правила поведения муравьев при выборе пути.
1. Муравьи имеют собственную память. Поскольку каждый город может быть посещен только один разу каждого муравья есть список уже посещенных городов – список запретов. Обозначим через
J
i, k
список городов, которые необходимо посетить муравью
k, находящемуся в городе i.
2. Муравьи обладают зрением – видимость есть эвристическое желание посетить город если муравей находится в городе i. Будем считать, что видимость обратно пропорциональна расстоянию между городами

153
η
i, j
= 1 /
D
ij
3. Муравьи обладают обонянием – они могут улавливать след феромона, подтверждающий желание посетить город
j из города i, на основании опыта других муравьев. Количество феромона на ребре (
i, j) в момент времени
t обозначим через τ
ij
(
t).
4. На этом основании можно сформулировать вероятностно- пропорциональное правило, определяющее вероятность перехода го муравья из города
i в город j:
   

  













k
i
J
l
il
il
ij
ij
k
ij
t
t
t
P
,
)
(
)
(
)
(
,
,
j
 J
i, k
0
)
(
,

t
P
k
ij
,
j
 J
i, где α, β – параметры, задающие веса следа феромона, при α = 0 алгоритм вырождается до жадного алгоритма (будет выбран ближайший город. Заметим, что выбор города является вероятностным, правило (7.1) лишь определяет ширину зоны города
j; в общую зону всех городов J
i, k бросается случайное число, которое и определяет выбор муравья. Правило (7.1) не изменяется входе алгоритма, ноу двух разных муравьев значение вероятности перехода будут отличаться, так как они имеют разный список разрешенных городов.
5. Пройдя ребро (
i, j) муравей откладывает на нем некоторое количество феромона, которое должно быть связано с оптимальностью сделанного выбора. Пусть
T
k
(
t) есть маршрут, пройденный муравьем k к моменту времени
t, L
k
(
t) – длина этого маршрута, a Q – параметр, имеющий значение порядка длины оптимального пути. Тогда откладываемое количество феромона может быть задано в виде
Q , (i, j)
 T
k
(
t);
Δτ
ij, k
(
t) = L
k
(
t)
0,
(
i, j)
 T
k
(
t). Правила внешней среды определяют, в первую очередь, испарение феромона. Пусть р
 [0, 1] есть коэффициент испарения, тогда правило испарения имеет вид
τ
ij
(
t + 1) = (1 – p) τ
ij
(
t) + Δ τ
ij
(
t); Δ τ
ij
(
t) =




m
k
k
ij
t
1
,
)
(
,
(7.2) где т – количество муравьев в колонии. Вначале алгоритма количество феромона на ребрах принимается равным небольшому положительному числу. Общее количество муравьев остается постоянными равным количеству городов, каждый муравей начинает маршрут из своего города.
(7.1)

154 Дополнительная модификация алгоритма может состоять во введении так называемых элитных муравьев, которые усиливают ребра наилучшего маршрута, найденного сначала работы алгоритма. Обозначим через Т наилучший текущий маршрут, через L* – его длину. Тогда если в колонии есть е элитных муравьев, ребра маршрута получат дополнительное количество феромона
Δ τ
e
=
e Q / L*.
(7.3) Муравьиный алгоритм для задачи коммивояжера
1. Ввод матрицы расстояний
D.
2. Инициализация параметров алгоритма – α, β, е, Q.
3. Инициализация ребер – присвоение видимости η
ij
и начальной концентрации феромона.
4. Размещение муравьев в случайно выбранные города без совпадений.
5. Выбор начального кратчайшего маршрута и определение
L*
// основной цикл.
6. Цикл повремени жизни колонии
t = 1, tmax.
7. Цикл по всем муравьям
k = 1, m
8. Построить маршрут
T
k
(
t) по правилу (7.1) и рассчитать длину
L
k
(
t).
9. конец цикла по муравьям.
10. Проверка всех
L
k
(
t) на лучшее решение по сравнению с L*.
11. Если да, то обновить
L* и Т.
12. Цикл по всем ребрам графа.
13. Обновить следы феромона на ребре по правилами. конец цикла по ребрам.
15. конец цикла повремени. Вывести кратчайший маршрут Т и его длину L*. Сложность данного алгоритма определяется непосредственно из приведенного выше текста – О, n
2
,
m), таким образом, сложность алгоритма зависит от времени жизни колонии (
tmax), количества городов (n) и количества муравьев в колонии (т.
7.3.4. Области применения и возможные модификации Поскольку в основе муравьиного алгоритма лежит моделирование передвижения муравьев по некоторым путям, то такой подход может стать эффективным способом поиска рациональных решений для задач оптимизации, допускающих графовую интерпретацию. Ряд экспериментов показывает, что эффективность муравьиных алгоритмов растет с ростом размерности решаемых задач оптимизации. Хорошие результаты получаются для нестационарных систем с изменяемыми во времени параметрами, например, для расчетов телекоммуникационных и компьютерных сетей. Муравьиный алгоритм применялся для разработки оптимальной структуры съемочных сетей
GPS, в рамках создания высокоточных геодезических и съемочных технологий. В настоящее время на основе применения муравьиных алгоритмов получены хорошие результаты для таких сложных оптимизационных задач, как задача коммивояжера, транспортная задача, задача календарного планирования, задача раскраски графа, квадратичной задачи о назначениях, задачи оптимизации сетевых графиков и ряда других. Качество получаемых решений во многом зависит от настроечных параметров в вероятностно-пропорциональном правиле выбора путина основе текущего количества феромона и параметров правил откладывания и испарения феромона. Возможно, что динамическая адаптационная настройка этих параметров может способствовать получению лучших решений. Немаловажную роль играет и начальное распределение феромона, а также выбор условно оптимального решения на шаге инициализации. Отмечается, что перспективными путями улучшения муравьиных алгоритмов является адаптация параметров с использованием базы нечетких правили их гибридизация, например, с генетическими алгоритмами. Как вариант, такая гибридизация может состоять в обмене, через определенные промежутки времени, текущими наилучшими решениями. Много полезной информации по муравьиным алгоритмам можно найти на специальных англоязычных сайтах поэтому направлению. Задания
1. Привести основные шаги вероятностного теста Миллера-Рабина.
2. Описать работу алгоритма Рабина-Карпа, обозначить возможные области его применения.
3. Описать основную идею работы генетических алгоритмов, основные структуры и фазы генетического алгоритма.
4. Привести основные шаги генетического алгоритма.
5. Описать основную идею муравьиных алгоритмов.
6. Представиьт формализацию задачи коммивояжера в терминах муравьиного подхода и привести шаги муравьиного алгоритма для задачи коммивояжера.

156
ЗАКЛЮЧЕНИЕ
Создание компьютерной программы для решения какой-либо задачи состоит из нескольких этапов формализация и создание технического задания на исходную задачу, разработка алгоритма решения задачи, написание кода программы, тестирование и отладка программы. Структуры данных и алгоритмы обработки данных можно рассматривать, как строительные блоки создаваемых компьютерных программ. Таким образом, алгоритмы и структуры данных, рассмотренные в данном учебном пособии, являются фундаментом современного программирования на вычислительных машинах. Очевидно, что эффективность компьютерной программы зависит от алгоритма, который в ней реализован. Приведенный в пособии подход к оценке и анализу времени выполнения алгоритмов позволяет выбрать оптимальный вариант для нужд программиста. Как было показано, не всегда самый быстрый алгоритм является лучшим вариантом в том случае, если объем обрабатываемых данных невелик, лучше воспользоваться более простым алгоритмом. Во-первых, это сэкономит время на его разработку, тестирование и отладку. Во-вторых, чем проще алгоритм для понимания самого программиста, тем меньше вероятность допустить логическую ошибку при его реализации. В учебном пособии представлены алгоритмы, направленные на решение таких классических задач, как поиск необходимой информации в некотором информационном пространстве, сортировка данных, были рассмотрены задачи обработки графов. Теоретические исследования данных проблем представляют большой интереса использование приведенных алгоритмов при обработке данных имеет большую практическую значимость. Другим достоинством учебного пособия являются такие современные алгоритмы, как генетические и муравьиные алгоритмы. Отметим, что сегодня наиболее интересные результаты в разработке эффективных алгоритмов связаны с привлечением аппарата других научных дисциплин таких, например, как биология. Данное учебное пособие можно рассматривать как обзорное, поскольку оно охватывает довольно широкий спектр задачи методов их решения. Рассмотренные в пособии алгоритмы обработки данных позволяют создавать программы, направленные на решение вычислительных задач различного характера и масштаба. Практическая значимость задачи обработки данных позволяет рассматривать представленные в данном учебном пособии алгоритмы как отправную точку для дальнейших исследований.

157 БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Ахо, А. Структуры данных и алгоритмы / А. Ахо, Дж. Хопкрофт, Дж. Ульман. – М. : Изд. дом «Вильямс», 2001. – 384 с.
2. Вирт, Н. Алгоритмы и структуры данных / Н. Вирт. – СПб.: Невский диалект, 2001. – 352 с.
3. Вирт, Н. Алгоритмы + структуры данных = программы / Н. Вирт. – М. : Мир, 1985. – 360 с.
4. Кнут, Д. Искусство программирования для ЭВМ. Поиски сортировка Д. Кнут. – М. : Изд. дом «Вильямс», 2001. – Т. 3. – 844 с.
5. Ковалев, ИВ. Моделирование и оптимизация параллельных процессов в информационно-управляющих системах / ИВ. Ковалев, Р. Ю. Царев. – Красноярск : ИПЦ КГТУ, 2003. – 111 с.
6. Макконел, Дж. Основы современных алгоритмов / Дж. Макконел. – М. : Техносфера, 2004. – 368 с.
7. Новиков, ФА. Дискретная математика для программистов / ФА. Новиков. – СПб.: Питер, 2000. – 304 с.
8. Полякова, О. А. Методические указания для выполнения лабораторных работ по информатике для студентов специальности АСУ / О. А. Полякова. – Пермь РИО ПГТУ, 2001. – с.
9. Царев, Р. Ю. Структуры и алгоритмы обработки данных : учеб. пособие / Р. Ю. Царев. – Красноярск : ИПЦ КГТУ, 2006. – 210 с.

158 Учебное издание Царев Роман Юрьевич АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ Учебное пособие
Редактор Э.А. Королькова
Компьютерная верстка Н. Г. Дербёневой
Подписано в печать 17.07.2013. Печать плоская. Формат 60×84/16. Бумага офсетная. Усл. печ. л. 10,0. Тираж 500 экз. Заказ № 2111 Издательский центр
Библиотечно-издательского комплекса Сибирского федерального университета
660041, Красноярск, пр. Свободный, 79
Тел./факс (391) 206-21-49, e-mail: rio@lan.krasu.ru Отпечатано Полиграфическим центром
Библиотечно-издательского комплекса Сибирского федерального университета
660041, Красноярск, пр. Свободный, а
Тел./факс (391) 206-26-58, 206-26-49
E-mail: print_sfu@mail.ru; http://lib.sfu-kras.ru