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

Генети́ческий алгори́тм (англ. genetic algorithm ) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Содержание

История [ править | править код ]

Первые работы по симуляции эволюции были проведены в 1954 году Нильсом Баричелли на компьютере, установленном в Институте перспективных исследований Принстонского университета. [1] [2] Его работа, опубликованная в том же году, привлекла широкое внимание общественности. С 1957 года, [3] австралийский генетик Алекс Фразер опубликовал серию работ по симуляции искусственного отбора среди организмов с множественным контролем измеримых характеристик. Положенное начало позволило компьютерной симуляции эволюционных процессов и методам, описанным в книгах Фразера и Барнелла(1970) [4] и Кросби (1973) [5] , с 1960-х годов стать более распространенным видом деятельности среди биологов. Симуляции Фразера включали все важнейшие элементы современных генетических алгоритмов. Вдобавок к этому, Ганс-Иоахим Бремерманн в 1960-х опубликовал серию работ, которые также принимали подход использования популяции решений, подвергаемой рекомбинации, мутации и отбору, в проблемах оптимизации. Исследования Бремерманна также включали элементы современных генетических алгоритмов. [6] Среди прочих пионеров следует отметить Ричарда Фридберга, Джорджа Фридмана и Майкла Конрада. Множество ранних работ были переизданы Давидом Б. Фогелем (1998). [7]

Хотя Баричелли в своей работе 1963 года симулировал способности машины играть в простую игру, [8] искусственная эволюция стала общепризнанным методом оптимизации после работы Инго Рехенберга и Ханса-Пауля Швефеля в 1960-х и начале 1970-х годов двадцатого века — группа Рехенберга смогла решить сложные инженерные проблемы согласно стратегиям эволюции. [9] [10] [11] [12] Другим подходом была техника эволюционного программирования Лоренса Дж. Фогеля, которая была предложена для создания искусственного интеллекта. Эволюционное программирование первоначально использовавшее конечные автоматы для предсказывания обстоятельств, и использовавшее разнообразие и отбор для оптимизации логики предсказания. Генетические алгоритмы стали особенно популярны благодаря работе Джона Холланда в начале 70-х годов и его книге «Адаптация в естественных и искусственных системах» (1975) [13] . Его исследование основывалось на экспериментах с клеточными автоматами, проводившимися Холландом и на его трудах написанных в университете Мичигана. Холланд ввел формализованный подход для предсказывания качества следующего поколения, известный как Теорема схем. Исследования в области генетических алгоритмов оставались в основном теоретическими до середины 80-х годов, когда была, наконец, проведена Первая международная конференция по генетическим алгоритмам в Питтсбурге, Пенсильвания (США).

С ростом исследовательского интереса существенно выросла и вычислительная мощь настольных компьютеров, это позволило использовать новую вычислительную технику на практике. В конце 80-х, компания General Electric начала продажу первого в мире продукта, работавшего с использованием генетического алгоритма. Им стал набор промышленных вычислительных средств. В 1989, другая компания Axcelis, Inc. выпустила Evolver — первый в мире коммерческий продукт на генетическом алгоритме для настольных компьютеров. Журналист The New York Times в технологической сфере Джон Маркофф писал [14] об Evolver в 1990 году.

Описание алгоритма [ править | править код ]

Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора («генотипа») генов, где каждый ген может быть битом, числом или неким другим объектом. В классических реализациях генетического алгоритма (ГА) предполагается, что генотип имеет фиксированную длину. Однако существуют вариации ГА, свободные от этого ограничения.

Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип, им описываемый, решает поставленную задачу.

При выборе «функции приспособленности» (или fitness function в англоязычной литературе) важно следить, чтобы её «рельеф» был «гладким».

Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.

Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:

• нахождение глобального, либо субоптимального решения;
• исчерпание числа поколений, отпущенных на эволюцию;
• исчерпание времени, отпущенного на эволюцию.

Генетические алгоритмы служат, главным образом, для поиска решений в многомерных пространствах поиска.

Таким образом, можно выделить следующие этапы генетического алгоритма:

1. Задать целевую функцию (приспособленности) для особей популяции
2. Создать начальную популяцию

• (Начало цикла)

1. Размножение (скрещивание)
2. Мутирование
3. Вычислить значение целевой функции для всех особей
4. Формирование нового поколения (селекция)
5. Если выполняются условия остановки, то (конец цикла), иначе (начало цикла).

Создание начальной популяции [ править | править код ]

Перед первым шагом нужно случайным образом создать начальную популяцию; даже если она окажется совершенно неконкурентоспособной, вероятно, что генетический алгоритм всё равно достаточно быстро переведёт её в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности (Fitness). Итогом первого шага является популяция H, состоящая из N особей.

