Растригин Л.А. Адаптация сложных систем

Подождите немного. Документ загружается.

1.Определяются l

= l(X

) ( i=1,..., N ) и проверяется усло

вие (4.3.12). Если оно нарушается, то вектор U следует изме

нить и повторить п. 1.

2. Производится ранжирование чисел li в ряд li

< ... < li

3. Определяется число изменений в ряде значений

функции

F(Хi

), F(Xi

), ..., F(Xi

). Это и есть число порогов МПЛЭ.

Сами значения порогов определяются из условия li

< τ

< li

j+1

где i

вычисляется из условия F(X

)≠F(Xi

j+1

), а параметр

В процессе синтеза МПЛЭ следует решить задачу:

(4.3.14)

где S — допустимые значения весов U, удовлетворяющих заданной

булевой функции F(X), т. е.

S : f (X) = F (X), (4.3.15)

где f(X) — логическая функция МПЛЭ (4.3.7). Решение задачи

(4.3.14) в виде U* и определяет МПЛЭ с минимальным числом

порогов

(4.3.16

)

МПЛЭ с минимальным числом порогов естественно назвать

оптимальным МПЛЭ. Перейдем к синтезу таких МПЛЭ.

4.3.3. Анализ задачи синтеза

оптимальных многопороговых логических элементов

Естественно задачу оптимального синтеза (4.3.14) решать

поисковым методом. Исследуем ее с этих позиций.

Прежде всего рассмотрим характер поведения минимизи-

руемой функции k(U). Она кусочно-постоянна, так как k — целое

число. Далее:

k (U) = k (cU) (4.3.17)

Для любого с. При этом пороги изменяются очевидным образом:

Т → сТ. (4.3.18)

Поэтому можно рассматривать не все пространство весов, а

лишь поверхность единичной гиперсферы:

| U | = 1. (4.3.19)

Необходимое условие (4.3.12) также накладывает на множество

допустимых весов U ограничение, которое сводится к выполнению

довольно очевидного требования линейной независимости:

(4.3.20)

где . Это означает, что веса могут быть лишь

слабо линейно-зависимыми. («Слабость» здесь выражается в

указанных ограничениях на коэффициенты линейной зависимости.)

Рассмотрим, как изменяется функция k(U) при незначительной

случайной вариации U. Элементарный анализ показывает, что

вероятность ее изменения — скачка не более чем на 4 — значительно

превышает вероятности других изменений. Это означает, что

существует корреляция между числом порогов k и расположением U

на поверхности гиперсферы | U | = 1.

Для проверки был поставлен следующий эксперимент [25].

Рассматривалась логическая функция пяти (k=5) переменных:

(4.3.21)

исходная каноническая

реализация которой (4.3.11) имеет k = = 15 порогов. Априори было

известно, что эта функция реализуется однопороговым (k=1)

элементом (4.3.8):

‹ (3, 5, 3, 1, 2); 6; 0 ›, (4.3.22)

которому на гиперсфере | U | = 1 соответствует точка

(4.3.23)

Эксперимент состоял в

следующем. На участке поверхности гиперсферы | U | = 1, лежащем в

первом гипероктанте, выбирались случайные точки U

в соответствии

с равномерным законом распределения по поверхности гиперсферы.

Затем строилась реализация МПЛЭ, т. е. определялось число порогов

k по формуле (4.3.7), где α = F (0, 0, ..., 0) = 0.

Расстояние ρ между точками U* (4.3.23) и U

для простоты

находилось по хорде:

(4.3.24)

Здесь φ — угол между векторами:

φ = агс cos ‹U

, U

›, (4.3.25)

где угловыми скобками обо-

значена операция скалярного

произведения векторов:

(4.3.26)

Результаты

эксперимента в

виде зависимости расстояния от

числа порогов показаны на рис. 4.3.3. Отчетливо видна зависимость

между этими величинами. Интересно, что уже на 117-м шаге такого

«слепого» случайного поиска была найдена однопороговая реализация

МПЛЭ [25].

Таким образом, можно считать, что при переходе от одной точки

сферы к ближайшей другой с достаточно большой вероятностью не

происходит значительного изменения числа порогов МПЛЭ. Это

означает, что синтез оптимального МПЛЭ можно производить

адаптивными параметрическими методами типа случайного поиска

(см. § 4.1).

4.3.4. Индексные зоны

Пусть u

, ..., u

— произвольные веса, удовлетворяющие условию

(4.3.20); {X} — множество всех двоичных векторов X

