Евгений Анатольевич Титенко¹, Татьяна Ивановна Лапина², Олег Гурьевич Добросердов³,

Алексей Николаевич Щитов4, Евгений Владимирович Талдыкин5

1− 5 Юго-Западный государственный университет (г. Курск, Россия) 1   2      3

 johntit@mail.ru,  lapinati@mail.ru,  serfingk@yandex.ru

Постановка проблемы. Работа посвящена рассмотрению важного подкласса систем искусственного интеллекта – продукционных систем. Прежде всего, продукционный аппарат применим в динамических экспертных системах (ЭС), таких как ECLIPSE. Они преимущественно работают с частично определенными данными. В работе рассматриваются образцы (шаблоны) как дискретные структуры. Эти структуры содержат константные и переменные фрагменты, что определяет многозначность их описания и неопределенность поиска. Показано, что наиболее критичной является операция поиска по образцу. Выполнен сравнительный анализ известных алгоритмов поиска по образцу для продукционных систем. Известные алгоритмы поиска по образцу (шаблону) не соответствуют таким показателям как аппаратная ориентация, адаптация. Метод исследования основан на применении генетических алгоритмов (ГА) для операции поиска по образцу. Операция поиска по заданному шаблону и операция скрещивания хромосом имеют одинаковое содержание. Исследование основано на выявлении совпадающего описания моделей. Базовая операция ГА (скрещивание) позволяет описать процессы поиска образца и дальнейшей модификации строки. Для этого выбран двухточечный формат скрещивания. В этом случае хромосома, понимаемая как строка, разбивается на три фрагмента. Они соответствуют в символьной обработке делению строк на префикс, тело и суффикс. Новизна применения ГА для задачи поиска по образцу состоит в изменении трактовки позиций (адресов) вхождений. В продукционных системах эти позиции вычисляются алгоритмом поиска по образцу и заранее неизвестны. В ГА они понимаются как входные данные, которые можно произвольно задавать или выбирать. Этот принципиальный момент определяет хранение и обработку ранее вычисленных позиций. Такой подход обосновывает функциональная общность операций поиска по образцу и скрещивания. Эта общность позволяет на итерациях работы продукционной системы использовать сохраненные позиции образца без затрат времени на поиск.

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

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

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

1. Wichert A. Artificial intelligence and a universal quantum computer // AI Communications. 2016. V. 29. № 4. P. 537−543.
2. Waterman D.A. A Guide to Expert Systems. Reading, MA: Addison–Wesley. 1996. 167 p.
3. Wang J.-J., Qiao Y., Xiong J.-Q., Wang H.-A. Method for Graph-based Real-time Rule Scheduling in Multi-core Environment // Journal of Software. V. 30. № 2. P. 481−494.
4. Wahid F., Ismail L.H., Ghazali R., Aamir M. An efficient artificial intelligence hybrid approach for energy management in intelligent buildings // KSII Transactions on Internet and Information Systems. 2019. V. 13. № 12. P. 5904−5927.
5. Briola D., Mascardi V., Martelli M., Arecco G., Caccia R. A prolog-based MAS for railway signalling monitoring: Implementation and experiments // 9th Workshop «From Objects to Agents». WOA 2008 Evolution of Agent Development: Methodologies, Tools, Platforms and Languages. 2008. P. 11−18.
6. Люгер Дж.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем. М.: «Вильямс». 2003. 864 с.
7. Титенко Е.А., Крипачев А.В., Марухленко А.Л. Коммутационная схема параллельных парных перестановок для специализированного продукционного устройства // Известия ЮФУ. Сер. «Технические науки». 2018. № 8(203). С. 29−38.
8. Титенко Е.А., Емельянов С.Г., Курочкин А.Г. Анализ алгоритмов поиска по образцу для управления группой роботов // Наукоемкие технологии. 2014. Т. 15. № 12. С. 4−8.
9. Wu S., Manber U. Fast text searching allowing errors // Communications of the ACM. 1992. V. 35. № 10. P. 83−91.
10. Биоинспирированные методы оптимизации. М.: Физматлит. 2009. 384 с.
11. Wahid F., Ismail L.H., Ghazali R., Aamir M. An efficient artificial intelligence hybrid approach for energy management in intelligent buildings // KSII Transactions on Internet and Information Systems. 2019. V. 13. № 12. P. 5904−5927.
12. Xiong Y., Ling Q.-H., Han F., Liu Q.-H. An efficient gene selection method for microarray data based on LASSO and BPSO // BMC Bioinformatics. 2019. V. 20. P. 212003.
13. Лысенко С.Н., Макаев В.А., Халин Ю.А Исследование результатов мета-поиска на основе генетического алгоритма // Естественные и технические науки. 2018. № 8(122). С. 171−173.
14. Титенко Е.А., Добросердов О.Г. Метод и модифицированный алгоритм направленного поиска вхождений // Информационно-измерительные и управляющие системы. 2009. Т. 7. № 11. С. 98−100.
15. Титенко Е.А., Зерин И.С. Исчислительная система продукций и процедура распознавания конфликтов данных // Вестник компьютерных и информационных технологий. 2012. № 6(96). С. 50−55.
16. Макконелл Дж. Основы современных алгоритмов. Изд. 2-е, доп. / Пер. с англ. под ред. С.К. Ландо. М.: Техносфера. 2004. 386 с.
17. Holland J.H. Adaptation in natural and artificial systems. An introductory analysis with application to biology, control, and artificial intelligence. London: Bradford book edition. 1994. 211 p.
18. Титенко Е.А., Атакищев O.И. Метод ассоциативной обработки строк и аппаратно-ориентированный алгоритм для его реализации // Известия Юго-Западного государственного университета. 2011. № 6(39). Ч. 2. С. 72−77.
19. Титенко Е.А., Петрик Е.А., Воронин Д.А., Атакищева И.В. Продукционная модель для параллельной обработки знаний // Информационно-измерительные и управляющие системы. 2011. Т. 9. № 11. С. 81−86.
20. Titenko E.A., Degtyarev S.V. Approximate search in the sample on the basis manber-wu method // Journal of Fundamental and Applied Sciences. 2017. V. 9. № 2. P. 914−918.