Research Areas Areas

    Биоинформатика

    Анализ данных геномного секвенирования исследуются различные математические модели сборки генома оценивается вычислительная сложность возникающих в этой области задач разрабатываются применимые на практике алгоритмы сборки генома При изучении генома живого существа выделяют три основных этапа: секвенирование молекул ДНК, содержащих информацию о генома  сборка геномной последовательности  анализ и сравнение геномов  На рисунке показана схема выполнения первых двух из указанных этапов Изучение генома человека и других живых существ имеет важное прикладное значение. На основании результатов сборки генома конкретного человека возможна реализация индивидуальной медицины – определения предрасположенности к различным болезням, создание индивидуальных лекарств и т. д. Кроме этого на основе результатов исследования геномов растений и животных с использованием методов биоинженерии могут быть выведены новые их виды, обладающие определенными свойствами.   Анализ данных экспрессии генов разрабатываются алгоритмы анализа данных, получаемых с помощью специальных чипов анализ данных является одним из этапов разработки экономичных тест-систем для выявления различных заболеваний   Интеграция различных источников биологической информации разрабатываются методы и алгоритмы, которые позволяют учитывать несколько видов биологической информации при анализе одного и того же процесса, происходящего в клетке организма. например, совместно с Washington University St. Louis реализуется проект по разработке алгоритмов совместного анализа данных об экспрессии генов и об обмене веществ 

    Технологии программирования

    О чем мечтают все программисты? Конечно, чтобы компьютер сам писал за них программы или максимально помогал в этом нелегком занятии. Множество программных проектов, начиная от ассемблеров, компиляторов и интерпретаторов и заканчивая построителями исполняемого кода по UML-диаграммам, направлены на достижение именно этой цели. Поисковая инженерия программного обеспечения (Search Based Software Engineering) -- способ решения задач, возникающих в процессе производства программного обеспечения, путем сведения их к задачам оптимизации и последующего решения этих задач. В поисковой инженерии программного обеспечения применяются: генетические алгоритмы эволюционные стратегии муравьиные алгоритмы Цель направления -- разработка методов поисковой инженерии программного обеспечения, позволяющих автоматизировать процесс проектирования, разработки и тестирования программного обеспечения.   Построение управляющих программ по спецификации Управляющие программные системы, как правило, обладают сложным поведением, а именно, могут порождать различные управляющие воздействия в ответ на одни и те же входные воздействия в зависимости от предыстории. Исследования, проводимые в ряде университетов мира (например, в Стенфордском университете), показывают, что для построения и анализа таких систем целесообразно применять модели, основанные на состояниях. Наиболее известной моделью, основанной на состояниях и имеющей детерминированный характер, является конечный автомат. Парадигма программирования, предполагающая описание логики работы программ в виде систем взаимодействующих конечных автоматов, известна как автоматное программирование. Проектирование управляющих программных систем, в том числе основанных на использовании конечных автоматов, вручную является крайне сложным и трудоемким процессом. Поэтому актуальной является разработка методов автоматизированного построения конечных автоматов. Исходные данные для построения автоматов могут быть различными. В частности, может быть известен набор тестов, который должна проходить система, или спецификация, выраженная в виде темпоральных формул, которым построенная система должна удовлетворять. По этой причине разработка различных методов, использующих различные виды исходных данных, является актуальной. При наличии способа оценить то, насколько хорошо тот или иной вариант управляющей системы (конечного автомата) решает поставленную задачу, задача автоматизированного построения управляющей программной системы может рассматриваться как задача оптимизации. При этом такая задача, как правило, не может быть решена с помощью традиционных методов оптимизации, так как пространство поиска – множество возможных конечных автоматов – не является непрерывным. Для решения таких задач, однако, перспективным методом является применение таких методов машинного обучения, как эволюционные или муравьиные алгоритмы. На рис. 1 представлена модель автопилота на основе конечного автомата, выполняющая "бочку". Автомат представлен в правой части рисунка. Данный автомат построен с помощью муравьиных алгоритмов на основе траекторий нескольких полетов, выполненных людьми в авиасимуляторе.   Рис. 1 - Автопилот на основе конечного автомата Для некоторых типов входных данных задача построения конечных автоматов может быть решена точно путем сведения к другим NP-трудным задачам для которых существуют эффективные методы решения. Например, задача построения управляющих конечных автоматов по сценариям работы может быть сведена к задачам выполнимости булевой формулы (SAT) и удовлетворения ограничениям (CSP). Для решения полученных формул на языках SAT и CSP применяются существующие эффективные программные средства.   Генерация тестов с испольхованием эволюционных алгоритмов Тестирование является одним из самых затратных этапов производства программного обеспечения - по оценке экспертов, на него уходит до 50% времени и более 50% стоимости производства ПО. В рамках исследований по направлению "Технологии программирования" решается одна из задач тестирования - нахождение таких тестовых данных, на которых тестируемая программа работает как можно дольше. Для генерации таких тестов используются генетические алгоритмы. Помимо производства программного обеспечения, такие тесты нужны в образовании - для проведения олимпиад по программированию. Кроме того, методы построения таких тестов применимы при автоматизации ускорения программ - организуется коэволюция программ и тестов, приводящая к появлению более быстрых версий исходной программы. Испытание разрабатываемых методов проводится при генерации тестов для олимпиадных задач по программированию. На рис. 2 приводятся графики, иллюстрирующие построение тестов против алгоритмов поиска максимального потока.   Рис. 2 - Графики, иллюстрирующие процесс построения тестов против алгоритма поиска максимального потока  

    Машинное обучение

    Разработка методов анализа больших объемов данных разработка методов машинного обучения для классификации пользователей интернет-ресурсов разработка методов решения задач машинного обучения с использованием SAT-солверов и CSP-солверов метод роевого интеллекта теоретические исследования эволюционных алгоритмов анализ времени работы эволюционных алгоритмов под управлением обучения с подкреплением Выбор вспомогательных критериев с помощью обучения с подкреплением Эффективность оптимизации в некоторых случаях может быть повышена путем введения вспомогательных критериев. В последнее время ведутся активные исследования по применению вспомогательных критериев в задачах дискретной оптимизации, решаемых с помощью эволюционных алгоритмов.   Использование вспомогательных критериев позволяет избежать остановку процесса оптимизации в локальных оптимумах целевого критерия, а также расширяет исследуемую область пространства поиска, за счет чего оптимальное значение целевого критерия может быть найдено за меньшее число итераций эволюционного алгоритма.   Вспомогательные критерии, как правило, формулируются в ходе анализа задачи. Например, может проводиться декомпозиция целевого критерия на вспомогательные. Также существует пример автоматической генерации вспомогательных критериев для задачи о генерации тестов против решений олимпиадных задач.   Обычно об эффективности вспомогательных критериев довольно сложно судить заранее. Более того, один и тот же вспомогательный критерий на различных этапах процесса оптимизации может как ускорять поиск оптимального значения целевого критерия, так и замедлять его. В связи с этим возникает задача автоматического выбора вспомогательного критерия, наиболее эффективного на данном этапе оптимизации, из заранее подготовленного набора критериев.   Автоматический выбор вспомогательных критериев может производиться с помощью предложенного сотрудниками нашей лаборатории метода EA+RL, основанного на выборе критериев оптимизации для эволюционного алгоритма с помощью обучения с подкреплением (см. рис.). Агент обучения на каждой итерации эволюционного алгоритма выбирает критерий оптимизации из списка, состоящего из вспомогательных критериев и целевого. Выбранный критерий используется при формировании очередного поколения эволюционного алгоритма. Затем формируется некоторое представление состояния эволюционного алгоритма, а также награда, зависящая от роста целевого критерия. Награда используется для обновления оценки ожидаемой награды в данном состоянии. Выбирается критерий, максимизирующий оценку ожидаемой награды. В случае, когда оценка одинакова, критерии выбираются равновероятно.   Эффективность метода EA+RL была подтверждена экспериментально на примере решения ряда модельных задач, а также практической задачи генерации тестов. Также существуют теоретические результаты, показывающий на примере модельных задач, что метод EA+RL позволяет игнорировать неэффективный вспомогательный критерий и выбирать эффективный.      Схема EA+RL метода выбора с помощью обучения с подкреплением функции приспособленности (ФП) для использования в эволюционном алгоритме, g(x) - целевая функция, которую необходимо оптимизировать, x - текущее поколение особей эволюционного алгоритма, t - номер поколения.

    Last publications Publications

    2018 year
    • Matveev Y., Alexeev A., Kukharev G.

      Using a Fully Connected Convolutional Network to Detect Objects in Images // Proc. 2018 Fifth International Conference on Social Networks Analysis, Management and Security (SNAMS) - 2018, pp. 1-6

    • Sholokhov A., Sahidullah M., Kinnunen T.

      Semi-supervised speech activity detection with an application to automatic speaker verification // Computer Speech and Language - 2018, Vol. 47, pp. 132-156

    • Olekhnovich E.I., Vasilyev A.T., Ulyantsev V.I., Kostryukova E.S., Tyakht A.V.

      MetaCherchant: analyzing genomic context of antibiotic resistance genes in gut microbiota // Bioinformatics - 2018, Vol. 34, No. 3, pp. 434-444

    • Иванько Д.В.

      Использование системы распознавания лиц для осуществления покупок в мобильных устройствах и веб-приложениях // Научно-технический вестник информационных технологий, механики и оптики - 2018. - Т. 18. - № 3(115). - С. 457-461

    • Лаврентьева Г.М., Новоселов С.А., Козлов А.В., Кудашев О.Ю., Щемелинин В.Л., Матвеев Ю.Н., Де Марсико М.

      Методы детектирования спуфинг-атак повторного воспроизведения на голосовые биометрические системы // Научно-технический вестник информационных технологий, механики и оптики - 2018. - Т. 18. - № 3(115). - С. 428–436

    • Krawczyk M.J., Kulakowski K., Holyst J.A.

      Hierarchical Partitions of Social Networks Between Rivaling Leaders // PLoS ONE - 2018, Vol. 13, No. 3, pp. e0193715

    Information © 2015-2018 ITMO University
    2015 Department of Information Technology