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

С.В.Галенко (s-galenko®hotmail.com) Институт проблем передачи информации РАН

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

Ключевые слова: беспроводные сети передачи данных, емкостная задача размещения с одним источником, генетический алгоритм, гибридный алгоритм.

1. Введение

В последние годы беспроводные сети передачи данных получили стремительное развитие во всем мире. Возрастающая популярность беспроводных сетей, особенно, работающих на базе семейства протоколов стандарта IEEE 802.11 и IEEE 802.16, приводит к увеличению количества и масштаба сетей этого типа. Сети беспровод­ного доступа, в которых количество базовых станций насчитывается несколькими десятками, давно стали обычным явлением. Популярность беспроводных сетей объ­ясняется наличием целого ряда присущих им достоинств [1]. Таким образом, остро встает вопрос о проектировании беспроводных сетей, что предполагает решение множества сложных взаимосвязанных задач.

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

—    подключаются все наперед заданные клиенты;

—    каждый клиент подключается только к одной базовой станции;

—    к каждой базовой станции может быть подключено лишь определенное, наперед заданное количество клиентов;

—    обхождение областей нежелательного попадания электромагнитного излучения (требования экологичности).

© 2005, Институт динамики систем и теории управления СО РАН, Иркутск, Россия

2. Постановка задачи

Будем рассматривать задачу со следующими условиями. Пусть имеется набор мест I = (1,..., п), в которых молено разместить базовые станции. Каждая базовая стан­ция имеет определенную емкость сц > 0, г G I, выраженную в Мбит/с или в допустимом количестве подключаемых к ней клиентов. Задан набор мест рас­положений клиентов J = (1,...,т), каждый из которых имеет свою потребность в полосе пропускания bj > 0, j £ J, и каждый клиент должен быть подключен только к одной базовой станции. Существует фиксированная цена установки базовых станций fi > О, г € I, если базовая станция установлена в г-м месте-кандидате, и фиксированная цена подключения клиентов с у > 0, г £ I, j G J, если j-й клиент подключается к базовой станции, установленной в г'-м месте-кандидате. Необходимо установить базовые станции среди подмножества потенциальных мест размещения S С I, S ^ 0 так, чтобы все клиенты были подключены, емкостные ограничения базовых станций не нарушались, а суммарная стоимость, состоящая из фиксированных цен установки базовых станций и цен подключений клиентов, была минимальной.

Введем следующие обозначения: ж у = 1, если клиент j подключен к базовой станции, размещенной в г-м месте-кандидате, х ij = 0 в противном случае, и у j = 1, если в1-м месте-кандидате установлена базовая станция, у j = 0, в противном случае. Теперь, в линейно-целочисленном виде задачу можно сформулировать так:

Ограничения (2) гарантируют, что будут подключены все клиенты, причем каж­дый клиент подключается только к одной базовой станции. Ограничения (3) связаны с ограничениями, накладываемыми на емкости базовых станций, а также обеспечи­вают подключение клиентов только к установленным базовым станциям. (4) и (5) накладывают на переменные ограничения целочисленности.

В литературе такую задачу общепринято называть емкостной задачей размеще­ния с одним источником. Ее изучению посвящены рыботы: [4], [5], [6], [7] и др. В большинстве статей для решения задачи используют Лагранжевы эвристики.

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

3. Генетические алгоритмы

3.1.   Представление данных

Первым шагом в разработке генетического алгоритма для данной задачи являет­ся создание удобного представления данных. Для емкостной задачи размещения с одним источником обычное двоичное представление переменных в виде 0 и 1 неудобно, поскольку потребуются двоичные строки длины т х п и, в тоже время, это не гарантирует того, что ограничения связанные с подключением клиентов и емкостные ограничения не будут нарушены. Для того чтобы избежать вышеописан­ной ситуации с нарушениями ограничений, будем использовать представление, где каждая хромосома является m-мерным вектором, состоящим из целых чисел от 1 до п: целое число, находящееся на j-м месте обозначает номер места-кандидата, в котором расположена базовая станция, и к которой подключен j'-й клиент. Далее, будем применять название "г-я базовая станция", подразумевая под этим базовую станцию, установленную в г-м месте-кандидате. Так, например, если п = 3 и т = 7, хромосома {2, 1, 3, 1, 1, 2, 3} представляет одно из возможных решений задачи, где клиенты 2, 4, 5 подключены к базовой станции с номером 1, клиенты 1, 6 - к базовой станции с номером 2, а 3 и 7 - к базовой станции с номером 3. Введем следующее обозначение:

