Оптимального управления 14 страница

Один из способов повышения эффективности ГА связан с параллельным развитием нескольких популяций и применением генетических операторов к хромосомам из разных популяций, что позволяет повысить генетическое разнообразие наследственного материала и приводит к улучшению окончательного решения. Мотивом создания этого подхода является известный из генетики факт: из аллелей формируются генотипы особей, из особей популяции, из популяций биоценозы, являющиеся итогом прогрессивного развития нескольких популяций. В соот-ветствии с вышесказанным, ГА, в котором генетические oriepa- торы применяются к хромосомам разных популяций, будем называть многопопуляционными (биоценозными).

В многопопуляционном ГА одновременно создается N начальных популяций Р®, Р2°,..., которые развиваются не-зависимо друг от друга до определенного момента tv (начало периода взаимодействия), после которого популяции обмениваются хромосомами и затем снова развиваются независимо. Норму взаимодействия (количество обменных хромосом) можно регулировать с тем, чтобы каждая из популяций могла также создать "свои" уникальные хромосомы. Главные проблемы реализации многопопуляционного ГА заключаются в следующем:

1) определение момента начала периода взаимодействия tv;

2) выбор принципа отбора обменных хромосом.

3.5. Гибридные нейронные сети

Основное преимущество нейросетевого подхода — возможность выявления закономерностей в данных, их обобщение, т. е. извлечение знаний из данных, а основной недостаток — невозможность непосредственно (в явном виде, а не в виде вектора весовых коэффициентов межнейронных связей) представить функциональную зависимость между входом и выходом исследуемого объекта. Исключением является случай представления НС и данных в алгебре по mod 2. Однако при этом, как правило, НС становится избыточной. Другим недостатком нейросетевого подхода является также трудность формирования представительной выборки, большое число циклов обучения и забывание "старых" примеров, трудность определения размера и структуры сети.

Основное преимущество нечетких систем заключается в том, что знания в этих системах представляются в форме легко понимаемых человеком гибких логических конструкций, таких, как "ZF... — THEN...". Кроме того, необходимо отметить, что, в соответствии с теоремой, доказанной Б. Коско (1993), любая математическая функция может быть аппроксимирована системой, основанной на нечеткой логике, следовательно, такие системы являются универсальными [16]. Основные трудности при исполь-зовании нечетких систем на практике связаны с априорным определением правил и построением функций принадлежности для каждого значения лингвистических переменных, описывающих структуру объекта, которые обычно проектировщик выполняет вручную. Поскольку вид и параметры функций принадлежности выбираются субъективно, они могут быть не вполне адекватны реальной действительности.

Два подхода к управлению сложными объектами на основе НС и нечетких систем взаимно дополняют друг друга, поэтому целесообразно их объединение на основе принципа "мягких" вычислений (Soft Calculation). Основы построения таких систем с использованием разнородных методов были сформулированы Л. Заде в 1994 году. Они сводятся к следующему: терпимость к нечеткости и частичной истинности используемых данных для достижения интерпретируемости, гибкости и низкой стоимости решений.

Реализация объединения рассмотренных двух подходов возможна в следующих гибридных системах:

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

• нечеткие НС, в которых с помощью аппарата нечеткой математики осуществляется фазификация отдельных элементов нейросетевых моделей;

• нечетко-нейросетевые гибридные системы, в которых осуществляется объединение нечетких и нейросетевых моделей в единую систему.

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

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

Рассмотрим вопросы, связанные с обучением НС для представления функций принадлежности произвольной формы. Построение простых форм функции принадлежности, таких как треугольная или кол околообразная, осуществляется на одном нейроне путем подстройки функции активации к желаемой функции принадлежности. Например, для представления колоколо- образной функции принадлежности может быть использован нейрон, функция активации которого имеет вид:

/(net) = ехр(— (net - ш)2/а2), (3.29)

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

