Применение муравьиных алгоритмов при решении задач оптимизации

     

     Рис.1.

              Представим решение в виде:

1. В начале движения из вершины  1 муравей имеет четыре возможных пути: в вершину 2, 3, 4 или 5. Вычислим вероятности перехода в эти вершины

     

     

     

       

     Вычисляем границы четырех секторов , j=2,3,4,5 вероятностей:

     

     

     

     

     Таким образом, отрезок [0,100] разбился на четыре участка

     

         Остается запустить генератор  случайных чисел и узнать , куда  попадает случайное число . В  нашем случае генератор  дает  =65, что указывает на третий участок 57,5<65<75,89. Следовательно, муравей должен направиться к вершине 4.   

2. Из вершины 4 только три возможные пути: 4-2, 4-3, 4-5. Пройденная вершина 1 попадает в список запрещенных вершин.

     Вероятности перехода в эти вершины

     

     

     

     Вычисляем границы трех секторов , j=2,3,5 вероятностей:

     

     

     

     Таким образом, отрезок [0,100] разбился на три участка

     

     

        Случайное число   =61, полученное генератором случайных чисел попадает на второй участок. Этот участок указывает на вершину 3. Далее муравей будет выбирать маршрут из этой вершины.

3. При выходе из вершины 3 имеется только 2 возможности  - направиться в вершину 2 или 5. Остальные вершины попадают в список запрещенных вершин. Оценим возможности перехода:

      

     

     Таким образом, отрезок [0,100] разбился на два участка

     

     

        Случайное число   =35, полученное генератором случайных чисел указывает на вершину 2.

4. В вершине 2 выбор делать не приходиться. Все вершины, кроме 5 попали в список запрещенных вершин, поэтому дальнейший путь муравья очевиден. Сначала он идет в вершину 5, а затем завершает маршрут в 1, там, откуда он и вышел. Общая длина маршрута 1-4-3-2-5-1 равна

       
 
 
 

 

      1.2 Муравьиный алгоритм для задачи коммивояжёра в псевдокоде

     1. Ввод матрицы расстояний D

     2. Инициализация параметров алгоритма  – α,β,e,Q

     3. Инициализация рёбер – присвоение  видимости и начальной концентрации феромона

     4. Размещение муравьёв в случайно  выбранные города без совпадений 

     5. Выбор начального кратчайшего  маршрута и определение L*

      //Основной цикл 

     6. Цикл по времени жизни колонии  t=1, tmax

     7. Цикл по всем муравьям k=1,m

     8. Построить маршрут   по правилу (1) и рассчитать длину

     9. конец цикла по муравьям 

     10. Проверка всех  на лучшее решение по сравнению с L*

     11. В случае если решение  лучше, обновить L* и T*

     12. Цикл по всем рёбрам графа

     13. Обновить следы феромона на  ребре по правилам (2) и (3)

     14. конец цикла по рёбрам 

     15. конец цикла по времени 

     16. Вывести кратчайший маршрут T* и его длину L*

     Сложность данного алгоритма, как несложно заметить, зависит от времени жизни колонии (tmax), количества городов (n) и количества муравьёв в колонии (m).  

     Для исследования работы муравьиного алгоритма  проведен вычислительный эксперимент. Предложенным алгоритмом  решена задача коммивояжера. Количество городов и количество муравьев совпадают. Программа составлена в среде Delphi (Приложение 1).

      Зададим начальные значения: количество городов, интенсивность феромона  и стоимость маршрута.

     После подсчета программа  выводит кратчайший путь 1-2-3-4-5, и длину пути равную 220.  Интенсивность феромона на путях после прохождения по ним муравьев  увеличилась.  
 
 
 

 

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

 
 

2. 1. Задача оптимального распределения файлов

в    компьютерной сети.

     В данной главе решается задача уменьшения времени отклика компьютерной сети за счет оптимизации размещения файлов распределенной системы. Для решения  задачи предлагается алгоритм, относящийся  к классу алгоритмов муравьиной колонии. [16]

     Обозначим: - количество запросов к файлу i из узла j в единицу времени; , если файл i расположен в узле j, иначе ;    - объем файла i;   - объем узла j, i=1...m,  j=1…n.

     В задаче (1)-(3) необходимо найти матрицу  размещений файлов X. В задаче максимизируется суммарный поток локальных запросов. Задача размещения файлов по узлам компьютерной сети имеет вид:

     Целевая функция

                            (1)

     Ограничения:

                             (2)                                                                                                     (3) 

     2.2  Муравьиный алгоритм для задачи распределения файлов в компьютерной сети в псевдокоде. 