Si = 0, если 22 bj < Щ

и

Si = \щ — 2_,bj\,B противном случае,

где J? - множество клиентов, подключенных к г-й базовой станции. Теперь можно говорить, что решение является допустимым, только в том случае, если Si = 0, Уг G 7". Следовательно, степень недопустимости решения (жу,Уг) будет

u{xij,yi) = ^2 s^ iei

Для сравнения качества допустимых и недопустимых решений х будем использо­вать две функции: z(x) и и(х), где z(x) - целевая функция, а и(х) - сумма величин нарушений емкостных ограничений. Таким образом, при сравнении двух решений х\ и Ж2 будем говорить, что решение х\ лучше решения Ж2, если и{х\) < и(х2) или

и(х\) = и(х<2) И z(x\) < z{x,2)-

3.2.   Псевдокод генетического алгоритма

Общий вид псевдокода генетических алгоритмов представлен как Genetic AlgorithmQ. В этом псевдокоде используются пять процедур: Init_Pop (), Cros_Sol(), Mut_Sol(), Eval_Sol() и Imp_Sol(). Процедура Init_Pop является процедурой инициализации популяции, Cros_Sol() и Mut_Sol() - генетические операторы скрещивания и му­тации и Imp_Sol() - процедура, с помощью которой делается попытка улучшить качество определенного решения. Процедура Eval_Sol() служит для оценки качества

3

хромосомы, измеряя две различные величины: цену z(x) и степенв допустимости решения и(х).

Общий вид генетических алгоритмов:

Procedure Genetic Algorithm();

Инициализируем популяцию, исполвзуя Init_Pop();

foreach x G Pop

х <— Imp_Sol(a;);

Оцениваем х с помощвю Eval_Sol(a;); for t = 1 to MaxGen

for к = 1 to MaxCross

Выбираем два индивида х\ и х%

New_a; <— Cros_Sol(a;i, x-i)\

New_a; -«- Mut_Sol(New_a;i);

Оцениваем New_a; с помощью Eval_Sol(New_a;);

New_a; «— Imp_Sol(New_a;); z -<— New_x.

3.3. Генетические операторы

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

Procedure Crossover! (); Инициализируем хромосому потомка:

СЫЫМ <- { ^Fatlierl^'L ^{если Fatherl}[i] = Father2[j]

\ 0, в противном случае; Выбираем произвольно одну из родительских хромосом: Fatherl; Выбираем произвольно число г € [0, т]; repeat

Устанавливаем а «— Fatherl [г]; Устанавливаем А -<— {j | Fatherl[j] = a}; foreach j £ A such that Child [j] — 0

if (j может быть подключен к а без нарушения емкостных ограничений базовой станции а ) then

Child[j] -<— а и обновляем емкость базовой станции; else

Устанавливаем /3 -(— Father2[j] и В <- {/ | Father2[/] = /3}; foreach I е В | Child[Z] = О ChildH <r- /3;

Обновить емкость базовой станции /3; until не существует j такое, что Child [j] = 0.

Procedure Crossover2();

Выбираем произвольно одну из родительских хромосом: Fatherl;

Создаем перестановку Р набора {1,2,..., т};

foreach j G J

Childfj] <- Fatherl [j]; foreach элемента P(j), j = 1,2,..., m

Заменяем в хромосоме потомка значение в позиции P(j) на

Father2[P[j]], если такая замена не нарушает емкостные

ограничения.

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

Procedure MutationlQ; Произвольным образом делаем переставку клиентов {«1,..., а_т}; foreach клиента j = 1,..., т

if (клиент j и otj подключены к разным базовым станциям) then Обменяться базовыми станциями.

Procedure Mutation2();

Произвольным образом выбираем одну установленную базовую

станцию а и неустановленную базовую станцию /3;

А 4— {з' | 3 подключен к базовой станции а};

foreach клиента j G А

Подключаем j к базовой станции /3.

5

4. Мультистарт и генетический алгоритм

Стратегия мультистарт позволяет более полно исследовать пространство поиска решения задачи по сравнению с традиционным использованием генетического ал­горитма, где может иметь место вырождение решений. Само название "мульти­старт "говорит о том, что на начальном этапе поиск повторяется несколько раз. Применительно к нашей задаче имеем следующее:

—    сам генетический алгоритм дает возможность после некоторого количества ите­раций избавиться от недопустимости решения (свести недопустимость к нулю);

—    на втором этапе выбирается лучшее решение из всей популяции и добавляется к элитной популяции;

—    процесс повторяется необходимое количество раз;

—    созданная элитная популяция, состоящая из лучших решений, используется генетическим алгоритмом для дальнейшего поиска.

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

Procedure Hybrid Algorithm!. ();

{Создаем элитную популяцию с помощью процедуры Genetic Algorithm()} while элитная популяция не создана do Procedure Genetic Algorithm(); elite_pop -<— New(x); {Применяем процедуру Genetic Algorithm() к полученной элитной популяции и находим решение} Procedure Genetic Algorithm(elite_pop).

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

5. Поиск с запретами и генетический алгоритм

Поиск с запретами (Tabu Search) является одним из наиболее используемых мета-эвристик. Основоположником алгоритма поиска с запретами является Glover [2]. Более детальное описание алгоритма можно найти в работе [3]. Поиск с запрета­ми активно использует историю поиска как для того, чтобы выйти из локального оптимума, так и для исследования пространства поиска.

Простой алгоритм поиска с запретами использует обычный локальный поиск, а также использует краткосрочную память, чтобы избежать зацикливания и для выхода из локального оптимума. Краткосрочная память используется как список запретов или табу, который содержит недавно посещенные решения и препятствует движению поиска по направлению к этим решениям. Таким образом, окрестность текущего решения ограничивается решениями, не принадлежащими списку запре­тов. Решения, не принадлежащие списку запретов, иногда называют разрешенным списком или разрешенным набором решений. На каждом шаге из разрешенного списка выбирается решение, производится поиск и это решение заносится в за­прещенный список, а одно из решений, уже находящихся в запрещенном списке, исключается из этого списка, например, с использованием очередности FIFO. Спи­сок запретов выбирается определенной длинны L которая, как правило, меньше мощности всего пространства поиска. При наличии маленькой продолжительности запрета, поиск сосредоточится в небольшой области части пространства поиска. И наоборот, если запрет будет более длинным, то это подтолкнет к исследованию боль­шего пространства поиска, поскольку будет запрещен возврат в большее количество решений.

В нашей задаче поиск с запретами будем применять по отношению к решениям-производителям, после того как они приняли участие в скрещивании и по отношению к новым найденным улучшенным решениям-потомкам:

Procedure Hybrid Algorithm2();

ИСПОЛЬЗОВАНИЕ ГИБРИДНЫХ АЛГОРИТМОВ...                                       7

Procedure Genetic Algorithm(); Инициализируем популяцию, используя Init_Pop(); foreachforeach x € Pop х •<— Imp_Sol(a;);

Оцениваем х с помощью Eval_Sol(a;); for t—1 to MaxGen

for k—1 to MaxCross

Выбираем два индивида х\ vl x% if x\ и Х2 fi TabuList then

New_a; -<— Cros_Sol(a;i,a;2); New_a; <- Mut_Sol(New_a;);

Оцениваем New_x с помощью Eval_Sol(New_a;); New_x •<— Imp_Sol(New_a:); Обновляем списки запретов; Обновляем условия аспирации; z -(— New х.

6. Выводы

В этой статье, для решения емкостных задач размещения с одним источником, предложен подход с использованием гибридных алгоритмов созданных на основе генетического алгоритма и стратегии поиска с запретами, а также генетического алгоритма и стратегии мультистарт. Результаты применения гибридных алгоритмов показали их перспективность для решения задач указанного выше типа, а также их преимущества по сравнению с просто генетическим алгоритмом. Результаты были получены с использованием стандартных тестовых задач [4], [5], [6], [7].

Список литературы

1.     Вишневский В.М. Теоретические основы проектирования компьютерных сетей. / — М.: Техносфера, 2003.

2.     Glover F. Future paths for integer programming and links to artificial intelligence. // Computers and Operations Research, —1986, —vol. 13, —p. 533-549.

3.     Glover F. and Laguna M Tabu Search. / Kluwer Academic Publishers, 1997.

4.     Holmberg K., Ronnqvist M. and Yuan D. An exact algorithm for the capacitated facility location problems with single sourcing. // European Journal of Operational Research, —1999, —vol. 113, — p. 544-559.

5.     Klincewicz J.G. and Luss H. A lagrangean relaxation heuristic for the capacitated facility location with single-source constraints. // Journal of the Operational Research Society, —1986, —vol. 37(5), — p. 495-500.

6.     Pirkul H. Efficient algorithms for the capacitated concentrator problem. // Computers and Operations Research, —1987, —vol. 14, —p. 197-208.

7.     Sridharan R. A lagrangean heuristic for the capacitated plant problem with single source constraints. // European Journal of Operational Research, —1993, —vol. 66, —p. 1305-312.