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

Естественно задачу оптимального синтеза (4.3.14) решать поисковым методом. Исследуем ее с этих позиций.

Прежде всего рассмотрим характер поведения минимизируемой функции Она кусочно-постоянна, так как к — целое число. Далее:

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

Поэтому можно рассматривать не все пространство весов, а лишь поверхность единичной гиперсферы:

    (4.3.19)

Необходимое условие (4.3.12) также накладывает на множество допустимых весов ограничение, которое сводится к выполнению довольно очевидного требования линейной независимости:

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

Рассмотрим, как изменяется функция при незначительной случайной вариации Элементарный анализ показывает, что вероятность ее изменения — скачка не более чем на 4 — значительно превышает вероятности других изменений. Это означает, что существует корреляция между числом порогов к и расположением на поверхности гиперсферы

Для проверки был поставлен следующий эксперимент [25]. Рассматривалась логическая функция пяти переменных:

исходная каноническая реализация которой (4.3.11) имеет порогов. Априори было известно, что эта функция реализуется однопороговым элементом (4.3.8):

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

Эксперимент состоял в следующем. На участке поверхности гиперсферы лежащем в первом гипероктанте, выбирались случайные точки в соответствии с равномерным законом распределения по поверхности гиперсферы. Затем строилась реализация МПЛЭ, т. е. определялось число порогов к по формуле (4.3.7), где

Расстояние между точками U (4.3.23) и для простоты находилось по хорде:

Рис. 4.3.3. Экспериментальная зависимость между расстоянием и числом порогов к.

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

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

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

Таким образом, можно считать, что при переходе от одной точки сферы к ближайшей другой с достаточно большой вероятностью не происходит значительного изменения числа порогов МПЛЭ. Это означает, что синтез оптимального МПЛЭ можно производить адаптивными параметрическими методами типа случайного поиска (см. § 4.1).