1.Присвоить переменной record первоначальное (небольшое) значение;

2.Присвоить переменной t значение 1;

3. While  Do

         Begin        

       For i:=1 to m do           

       Begin

     а). Сформировать вектор P(n) вероятностей размещения i-го файла в j-й узел.

     б). Сгенерировать случайную величину g, распределенную по закону P(n);

     в). Если  и условие (3) выполняется,

                   то назначить  i-й файл в j-й узел,

                  иначе - сгенерировать новое значение случайной величины g.    

       End;

     г).Вычислить значение целевой функции по формуле (1) и присвоить его

     переменной c_f;

д) Если c_f > record,

е) то   

                  Begin

     ж) Присвоить переменной record значение переменной c_f и                сохранить рекордное решение;             

       End;

     з) Присвоить переменной t значение t+1;           

       End;

     4. Вывести наилучшее решение и завершить алгоритм.

     Пусть - количество феромона, накопленное очередным муравьем на маршруте j, – коэффициент испарения феромона, ,  – первоначальный уровень феромона, ,  - уровень феромона на маршруте j. Вероятность размещения файла в узел j вычисляется по формуле:

     

         (4)

     При выборе узла p для размещения файла происходит увеличение значения : , значение переменной d должно быть одного порядка с оптимальным значением целевой функции. При переходе к очередной итерации алгоритма уровень феромона накапливается:   

     

. 

     Для исследования работы муравьиного алгоритма  проведен вычислительный эксперимент. Предложенным алгоритмом и методом  полного перебора решена задача распределения m файлов среди n узлов сети, m=5, n=3. Объемы файлов - случайные числа. Программа составлена в среде Delphi (Приложение 2).  

       
 
 
 
 

 

            Заключение

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

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

             

Список  использованной литературы:

1. Штовба С. Д. Муравьиные алгоритмы. Математика в приложениях,                     2003, №4, стр. 70-75.
2. МакКоннелл Дж. Основы современных алгоритмов. – М.: Техносфера, 2004. – 368 с.
3. Столлингс В. Современные компьютерные сети. 2-е изд. - СПб: Питер, 2003. - 783с.
4. Муравьиный алгоритм. Статья Чуракова Михаила, Якушева Андрея, 2006
5. Планирование и оптимизация. Статья Ильи Маляренко Источник: Корпоративные системы PC WEEK/RE №27 25 июля, 2006
6. Кузьменко В.М., Таран С.В. Анализ современных методов искусственного интеллекта . Источник: ВІСНИК Донбаської державної машинобудівної академії № 1Е(6), 2006
7. Thompson, Jonathan. Ant Colony Optimization.
8. Delphi 5.0, учебный курс, Фараонов В.В.,  ISBN 5-8952-020-4, 400 с.
9. Delphi 4.0, Дарахвелидзе П.Г., Марков Е. П. 1998, 816 с.
10. Модификация муравьиного алгоритма и его применение к задаче коммивояжера. Статья Кажарова А.А.
11. Кирсанов М.Н. Графы в Maple. Задачи,  алгоритмы,  программы.- М.: Издательство ФИЗМАТЛИТ, 2007
12. Отбор информативных признаков на основе модифицированного метода муравьиных колоний. Статья Субботина С.А., Олейник А.А.
13. Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах. Статья Игнатьева А.Л.
14. Об одном муравьином алгоритме. Статья Курейчик В.М.
15. Гладков Л.А., Курейчик В.М., Курейчик В.В. Генетические алгоритмы. – Ростов-на-Дону: ООО «Ростиздат», 2004г.
16. Гладков Л.А., Курейчик В.М., Курейчик В.В. Основы теории алгоритмов: Учебное пособие по курсу «Математическая логика и теория алгоритмов». – Таганрог: изд-во ТРТУ, 2002г.