Икусственный интеллект и нечеткие системы



Скачать 334.93 Kb.
Дата13.02.2017
Размер334.93 Kb.
Просмотров271
Скачиваний0

ИКУССТВЕННЫЙ ИНТЕЛЛЕКТ И НЕЧЕТКИЕ СИСТЕМЫ


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

Эволюционные распределенные алгоритмы; квантовый поиск; параллельная обработка информации.


V.V. Kureichik, V.V. Bova, P.V. Sorokoletov, V.V. Golenkov, N.A. Gulyakina
PROBLEMS OF KNOWLEDGE PRESENTATION IN MANAGEMENT DECISION SUPPORT OF INTEGRATED SYSTEMS
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]. При поиске и обнаружении данных предлагается новая технология на основе квантового поиска. Описаны новые архитектуры и принципы такого поиска. Это позволяет расширить область поиска данных без увеличения времени работы и сократить преждевременную сходимость алгоритмов, повысить эффективность и качество получаемых решений.



1. Квантовые алгоритмы

В последнее время появились новые подходы решения 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].



  1. Начало.

  2. Ввод исходных данных.

  3. Проверка условий существования инвариантных частей в БЗ.

  4. Анализ математической модели БЗ и на ее основе построение дерева частичных решений.

  5. Суперпозиция частичных решений на основе жадной стратегии и квантового поиска.

  6. В случае наличия тупиковых решений возврат к шагу 4 и проведение параллельного поиска.

  7. Последовательный поиск в ветвях дерева решений с пошаговым возвращением.

  8. Если набор полных решений построен, то переход к 9, если нет, то к 4.

  9. Лексикографический перебор полных решений и выбор из него оптимального или квазиоптимального решения.

  10. Конец работы алгоритма.

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

Алгоритм


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).


Рис. 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].


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

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

  • Принцип соответствия. Язык описания исходной задачи должен соответствовать наличию имеющейся о ней информации.

  • Принцип разнообразия путей развития. Построение ИИС многовариантно и альтернативно. Основная задача – выбрать путь, приводящий к получению оптимального или квазиоптимального решения.

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

  • Принцип иерархичности. ИИС могут надстраиваться по горизонтали и вертикали (например, сверху вниз и снизу вверх).

  • Принцип «Бритвы Оккама». Нежелательно увеличивать сложность ИИС без необходимости.

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

Заключение

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


БИБЛИОГРАФИЧЕСКИЙ СПИСОК

  1. Люггер Д.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем / Пер. с англ. – М.: Издательский дом «Вильямс», 2003.

  2. Дюк В., Самойленко А. Data Mining: учебный курс. – СПб.: Питер, 2001. – 368 с.

  3. Курейчик В.В., Курейчик В.М., Гладков Л.А., Сороколетов П.В. Бионспирированные методы в оптимизации. – М.: Физмалит, 2009.

  4. Grover L.K. A Fast Quantum Mechanical Algorithm for Data-base Search. Proc. 28-th Ann. ACM Press, New York, 1996. – pp. 212-219.

  5. Grover L.K. Synthesis of Quantum Superpositions by Quantum Computation. Physical Rev. Letters. – 2000. Vol. 85, No. 6. – pp 1334-1337.

  6. Williams C.P. Quantum Search Algorithms in Sciences and Engineering. Computing in sciences and engineering, – March April 2001. – pp. 44-51.

  7. Валиев К.А., Конан А.А. Квантовые компьютеры: надежда и реальность. – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

  8. Курейчик В.М. Совместные методы квантового и бионического поиска // Труды конференций IEEE «AIS’04», «CAD-2004». – М.: Физматлит, 2004. – С. 12-19.

  9. Курейчик В.М., Неупокоева Н.В. Квантовые и генетические алгоритмы размещения компонентов ЭВА: Монография. – Таганрог: Изд-во ТТИ ЮФУ, 2010.

  10. Литвинцева Л.В., Ульянов С.В. Интеллектуальные системы управления I.Квантовые вычисления и алгоритм самоорганизации // Известия РАН. Теория и системы управления. – 2009. –№6. С 102 –141.

  11. Курейчик В.В., Сороколетов П.В. Новая технология квантового поиска // Известия высших учебных заведений // Электромеханика. – 2007. № 3. – С. 48-52.

  12. Комарцова Л.Г., Максимов А.В. Нейрокомпьютеры. – М.: Изд-во МГТУ, 2002.

  13. Каляев И.А. и др. Реконфигурацируемые мультиконвейерные вычислительные структуры / Под общ. ред. И.А. Каляева. – Ростов Н/Д: Изд-во ЮНЦ РАН, 2009.

  14. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. – М.: Эдиториал УРСС, 2002.


Курейчик Владимир Викторович

Технологический институт федерального государственного образовательного учреждения высшего профессионального образования «Южный федеральный университет» в г. Таганроге.

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)


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал