Извлечение ответа из опровержения, основанного на резолюции. Этапы процесса извлечения ответа

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

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

Этапы извлечения ответа:

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

B. Сколемовские функции в предложениях, являющихся результатом отрицания целевой функции, заменяются на новые переменные.

C. Предложения, являющиеся результатом отрицания целевой функции, преобразуются в тавтологии.

D. Модификация дерева опровержений в дерево доказательств при неизменном множестве унификаторов.

E. Получение ответа в корневой вершине.

В качестве примера рассмотрим следующую логическую задачу:

“Если Джим ходит туда же, куда ходит Джон, и если Джон находится в школе, то где Джим?”

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

,

,

где х – названия мест, в которых могут находится Джон и Джим.

Целевая функция, соответствующая вопросу, имеет вид:

,

что буквально можно трактовать следующим образом:

«существует место X, такое, что в нем находится Джим».

Дерево опровержения строится обычным образом и показано на рис.3.

Рис.3. Дерево опровержения

Дерево доказательств показано на рис.4 и строится следующим образом:

o К каждому предложению, порожденному отрицанием целевой функции, добавляется его отрицание, то есть ППФ преобразуется в тавтологию.

o Вычисляются резолюции, аналогично дереву опровержений.

o В корневой вершине формируется ответ.

Рис. 4. Дерево доказательств

9. Теоремы Гёделя, Тарского и Черча о неполноте формальных систем

Общее представление о перспективах и рамках развития систем искусственного интеллекта в области формализации знаний и формальных методов получения новых знаний дают теоремы Гёделя, Тарского и Черча.

Первая теорема Гёделя (1931 год): Невозможно формализовать полностью любую систему знаний. Если доказано, что какая-либо формальная система знаний непротиворечива, значит она не полна.

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

Вторая теорема Гёделя: Невозможно доказательство непротиворечивости формальной системы средствами той же системы.

Теорема Тарского (1935 г.): Существуют формальная системы, для которых всякая интерпретация приводит к выражениям, одновременно истинным и недоказуемым.

Гёдель: “То, что истинно, всегда недоказуемо, то есть понятие истинности неформализуемо”.

Теорема Черча (1936 г.): Исчисление предикатов первого порядка неразрешимо, то есть существуют неразрешимые формальные системы.

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

6. ПЗ_6. Эволюционные аналогии в искусственных интеллектуальных системах

Эволюционное моделирование можно определить как вос­произведение процесса естественной эволюции с помощью спе­циальных компьютерных программ. Термин эволюция в ограни­ченном смысле, касающемся только смены поколений организ­мов, начал широко использоваться в XVII в. С появлением в 1859 г. учения Дарвина этот термин приобрел современное толко­вание: «Биологическая эволюция — историческое развитие орга­низмов». Необходимые и достаточные условия, определяющие главные факторы эволюции, были сформулированы в XX в. на основе созданной популяционно-генетической теории. К факто­рам, определяющим неизбежность эволюции, относятся:

• наследственная изменчивость как предпосылка эволюции, ее материал;

• борьба за существование как контролирующий и направляющий фактор;

• естественный отбор как преобразующий фактор.

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

Современная теория эволюции базируется на теории общей и популяционной генетики. Элементарным объектом эволюции является популяция — сообщество свободно скрещивающихся особей. В популяциях происходят микроэволюционные процес­сы, приводящие к изменению их генофонда. Преобразования ге­нетического состава популяции происходят под действием эле­ментарных эволюционных факторов (см. рис. 1). Случайные структурные или функциональные изменения в генах, хромосомах

Рис.1. Схема взаимодействия факторов эволюции

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

Преобразования генофонда популяции происходят под уп­равлением естественного отбора.

Эволюция — это многоэтапный процесс возникновения орга­нических форм с более высокой степенью организации, который характеризуется изменчивостью самих эволюционных меха­низмов.