= = (x

, ..., x

количество которых равно N=2

(Х

= (0, 0, ...), X

= (1, 0, ..., 0), ..., X

(1, 1, ..., 1) ). Определим значения l

(j = 1, ..., 2

) и упорядочим их по возрастанию:

< lj

< ... < lj

n, (4.3.27)

где и j

≠j

при р≠q. Индексом точки U назо-

вем 2

-разрядный символ

Z (U) = (j

, ..., j

n). (4.3.28)

Множество точек U, имеющих одинаковые индексы Z(U), назовем

индексной зоной [26]. Эти зоны примечательны тем, что внутри

каждой из них любой МПЛЭ не изменяет, числа порогов.

ис. 4.3.3. Экспериментальная зависи-

мость между расстоянием ρ и числом

порогов k.

Действительно, число порогов любого МПЛЭ равно числу из-

менений ряда:

(4.3.29)

которые могут происходить лишь при, переходе

из одной индексной зоны в другую. Поэтому области пространства

весов U с одним и тем же числом порогов k для заданной логической

функции F(X) образуются из индексных зон, целиком входящих в ту

или иную область.

Легко показать, что индексные зоны выпуклы [26].

Для иллюстрации построим индексные зоны в первом октанте для

n=3. Пусть U = (u

, u

) — произвольная точка (u

≥0, i = l, 2, 3) в

индексной зоне точки U = (1, 2, 4), являющейся канонической

реализацией (4.3.11). Определим эту зону.

Ряд (4.3.27) в этом случае принимает вид

0 < u

< u

+ u

< u

+ u

< u

+ u

< u

+ u

. (4.3.30)

Исключая из системы неравенств (4.3.30) тривиальные, получаем

0 < u

< u

; (4.3.31)

+ u

< u

Отсюда находим индекс искомой зоны, соответствующей кано-

нической форме:

Z (l, 2, 4) = (1, 2, 3, 4, 5, 6, 7, 8).

Построим эту зону в сферических координатах (φ, ψ):

= ρ cos φ sin ψ;

= ρ sin φ cos ψ; (4.3.32)

= ρ cos ψ.

Система неравенств (4.3.31) определяет первую зону:

(4.3.33)

Аналогично можно построить

индексы остальных 11 зон: Z

= (1, 3, 2, 4, 5, 7, 6, 8); Z

= (1, 3, 2, 5, 4,

7, 6, 8); Z

= (1, 3, 5, 2, 7, 4, 6, 8); Z

= (1, 3, 5, 7, 2, 4, 6, 8); Z

= (1, 5, 3,

7, 2, 6, 4, 8);

= (1, 5, 3, 2, 7, 6, 4, 8);

= (1, 5, 2, 3, 6, 7, 4, 8); (4.3.34)

= (1, 5, 2, 6, 3, 7, 4, 8);

= (l, 2, 5, 6, 3, 4, 7, 8);

= (1, 2, 5, 3, 6, 4, 7, 8);

= (l, 2, 3, 5, 4, 6, 7, 8)

и неравенства, определяющие эти зоны. На рис. 4.3.4 показаны зоны

на плоскости углов φ и ψ. Номера зон соответствуют (4.3.34).

Пусть теперь задана булева функция

(4.3.35)

для которой легко определить число порогов k

в i-зоне:

= k

= 1;

= k

= 3; (4.3.36)

= k

= 5.

В результате получаем рельеф функции k(φ, ψ), изображенный на

рис. 4.3.5. Хорошо видно, что скачки функции не превышают 2, т. е.

минимального изменения значения функции числа порогов.

Рис. 4.3.4. Индексные зоны для положительного квадранта (n=3).

Рис. 4.3.5. Рельеф функции числа порогов для примера (4.3.35), Пунктиром

показаны границы индексных зон.

Таким образом, индексные зоны в задаче синтеза оптимального

МПЛЭ являются теми «квантами», из которых состоят области

равного уровня функции числа порогов k(U).

4.3.5. Экспериментальный синтез

многопороговых логических элементов

Поиск оптимальной точки осуществляется в n-мерном парал-

лелепипеде, содержащем начало координат:

≤ u

≤ b

(j = 1, ..., n). (4.3.37)

Компоненты начальной точки поиска U

вычислялись по формуле

= a

+ ξ

- a

). (4.3.38)

Компоненты последующих (текущих) точек поиска U опре-

делялись следующим образом:

(4.3.39)

где u*

— компоненты оптимальной точки U*,

полученной на предыдущих шагах поиска (на первом шаге

оптимальной считается точка U

); µ=const — шаг поиска; —

случайные числа с равномерным законом распределения.

Значение критерия качества k(U) в текущей точке U сравнивается

со значением k* = k(U*). Точка U считается удачной, если k<k*, т. е.

полагается U*=U, и дальнейший поиск идет от этой последней точки,

что соответствует случайному поиску по наилучшей пробе.

Критерий окончания поиска связан с тем, что в течение т шагов

подряд не найдена новая удачная точка.

В процессе поиска возможен выход за пределы области поиска. Во

избежание этого достаточно, например, полагать u

= a

= b

), если

имел место выход j-й компоненты за левую (правую) границу

