Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Петухова Н.Д., аспирант первого года обучение кафедры математики СПб ГМТУ, ninka_mat@mail.ru

Аннотация

искусственный интеллект предикат исчисление

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

NP-трудность решения задач искусственного интеллекта, в частности, допускающих формализацию в исчислении предикатов [2], накладывает на алгоритмы их решения требования по оптимизации перебора, возникающего при поиске подходящей подстановки, обеспечивающей выполнение целевой формулы. Обратный метод Маслова разработан для эффективизации процедуры построения вывода в исчислении предикатов.

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

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

,

где - набор констант, - набор постоянных атомарных формул или их отрицаний, - элементарная конъюнкция вида [2]. Такое логическое следование равносильно истинности формулы:

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

(1)

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

,

где s - количество атомарных формул в .

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

В дополнение к идеям метода Маслова упорядочим все формулы в (1) следующим образом. Так как в каждой всего одна формула , имеющая переменные, сгруппируем их по одинаковым именам , затем упорядочим эти группы в порядке возрастания количества вхождений одноименных предикатных символов в (1). Формулы в сначала сгруппируем по именам предикатных символов, затем упорядочим в том же порядке по именам предикатных символов, что и в (1).

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

Алгоритм IMA (inverse method algorithm) поиска вывода,

основанный на Обратном методе.

Определение: Пусть список Г не повторяющихся формул вида называется F-набором для формул вида (1) [3], [4].

Определение: F-набор будем называть пустым ?, если все формулы, входящие в него не имеют переменных и тавтологичны [3], [4].

Определение: F-набор будем называть тупиковым, если в него входит хотя бы одна формула, не имеющая переменных и являющаяся ложной или не являющаяся ни тавтологией ни противоречием [3].

1. Строим д-членный F-набор, формулы в котором не повторяются. То есть переписываем без конъюнкций все дизъюнкты .

2. Присваиваем значения переменным следующим образом:

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

2.2. Берем формулу из рассматриваемого F-набора, содержащую m-местный предикатный символ такой, что набор содержит хотя бы одну переменную.

2.3. Ищем среди предикатов в отрицание предикатного символа при наборе констант , если нашли подходящее отрицание - помечаем его как удаленное и переходим к пункту 2.4., если его не существует - переходим к пункту 3.

2.4. Решаем систему уравнений, отождествляющую списки переменных и констант и . В случае, если эта система имеет решение В данном случае, помимо прочих, система уравнений не имеет решений, если какое-то из присваиваемых переменным значений, было присвоено ранее другой переменной., перейти к пункту 2.5., если система решений не имеет - перейти к пункту 2.3.

2.5. Заменяем во всем F-наборе переменные из списка на их значение, полученные в пункте 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.3.

3.2. Если отмена последнего действия пункта 2.5. не возможна - помечаем как удаленный и переходим к пункту 2.

4. Если все формулы помечены как удаленные значит, формула не выводима. Алгоритм заканчивает работу.

Алгоритм муравья.

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

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

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

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

Применяение муравьиной тактики.

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

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

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

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

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

Так как мы имеем i штук дизъюнктов в (1) и формулы не повторяются, то муравьев тоже i штук. Каждый муравей начинает свой итерационный цикл со своего дизъюнкта, и действует согласно алгоритму IMA поиска вывода, приведенному выше. Но при этом при каждом присвоении переменным значений муравьи связываются друг с другом, и сравнивают результаты.

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

Одинаковое присвоение значений переменным разными муравьями допустимо. Если один из муравьев не может присвоить ни одного нового значения (на всех замыканиях количество феромона равно 0), этот муравей перестает участвовать в итерациях. Алгоритм заканчивает работу, если доказана выводимость или на всех замыканиях количество феромона равно 0.

Литература

1. Dorigo M., Birattari M., Stutzle T. Ant Colony Optimization. Arti?cial Ants as a Computational Intelligence Technique. // IRIDIA - Technical Report Series, 2006, № 23, pp 1-2.

2. Kosovskaya T. Discrete Artificial Intelligence Problems and Number of Steps of their Solution // International Journal on Information Theories and Applications, Vol. 18, Number 1, 2011. P. 93 - 99.

3. Kosovskaya T., Petukhova N. The Inverse Method for Solving Artificial Intelligence Problems in the Frameworks of Logic-Objective Approach and Bounds of its Number of Steps // International Journal «Information Models and Analyses», Vol. 1. 2012. P. 84-93

4. Оревков В.П., Обратный метод поиска вывода // В кн.: Адаменко А.Н., Кучуков А.М., Логическое программирование и Visual Prolog - Санкт-Петербург, БХВ, 2003, с. 952-965

Размещено на Allbest.ru