Лаб_практикум_ОВИ_03_06_13

[x,fval,exitflag,output,population,score] = ...

ga(@ex2,nvars,[],[],[],[],[],[],[],options);

12.5. Применение генетических алгоритмов для поиска максимума

функции

Найдем максимум функции двух переменных вида:

z(x, y) exp( x2 y2 ) sin(x y).

В диалоговом окне ГА можно решить только задачи минимизации.

Для нахождения максимума функции f(x) следует минимизировать функцию –f(x). Это объясняется тем, что точка минимума –f(x) является некоторой точкой f(x), в которой достигается максимум.

Напишем M-файл для функции z(x) = –f(x) и сохраним его в текущей папке под именем ex13.m:

function z = ex13(x)

z=–(exp(–x(1)^2–x(2)^2)+sin(x(1)+x(2)));

Вызовем диалоговое окно с помощью gatool.

В поле fitness function введем имя целевой функции @ex13.

Установим значения параметров ГА: количество переменных, равное 2,

количество особей в популяции, равное 10, количество поколений, равное

100 (в окне критерия остановки алгоритма), начальный отрезок, равный

[–1; 3]. Для построения графиков в разделе plots установим флажки для best fitness, best individual, distance и нажмем кнопку start.

В результате завершения процесса в окне final point появится значение переменной x, соответствующее минимуму функции, а в окне

231

status and result можно увидеть найденное минимальное значение целевой

функции z(x).

Для данной задачи результаты получились следующие:

максимум функции достигается в точке x = 0.46419, y = 0.42406;

значение функции f(0.46419; 0.42406) = 1.449.

Также можно сконструировать другие ГА, моделируя операторы

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

Дальнейшее изучение оптимизации с помощью ГА можно продолжить, рассматривая Direct Search Toolbox. Для вызова окна можно в командной строке просто прописать psearchtool.

12.6. Индивидуальные задания

1.По номеру в журнале группы из табл. 12.1 выбрать функцию для определения экстремумов с помощью ГА в пакете MATLAB.

2.Осуществить поиск минимума и максимума выбранной функции с помощью командной строки и графического интерфейса ГА пакета

MATLAB, используя при этом функции gaoptimset и ga. При этом обосновать выбор всех параметров и критериев остановки работы ГА.

3. Просчитать время, затраченное на поиск экстремумов функции,

при реализации ГА с помощью командной строки пакета MATLAB.

4.Построить график функции для того, чтобы убедиться в правильности найденных с помощью ГА экстремумов.

5.Сгенерировать коды M-файлов для каждой задачи поиска экстремумов функции с помощью ГА.

6.Пояснить различие между полученными результатами при многократных запусках ГА во время поиска оптимального решения.

7.Оформите отчет по лабораторной работе.

232

Таблица 12.1 – Функции для определения экстремумов с помощью

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

233

Лабораторная работа 13

ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В ЗАДАЧАХ ОПТИМИЗАЦИИ

Цель лабораторной работы: получение и закрепление знаний,

формирование практических навыков применения генетических

алгоритмов к различным задачам оптимизации.

13.1.Краткие сведения из теории

13.1.1.Применение генетических алгоритмов к задаче оптимизации вычислительной сети

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

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

Для оптимизации трафика необходимо решить следующие инженерные задачи:

разработать и реализовать систему снятия статистики трафика на бэкбоне, состоящем из концентраторов;

разработать систему представления входных данных для генетического алгоритма (ГА);

234

разработать и реализовать генетический алгоритм.

Модель вычислительной сети организации

Опишем текущее состояние ВС с точки зрения оптимизации.

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

Каждый узел (рабочая станция) может быть подключен только к одному коммутатору/концентратору (комм/конц), таким образом каждый комм/конц определяет сегмент ВС. Разбиение узлов по комм/конц считаем известным.

