Икусственный интеллект и нечеткие системы
скачатьИКУССТВЕННЫЙ ИНТЕЛЛЕКТ И НЕЧЕТКИЕ СИСТЕМЫУДК 321.3 В.В. Курейчик, П.В. Сороколетов, В.В. Бова, В.В. Голенков, Н.А. Гулякина ПАРАЛЛЕЛЬНЫЕ КОМБИНИРОВАННЫЕ АРХИТЕКТУРЫ ИНТЕЛЛЕКТУАЛЬНОГО ПОИСКА1 Работа посвящена рассмотрению новых подходов решения неструктурированных проблем поиска при построении интеллектуальных искусственных систем. Описаны комбинированные архитектуры и схемы распараллеливания квантового поиска. Предложены модифицированные принципы для управления и реализации процесса совместного поиска. Эволюционные распределенные алгоритмы; квантовый поиск; параллельная обработка информации. V.V. Kureichik, V.V. Bova, P.V. Sorokoletov, V.V. Golenkov, N.A. Gulyakina ^ This article is devoted to consideration of new approaches to solving unstructured search problems in the construction of intelligent artificial systems. Describes the combination of architecture and parallel quantum search scheme. The modified guidelines for the management and implementation of a joint search. Evolutionary distributed algorithms; quantum search; parallel processing of information. Введение В основе интеллектуальных систем поддержки принятия решений лежит понятие искусственного интеллекта (ИИ). Проблемы ИИ тесно связаны с организацией знаний об окружающем мире в виде математических структур, например, множеств, графов, алгоритмов, которые отражают реальные связи и отношения между любыми объектами в природе (в частности в предметной области). Под интеллектуальной искусственной системой (ИИС) понимают организационно-техническую систему, состоящую из интеллектуального комплекса средств поддержки принятия решений взаимосвязанного и взаимодействующего с пользователями и сетями ЭВМ, и выполняющую решения заданных задач. При решении задач искусственного интеллекта важнейшим является обнаружение в «сырых» данных ранее неизвестных, нетривиальных, нечетких, практически полезных и доступных интерпретаций знаний [1,2]. Данное направление известно как Data Mining (DM). Классы систем DM входят в мультидисциплинарную область. К основным методам и алгоритмам, использующимся в DM, относят: нейронные сети, квантовые и генетические алгоритмы, эволюционное программирование и др. [2,3]. Использование идей квантовой механики позволяет при поиске данных использовать подходы параллельных вычислений, что особенно важно при построении интеллектуальных искусственных систем. Согласно известному принципу суперпозиции система может, как бы одновременно находиться во всех возможных состояниях. Производя над одним состоянием системы произвольные действия, мы производим это одновременно над заданным множеством состояний [4]. При поиске и обнаружении данных предлагается новая технология на основе квантового поиска. Описаны новые архитектуры и принципы такого поиска. Это позволяет расширить область поиска данных без увеличения времени работы и сократить преждевременную сходимость алгоритмов, повысить эффективность и качество получаемых решений. ^ В последнее время появились новые подходы решения NP-полных проблем и неструктурированных проблем поиска при построении интеллектуальных искусственных систем [4-11]. Квантовый поиск анализирует неструктурированные проблемы, которым в общем виде формулируются следующим образом [4,5]. Задана функция f(x), аргументы x – целые числа x = 1,2,….,N, причем f(x) принимает значение ноль во всех случаях, кроме x=w. Необходимо найти значение w, используя наименьшее число запросов к f(x). Задачи такого типа при «небольшом» x<100 решаются на основе полного перебора (исчерпывающего поиска) или методом проб и ошибок. Неструктурированный поиск неформально заключается в следующем. Задана «большая» база данных (x>100000) нечетких ситуаций принятия решений. Тогда при отсутствии ключей поиска потребуется O[(x/2)!] запросов для нахождения искомого решения f(x). Идею и структуру квантового алгоритма предложил Л. Гровер [4,5]. Согласно [5] при решении неструктурированной проблемы поиска существует “оракул”, определяющий является ли рассматриваемое решение искомым. Л. Гровер рассматривает N целых чисел индекса x = 1,2,…, N как набор ортогональных векторов  в N – размерном пространстве Гильберта. Этот шаг алгоритма на языке вычислений ставит в соответствие каждому возможному индексу уникальный собственный вектор. Первоначально задается пространство поиска, , т.е. модель квантового регистра памяти, содержащего определенное количество суперпозиций, равное количеству всех N [4,5].Для реализации поиска это квантовое пространство преобразуется в общую суперпозицию, которая концентрируется в  векторе, определяющем путь до цели поиска. Предлагается процедура квантового кругооборота U. Другими словами, если имеется отличное от нуля совпадение между стартовым пространством  и целевым , то есть |U| 0, тогда можно использовать унитарную процедуру U для выполнения классического поиска цели. Л. Гровер предлагает использовать U и f(x), чтобы построить увеличивающий амплитуду оператор Q. Он изменяет амплитуду вероятности от «не – цели» векторов в цель =. Поведение «оракула» в алгоритме квантового поиска моделируется возвратной функцией f(x)=0, для всех x,w и f(x)=1, для x=w.Для решения NP–полных проблем принятия решений при поиске неструктурированных знаний предлагается анализировать базу знаний (БЗ), чтобы «выращивать» полные решения, рекурсивно расширяя последовательные частичные решения. Приведем модифицированный алгоритм квантового поиска [8,9].
Приведем укрупненный псевдокод алгоритма квантового поиска оптимальных решений. Алгоритм begin {основная программа} generation:=0 {установка} initialize; repeat {основной цикл} gen:=gen+1 generation; cycle; return; statistics (max, avg, min, sumfitness, newsоl) report (gen) oldsol:=newsol until (gen maxgen) end {конец основной программы}. Здесь generation (gen) – генерации (итерации) алгоритма; max, avg, min, sumfitness – максимальное, среднее, минимальное, суммарное значение целевой функции; oldsol, newsol – старое и новое решение соответственно. Алгоритм квантового поиска (1 итерация выполняется в блоке repeat). Работа алгоритма начинается с чтения данных, инициализации случайных решений, вычисления статистических данных и их печати. Процедура report представляет полный отчет обо всех параметрах алгоритма. На основе анализа данных из процедуры report строится график зависимости значений целевой функции от числа генераций. Если функция имеет несколько локальных оптимумов, и мы попали в один из них, то увеличение числа генераций может не привести к улучшению значений целевой функции. В этом случае наступила предварительная сходимость алгоритма. Операция return предусматривает пошаговый возврат до выхода из тупика. Алгоритмы квантового поиска весьма чувствительны к изменениям и перестановкам входных параметров исходной модели. Это говорит о том, что, например, для одного вида модели объекта, представленного матрицей можно получить решение с одним локальным оптимумом. А для этой же матрицы с переставленными строками и столбцами можно получить другое решение с лучшим локальным оптимумом. Следует отметить, что, изменяя параметры, алгоритмы и схему квантового поиска, в некоторых случаях, можно выходить из локальных оптимумов. Эта проблема продолжает оставаться одной из важнейших при построении ИИС. 2. Архитектуры поиска Для повышения скорости нахождения оптимальных решений предлагаются схемы распараллеливания квантового поиска на основе тетраэдра (рис. 1) и октаэдра (рис. 2), как основных моделей стандартных блоков построения ИИС [11]. Введение экспертной подсистемы позволит определить назначение каждого блока квантового алгоритма. Например, КА1 – определяет целевую функцию, КА2 – операцию суперпозиции и т.п.  Рис. 1. Схема распараллеливания квантового поиска на основе тетраэдра  Рис. 2. Схема распараллеливания квантового поиска на основе октаэдра Опишем теперь идею различных комбинированных алгоритмов для построения ИИС. Предлагается комплексный подход, основанный на взаимодействии генетических и квантовых алгоритмов (рис. 3).  ^ Очевидно, что данные схемы можно взять как строительные блоки и наращивать иерархически. При этом возможно построить схему последовательного или параллельного совместного поиска любой сложности. На рис. 4 (а, б) показаны схемы взаимодействия совместного поиска квантовых, генетических и алгоритмов случайного поиска.   а б Рис. 4. Схемы совместного поиска: а – квантовых, генетических алгоритмов; б – алгоритмов случайного поиска Отметим также, что квантовый поиск может ускорить классический случайный алгоритм, создавая суперпозиции частичных решений, увеличивая пространство поиска искомого решения. Данные блоки могут быть раскрыты и другим способом в зависимости от начальных условий и знаний о решаемой задаче. Для повышения скорости работы комбинированных алгоритмов предлагается параллельная обработка информации. Параллельной называется такая обработка на ЭВМ, которая предусматривает одновременное выполнение программ и/или их отдельных частей на независимых устройствах. Согласно закону Грота производительность одного процессора увеличивается пропорционально квадрату его стоимости. Существует гипотеза, что в параллельной системе с n процессорами, производительность каждого из которых равна единице, общая производительность растет как log2n [12]. Одним из возможных путей ускорения вычислений за счет параллельного выполнения композитных алгоритмов является представление их структуры в виде совокупности слабо связанных потоков команд. Тогда алгоритм может быть сегментирован как набор процессов, каждый из которых может выполняться на отдельном процессоре и (при необходимости) осуществлять взаимодействие с другими процессорами. Такая архитектура (рис. 5а,б) поиска аналогична архитектурам ЭВМ с множественным потоком команд и множественным потоком данных [12]. Например, на рис. 5а показана архитектура поиска с общей памятью, а на рис. 5б с локальной памятью для каждого композитного алгоритма. Отметим, что здесь могут быть использованы различные алгоритмы, реализующие любую модель эволюции [3].   а б Рис. 5. Архитектура ГП: а – с общей памятью; б – с локальной памятью В рассматриваемых архитектурах (рис. 5а,б) в блоке памяти реализуется оператор миграции, в который каждый раз отправляется лучший представитель из популяции. Связь между ГА осуществляется через коммутационную сеть. Отметим, что можно организовать различное количество связей между ГА по принципу полного графа, по принципу звезды и т.д. Такая схема в случае наличия большого количества вычислительных ресурсов может быть доведена до N блоков, где N - размер популяции альтернативных решений задачи компоновки. Причем N–1 блоков могут параллельно осуществлять эволюционную адаптацию и через коммутационную сеть обмениваться лучшими представителями решений. Для повышения эффективности поиска предлагается использовать параллельные методы и архитектуры, основанные на бионическом поиске [3,13]. Это позволит сократить количество компьютерных ресурсов, время поиска и позволит получать оптимальные и квазиоптимальные результаты. На рис.6 приведем схему каскадной реализации схемы бионического поиска. Здесь ГА – генетический, МА – муравьиный, КА – квантовый, ЭА – эволюционный, МО – моделирования отжига алгоритмы. Они реализуются каждый на своем процессоре. Коммутаторы Ki (i I =1,2,…,n) обеспечивают полнодоступную коммутацию между процессорами i-го и (i+1)-го каскадов. Имеется также возможность прямой передачи результатов поиска с коммутатора Ki на входы коммутатора Ki + 1 следующего каскада. Известно [208], что аппаратные затраты для создания H каскадов коммутаторов равны: , где – число процессоров на i–м каскаде. Следовательно, это будет в H раз меньше, чем для коммутаторов со связью по принципу полного графа. Для ускорения поиска можно использовать блочную идею организации макропроцессоров (рис. 7). Отметим, что такой поиск обеспечивает более гибкую коммутацию между процессорными элементами. Коммутатор здесь разбивается на 2 уровня: локальный коммутатор макропроцессора и системный коммутатор (СК) верхнего уровня. В этой связи затраты на реализацию поиска будут уменьшаться [13]. Заметим, что такой макроконвейер можно строить не только на уровне алгоритмов, но и на уровне крупных операций, использую принцип “матрешки” (рис. 8).  Рис. 6. Схема каскадной реализации бионического поиска  Рис. 7. Схема поиска на основе макропроцессора (МП1)  Рис. 8. Схемы поиска на основе мультимакроконвейера Для управления и реализации процессом совместного поиска авторы предлагают ввести следующие модифицированные принципы [14].
Заключение Отметим, что такие архитектуры поиска позволяют описать механизм взаимодействия системы с внешней средой. Предложенные стратегии позволяют быстрее находить локально-оптимальные результаты. Это связано с параллельной обработкой множества альтернативных решений. Причем на основе такой архитектуры, возможно, концентрировать поиск на получение более перспективных решений. ^
Курейчик Владимир Викторович Технологический институт федерального государственного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге. E-mail: vkur@tsure.ru 347928, г. Таганрог, Некрасовский, 44. Тел.:8(8634) 38-34-51. Кафедра систем автоматизированного проектирования. Заведующий кафедрой, д.т.н., профессор. Сороколетов Павел Валерьевич ЗАО «СЕДИКОМ», г. Москва. E-mail: SorokoletovPV@gidroogk.ru Тел.:8(8495) 787-5358. Начальник отдела. ^ Технологический институт федерального государственного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге. E-mail: vvbova@yandex.ru 347928, г. Таганрог, Некрасовский, 44. Тел.:8(8634) 37-16-51. Кафедра систем автоматизированного проектирования, старший преподаватель. Голенков Владимир Васильевич Учреждение образования "Белорусский государственный университет информатики и радиоэлектроники". 220013, Республика Беларусь, г. Минск, ул. П.Бровки 6. Тел.: 8(+375) 296 06 22 59. Кафедра интеллектуальных информационных технологий, зав. кафедрой, д.т.н., профессор. Гулякина Наталья Анатольевна Учреждение образования "Белорусский государственный университет информатики и радиоэлектроники" 220013, Республика Беларусь, г. Минск, ул. П. Бровки, 6. Тел.: 8(+375) 296 06 22 59. Кафедра интеллектуальных информационных технологий, зам. зав. кафедрой, к.физ-мат.н., профессор. Kureichik Vladimir Viktorovich Taganrog Institute of Technology – Federal State-Owned Educational Establishment of Higher Vocational Education “Southern Federal University”. E-mail: vkur@tsure.ru 44, Nekrasovskiy, Taganrog, 347928, Russia. Phone: 8(8634) 38-34-51. The Department of Computer Aided Design. Head the Department of Computer Aided Design, professor. Sorokoletov Pavel Valerievich CAS «SEDIKOM», Moscow, Russia. E-mail: SorokoletovPV@gidroogk.ru Phone: 8(8495) 787-5358. Chief of department. Bova Viktoria Viktorovna Taganrog Institute of Technology – Federal State – Owned Educational Establishment of Higher Vocational Education “Southern Federal University”. E-mail: vvbova@yandex.ru 44, Nekrasovskiy, Taganrog, 347928, Russia. Phone: 8(8634) 37-16-51. The Department of Computer Aided Design, senior teacher. 1 Работа выполнена при поддержке РФФИ (грант № 10-01-90017)
|
Ваша оценка этого документа будет первой.
Ваша оценка: 