«Ю.Ю. Громов, О.Г. Иванова, В.В. Алексеев, М.П. Беляев, Д.П. Швец, А.И. Елисеев ИНТЕЛЛЕКТУАЛЬНЫЕ ИНФОРМАЦИОННЫЕ СИСТЕМЫ И ТЕХНОЛОГИИ Рекомендовано федеральным государственным бюджетным образовательным учреждением высшего ...»

В противном случае вычисляется разница между фактическими и требуемыми выходными значениями, которая передаётся последовательно от выходного слоя к входному. На основе этой информации проводится модификация связей в соответствии с обобщённым дельтаправилом, которое имеет вид: p w ji = jp yip, где изменение в силе связи wji для р-й обучающей пары p w ji пропорционально произведению сигнала ошибки j-го нейрона jp, получающего входной сигнал по этой связи, и выходного сигнала i-го нейрона yip, посылающего сигнал по этой связи. Определение сигнала ошибки является рекурсивным процессом, который начинается с выходных блоков. Для выходного блока сигнал ошибки jp = y j T jp R jp, где Tjp и Rjp – соответственно желаемое и действительное значения выходного сигнала j-го блока; y j – производная от выходного сигнала j-го блока. Сигнал ошибки для скрытого блока определяется рекурсивно через сигнал ошибки блоков, с которым соединён его выход, и веса этих связей равны jp = yi kp wkj. Для сигмоидальной функции y j = y j 1 y j, поk этому на интервале 0 < yj < 1 производная имеет максимальное значение в точке уj = 0,5, а в точках уj = 0 и уj = 1 обращается в ноль. Максимальные изменения весов соответствуют блокам (нейронам), которые ещё не выбрали своё состояние. Кроме того, при конечных значениях весовых коэффициентов выходные сигналы блоков не могут достигать значений 0 или 1. Поэтому за 0 обычно принимают значения yj < 0,1, а за 1 – значения yj > 0,9.

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

Алгоритм обратного распространения ошибки используется также для обучения сетей с обратными связями. При этом используется эквивалентность многослойной сети с прямыми связями и синхронной сети с обратными связями на ограниченном интервале времени (слой соответствует такту времени).

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

2.5. Способы реализации нейронных сетей Нейронные сети могут быть реализованы программным или аппаратным способом.

Вариантами аппаратной реализации являются нейрокомпьютеры, нейроплаты и нейроБИС (большие интегральные схемы). Одна из самых простых и дешёвых нейроБИС – модель MD 1220 фирмы Micro Devices, которая реализует сеть с 8 нейронами и 120 синапсами.

Среди перспективных разработок можно выделить модели фирмы Adaptive Solutions (США) и Hitachi (Япония). Разрабатываемая фирмой Adaptive Solutions нейроБИС является одной из самых быстродействующих: объявленная скорость обработки составляет 1,2 млрд. межнейронных соединений в секунду (мнс/с). Схемы, производимые фирмой Hitachi, позволяют реализовывать ИНС, содержащие до 576 нейронов.

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

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

Типичными представителями таких систем являются компьютеры семейства Mark фирмы TRW (первая реализация перцептрона, разработанная Ф. Розенблатом, называлась Mark I). Модель Mark III фирмы TRW представляет собой рабочую станцию, содержащую до 15 процессоров семейства Motorola 68000 с математическими сопроцессорами. Все процессоры объединены шиной VME. Архитектура системы, поддерживающая до 65 000 виртуальных процессорных элементов с более чем 1 млн. настраиваемых соединений, позволяет обрабатывать до 450 тыс. мнс/с.

Другим примером является нейрокомпьютер NETSIM, созданный фирмой Texas Instruments на базе разработок Кембриджского университета. Его топология представляет собой трёхмерную решётку стандартных вычислительных узлов на базе процессоров 80188. Компьютер NETSIM используется для моделирования сетей Хопфилда– Кохонена. Его производительность достигает 450 млн. мнс/с.

В тех случаях, когда разработка или внедрение аппаратных реализаций нейронных сетей обходятся слишком дорого, применяют более дешёвые программные реализации. Одним из самых распространённых программных продуктов является семейство программ Brain Maker фирмы CSS (California Scientific Software). Первоначально разработанный фирмой Loral Space Systems no заказу NASA и Johnson’s Space Center пакет Brain Maker был вскоре адаптирован для коммерческих приложений и сегодня используется несколькими тысячами финансовых и промышленных компаний, а также оборонными ведомствами США для решения задач прогнозирования, оптимизации и моделирования ситуаций. Назначение пакета Brain Maker – решение задач, для которых пока не найдены формальные методы и алгоритмы, а входные данные неполны, зашумлены и противоречивы. К таким задачам относятся прогнозирование курсов валют и акций на биржах, моделирование кризисных ситуаций, распознавание образов и многие другие. Brain Maker решает поставленную задачу, используя математический аппарат теории нейронных сетей (более конкретно – сеть Хопфилда с обучением по методу обратного распространения ошибки).

В оперативной памяти строится модель многослойной нейронной сети, которая обладает свойством обучаться на множестве примеров, оптимизируя свою внутреннюю структуру. При правильном выборе структуры сети после её обучения на достаточно большом количестве примеров можно добиться высокой достоверности результатов (97% и выше). Существуют версии Brain Maker для MS DOS и MS Windows, а также для Apple Macintosh. Кроме базовой версии пакета в семейство Brain Maker входят следующие дополнения:

Brain Maker Student – версия пакета для университетов. Она особенно популярна у небольших фирм, специализирующихся на создании приложений для не очень сложных задач.

Toolkit Option – набор из трёх дополнительных программ, увеличивающих возможности Brain Maker. Binary, которая переводит обучающую информацию в двоичный формат для ускорения обучения;

Hypersonic Training, где используется высокоскоростной алгоритм обучения; Plotting, которая отображает факты, статистику и другие данные в графическом виде.

Brain Maker Professional – профессиональная версия пакета Brain Maker с расширенными функциональными возможностями включает в себя все опции Toolkit.

Genetic Training Option (для Brain Maker Pro) – программа автоматической оптимизации нейронной сети для решения заданного класса задач, использующая генетические алгоритмы для селекции наилучших решений.

Data Maker Editor – специализированный редактор для автоматизации подготовки данных при настройке и использовании нейронной сети.

Training Financial Data – специализированные наборы данных для настройки нейронной сети на различные виды аналитических, коммерческих и финансовых операций, которые включают реальные значения макроэкономических показателей NYSE, NADDAW, ASE, OEX, DOW и др., индексы инфляции, статистические данные биржевых сводок по различным видам продукции, а также информацию по фьючерсным контрактам и многое другое.

Brain Maker Accelerator – специализированная нейроплата– акселератор на базе сигнальных процессоров TMS320C25 фирмы Texas Instruments. Вставленная в персональный компьютер, она в несколько раз ускоряет работу пакета Brain Maker.

Brain Maker Accelerator Pro – профессиональная многопроцессорная нейронная плата. Она содержит пять сигнальных процессоров TMS320C30 и 32 Мбайт оперативной памяти.

В настоящее время на рынке программных средств имеется большое количество разнообразных пакетов для конструирования нейронных сетей и решения различных задач. Пакет Brain Maker можно назвать ветераном рынка. Кроме представителей этого семейства, к хорошо известным и распространённым программным средствам можно отнести Neuro Shell (Ward System's Group), Neural Works (Neural Ware Inc.) и Neuro Solutions (Neuro Dimension Inc.). Объектноориентированные программные среды семейства Neuro Solutions предназначены для моделирования ИНС произвольной структуры. Пользователю систем Neuro Solutions предоставлены возможности исследования и диалогового управления. Все данные в сети доступны для просмотра в процессе обучения посредством разнообразных инструментов визуализации. Проектирование ИНС в системе Neuro Solutions основано на модульном принципе, который позволяет моделировать стандартные и новые топологии. Важным преимуществом системы является наличие специальных инструментов, позволяющих моделировать динамические процессы в ИНС.

2.6. Практическое применение нейросетевых технологий Применение нейросетевых технологий целесообразно при решении задач, имеющих следующие признаки:

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

наличие большого объёма входной информации, характеризующей исследуемую проблему;

зашумлённость, частичная противоречивость, неполнота или избыточность исходных данных.

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

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

Рассмотрим решение задачи прогнозирования цены закрытия на завтра по акциям некоторого предприятия X. Для моделирования воспользуемся данными наблюдений за месяц. В качестве исходных данных можно использовать индикаторы Dow Jones, NIKKEI, FTSE100, индексы и акции российских компаний, «сезонные» переменные и др.

Относительный показатель однодневной доходности предприятия можно определить из соотношений:

где Pi – оценка операции «вчера купил, сегодня продал»; Pi – оценка операции «вчера продал, сегодня купил»; Pi – значение выбранного показателя доходности в i-й день; Pi 1 – значение показателя в (i – 1)-й день.

Итоговая доходность за установленный интервал времени (n дней) рассчитывается по формуле Результаты оценки доходности предприятия за 30 дней с использованием различных моделей ИНС, а также доходов «идеального»

трейдера приведены ниже.

Стандартная трёхслойная сеть

Стандартная четырёхслойная сеть

Рекуррентная сеть с обратной отрицательной связью от скрытого слоя

Рекуррентная сеть с отрицательной обратной связью.......... 0, Сеть Ворда: с тремя скрытыми блоками, с разными передаточными функциями

Трёхслойная сеть с обходным соединением

Четырёхслойная сеть с обходными соединениями............... 0, Сеть с общей регрессией

Сеть метода группового учёта аргументов

Сеть Ворда: с тремя скрытыми блоками, с разными передаточными функциями, с обходным соединением..….. 0, «Идеальный» трейдер

«Идеальный трейдер» знает цену закрытия на следующий день и поэтому получает максимально возможную прибыль. Трейдер пользуется значением нейросетевого индикатора следующим образом: на основе прогнозируемого в (i – 1)-й день значения Pi, (величина относительно изменения цены закрытия по акциям рассматриваемого предприятия X на завтрашний i-й день) трейдер принимает решение о покупке ( Pi > 0) или продаже ( Pi < 0) акций.

Анализ результатов моделирования показывает, что лучшую доходность обеспечила рекуррентная сеть с отрицательной обратной связью (45% за 30 дней). Динамика изменения однодневных показателей доходности, полученных с помощью этой ИНС, приведена на рис. 2.5.

Рис. 2.5. Динамика изменения доходности (Ri) и цен закрытия (Pi) за 30 торговых дней, полученная на рекуррентной сети Нейросетевые технологии активно используются в маркетинге для моделирования поведения клиентов и распределения долей рынка.

Нейросетевые технологии позволяют отыскивать в маркетинговых базах данных скрытые закономерности.

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

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

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

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

1. Необходимо как минимум 50, а лучше 100 наблюдений для создания приемлемой модели. Это достаточно большое число данных и они далеко не всегда доступны. Например, при производстве сезонного товара истории предыдущих сезонов недостаточно для прогноза на текущий сезон из-за изменения стиля продукта политики продаж и т.д. Даже при прогнозировании спроса на достаточно стабильный продукт на основе информации о ежемесячных продажах трудно накопить исторические данные за период от 50 до 100 месяцев. Для сезонных товаров проблема ещё более сложна, так как каждый сезон фактически представляет собой одно наблюдение. При дефиците информации модели ИНС строят в условиях неполных данных, а затем проводят их последовательное уточнение.

2. Построение нейронных сетей требует значительных затрат труда и времени для получения удовлетворительной модели. Необходимо учитывать, что излишне высокая точность, полученная на обучающей выборке, может обернуться неустойчивостью результатов на тестовой выборке – в этом случае происходит «переобучение» сети.

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

3. При обучении нейронных сетей могут возникать «ловушки», связанные с попаданием в локальные минимумы. Детерминированный алгоритм обучения не в силах обнаружить глобальный экстремум или покинуть локальный минимум. Одним из приёмов, который позволяет обходить ловушки, является расширение размерности пространства весов за счёт увеличения числа нейронов скрытых слоёв. Некоторые возможности для решения этой проблемы открывают стохастические методы обучения. При модификации весов сети только на основе информации о направлении вектора градиента целевой функции в пространстве весов можно достичь локального минимума, но невозможно выйти из него, поскольку в точке экстремума «движущая сила» (градиент) обращается в нуль и причина движения исчезает. Чтобы покинуть локальный экстремум и перейти к поиску глобального, нужно создать дополнительную силу, которая будет зависеть не от градиента целевой функции, а от каких-то других факторов. Один из простейших методов состоит в том, чтобы просто создать случайную силу и добавить её к детерминистической.

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

5. Неудачный выбор диапазона входных переменных – достаточно элементарная, но часто совершаемая ошибка. Если хi – двоичная переменная со значениями 0 и 1, то примерно в половине случаев она будет иметь нулевое значение: хi = 0. Поскольку хi входит в выражение для модификации веса в виде сомножителя, то эффект будет тот же, что и при насыщении: модификация соответствующих весов будет блокирована. Правильный диапазон для входных переменных должен быть симметричным, например от +1 до –1 [2, 12].

6. Процесс решения задач нейронной сетью является «непрозрачным» для пользователя, что может вызывать с его стороны недоверие к прогнозирующим способностям сети.

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

8. Отсутствуют теоретически обоснованные правила конструирования и эффективного обучения нейронных сетей. Этот недостаток приводит, в частности, к потере нейронными сетями способности обобщать данные предметной области в состояниях переобучения (перетренировки).

1. Опишите модель искусственного нейрона. Приведите примеры передаточных функций.

2. Сравните свойства биологических и искусственных нейронных сетей.

3. Проведите сравнение однослойных и многослойных ИНС.

4. Раскройте особенности рекуррентных и самоорганизующихся сетей.

5. Расскажите о моделях сетей Хопфилда и Кохонена.

6. Дайте характеристику основных этапов построения нейронной сети.

7. Расскажите о методах обучения ИНС (коррекция по ошибке, обучение Хебба, соревновательное обучение, метод обратного распространения ошибки).

8. Опишите алгоритм обратного распространения ошибки.

Сформулируйте его достоинства и недостатки.

9. Назовите и охарактеризуйте парадигмы обучения нейронной сети.

10. Расскажите об известных вам способах реализации ИНС.

11. Поясните условия применимости ИНС. Сформулируйте основные проблемы, возникающие при применении нейронных сетей.

12. Назовите негативные последствия переобучения нейронной сети.

13. Подготовьте набор содержательных примеров для обучения нейронной сети с заданной целью.

14. Изобразите наиболее известные функции активации и дайте им характеристику.

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

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

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

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

19. Сформулируйте задачу прогнозирования для решения с помощью технологии нейронных сетей. Подготовьте необходимые данные, выберите топологию сети.

20. Аргументировано выберете случай, в котором целесообразно применение ИНС:

а) выявление тенденций, взаимосвязей в больших объёмах данных, искажённых шумами;

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

21. Расскажите про выбор архитектуры и настройку многослойной нейронной сети.

22. Расскажите о задачах, решаемых при помощи самоорганизующихся карт Кохонена.

23. Назовите достоинства и недостатки алгоритма обратного распространения ошибки.

24. Назовите и дайте краткую характеристику базовым архитектурам нейронных сетей.

25. Расскажите о проблемах практического использования искусственных нейронных сетей.

1. Барцев, С.И. Адаптивные сети обработки информации / С.И. Барцев, В.А. Охонин. – Красноярск : Институт физики СО АН СССР, 1986.

2. Галушкин, А.И. Нейронные сети. Основы теории / А.И. Галушкин. – М. : Горячая Линия-Телеком, 2012. – 496 с.

3. Комьютер обретает разум / под ред. В.А. Стефанюк. – М. :

Мир, 1990. – 240 с.

4. Осовский, С. Нейронные сети для обработки информации / С. Осовский ; пер. с польс. И.Д. Рудинского. – М. : Финансы и статистика, 2002.

5. Лозин, Н.В. Моделирование нейронных структур / Н.В. Лозин. – М. : Наука, 1970.

6. Розенблат, Ф. Принципы нейродинамики / Ф. Розенблат. – М. : Мир, 1965.

7. Рутковская, Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская, М. Пилиньский, Л. Рутковский. – М. : Горячая Линия-Телеком, 2007.

8. Соколов, Е.Н. Нейроинтеллект: от нейрона к нейрокомпьютеру / Е.Н. Соколов, Г.Г. Вайтнявичус. – М. : Наука, 1989.

9. Толкачев, С. Нейронное программирование диалоговых систем / С. Толкачев. – М. : Корона-Век, 2011.

10. Трикоз, Д.В. Нейронные сети: как это делается? / Д.В. Трикоз // Компьютеры + программы. – 1992. – № 4, 5.

11. Уоссермен, Ф. Нейрокомпьютерная техника: Теория и практика / Ф. Уоссермен. – М. : Мир, 1992.

12. Фролов, Ю.В. Интеллектуальные системы и управленческие решения / Ю.В. Фролов. – М. : Изд-во МГПУ, 2000.

13. Хинтон, Дж.Е. Как обучаются нейронные сети / Дж.Е. Хинтон // В мире науки. – 1992.– № 11, 12.

14. Элементарное введение в технологию нейронных сетей с примерами программ / Р.Тадеусевич [и др.]. – М. : Горячая ЛинияТелеком, 2011.

15. Kohonen, Т. Self-organization and associative memory / Т. Kohonen. – New York : Springer, 1984.

3. ЭВОЛЮЦИОННЫЕ АНАЛОГИИ

В ИСКУССТВЕННЫХ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ

Эволюционное моделирование можно определить как воспроизведение процесса естественной эволюции с помощью специальных компьютерных программ. Термин эволюция в ограниченном смысле, касающемся только смены поколений организмов, начал широко использоваться в XVII в. С появлением в 1859 г. учения Дарвина этот термин приобрёл современное толкование: «Биологическая эволюция – историческое развитие организмов». Необходимые и достаточные условия, определяющие главные факторы эволюции, были сформулированы в XX в. на основе созданной популяционно-генетической теории. К факторам, определяющим неизбежность эволюции, относятся:

наследственная изменчивость как предпосылка эволюции, её материал;

борьба за существование как контролирующий и направляющий фактор;

естественный отбор как преобразующий фактор.

