Система моделирования муравьиных алгоритмов в грид: задача поиска последовательности мутаций между геномами Дырдина Анна Викторовна, 544 гр. Научный руководитель: - презентация

1 Система моделирования муравьиных алгоритмов в грид: задача поиска последовательности мутаций между геномами Дырдина Анна Викторовна, 544 гр. Научный руководитель: Вахитов А.Т. Рецензент: Вяххи Н.И.

2 Введение Грид - географически распределенная инфраструктура, объединяющая множество ресурсов разных типов Муравьиный алгоритм – вероятностный метод решения вычислительных задач, которые могут быть сведены к поиску оптимальных путей в графе; Condor – система управления распределенными вычислениями задач, требующих большого объема вычислений

3 Применение ACO алгоритмов в биоинформатике Вычисление расстояния между геномами Алгоритм поиска оптимальных и α-оптимальных сценариев: - граф перестановок; - сценарий между двумя геномами.

4 Цель работы Разработка приложения для параллельного запуска, вычисляющего количество сценариев; Исследование системы Condor, ее применимости для выполнения задачи, реализованной с помощью ACO алгоритма; Изучение зависимости количества сценариев от значения феромона.

5 Актуальность Вычислительная сложность задач, решаемых с помощью ACO алгоритмов; Неконвергентность ACO алгоритмов (отсутствие сходимости).

6 Описание алгоритма В цикле: На каждом компьютере кластера выполняется: –На вход подаются 2 вершины либо граф; –Муравей начинает путь из первой вершины и пытается достигнуть вторую; –Обновление вероятностей (феромонов): - t g – для хорошего ребра, - t n – для нейтрального ребра, - t b – для плохого ребра, где t g t n t b На центральном компьютере: –Слияние графов

7 Результаты работы алгоритма Константа для вычисления феромона Параллельное выполнение Последовательное выполнение Всего сценариев Оптимальных сценариев Всего сценариев Оптимальных сценариев Алгоритм был запущен на 9 компьютерах; Цикл повторялся 10 раз; В результате, количество найденных сценариев возросло примерно на 50%

8 Результаты Реализовано приложение для параллельного запуска с использование ACO алгоритма, вычисляющее сценарии перестановок; Система Condor показала простоту и удобство при использовании; Исследована зависимость количества сценариев от значения феромона