Автореферат (1150568), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

Полученыасимптотические оценки всех построенных алгоритмов.Теоретическая и практическая значимость работы. Полученныерезультаты исследования применимы при разработке систем распознаванияобразов, объекты исследования в которых характеризуются свойствами своихэлементов и отношениями между ними, вследствие чего они допускают5формализацию на языке исчисления предикатов. Разработанные алгоритмыотличаются легкостью практической реализации.Степень достоверности и апробация результатов. Результатыдиссертационной работы были представлены и обсуждались на научныхконференциях: СПИСОК-2012, Санкт-Петербург, Россия, 25-27 апреля 2012; XVМеждународная научная конференция «Informationtheoriesandapplications» (ITA2012), Варна, Болгария, 18 июня-6 июля 2012; СПИСОК-2013, Санкт-Петербург,Россия, 23-26 апреля 2013; XVI Международная научная конференция«Informationtheoriesandapplications» (ITA 2013), Варна, Болгария, 29 июня-11 июля2012, СПИСОК-2016, Санкт-Петербург, Россия, 26-29 апреля 2016.Основные результаты диссертации были получены в рамках выполненияисследований при финансовой поддержке РФФИ (проект 14-08-01276).Публикации результатов.

По теме диссертации опубликовано 7 работ, изних 3 статьи в научных журналах из перечня российских рецензируемыхжурналов, в которых должны быть опубликованы основные научные результатыдиссертаций на соискание учѐных степеней доктора и кандидата наук [1, 2, 3], 2статьи в зарубежных научных журналах на английском языке [4, 5] и тезисы 2докладов [6, 7]. В статьях [1, 2, 4 и 5] диссертанту принадлежит построениеалгоритмов решения задач логико-предметного распознавания образов,основанных на обратном методе Маслова и нахождение асимптотических оценокэтих алгоритмов. В статье [3] диссертантом предложено применение построенныхранее алгоритмов для решения задачи нахождения наибольшей общей сточностью до имѐн аргументов подформулы двух элементарных конъюнкцийатомарных формул.Личный вклад автора.

Результаты, представленные в диссертационнойработе, получены соискателем либо самостоятельно, либо при егонепосредственном участии.Положения, выносимые на защиту1. Построен алгоритм IMA поиска вывода формул, к доказательству которыхсводятся многие задачи Искусственного Интеллекта, основанный на тактикахобратного метода Маслова. Получены асимптотические оценки числа шаговработы этого алгоритма.2.

Построен алгоритм IAPTA поиска вывода формул, к доказательствукоторых сводятся многие задачи Искусственного Интеллекта, основанный натактиках обратного метода Маслова, а также тактиках муравьиных алгоритмов сиспользованием идей параллельных вычислений. Получены асимптотическиеоценки числа шагов работы этого алгоритма.3. Построен алгоритм PHIAPTA поиска наибольшей общей подформулы,основанный на алгоритме IAPTA. Получены асимптотические оценки числашагов работы этого алгоритма.Структура и объем диссертации. Работа состоит из введения, четырех глав,разбитых на разделы подразделы, заключения, списка литературы и6трехприложений. Общий объем рукописи составляет 157 страниц текста, включая88 страниц непосредственно текста диссертации и 69 страниц приложений. Текстсодержит 21 рисунок.

Библиографический список включает 105 наименований.Содержание работыВо введении обосновывается актуальность темы исследования,формулируется цель работы, дается обзор литературы по изучаемой проблеме,приводится краткое содержание работы по главам.В первой главе приведен обзор современного состояния предметной областипо рассматриваемой в диссертации теме. В разделе 1.1 рассматриваетсяпостановка задач Искусственного Интеллекта при логико-предметном подходе. Вразделе 1.2 приведена формулировка обратного метода С.Ю. Маслова длярешения задач логико-предметного распознавания образов. В разделах 1.3-1.6даны обзоры тем алгоритмов муравья, параллельных вычислений и неполнойвыводимости предикатных формул соответственно.Во второй главе сформулирован обратный метод Маслова для решениязадач логико-предметного распознавания образов, построен алгоритм IMAрешения таких задач на основе обратного метода, получены асимптотическиеоценки этого алгоритма.В разделе 2.1 сформулирован обратный метод для доказательствавыводимости формул вида x1 ,..., xn   & Di a1 ,..., ak , x1 ,..., xn i 1(1)Эта формула является частным случаем формул, для которых разработанобратный метод Маслова.