На рисунке 3.1 приведена конкретизация факторов эволюции, учитывающая многообразие форм их проявления, взаимосвязей и взаимовлияния [11]. Главные факторы выделены пунктиром.

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

Преобразования генофонда популяции происходят под управлением естественного отбора.

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

История эволюционных вычислений началась с разработки ряда независимых моделей, среди которых были генетические алгоритмы и классификационные системы, созданные американским исследователем Дж. Холландом. Он предложил использовать методы и модели развития органического мира на Земле в качестве механизма комбинаторного пеРис. 3.1. Схема взаимодействия факторов эволюции ребора вариантов при решении оптимизационных задач [14, 26].

Компьютерные реализации этого механизма получили название «генетические алгоритмы». В 1970-х гг. в рамках теории случайного поиска Л.А. Растригиным был предложен ряд алгоритмов, использующих идеи бионического поведения особей [10]. Развитие этих идей нашло отражение в цикле работ И.Л. Букатовой по эволюционному моделированию [2, 3]. Идеи М.Л. Цетлина, развитые в исследованиях поведения сообществ конечных автоматов, легли в основу алгоритмов поиска глобального экстремума, основанных на моделировании процессов развития и элиминации особей [15]. Большой вклад в развитие эволюционного программирования внесли работы Л. Фогеля, А. Оуэнса и М. Уолша [12, 20, 21].

К основным направлениям развития эволюционного моделирования на современном этапе относятся следующие:

генетические алгоритмы (ГА), предназначенные для оптимизации функций дискретных переменных и использующие аналогии естественных процессов рекомбинации и селекции;

классифицирующие системы (КС), созданные на основе генетических алгоритмов, которые используются как обучаемые системы управления;

генетическое программирование (ГП), основанное на использовании эволюционных методов для оптимизации создаваемых компьютерных программ;

эволюционное программирование (ЭП), ориентированное на оптимизацию непрерывных функций без использования рекомбинаций;

эволюционные стратегии (ЭвС), ориентированные на оптимизацию непрерывных функций с использованием рекомбинаций.

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

В России развитием эволюционных методов занимаются научные школы профессоров И.Л. Букатовой [2, 3], Д.И. Батищева [1], В.М. Курейчика [7 – 9] и И.П. Норенкова [6].

В основе генетических алгоритмов лежат генетика и хромосомная теория эволюции организмов. Хромосомы – это нитевидные структуры, находящиеся в клеточном ядре, которые являются носителями наследственности. Каждая хромосома уникальна морфологически и генетически и не может быть заменена другой либо восстановлена при утере (при потере хромосомы клетка, как правило, погибает). Каждый биологический вид имеет определённое, постоянное количество хромосом. Каждая клетка содержит удвоенный набор морфологически и генетически сходных хромосом. Например, в клетках человека содержится 23 пары хромосом, в клетках комара – 3.

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

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

В фазе редукции хроматиды обмениваются генами, т.е. участками дезоксирибонуклеиновой кислоты (ДНК). После этого клетка разделяется на две новые, причём каждая из них содержит удвоенный набор хромосом, структуры которых отличаются от исходных. Механизм обмена генами называется кроссинговером.

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

Таким образом, митоз обеспечивает возобновление клеток, а мейоз отвечает за передачу наследственной информации и способствует генетическому разнообразию организмов данного вида.

Классическая генетика обосновала наследственность и изменчивость благодаря созданию фундаментальной теории гена, основные положения которой формулируются следующим образом:

все признаки организма определяются наборами генов;

гены – это элементарные единицы наследственной информации, которые находятся в хромосомах;

гены могут изменяться – мутировать;

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

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

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

1) рекомбинация хромосомных и нехромосомных генов;

2) рекомбинация целевых негомологических хромосом;

3) рекомбинация участков хромосом, представленных непрерывными молекулами ДНК.

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

Кроссинговер соответствует регулярной рекомбинации, при которой происходит обмен определёнными участками между гомологичными хромосомами. Он приводит к появлению нового сочетания сцепленных генов.

Сайт – это вид рекомбинации, при которой на коротких специализированных участках хромосом происходит обмен генофоров (генных носителей), часто различных по объёму и составу генетической информации.

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

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

Основная цель кроссинговера заключается в создании из имеющегося генетического материала желаемой комбинации признаков в одном решении.

Кроссинговер может происходить в нескольких точках. Пример двойного кроссинговера между хромосомами приведён на рис. 3.4.

а – родительские хромосомы А, В до кроссинговера;

б – хромосомы-потомки А', В' после кроссинговера Рис. 3.4. Схема двойного кроссинговера:

а – до кроссинговера; б – во время кроссинговера; в – после кроссинговера Помимо кроссинговера для решения различных прикладных задач полезными являются такие генетические операции, как мутация, инверсия, транслокация, селекция (инбридинг и гибридизация), генная инженерия.

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

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

Инверсия, транслокация, транспозиция, делеция и дупликация относятся к разновидностям хромосомной мутации. При инверсии участок хромосомы поворачивается на 180°. Транслокацией называют перенос части одной хромосомы в другую. При перемещении небольших участков генетического материала в пределах одной хромосомы используют термин транспозиция. Делеция – это выпадение отдельных участков хромосом, дупликация – повторение участка генетического материала. Кроме перечисленных, существуют другие разновидности хромосомных мутаций [7].

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

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

Механизм эволюции основан на трёх повторяющихся процессах:

отборе, амплификации (процесс производства потомков) и мутации.

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

Генетический алгоритм – это поисковый алгоритм, основанный на природных механизмах селекции и генетики. Эти алгоритмы обеспечивают выживание сильнейших решений из множества сгенерированных, формируя и изменяя процесс поиска на основе моделирования эволюции исходной популяции решений. Генетические алгоритмы сконструированы таким образом, что при генерации каждой новой популяции используются фрагменты исходных решений, к которым добавляются новые элементы, обеспечивающие улучшение решений относительно сформулированного критерия отбора. Другими словами, генетические алгоритмы используют информацию, накопленную в процессе эволюции [2, 3, 7, 8, 16, 22 – 26].

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

Генетика Генетические алгоритмы Хромосома Решение, стринг, строка, последовательность, Популяция Набор решений (хромосом) Локус Местоположение гена в хромосоме Поколение Цикл работы генетического алгоритма, в процессе которого сгенерировано множество решений Ген Элемент, характеристика, особенная черта, Аллель Значение элемента, характеристики Эпистасис Множество параметров, альтернативные решения Скрещивание, Оператор рекомбинации рекомбинация, кроссинговер Мутация Оператор модификации При разработке генетических алгоритмов преследуются две главные цели:

абстрактное и формальное объяснение процессов адаптации в естественных системах;

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

Основные отличия ГА от других алгоритмов оптимизации:

используются не параметры, а закодированные множества параметров;

поиск осуществляется не из единственной точки, а из популяции точек;

в процессе поиска используются значения целевой функции, а не её приращения;

применяются вероятностные, а не детерминированные правила поиска и генерации решений;

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

Согласно репродуктивному плану Холланда [14, 26] генетические схемы поиска оптимальных решений включают следующие этапы процесса эволюции:

1. Конструируется начальная популяция. Вводится начальная точка отсчёта поколений t = 0. Вычисляются приспособленность хромосом популяции (целевая функция) и средняя приспособленность всей популяции.

2. Устанавливается значение t = t + 1. Выбираются два родителя (хромосомы) для кроссинговера. Выбор осуществляется случайным образом пропорционально жизнеспособности хромосом, которая характеризуется значениями целевой функции.

3. Формируется генотип потомка. Для этого с заданной вероятностью над генотипами выбранных хромосом производится операция кроссинговера. Случайным образом выбирается один из потомков A(t), который сохраняется как член новой популяции. Далее к потомку A(t) последовательно с заданными вероятностями применяются операторы инверсии и мутации. Полученный в результате генотип потомка сохраняется как A'(t).

4. Обновление текущей популяции путём замены случайно выбранной хромосомы A'(t).

5. Определение приспособленности A'(t) и пересчёт средней приспособленности популяции.

6. Если t = t*, где t* – заданное число шагов, то переход к этапу 7, в противном случае – переход к этапу 2.

7. Конец работы.

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

Простой генетический алгоритм [23, 26] включает операцию случайной генерации начальной популяции хромосом и ряд операторов, обеспечивающих генерацию новых популяций на основе начальной.

Этими операторами являются репродукция, кроссинговер и мутация.

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

Рассмотрим пример применения простого генетического алгоритма для максимизации функции f (x ) = x 2 на целочисленном интервале [0, 31] (пример взят из монографии В.М. Курейчика «Генетические алгоритмы» [7]).

Значения аргумента функции f (x ) = x 2, изменяющегося в интервале от 0 до 31, можно представить пятиразрядными двоичными числами. Первоначальная популяция, состоящая из четырёх строк пятиразрядных чисел, полученная с помощью процедуры генерации случайных чисел, приведена во втором столбце табл. 3.1. Значение целеАнализ начальной популяции на первом шаге простого генетического алгоритма хромосомы Номер Суммарная Среднее значение целевой функции Максимальное значение вой функции для каждой хромосомы определяется путём возведения в квадрат значения двоичного числа, кодирующего решение х. Претенденты для скрещивания (кроссинговера) могут выбираться из начальной популяции или после выполнения оператора репродукции.