Отбор (селекция) [ править | править код ]

На этапе отбора нужно из всей популяции выбрать определённую её долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и её просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H’. Остальные особи погибают.

• Турнирная селекция — сначала случайно выбирается установленное количество особей (обычно две), а затем из них выбирается особь с лучшим значением функции приспособленности
• Метод рулетки — вероятность выбора особи тем вероятнее, чем лучше её значение функции приспособленности p i = f i ∑ i = 1 N f i <displaystyle p_=<frac ><sum _^>>>>, где p i <displaystyle p_>— вероятность выбора i особи, f i <displaystyle f_>— значение функции приспособленности для i особи, N <displaystyle N>— количество особей в популяции
• Метод ранжирования — вероятность выбора зависит от места в списке особей отсортированном по значению функции приспособленности p i = 1 N ( a − ( a − b ) i − 1 N − 1 ) <displaystyle p_=<frac <1>>(a-(a-b)<frac >)>, где a ∈ [ 1 , 2 ] <displaystyle ain [1,2]>, b = 2 − a <displaystyle b=2-a>, i <displaystyle i>— порядковый номер особи в списке особей отсортированном по значению функции приспособленности (то есть i< ext< >>< ext< >>f_leq f_>"> ∀ i ∀ j > i f i ≤ f j <displaystyle forall < ext< >>i< ext< >>forall < ext< >>j>i< ext< >>< ext< >>f_leq f_>i< ext< >>< ext< >>f_leq f_"/> — если мы минимизируем значение функции приспособленности)
• Равномерное ранжирование — вероятность выбора особи определяется выражением: p i = < 1 μ , if 1 ≤ i ≤ μ 0 , if μ ≤ i ≤ N <displaystyle p_=<egin<frac <1><mu >>,&<mbox>1leq ileq mu \0,&<mbox>mu leq ileq Nend>>, где μ ≤ N <displaystyle mu leq N>параметр метода
• Сигма-отсечение — для предотвращения преждевременной сходимости генетического алгоритма используются методы, масштабирующие значение целевой функции. Вероятность выбора особи тем больше, чем оптимальнее значение масштабируемой целевой функции p i = F i ∑ i = 1 N F i <displaystyle p_=<frac ><sum _^>>>>, где F i = 1 + f i − f a v g 2 σ <displaystyle F_=1+<frac -f_><2sigma >>>, f a v g <displaystyle f_>— среднее значение целевой функции для всей популяции, σ — среднеквадратичное отклонение значения целевой функции [15] .

Выбор родителей [ править | править код ]

Размножение в генетических алгоритмах требует для производства потомка нескольких родителей, обычно двух.

Можно выделить несколько операторов выбора родителей:

1. Панмиксия — оба родителя выбираются случайно, каждая особь популяции имеет равные шансы быть выбранной
2. Инбридинг — первый родитель выбирается случайно, а вторым выбирается такой, который наиболее похож на первого родителя
3. Аутбридинг — первый родитель выбирается случайно, а вторым выбирается такой, который наименее похож на первого родителя

Инбридинг и аутбридинг бывают в двух формах: фенотипной и генотипной. В случае фенотипной формы похожесть измеряется в зависимости от значения функции приспособленности (чем ближе значения целевой функции, тем особи более похожи), а в случае генотипной формы похожесть измеряется в зависимости от представления генотипа (чем меньше отличий между генотипами особей, тем особи похожее).

Размножение (Скрещивание) [ править | править код ]

Размножение в разных алгоритмах определяется по-разному — оно, конечно, зависит от представления данных. Главное требование к размножению — чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.

Почему особи для размножения обычно выбираются из всей популяции H, а не из выживших на первом шаге элементов H’ (хотя последний вариант тоже имеет право на существование)? Дело в том, что главный недостаток многих генетических алгоритмов — отсутствие разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них — выбор для размножения не самых приспособленных, но вообще всех особей. Однако такой подход вынуждает хранить всех существовавших ранее особей, что увеличивает вычислительную сложность задачи. Поэтому часто применяют методы отбора особей для скрещивания таким образом, чтобы «размножались» не только самые приспособленные, но и другие особи, обладающие плохой приспособленностью. При таком подходе для разнообразия генотипа возрастает роль мутаций.

Мутации [ править | править код ]

К мутациям относится все то же самое, что и к размножению: есть некоторая доля мутантов m, являющаяся параметром генетического алгоритма, и на шаге мутаций нужно выбрать mN особей, а затем изменить их в соответствии с заранее определёнными операциями мутации.

Критика [ править | править код ]

Существует несколько поводов для критики насчёт использования генетического алгоритма по сравнению с другими методами оптимизации:

