Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 36
Текст из файла (страница 36)
Пример 8. Полным перебором всех существенно различных (в указанном выше смысле) индексных зон можно найти локальные минимумы функции (!0.3.1) для следующих БФ: 1) для функции х~~/хзхз имеем 1~*=1, Ать=2, й;=й,~=З (нижний индекс соответствует номеру октанта); 2) для функции хз(х~хзч'х,хз) имеем А,а=й„~=З, йэ"=йзе=2; 3) для функции х,хэ ~lхгхз имеем й~* =й~~ =- 4, йз* =йза =3. Глобальному минимуму функции (10.3.1) соответствует МПЭ с минимально возможным числом порогов, который реализует заданную БФ. Можно поэтому ввести следующее определение.
Определение 4. БФ называется и-пороговой (и обозначается через х-ПФ), если она реализуема МПЭ с минимальным числом порогов, равным н. Число и назовем пороговыч порядком данной БФ. Пример 9. Рассмотренные в примере 8 функции являются соответственно 1-ПФ, 2-ПФ и З-ПФ. Задача нахождения порогового порядка х для произвольной БФ является важной и нерешенной проблемой многопороговой логики. В связи с этим следует заметить, что любая БФ 1(Х) реализуема МПЭ с числом порогов 1~Й~2Е(!), где ЕЯ =гп!п(Х 1(Х),,~ ЦХ)). Число Е(1) условно назовем рангом 1(Х).
Можно показать, что количество БФ ранга Е(1) равно С,,,в!л. Максимальное число порогов й=2" — 1 могут иметь только функции ранга Е(1) =. =2"-'. Следовательно, число таких функций равно (2а) ! 3" 2а-л+ з 1(2Ц вЂ” ') 1)з П, В действительности, однако, для любой БФ верхняя граница порогового порядка н с2"-1.
Данные о количестве 1-ПФ для п=,7 приведены в табл. 10.1. При а=2 имеется 14 функций типа 1-ПФ и две функции типа 2-ПФ, а при п=З имеется 104 функции типа !-ПФ, 126 функций типа 2-ПФ и 26 функций типа З-ПФ. Относительно функция (10.3.2) можно показать, что она постоянна для фиксированного гипероктанта. язв $9.6. метОды Решения 3АдАчи синтезА ОптимАльнОГО ЛИНЕЙНОГО МПЗ При малой размерности пространства весов входов задача синтеза оптимального линейного МПЭ, реализующего задан,ную БФ, решается довольно просто путем полного перебора всех индексных зон.
Однако при больших значениях а, практически уже начиная с я=5, этот метод не применим ввиду большой трудоемкости вычислений (например, при л=5 количество существенно различных индексных зон равно 1048320). Наличие корреляции между расположением индексных зон иа гиперсфере а„и количеством порогов соответствующих МПЭ позволяет применить для решения поставленной задачи поисковые методы оптимизации (31 — 331 Заметим, что детерминированные методы поиска экстремума (метод градиента, паискорейший спуск и др.) в данном случае не работают ввиду отмеченных выше свойств функции (!0.3.1).
Простейшим методом поиска является так называемый слепой поиск (случайное сканирование), который заключается в исследовании случайных точек, выбираемых в соответствии с некоторым законом распределения по поверхности гнперсферы а„,. Поскольку пороговый порядок заданной БФ заранее неизвестен, то критерия окончания поиска не существует и ои выбирается из практических соображений, Этот метод прост для реализации на ЭЦВМ, но малоэффективен при и)5.
Так, оптимальная реализация для БФ (!0.5,3) была найдена лишь иа !!7-м шаге (181 Эффективны методы поиска, предлагаемые в работе [3!1, по они требуют сравнительно сложной организации вычислений. Наиболее целесообразно (на паш взгляд) решать поставленную задачу методом случайного поиска (32], идея которого заключается в исследовании локального поведения минимизируемой функции на базе небольшого числа случайных пробных шагов.
Рассмотрим кратко один из алгоритмов случайного поиска (33! применительно к задаче синтеза оптимального линейного МПЭ, который был экспериментально проверен на ЭЦБМ «Урал-4» и «БЭСМ-ЗМэ (более подробно данный алгоритм описан в работе (29)). Координаты начальной точки поиска %э= (ш,э, шзэ,..., ш„ч) формируются по формуле !'10.6.!) где ш;=-.а,+в;(р; — о,); аь (1; — вещественные числа (а,((1;); $; — случайные числа, снимаемые с датчика случайных чисел (ДСЧ) с равномерным (нлн нормальным) законом распределения. Из (10.6,1) видно, что (%о! =1, т.
е. %чена,. Поскольку все ш~ являются функциями (10.6.1) случайного аргумента $, с многоразрядной мантиссой (в случае «БЭСМ-ЗМ» разрядность мантиссы равна 36), то вероятность невыполнения условия (10.2.2) практически равна нулю„что подтвердилось в процессе эксперимента. Следовательно, начальная точка поиска %а лежит, как правило, внутри некоторой индексной зоны. Указанным выше способом строится МПЭ, реализующий заданную БФ, и определяется число порогов Ьэ —— Ь(%,). Относительно начальной точки %, строится симметричная окрестность Гь(%э) радиуса Ь (способ построения окрестности дается в раооте (33)). Затем отыскивается случайная точка %~~Ух(%э), прн которой Ь~ =Ь(%~) ~йв (!0.6.2) Далее повторяется процедура построения окрестности Уь(%~).
симметричной относительно точки %, и т. д. Координаты точек %ь %ь... формируются аналогично координатам начальной точки %о. В процессе поиска радиус Ь окрестности уменьшается, если очередные и (~п — фиксированное число) точек поиска оказались неудачнымн (условие (10.6.2) не выполняется). Поиск заканчивается, если радиус Ь становится меньше некоторого наперед заданного числа е. Характерной особенностью данного алгоритма, учитывающей строение функции (10.3.1), является скользящий режим поиска внутри индексной зоны, который обеспечивается критерием (10.6.2). Для нахождения глобального минимума функции (10.3.1) необходимо провести серию рассмотренных поисков с различных начальных точек.
Поскольку количество существенно различных локальных минимумов заранее известно и равно 2" ', < Ок ж4 ~ ш5' ш~', ш1+шз~шз шз+ ша ~ геь' (10.6.3) ш~< ш~+шз,' ы~з» ш) + жз, ге~+ шз+нч~жа+шм газмаш~+Юз+юз~ аЫ+шз. (10.6.4) !!айдем выражения координат ш; (1=1, 2,..., 5) через положительные числа рь т. е. перейдем от неравенств (10.6.3) и следующим равенствам: ш~'=-94 гез=ша+Рз=!м+ры ш~ =и~+газ=и~+из+из шз= из+ ш~+ шз = 9~+ из+ 2 (им+ рз); ша = Оз+ щз+ шз = Р~+ 1~а+ из+ 3 (Рз+ Рз) .
(10 65) Из неравенств (10.6.4) получаем систему ограничений на числа рз" р!(рм р1~Р2+рз~ рз(1м (1066) 0(и~+ма+2(рз+р~) +3рм 248 то число поисков, вообще говоря, должно быть больше 2"-' (пбо некоторые поиски могут сходится к одинаковым локальным минимумам). Рассмотренный алгоритм был применен для решения целого ряда задач с числом переменных а -10 и оказался достаточно аффективным. Так, на поиск локального минимума функции (10.5.3) в среднем требовалось 15 — 20 шагов.
В результате поиска находится оптимальная точка тт'*ево с вещественными координатами. С точки зрения технической реализации МПЭ (например, сетью пз 1-ПЭ), часто бывает важно, чтобы веса входов и; (1=1, 2,..., а) и пороги (1==1, 2,..., Й) были целыми числами. Покажем на примере один нз способов получения целочисленных решений, если имеется решение %*еде„. Пример 10. В результате поиска оптимальной реализации для БФ (10.5.3) была получена точка %* с координатами: ш~ —— =0,0314, ш,=0,0994, из=0,0696, шз — — 0,0198 и газ=0,0225. Согласно (10.4.1), системы неравенств, определяющих соответствующую индексную зону, будут следующими: последнее из которых травиально.
Графически система ограничений (10.6.6) показана на рнс. 10.7. Минимальные целочисленные значения величин рь рь... ..., Иь удовлетворяющие системе ограничений (!0.6.6), будут Рс — — ~ У Рс М Рис. /0.7. следующими: аз= И,= 1; р, == па=2„ц~ — — 3. Согласно (10 6 5). кооРдинаты точки 1та также бУдУт целыми числами: в~— - 7; из--- =19; ос=13; м,=-3 и из=5. Легко проверить, что опи удовлетворяют условиям (!0.6.3) и (10.6.4). Если в качестве порога взять число с=23, то построенный 1-ПЭ реализует БФ (10.5.3). й 10.7.
СИНТЕЗ НАДЕЖНОГО ЛИНЕЙНОГО МПЗ Прп проектировании реальных ПЭ и МПЭ необходимо учитывать нестабильность пх физических характеристик, которая влияет на правильность вычисления логической функции. Следуя работе [4), будем считать, что эта нестабильность сводится к случайным отклонениям величин весов входов и порогов относительно их номинальных значений, а модули отклонений пропорциональны соответствующим номинальным значениям.
Пусть задан МПЭ (Ф, Т, т1, реализующий некоторую БФ. Для простоты будем считать все веса входов возбуждающими, Ра . Ю.В. т. е. в;>О, Е=!, 2,..., а. Обозначим через б; относительное отклонение весов входов и порога Е; для Ечго порогового интервала (Еч, Е а,) (рис. 10.8), где Е, =гпах Е(Х), Е(Х) <Е,; Еа пт!пЕ(Х), Е(Х),= Еь х Тогда условия надежного функционирования данного МПЭ (для Е-го порогового интервала) будут следующими: Еа ~~ЕЕ (10.7.1) где Еа «~!п, (1+б!) Е в.=Еа (1 б!)~ Е';=Е;(1 — б,); Ез'!=ЕЕ(1+б„).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
