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

Презентация:



Advertisements
Похожие презентации
Адаптивный метод распределения SPMD-заданий в грид Паньшенсков Михаил, 545 группа Научный руководитель: Лукичев А.С. Рецензент: Демьянович Ю.К июня.
Advertisements

Разработка методологии переноса вычислительно сложных SPMD задач на GPE Grid Власов Всеволод, 544 группа Научный руководитель: Краснощеков В.Е. Рецензент:
Муравьиный алгоритм определения критических связей в СБИС Зав. каф. САПР ИКТиИБ ЮФУ, д.т.н., проф. В.В. Курейчик, аспирант каф САПР ИКТиИБ ЮФУ, Д. Ю. Запорожец,
Основу поведения муравьиной колонии составляет самоорганизация. Самоорганизация является результатом взаимодействия следующих четырех компонентов: - случайность;
Балансировка вычислений в библиотеке Threading Building Blocks Дипломная работа Вьюшковой К.А., 544 гр. Научный руководитель: Вахитов А.Т. Рецензент: Немнюгин.
Взвешенные скелеты для простых многоугольников Дипломная работа студента 544 группы Игнатьевского Сергея Васильевича Научный руководитель: К.В. Вяткина.
Мелкозернистая параллельная реализация алгоритма Монтгомери Руководитель: доктор физико- математических наук, профессор Соболевский П.И.
Реализация индексного анализа для деревьев циклов любого вида сложности Выполнил : студент 818 гр. Юдин Павел Научный руководитель : к. т. н. Муханов Л.
Разработка методов совместного применения генетического и автоматного программирования Федор Николаевич Царев, гр Магистерская диссертация Научный.
Разработка методов совместного применения генетического и автоматного программирования Федор Николаевич Царев, гр Магистерская диссертация Научный.
ИССЛЕДОВАНИЕ ФУНКЦИЙ НА МОНОТОННОСТЬ.. Функцию y = f(x) называют возрастающей на множестве X D(f), если для любых двух точек x 1 и x 2 множества X, таких,
Разработка методов машинного обучения на основе генетических алгоритмов и эволюционной стратегии для построения управляющих конечных автоматов Второй этап.
Выполнил студент группы А Буренков Сергей Александрович. Научный руководитель к.т.н., доцент Шамаева Ольга Юрьевна. ОРГАНИЗАЦИЯ И ИССЛЕДОВАНИЕ ПАРАЛЛЕЛЬНО-ПОСЛЕДОВАТЕЛЬНЫХ.
Понятие сложности алгоритма Для практики недостаточно знать, что задача алгоритмически разрешима. Т. к. ресурсы ЭВМ (ОП и время процессора) ограничены,
Автоматизированная поддержка пользовательской документации Web-приложений, разрабатываемых в среде WebRatio Студент: Дорохов Вадим, 544 гр. Научный руководитель:
Работу выполнили ученики 21 гимназии 10 А класса.
Исследование двухэтапного алгоритма поиска навигационного сигнала И.В. Липа, студ. рук. Е.Н. Болденков, к.т.н., доцент (МЭИ(ТУ))
Структурный синтез и построение расписаний. План лекции. Классификация задач построения расписаний, возникающих при проектировании ИУС РВ. Алгоритмы имитации.
Поиск путей в сложных полигонах для динамических систем реального времени. Работа Порошина И.А., 544 гр. Научный руководитель Уфнаровский В.В. Рецензент,
ПАРАЛЛЕЛЬНАЯ ФИЛЬТРАЦИЯ ИЗОБРАЖЕНИЙ Фурсов В.А., Попов С.Б. Самарский научный центр РАН, Самарский государственный аэрокосмический университет, Институт.
Транксрипт:

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

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

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

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

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

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

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

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