• Повторная оценка функции приспособленности (фитнесс-функции) для сложных проблем, часто является фактором, ограничивающим использование алгоритмов искусственной эволюции. Поиск оптимального решения для сложной задачи высокой размерности зачастую требует очень затратной оценки функции приспособленности. В реальных задачах, таких как задачи структурной оптимизации, единственный запуск функциональной оценки требует от нескольких часов до нескольких дней для произведения необходимых вычислений. Стандартные методы оптимизации не могут справиться с проблемами такого рода. В таком случае, может быть необходимо пренебречь точной оценкой и использовать аппроксимацию пригодности, которая способна быть вычислена эффективно. Очевидно, что применение аппроксимации пригодности может стать одним из наиболее многообещающих подходов, позволяющих обоснованно решать сложные задачи реальной жизни с помощью генетических алгоритмов.
• Генетические алгоритмы плохо масштабируемы под сложность решаемой проблемы. Это значит, что число элементов, подверженных мутации очень велико, если велик размер области поиска решений. Это делает использование данной вычислительной техники чрезвычайно сложным при решении таких проблем, как, например, проектирование двигателя, дома или самолёта. Для того чтобы сделать так, чтобы такие проблемы поддавались эволюционным алгоритмам, они должны быть разделены на простейшие представления данных проблем. Таким образом, эволюционные вычисления используются, например, при разработке формы лопастей, вместо всего двигателя, формы здания, вместо подробного строительного проекта и формы фюзеляжа, вместо разработки вида всего самолёта. Вторая проблема, связанная со сложностью, кроется в том, как защитить части, которые эволюционировали с высокопригодными решениями от дальнейшей разрушительной мутации, в частности тогда, когда от них требуется хорошая совместимость с другими частями в процессе оценки пригодности. Некоторыми разработчиками было предложено, что подход, предполагающий развитие пригодности эволюционирующих решений, смог бы преодолеть ряд проблем с защитой, но данный вопрос всё ещё остаётся открытым для исследования.
• Решение является более пригодным лишь по сравнению с другими решениями. В результате условие остановки алгоритма неясно для каждой проблемы.
• Во многих задачах генетические алгоритмы имеют тенденцию сходиться к локальному оптимуму или даже к произвольной точке, а не к глобальному оптимуму для данной задачи. Это значит, что они «не знают», каким образом пожертвовать кратковременной высокой пригодностью для достижения долгосрочной пригодности. Вероятность этого зависит от формы ландшафта пригодности: отдельные проблемы могут иметь выраженное направление к глобальному минимуму, в то время как остальные могут указывать направление для фитнесс-функции на локальный оптимум. Эту проблему можно решить использованием иной фитнесс-функции, увеличением вероятности мутаций, или использованием методов отбора, которые поддерживают разнообразие решений в популяции, хотя Теорема об отсутствии бесплатного обеда при поиске и оптимизации[16] доказывает, что не существует общего решения данной проблемы. Общепринятым методом поддержания популяционного разнообразия является установка уровневого ограничения на численность элементов с высоким сродством, которое снизит число представителей сходных решений в последующих поколениях, позволяя другим, менее сходным элементам оставаться в популяции. Данный приём, тем не менее, может не увенчаться успехом в зависимости от ландшафта конкретной проблемы. Другим возможным методом может служить простое замещение части популяции случайно сгенерированными элементами, в момент, когда элементы популяции становятся слишком сходны между собой. Разнообразие важно для генетических алгоритмов (и генетического программирования) потому, что перекрёст генов в гомогенной популяции не несёт новых решений. В эволюционных стратегиях и эволюционном программировании, разнообразие не является необходимостью, так как большая роль в них отведена мутации.

Имеется много скептиков относительно целесообразности применения генетических алгоритмов. Например, Стивен С. Скиена, профессор кафедры вычислительной техники университета Стоуни—Брук, известный исследователь алгоритмов, лауреат премии института IEEE, пишет [17] :

Я лично никогда не сталкивался ни с одной задачей, для решения которой генетические алгоритмы оказались бы самым подходящим средством. Более того, я никогда не встречал никаких результатов вычислений, полученных посредством генетических алгоритмов, которые производили бы на меня положительное впечатление.

Применение генетических алгоритмов [ править | править код ]

Генетические алгоритмы применяются для решения следующих задач:

Пример простой реализации на C++ [ править | править код ]

Поиск в одномерном пространстве, без скрещивания.

Задача размещения вершин графа на линейке является NP-полной[1]. Это означает то, что на данный момент не существует универсального алгоритма, который мог бы находить решение за полиномиальное время.
Данная задача имеет теоретическую ценность теории алгоритмов. Ее ценность заключается в том, что если будет найдет «полиномиально быстрый» алгоритм решение данной задачи, то и любая другая задача из класса NP может быть решена также «быстро», а это в свою очередь докажет равенство классов и . До недавнего времени не существовало эффективного метода поиска решений NP-полных задач. С появлением эволюционного моделирование стало возможно находить квазиоптимальные решение за «приемлемое время».