Репродукция начального множества заключается в четырёхкратном вращении колеса рулетки (4 – мощность популяции), в результате чего состав исходной популяции может измениться (рис. 3.5). Вероятность выбора i-й хромосомы вычисляется по формуле где fi (x) – значение целевой функции i-й хромосомы в популяции;

sum f (x ) – суммарное значение целевой функции всех хромосом в популяции.

Ожидаемое число копий i-й хромосомы после оператора репродукции равно где n – число анализируемых хромосом.

Число копий хромосомы, переходящих в следующее поколение, определяют по формуле где f ср (x ) – среднее значение целевой функции.

3.2. Результаты операций репродукции и кроссинговера хромосомы Номер Суммарное значение целевой функции sum f ( x) = Среднее значение целевой функции f ср ( x ) = Максимальное значение целевой функции f (x) = Значение N для первой хромосомы будет равно 0,14 4 = 0,56 копий, для второй – 0,49 4 = 1,96 копий, для третьей – 0,06 4 = 0,24 и для четвёртой – 0,31 4 = 1,23. В результате репродукции в новой популяции (второй столбец в табл. 3.2) будут присутствовать по одной копии первой и четвёртой хромосомы и две копии второй, а третья хромосома будет исключена. Таким способом оператор репродукции отбирает лучших представителей популяции.

На шаге 2 с помощью колеса рулетки осуществляется выбор хромосом для кроссинговера. Поля колеса рулетки соответствуют нормированным значениям целевой функции. Указатель рулетки после остановки колеса определяет выбранную хромосому.

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

После репродукции выполняется оператор кроссинговера, который может повторяться несколько раз. При этом каждый раз будет осуществляться выбор двух кандидатур из множества хромосом. Затем каждая пара хромосом (стрингов) пересекается. Место пересечения K выбирается случайным образом на интервале (1, L – 1), где L – длина хромосомы, определяемая количеством значащих цифр в её двоичном коде. В нашем случае L = 5. Две новые хромосомы создаются путём взаимного обмена всех значений после точки пересечения, т.е. между позициями (K + 1) и L. При выборе двух первых хромосом из популяции (см. табл. 3.1) и значения K = 4 до применения оператора кроссинговера имеем описание а после применения оператора кроссинговера получаем описание Аналогично были получены потомки от третьей и четвёртой хромосом.

Анализ полученных результатов (см. табл. 3.2) показывает, что после проведения одной генерации улучшились и среднее, и максимальное значение целевой функции по сравнению с начальной популяцией (см. табл. 3.1).

Согласно схеме простого генетического алгоритма на шаге 3 выполняется оператор мутации, который играет существенную роль в естественной генетике и эволюции, но менее значим в генетических алгоритмах. Обычно выбирают одну мутацию на 1000 бит. Оператор мутации относится к унарным операциям и реализуется в два этапа.

Этап 1. В хромосоме A = { a1, a 2, a3,..., a L 2, a L 1, a L } случайным образом определяют две позиции, например, 2 и L – 1.

