Строительные исследования
страница - 0
ИСПОЛЬЗОВАНИЕ МЕТОДОВ ЭВОЛЮЦИОННОГО МОДЕЛИРОВАНИЯ ДЛЯ ПОИСКА КВАЗИОПТИМАЛЬНЫХ СТРУКТУР СЕТЕЙ КАМПУСОВ
Пятаев О.В. (pytaev@kis.ru)
Нижегородский Государственный Технический Университет
Задача оптимизации структуры сетей кампусов достаточно актуальна. В то же время эта задача очень сложна вследствие ее большой размерности и целочисленности параметров. Формулировка задачи структурной оптимизации кампусной сети приводится в [1]. Под определением структуры кампусной сети будем понимать определение топологии сети (способа объединения узлов сети), выбор пропускной способности каналов связи, определение размещения коммутаторов, выбор моделей коммутаторов. В качестве критерия оценки решений принимается стоимость создания проектируемой кампусной сети. Показатели надежности и производительности сети задаются в виде ограничений. В настоящей статье рассматривается один из вариантов решения этой задачи, основанный на известном методе эволюционного моделирования - генетическом алгоритме.
Термин «генетический алгоритм» (ГА) был введен в 1975 году Д.Голдбергом, и обозначает раздел эволюционного моделирования, заимствующий методические приемы из теоретических положений популяционной генетики [2]. Идея ГА основывается на использовании принципов, лежащих в основе процессов эволюции для поиска глобального экстремума многоэкстремальной функции. При решении задачи с помощью ГА ее параметры задачи кодируются в виде бинарной цепочки, называемой хромосомой. Алгоритм оперирует с множеством хромосом, или популяцией. Каждой хромосоме ставится в соответствие функция приспособленности, которая обычно прямо пропорциональна целевой функции задачи проектирования. Во время работы алгоритма происходит эволюция популяции хромосом, в процессе которой улучшается средняя приспособленность популяции. Новые хромосомы образуются в результате действия генетических операторов (ГО) на хромосомы из старой популяции. Чем выше уровень приспособленности хромосомы, тем чаще она участвует в порождении новых особей. Постепенно значения хромосом сходятся к оптимальному решению. К достоинствам ГА относятся высокая скорость поиска решения сложных задач, возможность распараллеливания вычислений, комплексная, а не поэтапная оптимизация задачи.
Электронный журнал «ИССЛЕДОВАНО В РОССИИ» 96 1 http: zhurnal.ape.relarn.ru/articles/2001/087.pdf
Мы применяли ГА к решению задачи оптимизации структуры кампусной сети по следующей схеме. В качестве особей популяции выступают различные структуры сети. Функция приспособленности особи равна стоимости синтезируемой сети. Чем меньше значение функции, тем приспособленней считается особь. Порождение новой структуры сети проходит в два этапа. На первом этапе путем применения различных ГО к старым структурам синтезируется новая топология сети. На втором этапе с помощью специального алгоритма однозначно определяются оптимальные для синтезированной топологии пропускные способности каналов связи, число каналов связи и модели коммутаторов, стоимость сети. Нами рассматривалось два варианта реализации первого этапа алгоритма. Первый вариант заключается в кодировании матрицы, описывающей топологию сети, в виде бинарной цепочки, и использовании стандартных ГО, оперирующих с хромосомами. Использование стандартных ГО приводит к получению топологий сети, не всегда удовлетворяющих топологическим ограничениям, в частности требованиям древовидности структуры. Для исправления таких структур в алгоритм приходиться добавлять стадию «ремонта» хромосомы, который отнимает значительное время. Результаты исследования алгоритма, работающего по данной схеме, приводятся в статье [3].
Второй вариант реализации первого этапа алгоритма заключается в использовании специализированных ГО, позволяющих сразу получать топологии, удовлетворяющие ограничениям. При действии специализированных ГО структура сети представляется в виде неориентированного мультиграфа. Множество разрешенных ребер в графе делится на два подмножества - ребра, соединяющие абонента с коммутатором (АК), и ребра, соединяющие коммутатор с коммутатором (КК). Ребра, соединяющие абонента с абонентом, являются запрещенными. Было разработано четыре специализированных оператора: графовый кроссовер, графовая мутация, оператор удаления коммутатора, оператор замены коммутатора. Приведем описание этих операторов.
Графовый кроссовер. Есть две родительских структуры (СР), представленных графами Г1=(Г1,Я1), Г2=(Г2,Я2). На базе этих структур требуется получить две структуры-потомка (СП) Г1 =(V ,Rj), Г2 =(V2 ,R2), образующихся смешиванием ребер первой и второй СР.
Пусть Ro=RirR2 - множество каналов связи, совпадающих у СР1 и СР2; R*=RjuR2-R0 -множество каналов связи, различных у СР1и СР2. На первом этапе действия оператора считаем, что Г1 =Г1, Г2 =Г2. Разделим множество R* на два подмножества R*=RauRk, где RaaR* -подмножество ребер вида АК, RczR* - подмножество ребер вида КК.
Формирование структуры потомка производится в два этапа. На первом этапе создаются абонентские подключения структур потомков, на втором этапе формируются магистральные подключения.
Шаг 1. Создание множества связей АК структур-потомков.
Электронный журнал «ИССЛЕДОВАНО В РОССИИ» 962 http: zhurnal.ape.relarn.ru/articles/2001/087.pdf Шаг 1.1. Пусть A* - множество всех вершин-абонентов, инцедентных ребрам из множества
Ra, m - мощность этого множества. Выбираем случайное число m1 абонентов, 1 < mi < m-1, из
множества A*, сформировав множество Ai*cA*.
Шаг 1.2. Удаляем из множества R1 все ребра, инцедентные абонентам множества A1*
(обозначим множество таких ребер как R1(A 1 *)): R1 =R1 - R1(A 1 *). Этим удалением мы отключаем в
СП1 абонентов множества A1* от коммутаторов. Аналогичную операцию проводим с СП2: R2 =R2 -
R2(A1*).
Шаг 1.3. Добавляем к множеству R1 ребра из множества R2, инцедентные вершинам из множества A1*: R1 =R1 uR2(A1*). Таким образом, мы подключаем отключенных на шаге 1.2 абонентов в СП1 с помощью подключений, взятых в СР2. Аналогичное подключение проводим в СП2: R2 =R2 uRXA1*).
Шаг 2. Формируем соединения коммутаторов в структурах-потомках.
Шаг 2.1. Пусть mk - мощность множества Rh. Случайным образом разобьем множество R на два подмножества с мощностью mk/2 каждый: Rk=Rk1KjRk2, R1nRk2=0.
Шаг 2.2. В СП1 и СП2 удаляем все связи вида КК: R1=R1 - R1(K1); R2=R2 - R2(K2).
Шаг 2.3. В структурах-потомках выбираем случайные стартовые коммутаторы: k1s в СП1 и k2s в СП2.
Шаг 2.4. Множество коммутаторов СП1 делим на два подмножества: K1°nK11=0. Здесь K1° - множество связанных коммутаторов; K11 - множество изолированных коммутаторов. На этом шаге множество K1° состоит из одного стартового коммутатора: K1°={k1s}. Аналогично разбиваем множество K2: K2=K2° kjK2 , K2°nK21=0, K2°={k2s}.
Шаг 2.5. Для СП1 ищем ребро rtj, соединяющее любую вершину из множества K1° с вершиной из множества K11. Поиск такого ребра производим в следующем порядке:
1 . Ищем ребро в множестве R°.
2.Если в R°° такое ребро не найдено, то производим поиск в множестве Rk1.
3.Если ребро не найдено в Rk1, то выбираем случайным образом ребро из списка всех возможных ребер.
Найденное ребро rj добавляем в множество R1. Подключенный коммутатор переводим из множества K11 в множество K1°.
Аналогично для СП2 ищем ребро, соединяющее любую вершину из множества K2° с вершиной из множества K21.
Шаг 2.6. Если множества K11 и K21 - не пустые, переходим на шаг 2.5. Если множества K11 и K21 - пустые, то все коммутаторы подключены в сеть, действие оператора считаем законченным.
Графовая мутация. Есть СР, представленная графом Г=(У,К). На базе этой структуры необходимо получить СП Г = (V ,R ). На первом этапе действия оператора считаем, что Г = Г.
содержание:
[стр.Введение] [стр.1] [стр.2] [стр.3]