Диссертация (1150569), страница 6

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

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

Решение σ1 поглощает решение σ2, еслиσ2 можно получить из σ1 путем замены некоторых основных переменных надругиепеременные.Решениесистемыуравнений(1.2.3)называютуниверсальным, если оно поглощает все решения этой системы.Процедура отождествления переменных с константами[61].Пусть Г – список формул вида (1.2.2); S – система уравнений в переменныхс переменными u1,..., u p в качестве неизвестных; σ – решение этой системы.Процедура отождествления переменных в списке Гсогласно системе S состоитв замене во всех формулах списка Г переменных u1,..., u p на их значения врешении σ.Процедура отождествления формул[61].Пусть Г – список формул вида (1.2.2). Допустим, что в список Г входятформулы Di a1,..., ak , u1,..., un , d1,..., d m  и Dr a1,..., ak , v1,..., vn , c1,..., cm  .Процедураотождествления этих формул в списке Г состоит в применении к списку Гпроцедурыпеременныхотождествленияпеременныхсогласносистемеуравненийв33 u1  v1  un  vn d1  c1 d m  cmОпределяемая процедура заканчивается успешно, если эта система имеетрешение.Процедура преобразования списков формул в F-наборы[61].Пусть Г – список формул вида (1.2.2).

Процедура преобразования спискаГ в F-набор состоит в последовательном выполнении следующих действий:1.Проверить, является ли список допустимым. Если является, перейти кследующему пункту. В противном случае определяемая процедуразаканчивается без результата.2.Сократить все повторения формул в списке.3.Проверить, не является ли список F-набором. Если является,обрабатываемый список будет результатом определяемой процедуры.

Впротивном случае перейти к следующему пункту.4.Найтивспискетакиеформулы Di a1,..., ak , u1,..., un , d1,..., d m иDr a1,..., ak , v1,..., vn , c1,..., cm  что наборы d1,..., d m и c1,..., cm имеют общуюпеременную. Затем применить процедуру отождествления этих формул.Если она заканчивается успешно, то перейти к следующему пункту. Впротивном случае определяемая процедура заканчивается без результата.5.Проверить, есть ли в полученном на предыдущем шаге спискеповторения формул. Если есть, то перейти к пункту 1. В противном случаеопределяемая процедура заканчивается без результата.34Процедура склейки формул в F-наборах[61].Пусть Г – F-набор.

Допустим, что в список Г входят формулы А и В.Процедура склейки формул А и В в спискеГ состоит в последовательномвыполнении следующих действий:1.Применить процедуру отождествления формул А и В. Если оназаканчивается успешно, то перейти к следующему пункту. В противномслучае определяемая процедура заканчивается без результата2.Применить к полученному на предыдущем шаге списку формулпроцедуру преобразования списков формул в F-наборы.Процедура построения замкнутого F-набора[61].Пусть Di a1,..., ak , u1,..., un , d1,..., d m  и Dr a1,..., ak , v1,..., vn , c1,..., cm  – формулывида (1.2.2), где все переменные a1,..., ak , u1,..., un , d1,..., dm , v1,..., vnи c1,..., cm –попарно различны. Обозначим первую формулу посредством А, а вторую – В.Предположим, что в А входит в качестве дизъюнкции атомарная формулаP t1,..., t s  , а в В – отрицание формулы Pv1,..., vs  , где Р – s-местный предикат.Процедура построения замкнутого F-набора по парам формул А, P(t1,…,ts) иВ, ¬P(v1,…,vs) состоит в последовательном выполнении следующих действий:1.Применить к списку (А, В) процедуру отождествления переменныхсогласно системе уравнений в переменных t1  v1  ;t  vs s2.Вслучаеуспешногозавершенияпроцедурыотождествления,применить процедуру преобразования полученного списка формул в Fнабор.35Определение1.2.9[61].F-набор будем называть замкнутым, если онможет быть получен в результате применения процедуры построениязамкнутого F-набора к подходящим парам формул А, P t1,..., t s  и В, P a1,..., as  .Процедура применения правила Б к F-наборам[61].Рассмотрим δ F-наборов1 Г1, D1 a1,..., ak , c11,..., c1n , d11,..., d m, Г , D a ,..., a , c ,..., c , d  ,..., d  1k 1n 1m (1.2.4)где Г1,…,Гδ – списки формул вида (1.2.2).

Если какие-нибудь два из этих наборовсодержат общую основную переменную, переименуем еѐ на новую переменную.Таким способом добьемся, чтобы F-наборы (1.2.4) не содержали общих основныхпеременных. Применим к списку Г1,…,Гδ процедуру отождествления переменныхсогласно системе уравнений в переменных: c11  c12    c1 c1  c 2    cnnn , 12 d1  d1    d1 12d m  d m    d m(1.2.5)а затем к полученному списку – процедуру преобразования списков формул в Fнаборы. Построенный таким образом F-набор Σ является результатомприменения правила Б к F-наборам (1.2.4), если значения переменныхd11, d21 ,..., dm1 в универсальном решении σ системы (1.2.5) удовлетворяютследующим условиям:1.Попарно различны;2.Не входят в формулы из Σ;363.Отличаютсяотзначенийврешенииσпеременныхc11, c12 ,..., c1n , c12 , c22 ,..., cn2 , c1 , c2 ,..., cn .Теорема[61].