В качестве примера рассмотрим возможность построения функций принадлежности для трех значений некоторой лингвистической переменной: "мало (S — Small)", "средне (М — Medium)", "много (L— Large)". Для этого используем НС, представленную на рис. 3.38, а. На этом рисунке выходы yv yv у3 определяют величины соответствующих функций принадлежности — ji/x), \ьм(х), ixL(x). Узлы со знаком "+" суммируют сигналы входов нейронов, а узлы с символом /реализуют сигмои- дальные функции. Например, для значения лингвистической переменной "мало" функцию принадлежности можно определить следующим образом:

ух = \is(x) = 1/(1 + ехр(- wg(x + wc))), (3.30)

где wc— весовой коэффициент для смещения и wg— вес суммарного сигнала на входе нелинейного преобразователя. Путем подстройки весовых коэффициентов формируются функции при-надлежности (рис. 3.38, б).

Реализация нечетких И (AND), ИЛИ (OR) и других операторов в нейросетевом логическом базисе дает основу для построения нейросетевых нечетких моделей. Определим процедуру реализации базовых нечетких логических операторов. Возможность использования различных функций активации нейрона позволяет разрабатывать различные (желаемые) логические операторы,

" M*)

y{ = \ip) 1,0

max(jc) x

= 0 mteW

Рис. 3.38. Нейросетевая реализация функций принадлежности:

а— структура НС; график функций принадлежности

т. е. можно задать функцию активации, реализующую min-one- ратор для нечеткой операции AND, шах-оператор для нечеткой операции OR. Возможность применения недифференцируемых функций активации в процедуре обучения НС не обеспечивает-ся использованием генетических алгоритмов оптимизации. В некоторых случаях, когда процедура обучения связывается с алгоритмом Back Propagation в НС прямого распространения, возможна замена или аппроксимация желаемой недифферен- цируемой функции дифференцируемой. Например, следующий "мягкий" (softmin) оператор может быть использован для замены оригинального нечеткого оператора И:

(алЬ) = softmin(tf, h) = (ае~ка + be~kb)/(e-a + e~b), (3.31)

где к — параметр, контролирующий "soft": при к -»©о реализуется обычный min-оператор. При конечных к имеем обычную дифференцируемую функцию. Априорно вводя различные типы аппроксимирующих функций типа (3.31), можно разработать большое количество "мягких" логических операторов, способ-ных наилучшим образом адаптироваться к решаемой задаче.

Возможны различные способы реализации нечетких отношений в системах нечеткого логического вывода [16]. Основные трудности построения нечетких отношений связаны с настройкой большого числа функций принадлежности. Для устранения этих трудностей можно использовать подход, основанный на обучении НС с весовыми коэффициентами, соответствующими этим функциям принадлежности. 

Пусть Хи Y— нечеткие множества в U и К соответственно и R — нечеткое отношение в UxV. Рассмотрим уравнение нечеткого отношения:

(3.32)

где 0 — операция композиции (например, max-min операция).

Пусть U = Ц, xv..., хп) и F = {з^р.у2, Тогда можно

записать max-min композицию:

liyiy) = max(min(|iv(x), \xR(xn у))), (3.33)

где X— нечеткое множество на U; У— нечеткое множество на К и Л - нечеткое отношение R: UxV[0,/], описываемое всеми отношениями принадлежности (связями) между входом и выходом. Выражение (3.33) можно записать в другом виде, представив отношение R в виде матрицы:

M-Kl^l) • • М*1>У/>)

• M*2 >Уп)

■ Vfi(x„,y„)

. (3.34)

X°R = [цЛ. (x,), [ix (x2),..., \xx (xn)]°

Уравнение (3.34) определяет величину ц/у.) путем композиции векторам X и j-й колонки матрицы отношения R. Такое отношение может быть реализовано НС, структура которой показана на рис. 3.39. В этой сети выходной узел выполняет max- min композицию вместо обычной операции суммирования, реализуемой НС.

Однако, следуя уравнению (3.33), на определенном вы-ходном узле необходимо получить сигнал (max или min), отличающийся от сигналов на других узлах. Если использовать обычную операцию суммирования сигналов на входах нейрона, то результирующий сигнал может быть слишком низким для активизации выхода. В связи с этим к каждому выходному узлу рассматриваемой НС добавляется порог (bias), обозначаемый be [0, 1]. Тогда уравнение (3.33) можно представить в виде:

M-yCv) = max[max(min(fxx(x), jaR(x.,y))), b(y)]. (3.35)

vyiy) у

Рис. 3.39. Нейросетевая модель нечетких отношений

MyO^i)

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

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

Один из вариантов реализации нейросетевого нечеткого вывода (для базы из трех правил Rp R2, R3), позволяющего формировать функцию принадлежности условной части IF правил и управлять выводом на основе сформированной функции принадлежности, представлен на рис. 3.40. 

Обучение степеням принадлежности условной части правил

х, О буч ё н и ё ~ зао ю ч й тел ь н о й ч_асти_ правил

Ответ

Рис. 3.40. Нейросетевая модель нечеткого вывода

•'Л1*- ••'/••

п У*

* * Л '<•

г '•''*♦*)» • '

Правила нечеткого вывода в рассматриваемой модели имеют следующий формат:

Rs: IFX = (х1?..., х) is AsTHENys = HC/xt,..., х),

S = 1,2,..., г, (3.36)

где г — число правил вывода; As — представляет нечеткое множество условной части каждого правила; НС^(.) - определяет структуру нейросетевой модели (многослойный персептрон) со входами х{9 xv..., хп и выходом ys, причем для каждого правила используется своя НС. Для определения функций принадлежности условной части правил используется нейронная сеть HC5(^i) (многослойный персептрон). Нейронная сеть НС5(т) обучается на входных данных из обучающей выборки. Выходы обученной НС рассматриваются как величины функций принадлежности

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

Предположим, что в рассматриваемой нейросетевой модели нечеткой системы, состоящей из нескольких НС, имеется п входов хр х2,..., и единственный выход у. Обозначим через НС^-НС, которая вычисляет выходу для каждого S-го правила. Тогда процедура нечеткого вывода на основе нейросетевой модели реализуется следующим алгоритмом:

1. Формирование обучающей No и тестовой NT выборки; N = jV + N(— общее число примеров из базы данных.

2. Кластеризация обучающей выборки. Делим обучающую выборку на г классов Rs (по числу правил), где S = 1, 2,..., г. Каждая обучающая подвыборка для класса Rs определяется парой (xf, yf), где / = 1, 2,..., Ns, a Ns— число примеров в обучающей выборке для класса Rs. Разделение «-мерного входного пространства на г в данном случае означает, что число правил вывода равно г.

3. Обучение НС(ц). Для каждого входного вектора Хе Rs определим вектор функций принадлежности к правилу М. — (т), т},

т-У такой, что mf = 1 и mf = 0 для к * S. Нейронная сеть НС(|л) с п входами и г выходами обучается на парах (X., М), / = = 1,2,..., N(), следовательно, после обучения и тестирования такая сеть будет способна определить степень принадлежности mf для каждого входного вектора, принадлежащего классу Rs. Таким образом, функция принадлежности к части IF правила определяется как выходная величина mf обученной #Сфп, т. е.

mAs{X) = mf, I = 1, 2,..., N, S = 1, 2,..., r,

где As соответствует нечеткому множеству условной части S-rо правила.

4. Обучение НСУ Обучающая выборка с входами, xf2,..., xfn и выходной величиной yf; / = 1, 2,..., Ns подается на вход и выход НСу, которая является нейросетевой моделью части THEN в Rs. С помощью тестовой выборки вычисляется ошибка обобщения:

NT

Esn=JJ{yi-ms{Xi)mAs{Xi)}\ i=1

где ms(Xt) — наблюдаемый выход НС5. Если Es< 8, где 8 — априори заданная величина, HCS — обучена.

5. Принятие решения. Для заданного входного вектора проводится вычисление выходной величины по аналогии с формулой дефазификации, используемой в классическом композиционном выводе:

JjmAs(Xi)ms(Xi) / 5>А(ЛГ,)

\ Г г \

у. = ~

s=\

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

Можно выделить три базовых типа нечетких нейронов, на основе которых можно построить нечеткие НС:

• нечеткий нейрон с четкими входными сигналами, но с нечеткими весами;

• нечеткий нейрон с нечеткими входными сигналами и нечеткими весами;

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

Нечеткий нейрон первого типа nv (рис. 3.41) имеет п четких входов х,, х2, хп. Весовые коэффициенты такого нейрона представляют собой нечеткие множества Ар i = 1,..., п, т. е. операции взвешивания входных сигналов в классическом нейроне заменяются функциями принадлежности и происходит их объединение (агрегирование) в узле пх с выдачей сигнала у = м^С*,, х2,..., хл), принадлежащего интервалу [0,1], который может рассматриваться как "уровень правдоподобия". 