Обоснования выбора генетического алгоритма:

• генетические алгоритмы продемонстрировали свою эффективность для решения задачы, плохо поддающихся решению традиционными методами;
• вычислительное время генетических алгоритмов для большинства приложений практически линейно зависит от размера задачи и числа оптимизируемых параметров;

Приведем постановку задачи. Основная цель алгоритмов размещения минимизировать общую суммарную длину ребер графа или гиперграфа.
В каждую ячейку в линейке может быть размещена вершина графа или гиперграфа. Расстояние между вершинами считается на основе следующей формулы[2]:

(1)

Здесь — позиции элементов (вершин графа) в линейке, — расстояние между вершинами в линейке.

Общая суммарная длина ребер графа вычисляется формулой[2]:

(2)

Здесь — общая суммарная длина ребер графа в линейке, — количество вершин графа, , — количество ребер соединяющих вершины , .
В оптимизационной задачи размещения входными данными являются вершины графа или гиперграфа , множество ребер графа или гиперграфа и множество позиций . Причем , если производится размещение на заданные позиции.
Сформулируем задачи размещение как оптимизационную. В качестве целевой функции выбирается формула (2) которую нужно минимизировать т. е. . Выходными данными будут позиции назначения каждой вершины. Теперь определим ограничения. Для каждого назначается только одна позиция . Для каждой позиции соответствует, по крайней мере, одна вершина. Следовательно сформулирована задача размещения как оптимизационная.

Генетические алгоритмы предназначены для решения задач оптимизации. В основе генетических алгоритмов лежит метод случайного направленного поиска. Для нашей задачи мы будем использовать классическую модель ГА, предложенную в 1975 г. Джоном Холландом (John Holland) в Мичиганском университете[3].

Схема алгоритма Холланда:

1. Сгенерировать исходную популяцию, состоящую из особей;
2. Оценить приспособленность хромосом в популяции на основе целевой функции ;
3. Выполнить операцию селекции;
4. Применить генетические операторы (мутация, скрещивание);
5. Сформировать новую популяцию;
6. Если критерий останова алгоритма не достигнут, перейти к шагу 2, иначе завершить работу;

Для начала нам нужно выбрать способ представления графа в виде хромосомы. Проанализировав различные способы кодирования, было выбрано кодирование перестановка: такой способ выбран по причине того, что нам нужно чтобы гены в хромосоме не повторялись. Приведем кодирование решений: имеется вектор , — количество вершин графа, как показано на рис. 1. Таким образом мы определили кодирование решений(хромосом).

Рис. 1. Кодировка хромосомы

В качестве метода селекции был выбран турнирный отбор[4]. Данный метод можно описать следующим образом: из популяции, содержащей особей, выбирается случайным образом особей и лучшая особь записывается в промежуточную популяцию (между выбранными особями проводится турнир). Это операция повторяется раз. Затем особи в полученной промежуточной популяции скрещиваются (также случайным образом). С ростом параметра ужесточается отбор между особями, т.к. если у особи низкий показатель приспособленности, у нее нет шансов «завести потомство». Преимуществом данной стратегии является то, что она не требует дополнительных вычислений и упорядочивания особей в популяции по возрастанию приспособленности.

В качестве оператора скрещивания (кроссинговера) был выбран модифицированный одноточечный[5] кроссинговер. По принципу работы оператора похож на одноточечный кроссинговер Холанда но т. к. нам нельзя чтобы гены в хромосоме после скрещивания повторялись использовался модифицированный оператор кроссинговера. Например у нас имеются пара хромосом-родителей. Случайным образом выберем точку разреза , . После того как была выбрана точка разреза, мы переносим все гены до точки разреза из родителя 1 в первого потомка, а из родителя 2 во второго потомка. Для того чтобы закончить потомка нам нужно заполнить вторую часть хромосом; для этого мы начинаем переносить гены после точки разреза из родителя 1 во второго потомка, а из родителя 2 в первого, но когда мы встречаем повторяющийся ген в потомке мы его пропускаем, так двигаясь до самого конца генов родителей. Если у нас получается так, что гены потомка еще не до конца заполнены, то мы начинаем брать гены сначала родителя, т. е. делаем цикличный сдвиг хромосомы в лево. Проиллюстрируем все выше сказанное. Например у нас имеется точка разреза , хромосомы-родители рис. 2.

Рис. 2. Хромосомы-родители

Теперь применим к ним описанный оператор кроссинговера рис. 3.

Рис. 3. Хромосомы-потомки

Таким образом мы получили двух потомков со схожими значениями приспособленности.