Пусть в ВС имеется n комм/конц и т узлов. Обозначим узлы ui, i = 1, ..., m, а коммутаторы/концентраторы qj, j = 1, ..., n. Каналы связи между ql и qk будем обозначать Slk. Ограничения с точки зрения задачи размещения представлены ограничениями на допустимые длины каналов связи. Каналы Slk в большинстве реальных ВС соединены последовательно

(рис. 13.1). Каналы, замыкающие кольцо (на рис. 13.1 – точечная линия),

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

В контексте задачи существуют два вида каналов связи:

<узел> – <коммутатор/концентратор>;

<коммутатор/концентратор> – <коммутатор/концентратор>.

В любой ВС имеется т каналов первого типа (по числу узлов) и не более п · (п – 1)/2 – каналов второго типа.

235

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

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

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

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

упорядочены в соответствии с этими номерами. Позиция i содержит номер коммутатора/концентратора (от 1 до n), к которому подключен узел i.

Пример кодирования топологии ВС, изображенной на рис. 13.1, приведен в табл. 13.1.

Таблица 13.1 – Пример кодирования подключения узлов ВС

Для двоичного кодирования номера qi коммутатора/концентратора необходимо: [log2 n] бит, где [] – операция округления в большую сторону.

Для вышерассмотренного примера хромосома с использованием двоичного кодирования приведена в табл. 13.2.

Таблица 13.2 – Хромосома с двоичным кодированием

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

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

представляет собой последовательность операций:

237

случайный выбор гена (вероятность 0,001);

случайный выбор бита;

инверсия выбранного бита;

операция по модулю п над геном, содержащим результат инверсии modn(x).

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

Наибольшую важность имеет определение функции оптимальности хромосомы, так как определение влияет на сходимость эволюции. В

качестве функции оптимальности может быть взята следующая функция:

L – множество всех вариантов выбора коммуникационного оборудования;

K – количество каналов связи.

Вид коммуникационного оборудования значительно влияет на загруженность каналов связи. Реальная ВС часто содержит как коммутаторы, так и концентраторы. Улучшить пропускные способности каналов связи можно за счет оптимального выбора коммутаторов или концентраторов. Задача выбора коммуникационного оборудования задается на уровне каналов связи, каждый канал k характеризуется пропускной способностью – реальной Рk и максимальной Рkmax (бит/с).

Интенсивность взаимодействия (передачи сообщений) любой пары узлов – это величина Bij (бит/с). Величина Bij измеряется в течение длительного промежутка времени и усредняется. Усреднение может быть представлено или вычислением среднего значения Bijcp, или построением на основе гистограммы распределения вероятностей.

238

Суммарный трафик, приходящийся на канал связи, зависит от типа канала. Будем рассматривать только каналы типа:

<коммутатор/концентратор> – <коммутатор/концентратор>.

Тогда можно выделить следующие подвиды каналов:

<коммутатор> – <коммутатор>;

концентратор> – <концентратор>;

коммутатор> – <концентратор>.

Суммарный трафик выражается по-разному для трех подвидов каналов связи. Рассмотрим суммарный трафик канала типа

<коммутатор> – <коммутатор>:

n n

Tk Bij .

j M1 j M 2

Множество вершин М1 и множество вершин M2 – это множества узлов по одну и другую стороны от канала связи. Суммарный трафик канала <концентратор> – <концентратор> измеряется по-другому, так как канал, образованный концентраторами, составляет общую магистраль:

n n

Tk Bij .

j1 j1 i j i j

Суммарный трафик канала <концентратор> – <коммутатор> может быть вычислен следующим образом:

n n

Tk Bij .

j1 j M 2 i j

239

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

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

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

закодированном в хромосоме.

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

Шаг 4. Для каждой хромосомы вычисляется вероятность отбора

f – функция оптимальности; t – номер поколения; λ – размер популяции.

Шаг 5. Проводится масштабирование вероятностей отбора,

наибольшая вероятность принимается за единицу, наименьшая – за нуль,

остальные пропорционально масштабируются:

Psl Psi Pmin ,

Pmax Pmin

240