Курсовая работа: Система моделирования муравьиных алгоритмов в грид: задача поиска последовательности мутаций между геномами

Оглавление

• Введение 3
  • Актуальность работы 3
  • ACO algorithms или муравьиные алгоритмы 4
  • Виды распараллеливания ACO алгоритмов 6
  • Грид-технологии 8
• Система Condor 11
  • Введение 11
  • Методология программирования под Condor 11
  • Condor’s ClassAds 12
• Реализация ACO алгоритма с использованием системы Condor 13
  • Цель работы и постановка задачи 13
  • Теоретические основы 14
    • Сценарии перестановки геномов 14
    • Сценарии перестановки геномов: основные термины 14
    • Вычисление последовательностей перестановок с использованием ACOалгоритма 16
  • Описание алгоритма 17
  • Пример управляющего файла для Condor, запускающего

выполнение алгоритма 19

• Результаты 20
• Выводы 21

Список литературы 22






1 Введение

1.1 Актуальность работы

Интерес к муравьиным алгоритмам (Ant Colony Optimization Algorithm или ACO) сильно возрос в последнее время [1]. Использование ACO алгоритмов помогают при решении сложных комбинаторных задач таких, как:

• задача оптимизации маршрутов,
• задача коммивояжера,
• задача о раскраске графа,
• задача оптимизации сетевых графиков,
• задача о календарном планировании.

Муравьиные алгоритмы также могут быть использованы в задачах о динамической оптимизации процессов в распределенных нестационарных системах, например, трафика в телекоммуникационных сетях.
Чаще всего ACO алгоритмы применяются к NP-полным задачам, позволяя найти качественные субоптимальные решения за короткое время. Так же муравьиные алгоритмы применяются в задачах динамического нахождения кратчайшего пути, возникающих при работе с телекоммуникационными сетями. Благодаря успеху применения ACO алгоритмов в решении научных задач его так же стали использовать при решении промышленных задач [1].
Важным свойством муравьиных алгоритмов является неконвергентность: даже после большого числа итераций одновременно исследуется множество вариантов решения, вследствие чего не происходит длительных временных задержек в локальных экстремумах. Все это позволяет рекомендовать применение муравьиных алгоритмов для решения сложных комбинаторных задач оптимизации.
Большая часть задач, для которых используется муравьиный алгоритм, является вычислительно сложными. При этом ACO алгоритмы хорошо подходят для решения параллельными методами, так как муравьи действуют независимо и асинхронно друг от друга. Для увеличения вычислительной мощности приложений, использующих муравьиные алгоритмы, можно применять грид-технологии. Это позволит запускать алгоритм большее количество раз и, следовательно, увеличить точность получаемого решения.
В этой работе ставилась задача разработать систему для параллелизации ACO алгоритмов с использованием системы Condor.

1.2 ACO algorithms или муравьиные алгоритмы