Оператор мутации в генетических алгоритмах используется для того, что бы «выбивать» решения из локальных оптимумов, которые далеки от глобальных.
Для мутации генов использовался простой способ обмена двух генов. Например у нас есть такая хромосома рис. 4. Теперь выберем случайно два гена и поменяем их местами рис. 5.

Рис. 4. Хромосома до мутации

Рис. 5. Хромосома после мутации

Параметры подбирались методом проб и ошибок: алгоритм запускался с разными значениями параметров. Значение параметра считается «хорошим» если решения получились «хорошими». Вполне приемлемые результаты получались со следующими параметрами:

• порог вероятности мутации 0,01-0,1;
• размер популяции 20-30;
• параметр (количество особей в турнире);

Заполнение исходной популяции выполнялось случайным образом.

Отладка и тестирование проводились на ЭВМ типа IBM PC с процессором Intel Core i3 с ОЗУ-4Гб. Язык программирования C++. Были проведены исследования по определению эффективности предложенного генетического алгоритма. Проведенные экспериментальные исследования показали преимущество использования генетического алгоритма стандартным методам. Следующий пример показывает эффективность данного метода, на неком графе с . На рис. 6. случайная хромосома с общей суммарной длинной ребер .

Рис. 6. Случайная хромосома

После запуска алгоритма на 15 поколений общая суммарная длинна стала рис. 7.

Рис. 7. Лучшая хромосома на 15 поколении

Если перебрать все варианты размещения для данного графа легко убедится, что целевая функция графа принимает меньшее значения при таком размещении. На самом деле целевая функция для данного графа является многоэкстремальной и мы просто нашли один из ее экстремумов.

Результаты исследования позволяют сделать вывод о том, что предложенный подход к решению данной задачи оказывается эффективнее известных методов. Алгоритм хорошо подходит для графов больших размерностей, в таких случаях стандартные методы оказываются неэффективными по сравнению с методами эволюционного моделирования.

1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ.

2. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М.: ФИЗМАТЛИТ, 2003. — С. 264-275.

3. Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. Michigan Press, 1975.

4. Цой Ю.Р. Стратегии отбора и формирования нового поколения [Электронный ресурс] / Ю. Цой. — Режим доступа: www.qai.narod.ru/GA/strategies.html

5. Панченко, Т. В. Генетические алгоритмы: учебно-методическое пособие / под ред. Ю. Ю. Тарасевича. — Астрахань: Издательский дом«Астраханский университет», 2007. — С. 20.

Вы можете помочь и перевести немного средств на развитие сайта

Аннотация научной статьи по математике, автор научной работы — Старостин Н. В., Панкратова М. А.

Рассматривается задача отображения графа на граф , которая имеет место в процессе планирования выполнения параллельной задачи на многопроцессорной вычислительной системе. В общем случае задача является NP -трудной. Предложен гибридный генетический алгоритм решения.

Похожие темы научных работ по математике , автор научной работы — Старостин Н. В., Панкратова М. А.

GENETIC ALGORITHM TO SOLVE GRAPH MAPPING PROBLEM

The article considers a graph mapping problem (in general an NP-hard one) which occurs in the process of running a parallel task on a multiprocessor computing system. We propose a hybrid genetic algorithm to solve the problem.

Текст научной работы на тему «Генетический алгоритм решения задачи отображения графа»

Вестник Нижегородского университета им. Н,И. Лобачевского, 2 013, № 5 (1), с. 204-209

ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ОТОБРАЖЕНИЯ ГРАФА © 2013 г. Н.В. Старостин, М.А. Панкратова

Нижегородский госуниверситет им. Н.И. Лобачевского

Поитупила в редакцию 14.05.2013

Рассматривается задача отображения графа на граф, которая имеет место в процессе планирования выполнения параллельной задачи на многопроцессорной вычислительной системе. В общем случае задача является ^У-трудной. Предложен гибридный генетический алгоритм решения.

Ключевые илова: параллельная вычислительная система, отображение графа на граф, генетический алгоритм.

Процесс назначения параллельной программы на узлы многопроцессорной вычислительной системы сопряжен с задачей отображения графа на граф, в которой требуется минимизировать временные затраты на обмен информацией между параллельными частями задачи. Данная задача известна в литературе [1-4] как задача оптимального отображения виртуальной топологии параллельной задачи на физическую топологию вычислительной системы. К алгоритмам решения данной задачи предъявляются особые требования, связанные со временем поиска решения (задачи имеют большую размерность и являются ресурсоемкими, а время их решения должно быть намного меньше, чем время выполнения задачи, назначаемой на вычислительную систему). В работе рассматривается эвристический алгоритм, который осуществляет направленный перебор решений генетическим методом совместно с известными конструктивными и итерационными схемами решения.

