Автор: А.М. Троянов
В работе рассмотрены и проанализированы натуральные алгоритмы, имеющие в своей основе роевую составляющую. Произведен анализ применения роевых SWARM алгоритмов, на примере алгоритма муравьиной колонии, при планировании загрузки многопроцессорных компьютерных систем.
Ключевые слова: SWARM, роевые алгоритмы, роевой интеллект, муравьиный алгоритм, алгоритм пчелиной колонии, boids.
Достаточно острой проблемой, стоящей при создании многопроцессорных вычислительных систем является проблема планирования загрузки вычислительных ядер. Повышению эффективности управления очередями в параллельных вычислениях посвящены работы таких ученых, как: Kelly P.P., Chen L., Wenbin Jiang, Jia-Shiang , Коваленко В.Н., Корягина Д.А., Семячкина Д.А и других [1-3]. Описанная проблема достаточно хорошо исследована в зарубежной литературе. Одним из вариантов решения данной проблемы является использование SWARM алгоритмов.
Swarm – от английского слова рой. Роевое поведение в природе встречается довольно часто. Это и поведение птиц в стае, и поведение пчелиной семьи, и поведение колонии муравьев, и поведение косяка рыб и т.д. Человек, наблюдая за поведением роевых животных, вывел некоторые алгоритмы их поведения, и применил эти знания в других областях. Поэтому роевые алгоритмы относятся к естественным алгоритмам, т.е. алгоритмам, позаимствованным у природы.
Производя наблюдения за птицами, Крейг Рейнольдс (Craig Reynolds) в 1986 году создал компьютерную модель, которую он назвал Boids. Название Boids составное и расшифровывается как "bird-like object", что переводится на русский язык как «птица как объект». Пытаясь реализовать имитацию поведения стаи птиц, Крейг Рейнольдс алгоритмически вывел поведение каждой из птиц в отдельности, а также их общее взаимодействие в стае. Им было выведено три элементарных правила поведения:
Несмотря на простоту лежащих в основе программы правил, стая, реализованная на компьютере, выглядела достаточно реалистично. Птицы в программе образовывали группы, пытались уйти от столкновений и хаотично бросались в разные стороны, повторяя поведение реальной стаи птиц.
В своей статье, посвященной Boids, он также написал, что разработанная им модель поведения стаи птиц может быть дополнена введением дополнительных факторов, например таких, как поиск пищи, уклонение от препятствия или боязнь хищников [4]. На рисунке 1 показана компьютерная реализация алгоритмов, заложенных в Boids.
Рисунок 1. Компьютерная реализация алгоритмов, заложенных в Boids
Муравьи, в природе, в первый момент времени, производят поиск пищи в случайном порядке, а по нахождению источника продовольствия возвращаются в гнездо, оставляя феромоновый след, рисунок 2а. Когда другие муравьи обнаруживают данный след, то они, с большой долей вероятности начнут перемещаться вдоль него. Если в конце пути был найден источник пищи, то муравей укрепляет, обновляя путь феромонами при возвращении. Чем более сильный феромоновый след оставлен на пути, тем большее количество муравьев выберут его в качестве собственного, рисунок 2б. Через некоторое время феромоны на тропе начинают испаряться, что приводит к уменьшению привлекательности пути. На более коротком участке, за одно и тоже время пройдет большее количество муравьев, чем на длинном, что приведет к увеличению количества феромонов на нем, по сравнению с более длинным участком. Это приведет к перемещению муравьев на короткие участки пути, рисунок 2в. Испарение феромонов является защитой от поиска локально-оптимального решения. Если предположить, что феромоны на пути не испаряются, то путь, выбранный первым муравьем, всегда будет самым привлекательным [5].
а) б) в)
Рисунок 2. Процесс поиска пищи муравьиной колонией
Метод пчелиного роя (Bees Algorithm) является одним из новейших методов. Первые статьи, в которых был предложен данный метод, были опубликованы в 2005 г. Метод основан на моделировании поведения пчёл при поиске нектара.
Реальная пчелиная колония действует следующим образом: существует некоторый источник нектара, который характеризуется своей полезностью. То есть такими факторами, как удалённость от улья, концентрация нектара, удобство его добычи. Пчелы-разведчики осуществляют облёт территории и поиск источников нектара для его сбора. По возвращении в улей, пчела-разведчик выполняет «вербовку» незанятых пчел с помощью танца на специальной площадке улья – области танцев. Одновременно в пределах области танцев разные пчелы могут "рекламировать" различные источники нектара. Механизмы принятия решений, в соответствии с которыми пчела решает следовать за той или иной пчелой-вербовщиком, исследованы недостаточно хорошо. Логично предположить, что вероятность вербовки тем или иным образом определяется полезностью соответствующего источника нектара. Завербованная пчела следует за соответствующей пчелой-разведчиком к области с нектаром и становится, таким образом, занятым фуражиром. Занятый фуражир после добычи нектара возвращается в улей и оставляет его там. После этого данный фуражир может выполнить одно из следующих действий: оставить «свой» источник нектара и стать незанятым фуражиром; продолжить заготовку нектара из прежнего источника, не вербуя других пчел; выполнить вербовку. Пчела выбирает одно из указанных действий по некоторому вероятностному закону[6-8]. На рисунке 3а можно увидеть работу алгоритма оптимизации методом пчелиного роя в начале работы, а на рисунке 3б при нахождении вариантов решения.
а) б)
Рисунок 3. Работа алгоритма оптимизации методом пчелиного роя а) в начале работы, б) при нахождении вариантов решения
Для сопоставления системы муравьев многопроцессорной системе, мы определим следующие понятия:
А. Муравей. Муравей в муравьиной системе это работа в многопроцессорной системе.
Б. Феромон. Значение феромонов на пути в муравьиной системе это вес для ресурса в многопроцессорной системе. То, что ресурс имеет большее значение веса, означает, что ресурс имеет больше вычислительной мощности. Планировщик собирает данные о ресурсах системы и использует эти данные для расчета значения веса ресурса. Феромон - вес каждого ресурса сохраняется в планировщике, и планировщик использует его в качестве параметра для алгоритма. Наконец, планировщик выбирает ресурс по алгоритму планирования и отправляет задания на выбранный.
На рисунке 4 представлено соответствие между системой муравьев и многопроцессорной системой.
Рисунок 4. Сопоставление муравьиной системы и многопроцессорной системы
Начальное значение феромона каждого ресурса для каждого задания равно индикатору феромонов. Индикатор феромона каждого ресурса для каждого задания рассчитывается путем сложения расчетного времени передачи и времени выполнения данной работы при назначении на этот ресурс. Расчетное время передачи может быть легко определено Mj/bandwidthi, где Mj является размером данной работы j, а bandwidthi является пропускной способностью между планировщиком и ресурсом. Тем не менее, другие параметры, например время выполнения задания, трудно предсказать. В зависимости от типа программы, многие методы могут быть использованы для оценки времени выполнения программы. При этом индикатор феромона определяется по формуле: Индикатор феромона:
где PIij является индикатором феромона работы j назначеной ресурсу i, М является размером данной работы j, Т является процессорным временем, необходимым работе j, CPU_speedi (скорость процессора), loadi (текущая нагрузка) и bandwidthi (пропускная способность между планировщиком и ресурсом) все они являются состоянием ресурса I [9].
Индикатор феромона показывает, что когда работа назначена ресурсу, мы рассматриваем состояние ресурса, размеры работ, а также время выполнения программы для того, чтобы выбрать подходящий ресурс для исполнения. Чем больше значение PIij, тем более эффективно оно для ресурса I для выполнения этой работы j.
Желание человека постоянно наращивать мощность компьютерных систем привела к изобретению новых подходов к созданию многопроцессорных систем. Кроме улучшения характеристик одного ядра, человек создал многопроцессорные системы, способные при использовании распараллеливания процесса вычисления многократно превосходить возможности однопроцессорных машин. Балансировка нагрузки и своевременное и правильное распределение задач по вычислительным узлам является приоритетной задачей в данных системах. И действительного прорыва в данном вопросе можно достичь при использовании SWARM алгоритмов.