А

Рис. 3.41. Модель нечеткого нейрона с четкими входными сигналами и нечеткими весами

Операцию агрегирования взвешенных сигналов обозначим как для реализации которой можно использовать нечеткие операторы Г-нормы и /-конормы. В зависимости от типа используемой операции ® можно получить различные схемы нечетких нейронов. Математическое описание нейрона может быть представлено в виде:

*2> — х) = M*i> ® М*2) ® - ®

где ® — знак операции агрегирования; х. — /-й (не нечеткий) вход нейрона; jui^.) -— функция принадлежности /-го (нечеткого) веса; \хп1 выходная функция нейрона.

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

У л

У = Х{® Х'2®...® Х'п

Рис. 3.42. Модель нечеткого нейрона с нечеткими входами и выходами

Каждый сигнал на каждом нечетком входе X. преобразуется путем операции взвешивания в нечеткое множество Х\ = А*ХР i = 1,..., п, с использованием некоторого оператора *, где А. — /-й нечеткий вес. Операция взвешивания здесь не является

функцией принадлежности, как в нейроне первого типа; вместо нее проводится модификация каждого нечеткого входа. Математическое описание нейрона второго типа имеет вид

Xt'= А *Х, /= 1, 2, л; (3,37)

г= х\®х'2 ®...®х'п,

где Y— нечеткое множество, представляющее собой выход нейрона п2; X\ и Х- —- /-й вход до и после операции взвешивания соответственно; А. — вес на /-й связи; ® — операция агрегирования, * — оператор взвешивания двух нечетких множеств (например, операция произведения двух нечетких множеств).

Нечеткий нейрон третьего типа п3 с п нечеткими входами и одним нечетким выходом показан на рис. 3.43. Отношение входа-выхода нечеткого нейрона этого типа представляется с помощью одного нечеткого правила IF-THEN:

IFX AND Х~ AND... AND X THEN У,

11 n '

где Xr Xv..., Xn— текущие входы, Y— текущий выход. Тип нейрона пъ можно описать нечетким отношением, например,

R = ХхХх...хХ хГ

1 2 п

или в общем случае

R = f(Xv Х2,..., Хп, Y),

Рис. 3.43. Модель нечеткого нейрона, реализующего нечеткое отношение

где/(.) — функция импликации. Следовательно, нейрон рассматриваемого типа описывается нечетким отношением R. Задавая соответствующие входы (четкие или нечеткие) xv xv хп, в соответствии с композиционным правилом вывода получим

(3.38)

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

На основе рассмотренных типов нечетких нейронов можно конструировать нечеткие НС различной архитектуры, которые в отличие от обычных НС обладают расширенными возможностями представления и обработки входной и выходной информации.

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

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

Рассмотрим реализацию стандартного алгоритма обратного распространения ошибки в случае разбиения входного пространства векторов на два пересекающихся класса (рис. 3.44).

Рис. 3.44. Неразделимые классы объектов

Пусть имеется обучающая выборка, состоящая из векторов {Х}, Х2, Хр}, и функция принадлежности пг(Лу, i = 1, 2; к = 1, 2, р, определяемая как мера нечеткого разбиения пространства входов на два класса по от-ношению к этим векторам, показывающая степень принадлежности каждого из этих векторов к каждому из двух классов. Эти предположения могут быть представлены следующими соотношениями: 

£й/(**) =»; 0 <ivn(Xk)<K [0,1], (3.39)

1=1 к=\

причем для векторов, чей класс является менее определенным, функция принадлежности находится в интервале до 0,5 (рис. 3.45).

Степень влияния образца Хк на модификацию весовых коэффициентов можно определить как разность [Хк) - \х2 (Хк)|т,

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

Wj(t) = Wj(t-\) +

+ к\щ (Хк (t-l))-n2 {Хк (t - l)f [dk - y(t - l)]xf\ (3.40) 1 <j < n + 1,

где h — скорость обучения; dk — желаемый выходной сигнал при Хк входном векторе; t — текущий такт обучения НС.

Рис. 3.45. Представление функций

принадлежности двух пересекающихся классов объектов

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

При этом, если Jjm, (Хк (f))-M<2 {хк (0)f = К0ГДа М-1 (-**)>

]х2(Хк)е [0,1], нечеткий персептрон становится четким, тогда значения величин функций принадлежности также будуг четкими. При выборе стратегии обучения, как было показано ранее, большое значение имеет выбор шага обучения, в особенности на ранних итерациях, когда определяется выбор направления поиска, поэтому для векторов, значения функций принадлежности которых близки к 0,5, можно установить значение т > 1 и на последующих итерациях постепенно его уменьшать.

При разработке алгоритма обучения нечеткого персептрона необходимо решить две задачи:

1) определить способ вычисления функций принадлежности на каждом этапе итерации;

2) определить критерий останова.