Математическая постановка задачи

Физическая топология вычислительной системы моделируется неориентированным графом Н (V, Р, Е), где V – множество всех сетевых устройств вычислительной системы;

Р Чр^^Рп>е V – вычислители (ядра, процессоры, узлы); Е с V(2> – непосредственные двунаправленные связи между элементами вычислительной системы. Неориентированный граф G(Q, с) определяет структуру виртуальной топологии, где Q = ^. qn> – множество вершин; С с Q Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Обозначим через (а у )пхп матрицу смежности

графа топологии О.

Варьируемым параметром является матрица назначения X = (ху )пхп, где х^ =1, если элемент

qi е Q виртуальной топологии приведен в соответствие с вычислителем р 1 е Р ; х ^ = 0 в

В задаче отображения требуется минимизировать издержки на коммуникации. Если исходить из суммарных затрат на коммуникацию, то критерий примет вид:

^Биы (Х) = Ц ау ‘I II ХіІХуАк

Можно минимизировать самые «дорогие» коммуникации, тогда критерий можно записать в виде

Рылх (Х) = тах ау-| II ^ min. (5)

Критерии (4) и (5) в общем случае являются противоречивыми. Задачу (1)-(4) будем называть задачей отображения с аддитивным критерием. Задачу (1)-(3), (5) будем называть задачей отображения с минимаксным критерием.

В общем случае задачи отображения с критериями (4) и (5) являются #Р-трудными в сильном смысле [5]. Можно привести частные случаи, когда задача сводится к задаче равномерного разбиения графа на два подграфа с минимизацией внешних связей или к задаче поиска гамильтонова цикла минимальной длины. Данные задачи являются NP -трудными в сильном смысле [6].

Таким образом, число допустимых решений для задач отображения равно п!, где п – размер графа виртуальной топологии О . На практике размеры задачи определяются числом функциональных устройств (ядер процессоров) вычислительных сетей. Так, например, один из самых производительных суперкомпьютеров в мире Tianhe-1A (Китай) содержит 186 368 ядер. Один из самых производительных суперкомпьютеров в России «Ломоносов» (МГУ) содержит 35 776 ядер. Это говорит о том, что порядки прикладных задач – сотни тысяч. Использование точных методов для решения прикладных задач не представляется возможным.

Задача (1)-(3) с критериями (4) и (5) в силу #Р-трудности и больших порядков входных данных не позволяет использовать точные методы решения (полный перебор, метод ветвей и границ). На практике часто бывает важно найти не оптимальное решение, а быстро получить достаточно «хорошее» решение (за счет оптимизации межпроцессорных коммуникаций время выполнения параллельной программы должно сокращаться на величину большую, чем время решения задачи отображения). В основе конструктивных алгоритмов лежит стратегия поиска и назначения структурно похожих фрагментов графов, например, клик [2]. Решения, полученные при помощи конструктивных эвристик можно улучшать итерационными методами, которые основаны на анализе окрестностей решений и последовательном переходе в локальный оптимум. Главный минус обозначенных подходов в том, что они не позволяют преодолевать локальные экстремумы сложных ландшафтов. Имеется множество различных подходов, позволяющих устранить эти недостатки.

Примером может служить метод Simulated Annealing [7]. В данной работе предлагается гибридный алгоритм, который основан на генетической оптимизации [6].

Структура генетического алгоритма

В качестве символьной модели выбрано представление решения в виде перестановки. Элемент

перестановки xt, i = 1, n, означает, что вершина i

графа G назначается на вершину xt графа H.

Предлагаемый генетический алгоритм стартует с начальной популяции Р0 (совокупности кодировок (Xj0. XП)) и итеративно выполняет следующий цикл операций:

1. Генерация начальной популяции (формирование с помощью конструктивных алгоритмов множества начальных решений).

2. Выбор родительских пар. Происходит случайным образом с равными вероятностями.

3. Кроссовер. Конструирование новых кодировок путем комбинации фрагментов родительских решений.

4. Мутация. Имеет место на кодировках потомков, основана на случайных обменах в перестановках.

5. Локальная оптимизация. Специальный оператор (не свойственен классическому генетическому алгоритму), предназначен для улучшения качества найденных решений.

6. Оценивание. Построение по кодировке решения задачи, вычисление критерия для решений, полученных в процессе текущего поколения.

7. Переход к следующему поколению. Происходит путем отбора необходимого количества лучших решений с точки зрения функции цели (4).

Генерация начальной популяции

Конструктивные алгоритмы являются детерминированными, что не позволяет сгенерировать необходимое количество различных решений для построения начальной популяции. Выход из данной проблемы заключается во введении элементов рандомизации в алгоритмы. В предлагаемом алгоритме генерация начальных решений осуществляется согласно процедуре построения корневой структуры смежности графов [8] (нужное разнообразие решений достигается за счет случайного выбора корневых вершин исходных графов) и с помощью модификации алгоритма, предложенного в [2].

Конструктивный алгоритм 1

На входе: графы физической и виртуальной топологий Н и О . Результат: перестановка.

1. Рекурсивное выделение клик в графах Н и О [2].

2. Переупорядочивание графов согласно выделенным кликам.

3. Назначение вершин графов согласно произведенному упорядочиванию.

4. Генерация перестановки назначения.

Конструктивный алгоритм 2

На входе: графы физической и виртуальной топологий Н и О . Параметры алгоритма: необходимое количество решений п. Результат: заданное количество перестановок.

1. Формирование списков из п вершин с минимальной степенью для графов Н и О .

2. Цикл 3-7 по числу решений п.

3. Выбор текущих вершин из построенных списков в качестве корневых.

4. Упорядочивание графов Н и О с помощью профильной схемы [8].

5. Назначение вершин графов согласно произведенному упорядочиванию.

6. Генерация перестановки назначения.

7. Переход к следующим вершинам в списках.

Целью кроссовера является генерация новых решений, которые получаются комбинацией фрагментов родительских перестановок. В качестве оператора кроссовера можно выбрать любую классическую схему порядкового кроссовера [6], которая гарантированно из перестановок получает новые перестановки. Проблема классических схем в том, что они не учитывают специфику задачи, что в итоге приводит к низкой вероятности получения потомков, по качеству лучших или сравнимых с родительскими решениями. Важно, чтобы кроссовер сохранял в потомках лучшие «фрагменты» родительских решений. Предлагается такая модификация позиционного кроссовера, которая в отличие от классической схемы активно эксплуатирует информацию о структуре графов физической и виртуальной топологий.

Алгоритм модифицированного позиционного кроссовера

На входе: графы физической и виртуальной топологий Н и О , родительские решения

ХРаГеп, и Хр,аГеп,. Параметры алгоритма к – объем копируемой информации из первого родителя. Результат: новые решения Х1Ш и х]ыи.

