Материал: Основы автоматизации проектирования беспроводных систем и сетей связи. Семёнов Р.В

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

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

Генетический алгоритм – это поисковой алгоритм, основанный на природных механизмах селекции и генетики. Эти алгоритмы обеспечивают выживание сильнейших решений из множества сгенерированных, формируя и изменяя процесс поиска на основе моделирования эволюции исходной популяции решений. Генетические алгоритмы сконструированы таким образом, что при генерации каждой новой популяции используются фрагменты исходных решений, к которым добавляются новые элементы, обеспечивающие улучшение решений относительно сформулированного критерия отбора. Другими словами, генетические алгоритмы используют информацию, накопленную в процессе эволюции [23, 24].

При разработке генетических алгоритмов преследуются две главные цели:

–абстрактное и формальное объяснение процессов адаптации в естественных системах;

–проектирование искусственных программных систем, воспроизводящих механизмы функционирования естественных систем.

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

141

Основные отличия ГА от других алгоритмов оптимизации:

–используются не параметры, а закодированные множества параметров;

–поиск осуществляется не из единственной точки, а из популяции точек;

–в процессе поиска используются значения целевой функции, а не ее приращения;

–применяются вероятностные, а не детерминированные правила поиска и генерации решений;

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

Рассмотрим простой генетический алгоритм. Согласно репродуктивному плану Холланда генетические схемы поиска оптимальных решений включают следующие этапы эволюции:

142

Этап 1. Конструируется начальная популяция. Вводится начальная точка отсчета поколений t = 0 . Вычисляются приспособленность хромосом популяции (целевая функция) и средняя приспособленность всей популяции.

Этап 2. Устанавливается t = t +1 значение. Выбираются два родителя (хромосомы) для кроссинговера. Выбор осуществляется случайным образом пропорционально жизнеспособности хромосом, которая характеризуется значениями целевой функции.

Этап 3. Формируется генотип потомка. Для этого с заданной вероятностью над генотипами выбранных хромосом производится операция кроссинговера. Случайным образом выбирается один из потомков A(t ), который сохраняется как новый член

популяции. Далее к потомку A(t ) последовательно с заданными вероятностями применяются операторы инверсии и мутации. Полученный в результате генотип потомка сохраняется как А′(t ).

Этап 4. Обновление текущей популяции путем замены случайно выбранной хромосомы на А′(t ).

Этап 5. Определение приспособленности А′(t ) и пересчет средней приспособленности популяции.

Этап 6. Если t = t* , где t* – заданное число шагов, переход к этапу 7 в противном случае – переход к этапу 2.

Этап 7. Конец алгоритма.

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

Простой генетический алгоритм [23] включает операцию случайно генерации начальной популяции хромосом и ряд операторов, обеспечивающих генерацию новых популяций на основе начальной. Этими операторами являются репродукция, кроссинговер и мутация.

Репродукцией называется процесс копирования хромосом с учетом значений целевой функции, т.е. хромосомы с «лучши-

143

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

Если длина обрабатываемых последовательностей невелика, то в процессе мутации можно осуществить полный перебор возможных перестановок генов и найти комбинацию с максимальным значением целевой функции. При длине хромосомы L = 50..200 полный перебор вариантов становится затруднительным, поэтому здесь производится случайно-направленный поиск, который может быть реализован на основе простого генетического алгоритма.

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

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

2.Репродукция осуществляется на основе моделирования движения колеса рулетки.

3.Оператор кроссинговера реализуется как взаимный обмен короткими фрагментами двоичных строк гомологических хромосом.

4.Вероятность оператора кроссинговера принимается

равной P(CO)£ 1.0 .

5. Вероятность оператора мутации принимается равной

P(MO)³ 0.001 .

144

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

4.1. Выбор технологии построения

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

В настоящее время на телекоммуникационном рынке наиболее популярными являются технологии БД LTE, WiMAX, и Wi-Fi [1, 2]. Для сравнения этих технологий используем следующие показатели конкурентоспособности: q1 –

стоимость затрат на закупку оборудования и развертывание технологии в заданном локальном территориальном районе; q2 – максимальная дальность радиосвязи или радиус зоны об-

служивания базовой станции (БС); q3 – перечень услуг, предоставляемых пользователям; q4 – безопасность (целостность) информации, определяющая, что данные не будут изменены при хранении и передаче информации; q5 – пропускная способность каналов связи (максимальный трафик, который способна поддерживать система); q6 – надежность обеспечения радиосвязи; q7 – помехозащищенность; q8 – мобильность абонента; q9 – сложность решения задач частотного обеспече-

ния (выделение полос частот для беспроводных технологий, присвоение частот базовым станциям).

Выбор показателей в каждом конкретном случае индивидуален и обусловлен тем, что, по мнению экспертов (операторов связи), именно эти показатели наиболее сильно влияют

145