интервала [a

, b

Описанный алгоритм поиска был экспериментально исследован на

ЭВМ. Составлена программа поиска оптимальных независимых

реализаций булевых функций с числом переменных n ≤ 5.

В частности, был осуществлен поиск оптимальных реализаций

рассмотренной выше функции пяти переменных (4.3.21), который

проводился в параллелепипеде:

0 ≤ u

≤ 10 (j = 1,..., 5). (4.3.40)

Параметры алгоритма: шаг поиска µ = 2, параметр критерия останова

m = 30.

В процессе поиска (из разных начальных точек U

) было получено

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

число шагов поиска равнялось 15—20. Для сравнения заметим, что

при случайном сканировании (см. (4.3.3)) оптимальная реализация

была найдена лишь на 117-м шаге.

Одна из найденных точек U* имела следующие компоненты: u*

l,9; u*

= 6; u*

=4,2; u*

=1,2; u*

=1,36. Соответствующая оптимальная

зона определяется, согласно формуле (4.3.27), неравенствами:

< u

+ u

;

0 < u

< u

;

+ u

< u

+ u

; (4.3.41)

+ u

< u

+ u

;

+ u

< u

+ u

< u

+ u

4.3.6. Вероятностные характеристики поиска

Эффективность описанного алгоритма поиска существенно

зависит от вида заданной логической функции F(X), а также

от параметров µ и m алгоритма поиска. Действительно, с уве

личением п количество индексных зон быстро возрастает и ве

роятность нахождения оптимальной (для заданной функции)

зоны уменьшается. Если в подобной ситуации осуществлять

поиск с большим шагом µ при малом значении т, то функция

k(U) ведет себя как многоэкстремальная, хотя в действитель

ности она может и не обладать этим свойством. С другой сто

роны, при малом шаге µ и большом т поиск становится

неэффективным по затратам времени, хотя принципиально позво

ляет решить задачу.

Таким образом, параметры алгоритма должны быть в опре-

деленном смысле согласованы с характером функции F(X). В этом

отношении можно дать лишь качественные рекомендации.

Для случая функций трех переменных получены количественные

оценки эффективности поиска, которые приводятся ниже.

Пусть в пространстве {U} задана сфера с центром в начале

координат. На участке сферы, лежащем в первом октанте, возьмем

случайную точку U

в соответствии с равномерной плотностью

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

попадания этой точки в индексные зоны (см. подраздел 4.3.4

настоящей книги и работу [26]).

Найдем плотности распределения углов φ и ψ, являющихся

сферическими координатами точки U

. Пусть плотность распре-

деления угла равномерная:

(4.3.42)

Тогда плотность распределения угла , согласно

[161],

ρ (ψ) = sin ψ. (4.3.43)

Поскольку φ и ψ — независимые случайные величины, то

ρ (φ, ψ) = ρ(φ) ρ (ψ). (4.3.44)

Следовательно, вероятность попадания точки U в индексную зону Z

= 1, 2, ..., 12) равна

(4.3.45)

где φ

, φ

, ψ

(φ) и ψ

(φ) определяются

границами этой зоны. Вычислим, например, вероятность P

попадания

в первую индексную зону (см. рис. 4.3.4). Пределы интегрирования:

= 0; φ

= π/2; ψ

(φ) = 0; ψ

(φ) = arc ctg (sin φ + соs φ). (4.3.46)

Получаем

(4.3.47)

Аналогично можно найти остальные

вероятности:

= P

≈ 0,062;

≈ 0,060;

= P

≈ 0,100; (4.3.48)

= P

≈ 0,116;

= P

≈ 0,054.

Для рассмотренной выше функции F(X) (4.3.35) вероятность

случайного попадания в оптимальную область равна

+ P

≈ 0,33, (4.3.49)

т. е. потери на поиск достаточно малы (в среднем каждый третий

случайный шаг поиска оказывается удачным).

4.3.7. Синтез надёжного многопорогового

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

При проектировании реальных МПЛЭ необходимо учитывать

нестабильность их физических характеристик и сигналов, которые

влияют на правильность вычисления логической функции.

Следуя работе [77], будем считать, что эта нестабильность сво-

дится к случайным отклонениям весов входов и порогов относительно

их номинальных значений, а модули отклонений пропорциональны

соответствующим номинальным значениям.

Пусть задан однопороговый ПЛЭ, реализующий некоторую булеву

функцию с пороговым интервалом (l

, l

(4.3.50)

Обозначим через 6 относительное

отклонение параметров данного элемента. Тогда условия надежной

работы МПЛЭ (с учетом указанных выше функций) будут

следующими (рис. 4.3.6):

≤τ;

τ''≤l

, (4.3.51)

где

= l

(1 + δ);

= l

(1 - δ); (4.3.52)

τ' = τ (1 - δ);

τ'' = τ (1 + δ).

ис. 4.3.6. Пороговый интервал однопорогового логиче-

эле

нт

а.