1. В перестановке родителя Х1рагеп1 (х1, х2. хп) выбираются пары элементов (х1, ху), для которых существует ребро (г, у) в графе О.

2. Для всех таких пар рассчитывается расстояние между вершинами х1 и ху в системном графе Н.

3. Пары сортируются в порядке возрастания рассчитанных расстояний.

4. Из полученного списка выбирается к связей с наименьшими расстояниями.

5. Элементы каждой выбранной пары (х, ху) копируются в перестановку потомка

Хиы на свои места.

6. Позиции, оставшиеся незаполненными

в перестановке потомка Х1сШ, заполняются согласно порядку значений в перестановке Х^агеп1.

7. Алгоритм модифицированного позиционного кроссовера генерирует генотип второго потомка для тех же родителей, меняя их роли местами.

Локальная оптимизация призвана улучшать решения, сгенерированные в результате работы оператора кроссовера и мутации. Суть предлагаемого оператора заключается в исследовании окрестности относительного обмена для заданной перестановки – решения из окрестности получаются посредством парных обменов в перестановке текущего решения. Т.к. обмен каждого элемента перестановки с каждым занимает достаточно много времени и не является разумным, то предлагается алгоритм локальной оптимизации, который оперирует не только информацией о перестановке, представляющей решение, но и информацией о структуре графов, описывающих физическую топологию вычислительной сети и виртуальную топологию задачи. Алгоритм выделяет элементы перестановки, соответствующие самым длинным связям между задачами, и пытается их уменьшить путем парных обменов с остальными элементами перестановки.

Алгоритм локальной оптимизации

На входе: графы физической и виртуальной топологий Н и О, решение Х. Параметры алгоритма: к – часть связей виртуальной топологии, с которой будет оперировать алгоритм. Результат: улучшенное решение R .

Сравнение результатов алгоритма с оптимальным решением задач

Количество вершин в графах Оптимальное решение Результат работы алгоритма

Характеристики тестовых графов физической топологии

Ыомер Ыазвание Количество вершин Количество ребер

4 mesh1em148 48 129

5 bcsstk0148 48 176

б GD06 theory 100 180

7 can 144 138 544

8 can 161 161 608

9 grid1 dual224 224 420

10 grid1 252 476

1. В перестановке решения Х(х1,х2. хп) выбираются пары элементов (х1, ху), для которых существует ребро (‘, у) в графе О.

2. Для всех таких пар рассчитывается расстояние между вершинами х1 и ху в системном графе Н.

3. Пары сортируются в порядке убывания рассчитанных расстояний.

4. Из полученного списка выбирается часть к связей с наибольшими расстояниями.