Этап 2. Гены, соответствующие выбранным позициям, меняют местами и формируют новую хромосому A = { a1, a L1, a3,..., Если длина обрабатываемых последовательностей невелика, то в процессе мутации можно осуществить полный перебор возможных перестановок генов и найти комбинацию с максимальным значением целевой функции. При длине хромосомы L = 50 – 200 полный перебор вариантов становится затруднительным, поэтому здесь производится случайно-направленный поиск, который может быть реализован на основе простого генетического алгоритма. Рассмотрим этот механизм на исследуемой задаче.

Выберем третью хромосому из пятого столбца табл. 3.2 со значением целевой функции f (х) = 729 и применим операцию мутации к позициям 3 и 4:

У новой хромосомы 3' значение целевой функции равно (29)2 = 841. Сделаем ещё одну перестановку 4 и 5 генов в хромосоме 3':

хромосома 3': 11101 хромосома 3": 11110.

Значение целевой функции для хромосомы 3" равно 900, что соответствует квазиоптимальному решению задачи нахождения максимального значения функции f (x ) = x 2 на интервале [0,31].

В генетических алгоритмах и эволюционном программировании используют два основных механизма воспроизводства хромосом:

воспроизводство без мутаций, соответствующее митозу, результатом которого являются потомки – копии родителей;

воспроизводство потомков, имеющих большие отличия от родителей. Этот механизм соответствует половому размножению.

В генетических алгоритмах в основном используется механизм родительского воспроизводства [4] с рекомбинацией и мутацией, а в эволюционном программировании – механизм на основе мутации без рекомбинации.

В алгоритмических реализациях механизма воспроизводства хромосом следует придерживаться следующих правил.

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

2. Репродукция осуществляется на основе моделирования движения колеса рулетки.

3. Оператор кроссинговера реализуется как взаимный обмен короткими фрагментами двоичных строк гомологичных хромосом.

4. Вероятность оператора кроссинговера принимается равной Р(СО) < 1.0.

5. Вероятность оператора мутации принимается равной Р(МО) > 0.001.

Разновидности генетических алгоритмов. Генетический алгоритм Девиса [25] включает следующие шаги:

1. Инициализация популяции хромосом.

2. Оценка каждой хромосомы в популяции.

3. Создание новых хромосом посредством изменения и скрещивания текущих хромосом (применение операторов мутации и кроссинговера).

4. Устранение хромосом из популяции для замены их новыми.

5. Оценка новых хромосом и включение их в популяцию.

6. Проверка условия исчерпания ресурса времени, отведённого на поиск оптимального решения (если время исчерпано, то работа алгоритма завершается и производится возврат к наилучшей хромосоме, в противном случае – переход к шагу 3).

Холланд [14, 26] предложил для генетического алгоритма оператор инверсии, который реализуется по схеме:

1. Стринг (хромосома) B = { b1, b2,..., bL } выбирается случайным образом из текущей популяции.

2. Из множества Y = {0, 1, 2,..., L + 1} случайным образом выбираются два числа y1 и у2 и определяются значения x1 = min{y1, y2 } и x2 = max{y1, y 2 }.

3. Из хромосомы В формируется новая хромосома путём инверсии (обратного порядка) сегмента, лежащего справа от позиции х1 и слева от позиции х2 в хромосоме В. После применения оператора инверсии строка В примет вид B = { b1, bx1, bx 2 1, bx 2 2, bx1+1, bx 2,..., bL }.

Например, для строки В = {1, 2, 3, 4, 5, 6} при выборе у1 = 6 и у2 = 2 и соответственно x1 = 2, x2 = 6 результатом инверсии будет B = {1, 2, 5, 4, 3, 6}.

Операции кроссинговера и мутации, используемые в простом ГА, изменяют структуру хромосом, в том числе разрушают удачные фрагменты найденных решений, что уменьшает вероятность нахождения глобального оптимума. Для устранения этого недостатка в генетических алгоритмах используют схемы (схематы или шаблоны), представляющие собой фрагменты решений или хромосом, которые желательно сохранить в процессе эволюции. При использовании схем в генетическом алгоритме вводится новый алфавит {0,1,*}, где * интерпретируется как «имеет значение 1 или 0». Например:

схема (*0000) соответствует двум стрингам {10000 и 00000};

схема (*111*) соответствует четырём строкам {01110, 11110, 01111, 11111};

схема (0*1**) может соответствовать восьми пятизначным стрингам.

В общем случае хромосома длиной L максимально может иметь 3L схем (шаблонов), но только 2L различных альтернативных стрингов.

Это следует из факта, что схеме (**) в общем случае могут соответствовать 32 = 9 стрингов, а именно {**,*1,*0,1*, 0*,00,01,1011}, и только 22 = 4 альтернативные строки {00,01,10,11}, т.е. одной и той же строке может соответствовать несколько схем.

Если в результате работы генетического алгоритма удалось найти схемы типа (11***) и (**111), то, применив к ним оператор кроссинговера, можно получить хромосому (11111), обладающую наилучшим значением целевой функции.

Схемы небольшой длины называются строительными блоками.

Размер строительных блоков заметно влияет на качество и скорость нахождения результата. Вид строительного блока выбирается с учётом специфики решаемой задачи, а их разрыв в генетических алгоритмах допускается только в исключительных случаях, определяемых пользователем. Например, в схеме (****1) строительным блоком является элемент 1, а в схеме (10***) – составной элемент 10.

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

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

Процедура удаления лишних хромосом в стационарных и поколенческих генетических алгоритмах основана на эвристических правилах, примерами которых являются следующие:

случайное равновероятное удаление хромосом;

удаление хромосом, имеющих худшие значения целевой функции;

удаление хромосом на основе обратного значения целевой функции;

удаление хромосом на основе турнирной стратегии.

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

Фундаментальная теорема генетического алгоритма. Пусть в момент времени t в популяции S(t) содержится множество хромосом Sj, j = 1, 2,.., n, а схема H строится на основе алфавита V = {0,1,*}. Тогда схема может быть определена на двоичной хромосоме длины L. Очевидно, что для алфавита мощности М существует (М + l)L схем и n2L схем, содержащихся в популяции размера n, поскольку стринг представляется двумя схемами.

Для количественной оценки схем введём две характеристики: порядок схемы О(Н) и определённая длина схемы L(H). Порядок схемы определяет число закреплённых позиций (в двоичном алфавите – число единиц и нулей), представленных в шаблоне. Определённая длина схемы – это расстояние между первой и последней числовой позицией стринга.

Предположим, что заданы шаг по времени t и m примеров схем Н, содержащихся в популяции S(t), которые определяют возможное число различных схем Н при заданном t, т.е. m = m{Н,t).

В процессе репродукции вероятность попадания хромосомы Si в значения целевой функции. За время t + 1 в популяции S(t) ожидается получить m (Н, t + 1) представителей схемы Н, которое вычисляется по формуле где f (H) – среднее значение целевой функции хромосом, представленных схемой H за время t.

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

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

Если предположить, что схема H является жизнеспособной, то f (H ) f ср (S ). Тогда значение целевой функции для схемы H можно выразить через среднее значение для всей популяции, например, следующим образом: (1+ c ) f ср (S ), где с – константа. Число представителей схемы в следующем поколении будет Если принять значение с постоянным во времени, то за период 0 < t < t* можно вычислить количество представителей схемы H по формуле m (H, t ) = (1 + c )t m (H, 0), из которой следует, что репродукция может приводить к экспоненциальному увеличению (с > 0) или уменьшению (с < 0) числа схем.

Лемма. Если на некотором шаге генетического алгоритма Р1 есть вероятность того, что хромосома А порождает потомка, и Р2 есть вероятность, что А уничтожается, то ожидаемое число потомков хромосомы А равно Р1 / Р2 [26].

Вероятность выживания хромосомы А на шаге t после операции репродукции определяется по формуле PS (t ) = (1 P2 ) P2, где t = 1, 2,..., g; g – число шагов (генераций) генетического алгоритма. Значение вероятности выживания хромосомы изменяется после операций кроссинговера и мутации. Использование оператора кроссинговера может вызывать увеличение или уменьшение числа схем в популяции.

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

Вероятность выживания схемы после применения оператора кроссинговера определяется по формуле где О(Н) – порядок схемы; L – длина стринга.

Если оператор кроссинговера выполняется на основе случайного выбора с вероятностью Р(СО), то вероятность выживания схемы определяется по формуле где L(H) – определённая длина схемы.

Приведённое выражение свидетельствует о том, что вероятность выживания схемы уменьшается при возрастании Р(СО).

Вычислим число схем Н в новой генерации после операций репродукции и кроссинговера, допуская их взаимную независимость:

Из этого выражения следует, что число схем m (H, t + 1) зависит от значений целевой функции для схемы и для всей популяции, а также от длины схемы L(H).

Рассмотрим влияние мутации на выживание схем. Известно, что единственная хромосома выживает с вероятностью 1 – Р(МО), где Р(МО) – вероятность оператора мутации. Если учесть тот факт, что частная схема выживает в случаях, когда выживает каждая из L(H) закреплённых позиций схемы, то для малых величин Р(МO) new, заменить новым узлом прежний всписке, причём, если прежний узел был в списке CLOSED, перенести его в список OPEN.

5.2. Особенности создания баз данных и правил на языке CLIPS При работе с CLIPS применяется понятие факта.

Факт представляет собой основную единицу данных, используемую правилами. Факты помещаются в текущий список фактов fact-list.

Количество фактов в списке и объём информации, содержащейся в факте, ограничивается только размером памяти компьютера [4 – 8].

Факт может описываться индексом или адресом. Всякий раз, когда факт добавляется (изменяется) ему присваивается уникальный целочисленный индекс. Индексы в fact-list начинаются с нуля.

Идентификатор факта – это короткая запись факта, которая состоит из символа факта – f и индекса факта (f-10). Например:

f-0 (today is Sunday), f-1 (weather is warm).

Факты представляются в двух форматах: позиционные и непозиционные.

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

(altitude is 10000 feet) (grocery_list bread milk eggs) (today is Sunday) (weather is warm) Поля в позиционных фактах могут быть любого простого типа, за исключением первого поля, которое всегда должно быть типа symbol.

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

(deffacts today (today is Sunday) (weather is warm)) Выражение начинается с команды deffacts, затем приводится имя списка фактов, который программист собирается определить (в нашем примере – today), а за ним следуют элементы списка, причём их количество не ограничивается.

Конструкция defclass. Прежде чем появится возможность создания экземпляров, в систему CLIPS необходимо передать информацию о списке допустимых слотов для данного конкретного класса. Для этой цели применяется конструкция defclass. В своей наиболее фундаментальной форме эта конструкция весьма напоминает конструкцию deftemplate [4 – 7]:

(defclass [] В этом определении терм определяет класс, от которого данный, вновь создаваемый класс должен наследовать информацию. Классом, от которого в конечном итоге наследуют информацию все определяемые пользователем классы, является системный класс USER. Определяемый пользователем класс должен наследовать информацию либо от другого определяемого пользователем класса, либо от класса USER. Синтаксическое описание определено следующим образом:

С помощью этого синтаксиса экземпляр PERSON может быть описан с использованием такой конструкции defclass:

(defclass PERSON "PERSON defclass" При определении слотов конструкции defclass могут также применяться следующие атрибуты слота из конструкции deftemplate: type, range, cardinality, allowed-symbols, allowed-strings, allowed-Iexemes, allowed-integers, allowed-floats, allowed-numbers, allowed-values, allowedinstance-names, default и default-dynamic.

Пример применения таких атрибутов:

(defclass PERSON "PERSON defclass" Атрибуты слота для конструкций defclass называют также фасетами слота.

В CLIPS существуют следующие зарезервированные слова, которые не могут использоваться как первое поле любого факта: test, and, or, not, declare, logical, object, exists, forall.

Непозиционные факты (шаблонные факты) – реализуются через конструкцию, подобную структуре или записи в языках C и PASCAL.

Шаблонные факты позволяют задавать имена каждому из полей факта.

Для задания шаблона, который затем может использоваться при доступе к полям по именам, используется конструкция (deftemplate (slot-1) (slot-2) (slot-N)), где – имя шаблона, (slot-N) – именованное поле (или слот).

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

(deftemplate student "a student record" (slot name (type STRING)) (slot age (type NUMBER) (default 18))) Каждое определение шаблона состоит из произвольного имени шаблона, необязательного комментария и некоторого количества определений слотов (начинаются с ключевого слова slot или field). Слот включает поле данных, например name, и тип данных, например STRING. Можно указать и значение по умолчанию, как в приведённом выше примере, где возраст студента по умолчанию равен 18.

Если в программу включено приведённое выше определение шаблона, то выражение (deffacts students (student (name "fred")) (student (name "jack") (age 19))) приведёт к тому, что и базу фактов после выполнения команды reset будет добавлено (student (name "fred") (age 18)) (student (name "jack") (age 19)) При работе с базами данных язык CLIPS предоставляет пользователю возможность использования следующих операций над фактами:

добавление к списку фактов (assert); удаление из списка фактов (retract); изменение списка фактов (modify), дублирование списка фактов (duplicate); очищение списка фактов (clear).

Кроме того, команды assert и retract используются в выполняемой части правила (заключении правила) и с их помощью выполняется программное изменение базы фактов. Для вывода списка фактов, имеющихся в базе, используется команда facts. Для удаления из базы массив фактов применяется оператор (команда) undeffacts.

Работа с базой правил основывается на их представлении соответствующими форматами.

В языке CLIPS правила имеют следующий формат [4 – 8]:

< необязательный комментарий > < необязательное объявление > < предпосылка_1 > < предпосылка_m> (defrule chores "Things to do on Sunday" (declare (salience 10)) (today is Sunday) (weather is warm) (assert (wash car)) (assert (chop wood)) В этом примере Chores – произвольно выбранное имя правила.

Предпосылки условной части правила – это (today is Sunday) (weather is warm) сопоставляются затем интерпретатором с базой фактов, а действия, перечисленные в выполняемой части правила (она начинается после пары символов =>), вставят в базу два факта:

(chop wood) в случае, если правило будет активизировано. Приведённый в тексте правила комментарий "Things todo on Sunday" (Что сделать в воскресенье) поможет в дальнейшем вспомнить, чего ради это правило включено в программу. Выражение (declare (salience 10)) указывает на степень важности правила. Пусть, например, в программе имеется другое правило (defrule fun "Better things todo on Sunday" (salience 100) (today is Sunday) (weather is warm) (assert (drink beer)) (assert (play guitar)) Поскольку предпосылки обоих правил одинаковы, то при выполнении оговорённых условий они будут «конкурировать» за внимание интерпретатора, предпочтение будет отдано правилу, у которого параметр salience имеет более высокое значение, в данном случае – правилу fun. Параметру salience может быть присвоено любое целочисленное значение в диапазоне [-10 000, 10 000]. Если параметр salience в определении правила опущен, ему по умолчанию присваивается значение 0.

Обычно в определении правила присутствуют и переменные (они начинаются с символа ?). Если, например, правило (defrule pick-a-chore "Allocating chores to days" (today is ?day) (chore is ?job) (assert (do ?job on ?day))) будет сопоставлено с фактами (today is Sunday) (chore is carwash) то в случае активизации оно включит в базу новый факт (do carwash on Sunday) Аналогично, правило (defrule drop-a-chore "Allocating chores to days" (retract ?chore)) отменит выполнение работ по дому (?chore). Обратите внимание на то, что оба экземпляра переменной ?day должны получить одно и то же значение. Переменная ?chore в результате сопоставления должна получить ссылку на факт (это делает оператор ) Пример:

(deffunction hypotenuse (?а ?b) (sqrt (+ (* ?а ?а) (* ?b ?b))) Аргументы-переменные должны иметь префикс ?, как это показано в приведённом примере.

Вызовы функций в CLIPS имеют префиксную форму: аргументы стоят после её названия. Вызов функции производится в скобках:

(hypotenuse 7 4) После открывающейся скобки следует имя функции, затем идут аргументы, каждый из которых отделён одним или несколькими пробелами. Аргументами функции могут быть данные простых типов, переменные или вызовы других функций.

Функция возвращает результат последнего выражения в списке.

Иногда выполнение функции имеет побочные эффекты, как в приведённом ниже примере.

(deffunction init (?day) (assert (todayis ?day)) В результате после запуска функции на выполнение командой CLIPS> (init Sunday) будет выполнена команда reset и, следовательно, очищена база фактов, а затем в неё будет включён новый факт (today is Sunday).

А в результате запуска функции hypotenuse на выполнение, командой CLIPS> (hypotenuse 3 4) будет выдан известный ответ CLIPS> 5. (deffunction between(?lb ?value ?ub) Эта функция определяет, попало ли заданное целочисленное значение в диапазон между нижним и верхним пределами.

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

Например, переменной ?а присваивается значение 4:

Для более подробного изучения функциональных возможностей языка CLIPS целесообразно воспользоваться литературными источниками [4 – 8].

5.4. Особенности решения задач планирования действий системы Задачи планирования – определить последовательность действий модуля решения, например системы управления. Традиционное планирование основано на знаниях, поскольку создание плана требует организации частей знаний и частичных планов в процедуру решения.

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

Планы создаются путём поиска в пространстве возможных действий до тех пор, пока не будет найдена последовательность, необходимая для решения задачи. Это пространство представляет состояния мира, которые изменяются при выполнении каждого действия. Поиск заканчивается, когда достигается целевое состояние (описание мира) [3].

Приведём фрагмент программы по планированию действий робота «Робот и ящик» [3].

Имеются 2 комнаты – А и В. В комнате А находится робот, в комнате В – ящик. Задача – вытолкнуть ящик в комнату А.

Эта задача решается с помощью шаблонных фактов. Введём шаблон in, определяющий местоположение предмета:

(deftemplate in (slot object (type SYMBOL)) (slotlocation (typeSYMBOL)) Слот object будет задавать название предмета или робота, location – название места, где этот предмет или робот находится.

Чтобы задать роботу конкретную цель действий зададим шаблон goal:

(deftemplate goal (slot object (type SYMBOL)) (slot from (type SYMBOL)) (slot to (type SYMBOL)) слот object определяет название объекта, который необходимо переместить, слоты from и to определяют откуда и куда.

На основе шаблонов in и goal запишем начальные факты:

(deffacts world (in (object robot) (location RoomA)) (in (object box) (location RoomB)) (goal (action push) (object box) (from RoomB) (to RoomA)) Первый факт соответствует тому, что робот находится в комнате А, второй, что ящик в комнате В, третий – перетащить ящик из комнаты B в A.

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

1) перемещение робота в комнату, где находится объект;

2) перемещение робота с объектом в комнату, указанную в цели;

3) остановка программы если цель достигнута.

Реализуем первое действие:

(defrule move (goal (object ?X) (from ?Y)) (in (object ?X) (location ?Y)) ?robot-position (modify ?robot-position (location ?Y)) В данном правиле имеются три предпосылки. В первой предпосылке, использующей шаблон goal, задаются значения переменных ?X и ?Y. Во второй определяется наличие объекта ?X в комнате ?Y.

В третьей предпосылке проверяется, что местоположение робота не соответствует ?Y и запоминается ссылка на данный факт в переменной ?robot-position. Если все предпосылки данного правила истинны, то с помощью оператора modify меняется значение слота location на значение переменной ?Y факта ?robot-position, т.е. робот перемещается в комнату, в которой находится объект, который необходимо переместить.

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

(defrule push (goal (object ?X) (from ?Y) (to ?Z)) ?object-position (halt)) Полный листинг программы представлен в [3].

5.5. Возможности наследования информации Одно из преимуществ использования языка COOL состоит в том, что классы могут наследовать информацию от других классов, что позволяет обеспечить совместный доступ к информации. Рассмотрим, какие действия пришлось бы предпринимать при наличии конструкции deftemplate, которая представляет информацию о людях [4]:

(deftemplate PERSON "PERSON deftemplate" (slot full-name) (slot age) (slot eye-color) (slot hair-color)) В таком случае, если бы потребовалось представить дополнительную информацию, относящуюся к тому, кто является служащим компании или студентом университета, пришлось бы предпринять определённые усилия. Один из возможных подходов мог бы предусматривать дополнение конструкции deftemplate с именем PERSON для включения другой необходимой информации:

(deftemplate PERSON "PERSON deftemplate" (slot full-name) (slot age) (slot eye-color) (slot hair-color) (slot job-position) (slot employer) (slot salary) (slot university) (slot major) (slot GPA)) Но ко всем людям относились бы только четыре слота этой конструкции deftemplate: full-name, age, eye-color и hair-color. С другой стороны, слоты job-position, employer и salary относились бы только к служащим, а слоты university, major и GPA – только к студентам. По мере добавления информации о людях, занимающихся другой деятельностью, приходилось бы вводить всё больше и больше слотов в конструкцию deftemplate с именем PERSON, причём по большей части эти слоты оказались бы неприменимыми для всех людей.

Ещё один подход мог бы состоять в создании отдельных конструкций deftemplate для служащих и студентов, как в следующем примере:

(deftemplate employee "Employee deftemplate" (slot full-name) (slot eye-color) (slot hair-color) (slot job-position) (slot employer) (slot salary)) (deftemplate student "Student deftemplate" (slot full-name) (slot eye-color) (slot hair-color) (slot university) При использовании такого подхода каждая конструкция deftemplate содержит только необходимую информацию, но приходится дублировать некоторые из слотов. Если бы пришлось модифицировать атрибуты одного из таких дублирующихся слотов, то потребовалось бы вносить изменения во многих местах, чтобы обеспечить единообразие представления информации. Кроме того, если бы нужно было написать правило, позволяющее отыскивать всех людей с синими глазами, то пришлось бы использовать два шаблона вместо одного (а если потребовалось бы также включить факты PERSON, количество шаблонов стало бы равным трём), как показано ниже.

(defrule find-blue-eyes (or (employee (full-name ?name) (eye-color blue)) (student (full-name ?name) (eye-color blue))) (printout t ?full-name "has blue eyes." crlf)) Классы позволяют совместно использовать общую информацию, принадлежащую к различным категориям, без дублирования, или включения ненужной информации. Вернёмся к первоначально рассматриваемому определению конструкции defclass с именем PERSON:

(defclass PERSON "PERSON defclass" (is-a USER) (slot full-name) (slot age) (slot eye-color) (slot hair-color)) Чтобы определить новые классы, которые расширяют определение класса PERSON, достаточно указать имя класса PERSON в атрибуте is-a нового класса, как показано ниже.

(defclass EMPLOYEE "Employee defclass" (is-a PERSON) (slot job-position) (slot employer) (slot salary)) (defclass STUDENT "Student defclass" (is-a PERSON) (slot university) (slot major) (slot GPA)) Атрибуты класса PERSON наследуются и в классе EMPLOYEE, и в классе STUDENT. Примеры создания экземпляров для каждого из этих трёх классов иллюстрирует следующий диалог:

CLIPS> (make-instance [John] of PERSON) CLIPS> (make-instance [Jack] of EMPLOYEE) CLIPS> (make-instance [Jill] of STUDENT) CLIPS> (send [John] print) [John] of PERSON (full-name nil) (age nil) (eye-color nil) (hair-color nil) CLIPS> (send [Jack] print) [Jack] of EMPLOYEE (full-name nil) (eye-color nil) (hair-color nil) (job-position nil) (employer nil) CLIPS> (send [Jill] print) [Jill] of STUDENT (full-name nil) (age nil) (eye-color nil) (hair-color nil) (university nil) (major nil) (GPA nil) Обратите внимание на то, что каждый экземпляр содержит только слоты, относящиеся к его классу. Как показано в следующем подразделе, в любом классе можно переопределить любой слот, который был уже определён в любом из его суперклассов.

Класс, который либо прямо, либо косвенно наследует свойство другого класса, называется подклассом того класса, от которого он наследует свойства. Класс, от которого наследуются свойства, называется суперклассом наследующего класса. Классы PERSON, EMPLOYEE и STUDENT представляют собой подклассы класса USER. Классы EMPLOYEE и STUDENT являются подклассами класса PERSON.

Класс USER – суперкласс классов PERSON, EMPLOYEE и STUDENT, а класс PERSON – суперкласс классов EMPLOYEE и STUDENT. Иерархией классов с единичным наследованием называется такая иерархия, в которой каждый класс имеет только один суперкласс, связанный с ним прямыми отношениями наследования. Иерархией классов с множественным наследованием называется такая иерархия, в которой любой класс может иметь несколько суперклассов, связанных с ним прямыми отношениями наследования. В языке COOL поддерживается множественное наследование. Мы будем ограничиваться применением примеров единичного наследования. Ниже приведён пример класса, в котором используется множественное наследование (в нём рассматривается студент, который имеет работу) [4].

(defclass WORKING–STUDENT "Working Student defclass" (is-a STUDENT EMPLOYEE)) По умолчанию, если какой-то слот переопределяется в подклассе, то атрибуты слота из нового определения используются исключительно в экземплярах этого класса. Например, предположим, что определены следующие классы:

(defclass А (is-aUSER) (slot х (default 3)) (slot z (default 4))) (defclassВ (slot у (default 5)) (slot z (default 6))) В таком случае создание экземпляров классов А и В приведёт к получению следующих результатов:

CLIPS> (make-instance [a] of A) CLIPS> (make-instance [b] of В) CLIPS> (send [a] print) CLIPS> (send [b] print) [b] ofВ (х nil) (y 5) (z 6) Обратите внимание на то, что слоту х экземпляра b по умолчанию присвоено значение nil вместо 3. Это связано с тем, что при отсутствии заданного по умолчанию значения для слота х класса В полностью перекрывается заданное по умолчанию значение 3, присваиваемое слоту х в классе А. Чтобы обеспечить возможность наследовать атрибуты слота от суперклассов, можно воспользоваться атрибутом слота source.

Если этому атрибуту присваивается значение exclusive, которое применяется по умолчанию, то атрибуты для слота устанавливаются на основе наиболее конкретного класса, определяющего этот слот. В иерархии единичного наследования как таковой рассматривается класс, имеющий наименьшее количество суперклассов. Если же атрибуту source присваивается значение composite, то атрибуты, которые не определены явно в наиболее конкретном классе, определяющем слот, берутся из следующего по порядку наиболее конкретного класса, в котором определяется данный атрибут. Например, если описанные ранее конструкции defclass с именами А и В будут объявлены следующим образом:

(defclassА (is-a USER) (slot х (default 3)) (slot z (default 4))) (defclass В (is-a A) (slot x (source composite)) (slot у (default 5)) (slot z (default 6))) то после создания экземпляров классов А и В будут получены такие результаты:

CLIPS> (make-instance [a] of A) CLIPS> (make-instance [b] of В) CLIPS> (send [a] print) CLIPS> (send [b] print) Теперь, после того как слот х класса В объявлен с атрибутом source, которому присвоено значение composite, этот слот может наследовать заданный по умолчанию атрибут от класса А, и применяемое по умолчанию результирующее значение для слота х экземпляра b становится равным 3.

Возможно также запретить наследование значения слота с использованием атрибута слота propagation. Если этому атрибуту присваивается значение inherit, которое является заданным по умолчанию, то данный слот наследуется подклассами. А если этому атрибуту присваивается значение no-inherit, то слот подклассами не наследуется.

Например, если классы А и В будет определены следующим образом:

(slot х (propagation no-inherit)) то после создания экземпляров классов А и В будут получены такие результаты:

CLIPS> (make-instance [a] of A) CLIPS> (make-instance [b] of В) CLIPS> (send [a] print) CLIPS> (send [b] print) Экземпляр b класса В наследует слот у из класса А, но не наследует слот х из класса А, поскольку атрибут propagation последнего имеет значение no-inherit.

Абстрактные и конкретные классы. В языке CLIPS предусмотрена возможность определять классы [4 – 8], используемые только для наследования. Такие классы называются абстрактными классами. Создание экземпляров абстрактных классов невозможно. По умолчанию классы являются конкретными. Для указания на то, должен ли класс быть абстрактным (abstract) или конкретным (concrete), применяется атрибут класса role. Атрибут класса role должен быть указан после атрибута класса is-a, но перед любыми определениями слотов, например, как показано ниже [4].

(defclass ANIMAL

(role abstract))

(defclass MAMMAL

(role abstract))

(defclass CAT (defclass DOG Классы ANIMAL и MAMMAL являются абстрактными, а классы CAT и DOG – конкретными. Атрибут role наследуется, поэтому, хотя и не требуется объявлять класс MAMMAL как абстрактный, поскольку он наследует этот атрибут от класса ANIMAL, необходимо объявить классы CAT и DOG как конкретные, в связи с тем, что в противном случае они будут рассматриваться как абстрактные. Попытка создать экземпляр абстрактного класса приводит к формированию сообщения об ошибке, как в следующем примере:

CLIPS> (make-instance [animal-1] of ANIMAL) [INSMNGR3] Cannot create instances of

Abstract

class ANIMAL.

CLIPS> (make-instance [cat-1] of CAT) [cat-1] Настоятельная необходимость объявлять какой-либо класс как абстрактный не возникает, но при использовании такого подхода в соответствующих условиях код становится более удобным для сопровождения и проще обеспечивает повторное использование. При этом достаточно лишь исключить для пользователя возможность создавать экземпляры с помощью какого-то класса, если класс не предназначен для этой цели. Но если данный класс уже используется таким образом, то в будущих реализациях станет невозможным его исключение, поскольку это приведёт к нарушению работы существующего кода.

В рассматриваемом примере [4] ответ на вопрос о том, должны ли классы ANIMAL и MAMMAL быть абстрактными, не так уж однозначен. Если требуется создать картотеку с информацией о животных, содержащихся в некотором зоопарке, то данные классы, по-видимому, должны быть абстрактными, поскольку в природе не существует животных (в данном случае речь идёт о млекопитающих), которые соответствовали бы только этому определению и не относились бы к какому-то более конкретному виду живых существ. Но если бы предпринималась попытка идентификации какого-то животного, то вполне могла бы возникнуть необходимость создавать экземпляры класса ANIMAL или MAMMAL, например, для включения в них информации о том, что мы смогли выяснить в отношении данного животного.

(defclass A (is-a USER)) Класс А является прямым наследником класса USER. Список старшинства классов для A: A USER OBJECT.

Пример 2:

(defclass В (is-a USER)) Класс В является прямым наследником класса USER. Список старшинства классов для В: В USER OBJECT.

Пример 3:

(defclass С (is-a А В)) Класс С является прямым наследником классов А и В. Список старшинства классов для С: С А В USER OBJECT.

Пример 4:

(defclass D (is-a В A)) Класс D является прямым наследником классов А и В. Список старшинства классов для D: D В A USER OBJECT.

Пример 5:

(defclass Е (is-a А С)) В соответствии с правилом 2, А должен быть старше С. В нашем случае, С – это потомок А и является более старшим в соответствии с правилом 1. Ошибка.

Пример 6:

defclass Е (is-a С А)) Правильное определение класса из примера 5. Список старшинства для Е: Е С А В USER OBJECT.

Абстрактные и конкретные классы. Абстрактный класс предназначен только для наследования, на его основе не могут создаваться экземпляры. На основе конкретного класса могут создаваться его экземпляры [4 – 8].

Слоты. Слот – это место для хранения значений поля класса. Каждый экземпляр класса содержит копию всех слотов своего родителя.

Количество слотов класса ограничено только размером свободной памяти, имя слота – любой набор символов, за исключением зарезервированных слов. Потомок класса содержит слоты родителя. В случае конфликта имён слотов, он разрешается в соответствии с правилом старшинства.

(defclass A (is-a USER) (slot fooA) (slot barA)) (defclass В (is-a A) (slot fooB) (slot barB)) Список старшинства для A: A USER OBJECT. Экземпляр класса А будет иметь 2 слота: fooA и barA. Список старшинства для В: В A USER OBJECT. Экземпляр класса В будет иметь 4 слота: fooB, barB, fooA, barA.

Для каждого слота может быть определён набор фасетов. Фасеты описывают различные свойства слотов: значения по умолчанию, вид хранения, видимость и т.п. Более подробно фасеты будут рассмотрены далее.

Создание экземпляра класса производится командой (makeinstance a of А) – создаётся экземпляр с именем класса А. Другой вариант (создание массива экземпляра классов):

(definstances my_inst Тип поля слота. Слот может содержать как одно, так и несколько значений. По умолчанию слот содержит только одно значение. Ключевое слово multislot устанавливает тип слота, позволяющий хранить несколько значений, а slot или singleslot устанавливает тип слота, который может содержать только одно значение. Многозначные слоты хранятся как значения с несколькими полями. Манипуляции с ними производятся посредством стандартных функций nth$ и length$. Для установки значения слота используется функция slotinsert$. Слоты с одним значением хранятся в CLIPS как обычные переменные стандартных типов.

CLIPS> (сlеаr) (defclass А (is-а USER) (rоlесоnсrеte) (multislot foo (сrеаtе-ассеssоr read) (default abc def ghi))) CLIPS> (make-instance а of А) CLIPS> (nth$ 2 (send [a] get-foo)) Если при создании слота указывается модификатор для создания методов для записи или чтения по умолчанию ((create-accessor readwrite)), то экземпляр класса будет реагировать на сообщения getимя_слота и put-имя_слота соответственно чтением и записью значения слота. Создание обработчиков сообщений будет рассмотрено далее.

Фасет для задания значений по умолчанию. Фасеты используются для задания значений слота по умолчанию при создании экземпляра класса. Фасет default используется для задания статических значений слота. Фасет default-dynamic используется для заданий значения слота, которое задаётся всякий раз при создании нового экземпляра класса.

Пример:

CLIPS> (сlеаr) CLIPS> (setgen 1) (defclass A (is-a USER) (rоlе concrete) (slot foo (default-dynamic (gensym)) (create-accessor read))) CLIPS> (make-instance al of А) CLIPS> (make-instance a2 of А) CLIPS> (send [а1] get-foo) CLIPS> (send [a2] get-foo) Фасет Storage. Фасет определяет, будет ли значение слота храниться локально в экземпляре класса (lосаl), либо это значение будет одно для всех экземпляров класса (shared).

Пример:

CLIPS> (clear) (defclass A (is-a USER) (role concrete) (slot foo (create-accessor write) (storage shared) (default 1)) (slot bar (create-accessor write) (storage shared) (default-dynamic 2)) (slot woz (create-accessor write) (storage local))) CLIPS> (make-instance a of A) CLIPS> (send [a] print) (woz ni1) CLIPS> (send [a] put-foo 56) СLIPS> (send [a] put-bar 104) CLIPS> (make-instance b of A) CLIPS> (send [b] print) CLIPS> (send [b] put-foo 34) CLIPS> (send [b] put-woz 68) CLIPS> (send [a] print) CLIPS> (send [b] print) Фасет типа доступа к слоту. Для слота может быть задано три типа фасетов[4 – 6]: read-write, read-only, initialize-only Пример работы с разными типами фасетов:

CLIPS> (clear) (defclass A (is-a USER) (role concrete) (slot foo (create-accessor write) (access read-write)) (slot bar (access read-only) (default abc)) (slot woz (create-accessor write) (access initialize-only))) (defmessage-handler A put-bar (?value) (dynamic-put (sym-cat bar) ?value)) CLIPS> (make-instance a of A (bar 34)) [MSGFUN3] bar slot in [a] of A: write access denied.

[PRCCODE4] Execution halted during the actions of message-handler put-bar primary in class A CLIPS> (make-instance a of A (foo 34) (woz 65)) CLIPS> (send [a] put-bar 1) [MSGFUN3] bar slot in [a] of A: write access denied.

[PRCCODE4] Execution halted during the actions of message-handler put-bar primary in class A CLIPS> (send [a] put-woz 1) [MSGFUN3] woz slot in [a] of A: write access denied.

[PRCCODE4] Execution halted during the actions of message-handler put-bar primary in class A CLIPS> (send [a] print) Изменение значений свойств объектов по правилам объектноориентированного программирования производится самими объектами, поэтому в языке CLIPS это реализовано посредством обработчиков сообщений [4 – 8].

Общий синтаксис команды создания обработчика сообщений:

(defmessage-handler Вызов обработчика сообщений экземпляра класса:

(send [имя_экземпляра] имя_метода параметры) Обработчик сообщений уникально идентифицируется наименованием класса и типом. Для класса обработчик сообщений может задаваться как при создании определения класса, так и после. Заметим, что при создании определения класса создаётся только заголовок обработчика сообщений. Собственно программный код обработчика создаётся позже при помощи команды defmessage-handler.

Обработчики сообщений, определяемые системой. За классами можно закрепить не только данные, но и процедурную информацию.

Процедуры, входящие в состав классов, называются обработчиками сообщений. Для каждого класса, кроме обработчиков сообщений, определяемых пользователем, автоматически создаётся также целый ряд обработчиков сообщений, определяемых системой. Эти обработчики сообщений можно вызывать для работы с некоторым экземпляром с помощью команды send. Команда send имеет следующий синтаксис [4 – 8]:

Например, сообщение print отображает информацию о слотах экземпляра:

CLIPS> (send [John] print) [John] of PERSON (full-name "John Q. Public") (eye-color blue) (hair-color black) Для каждого слота, определяемого в конструкции defclass, система CLIPS автоматически определяет обработчики сообщений слота с префиксами get- и put-, которые используются для выборки и задания значений слота. Действительные имена обработчиков сообщений формируются в результате добавления к этим префиксам имени слота. Поэтому, например, конструкция defclass с именем PERSON, имеющая слоты full-name, age, eye-color и hair-color, автоматически создаётся для данного класса с восемью обработчиками сообщений, имеющими имена get-full-name, put-full-name, get-age, put-age, get-eye-color, puteye-color, get-hair-color и put-hair-color. Обработчики сообщений get- не имеют параметров и возвращают значение слота, например [4]:

CLIPS> (send [John] get-full-name) "John Q. Public" CLIPS> (send [John] get-age) Обработчики сообщений put- принимают от нуля и больше параметров. Если параметры не задаются, то восстанавливается первоначальное, предусмотренное по умолчанию значение слота, а при передаче одного или большего количества параметров значение слота устанавливается с учётом этих параметров. Попытка поместить больше одного значения в однозначный слот приводит к возникновению ошибки. Обработчик сообщений put- возвращает значение, представляющее собой новое значение слота, например, как показано в следующем диалоге:

CLIPS> (send [Jack] get-age) CLIPS> (send [Jack] put-age 22) CLIPS> (send [Jack] get-age) CLIPS>(send [Jack] put-age) CLIPS> (send [Jack] get-age) Команда watch принимает в качестве параметров несколько элементов, подлежащих отслеживанию, которые относятся к данному экземпляру. Одним из таких элементов является slots (слоты). Если осуществляется отслеживание слотов, то при каждом изменении значения любого слота экземпляра выводится информационное сообщение. Отслеживание изменений в слотах можно отменить с помощью команды unwatch:

CLIPS > (watch slots) CLIPS> (send [Jack] put-age 24) ::= local slot age in instance Jack (unwatch slots) CLIPS> (send [Jack] put-age 22) Ещё одним заранее определённым обработчиком сообщений является delete. Как и можно было бы предположить, обработчик сообщений delete используется для удаления экземпляра. Он возвращает символ TRUE, если экземпляр был успешно удалён, в противном случае – символ FALSE:

CLIPS> (instances) [John] of PERSON [genl] of PERSON [Jack] of PERSON For a total of 3 instances.

CLIPS> (send [genl] delete) CLIPS> (instances) [John] of PERSON [Jack] of PERSON For a total of 2 instances.

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

CLIPS> (watch instances) CLIPS> (make-instance Jill of PERSON) ==>instance [Jill] of PERSON [Jill] CLIPS> (send [Jill] put-age 22) CLIPS> (send [Jill] delete) (unwatchinstances) Последовательность знаков свидетельствует о том, что экземпляр создаётся.

;;создаём класс «прямоугольник» и объявляем у него обработчик сообщений, позволяющий находить его площадь:

(defclass rectangle (is-a USER) (slot side-a (default 1)) (slot side-b (default 1)) (message-handler find-area)) ;;создаём тело обработчика сообщений:

(defmessage-handler rectangle find-area () (* ?self:side-a ?self:side-b)) ;;создаём ещё один обработчик сообщений, позволяющий напечатать полученную площадь прямоугольника:

(defmessage-handler rectangle print-area() (printout t (send ?self find-area) crlf)) Ссылка на активный (т.е. принимающий сообщение в данный момент) экземпляр сущности может быть получена при помощи переменной ?self. Имя этого параметра зарезервировано.

Пример:

(defclass A (is-a USER) (role concrete) (slot foo (default 1)) (slot bar (default 2))) (defmessage-handler A print-all-slots () (printout t ?self:foo “ “?self:bar crlf)) CLIPS> (make-instance a of A) CLIPS> (send [a] print-all-slots) Опишите основные элементы языка CLIPS.

Расскажите об основных типах данных языка.

Расскажите про конструкторы, используемые в языке CLIPS.

Абстракции данных.

Упорядоченные факты.

Неупорядоченные факты.

Функции для работы с фактами.

Поясните процесс инициализация фактов.

9. Расскажите о процессе использования локальных и глобальных переменных.

10. Создание правил. Конструктор defrule.

11. Поясните основной цикл выполнения правил.

12. Условные логические элементы.

13. Команды и функции для работы с правилами.

14. Функции, конструктор deffunction.

15. Конструктор defclass.

16. Расскажите об особенностях абстрактных и конкретных классов.

17. Расскажите об особенностях активных и неактивных классов.

18. Слоты класса.

19. Конструктор обработчика сообщений.

20. Работа с объектами.

21. Поясните процесс инициализации объектов.

22. Расскажите о функциях для работы с объектами.

23. Преобразуйте сеть общего вида, на которой представлены авиалинии, в ряд фактов, заданных в операторе deffacts. Для описания фактов используйте единственную конструкцию deftemplate.

24. Преобразуйте семантическую сеть, представляющую семью, в ряд фактов, заданных в операторе deffacts. Для описания сформированных фактов используйте несколько конструкций deftemplate.

25. Преобразуйте семантическую сеть классификации летательных аппаратов в ряд фактов, заданных в операторе deffacts. Для описания фактов используйте несколько конструкций deftemplate.

26. Преобразуйте бинарное дерево решений, представляющее информацию о классификации животных в ряд фактов, заданных в операторе deffacts.