История эволюционных вычислений началась с разработки ряда независимых моделей, среди которых были генетические алгоритмы и классификационные системы, созданные американским исследователем Дж. Холландом. Он предложил исполь­зовать методы и модели развития органического мира на Земле в качестве механизма комбинаторного перебора вариантов при ре­шении оптимизационных задач . Компьютерные реализа­ции этого механизма получили название «генетические алгорит­мы». В 1970-х гг. в рамках теории случайного поиска Л. А. Растригиным был предложен ряд алгоритмов, использующих идеи био­нического поведения особей . Развитие этих идей нашло от­ражение в цикле работ И. Л. Букатовой по эволюционному моде­лированию [2, 3]. Идеи М. Л. Цетлина, развитые в исследовани­ях поведения сообществ конечных автоматов, легли в основу ал­горитмов поиска глобального экстремума, основанных на моде­лировании процессов развития и элиминации особей. Боль­шой вклад в развитие эволюционного программирования внесли работы Л. Фогеля, А. Оуэнса и М. Уолша.

К основным направлениям развития эволюционного модели­рования на современном этапе относятся следующие:

• генетические алгоритмы (ГА), предназначенные для оптимизации функций дискретных переменных и использующие аналогии естественных процессов рекомбинации и селекции;

• классифицирующие системы (КС), созданные на основе генетических алгоритмов, которые используются как обучаемые системы управления;

• генетическое программирование (ГП), основанное на использовании эволюционных методов для оптимизации создаваемых компьютерных программ;

• эволюционное программирование (ЭП), ориентированное на оптимизацию непрерывных функций без использования рекомбинаций;

• эволюционные стратегии (ЭвС), ориентированные на оптимизацию непрерывных функций с использованием рекомбинаций.

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

В России развитием эволюционных методов занимаются на­учные школы профессоров И. Л. Букатовой , Д. И. Батище-ва , В. М. Курейчика и И. П. Норенкова.

Генетические алгоритмы

В основе генетических алгоритмов лежат генетика и хромо­сомная теория эволюции организмов. Хромосомы — это нитевид­ные структуры, находящиеся в клеточном ядре, которые являют­ся носителями наследственности. Каждая хромосома уникальна морфологически и генетически и не может быть заменена другой либо восстановлена при утере (при потере хромосомы клетка, как правило, погибает). Каждый биологический вид имеет опреде­ленное, постоянное количество хромосом. Каждая клетка содер­жит удвоенный набор морфологически и генетически сходных хромосом. Например, в клетках человека содержится 23 пары хромосом, в клетках комара — 3.

На процесс наследования признаков существенно влияет по­ведение хромосом при делении клеток. Существует митозное и мейозное деление клеток. Митозное деление обеспечивает рас­пределение исходных хромосом между двумя образующимися дочерними клетками, которые будут иметь равноценные наборы хромосом и будут очень похожи друг на друга. При этом проис­ходит редупликация исходных хромосом, вследствие чего к мо­менту деления клетки каждая хромосома состоит из двух копий исходной материнской хромосомы — сестринских хроматид (рис. 2).

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

В фазе редукции хроматиды обмениваются генами, т. е. участ­ками дезоксирибонуклеиновой кислоты (ДНК). После этого клетка разделяется на две новые, причем каждая из них содержит удвоенный набор хромосом, структуры которых отличаются от исходных. Механизм обмена генами называется кроссинговером.

В результате эквационного деления из двух получившихся кле­ток образуются четыре клетки, каждая из которых содержит оди­ночный набор хромосом (см. рис. 2).

Таким образом, митоз обеспечивает возобновление клеток, а мейоз отвечает за передачу наследственной информации и спо­собствует генетическому разнообразию организмов данного вида

Рис.2. Механизм деления клеток

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

• все признаки организма определяются наборами генов;

• гены — это элементарные единицы наследственной инфор­
мации, которые находятся в хромосомах;

• гены могут изменяться — мутировать;

• мутации отдельных генов приводят к изменению отдельных
элементарных признаков организма, или фенов.

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

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