В (1) дизъюнкты Di a1 ,..., ak , x1 ,..., xn  имеют видDi   S a1 ,..., ak  Pk x1 ,..., xn1,где S a1 ,..., a k–обозначениедлядизъюнкции отрицаний атомарных формул, входящих в S a1 ,..., ak  .Определение 1. Любой список Г формул вида Di a1 ,..., a k , с1 ,..., сn являетсяF-набором для формул вида (1), если формулы в этом списке неповторяются.Определение 2. Пусть  1 ,..., l – список констант из списка a1 ,..., a k . 1 ,...,  l – список переменных и констант из списка a1 ,..., a k . Рассмотримсистему равенств:1  1  l   l7(2)Пусть u1 ,..., u p – список без повторений всех переменных, входящих вравенства системы (2). Систему (2) будем называть системой уравнений впеременных u1 ,..., u p .Решением системы уравнений(2) будем называть всякийнабор значенийконстант  1 ,...,  p из списка a1 ,..., a k такой, что в результатеодновременной замены всех переменных u1 ,..., u pна константы  1 ,...,  pсоответственно левые и правые части каждого равенства системы совпадут.Система уравнений (2) не имеет решений, если в списке  1 ,...,  p естьповторения, или если в системе уравнений (2) приходится сравнивать разныеконстанты.Определение 3.

F-набор называется пустым □, если все формулы, входящиев него, не имеют переменных и тавтологичны.Определение 4.F-набор называется тупиковым, если в него входит хотя быодна формула, не имеющая переменных и являющаяся ложной или не являющаясяни тавтологией ни противоречием.В разделе 2.2 сформулирован алгоритм IMA (inversemethodalgorithm),использующий тактику обратного метода.Алгоритм IMA (inverse method algorithm)1.

Строим δ-членный F-набор, формулы в котором не повторяются. То есть вформуле (1) удаляем все знаки конъюнкций и составляем список элементарныхдизъюнкций вида  S a1 ,..., ak   Pk x1 ,..., xn .ii2. Присваиваем значения переменным следующим образом:2.1. Отменяем все пометки об удалениях предикатных формул из S(ω) (еслиони были).2.2. Берем формулу  S a1 ,..., ak   Pk t1 ,..., t m  из рассматриваемого Fiнабора, содержащую m-местный предикатный символ такой, что набор t1 ,..., t mсодержит хотя бы одну переменную.2.3.

Ищем в S(ω)формулу Pk v1 ,..., vm  при наборе констант v1 ,..., vm сiотрицанием перед выбранным в п. 2.2 предикатным символом. Если нашлиподходящую формулу – помечаем еѐ как удаленную и переходим к пункту 2.4,если еѐ не существует, то переходим к пункту 3.2.4. Решаем систему уравнений, отождествляющую списки переменныхt1 ,..., t m и констант v1 ,..., vm . В случае, если эта система имеет решение, перейтик пункту 2.5, если система решений не имеет, то перейти к пункту 2.3.82.5. Заменяем во всем F-наборе переменные из списка t1 ,..., t m на ихзначение, полученные в пункте 2.4.2.6.

В полученном F-наборе удаляем повторения формул.2.7. Если получился пустой F-набор, то алгоритм заканчивает работу.2.8. Если получился тупиковый F-набор – перейти к пункту 3.2.9. Если в F-наборе все формулы, имеющие переменные помечены какудаленные – переходим к пункту 4.2.10. Если в F-наборе существуют элементарные дизъюнкции, имеющиепеременные, которым еще не присвоено значение, то перейти к пункту 2.2.3. Возвратная часть алгоритма.3.1.