5. Для каждой выбранной пары (х, ху) рас-

сматриваются перестановки, полученные методом парных обменов х1 с х1, х1 с х2, . х1 с

хп, х, с х,, х, с х2, ., х, с хп. Каждая из этих

п у и 1 у и 2 у ”и п

перестановок оценивается, и выбирается наилучший вариант обмена.

Предложенный алгоритм решения поставленной задачи является эвристическим, поэтому дать объективные оценки решений, получаемых этим методом, достаточно проблематично. Для подтверждения работоспособности разработанного алгоритма будем сравнивать решение, сгенерированное алгоритмом, с оптимальным решением

задачи (на искусственно сгенерированных задачах с известным оптимальным решением). Также будем сравнивать результаты работы алгоритма с результатами работы ряда известных алгоритмов на общедоступных тестовых задачах.

Для первой части эксперимента было разработано 5 искусственных примеров с известным оптимальным решением. Характеристики тестовых задач и результаты работы алгоритма представлены в табл. 1.

Тестовые задачи для второй части эксперимента были выбраны с ресурса [9]. Характеристики графов топологии вычислительной системы представлены в табл. 2.

Характеристики графов виртуальной топологии задачи представлены в табл. 3.

В табл. 4 представлено сравнение результатов разработанного гибридного генетического алгоритма с результатами ряда известных алгоритмов.

Из полученных результатов видно, что предлагаемый гибридный генетический алгоритм решения задачи отображения показывает лучшие результаты на тестовых задачах по сравнению с известными алгоритмами.

В работе рассмотрена актуальная задача отображения графа на граф. Описан ряд практически

Ыомер Ыазвание Количество вершин Количество ребер

2 Trefethen 20b 18 59

3 karate24 24 Зб

5 bcspwr0248 48 55

б bfwb6248 48 107

8 bcsstk22 138 279

9 dwt 161 161 468

10 dwt 245224 224 555

11 lshp_265 252 696

Сравнение результатов алгоритма с известными конструктивными методами

Граф системы Граф задач Конструктивный алгоритм 1 Конструктивный алгоритм 2 Гибридный генетический алгоритм

Результат Время (мс) Результат Время (мс) Результат Время (мс)

1 1 64 46 58 22 54 631

1 2 125 28 148 31 125 1399

2 3 68 30 54 40 47 1032

3 4 199 32 222 41 167 3668

4 5 121 54 157 57 76 4928

5 б 218 82 226 83 158 8710

б 7 658 86 674 63 493 52493

7 8 617 98 1039 38 409 130555

8 9 961 61 1875 64 680 258202

9 10 2685 192 3790 89 1446 478133

10 11 3590 108 4263 64 1793 729622

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

1. El-Rewini H., Lewis T.G., Ali H.H. Task Scheduling in Parallel and Distributed Systems. Prentice Hall, 1994.

2. Chen S., Eshaghian M.M. A fast recursive mapping algorithm. Department of computer and information science New Jersey institute of technology Newarc, NJ 07102.

3. Bokhari S.H. On the Mapping Problem// IEEE Transactions on computers. 1981. V. C-30. №. 3.

4. Walshaw C., Cross M., Everett M.G., Johnson S., et. al. Partitioning & Mapping of Unstructured Mashes to Parallel Machine Topologies. Parallel Processing Group, Centre for Numerical Modelling & Process Analysis. University of Greenwich, London, SE18 6PF.

5. Hoefler T., Snir M. Generic Topology Mapping Strategies for Large-scale Parallel Architectures. University of Illinois at Urbana-Champaign Urbana, IL, USA. 2011. Р. 75-85.

6. Батищев Д.И., Костюков В.Е., Неймарк Е.А., Старостин Н.В. Решение дискретных задач с помощью эволюционно-генетических алгоритмов. Н. Новгород: Изд-во ННГУ, 2011.

7. Аладышев О.С., Киселёв Е.А. Алгоритм эффективного размещения программ на ресурсах многопроцессорных вычислительных систем // Междунар. журн. Программные продукты и системы. 2012. № 4. С. 18-25.

8. Pissanetzki S. Sparse Matrix Technology. Centro Atomico Bariloche. Bariloche, Argentina, 1984.

9. Коллекция разреженных матриц Университета Флориды. URL: http://www.cise.ufl.edu/research/spar-se/matrices/.

GENETIC ALGORITHM TO SOLVE GRAPH MAPPING PROBLEM

N. V. Starostin, M.A. Pankratova

The article considers a graph mapping problem (in general an NP-hard one) which occurs in the process of running a parallel task on a multiprocessor computing system. We propose a hybrid genetic algorithm to solve the problem.

Keywords: parallel computing system, graph mapping, genetic algorithm.