Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 35
Текст из файла (страница 35)
Нетрудно проверить, что МПЭ, реализующий функцию [(Х) =х,'/хохм будет иметь тнп т=1 и размерность вектора порогов й=-6 (рнс. 10.3,б), при векторе%= (4,2, 1) имеем т=--0 и й=! (рнс. 10.3,в). Задача синтеза оптимального линейного МПЭ, реализующего заданную БФ, заключается в нахождении такого вектора весов 237 входов %*, при котором размерность А вектора порогов Т была бы минимальной: (10.3.3) А*=й(%э) =тш Такая постановка задачи синтеза объясняется тем, что МПЭ с минимальным числом порогов имеет максимальную надежность функционирования и технически реализуется более просто, нежели элемент с большим числом порогов. Областью поиска вектора %* является и-мерное евклидова пространство весов входов <%>.
Заметим, что элементы в.аахм Ц ь ь ь о [%, Т, т) и [с%, сТ, т] (с> 0 — вещественное число) эквивалентны, поскольку онп реализуют одну и ту же БФ (этнм. в частности, обьясняется бесконечность множества решений задачи синтеза). Сле овательно п оиз- мне? и ° ° ° э ~ 2 3 с 5 б 1 тоо 23В д р вольный вектор % можно нормировать, т. е.
однозначно сопоставить с нич точку %', лежащую на поверхности и-мерной единичной гнперсферы а„с центром в начале координат. Таким образом, задача синтеза оптимального линейного МПЭ, реализующего заданную БФ, сводится к задаче нахождения точки %" ~а„, удовлетворяющей критерию (10.3.3). Прежде чем рекомендовать какой-либо метод решения поставленной задачи, изучим структуру пространства весов входов и выясним качественный характер поведения функций (10.3.1) и (10.3.2). ф !04. ИНДЕКСНЫЕ ЗОНЫ Пусть компоненты произвольной точки %ен<%> удовлетворяют условию (10.2.2). Тогда оператор (1О.!.! ) однозначно отображает множество булевых наборов (Х,,) (а=О, 1,... ...,2" — 1) на множество вещественных чисел 1,= — 1(Х,), лежащих на одной прямой.
Упорядочпм числа 1, (а=О, 1,, 2 — !) по возрастаншо: (10.4.1) (14 (...~(тл о Введем следующие определения (29). Определение 1. Индексом точки % называется вектор-строка Л'(%) = (ус,уь, у,). (10.4.2) Определение 2. Множество (%) точек с одинаковым индексом называется индексной зоной.
Содержательность данных определений покажем на примерах. Пример 4 (и=-2). Пусть %=(1,2), тогда 1,=-з, где з=(0,1, 2, 3). Следовательно индекс точки % равен й((%) = (О, 1, 2, 3). 1-1айдем множество (%) всех точек с таким же индексом. Пусть %=(шь газ) — произвольная точка с индексом (О, 1, 2, 3).
Тогда, в силу (10.4.1), получаем систему неравенств, определяющих индексную зону (%): 0 ~ га 1 ( газ ( щ ~ + шм последнее нз которых является лишним. Аналогично можно получить систему неравенств для индексной зоны, содержащей, например, точку %= (2, ! ): О~гиз~шь Можно показать, что других индексных зон в первом квадранте не имеется в виду с<неподвижности» взвешенных входных сигналов 14=0 и 1з — — га,+газ н очевидных неравенств: О ~шь гвг, ш1+ гвь Аналогично находятся индексные зоны для остальных квадрантов.
Все индексные зоны при п=2 показаны на рис. !0.4. 239 из А) адам А Ф и щам' б ю/ет Ж: аг и-мои ге~"- щз< щз (10.4.3) Тогда возможны два случая: а) щ~+вз<щз и б) из<ге~+гпь которым соответствуют две индексные зоны с индексами (О, 1, 2, 3, 4, 5, 6, 7) и (О„ 1, 2, 4, 3, 5, 6, 7). Поскольку веса входов можно упорядочить шестью способами типа (10.4.3), то всего впервом оптанте имеется 12 индексных зоп со следующими индексами: ,~ и;иек» и;езоб~,, Рис, 10Х Л'~ = (0,2, 1,3,4,6,5,7); Уа = (О, 2, 1, 4, 3, 6, 5, 7); й~з = (О, 2, 4, 1, 6, 3, 5, 7); Уа = (О, 2, 4, 6, 1, 3, 5, 7); йГз = (О, 4, 2, 6, 1, 5, 3, 7); Жа = (О, 4, 2, 1, 6, 5, 3, 7); '4т =(0,4,1,2,5,6,3,7): Уз =(0,4, 1,5,2,6,3,7); Мз =(О, 1,4,5, 2,3,6,7); Мм= (О, 1, 4, 2, 5, 3, 6, 7), йгц = (О, 1, 2, 4, 3, 5, 6, 7); йГм = (О, 1, 2, 3, 4, 5, 6, 7). Согласно (10.4.1), система неравенств, определяющих индексную зону с номером 12, имеет вид Заметим, что компоненты точек, лежащих на биссектрисах координатных углов, не удовлетворяют условшо линейной независимости (10.2.2) и, следовательно, не принадлежат индексным зонам.
Пример 5 (п=3). Найдем индексные зоны первого октанта. В этом случае гпь вм газ)0. Пусть веса входов упорядочены по возрастанию: гчп ( 0(га, (вз., гп!+таз(газ. (10.4.4) Если перейти к сферическим координатам ж,=о соя ~рз!и Й; газ=цз!п<рз(пР; гез=йсоз1г, то система (!044) примет следующий вид: 0(соз ~р~з!и га; з!и ~р+ соя ~р с!и Й. а ) Р.Ю Аналогичным способом находятся системы неравенств для других индексных зон. На рис. 10.5 показаны все индексные зоны первого октанта в плоскости (ср, !1). С ростом размерности и пространства весов входов количество 9, индексных зон, лежащих только в одном гнпероктанте, очень быстро возрастает (например„64=14Х4! =336; 6з=546Х5=-65520 и т.
д.). Точная 241 1б — м оценка величины В„в общем случае неизвестна, а верхняя граница 6„< (2")! является слишком грубой. Следует заметить, что индексная зона вполне характеризуется любой своей точкой (см. пример 4) и является односвязным выпуклым множеством [291, $ !О.а. СВОЙСТВА ФУНКЦИЯ а=а(%) и т=т(%) Произвольную БФ )(Х) будем задавать в виде вектора- строки ~(Х) = У4,)ь...,),. ), (10.5.1) где )з=)(Х,,), з=-О, 1,..., 2" — 1. Определение 3 (29). Проекцией БФ 1(Х) па индексную зону (ТУ).
с индексом (10.4.2) называется вектор-строка 1(.)(Х) =Ц„,~т„...,~„. ). (10.5.2) Проекции БФ будем нумеровать теми же числами (в фигурных скобках), что и соответствующие индексные зоны, Из определения ясно, что (10.5.1) есть проекция 1(Х) на зону индекса (О, 1,..., 2" — 1); будем условно, называть эту проекцию канонической. Пример 6. Пусть 1(хь хт) =х~=(0, 1, О, 1). Проекции этой функции на все индексные зоны будут следующими; )!!) =)(В»= (О, 0,1, !); 1[2) )!7) (О~ ! 0 !) Р!3) =((в) =(1,О,1, 0); 1(4)=р(з)=(1, 1,0,0), Вернемся к последовательности чисел (10.4.1). Пусть 1(Х) задана проекцией (10.5.2). Из всех интервалов (1, 1т, ), з= =-О, 1,...,2*' — 2, удовлетворяющих условию )Ъ, Ф(теч выберем (произвольным образом) по одному представителю Гь !и..., !а (й =.2'* — 1) так, что г,<Гз«...(ми образуем вектор порогов Т=(!ь Гь, !а) Поскольку 1;, =1(Х -, ) =гп!и !(Х), то полагаем т=1(Хт„).
Таким образом, по заданной БФ 1(Х) построен реализующий ее линейный МПЭ [%, Т, т), структура которого полностью определяется вектором весов входов Ф (нли, что то же, точкой и-мерного евклидова пространства <%>). Можно показать, что для всех точек %, принадлежащих фиксированной индексной зоне [!!т), функциональные зависимост~ (10.3.1) н (10,3.2) имеют следующий внд: й=сопз1; т=-сопз(, т. е. количество порогов и тнп элемента, реализующего заданную БФ, являются инварнантами для всех точек одной н той же индексной зоны. С другой стороны. если имеются две точки %~ и !чь принадлежащие разным индексным зонам, то соответствующие этим точкам элементы могут иметь разное число порогов н разные типы.
Пример 7. Для рассмотренной в примере 6 функции количество порогов и типы элементов будут следующими: й~=й4=-йз= йз=1; йг=йз йа йг — 3; т~=тз=тг=тз=О; тз=т~=-тз=та=1. Естественно предположить наличие корреляции между числом порогов й=й(%) и расположением индексных зок на поверхности гнперсферы о для произвольной фиксированной БФ. Экспериментальная проверка этой гипотезы на ЭЦВМ дала следующий результат [18). В качестве одного из примеров была взята БФ пяти переменных !(Х) =хатха'/х,хз~/хгез~/х,хзхэ'/х,хатз, (!05.3) исходная каноническая проекция которой имеет 15 порогов.
Было известно [30), что эта функция реализуется однопороговым элементом [(3, 5, 3, !, 2), 6), вектору весов входов которого соответствует на гнперсфере оз точка %* с координатами и, = — ; ТЗ 4 о )3 1 1 газ= —, юз= —, га,=-= и щз= —,. На участке поверхности 4ТЗ 4 4ТЗ 2ТЗ гиперсферы ам лежавшем в первом гппероктанте, выбирались случайные точки % в соответствии с равномерным законом распределения по поверхности этого участка. Затем (указанным выше приемом) строились соответствующие линейные МПЭ (%„, Т, т], определялось количество порогов А„=Й(% ) и вычислялось расстояние по хорде между точками %и н%": л<н, яч (в ат й (%„, %') = 2 з!ив 244 где <р -- угол между радиус-векто' з з ' У ' а а к рамн точек %„н %*.
На рис. 10.6 показана зависимость величин й„ Рис. /06 Ф(%,) и о(%„, %"), которая саиде. тельствует о наличии положительной корреляции между ними, Следовательно, функция (10.3.!) характеризуется тем, что переход из одной индексной зоны гиперсферы о„ в достаточно близкую (по метрике) соседнюю не влечет за собой резкого изменения количества порогов соответствующих МПЭ (можно показать, что величина Л скачка функции (10.3.1) на границах соприкасающихся индексных зон принимает одно из следующих значений: О, ~-2, +-4), Обратное утверждение, вообще говоря, неверно: например, функция (сумма по модулю 2) х,9хз —— = (О, 1, 1, О) во всех индексных зонах реализуема только двух- пороговым элементом, что легко проверить (аналогично примерам б и 7).
Таким образом, функция (!0.3,1) имеет постоянный уровень для всех точек фиксированной индексной зоны. Разным индексным зонам соответствуют, вообще говоря, разные уровни этой функции. На границах индексных зон функция (10.3.1) может иметь разрывы и, таким образом, является ступенчатой. Для дальнейшего важно отметить, что эта функция имеет локальный минимум в каждом из 2" гипероктантов, т. е. является много- экстремальной. Поскольку точки % и с% (с<0 -- вещественное число) лежат в симметричных гипероктантах и соответствуют МПЭ с одинаковым числом порогов, то количество существенно различных локальных минимумов в общем случае равно 2"-'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