Отменяем последнее действие пункта 2.5, если это возможно, ипереходим к пункту 2.33.2. Если отмена последнего действия пункта 2.5 невозможна, то помечаематомарную формулу Pk t1,..., t m  как удаленную и переходим к пункту 2.i4. Если все формулы помечены как удаленные значит, формула не выводима.Алгоритм заканчивает работу.В разделе 2.3 получены асимптотические оценки числа шагов работыалгоритма IMA.Определение 5.Однимшагомработы алгоритма называется как присвоениепеременной значения (решение одного уравнения вида х=а), так и проверка награфическое совпадение атомарных формул или подстановка значенийпеременных в атомарные формулы, имеющие вхождения данных переменных.Пусть l – наибольшее количество аргументов в атомарной формуле;s+1 – количество атомарных формул в каждом из дизъюнктов;s k – количество вхождений в исходную формулу атомарных формул с k-мпредикатным символом.Теорема 1.

(Нижняя оценка работы алгоритма IMA.)Количество шаговрешения задачи искусственного интеллекта, сведѐнной к доказательствуследствия вида S ( )  x A x  при использовании алгоритма IMA, основанногона тактиках Обратного метода не менее О(sl)шагов.Теорема 2. (Верхняя оценка числа шагов работы алгоритмаIMA.)Количество шагов затрачиваемых на решение задачи искусственногоинтеллекта, сведѐнной к доказательству следствия вида S ( )  x A x  прииспользовании алгоритма IMA, основанного на тактиках Обратного метода, атакже нахождения значений для переменных, существование которыхутверждается в заключении логического следования задачи не превосходит O   max sk  l  шагов. k9В третьей главе описаны идеи применения муравьиных алгоритмов ипараллельных вычислений для решения задач логико-предметного распознаванияобразов с помощью обратного метода Маслова.Используя идеи муравьиных алгоритмов, создаем многопроцессорнуюсистему, в которой действия между процессорами распределены поровну.

Равноеразделение действий необходимо для того, чтобы каждое действие имеловозможность стать первым выполненным. Каждый процессор может выполнятьследующие простые действия:1) присвоение значения переменным;2) замена всех вхождений переменной на еѐ значение;3) проверка формул на графическое совпадение;4) отмена присвоения значения переменным;5) отмена замены всех вхождений переменной;6) изменение приоритета данного действия на 0.В разделе 3.1 сформулирован алгоритм IAPTA, основанный на примененииобратного метода, муравьиных тактик и параллельных вычислений.АлгоритмIAPTA (Inverse Ant Parallel Tactic Algorithm)1. Строим δ-членный F-набор, формулы в котором не повторяются.

То естьпереписываем без конъюнкций все дизъюнкты вида  S    Pk x1 ,..., xn приi  1,...,  . Создаем популяцию из δ процессоров.КаждойPkпаре a ,..., ajni  j1iпотенциальноконтрарныхiPk x1,..., xniiiформули , входящих в один F-набор, назначаем приоритет ихотождествления равным 1. Остальные приоритеты назначаем равными 0.2. Копируем δ-членный F-набор δ – 1 раз.

Получаем ровно δ одинаковых Fнаборов. Назначаем i-му процессору i  1,...,   свою начальную формулу– формулу, с которой данный процессор начинает свойPk x1,..., xniiитерационный цикл, и потенциально контрарную ей формулу из S(ω), имеющуюприоритет, равный 1. Если каким-то двум процессорам назначены формулы,начинающиеся с одного и того же предикатного символа (таких формул не болееδ), то назначаем для них разные формулы из S(ω), потенциально контрарныеданной.Если для каких-то двух процессоров не существует разных потенциальноконтрарных формул, то формула не выводима.

Характеристики

Список файлов диссертации