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

где Psl – масштабированная вероятность; Psi – вероятность отбора;

Pmin – минимальная вероятность в популяции; Pmах – максимальная вероятность в популяции.

Шаг 6. Начинается формирование новой популяции: производится элитный отбор, т.е. определенное число "старых" хромосом переносится в новую популяцию.

Шаг 7. Производится кроссинговер случайно выбранных хромосом.

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

Шаг 8. Переход к шагу 2, и цикл повторяется заданное число раз.

Шаг 9. Останов.

13.1.2. Применение генетических алгоритмов к задаче размещения радиоэлементов в корпусе устройства

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

ограничения пространства объема размещения (например,

габариты конкретного корпуса, определенные стандартом предприятия);

элементы размещения, заданные своими габаритами (объемами).

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

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

241

Исходными данными являются: а, b – габариты монтажного пространства; {(а1, b1), ..., (аi, bi), ..., (ап, bп)) – множество элементов размещения; С – матрица связей элементов размещения, представляющая собой матрицу связности. Необходимо найти вариант размещения элементов на монтажном пространстве

Z = ((x1, y1), ..., (xi, yi), ..., (xп, yп)),

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

Задача размещения ставится как задача оптимизации функции,

выражающей нормированную оценку суммы штрафа за перекрытие площадей размещаемых электронных радиоэлементов (ЭРЭ) и общей длины соединений:

F min (k O(L(z j )) P(Sобщ (z j )),

z j Z

где k – весовой коэффициент; O(L(zj)) – оценка общей длины соединений,

приведенная к интервалу [0, 1]; zj – вариант размещения; Р(Sобщ(zj)) –

функция штрафа за перекрытие площадей, принимающая значения из интервала [0,1]; Sобщ – общая площадь перекрытия площадей размещаемых элементов.

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

n n

Ldij cij , i1 j1

где dij – расстояние между позициями установки элементов

dij (xi x j )2 ( yi y j )2 ; сij – число связей между элементами i и j из исходной матрицы смежности С.

242

Нормирование общей длины соединений можно провести, вычисляя отношение L(zj) к Lmax, где

Lmax n2 a2 b2 ;

O(L(zj))= L(zj) / Lmax.

Общая площадь перекрытия вычисляется по следующей формуле:

n n

Sпер Sij ,

i1 j1

где Sij – площадь перекрытий элементов zi и zj,

Sij [0,5(a2 a1) x2 x1 ][0,5(b2 b1) y2 y1 ].

Функция штрафа за перекрытие площадей

P(Sобщ ) Sобщ/nab.

13.1.3. Исследование эффективности генетических алгоритмов для задачи размещения радиоэлементов в корпусе устройства

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

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

1. Хромосома представляет собой связанный список пар координат

243

центров тяжестей элементов размещения. Каждая координата описывается

вещественным числом.

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

3.Условие завершения эволюции задается в виде определения числа поколений либо в виде условия достижения нулевого перекрытия элементов.

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

Эксперимент проводился для значений вероятностей мутации в диапазоне от 0,1 до 0,6 с шагом 0,1. Значение вероятности более 0,6 нарушает сходимость функции оптимальности ГА.

Рис. 13.2. Диаграмма: длительность эволюции в зависимости от значения вероятности мутации

Кроме стандартного ГА, для решения задачи размещения можно использовать эволюционные стратегии: стратегию "только мутация" с

пропорциональным оператором селекции; стратегию с рекомбинацией

244

(т, k). Такой оператор рекомбинации предполагает т родителей и k

потомков. Параметры m и k устанавливает пользователь. Теоретически

следующие сочетания родителей и потомков: (2, 2), (3, 1), (3, 2), (3, 3),

(4, 1), (4, 2), (4, 3), (4, 4). Следует отметить, что при сочетании (2, 1) мы получаем в качестве оператора рекомбинации обычный одноточечный кроссинговер, в котором участвуют два родителя и один потомок,

выбираемый случайным образом. На рис. 13.3 и 13.4 показаны для сравнения виды графиков оптимальности генетического алгоритма.

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

это заметно по многочисленным "всплескам" на графике.

Рис. 13.3. График функции оптимальности ГА при одноточечном крассовере

245

Рис. 13.4. График функции оптимальности ГА при стратегии с рекомбинацией (m, k)

При применении мобильного генетического алгоритма на практике возникают трудности, как с формулировкой первоначальной популяции решений, так и с функцией оптимальности. Структура хромосомы представляет собой список пар координат, упорядоченных по номеру элемента: ((1, х1, y1), ..., (i, хi, yi), ..., (v, хv, yv)).

В мобильном генетическом алгоритме хромосома кодируется списком пар <номер гена, значение гена>. При решении задачи размещения номер гена совпадает с номером размещаемого элемента, а

значение гена – с парой координат. Таким образом, номер гена – это целое число, а координаты – два вещественных числа.

На этапе инициализации генерируется λ строк случайным образом.

Параметр λ – размер популяции, задается пользователем. Функция оптимальности для каждой хромосомы вычисляется, как площадь перекрытия элементов.

Эффективность мобильного ГА для задач структурного синтеза можно проверить на следующих четырех тестовых наборах: "большое монтажное поле и мало элементов размещения"; "много элементов размещения" (высокая плотность упаковки); "низкая плотность упаковки,

246

но разные элементы размещения"; "высокая плотность упаковки и велико разнообразие". Результаты экспериментов представлены в табл. 13.3.

Таблица 13.3 – Параметры стандартного ГА

В табл. 13.3 под четными номерами приведены результаты работы стандартного ГА, а под нечетными – мобильного ГА. На основании проведенных экспериментов можно сделать вывод о результативности мобильного генетического алгоритма.

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

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

2.Обосновать выбор всех параметров и критериев остановки работы генетического алгоритма.

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

247

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

ПРИМЕНЕНИЕ MATLAB ДЛЯ МОДЕЛИРОВАНИЯ НЕЙРОННОЙ СЕТИ ХЕББА

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

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

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

14.1.1.Формальные нейроны искусственных нейронных сетей

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

изображенный на рис. 14.1. На его входы поступает вектор Х = (х1, …, хп)

входных сигналов, являющихся выходными сигналами других нейронов, а

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

связей входных сигналов х1, …, хп; w0 – весовой коэффициент связи сигнала смещения.

248

w0

xn

wn

Рис. 14.1. Процессорный элемент, используемый в обычных нейросетях

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

Многие авторы при описании модели нейрона используют не сигнал смещения, а порог нейрона, что приводит к эквивалентной модели элемента. В этом случае выражения (14.2) и (14.3) принимают соответственно вид:

где

Графическое изображение бинарной и биполярной функций активации для этого случая представлено на рис. 14.2, а и 14.2, b.

Рис. 14.2. Функции активации нейронов

Из сопоставления выражений (14.1) – (14.3) и (14.4) – (14.6) следует,

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

Реже используются линейные бинарные или биполярные функции активации (рис. 14.2, с и 14.2, d):

где а равно нулю для бинарных выходных сигналов нейронов и а равно минус единице для биполярных сигналов; k, a0 постоянные коэффициенты.

250