При решении первой задачи используют формулы разделения двух пересекающихся классов. Тогда для некоторого вектора Хк в классе 1 получаем:

\л.(Хк) = 0,5 + (exp((/(dist2 - dist^/dist) -

- ехр(—/))/(2(ехр(/) - ехр(-/))); (3.41)

м2(хк) = 1 -- цода,

где dist, — расстояние вектора Хк до среднего значения класса 1; dist2 — расстояние вектора Хк до класса 2; dis^ — расстояние между средними значениями двух классов;/— положительная констан-та, подбираемая опытным путем (/> 2). Формулы (3.41) для Хк в классе 2 носят противоположный характер.

При решении второй задачи необходимо учесть тот факт, что, когда вектор не может быть однозначно отнесен к определенному классу, значение его функции принадлежности близко к величине 0,5, поэтому для останова процедуры обучения выбирается значение 8, показывающее близость функции принад- лежности к величине 0,5. Тогда критерием останова будет выполнение следующего условия:

\хх{Хк) > 0,5 + 5

или

цда > 0,5 - 5, для V к, к = 1, р. (3.42)

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

1. Инициализация весовых коэффициентов. Установление допусков т и 8.

2. Вычисление степеней функции принадлежности на всех образцах обучающей выборки в каждом классе в соответствии с формулами (6.31).

3. Установление флага "Обучение" в состояние "True".

4. Предъявление НС нового образца,

Хк={^\ *(*>,...,*?>-! }, где = 1 (порог), с желаемым выходом dke {1, —1} и вычис

ление действительного выхода:

п+1

У(<) =

(3.43)

2>/(')*}

м

Если y(t) = dk, то переход к шагу 7.

5. Коррекция весовых коэффициентов по формуле (3.40).

6. Если не выполняются условия (3.42), хотя бы для одного к, к — /,..., р, флаг "Обучение" установить "False".

7. Если все примеры из обучающей выборки просмотрены, перейти к следующему шагу, в противном случае перейти к шагу 4.

8. Если флаг "Обучение" находится в "True", то Останов и выдача весовых коэффициентов, определяющих границу разбиения, в противном случае — переход к шагу 3.

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

ГЛАВА 4

ВОЗМОЖНОСТИ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ УПРАВЛЯЮЩИХ СИСТЕМ

4.1. Программные средства интеллектуализации

Программные средства интеллектуализации, используемые в УВМ, позволяют значительно повысить качество управления. Среди наиболее часто используемых программных средств, используемых в интеллектуальных системах управления, можно выделить следующие:

языки программирования (ЛИСП, ПРОЛОГ и др.); базы данных;

оболочки экспертных систем; нейронные сети;

системы типа "искусственная жизнь" (A-life). Язык ЛИСП занял особое место среди ранних языков про-граммирования, обеспечивающих возможности манипуляции на ЭВМ символами при решении задач искусственного интеллекта. Уже в 1956 году Ньюэлл, Шоу и Саймон разработали язык программирования ИПЛ, с помощью которого можно было обрабатывать списки. Этот язык был одним из предшественников языка программирования ЛИСП, разработанного Дж. Маккарти в 1960 году. ЛИСП стал наиболее популярным в среде специалистов по искусственному интеллекту, особенно в США, где в качестве стандартного получил распространение его диалект COMMONLISP [40]. К достоинствам языка можно отнести точность, определенность, лаконичность и удобство в работе. ЛИСП является хорошим средством для представления древовидных структур, которые служат основой символьной обработки. Имен-

но поэтому до недавнего времени большинство программ искусственного интеллекта писались на языке ЛИСП. Хотя в настоящее время инструментарием для обработки списков обладают и такие развитые языки программирования, как Фортран, ПЛ/1, Паскаль, Ада и др. Кроме того, в последнее время переосмысливается роль и место символьной обработки в задачах искусственного интеллекта и появляются все новые и новые инструментальные средства решения задач искусственного интеллекта.

Выражения языка ЛИСП называются ^-выражениями. Они представляют собой либо атом, либо список.

Атом представляется каким-либо алфавитно-цифровым именем, т. е. в сущности числом.

Список — это некоторая внутренняя часть, заключенная в скобки.

Синтаксис языка ЛИСП в форме Бэкуса—Наура определяется следующим образом:

<8-выражение>

<список>

<внутренняя часть> = <атом> = <список> = <внутренняя часть> = <пусто> = <£-выражение>

= <5-выражение> <внутренняя часть>

< пусто > <атом>

: = цепочка алфавитно-цифровых символов без пробелов или специальных символов

Таким образом, всякое S-выражение представляет собой набор атомов и списков, например: ((король ферзь)((ладья) (слон)) пешка).

Как и во всех языках программирования, некоторые предварительно определенные атомы являются функциями, аргументы которых представляют собой следующие за ними ^-выражения. В свою очередь аргумент сам может быть функцией, которую нужно вычислить. При этом надо иметь возможность определить, что представляет собой данный элемент — значение выражения L или же символьное имя L какого-то ^-выражения. В первом случае перед выражением ставится апостроф, например CL, или же пишут в развернутой форме: (QUOTE L). Апостроф запрещает вы-

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

Для задания выражения используется функция SETQ. В об-щем случае всякое 5-выражение, поступающее в машину, тут же вычисляется. Необходимо отметить, что в языке ЛИСП любая программа сама по себе является 5-выражением. В частности, в ЛИСП данные имеют ту же структуру, что и программы, и также являются выражениями. Результат выполнения программы в Л ИСП также программа. Соответственно этому выражение в ЛИСП является программой. Это свойство языка ЛИСП позволяет создавать программы, которые могут перестраивать сами себя.

Кроме того, в языке ЛИСП имеется возможность создавать новые функции, и для этого используется функция DEFUN.

Более подробно с языком программирования ЛИСП и ме-тодами программирования в нем можно ознакомиться в [41].

Язык ПРОЛОГ применяется для решения какой-либо зада-чи системой в терминах предикатов. История создания языка начинается с 1972 года, когда А. Кольмрауер разрабатывал со своей группой сотрудников систему автоматического доказательства, построенную на базе логики первого порядка и методе Эрбрана—Робинсона. Система автоматически выдавала ответ, используя для этого унификацию и метод резолюций. Таким образом, ПРОЛОГ можно рассматривать как декларативный язык, где единственные входные данные — это формальное определение задачи. Так как часто желательно получение решения задачи в явном виде, то, с этой точки зрения, доказательство, основанное на опровержении специальным образом сконструированного предложения, получаемого методом резолюций, не является достаточным результатом. Поэтому в 1969 года для устранения отмеченного недостатка Грин предложил ввести в исходный набор предложений "ответный" предикат, связанный с заключением: 1 заключение (х) v вывод (х), либо заключение (х) л вывод (х), который обеспечивает получение системой решения в явном виде и выдачу х пользователю. Тем не менее использование ПРОЛОГА эффективно только в тех случаях, когда деревья доказательства не слишком велики.

Дата добавления: 2015-04-29