Ко-эволюционные алгоритмы для решения больших научных задач
Дата публикации: 16.12.2015
Магистрант второго курса кафедры высокопроизводительных вычислений Михаил Мельник принял участие в постерной сессии 7-ой Международной конференции ECTA (the International Conference on Evolutionary Computation Theory and Applications) в Лиссабоне (Португалия). Молодой ученый рассказал о результатах исследования, посвященного применению метаэвристических ко-эволюционных алгоритмов для задач оптимизации рабочего расписания (Workflow Scheduling) в облачной среде. Статью, в которой они отражены, Михаил написал совместно с преподавателем кафедры ВПВ Денисом Насоновым, магистранткой Натальей Шиндяпиной и аспирантом Николаем Бутаковым.
Конференция ECTA является крупнейшим событием для ученых и инженеров, которые занимаются изучением, анализом, дизайном, моделированием сложных систем, посвящая свои работы нейрокомпьютингу, эволюционным вычислениям и нечетким множествам. Сама ECTA входит в объединенную конференцию IJCCI – International Joint Conference on Computational Intelligence. Таким образом, в Португалии на несколько дней собирается самое большое в мире количество ведущих ученых в профильных областях. Михаил Мельник представил часть исследования, которое он проводит в рамках магистерской диссертации, обучаясь по программе двойного диплома и проводя третий семестр в Университете Амстердама.
Главной задачей работы является поиск наиболее быстрых способов оптимизации рабочего расписания Workflow scheduling. Эта система признана наиболее эффективной для обработки большого количества данных и выполнения сопутствующих сложных задач.
«Workflow scheduling в большей степени подходит для нужд ученых, – объясняет Михаил Мельник. – В ходе технологического прогресса те количества данных, с которыми им приходится работать, те вычисления, которые необходимо производить, становятся все более трудными для обработки. Представьте, что поступает какая-либо информация с большого адронного коллайдера – ее много и она требует предварительной оптимизации. Понятно, что чем быстрее и эффективнее произойдет этот процесс, тем лучше. Различные алгоритмы Workflow scheduling позволяет грамотно распределить рабочую нагрузку на ряд компьютеров, чтобы каждый выполнял посильную для себя задачу. Поиск новых алгоритмов оптимизации, которые могут быть эффективнее существующих – актуальное в науке направление. Усложняет проблему то, что, говоря о компьютерной организации информации, мы все чаще имеем дело с облачной средой: коллаборационные научные проекты подразумевают территориальное рассредоточение вычислительных мощностей по миру».
Большинство существующих способов оптимизации основаны на открытых эвристических и метаэвристических алгоритмах. Последние реализуют прямой случайный поиск возможных решений задачи, оптимальных или близких к оптимальным, пока не будет выполнено некое условие или достигнуто заданное число итераций. К таким быстрым способам оптимизации относится эволюционный метод, в свою очередь включающий в себя ко-эволюционные алгоритмы.
Эволюционные методы можно отнести к так называемым nature inspired процессам, то есть вдохновленным природой или позаимствованным у природы. Они не связаны напрямую с биологической эволюцией Дарвина, однако пользуются одним понятийно-терминологическим аппаратом. Как и в живой природе, в алгоритмическом «мире» есть популяции, существует размножение, мутации и, наконец, отбор наиболее приемлемых для задачи решений. Эволюционные алгоритмы подразумевают обязательное прохождение трех этапов: скрещивание – селекция – формирование нового поколения. Все как у зверей.
Особенность же ко-эволюционных алгоритмов состоит в следующем: они подразумевают то, что в пространстве поиска задачи оптимизации эволюционируют сразу несколько популяций, каждая из которых решает исходную оптимизационную задачу и имеет свою стратегию оптимизации. В процессе решения задачи популяции конкурируют между собой за ресурс, который в процессе работы ко-алгоритма перераспределяется в пользу более эффективной из них. Таким образом, идея ко-эволюции позволяет выполнять несколько эволюционных процессов параллельно, закрепляя их друг с другом.
Коллектив кафедры ВПВ, рассказывает Михаил Мельник, использовал в исследовании три ко-эволюционных алгоритма – ко-эволюционный генетический алгоритм (CGA), ко-эволюционный алгоритм роя частиц (СPSO) и ко-эволюционный алгоритм гравитационного поиска (CGSA). Несмотря на то, что сами алгоритмы существуют уже относительно давно, к процессу оптимизации Workflow scheduling в облачной среде, где одна популяция распределяет задачи между компьютерами, а вторая – выделяет и перераспределяет виртуальные машины, они применяются впервые
Исследования показали, что ко-эволюционный подход позволяет разбить трудоемкую проблему на более простые для оптимизации задачи. Помимо прочего, они по ряду характеристик превышают эффективность более традиционных, эвристических алгоритмов.
«Наше решение может быть применимо везде, где требуется быстрое и эффективное произведение сверхсложных вычислений, – отмечает магистрантка второго курса кафедры ВПВ Наталья Шиндяпина. – За примером далеко ходить не нужно: ко-эволюционные алгоритмы могут показать себя в работе с программным комплексом, прогнозирующим наводнения, который разработан сотрудниками нашей кафедры. Здесь очень важно правильно рассчитать, когда закрывать дамбу: если поторопиться, будет больше экономических издержек, если опоздать, часть территории все-таки будет затоплена. Поэтому, когда приходят метеорологические прогнозы, скорость ветра и другие данные, важно быстро их обработать и принять решение, когда закрывать дамбу лучше всего. Сейчас программный комплекс использует сразу несколько алгоритмов, в том числе и наши, а человек, который стоит за “пультом управления”, выбирает оптимальное решение».
Ульяна Малышева,
Редакция новостного портала Университета ИТМО