Для того, чтобы формула F была доказуема в исчислениипредикатов, необходимо и достаточно вывести пустой F-набор □ в исчисленииблагоприятных наборов[61].Это исчисление задается приведенными ниже правилами А, Б, склейки иперестановки.Правило А. Замкнутые F-наборы являются благоприятными.Правило Б. Если δ F-наборов (1.2.4) являются благоприятными и процедураприменения правила Б к ним заканчивается успешно, то еѐ результат такжеявляется благоприятным F-набором.Правилосклейки.РезультатприменениякблагоприятномуF-наборупроцедуры склейки формул также является благоприятным F-набором.Правило перестановки.

Перестановка формул в благоприятном F-наборетакже является благоприятным F-набором.1.3. Алгоритмы МуравьяАлгоритмы муравья являются относительно новым подходом к проблемерешениязадачИскусственногоИнтеллекта.Социальноеповедениемуравьевпородило ряд методов и методик, среди которых наиболееизученным и наиболее успешным является метод оптимизации колонии муравьев(AntСolonyOptimization – ACO)[27], [82],[84], [87], [88].Восновеоптимизацииколониимуравьевлежитсобирательскийинстинктнекоторыхвидовмуравьев.Существуетдвеосновныехарактеристики,которыеотличают систему коммуникаций в колониях некоторых видов муравьев отдругих форм общения животных. Первая характеристика заключается вкосвенности формы общения посредством окружающей среды: насекомыеобмениваться информацией, изменяя свое окружение.

Вторая заключается в37локальности распространения информации: она может быть доступна только темнасекомым, которые посетили помеченную территорию или еѐ непосредственноеокружение.Муравьи наносят особое вещество – феромон – напротяжении своего путииз муравейника до источника пищи и обратно, отмечая некоторый благоприятныймаршрут. Другие муравьи воспринимают присутствие феромонов и, как правило,следуют пути, где концентрация феромонов выше. С помощью этого механизма,муравьи эффективно перевозят еду к муравейнику. Муравьиные алгоритмыиспользуют подобный механизм для решения оптимизационных задач.Причеманалогом феромона являются веса, приписываемые параметрам задачи.Алгоритмы муравья являются итерационными. На каждой итерацииучитываются действия искусственных муравьев. Каждый из них строит решение,совершая различные действия и не повторяя дважды одно и то же действие.

Накаждом шаге муравей выбирает следующее действие в соответствии состохастическим механизмом, который зависит от количества феромонов, которымпомечены действия перед их выполнением.В алгоритмах муравья популяция искусственных муравьев строит решениерассматриваемой задачи путем выполнения действий и обмена информацией окачестве этих решений через схемы связи.Алгоритмы муравья применяются для решения таких задач, как задачаКОММИВОЯЖЕРА, а также эти алгоритмы успешно применяют для решениязадач, возникающих в таких областях, как машинное обучение и биоинформатика[13], [30], [87].Алгоритмы муравья поддаются распараллеливанию процесса.

В частности,любые параллельные модели, используемые для других алгоритмов, могут бытьадаптированы к алгоритмам муравья. При мелкозернистом распараллеливанииодиночнымпроцессорампринадлежатмалыепопуляции,ипостояннопроизводится обмен информацией между процессорами. В крупнозернистых38подходах, наоборот, большие субпопуляции присвоены одному процессору иобмен информацией проводится редко. Исследование параллельных алгоритмовмуравья показали, что при мелкозернистом распараллеливании затрачиваетсямноговременинаобмениспользуютсякрупнозернистыеинформацией.схемыТакимобразом,распараллеливания,гдевNосновномколонийработают параллельно на n процессорах [74], [87], [101].1.4. Параллельные вычисленияХарактерной чертой многих современных вычислительных систем являетсявозможность одновременного или параллельного использования для обработкиинформации большого числа процессоров.

Идея параллельного вычислениясостоит в следующем. Есть задача, которая должна быть решена, причемдостаточно быстро. Есть несколько процессоров (возможно, даже сколь угодномного), каждый из которых способен эту задачу решить, но недостаточнобыстро[16], [75], [81], [91], [102]. Берем из имеющегося числа процессоров неодин, а несколько, и заставляем их одновременно работать над различнымичастями этой задачи, надеясь получить соответствующее ускорение.Разрабатывая систему параллельного вычисления следует разделить задачуна фрагменты, которые можно решать с использованием разных процессоровнезависимо друг от друга.Существует принципиальное различие между реализацией алгоритмов наклассической однопроцессорной вычислительной системе и реализацией тех жеалгоритмов на параллельных вычислительных системах [16].Оноопределяется следующимиобстоятельствами. Любойалгоритмописывается, в конечном счете, направленным графом, вершины которогоотождествляются с выполняемыми операциями, а дуги – с информационнымисвязями между ними.

Процесс его реализации на классической однопроцессорнойвычислительной системе можно трактовать как процесс последовательногоисключения по одной из входных вершин графа до полного его исчерпывания.39Так как такой процесс можно осуществить для любого безконтурного графа, тонет принципиальных ограничений в эффективной реализации любого алгоритмана однопроцессорной вычислительной системе.Если вычислительная система имеет ρ процессоров и ρ достаточно большое,то положение изменяется радикально. Во-первых, эффективная реализацияалгоритма теперь означает, что каждый раз в графе должно исключаться ρвершин. Но при ρ>1 граф алгоритма в силу своей внутренней структуры можетпросто не обладать возможностью допускать каждый раз исключение ρ вершин.

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

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