1) рекомбинация хромосомных и нехромосомных генов;

2) рекомбинация целевых негомологических хромосом;

3) рекомбинация участков хромосом, представленных непре­
рывными молекулами ДНК.

Для построения генетических алгоритмов наибольший инте­рес представляет третий тип рекомбинации, который использует­ся для накопления в конечном решении лучших функциональ­ных признаков, какие имелись в наборе исходных решений. Су­ществует несколько типов рекомбинации участков хромосом: кроссинговер, сайт, иллегальная рекомбинация.

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

Сайт — это вид рекомбинации, при которой на коротких спе­циализированных участках хромосом происходит обмен генофо-ров (генных носителей), часто различных по объему и составу ге­нетической информации.

Иллегальная рекомбинация допускает негомологичные обме­ны, к которым относятся транслокации, инверсии и случаи не­равного кроссинговера. Такие способы могут оказаться полезны­ми при генерации новых решений.

В генетических алгоритмах наибольшее распространение по­лучила операция кроссинговера, заключающаяся в разрыве гомо­логичных хроматид с последующим соединением их в новом со­четании. Схема кроссинговера, демонстрирующая образование двух новых хромосом после обмена генетическим материалом, приведена на рис. 6.3.

Основная цель кроссинговера заключается в создании из имеющегося генетического материала желаемой комбинации признаков в одном решении.

Рис. 3. Схема кроссинговера: а — родительские хромосомы А, В до кроссинговера; б - хромосомы-потомки А', В 'после кроссинговера

Кроссинговер может происходить в нескольких точках. При­мер двойного кроссинговера между хромосомами/и w приведен на рис. 6.4.

Рис. 4. Схема двойного кроссинговера:

а — до кроссинговера; б— во время кроссинговера; в - после кроссинговера

Помимо кроссинговера для решения различных прикладных задач полезными являются такие генетические операции, как му­тация, инверсия, транслокация, селекция (инбридинг и гибриди­зация), генная инженерия.

Под мутацией понимается генетическое изменение, приводя­щее к качественно новому проявлению основных свойств генети­ческого материала: дискретности, непрерывности или линейнос­ти. Свойство дискретности позволяет выделить в исходном гене­тическом материале отдельные фрагменты, контролирующие те или иные функции. Непрерывность означает, что определенные комбинации генов совместно контролируют некоторую функ­цию. Линейность проявляется в определенной последовательно­сти генов в пределах группы сцепления.

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

Инверсия, транслокация, транспозиция, делеция и дуплика­ция относятся к разновидностям хромосомной мутации. При инверсии участок хромосомы поворачивается на 180°. Транслокацией называют перенос части одной хромосомы в другую. При переме­щении небольших участков генетического материала в пределах одной хромосомы используют термин транспозиция. Делеция — это выпадение отдельных участков хромосом, дупликация — повторе­ние участка генетического материала. Кроме перечисленных, су­ществуют другие разновидности хромосомных мутаций [7].

Селекция представляет собой форму искусственного отбора, который может быть массовым или индивидуальным. Установ­лено, что массовый отбор по фенотипу (совокупности всех внешних и внутренних признаков) менее эффективен, чем ин­дивидуальный, когда популяцию делят на отдельные линии, а для размножения выбирают носителей желаемых свойств. При­менение процедуры селекции в генетических алгоритмах опти­мизации способствует ускорению процесса синтеза искомого ре­шения.

Генная инженерия представляет собой совокупность методов для получения рекомбинантной ДНК и операции над нею. Ре-комбинантная ДНК получается путем объединения фрагментов ДНК различных организмов. Использование подходов генной инженерии позволяет в ряде задач значительно быстрее нахо­дить желаемое решение.

Механизм эволюции основан на трех повторяющихся про­цессах: отборе, амплификации (процесс производства потом­ков) и мутации. Он используется в качестве механизма случай­но направленного комбинаторного перебора при решении задач оптимизации и слабоструктурированных проблем принятия ре­шений.

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

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