BC/NW 2010, №1 (16): 10.1

Генетические алгоритмы в задачах о назначении

Во М. Т., Ладыгин И.И.

(Московский энергетический институт (технический университет), Москва, Россия)

Эффективное применение кластерных вычислительных систем (КВС) на практике оказалось не такой простой задачей. Основной проблемой, с которой столкнулись абсолютно все пользователи таких систем, стало то, как добиться эффективного решения задач на КВС. Начальным этапом для реализации параллельных вычислений, является представление задач в виде параллельных алгоритмов (ПА)[1]. Запись ПА на языке программирования называется параллельной программой (ПП). Параллельные алгоритмы и параллельные программы представляют собой композицию связанных ветвей (частей задачи). Каждая ветвь – последовательность операторов как обычных (вычислительных или логических), так и реализующих взаимодействия (обмен информацией) между данной ветвью и другими. Аксиоматически понятно, что все взаимодействия между ветвями, как на их организацию, так и реализацию – это накладные расходы.

Из этого следует, что время выполнения задачи существенно зависит от того, на сколько эффективно назначены ветви между вычислителями, при котором достигаются минимумы накладных расходов. Таким образом, задача оптимизации времени выполнения прикладной задачи сводится к минимизации накладных расходов. Одним из главных вопросов решения данной проблемы является осуществление оптимального назначения ветвей ПА на КВС, которое трудноразрешимо. Поэтому актуальным является разработка нетрудоемких алгоритмов назначения ветвей ПА на КВС. Данная работа посвящена рассмотрению различных методов назначения, предложен новый алгоритм назначения на основе нейроэволюционных алгоритмов[2].

В теоретическом плане при построении алгоритмов назначения, могут использоваться такие методы оптимизации как динамическое программирование, полный перебор и другие, но реализация их очень трудоемка. На практике обычно применяют методы приближенной оптимизации, в частности эвристические алгоритмы[3].

Одним из эвристических алгоритмов является генетический алгоритм (ГА) – алгоритм поиска[2,4], используемый для решения задач оптимизации и моделирования путем последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию.

Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов. В качестве решений кандидатов в задаче о назначении предлагается использовать результат реализации программной модели КВС, выполняющей заданную прикладную задачу с конечным набором вариантов распределения ее ветвей по свободным вычислителям КВС. Эволюционный процесс [2], выполняется в виде нескольких жизненных циклов, пока не будет выполнен критерий остановки ГА. Таким критерием может быть:

1. нахождение глобального, либо субоптимального решения;

2. исчерпание времени, отпущенного на эволюцию.

Были проведены тесты для сравнения качества представленного алгоритма по сравнению с полным перебором на простых задачах. Представленный алгоритм является универсальным, его можно использовать для КВС с разными конфигурациями.

Литература

1. Хорошевский В. Г. Архитектура вычислительных систем изд. МГТУ имени Н.Э.Баумана – 2008 г.,520 с.

2. Цой Ю.Р. Нейроэволюционный алгоритм и программные средства для обработки изображений. Кандидатская диссертация. 2007г.

3. Топорков В.В. Модели распределенных вычислений. — М.: ФИЗМАТЛИТ, 2004. — 320 с.

4.Вороновкий Г.К. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности – ОСНОВА – 1997. – 112 с.