| Шпаргалка по информатике | |
| Автор: drug | Категория: Технические науки / Автоматизация | Просмотров: | Комментирии: 0 | 01-01-2013 22:18 |
Муравьиные алгоритмы: сущность, область применения, достоинства и недостатки.
В последние годы интенсивно разрабатывается научное направление NaturalComputing – «Природные вычисления», объединяющее математические методы, в которых заложены принципы природных механизмов принятия решения.
Имитация самоорганизации муравьиной колонии составляет основу муравьиных алгоритмов оптимизации – нового перспективного метода природных вычислений. Колония муравьев может рассматриваться как многоагентовая система, в которой каждый агент (муравей) функционирует автономно по очень простым правилам. В противовес почти примитивному поведению агентов, поведение всей системы получается на удивление разумным. Одним из подтверждений оптимального поведения муравьиной колонии является тот факт, что сеть гнезд суперколоний близка к минимальному остовному дереву графа их муравейника.
Идея муравьиного алгоритма – моделирование поведения муравьёв, связанного с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, находя новый кратчайший путь. При своём движении муравей метит путь феромоном, и эта информация используется другими муравьями для выбора пути. Это элементарное правило поведения и определяет способность муравьёв находить новый путь, если старый оказывается недоступным.
Рассмотрим случай, показанный на рисунке 1, когда на оптимальном доселе пути возникает преграда. В этом случае необходимо определение нового оптимального пути. Дойдя до преграды, муравьи с равной вероятностью будут обходить её справа и слева. То же самое будет происходить и на обратной стороне преграды. Однако, те муравьи, которые случайно выберут кратчайший путь, будут быстрее его проходить, и за несколько передвижений он будет более обогащён феромоном. Поскольку движение муравьёв определяется концентрацией феромона, то следующие будут предпочитать именно этот путь, продолжая обогащать его феромоном до тех пор, пока этот путь по какой-либо причине не станет недоступен.
Рисунок 1 – Выбор оптимального пути даижения к цели
Очевидная положительная обратная связь быстро приведёт к тому, что кратчайший путь станет единственным маршрутом движения большинства муравьёв. Моделирование испарения феромона – отрицательной обратной связи – гарантирует нам, что найденное локально оптимальное решение не будет единственным – муравьи будут искать и другие пути. Если мы моделируем процесс такого поведения на некотором графе, рёбра которого представляют собой возможные пути перемещения муравьёв, в течение определённого времени, то наиболее обогащённый феромоном путь по рёбрам этого графа и будет являться решением задачи, полученным с помощью муравьиного алгоритма.
Муравьиный алгоритм (англ. AntColonyOptimization, ACO) – один из эффективных полиномиальных алгоритмов для нахождения приближенных решений задач оптимизации. Подход предложен бельгийским исследователем Марко Дориго. Суть подхода заключается в анализе и использовании модели поведения муравьев, ищущих пути от колонии в пище.
В основе алгоритма лежит поведение муравьиной колонии – маркировка более удачных путей большим количеством феромона. Работы начинается с размещения муравьев в вершинах графа, затем начинается движение муравьев – направление определяется вероятностным методом:
P_i=(l_i^q×f_i^p)/(∑_(k=0)^N▒l_k^q ×f_k^p ),
где P_i - вероятность перехода по пути i, l_i - длина i-ого перехода, f_i - количество феромона на i-ом переходе, q – величина, определяющая «жадность» алгоритма, р – величина, определяющая стадность алгоритма и p + q = 1.
Решение не является точным и даже может быть одним из худших, однако, в силу вероятности решения, повторение алгоритма может выдавать (достаточно) точный результат.
Обобщенный вид алгоритма:
Любой муравьиный алгоритм, независимо от модификаций, представим в следующем виде
Пока (условия выхода не выполнены)
1. Создаём муравьёв
2. Ищем решения
3. Обновляем феромон
4. Дополнительные действия {опционально}
Теперь рассмотрим каждый шаг в цикле более подробно
1 Создаём муравьёв
Стартовая точка, куда помещается муравей, зависит от ограничений, накладываемых условиями задачи. Потому что для каждой задачи способ размещение муравьёв является определяющим. Либо все они помещаются в одну точку, либо в разные с повторениями, либо без повторений.
На этом же этапе задаётся начальный уровень феромона. Он инициализируется небольшим положительным числом для того, чтобы на начальном шаге вероятности перехода в следующую вершину не были нулевыми.
2Ищем решения
Вероятность перехода из вершины i в вершину j определяется по следующей формуле
P_ij (t)=(τ_ij 〖(t)〗^α 〖(1/d_ij )〗^β)/(∑_(j∈allowednodes)▒〖τ_ij 〖(t)〗^α 〖(1/d_ij )〗^β 〗),
где τ_ij (t)– уровень феромона, d_ij– эвристическое расстояние, а α, β – константные параметры.
При α = 0 выбор ближайшего города наиболее вероятен, то есть алгоритм становится жадным.
При β = 0 выбор происходит только на основании феромона, что приводит к субоптимальным решениям.
Поэтому необходим компромисс между этими величинами, который находится экспериментально.
3 Обновляем феромон
Уровень феромона обновляется в соответствии с приведённой формулой
τ_ij (t+1)=(1-p) τ_ij (t)+∑_█(k∈Colonythat@usededge (i,j))▒Q/L_k ,
Где p– интенсивность испарения, L_k (t)– цена текущего решения для k-ого муравья, а Q – параметр, имеющий значение порядка цены оптимального решения, то есть Q/(L_k (t)) – феромон, откладываемый k-ым муравьём, использующим ребро (i,j).
4 Дополнительные действия
Обычно здесь используется алгоритм локального поиска, однако он может также появиться и после поиска всех решений.
Для того чтобы построить подходящий муравьиный алгоритм для решения какой-либо задачи, нужно
1 Представить задачу в виде набора компонент и переходов или набором неориентированных взвешенных графов, на которых муравьи могут строить решения
2 Определить значение следа феромона
3 Определить эвристику поведения муравья, когда строим решение
4 Если возможно, то реализовать эффективный локальный поиск
5 Выбрать специфический ACO алгоритм и применить для решения задачи
6 Настроить параметр ACO алгоритма
Также определяющими являются
Количество муравьёв
Баланс между изучением и использованием
Сочетание с жадными эвристиками или локальным поиском
Момент, когда обновляется феромон
Самой распространенной задачей, на примере которой показывается действие муравьиных алгоритмов, это задача коммивояжёра (бродячий торговец). Рассмотрим пример ее решения.
Задача формулируется как задача поиска минимального по стоимости замкнутого маршрута по всем вершинам без повторений на полном взвешенном графе с n вершинами. Содержательно вершины графа являются городами, которые должен посетить коммивояжёр, а веса рёбер отражают расстояния (длины) или стоимости проезда. Эта задача является NP-трудной, и точный переборный алгоритм её решения имеет факториальную сложность.
В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество алгоритмов, время работы которых существенно зависит от размера входных данных; в то же время, если предоставить алгоритму некоторые дополнительные сведения (так называемых свидетелей решения), то он сможет достаточно быстро (за время, не превосходящее многочлена от размера данных) решить задачу.
Моделирование поведения муравьёв связано с распределением феромона на тропе – ребре графа в задаче коммивояжёра. При этом вероятность включения ребра в маршрут отдельного муравья пропорциональна количеству феромона на этом ребре, а количество откладываемого феромона пропорционально длине маршрута. Чем короче маршрут, тем больше феромона будет отложено на его рёбрах, следовательно, большее количество муравьёв будет включать его в синтез собственных маршрутов. Моделирование такого подхода, использующего только положительную обратную связь, приводит к преждевременной сходимости – большинство муравьёв двигается по локально оптимальному маршруту. Избежать этого можно, моделируя отрицательную обратную связь в виде испарения феромона. При этом если феромон испаряется быстро, то это приводит к потере памяти колонии и забыванию хороших решений, с другой стороны, большое время испарения может привести к получению устойчивого локального оптимального решения.
Теперь с учётом особенностей задачи коммивояжёра, мы можем описать локальные правила поведения муравьёв при выборе пути.
1 Муравьи имеют собственную «память». Поскольку каждый город может быть посещён только один раз, то у каждого муравья есть список уже посещённых городов – список запретов. Обозначим через J_(i,k) список городов, которые необходимо посетить муравью k, находящемуся в городе i.
2 Муравьи обладают «зрением» – видимость есть эвристическое желание посетить город j, если муравей находится в городе i. Будем считать, что видимость обратно пропорциональна расстоянию между городами η_ij=1/D_ij .
3 Муравьи обладают «обонянием» – они могут улавливать след феромона, подтверждающий желание посетить город j из города i на основании опыта других муравьёв. Количество феромона на ребре (i,j) в момент времени t обозначим через τ_ij (t).
4 На этом основании мы можем сформулировать вероятностно-пропорциональное правило, определяющее вероятность перехода k-ого муравья из города i в город j:
{█(P_(ij,k) (t)=([τ_ij (t)]^α×[η_ij ]^β)/(∑_(l∈J_(i,k))▒〖[τ_il (t)]^α×[η_il ]^β 〗),j∈J_(i,k);@P_(ij,k) (t)=0,j∈J_(i,k);)┤ (1)
Где α, β – параметры, задающие веса следа феромона. При α = 0 алгоритм вырождается до жадного алгоритма (будет выбран ближайший город). Заметим, что выбор города является вероятностным, правило (1) лишь определяет ширину зоны города j; в общую зону всех городов бросается случайное число, которое и определяет выбор муравья. Правило (1) не изменяется в ходе алгоритма, но у двух разных муравьёв значение вероятности перехода будут отличаться, т.к. они имеют разный список разрешённых городов.
5 Пройдя ребро (i,j), муравей откладывает на нём некоторое количество феромона, которое должно быть связано с оптимальностью сделанного выбора. Пусть T_k (t) есть маршрут, пройденный муравьём k к моменту времени t, L_k (t) – длина этого маршрута, а Q – параметр, имеющий значение порядка длины оптимального пути. Тогда откладываемое количество феромона может быть задано в виде
∆τ_(ij,k) (t)={█(Q/(L_k (t) ),(i,j)∈T_k (t);@0,(i,j)∉T_k (t);)┤
Правила внешней среды определяют, в первую очередь, испарение феромона. Пусть p∈[0,1] есть коэффициент испарения, тогда правило испарения имеет вид
τ_ij (t+1)=(1-p)×τ_ij (t)+∆τ_ij (t);∆τ_ij (t)=∑_(k=1)^m▒〖∆τ_(ij,k) (t) 〗, (2)
В начале алгоритма количества феромона на рёбрах принимается равным небольшому положительному числу. Общее количество муравьёв остаётся постоянным и равным количеству городов, каждый муравей начинает маршрут из своего города.
Дополнительная модификация алгоритма может состоять в ведении так называемых «элитных» муравьёв, которые усиливают рёбра наилучшего маршрута, найденного с начала работы алгоритма. Обозначим через T* наилучший текущий маршрут, через L* – его длину. Тогда если в колонии есть e элитных муравьёв, то рёбра маршрута получат дополнительное количество феромона
∆τ_e=e×Q/L^* (3)
Алгоритм для решения данной задачи имеет вид:
1 Ввод матрицы расстояний D
2 Инициализация параметров алгоритма – α, β, e, Q
3 Инициализация рёбер – присвоение видимости η_ij и начальной концентрации феромона
4 Размещение муравьёв в случайно выбранные города без совпадений
5 Выбор начального кратчайшего маршрута и определение L*
//Основной цикл
6 Цикл по времени жизни колонии t=1, t_max
7 Цикл по всем муравьям k=1,m
8 Построить маршрут T_k (t) по правилу (1) и рассчитать длину L_k (t)
9 Конец цикла по муравьям
10 Проверка всех L_k (t) на лучшее решение по сравнению с L*
11 В случае если решение L_k (t) лучше, обновить L* и T*
12 Цикл по всем рёбрам графа
13 Обновить следы феромона на ребре по правилам (2) и (3)
14 конец цикла по рёбрам
15 конец цикла по времени
16 Вывести кратчайший маршрут T* и его длину L*
Сложность данного алгоритма, как несложно заметить, зависит от времени жизни колонии t_max, количества городов n и количества муравьёв в колонии m.
Области применения и возможные модификации
Поскольку в основе муравьиного алгоритма лежит моделирование передвижения муравьёв по некоторым путям, то такой подход может стать эффективным способом поиска рациональных решений для задач оптимизации, допускающих графовую интерпретацию. Ряд экспериментов показывает, что эффективность муравьиных алгоритмов растёт с ростом размерности решаемых задач оптимизации. Хорошие результаты получаются для нестационарных систем с изменяемыми во времени параметрами, например, для расчётов телекоммуникационных и компьютерных сетей. В Интернете можно найти описание применения муравьиного алгоритма для разработки оптимальной структуры съёмочных сетей GPS в рамках создания высокоточных геодезических и съёмочных технологий. В настоящее время на основе применения муравьиных алгоритмов получены хорошие результаты для таких сложных оптимизационных задач, как задача коммивояжёра, транспортная задача, задача календарного планирования, задача раскраски графа, квадратичная задача о назначениях, задача оптимизации сетевых трафиков и ряд других.
Качество получаемых решений во многом зависит от настроечных параметров в вероятностно-пропорциональном правиле выбора пути на основе текущего количества феромона и от параметров правил откладывания и испарения феромона. Возможно, что динамическая адаптационная настройка этих параметров может способствовать получению лучших решений. Немаловажную роль играет и начальное распределение феромона, а также выбор условно оптимального решения на шаге инициализации.
Перспективными путями улучшения муравьиных алгоритмов являются различные адаптации параметров с использованием базы нечётких правил и их гибридизация, например, с генетическими алгоритмами. Как вариант, такая гибридизация может состоять в обмене через определённые промежутки времени текущими наилучшими решениями.
В заключение отметим достоинства и недостатки муравьиных алгоритмов:
Достоинства:
1 Для TSP (Traveling Salesman Problem – задача коммивояжёра) сравнительно эффективны
Для небольшого количества узлов TSP может быть решена полным перебором
Для большого количества узлов TSP вычислительно сложна (NP-трудная) – экспоненциальное время сходимости
2 Работают лучше, чем другие глобальные оптимизации для TSP (нейронные сети, генетические алгоритмы)
3 Сравнение с GAs (GeneticAlgorithms – генетические алгоритмы):
Опираются на память обо всей колонии вместо памяти только о предыдущем поколении
Меньше подвержены неоптимальным начальным решениям (из-за случайного выбора пути и памяти колонии)
4 Могут использоваться в динамических приложениях (адаптируются к изменениям, скажем, расстояний)
5 Применялись к множеству различных задач
Маршрутизация
Маршрутизация сети
Планирование
Многое другое
Недостатки:
1 Теоретический анализ затруднён:
В результате последовательности случайных (не независимых) решений
Распределение вероятностей меняется при итерациях
Исследование больше экспериментальное, нежели теоретическое
2Сходимость гарантируется, но время сходимости не определено
3 Обычно необходимо применение дополнительных методов таких, как локальный поиск
4 Сильно зависят от настроечных параметров, которые подбираются только исходя из экспериментов
Гибридные экспертные системы проектирования ресурсосберегающих установок первичной нефтепереработки.
Важнейшими критериями, определяющими эффективность нефтеперерабатывающих и нефтехимических производств, являются показатели ресурсосбережения, и особенно энергосбережения, так как стоимость энергии постоянно возрастает. Необходимость разработки и реализации новых энергосберегающих технологий связана прежде всего с неиспользуемыми вторичными энергоресурсами (ВЭР) нефтеперерабатывающих производств. В энергетическом балансе НПЗ на долю прямого топлива приходится 43–45%, на тепловую энергию – 40–42%, на электрическую – 13–15%. Полезное использование энергии составляет лишь 30–40%. Энергия теряется с охлаждающей водой, с дымовыми газами и за счет теплообмена с окружающей средой горячих поверхностей оборудования. Поэтому основным направлением решения проблемы энергосбережения при проектировании НПЗ является максимальное использование ВЭР благодаря созданию оптимальных теплообменных систем (ТС) и систем рекуперации высоко- и низкопотенциального тепла.
Важную роль в разработке проектов НПЗ играет выбор их технологической схемы, разработка которой требует выявления всех возможных вариантов получения необходимого количества товарных нефтепродуктов с требуемыми показателями качества при ограниченном использовании сырьевых ресурсов и наименьших капитальных и эксплуатационных затратах [1]. Так как свойства нефтяного сырья, поступающего на переработку, меняются в зависимости от состава сырья, то важным является выбор типа схемы переработки нефти применительно к конкретному виду сырья и производимым целевым продуктам, а также возможность использования данной схемы при изменении состава сырья.
Одним из способов успешного решения указанных проблем является создание систем автоматизированного проектирования (САПР) и специальных экспертных систем (ЭС), которые на основе соответствующего математического и программно-информационного обеспечения позволяют aвтоматизированно принимать оптимальные решения по многим вопросам проектирования.
Разработка моделей представления знаний
Экспертные системы способны в интеллектуальном диалоге с непрограммирующим пользователем на основе накопления и переработки специальных знаний и правил принятия решений проводить экспертизу, консультировать и давать рекомендации по выбору действий (операций), распознавать ситуации, ставить диагноз и обосновывать заключения при поиске решений неформализованных задач некоторой проблемной области [2, 3].
Каждая неформализованная задача имеет семантическое или смысловое решение, представляющее собой словесное описание или графическое изображение некоторого явления, принципиальной технологической схемы или конструкции объекта. Поиск решения неформализованной задачи осуществляется путем переработки разнообразных знаний с помощью символьных рассуждений, основанных на использовании либо стратегии здравого смысла и эвристических правил, либо логического вывода.
Задача проектирования энергосберегающих установок первичной нефтепереработки как неформализованная задача химической технологии формулируется следующим образом: при заданных составах и свойствах потоков нефтяного сырья, названиях и показателях качества целевых продуктов, различных видах химико-технологических процессов (ХТП) нефтепереработки и типах инженерно-аппаратурного оформления ХТП требуется определить виды ХТП и типы инженерно-аппаратурного оформления ХТП, структуру, покомпонентный состав и фазовое состояние технологических потоков между аппаратами технологической схемы, оптимальные технологические параметры потоков, обеспечивающие максимум рекуперируемой энергии и минимум приведенных затрат на функционирование установки.
Разработка рациональных семантических решений задачи синтеза энергосберегающих НПЗ базируется на применении следующих основных физико-химических и технологических способов ресурсосбережения: способа наилучшего использования движущей силы ХТП, способа наиболее полной переработки сырья, способа рационального использования топливно-энергетических ресурсов, способа наилучшего функционально-структурного использования аппаратов и машин. Для поиска семантического решения используются декомпозиционные принципы синтеза ресурсосберегающих химико-технологических систем (ХТС), различные эвристическо-вычислительные процедуры автоматизированного синтеза ХТС, а также гибридные ЭС.
Основным интеллектуальным компонентом гибридной ЭС является база знаний, в которой представлены как результаты теоретических исследований, так и практические знания экспертов. База знаний состоит из базы данных, базы правил и базы процедур. Для программной реализации знаний предложено использовать продукционно-фреймовые модели [2]. При этом все декларативные и процедурные знания подразделяются на три класса: предметные знания, управляющие и метазнания. Предметные знания отображаются в виде фреймов, а управляющие знания, необходимые для поиска и генерации семантического решения неформализованной задачи, и метазнания отображаются в виде продукционных правил.
Для классификации знаний предметной области “Проектирование энергосберегающих установок первичной нефтепереработки” был проведен концептуальный анализ знаний о влиянии свойств нефтяного сырья на тип технологической схемы первичной нефтепереработки и об особенностях технологии первичной нефтепереработки, в результате которого выделены ключевые понятия и отношения между понятиями, необходимые для разработки процедуры поиска оптимального решения задачи.
Предметные знания соответствуют декларативным знаниям. К ним относятся: основные понятия (объекты) – нефтяное сырье, нефтепродукт, термодинамическое равновесие, фазовое равновесие, технологический поток, аппараты (колонна ректификации, теплообменник, печь и др.); операции – массопередача, теплообмен, конденсация, испарение, синтез целевых продуктов и др.; ситуации – подготовка сырья, разделение многокомпонентной смеси, нагревание технологического потока и др.
Управляющие знания соответствуют процедурным знаниям в области химической технологии и технологии переработки нефти. К управляющим знаниям относятся: законы равновесия, законы сохранения массы и энергии; законы термодинамики; физико-химические и технологические принципы наилучшего использования движущей силы ХТП, наиболее полного использования сырья и энергии в ХТС, наилучшего использования оборудования и др.; алгоритмы расчета состава смесей веществ, расчета массы и объемов веществ; системы уравнений математических моделей ХТП и ХТС и др.
В результате анализа знаний о проектировании энергосберегающих НПЗ можно сделать следующие выводы:
1) физико-химические свойства нефтяного сырья и нефтепродуктов являются основой выбора технологической схемы переработки нефти;
2) вариант технологической схемы переработки выбирается для определенного направления переработки нефти;
Рис. 1. Структура фрейма-прототипа “Нефтяное сырье”
3) каждый вид нефти характеризуется выходом узких и широких фракций, потенциалами отдельных топливных дистиллятов, показателями качества;
4) ХТП и продукты связаны друг с другом определенными закономерностями (между отбором топливных дистиллятов из нефти и широких фракций – продуктов вторичной нефтепереработки, качеством сырья, выходом и качеством конечных продуктов, технологическими параметрами ХТП, значениями выходов и показателями качества конечных продуктов и т.д.).
Продукционные правила имеют вид: “ЕСЛИ (условие) – ТО (действие)”. Условие представляет собой предложение, связывающее объекты с некоторыми конкретными их свойствами или значениями с помощью знака “равно”: “=”. В условную часть продукционного правила может входить несколько выражений, объединенных союзом “и”. В действии правила указывается заключение или операция, которые должны выполняться, если условие удовлетворено. В результате анализа предметной области выделены следующие классы продукционных правил: правила выбора технологической схемы первичной нефтепереработки; правила выбора вида уравнений расчета плотности нефти, дистиллятов и остатков; правила выбора вида уравнений расчета выхода легких фракций и базовых масел; правила выбора вида уравнений расчета параметров физико–химических свойств нефтяных фракций и параметров равновесия сложных смесей в зависимости от состава, плотности, температуры и давления смеси; правила выбора способов рекуперации ВЭР; правила выбора пар технологических потоков для участия в рекуперативном теплообмене и правила выбора последовательности выделения продуктов из многокомпонентной смеси.
Для моделирования и переработки знаний предметной области нами разработаны фреймы-прототипы и фреймы-примеры. Фреймы-прототипы отображают абстрактные понятия для класса сущностей или явлений, представляющих общие понятия предметной области. Фреймы-примеры отображают знания о конкретных сущностях и явлениях (объектах, ситуациях и т.д.) и используются для постановки исходной задачи, а также для генерации семантических решений. При преобразовании фрейма-прототипа во фрейм-пример каждой характеристике фрейма-прототипа присваивается конкретное значение. На рисунке 1 приведена структура фрейма-прототипа “Нефтяное сырье”.
Общая стратегия вывода семантических решений задачи проектирования энергосберегающих установок с использованием продукционных правил определяет тип процедуры управления выводом, тип процедуры проведения рассуждений при выводе, тип процедуры разрешения конфликтов или противоречий продукционных правил.
Описание процедуры вывода решений
Процедура вывода оптимальных решений при проектировании включает следующие этапы.
1. Ввод исходных знаний и данных о виде нефтяного сырья, которое может перерабатываться на проектируемой установке.
2. Расчет физико-химических свойств потоков нефтяного сырья и фракций с использованием уравнений, выбранных на основе продукционных правил, и с применением вычислительных алгоритмов, включенных в состав обеспечения ЭС.
3. Выбор типа технологической схемы установки первичной нефтепереработки и выбор инженерно-аппаратурного оформления установки с использованием продукционных правил.
4. Составление и расчет системы уравнений материальных и тепловых балансов для выбранной на этапе 3 технологической схемы.
5. Сравнение эффективности альтернативных технологических схем.
Стратегия вывода оптимального решения в данной процедуре осуществляется в обратном направлении, от “цели к данным”, то есть целевое состояние задачи используется как исходное при поиске семантического решения. Базовой стратегией при генерации альтернативных вариантов технологических схем является стратегия “поиска в глубину” на дереве вариантов решений [3]. Эта стратегия реализуется следующим образом. Сначала выбираются все продукционные правила, в заключение которых устанавливается какой-либо тип установки первичной нефтепереработки (или другое целевое состояние). Затем проверяется каждая часть предпосылки этого правила, и программа строит обратную цепочку для проверки фактов каждой предпосылки. В ходе поиска решения строится “и/или” дерево, называемое деревом целей. Каждая вершина этого дерева соответствует некоторой цели.
Операция обратного вывода позволяет отыскивать путь на данном дереве, то есть для подтверждения одной из всех связей “или”, которые соответствуют данной цели, выбирается одна, и делается попытка подтвердить все вершины, являющиеся предусловиями этой цели. В случае неудачи выбирается следующая связка “или”, и повторяется аналогичная процедура. Если хотя бы одна из связок “или” позволяет вывести последнюю цель, то доказательство этой цели является успешным.
Архитектура гибридной экспертной системы и ее использование
Рис. 2. Архитектура гибридной экспертной системы
Архитектура гибридной ЭС, показанная на рисунке 2, образована совокупностью трех функциональных блоков, реализованных в виде программных комплексов: базы знаний, блока вывода решения, предназначенного для генерации семантического решения с применением продукционных правил, и интерфейса пользователя. Программная реализация гибридной ЭС осуществлена на языке программирования Турбо-Паскаль. База знаний программно реализует декларативные и процедурные знания. При разработке логической структуры базы знаний применена методология создания расширенной реляционной модели.
Блок вывода решений, или машина вывода, реализует механизм обратного вывода “от цели к данным” и подсистему объяснения, показывающую, как было сгенерировано конкретное семантическое (смысловое) решение. Блок вывода решения имеет на входе полученное в результате диалога с пользователем описание исходных знаний и данных для поиска решения. В результате анализа знаний гибридная ЭС генерирует набор семантических решений, представляющих собой описание технологических схем первичной нефтепереработки, которые далее передаются в блок цифрового моделирования для выбора оптимальной технологической схемы.
При функционировании гибридной ЭС пользователь решает следующие задачи: выбирает тип технологической схемы первичной нефтепереработки; определяет направления использования ВЭР; выбирает номенклатуру продукции, вырабатываемой из сырья заданного состава. Взаимодействие пользователя с ЭС осуществляется в форме диалога, общая процедура которого включает этапы: инструктаж о режимах работы ЭС, постановку задачи, поиск решения задачи, выдачу результата – семантического решения задачи, объяснение всех операций вывода решения.
На этапе инструктажа ЭС объясняет пользователю свое назначение и режимы функционирования, определяет порядок ведения диалога и перечисляет средства, доступные пользователю. Этап постановки задачи состоит в сборе основной информации, необходимой для начала поиска. У пользователя запрашивается информация о виде нефтяного сырья, поступающего на переработку, а также цель использования ЭС. На этом этапе осуществляется структуризация исходной неформализованной задачи и распределение подзадач между пользователем и системой, то есть указывается, какие подзадачи решает сама ЭС и при решении каких задач ЭС обращается за помощью к пользователю.
Объяснительные способности ЭС реализуются в виде двух программных модулей. Первый модуль позволяет ЭС “объяснить” ход своих рассуждений путем вывода на экран цепочки продукционных правил, которыми она воспользовалась для получения конкретного заключения. Второй модуль позволяет ЭС отвечать пользователю, почему должен быть задан тот или иной вопрос.
Используя меню, пользователь имеет возможность добавить факт в базу знаний, просмотреть факты базы знаний, добавить новые продукционные правила.
Разработанная гибридная ЭС была использована при выборе установки первичной переработки уренгойской нефти, а также для синтеза ТС подогрева сырья этой установки с целью повышения показателей энергосбережения. Для первичной переработки нефти на основании правил из базы знаний была выбрана атмосферно-вакуумная установка с двукратным испарением, схема которой приведена на рисунке 3.
В результате анализа ТС, входящей в предложенную технологическую схему, с использованием продукционных правил была синтезирована ТС подогрева сырья на данной установке и разработаны рекомендации по ее реконструкции с целью повышения степени рекуперации теплоты за счет рационального перераспределения обменивающихся теплом потоков. С использованием блока цифрового моделирования были определены параметры состояния технологических потоков и степень рекуперации теплоты, которая составила 0.93.
Рис. 3. Схема установки АВТ:
1 - теплообменная система; 2 - электродегидраторы; 3 - отбензинивающая колонна; 4 - система атмосферной и вакуумной перегонки нефти; I - сырая нефть; II - обессоленная нефть; III - отбензиненная нефть; IV - нефтепродукты на переработку; V, VI, VII, VIII - нефтепродукты, циркуляционное орошение
3.Anytime алгоритмы: сущность, область применения, достоинства и недостатки.
В промышленных системах поддержки принятия решений, как правило, используются продукционные системы, для которых процесс принятия решения можно отобразить посредством дерева решений, вершины которого соответствуют состояниям (корневой вершине соответствует начальное состояние), а ребра – правилам преобразований. Специфика плохоформализуемых и слабоструктурированных задач принятия решений – их комбинаторность, т.е. лавинообразный рост решающих деревьев в процессе поиска, что не позволяет использовать для решения таких задач строгие алгоритмические методы и модели теории принятия решений.
Однако существует класс алгоритмов, которые способны прерываться в любой требуемый момент времени, возвращая лучший найденный на текущий момент результат и некоторую величину, характеризующую качество этого результата. Другой чертой этого класса алгоритмов является их способность оценивать качество результата на основе времени выполнения вычислений. Такие алгоритмы называются anytime-алгоритмами (постепенно приближающие псевдо-оптимальные алгоритмы реального времени), т.е. алгоритмов реального времени, которые в каждый определённый момент работы имеют лучшее (на данный момент) решение, при этом пользователь может просматривать эти псевдо-оптимальные решения в режиме реального времени, а последовательность таких решений в пределе даёт оптимальное решение.
Anytime-алгоритмы чрезвычайно важны в разработке искусственного интеллекта по двум причинам. Первая заключается в том, что хотя многие алгоритмы искусственного интеллекта могут искать точное решение задачи в течение долгого времени, зачастую достаточно хорошее неточное, приближенное решение может быть найдено за значительно более короткое время. Если бы было возможно определить, сколько времени необходимо для того, чтобы получить адекватный результат, многие интеллектуальные системы можно было бы сделать более адаптированными к сложной и изменяющейся окружающей среде. Вторая причина – технические приемы anytime-алгоритмов можно применять не только для одного вычислителя, но и в мультиагентных и параллельных системах.
Большинство из Anytime-алгоритмов можно представить в следующем виде:
AA = , где
f(r) – функция итерационного улучшения результата r. Функция многократно выполняется над текущим результатом r. Качество результата улучшается с каждой новой итерацией;
Q(r) – функция качества полученного результата. Функция Q(r) возвращает информацию о качестве текущего результата r. Anytime-алгоритмы возвращают помимо основного результата также и некоторые его характеристики (меры);
PP(Q,t) – профиль производительности. Функция ожидаемого качества решения от времени его поиска. Это самый важный компонент Anytime-алгоритма.
Алгоритмы планирования могут использовать эту оценку для определения наиболее эффективного количества времени, необходимого для выделения алгоритму.
Материал данной лекции формулирует метод построения anytime-алгоритмов для целого класса задач. Сначала, перед описанием применяемых методов принятия решений, перечислим сами рассматриваемые задачи, точнее – классы рассматриваемых задач.
Во-первых, классическая задача коммивояжёра. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Вообще, задаче коммивояжёра на протяжении последних десятилетий было посвящено очень много публикаций, но, конечно, проблемы остаются: какого-либо «универсального» метода решения задачи коммивояжёра просто не может существовать. В последние несколько лет авторы работ по эвристическим методам решения задачи коммивояжёра чаще других рассматривают так называемые симметричные – т.е. когда симметричной относительно главной диагонали является матрица стоимостей – и особенно их частные случаи, т.н. метрические задачи коммивояжёра. При этом для их решения чаще всего применяются фактическое сведéние работы с матрицей задачи коммивояжёра к работе с координатами городов. Однако, классический метод ветвей и границ может также с успехом применяться – для получения не только точного решения задачи коммивояжёра, но и различных эвристических; при этом сведéние задачи к работе с координатами городов не используется.
Во-вторых, несколько связанных между собой задач минимизации недетерминированных конечных автоматов (альтернативные названия – конечные автоматы-распознаватели, автоматы Рабина-Скотта). Наиболее важной из них, по-видимому, является задача вершинной минимизации – задача построения недетерминированных конечных автоматов, допускающего заданный регулярный язык и имеющего минимально возможное число вершин. С момента выхода книги в описании точных алгоритмов мало что изменилось: все описанные в литературе алгоритмы являются экспоненциальными – относительно числа состояний имеющегося автомата. Последнее обстоятельство связано с тем, что все имеющиеся алгоритмы требуют построения эквивалентного канонического конечного автомата – или какой-либо аналогичной графоподобной структуры.
Общим во всех описанных задачах являются следующие обстоятельства. Каждая из задач может быть просто решена для небольших размерностей (например – для матриц небольших размерностей в задачи коммивояжёра и в задаче вершинной минимизации конечных автоматов), но при переходе к большим размерностям (30 состояний в задаче вершинной минимизации конечного автомата, 70 городов в случайной задачи коммивояжёра) данные задачи в реальное время невозможно точно решить даже с помощью метода ветвей и границ и других эвристик.
Описываемые в лекции методы решения данных задач строятся на основе комбинации эвристик, взятых из нескольких различных областей теории искусственного интеллекта.
Во-первых, используется незавершённый метод ветвей и границ.
Во-вторых, для выбора очередного шага этого метода при наличии нескольких эвристик применяются динамические функции риска.
В-третьих, одновременно с функциями риска для подбора коэффициентов усреднения различных эвристик применяются генетические алгоритмы.
В-четвёртых, упрощённое самообучение теми же генетическими методами применяется и для старта незавершённого метода ветвей и границ. Таким образом, можно сказать, что данные комбинации эвристик представляют собой специальный поход к построению anytime-алгоритмов для задач дискретной оптимизации.
Незавершённый метод ветвей и границ
Метод ветвей и границ будем описывать для произвольной задачи дискретной оптимизации, однако, где это необходимо, будем приводить примеры метода ветвей и границ для самой известной из рассматриваемой нами задач – задачи коммивояжера. При этом будем употреблять следующие названия:
«случайная задача коммивояжера» – когда все элементы матрицы задачи коммивояжера генерируются как случайная величина с заданным законом равномерного распределения;
«метрическая задача коммивояжера» – когда случайно генерируются координаты всех городов как точек единичного квадрата (с равномерным распределением обеих координат), а элементы матрицы задачи коммивояжера суть расстояния между соответствующими точками. При этом очевидно выполнение следующего дополнительного условия, условия симметричности матрицы относительно главной диагонали: aij=ajiдля всех возможных i и j.
В последние годы наиболее часто встречаются публикации, посвящённые метрической задачи коммивояжера. Это объясняется, в первую очередь, тем обстоятельством, что один шаг алгоритма метода ветвей и границ «в среднем» упрощает матрицу случайной задачи коммивояжера значительно больше, чем матрицу метрической задачи коммивояжера.
Будем далее называть правой задачей очередного шага метода ветвей и границ задачу, полученную при уменьшении размерности. Например, в задаче коммивояжера таковой является та подзадача, в которой мы обязательно включаем в выбираемый маршрут дугу между двумя рассматриваемыми городами, а в задаче вершинной минимизации недетерминированных конечных автоматов – подзадача, когда мы обязательно включаем рассматриваемый блок в выбираемое множество блоков. Другую альтернативу – т.е. когда принимается временное решение об отсутствии некоторого элемента в оптимальном решении (например, когда в задаче коммивояжера мы обязательно не включаем в выбираемый маршрут дугу между двумя выбранными городами) – назовём, соответственно, левой задачей очередного шага метода ветвей и границ. Смысл всех модификаций метода ветвей и границ состоит в том, что с помощью некоторых эвристик мы добиваемся того, чтобы вероятность наличия оптимального решения была больше для правой задачи, чем для левой – ведь размерность правой задачи на 1 меньше, чем левой.
Несложная эвристика, преобразующая завершённый метод ветвей и границ в незавершённый (а именно на основе незавершённого метода и формируются все anytime-алгоритмы в лекции), заключается в следующем: каждый раз при получении очередной правой задачи (назовём её задачей T) мы фактически строим последовательность правых задач– т.е. саму задачу T, правую задачу задачи T, правую задачу правой задачи задачи T, и так далее. Естественно, каждый раз строятся (и включаются в список задач для потенциального решения в последующем) и соответствующие левые задачи – левая задача задачи T, левая задача правой задачи задачи T, и так далее. Описанный процесс заканчивается:
либо при получении тривиальной задачи (задачи нулевой размерности) – в этом случае мы запоминаем её решение (границу, получаемый к моменту её постановки тур, и т.п. характеристики) в качестве текущего на данный момент времени псевдо-оптимального решения нашего anytime-алгоритма;
либо при получении в какой-либо задаче достаточно большой границы – например, большей, чем имеющееся на данный момент времени псевдо-оптимальное решение.
Отметим, что на практике описанный процесс построения ППЗ не занимает много лишнего времени и не приводит к большому увеличению списка задач, предназначенных для потенциального решения в будущем.
Итак, был описан простой процесс построения anytime-алгоритма на основе некоторого конкретного варианта метода ветвей и границ. Важно отметить, что данный процесс возможен именно потому, что любая правая задача имеет размерность меньше, чем соответствующая ей левая.
Как уже было отмечены выше, кроме эвристики, формулирующей сам метод ветвей и границ, всегда необходима ещё одна эвристика. А именно – эвристика для выбора элемента, «разделяющего» рассматриваемую задачу на левую и правую подзадачи.
Однако некоторый эвристический разделяющий алгоритм может быть заменён на какой-либо другой; более того, очень часто при решении некоторой задачи дискретной оптимизации с помощью метода ветвей и границ желательно выбирать один из нескольких разделяющих алгоритмов – в зависимости от того, какая именно подзадача решается. Разные варианты разделяющих алгоритмов могут быть выбраны в зависимости от размерности решаемой задачи, от её границы, а также от многих других характеристик, связанных с конкретными задачами оптимизации.
В рассматривавшемся нами примере описания метода ветвей и границ для задачи коммивояжера используется хороший (т.е. дающий хорошие результаты по сравнению с другими) разделяющий алгоритм – но только один.
В разных конкретных ситуациях относительно лучше работают разные эвристики. Требуется определённым образом принять решение о выборе конкретного элемента матрицы стоимостей для ветвления. Имеется информация, данная разными экспертами – разными эвристиками, т.н. «предикторами». При этом очень часто эксперты дают противоречивую информацию – и надо её каким-то образом «усреднять».
Пусть имеются несколько различных эвристик для выбора конкретной стратегии решения некоторой задачи дискретной оптимизации. При этом каждая из возможных стратегий имеет несколько различных экспертных оценок перспективности (т.е. имеется несколько независимых подпрограмм-экспертов, предикторов). Стратегию можно выбирать просто по максимальному значению среднего значения перспективности.
Пусть экспертные оценки перспективности изменяются в пределах отрезка [0,1]. Пусть для 1-й стратегии 1 эксперт дал оценку 1, и 35 экспертов – оценку 0.055. А для 2-й стратегии 2 эксперта дали оценку 0.95, а остальные 34 эксперта – оценку 0. Видимо, на основе этих данных практически любой пользователь (человек) выберет 2-ю стратегию. (Поскольку в 1-й стратегии имеется 1 «очень хороший» результат и 35 «очень плохих», а для 2-й стратегии – соответственно 2 «очень хороших» и 34 «очень плохих»; «средних» же результатов ни в одном из двух случаев нет.) Однако усреднение по простейшему алгоритму (т.е., просто среднее арифметическое экспертных оценок) даёт 0.081 в 1-м случае и 0.053 во 2-м – т.е., надо выбирать 1-ю стратегию?
Для 1-й стратегии функция риска имеет вид:
–0.685 x2 + 1.300 x + 0.386 ,
а для 2-й –
–0.694 x2 + 1.374 x + 0.321 .
Окончательные значения усреднения экспертных оценок с помощью этих функций риска составляют 0.111 в 1-м случае и 0.147 – во 2-м. То есть применение алгоритмов динамического построения функций риска и усреднения экспертных оценок с их помощью даёт «более естественные» результаты.
Как уже было сказано, и в завершённом, и в незавершённом алгоритмах метода ветвей и границ нам необходимо воспользоваться тем фактом, что в разных конкретных подзадачах одной и той же задачи оптимизации относительно лучше работают разные эвристики. Было кратко упомянуто об усреднении, которое делается с помощью набора коэффициентов.
Для усреднения результатов, возвращаемых различными предикторами, без набора коэффициентов обойтись невозможно. Эти коэффициенты каким-то образом подбираются для организации наилучшей работы метода ветвей и границ. Однако до сих пор не существует систем, в которых были бы решены вопросы автоматизированного выбора этих коэффициентов. Одним из способов который сможет в будущем решить эту проблему, является применения генетических алгоритмов. Более того, стоит специально отметить: предметом самообучения генетических алгоритмов, например при решении задачи коммивояжера, является не выбор маршрута для конкретной, одной, заданной задачи коммивояжера – а набор-геном коэффициентов для целого класса однотипных задач.
В качестве посылки для организации процесса вычисления оптимального набора-генома коэффициентов может быть принята следующая очевидная цель: создать алгоритм, зависящий от этих коэффициентов, при которых случайно сгенерированная матрица стоимостей была бы посчитана в среднем за наименьшее время. При этом указанный набор коэффициентов (геном) должен быть выбран за ограниченное время – имеющееся в распоряжении исследователя. Важно отметить, что такой выбор оптимального набора-генома коэффициентов производился только для старта некоторого вычислительного процесса, а в процессе работы алгоритма такие наборы коэффициентов модифицируются – т.е. выбираются в зависимости от текущей ситуации в самой задаче.
Однако у описываемого метода имеются следующие две проблемы. Во-первых, применение самообучения коэффициентов при работе такого сложного алгоритма, как метода ветвей и границ с несколькими эвристиками, вряд ли сможет быстро дать хорошие результаты: связь между набором коэффициентов и конкретным рассматриваемым вариантом некоторой задачи оптимизации, конечно же, существует, но вряд ли может быть быстро найдена. Во-вторых, сравнение двух наборов коэффициентов может быть хорошо произведено только при наличии системы тестов с заранее известными результатами; в реальных же условиях такие системы тестов имеются только для самой известной из рассматриваемых задач, а именно задачи коммивояжера.
Обе вышеупомянутые проблемы решаются в различных задачах дискретной оптимизации с помощью одного общего подхода. Этот подход был взят из игрового программирования, отсюда и его название – турнирное самообучение.
Суть подхода заключается в следующем. Из множества наборов-геномов коэффициентов, каждый из которых (наборов) представляет собой один из объектов самообучения, выбираются некоторые два – и между ними проводится т.н. «матч». Каждый матч заключается в том, что для каждого из нескольких случайно сгенерированных вариантов рассматриваемой задачи дискретной оптимизации применяется один и тот же упрощённый алгоритм её решения. Далее для двух вариантов одного и того же алгоритма с разными наборами-геномами коэффициентов (или, что то же самое – двух разных алгоритмов, «участников турнира набора коэффициентов») запоминается:
либо информация о том, на каком из наборов получено относительно лучшее решение,
либо отношение границ, полученных при применении описанных жадных алгоритмов
(возможны и некоторые другие варианты) – в зависимости от конкретного способа реализации алгоритма турнирного самообучения.
Из подобных «сыгранных матчей» формируется «турнир». Выбор худших наборов-геномов (объектов самообучения) для их последующей замены с помощью стандартных (и нестандартных) генетических операторов происходит именно на основе результатов турнира. При этом мы избавляемся от необходимости иметь систему тестов – т.е. набор конкретных задач рассматриваемой задачи дискретной оптимизации. Очень важно отметить, что при этом также нет необходимости применять некоторую конкретную случайно сгенерированную задачу дискретной оптимизации ко всем наборам коэффициентов.
Среди эвристик для конкретных задачи дискретной оптимизации, рассмотрим только одну – а именно, задачу вершинной минимизации недетерминированных конечных автоматов. Описываемые эвристики являются общими для турнирного самообучения и для выбора очередного шага в методе ветвей и границ.
Итак, из всего множества блоков таблицы соответствий некоторого регулярного языка нам необходимо выбрать некоторое подмножество, включающее в себя все имеющиеся (т.е. построенные в процессе канонизации прямого и зеркального автоматов) элементы #. Для такого выбора необходимо ответить на вопрос о включении некоторого конкретного блока в оптимальное подмножество (важно отметить, что это необходимо как для турнирного самообучения, так и для описания очередного шага метода ветвей и границ), и для ответа на этот вопрос мы будем использовать следующий эвристический алгоритм, формулируемый для матрицы элементов #.
Пусть рассматривается клетка матрицы таблицы соответствий состояний с координатами (i,j), пусть также R(i) – количество знаков # в строке i, а C(j) – количество знаков # в столбце j. Тогда:
Для каждой пары (i,j), содержащей #, посчитаем значение
F(i,j) = G(H(R(i)),H(C(j))), (1)
где G(x,y) и H(x) – некоторые функции. При выборе этих функций методами применения генетических алгоритмов относительно вида функции H(x) заранее ничего не известно. Про функцию G(x,y) известно лишь то, что она является возрастающей (т.к. чем больше соседей у ячейки, тем с большей вероятностью она должна войти в искомый блок), но не известно ничего о её выпуклости. G, вообще говоря, не обязана удовлетворять условию симметричности G(x,y)=G(y,x) – поскольку общее число строк и столбцов в рассматриваемой таблице соответствий может различаться. Отметим ещё, что если у ячейки нет соседей ни в строке, ни в столбце (т.е. R(i)=0 либо C(j)=0), то соответствующий ей блок обязательно должен войти в искомое множество покрывающих блоков. Итак, подбор параметров, необходимых для описания поведения этих функций, и есть объект самообучения.
При самообучении обычно использовался следующий конкретный вид функции H(x):
H(x)= e–(P1X) + P2N(x–1)–1 + P3 x + 1, (2)
где N – соответствующая размерность таблицы соответствий состояний. При самообучении игровых программ: при начале самообучения с функциями произвольного вида, т.е. функциями, не имеющими вид (2), результат работы генетических алгоритмов даёт функции вида, близкого к указанному. Однако вид (2) всё же был априори подобран эвристически.
Возможные графики функции (2) для двух различных вариантов значений параметров (а именно, для P1=2/N, P2=1, P3=1 и P1=4/N, P2=5/N, P3=0.01) изображены ниже:
Среди всех блоков выбираем такой (R,C), для которого т.н. итоговая рейтинговая сумма ∑F(Ri,Cj), гдеRiR и CjC, будет наибольшей. Ещё раз отметим, что функция F выбирается согласно (1), а функции G иH при этом получаются в результате самообучения методами генетического алгоритма. Поместим выбранный блок в итоговое множество.
Специальным образом пометим ячейки, принадлежащие выбранному на шаге 3 блоку, чтобы они не учитывались при вычислении F(Ri,Cj), но могли входить в любой вновь выбираемый блок. Итак, в будущем, т.е. при повторном выполнении шагов 1–3, эти ячейки уже не считается помеченными символом #.
Если остались еще ячейки, не вошедшие ни в один блок из итогового множества, то возвращаемся на этап 1. Заметим, что блоки, которым принадлежит хотя бы одна ячейка, не имеющая соседей по вертикали либо по горизонтали, будут обязательно включены в искомое множество, т.к., согласно виду функции F, их рейтинговая сумма равна бесконечности.
Полученное множество блоков считается искомым – и используется либо для проведения очередного шага турнирного самообучения (в простом случае), либо для проведения очередного шага метода ветвей и границ.
ANY-TIME алгоритм фаззификации физических величин на основе четких множеств
В существующих фаззификаторах [22, 70] из-за наложения друг на друга смежных термов приходится в каждом цикле сканирования отрабатывать весь алгоритм фаззификации независимо от текущего значения физической величины. Однако в дискретно-логических регуляторах (ДЛР) [53] вследствие равенства в любой момент времени логической единице только одного терма из множества термов, изображающих конкретную физическую величину, имеется возможность при каждом сканировании отрабатывать не весь алгоритм фаззификации, а только ту его часть, которая находится выше продукционного правила, условная часть которого в данный момент времени равна логической единице. Поэтому в ДЛР для уменьшения цикла фаззификации в начало базы фаззификации нужно располагать правила с наибольшей частотой срабатывания.
К сожалению, на этапе проектирования ДЛР определить достоверное значение частоты срабатывания упомянутых правил крайне сложно, что приводит к неоправданному увеличению цикла сканирования алгоритма фаззификации. Наиболее просто минимизировать время цикла фаззификации в НР с четкими термами можно с помощью ANY-TIME алгоритма [131, 132].
Концептуальную основу такого алгоритма составляет система продукционных правил, которая исключает неопределенность в идентификации четких значений физической величины в совокупность четких термов и предотвращает их наложение [55]. Не снижая общности рассуждений, составим упомянутую систему (3.26) для физической величины, преобразованной в совокупность четких термов, которая изображена на рисунке 2.1,а:
Если 0 р < р1, то (рТ1) & (Сч1 Сч1+1);
Если р1 р < р2, то (рТ2) & (Сч2 Сч2+1);
Если р2 р < р3, то (рТ3) & (Сч3 Сч3+1); (3.26)
……….
……….
……….
Если рn-1 р рn, то (рТn) & (Счn Счn +1).
Из системы (3.26) следует, что все обозначения в ней заимствованы из рисунка 2.1 и цепочка отрезков (0 – р1), (р2 – р3), …, (рn-1 – рn), покрывая без наложения всю универсальную числовую ось, преобразуется в термы Т1 – Тn соответственно физической величины «Параметр р». Причем в любой момент времени только один из указанных термов равен логической единице, что свидетельствует о строгой однозначности процесса фаззификации.
Система (3.26) отличается от типовых систем продукционных правил наличием в консеквентах продукций операторов присваивания (Сч1 Сч1+1) (Счn Счn +1), используемых для подсчета числа фактов истинности условной части (антецедента) правил (1n) соответственно. Такая информация необходима для перерасположения цепочки операторов (рТ1) (рТn),(0 р < р1) (рn-1 р рn) и (Сч1 Сч1+1) (Счn Счn +1) с помощью программного блока «Расположить цепочку операторов в порядке убывания их частоты исполнения» при срабатывании ветви «Да» оператора условного перехода Ттек Тзад. Здесь Ттек – текущее время работы фаззификатора, а Тзад– априорно заданное значение периода модификации структуры фаззификатора с целью уточнения порядка размещения цепочек операторов (рТ1) (рТn),(0 р < р1) (рn-1 р рn) и (Сч1 Сч1+1) (Счn Счn+1) в порядке убывания их частоты срабатывания.
Для более глубокого понимания особенностей преобразования четких значений физической величины в эквивалентную совокупность четких термов на рисунке 3.11 изображена логическая схема алгоритма, соответствующая системе (3.26). Основу схемы составляют n соединенных в цепочку операторов условного перехода, в ветви «Да» которых включены операторы присваивания и счетчики, фиксирующие число инициализаций этих ветвей.
Рассмотрим принцип действия алгоритма, изображенного на рисунке 3.11. В каждом цикле сканирования программно реализованных компонентов нечеткого регулятора инициируется поиск терма, соответствующего текущему четкому значению физической величины. С этой целью оператором условного перехода «0р<р1»определяется принадлежность текущего значения фаззифицируемой величины р отрезку (0 р1). Если р(0 р1), то по ветви «Да» управление передается оператору «рТ1», который текущее четкое
Рисунок 3.11 – Логическая схема ANY-TIME алгоритма фаззификации
с помощью четких термов
значение физической величины р преобразует (фаззифицирует) в терм Т1, а содержимое счетчика Сч1увеличивается на единицу. Если Ттек Тзад, то с помощью блока «Модификация структуры алгоритма» происходит перерасположение цепочки операторов (0 р < р1) (рn-1 р рn), (рТ1) (рТn) и (Сч1 Сч1+1) (Счn Счn +1) в теле программы фаззификатора в соответствии с частотой их исполнения. В противном случае цикл сканирования алгоритма фаззификации закончится без модификации структуры программы фаззификатора. При срабатывании выхода «Да» операторов «р1р<р2» «рn-1р рn», описанная процедура повторяется, но уже при участии других ветвей алгоритма фаззификации.
С точки зрения законов материального мира, в любой момент времени физическая величина имеет только одно значение, вследствие чего в любой момент времени только у одного из операторов (0 р < р1) (рn-1 р рn) выход «Да» имеет истинное значение. В случае некорректного задания диапазонов существования термов Т1 Тn, когдани одно из условий (0 р < р1) (рn-1 р рn) не выполняется, управление передается блоку «Аларм» для идентификации аварийной ситуации.
Блок «Модификация структуры алгоритма (МСА)» реализует процедуру ANY-TIME минимизации времени фаззификации НР. При выполнении условия Ттек Тзад блок МСА по информации, накопленной в счетчиках (Сч1 Сч1+1) (Счn Счn+1) переставляет цепочки операторов ((0 р < р1) - (рТ1) - (Сч1 Сч1+1) (рn-1 р рn),(рТn) и (Счn Счn+1) на рисунке 3.11 слева направо в порядке убывания их частоты использования. После этого счетчики обнуляются и начинается новый отсчет текущего времени Ттек. Тем самым на основе статистической информации, архивируемой в счетчиках Сч1 Счn, через каждый промежуток времени, равный Тзад, происходит перестановка упомянутых выше цепочек операторов с целью минимизации времени, необходимого для фаззификации.
Произведем количественную оценку снижения продолжительности фаззификации, обусловленной использованием ANY-TIME алгоритма. Пусть физическая величина «Параметр р» в результате фаззификации эквивалентно преобразовывается в n четких термов Т1 Тn. Введем следующие обозначения: nt – количество продукционных правил из системы (3.26), отработанных в текущем цикле сканирования алгоритма фаззификции; tу и tз – соответственно время отработки условной и заключительной частей одного продукционного правила; tм – время проверки условия Ттек Тзад.
С учетом принятых обозначений время цикла фаззификации можно выразить следующей формулой:
Тц=nttу+2tз+tм. (3.27)
В выражении (3.27) предполагается, что на исполнение операторов рТiи Счi Счi+1 процессор затрачивает одинаковое время.
При nt=1 из выражения (3.27) получается формула для минимального значения времени цикла:
Тmin=tу+2tз+tм. (3.28)
В этом случае в схеме на рисунке 3.11 последовательно отрабатываются операторы (0 р < р1) – (рТ1) – (Сч1 Сч1+1) – (Ттек Тзад), а в системе продукционных правил (3.26) отрабатывается только первое правило, условная часть которого равна логической единице.
Аналогично из (3.27) при nt=n максимальное время цикла фаззификации
Тmax=ntу+2tз+tм. (3.29)
Применительно к схеме на рисунке 3.11 выражение (3.29) соответствует ситуации, когда последовательно отрабатываются операторы (0 р < р1) – (р1 р < р2) – (р2 р < р,) ÷ (рn-1 р < рn) – (рТn) – (Счn Счn+1) – (Ттек Тзад), а в системе продукционных правил (3.26) условная часть только последнего продукционного правила равна логической единице.
Из (3.28) и (3.29) можно определить, на сколько короткий цикл сканирования меньше длинного
Т1,0= Тmax– Тmin=(n-1) tу (3.30)
Однако в типовых процедурах фаззификации, вырабатывающих четкие термы, даже с ANY-TIME алгоритмом в каждом цикле сканирования отрабатываются (1030)% продукционных правил, относящихся к процедуре фаззификации.
Семейство функций (3.27) Тц=f(nt) для четырех наиболее известных производителей программируемых контроллеров приведено на рисунке 3.12, из которого следует, что наибольшим быстродействием обладает контроллер фирмы YOKOGAWA, а наименьшим – Российский контроллер КР-500. На этом же рисунке указаны минимальные Тmin1÷ Тmin4 (nt=1) и максимальные Тmax1÷ Тmax4 значения циклов сканирования алгоритма фаззификации при nt=8.
Используя те же обозначения, что и в (3.27), получим выражение для цикла сканирования Ттфв типовом фаззификаторе, в котором, как известно [70], при каждом цикле сканирования безусловно, полностью и независимо от логического состояния антецедентов отрабатываются все продукционные правила. Отсюда
Ттф=n(tу+ tз). (3.31)
Рисунок 3.12 – Зависимость длительности цикла Тц сканирования алгоритма фаззификации то числа отработанных продукционных правил nt
Для упрощения выражения (3.31) принимаем tу=tз. Тогда выражение (3.31) принимает следующий вид:
Ттф=2ntу. (3.32)
В свою очередь, выражения (3.30) и (3.32) позволяют определить долю Т1,0 в цикле сканирования Ттф типового фаззификатора:
(3.33)
Как уже отмечалось, при эффективной работе ANY–TIME алгоритма в каждом цикле сканирования отрабатывается не одно, а (0,10,3)n подукционных правила. Поэтому практический интерес представляет получение выражений, аналогичных выражениям (2.11) и (2.14) при nt=0,1n; 0,2n и 0,3n.
Т0,9=(0.9n-1)tу; (3.34)
Т0,8=(0,8n-1)tу; (3.35)
Т0,7=(0,7n-1)tу; (3.36)
Графическое изображение функций (3.33)(3.36) представлено на рисунке 3.13,
Ряд 1 – , Ряд 2 – , Ряд 3 – , Ряд 4 – .
Рисунок 3.13 – Влияние ANY–TIME алгоритма на длительность сканирования алгоритма фаззификации
из которого следует, что наиболее интенсивное снижение времени цикла сканирования алгоритма фаззификации имеет место при малых значениях n. По мере увеличения n эффективность работы ANY–TIME алгоритма вначале снижается, а затем стабилизируется на определенном уровне. Например, из выражений (3.33 3.36) следует, что при n=10 длитедьность сканирования алгоритма фаззификации ДЛР уменьшается на (30 40)%. Оцифровка функций на рисунке 3.13 приведена в таблице 3.3.
Таблица 3.3 – В
В последние годы интенсивно разрабатывается научное направление NaturalComputing – «Природные вычисления», объединяющее математические методы, в которых заложены принципы природных механизмов принятия решения.
Имитация самоорганизации муравьиной колонии составляет основу муравьиных алгоритмов оптимизации – нового перспективного метода природных вычислений. Колония муравьев может рассматриваться как многоагентовая система, в которой каждый агент (муравей) функционирует автономно по очень простым правилам. В противовес почти примитивному поведению агентов, поведение всей системы получается на удивление разумным. Одним из подтверждений оптимального поведения муравьиной колонии является тот факт, что сеть гнезд суперколоний близка к минимальному остовному дереву графа их муравейника.
Идея муравьиного алгоритма – моделирование поведения муравьёв, связанного с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, находя новый кратчайший путь. При своём движении муравей метит путь феромоном, и эта информация используется другими муравьями для выбора пути. Это элементарное правило поведения и определяет способность муравьёв находить новый путь, если старый оказывается недоступным.
Рассмотрим случай, показанный на рисунке 1, когда на оптимальном доселе пути возникает преграда. В этом случае необходимо определение нового оптимального пути. Дойдя до преграды, муравьи с равной вероятностью будут обходить её справа и слева. То же самое будет происходить и на обратной стороне преграды. Однако, те муравьи, которые случайно выберут кратчайший путь, будут быстрее его проходить, и за несколько передвижений он будет более обогащён феромоном. Поскольку движение муравьёв определяется концентрацией феромона, то следующие будут предпочитать именно этот путь, продолжая обогащать его феромоном до тех пор, пока этот путь по какой-либо причине не станет недоступен.
Рисунок 1 – Выбор оптимального пути даижения к цели
Очевидная положительная обратная связь быстро приведёт к тому, что кратчайший путь станет единственным маршрутом движения большинства муравьёв. Моделирование испарения феромона – отрицательной обратной связи – гарантирует нам, что найденное локально оптимальное решение не будет единственным – муравьи будут искать и другие пути. Если мы моделируем процесс такого поведения на некотором графе, рёбра которого представляют собой возможные пути перемещения муравьёв, в течение определённого времени, то наиболее обогащённый феромоном путь по рёбрам этого графа и будет являться решением задачи, полученным с помощью муравьиного алгоритма.
Муравьиный алгоритм (англ. AntColonyOptimization, ACO) – один из эффективных полиномиальных алгоритмов для нахождения приближенных решений задач оптимизации. Подход предложен бельгийским исследователем Марко Дориго. Суть подхода заключается в анализе и использовании модели поведения муравьев, ищущих пути от колонии в пище.
В основе алгоритма лежит поведение муравьиной колонии – маркировка более удачных путей большим количеством феромона. Работы начинается с размещения муравьев в вершинах графа, затем начинается движение муравьев – направление определяется вероятностным методом:
P_i=(l_i^q×f_i^p)/(∑_(k=0)^N▒l_k^q ×f_k^p ),
где P_i - вероятность перехода по пути i, l_i - длина i-ого перехода, f_i - количество феромона на i-ом переходе, q – величина, определяющая «жадность» алгоритма, р – величина, определяющая стадность алгоритма и p + q = 1.
Решение не является точным и даже может быть одним из худших, однако, в силу вероятности решения, повторение алгоритма может выдавать (достаточно) точный результат.
Обобщенный вид алгоритма:
Любой муравьиный алгоритм, независимо от модификаций, представим в следующем виде
Пока (условия выхода не выполнены)
1. Создаём муравьёв
2. Ищем решения
3. Обновляем феромон
4. Дополнительные действия {опционально}
Теперь рассмотрим каждый шаг в цикле более подробно
1 Создаём муравьёв
Стартовая точка, куда помещается муравей, зависит от ограничений, накладываемых условиями задачи. Потому что для каждой задачи способ размещение муравьёв является определяющим. Либо все они помещаются в одну точку, либо в разные с повторениями, либо без повторений.
На этом же этапе задаётся начальный уровень феромона. Он инициализируется небольшим положительным числом для того, чтобы на начальном шаге вероятности перехода в следующую вершину не были нулевыми.
2Ищем решения
Вероятность перехода из вершины i в вершину j определяется по следующей формуле
P_ij (t)=(τ_ij 〖(t)〗^α 〖(1/d_ij )〗^β)/(∑_(j∈allowednodes)▒〖τ_ij 〖(t)〗^α 〖(1/d_ij )〗^β 〗),
где τ_ij (t)– уровень феромона, d_ij– эвристическое расстояние, а α, β – константные параметры.
При α = 0 выбор ближайшего города наиболее вероятен, то есть алгоритм становится жадным.
При β = 0 выбор происходит только на основании феромона, что приводит к субоптимальным решениям.
Поэтому необходим компромисс между этими величинами, который находится экспериментально.
3 Обновляем феромон
Уровень феромона обновляется в соответствии с приведённой формулой
τ_ij (t+1)=(1-p) τ_ij (t)+∑_█(k∈Colonythat@usededge (i,j))▒Q/L_k ,
Где p– интенсивность испарения, L_k (t)– цена текущего решения для k-ого муравья, а Q – параметр, имеющий значение порядка цены оптимального решения, то есть Q/(L_k (t)) – феромон, откладываемый k-ым муравьём, использующим ребро (i,j).
4 Дополнительные действия
Обычно здесь используется алгоритм локального поиска, однако он может также появиться и после поиска всех решений.
Для того чтобы построить подходящий муравьиный алгоритм для решения какой-либо задачи, нужно
1 Представить задачу в виде набора компонент и переходов или набором неориентированных взвешенных графов, на которых муравьи могут строить решения
2 Определить значение следа феромона
3 Определить эвристику поведения муравья, когда строим решение
4 Если возможно, то реализовать эффективный локальный поиск
5 Выбрать специфический ACO алгоритм и применить для решения задачи
6 Настроить параметр ACO алгоритма
Также определяющими являются
Количество муравьёв
Баланс между изучением и использованием
Сочетание с жадными эвристиками или локальным поиском
Момент, когда обновляется феромон
Самой распространенной задачей, на примере которой показывается действие муравьиных алгоритмов, это задача коммивояжёра (бродячий торговец). Рассмотрим пример ее решения.
Задача формулируется как задача поиска минимального по стоимости замкнутого маршрута по всем вершинам без повторений на полном взвешенном графе с n вершинами. Содержательно вершины графа являются городами, которые должен посетить коммивояжёр, а веса рёбер отражают расстояния (длины) или стоимости проезда. Эта задача является NP-трудной, и точный переборный алгоритм её решения имеет факториальную сложность.
В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество алгоритмов, время работы которых существенно зависит от размера входных данных; в то же время, если предоставить алгоритму некоторые дополнительные сведения (так называемых свидетелей решения), то он сможет достаточно быстро (за время, не превосходящее многочлена от размера данных) решить задачу.
Моделирование поведения муравьёв связано с распределением феромона на тропе – ребре графа в задаче коммивояжёра. При этом вероятность включения ребра в маршрут отдельного муравья пропорциональна количеству феромона на этом ребре, а количество откладываемого феромона пропорционально длине маршрута. Чем короче маршрут, тем больше феромона будет отложено на его рёбрах, следовательно, большее количество муравьёв будет включать его в синтез собственных маршрутов. Моделирование такого подхода, использующего только положительную обратную связь, приводит к преждевременной сходимости – большинство муравьёв двигается по локально оптимальному маршруту. Избежать этого можно, моделируя отрицательную обратную связь в виде испарения феромона. При этом если феромон испаряется быстро, то это приводит к потере памяти колонии и забыванию хороших решений, с другой стороны, большое время испарения может привести к получению устойчивого локального оптимального решения.
Теперь с учётом особенностей задачи коммивояжёра, мы можем описать локальные правила поведения муравьёв при выборе пути.
1 Муравьи имеют собственную «память». Поскольку каждый город может быть посещён только один раз, то у каждого муравья есть список уже посещённых городов – список запретов. Обозначим через J_(i,k) список городов, которые необходимо посетить муравью k, находящемуся в городе i.
2 Муравьи обладают «зрением» – видимость есть эвристическое желание посетить город j, если муравей находится в городе i. Будем считать, что видимость обратно пропорциональна расстоянию между городами η_ij=1/D_ij .
3 Муравьи обладают «обонянием» – они могут улавливать след феромона, подтверждающий желание посетить город j из города i на основании опыта других муравьёв. Количество феромона на ребре (i,j) в момент времени t обозначим через τ_ij (t).
4 На этом основании мы можем сформулировать вероятностно-пропорциональное правило, определяющее вероятность перехода k-ого муравья из города i в город j:
{█(P_(ij,k) (t)=([τ_ij (t)]^α×[η_ij ]^β)/(∑_(l∈J_(i,k))▒〖[τ_il (t)]^α×[η_il ]^β 〗),j∈J_(i,k);@P_(ij,k) (t)=0,j∈J_(i,k);)┤ (1)
Где α, β – параметры, задающие веса следа феромона. При α = 0 алгоритм вырождается до жадного алгоритма (будет выбран ближайший город). Заметим, что выбор города является вероятностным, правило (1) лишь определяет ширину зоны города j; в общую зону всех городов бросается случайное число, которое и определяет выбор муравья. Правило (1) не изменяется в ходе алгоритма, но у двух разных муравьёв значение вероятности перехода будут отличаться, т.к. они имеют разный список разрешённых городов.
5 Пройдя ребро (i,j), муравей откладывает на нём некоторое количество феромона, которое должно быть связано с оптимальностью сделанного выбора. Пусть T_k (t) есть маршрут, пройденный муравьём k к моменту времени t, L_k (t) – длина этого маршрута, а Q – параметр, имеющий значение порядка длины оптимального пути. Тогда откладываемое количество феромона может быть задано в виде
∆τ_(ij,k) (t)={█(Q/(L_k (t) ),(i,j)∈T_k (t);@0,(i,j)∉T_k (t);)┤
Правила внешней среды определяют, в первую очередь, испарение феромона. Пусть p∈[0,1] есть коэффициент испарения, тогда правило испарения имеет вид
τ_ij (t+1)=(1-p)×τ_ij (t)+∆τ_ij (t);∆τ_ij (t)=∑_(k=1)^m▒〖∆τ_(ij,k) (t) 〗, (2)
В начале алгоритма количества феромона на рёбрах принимается равным небольшому положительному числу. Общее количество муравьёв остаётся постоянным и равным количеству городов, каждый муравей начинает маршрут из своего города.
Дополнительная модификация алгоритма может состоять в ведении так называемых «элитных» муравьёв, которые усиливают рёбра наилучшего маршрута, найденного с начала работы алгоритма. Обозначим через T* наилучший текущий маршрут, через L* – его длину. Тогда если в колонии есть e элитных муравьёв, то рёбра маршрута получат дополнительное количество феромона
∆τ_e=e×Q/L^* (3)
Алгоритм для решения данной задачи имеет вид:
1 Ввод матрицы расстояний D
2 Инициализация параметров алгоритма – α, β, e, Q
3 Инициализация рёбер – присвоение видимости η_ij и начальной концентрации феромона
4 Размещение муравьёв в случайно выбранные города без совпадений
5 Выбор начального кратчайшего маршрута и определение L*
//Основной цикл
6 Цикл по времени жизни колонии t=1, t_max
7 Цикл по всем муравьям k=1,m
8 Построить маршрут T_k (t) по правилу (1) и рассчитать длину L_k (t)
9 Конец цикла по муравьям
10 Проверка всех L_k (t) на лучшее решение по сравнению с L*
11 В случае если решение L_k (t) лучше, обновить L* и T*
12 Цикл по всем рёбрам графа
13 Обновить следы феромона на ребре по правилам (2) и (3)
14 конец цикла по рёбрам
15 конец цикла по времени
16 Вывести кратчайший маршрут T* и его длину L*
Сложность данного алгоритма, как несложно заметить, зависит от времени жизни колонии t_max, количества городов n и количества муравьёв в колонии m.
Области применения и возможные модификации
Поскольку в основе муравьиного алгоритма лежит моделирование передвижения муравьёв по некоторым путям, то такой подход может стать эффективным способом поиска рациональных решений для задач оптимизации, допускающих графовую интерпретацию. Ряд экспериментов показывает, что эффективность муравьиных алгоритмов растёт с ростом размерности решаемых задач оптимизации. Хорошие результаты получаются для нестационарных систем с изменяемыми во времени параметрами, например, для расчётов телекоммуникационных и компьютерных сетей. В Интернете можно найти описание применения муравьиного алгоритма для разработки оптимальной структуры съёмочных сетей GPS в рамках создания высокоточных геодезических и съёмочных технологий. В настоящее время на основе применения муравьиных алгоритмов получены хорошие результаты для таких сложных оптимизационных задач, как задача коммивояжёра, транспортная задача, задача календарного планирования, задача раскраски графа, квадратичная задача о назначениях, задача оптимизации сетевых трафиков и ряд других.
Качество получаемых решений во многом зависит от настроечных параметров в вероятностно-пропорциональном правиле выбора пути на основе текущего количества феромона и от параметров правил откладывания и испарения феромона. Возможно, что динамическая адаптационная настройка этих параметров может способствовать получению лучших решений. Немаловажную роль играет и начальное распределение феромона, а также выбор условно оптимального решения на шаге инициализации.
Перспективными путями улучшения муравьиных алгоритмов являются различные адаптации параметров с использованием базы нечётких правил и их гибридизация, например, с генетическими алгоритмами. Как вариант, такая гибридизация может состоять в обмене через определённые промежутки времени текущими наилучшими решениями.
В заключение отметим достоинства и недостатки муравьиных алгоритмов:
Достоинства:
1 Для TSP (Traveling Salesman Problem – задача коммивояжёра) сравнительно эффективны
Для небольшого количества узлов TSP может быть решена полным перебором
Для большого количества узлов TSP вычислительно сложна (NP-трудная) – экспоненциальное время сходимости
2 Работают лучше, чем другие глобальные оптимизации для TSP (нейронные сети, генетические алгоритмы)
3 Сравнение с GAs (GeneticAlgorithms – генетические алгоритмы):
Опираются на память обо всей колонии вместо памяти только о предыдущем поколении
Меньше подвержены неоптимальным начальным решениям (из-за случайного выбора пути и памяти колонии)
4 Могут использоваться в динамических приложениях (адаптируются к изменениям, скажем, расстояний)
5 Применялись к множеству различных задач
Маршрутизация
Маршрутизация сети
Планирование
Многое другое
Недостатки:
1 Теоретический анализ затруднён:
В результате последовательности случайных (не независимых) решений
Распределение вероятностей меняется при итерациях
Исследование больше экспериментальное, нежели теоретическое
2Сходимость гарантируется, но время сходимости не определено
3 Обычно необходимо применение дополнительных методов таких, как локальный поиск
4 Сильно зависят от настроечных параметров, которые подбираются только исходя из экспериментов
Гибридные экспертные системы проектирования ресурсосберегающих установок первичной нефтепереработки.
Важнейшими критериями, определяющими эффективность нефтеперерабатывающих и нефтехимических производств, являются показатели ресурсосбережения, и особенно энергосбережения, так как стоимость энергии постоянно возрастает. Необходимость разработки и реализации новых энергосберегающих технологий связана прежде всего с неиспользуемыми вторичными энергоресурсами (ВЭР) нефтеперерабатывающих производств. В энергетическом балансе НПЗ на долю прямого топлива приходится 43–45%, на тепловую энергию – 40–42%, на электрическую – 13–15%. Полезное использование энергии составляет лишь 30–40%. Энергия теряется с охлаждающей водой, с дымовыми газами и за счет теплообмена с окружающей средой горячих поверхностей оборудования. Поэтому основным направлением решения проблемы энергосбережения при проектировании НПЗ является максимальное использование ВЭР благодаря созданию оптимальных теплообменных систем (ТС) и систем рекуперации высоко- и низкопотенциального тепла.
Важную роль в разработке проектов НПЗ играет выбор их технологической схемы, разработка которой требует выявления всех возможных вариантов получения необходимого количества товарных нефтепродуктов с требуемыми показателями качества при ограниченном использовании сырьевых ресурсов и наименьших капитальных и эксплуатационных затратах [1]. Так как свойства нефтяного сырья, поступающего на переработку, меняются в зависимости от состава сырья, то важным является выбор типа схемы переработки нефти применительно к конкретному виду сырья и производимым целевым продуктам, а также возможность использования данной схемы при изменении состава сырья.
Одним из способов успешного решения указанных проблем является создание систем автоматизированного проектирования (САПР) и специальных экспертных систем (ЭС), которые на основе соответствующего математического и программно-информационного обеспечения позволяют aвтоматизированно принимать оптимальные решения по многим вопросам проектирования.
Разработка моделей представления знаний
Экспертные системы способны в интеллектуальном диалоге с непрограммирующим пользователем на основе накопления и переработки специальных знаний и правил принятия решений проводить экспертизу, консультировать и давать рекомендации по выбору действий (операций), распознавать ситуации, ставить диагноз и обосновывать заключения при поиске решений неформализованных задач некоторой проблемной области [2, 3].
Каждая неформализованная задача имеет семантическое или смысловое решение, представляющее собой словесное описание или графическое изображение некоторого явления, принципиальной технологической схемы или конструкции объекта. Поиск решения неформализованной задачи осуществляется путем переработки разнообразных знаний с помощью символьных рассуждений, основанных на использовании либо стратегии здравого смысла и эвристических правил, либо логического вывода.
Задача проектирования энергосберегающих установок первичной нефтепереработки как неформализованная задача химической технологии формулируется следующим образом: при заданных составах и свойствах потоков нефтяного сырья, названиях и показателях качества целевых продуктов, различных видах химико-технологических процессов (ХТП) нефтепереработки и типах инженерно-аппаратурного оформления ХТП требуется определить виды ХТП и типы инженерно-аппаратурного оформления ХТП, структуру, покомпонентный состав и фазовое состояние технологических потоков между аппаратами технологической схемы, оптимальные технологические параметры потоков, обеспечивающие максимум рекуперируемой энергии и минимум приведенных затрат на функционирование установки.
Разработка рациональных семантических решений задачи синтеза энергосберегающих НПЗ базируется на применении следующих основных физико-химических и технологических способов ресурсосбережения: способа наилучшего использования движущей силы ХТП, способа наиболее полной переработки сырья, способа рационального использования топливно-энергетических ресурсов, способа наилучшего функционально-структурного использования аппаратов и машин. Для поиска семантического решения используются декомпозиционные принципы синтеза ресурсосберегающих химико-технологических систем (ХТС), различные эвристическо-вычислительные процедуры автоматизированного синтеза ХТС, а также гибридные ЭС.
Основным интеллектуальным компонентом гибридной ЭС является база знаний, в которой представлены как результаты теоретических исследований, так и практические знания экспертов. База знаний состоит из базы данных, базы правил и базы процедур. Для программной реализации знаний предложено использовать продукционно-фреймовые модели [2]. При этом все декларативные и процедурные знания подразделяются на три класса: предметные знания, управляющие и метазнания. Предметные знания отображаются в виде фреймов, а управляющие знания, необходимые для поиска и генерации семантического решения неформализованной задачи, и метазнания отображаются в виде продукционных правил.
Для классификации знаний предметной области “Проектирование энергосберегающих установок первичной нефтепереработки” был проведен концептуальный анализ знаний о влиянии свойств нефтяного сырья на тип технологической схемы первичной нефтепереработки и об особенностях технологии первичной нефтепереработки, в результате которого выделены ключевые понятия и отношения между понятиями, необходимые для разработки процедуры поиска оптимального решения задачи.
Предметные знания соответствуют декларативным знаниям. К ним относятся: основные понятия (объекты) – нефтяное сырье, нефтепродукт, термодинамическое равновесие, фазовое равновесие, технологический поток, аппараты (колонна ректификации, теплообменник, печь и др.); операции – массопередача, теплообмен, конденсация, испарение, синтез целевых продуктов и др.; ситуации – подготовка сырья, разделение многокомпонентной смеси, нагревание технологического потока и др.
Управляющие знания соответствуют процедурным знаниям в области химической технологии и технологии переработки нефти. К управляющим знаниям относятся: законы равновесия, законы сохранения массы и энергии; законы термодинамики; физико-химические и технологические принципы наилучшего использования движущей силы ХТП, наиболее полного использования сырья и энергии в ХТС, наилучшего использования оборудования и др.; алгоритмы расчета состава смесей веществ, расчета массы и объемов веществ; системы уравнений математических моделей ХТП и ХТС и др.
В результате анализа знаний о проектировании энергосберегающих НПЗ можно сделать следующие выводы:
1) физико-химические свойства нефтяного сырья и нефтепродуктов являются основой выбора технологической схемы переработки нефти;
2) вариант технологической схемы переработки выбирается для определенного направления переработки нефти;
Рис. 1. Структура фрейма-прототипа “Нефтяное сырье”
3) каждый вид нефти характеризуется выходом узких и широких фракций, потенциалами отдельных топливных дистиллятов, показателями качества;
4) ХТП и продукты связаны друг с другом определенными закономерностями (между отбором топливных дистиллятов из нефти и широких фракций – продуктов вторичной нефтепереработки, качеством сырья, выходом и качеством конечных продуктов, технологическими параметрами ХТП, значениями выходов и показателями качества конечных продуктов и т.д.).
Продукционные правила имеют вид: “ЕСЛИ (условие) – ТО (действие)”. Условие представляет собой предложение, связывающее объекты с некоторыми конкретными их свойствами или значениями с помощью знака “равно”: “=”. В условную часть продукционного правила может входить несколько выражений, объединенных союзом “и”. В действии правила указывается заключение или операция, которые должны выполняться, если условие удовлетворено. В результате анализа предметной области выделены следующие классы продукционных правил: правила выбора технологической схемы первичной нефтепереработки; правила выбора вида уравнений расчета плотности нефти, дистиллятов и остатков; правила выбора вида уравнений расчета выхода легких фракций и базовых масел; правила выбора вида уравнений расчета параметров физико–химических свойств нефтяных фракций и параметров равновесия сложных смесей в зависимости от состава, плотности, температуры и давления смеси; правила выбора способов рекуперации ВЭР; правила выбора пар технологических потоков для участия в рекуперативном теплообмене и правила выбора последовательности выделения продуктов из многокомпонентной смеси.
Для моделирования и переработки знаний предметной области нами разработаны фреймы-прототипы и фреймы-примеры. Фреймы-прототипы отображают абстрактные понятия для класса сущностей или явлений, представляющих общие понятия предметной области. Фреймы-примеры отображают знания о конкретных сущностях и явлениях (объектах, ситуациях и т.д.) и используются для постановки исходной задачи, а также для генерации семантических решений. При преобразовании фрейма-прототипа во фрейм-пример каждой характеристике фрейма-прототипа присваивается конкретное значение. На рисунке 1 приведена структура фрейма-прототипа “Нефтяное сырье”.
Общая стратегия вывода семантических решений задачи проектирования энергосберегающих установок с использованием продукционных правил определяет тип процедуры управления выводом, тип процедуры проведения рассуждений при выводе, тип процедуры разрешения конфликтов или противоречий продукционных правил.
Описание процедуры вывода решений
Процедура вывода оптимальных решений при проектировании включает следующие этапы.
1. Ввод исходных знаний и данных о виде нефтяного сырья, которое может перерабатываться на проектируемой установке.
2. Расчет физико-химических свойств потоков нефтяного сырья и фракций с использованием уравнений, выбранных на основе продукционных правил, и с применением вычислительных алгоритмов, включенных в состав обеспечения ЭС.
3. Выбор типа технологической схемы установки первичной нефтепереработки и выбор инженерно-аппаратурного оформления установки с использованием продукционных правил.
4. Составление и расчет системы уравнений материальных и тепловых балансов для выбранной на этапе 3 технологической схемы.
5. Сравнение эффективности альтернативных технологических схем.
Стратегия вывода оптимального решения в данной процедуре осуществляется в обратном направлении, от “цели к данным”, то есть целевое состояние задачи используется как исходное при поиске семантического решения. Базовой стратегией при генерации альтернативных вариантов технологических схем является стратегия “поиска в глубину” на дереве вариантов решений [3]. Эта стратегия реализуется следующим образом. Сначала выбираются все продукционные правила, в заключение которых устанавливается какой-либо тип установки первичной нефтепереработки (или другое целевое состояние). Затем проверяется каждая часть предпосылки этого правила, и программа строит обратную цепочку для проверки фактов каждой предпосылки. В ходе поиска решения строится “и/или” дерево, называемое деревом целей. Каждая вершина этого дерева соответствует некоторой цели.
Операция обратного вывода позволяет отыскивать путь на данном дереве, то есть для подтверждения одной из всех связей “или”, которые соответствуют данной цели, выбирается одна, и делается попытка подтвердить все вершины, являющиеся предусловиями этой цели. В случае неудачи выбирается следующая связка “или”, и повторяется аналогичная процедура. Если хотя бы одна из связок “или” позволяет вывести последнюю цель, то доказательство этой цели является успешным.
Архитектура гибридной экспертной системы и ее использование
Рис. 2. Архитектура гибридной экспертной системы
Архитектура гибридной ЭС, показанная на рисунке 2, образована совокупностью трех функциональных блоков, реализованных в виде программных комплексов: базы знаний, блока вывода решения, предназначенного для генерации семантического решения с применением продукционных правил, и интерфейса пользователя. Программная реализация гибридной ЭС осуществлена на языке программирования Турбо-Паскаль. База знаний программно реализует декларативные и процедурные знания. При разработке логической структуры базы знаний применена методология создания расширенной реляционной модели.
Блок вывода решений, или машина вывода, реализует механизм обратного вывода “от цели к данным” и подсистему объяснения, показывающую, как было сгенерировано конкретное семантическое (смысловое) решение. Блок вывода решения имеет на входе полученное в результате диалога с пользователем описание исходных знаний и данных для поиска решения. В результате анализа знаний гибридная ЭС генерирует набор семантических решений, представляющих собой описание технологических схем первичной нефтепереработки, которые далее передаются в блок цифрового моделирования для выбора оптимальной технологической схемы.
При функционировании гибридной ЭС пользователь решает следующие задачи: выбирает тип технологической схемы первичной нефтепереработки; определяет направления использования ВЭР; выбирает номенклатуру продукции, вырабатываемой из сырья заданного состава. Взаимодействие пользователя с ЭС осуществляется в форме диалога, общая процедура которого включает этапы: инструктаж о режимах работы ЭС, постановку задачи, поиск решения задачи, выдачу результата – семантического решения задачи, объяснение всех операций вывода решения.
На этапе инструктажа ЭС объясняет пользователю свое назначение и режимы функционирования, определяет порядок ведения диалога и перечисляет средства, доступные пользователю. Этап постановки задачи состоит в сборе основной информации, необходимой для начала поиска. У пользователя запрашивается информация о виде нефтяного сырья, поступающего на переработку, а также цель использования ЭС. На этом этапе осуществляется структуризация исходной неформализованной задачи и распределение подзадач между пользователем и системой, то есть указывается, какие подзадачи решает сама ЭС и при решении каких задач ЭС обращается за помощью к пользователю.
Объяснительные способности ЭС реализуются в виде двух программных модулей. Первый модуль позволяет ЭС “объяснить” ход своих рассуждений путем вывода на экран цепочки продукционных правил, которыми она воспользовалась для получения конкретного заключения. Второй модуль позволяет ЭС отвечать пользователю, почему должен быть задан тот или иной вопрос.
Используя меню, пользователь имеет возможность добавить факт в базу знаний, просмотреть факты базы знаний, добавить новые продукционные правила.
Разработанная гибридная ЭС была использована при выборе установки первичной переработки уренгойской нефти, а также для синтеза ТС подогрева сырья этой установки с целью повышения показателей энергосбережения. Для первичной переработки нефти на основании правил из базы знаний была выбрана атмосферно-вакуумная установка с двукратным испарением, схема которой приведена на рисунке 3.
В результате анализа ТС, входящей в предложенную технологическую схему, с использованием продукционных правил была синтезирована ТС подогрева сырья на данной установке и разработаны рекомендации по ее реконструкции с целью повышения степени рекуперации теплоты за счет рационального перераспределения обменивающихся теплом потоков. С использованием блока цифрового моделирования были определены параметры состояния технологических потоков и степень рекуперации теплоты, которая составила 0.93.
Рис. 3. Схема установки АВТ:
1 - теплообменная система; 2 - электродегидраторы; 3 - отбензинивающая колонна; 4 - система атмосферной и вакуумной перегонки нефти; I - сырая нефть; II - обессоленная нефть; III - отбензиненная нефть; IV - нефтепродукты на переработку; V, VI, VII, VIII - нефтепродукты, циркуляционное орошение
3.Anytime алгоритмы: сущность, область применения, достоинства и недостатки.
В промышленных системах поддержки принятия решений, как правило, используются продукционные системы, для которых процесс принятия решения можно отобразить посредством дерева решений, вершины которого соответствуют состояниям (корневой вершине соответствует начальное состояние), а ребра – правилам преобразований. Специфика плохоформализуемых и слабоструктурированных задач принятия решений – их комбинаторность, т.е. лавинообразный рост решающих деревьев в процессе поиска, что не позволяет использовать для решения таких задач строгие алгоритмические методы и модели теории принятия решений.
Однако существует класс алгоритмов, которые способны прерываться в любой требуемый момент времени, возвращая лучший найденный на текущий момент результат и некоторую величину, характеризующую качество этого результата. Другой чертой этого класса алгоритмов является их способность оценивать качество результата на основе времени выполнения вычислений. Такие алгоритмы называются anytime-алгоритмами (постепенно приближающие псевдо-оптимальные алгоритмы реального времени), т.е. алгоритмов реального времени, которые в каждый определённый момент работы имеют лучшее (на данный момент) решение, при этом пользователь может просматривать эти псевдо-оптимальные решения в режиме реального времени, а последовательность таких решений в пределе даёт оптимальное решение.
Anytime-алгоритмы чрезвычайно важны в разработке искусственного интеллекта по двум причинам. Первая заключается в том, что хотя многие алгоритмы искусственного интеллекта могут искать точное решение задачи в течение долгого времени, зачастую достаточно хорошее неточное, приближенное решение может быть найдено за значительно более короткое время. Если бы было возможно определить, сколько времени необходимо для того, чтобы получить адекватный результат, многие интеллектуальные системы можно было бы сделать более адаптированными к сложной и изменяющейся окружающей среде. Вторая причина – технические приемы anytime-алгоритмов можно применять не только для одного вычислителя, но и в мультиагентных и параллельных системах.
Большинство из Anytime-алгоритмов можно представить в следующем виде:
AA = , где
f(r) – функция итерационного улучшения результата r. Функция многократно выполняется над текущим результатом r. Качество результата улучшается с каждой новой итерацией;
Q(r) – функция качества полученного результата. Функция Q(r) возвращает информацию о качестве текущего результата r. Anytime-алгоритмы возвращают помимо основного результата также и некоторые его характеристики (меры);
PP(Q,t) – профиль производительности. Функция ожидаемого качества решения от времени его поиска. Это самый важный компонент Anytime-алгоритма.
Алгоритмы планирования могут использовать эту оценку для определения наиболее эффективного количества времени, необходимого для выделения алгоритму.
Материал данной лекции формулирует метод построения anytime-алгоритмов для целого класса задач. Сначала, перед описанием применяемых методов принятия решений, перечислим сами рассматриваемые задачи, точнее – классы рассматриваемых задач.
Во-первых, классическая задача коммивояжёра. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Вообще, задаче коммивояжёра на протяжении последних десятилетий было посвящено очень много публикаций, но, конечно, проблемы остаются: какого-либо «универсального» метода решения задачи коммивояжёра просто не может существовать. В последние несколько лет авторы работ по эвристическим методам решения задачи коммивояжёра чаще других рассматривают так называемые симметричные – т.е. когда симметричной относительно главной диагонали является матрица стоимостей – и особенно их частные случаи, т.н. метрические задачи коммивояжёра. При этом для их решения чаще всего применяются фактическое сведéние работы с матрицей задачи коммивояжёра к работе с координатами городов. Однако, классический метод ветвей и границ может также с успехом применяться – для получения не только точного решения задачи коммивояжёра, но и различных эвристических; при этом сведéние задачи к работе с координатами городов не используется.
Во-вторых, несколько связанных между собой задач минимизации недетерминированных конечных автоматов (альтернативные названия – конечные автоматы-распознаватели, автоматы Рабина-Скотта). Наиболее важной из них, по-видимому, является задача вершинной минимизации – задача построения недетерминированных конечных автоматов, допускающего заданный регулярный язык и имеющего минимально возможное число вершин. С момента выхода книги в описании точных алгоритмов мало что изменилось: все описанные в литературе алгоритмы являются экспоненциальными – относительно числа состояний имеющегося автомата. Последнее обстоятельство связано с тем, что все имеющиеся алгоритмы требуют построения эквивалентного канонического конечного автомата – или какой-либо аналогичной графоподобной структуры.
Общим во всех описанных задачах являются следующие обстоятельства. Каждая из задач может быть просто решена для небольших размерностей (например – для матриц небольших размерностей в задачи коммивояжёра и в задаче вершинной минимизации конечных автоматов), но при переходе к большим размерностям (30 состояний в задаче вершинной минимизации конечного автомата, 70 городов в случайной задачи коммивояжёра) данные задачи в реальное время невозможно точно решить даже с помощью метода ветвей и границ и других эвристик.
Описываемые в лекции методы решения данных задач строятся на основе комбинации эвристик, взятых из нескольких различных областей теории искусственного интеллекта.
Во-первых, используется незавершённый метод ветвей и границ.
Во-вторых, для выбора очередного шага этого метода при наличии нескольких эвристик применяются динамические функции риска.
В-третьих, одновременно с функциями риска для подбора коэффициентов усреднения различных эвристик применяются генетические алгоритмы.
В-четвёртых, упрощённое самообучение теми же генетическими методами применяется и для старта незавершённого метода ветвей и границ. Таким образом, можно сказать, что данные комбинации эвристик представляют собой специальный поход к построению anytime-алгоритмов для задач дискретной оптимизации.
Незавершённый метод ветвей и границ
Метод ветвей и границ будем описывать для произвольной задачи дискретной оптимизации, однако, где это необходимо, будем приводить примеры метода ветвей и границ для самой известной из рассматриваемой нами задач – задачи коммивояжера. При этом будем употреблять следующие названия:
«случайная задача коммивояжера» – когда все элементы матрицы задачи коммивояжера генерируются как случайная величина с заданным законом равномерного распределения;
«метрическая задача коммивояжера» – когда случайно генерируются координаты всех городов как точек единичного квадрата (с равномерным распределением обеих координат), а элементы матрицы задачи коммивояжера суть расстояния между соответствующими точками. При этом очевидно выполнение следующего дополнительного условия, условия симметричности матрицы относительно главной диагонали: aij=ajiдля всех возможных i и j.
В последние годы наиболее часто встречаются публикации, посвящённые метрической задачи коммивояжера. Это объясняется, в первую очередь, тем обстоятельством, что один шаг алгоритма метода ветвей и границ «в среднем» упрощает матрицу случайной задачи коммивояжера значительно больше, чем матрицу метрической задачи коммивояжера.
Будем далее называть правой задачей очередного шага метода ветвей и границ задачу, полученную при уменьшении размерности. Например, в задаче коммивояжера таковой является та подзадача, в которой мы обязательно включаем в выбираемый маршрут дугу между двумя рассматриваемыми городами, а в задаче вершинной минимизации недетерминированных конечных автоматов – подзадача, когда мы обязательно включаем рассматриваемый блок в выбираемое множество блоков. Другую альтернативу – т.е. когда принимается временное решение об отсутствии некоторого элемента в оптимальном решении (например, когда в задаче коммивояжера мы обязательно не включаем в выбираемый маршрут дугу между двумя выбранными городами) – назовём, соответственно, левой задачей очередного шага метода ветвей и границ. Смысл всех модификаций метода ветвей и границ состоит в том, что с помощью некоторых эвристик мы добиваемся того, чтобы вероятность наличия оптимального решения была больше для правой задачи, чем для левой – ведь размерность правой задачи на 1 меньше, чем левой.
Несложная эвристика, преобразующая завершённый метод ветвей и границ в незавершённый (а именно на основе незавершённого метода и формируются все anytime-алгоритмы в лекции), заключается в следующем: каждый раз при получении очередной правой задачи (назовём её задачей T) мы фактически строим последовательность правых задач– т.е. саму задачу T, правую задачу задачи T, правую задачу правой задачи задачи T, и так далее. Естественно, каждый раз строятся (и включаются в список задач для потенциального решения в последующем) и соответствующие левые задачи – левая задача задачи T, левая задача правой задачи задачи T, и так далее. Описанный процесс заканчивается:
либо при получении тривиальной задачи (задачи нулевой размерности) – в этом случае мы запоминаем её решение (границу, получаемый к моменту её постановки тур, и т.п. характеристики) в качестве текущего на данный момент времени псевдо-оптимального решения нашего anytime-алгоритма;
либо при получении в какой-либо задаче достаточно большой границы – например, большей, чем имеющееся на данный момент времени псевдо-оптимальное решение.
Отметим, что на практике описанный процесс построения ППЗ не занимает много лишнего времени и не приводит к большому увеличению списка задач, предназначенных для потенциального решения в будущем.
Итак, был описан простой процесс построения anytime-алгоритма на основе некоторого конкретного варианта метода ветвей и границ. Важно отметить, что данный процесс возможен именно потому, что любая правая задача имеет размерность меньше, чем соответствующая ей левая.
Как уже было отмечены выше, кроме эвристики, формулирующей сам метод ветвей и границ, всегда необходима ещё одна эвристика. А именно – эвристика для выбора элемента, «разделяющего» рассматриваемую задачу на левую и правую подзадачи.
Однако некоторый эвристический разделяющий алгоритм может быть заменён на какой-либо другой; более того, очень часто при решении некоторой задачи дискретной оптимизации с помощью метода ветвей и границ желательно выбирать один из нескольких разделяющих алгоритмов – в зависимости от того, какая именно подзадача решается. Разные варианты разделяющих алгоритмов могут быть выбраны в зависимости от размерности решаемой задачи, от её границы, а также от многих других характеристик, связанных с конкретными задачами оптимизации.
В рассматривавшемся нами примере описания метода ветвей и границ для задачи коммивояжера используется хороший (т.е. дающий хорошие результаты по сравнению с другими) разделяющий алгоритм – но только один.
В разных конкретных ситуациях относительно лучше работают разные эвристики. Требуется определённым образом принять решение о выборе конкретного элемента матрицы стоимостей для ветвления. Имеется информация, данная разными экспертами – разными эвристиками, т.н. «предикторами». При этом очень часто эксперты дают противоречивую информацию – и надо её каким-то образом «усреднять».
Пусть имеются несколько различных эвристик для выбора конкретной стратегии решения некоторой задачи дискретной оптимизации. При этом каждая из возможных стратегий имеет несколько различных экспертных оценок перспективности (т.е. имеется несколько независимых подпрограмм-экспертов, предикторов). Стратегию можно выбирать просто по максимальному значению среднего значения перспективности.
Пусть экспертные оценки перспективности изменяются в пределах отрезка [0,1]. Пусть для 1-й стратегии 1 эксперт дал оценку 1, и 35 экспертов – оценку 0.055. А для 2-й стратегии 2 эксперта дали оценку 0.95, а остальные 34 эксперта – оценку 0. Видимо, на основе этих данных практически любой пользователь (человек) выберет 2-ю стратегию. (Поскольку в 1-й стратегии имеется 1 «очень хороший» результат и 35 «очень плохих», а для 2-й стратегии – соответственно 2 «очень хороших» и 34 «очень плохих»; «средних» же результатов ни в одном из двух случаев нет.) Однако усреднение по простейшему алгоритму (т.е., просто среднее арифметическое экспертных оценок) даёт 0.081 в 1-м случае и 0.053 во 2-м – т.е., надо выбирать 1-ю стратегию?
Для 1-й стратегии функция риска имеет вид:
–0.685 x2 + 1.300 x + 0.386 ,
а для 2-й –
–0.694 x2 + 1.374 x + 0.321 .
Окончательные значения усреднения экспертных оценок с помощью этих функций риска составляют 0.111 в 1-м случае и 0.147 – во 2-м. То есть применение алгоритмов динамического построения функций риска и усреднения экспертных оценок с их помощью даёт «более естественные» результаты.
Как уже было сказано, и в завершённом, и в незавершённом алгоритмах метода ветвей и границ нам необходимо воспользоваться тем фактом, что в разных конкретных подзадачах одной и той же задачи оптимизации относительно лучше работают разные эвристики. Было кратко упомянуто об усреднении, которое делается с помощью набора коэффициентов.
Для усреднения результатов, возвращаемых различными предикторами, без набора коэффициентов обойтись невозможно. Эти коэффициенты каким-то образом подбираются для организации наилучшей работы метода ветвей и границ. Однако до сих пор не существует систем, в которых были бы решены вопросы автоматизированного выбора этих коэффициентов. Одним из способов который сможет в будущем решить эту проблему, является применения генетических алгоритмов. Более того, стоит специально отметить: предметом самообучения генетических алгоритмов, например при решении задачи коммивояжера, является не выбор маршрута для конкретной, одной, заданной задачи коммивояжера – а набор-геном коэффициентов для целого класса однотипных задач.
В качестве посылки для организации процесса вычисления оптимального набора-генома коэффициентов может быть принята следующая очевидная цель: создать алгоритм, зависящий от этих коэффициентов, при которых случайно сгенерированная матрица стоимостей была бы посчитана в среднем за наименьшее время. При этом указанный набор коэффициентов (геном) должен быть выбран за ограниченное время – имеющееся в распоряжении исследователя. Важно отметить, что такой выбор оптимального набора-генома коэффициентов производился только для старта некоторого вычислительного процесса, а в процессе работы алгоритма такие наборы коэффициентов модифицируются – т.е. выбираются в зависимости от текущей ситуации в самой задаче.
Однако у описываемого метода имеются следующие две проблемы. Во-первых, применение самообучения коэффициентов при работе такого сложного алгоритма, как метода ветвей и границ с несколькими эвристиками, вряд ли сможет быстро дать хорошие результаты: связь между набором коэффициентов и конкретным рассматриваемым вариантом некоторой задачи оптимизации, конечно же, существует, но вряд ли может быть быстро найдена. Во-вторых, сравнение двух наборов коэффициентов может быть хорошо произведено только при наличии системы тестов с заранее известными результатами; в реальных же условиях такие системы тестов имеются только для самой известной из рассматриваемых задач, а именно задачи коммивояжера.
Обе вышеупомянутые проблемы решаются в различных задачах дискретной оптимизации с помощью одного общего подхода. Этот подход был взят из игрового программирования, отсюда и его название – турнирное самообучение.
Суть подхода заключается в следующем. Из множества наборов-геномов коэффициентов, каждый из которых (наборов) представляет собой один из объектов самообучения, выбираются некоторые два – и между ними проводится т.н. «матч». Каждый матч заключается в том, что для каждого из нескольких случайно сгенерированных вариантов рассматриваемой задачи дискретной оптимизации применяется один и тот же упрощённый алгоритм её решения. Далее для двух вариантов одного и того же алгоритма с разными наборами-геномами коэффициентов (или, что то же самое – двух разных алгоритмов, «участников турнира набора коэффициентов») запоминается:
либо информация о том, на каком из наборов получено относительно лучшее решение,
либо отношение границ, полученных при применении описанных жадных алгоритмов
(возможны и некоторые другие варианты) – в зависимости от конкретного способа реализации алгоритма турнирного самообучения.
Из подобных «сыгранных матчей» формируется «турнир». Выбор худших наборов-геномов (объектов самообучения) для их последующей замены с помощью стандартных (и нестандартных) генетических операторов происходит именно на основе результатов турнира. При этом мы избавляемся от необходимости иметь систему тестов – т.е. набор конкретных задач рассматриваемой задачи дискретной оптимизации. Очень важно отметить, что при этом также нет необходимости применять некоторую конкретную случайно сгенерированную задачу дискретной оптимизации ко всем наборам коэффициентов.
Среди эвристик для конкретных задачи дискретной оптимизации, рассмотрим только одну – а именно, задачу вершинной минимизации недетерминированных конечных автоматов. Описываемые эвристики являются общими для турнирного самообучения и для выбора очередного шага в методе ветвей и границ.
Итак, из всего множества блоков таблицы соответствий некоторого регулярного языка нам необходимо выбрать некоторое подмножество, включающее в себя все имеющиеся (т.е. построенные в процессе канонизации прямого и зеркального автоматов) элементы #. Для такого выбора необходимо ответить на вопрос о включении некоторого конкретного блока в оптимальное подмножество (важно отметить, что это необходимо как для турнирного самообучения, так и для описания очередного шага метода ветвей и границ), и для ответа на этот вопрос мы будем использовать следующий эвристический алгоритм, формулируемый для матрицы элементов #.
Пусть рассматривается клетка матрицы таблицы соответствий состояний с координатами (i,j), пусть также R(i) – количество знаков # в строке i, а C(j) – количество знаков # в столбце j. Тогда:
Для каждой пары (i,j), содержащей #, посчитаем значение
F(i,j) = G(H(R(i)),H(C(j))), (1)
где G(x,y) и H(x) – некоторые функции. При выборе этих функций методами применения генетических алгоритмов относительно вида функции H(x) заранее ничего не известно. Про функцию G(x,y) известно лишь то, что она является возрастающей (т.к. чем больше соседей у ячейки, тем с большей вероятностью она должна войти в искомый блок), но не известно ничего о её выпуклости. G, вообще говоря, не обязана удовлетворять условию симметричности G(x,y)=G(y,x) – поскольку общее число строк и столбцов в рассматриваемой таблице соответствий может различаться. Отметим ещё, что если у ячейки нет соседей ни в строке, ни в столбце (т.е. R(i)=0 либо C(j)=0), то соответствующий ей блок обязательно должен войти в искомое множество покрывающих блоков. Итак, подбор параметров, необходимых для описания поведения этих функций, и есть объект самообучения.
При самообучении обычно использовался следующий конкретный вид функции H(x):
H(x)= e–(P1X) + P2N(x–1)–1 + P3 x + 1, (2)
где N – соответствующая размерность таблицы соответствий состояний. При самообучении игровых программ: при начале самообучения с функциями произвольного вида, т.е. функциями, не имеющими вид (2), результат работы генетических алгоритмов даёт функции вида, близкого к указанному. Однако вид (2) всё же был априори подобран эвристически.
Возможные графики функции (2) для двух различных вариантов значений параметров (а именно, для P1=2/N, P2=1, P3=1 и P1=4/N, P2=5/N, P3=0.01) изображены ниже:
Среди всех блоков выбираем такой (R,C), для которого т.н. итоговая рейтинговая сумма ∑F(Ri,Cj), гдеRiR и CjC, будет наибольшей. Ещё раз отметим, что функция F выбирается согласно (1), а функции G иH при этом получаются в результате самообучения методами генетического алгоритма. Поместим выбранный блок в итоговое множество.
Специальным образом пометим ячейки, принадлежащие выбранному на шаге 3 блоку, чтобы они не учитывались при вычислении F(Ri,Cj), но могли входить в любой вновь выбираемый блок. Итак, в будущем, т.е. при повторном выполнении шагов 1–3, эти ячейки уже не считается помеченными символом #.
Если остались еще ячейки, не вошедшие ни в один блок из итогового множества, то возвращаемся на этап 1. Заметим, что блоки, которым принадлежит хотя бы одна ячейка, не имеющая соседей по вертикали либо по горизонтали, будут обязательно включены в искомое множество, т.к., согласно виду функции F, их рейтинговая сумма равна бесконечности.
Полученное множество блоков считается искомым – и используется либо для проведения очередного шага турнирного самообучения (в простом случае), либо для проведения очередного шага метода ветвей и границ.
ANY-TIME алгоритм фаззификации физических величин на основе четких множеств
В существующих фаззификаторах [22, 70] из-за наложения друг на друга смежных термов приходится в каждом цикле сканирования отрабатывать весь алгоритм фаззификации независимо от текущего значения физической величины. Однако в дискретно-логических регуляторах (ДЛР) [53] вследствие равенства в любой момент времени логической единице только одного терма из множества термов, изображающих конкретную физическую величину, имеется возможность при каждом сканировании отрабатывать не весь алгоритм фаззификации, а только ту его часть, которая находится выше продукционного правила, условная часть которого в данный момент времени равна логической единице. Поэтому в ДЛР для уменьшения цикла фаззификации в начало базы фаззификации нужно располагать правила с наибольшей частотой срабатывания.
К сожалению, на этапе проектирования ДЛР определить достоверное значение частоты срабатывания упомянутых правил крайне сложно, что приводит к неоправданному увеличению цикла сканирования алгоритма фаззификации. Наиболее просто минимизировать время цикла фаззификации в НР с четкими термами можно с помощью ANY-TIME алгоритма [131, 132].
Концептуальную основу такого алгоритма составляет система продукционных правил, которая исключает неопределенность в идентификации четких значений физической величины в совокупность четких термов и предотвращает их наложение [55]. Не снижая общности рассуждений, составим упомянутую систему (3.26) для физической величины, преобразованной в совокупность четких термов, которая изображена на рисунке 2.1,а:
Если 0 р < р1, то (рТ1) & (Сч1 Сч1+1);
Если р1 р < р2, то (рТ2) & (Сч2 Сч2+1);
Если р2 р < р3, то (рТ3) & (Сч3 Сч3+1); (3.26)
……….
……….
……….
Если рn-1 р рn, то (рТn) & (Счn Счn +1).
Из системы (3.26) следует, что все обозначения в ней заимствованы из рисунка 2.1 и цепочка отрезков (0 – р1), (р2 – р3), …, (рn-1 – рn), покрывая без наложения всю универсальную числовую ось, преобразуется в термы Т1 – Тn соответственно физической величины «Параметр р». Причем в любой момент времени только один из указанных термов равен логической единице, что свидетельствует о строгой однозначности процесса фаззификации.
Система (3.26) отличается от типовых систем продукционных правил наличием в консеквентах продукций операторов присваивания (Сч1 Сч1+1) (Счn Счn +1), используемых для подсчета числа фактов истинности условной части (антецедента) правил (1n) соответственно. Такая информация необходима для перерасположения цепочки операторов (рТ1) (рТn),(0 р < р1) (рn-1 р рn) и (Сч1 Сч1+1) (Счn Счn +1) с помощью программного блока «Расположить цепочку операторов в порядке убывания их частоты исполнения» при срабатывании ветви «Да» оператора условного перехода Ттек Тзад. Здесь Ттек – текущее время работы фаззификатора, а Тзад– априорно заданное значение периода модификации структуры фаззификатора с целью уточнения порядка размещения цепочек операторов (рТ1) (рТn),(0 р < р1) (рn-1 р рn) и (Сч1 Сч1+1) (Счn Счn+1) в порядке убывания их частоты срабатывания.
Для более глубокого понимания особенностей преобразования четких значений физической величины в эквивалентную совокупность четких термов на рисунке 3.11 изображена логическая схема алгоритма, соответствующая системе (3.26). Основу схемы составляют n соединенных в цепочку операторов условного перехода, в ветви «Да» которых включены операторы присваивания и счетчики, фиксирующие число инициализаций этих ветвей.
Рассмотрим принцип действия алгоритма, изображенного на рисунке 3.11. В каждом цикле сканирования программно реализованных компонентов нечеткого регулятора инициируется поиск терма, соответствующего текущему четкому значению физической величины. С этой целью оператором условного перехода «0р<р1»определяется принадлежность текущего значения фаззифицируемой величины р отрезку (0 р1). Если р(0 р1), то по ветви «Да» управление передается оператору «рТ1», который текущее четкое
Рисунок 3.11 – Логическая схема ANY-TIME алгоритма фаззификации
с помощью четких термов
значение физической величины р преобразует (фаззифицирует) в терм Т1, а содержимое счетчика Сч1увеличивается на единицу. Если Ттек Тзад, то с помощью блока «Модификация структуры алгоритма» происходит перерасположение цепочки операторов (0 р < р1) (рn-1 р рn), (рТ1) (рТn) и (Сч1 Сч1+1) (Счn Счn +1) в теле программы фаззификатора в соответствии с частотой их исполнения. В противном случае цикл сканирования алгоритма фаззификации закончится без модификации структуры программы фаззификатора. При срабатывании выхода «Да» операторов «р1р<р2» «рn-1р рn», описанная процедура повторяется, но уже при участии других ветвей алгоритма фаззификации.
С точки зрения законов материального мира, в любой момент времени физическая величина имеет только одно значение, вследствие чего в любой момент времени только у одного из операторов (0 р < р1) (рn-1 р рn) выход «Да» имеет истинное значение. В случае некорректного задания диапазонов существования термов Т1 Тn, когдани одно из условий (0 р < р1) (рn-1 р рn) не выполняется, управление передается блоку «Аларм» для идентификации аварийной ситуации.
Блок «Модификация структуры алгоритма (МСА)» реализует процедуру ANY-TIME минимизации времени фаззификации НР. При выполнении условия Ттек Тзад блок МСА по информации, накопленной в счетчиках (Сч1 Сч1+1) (Счn Счn+1) переставляет цепочки операторов ((0 р < р1) - (рТ1) - (Сч1 Сч1+1) (рn-1 р рn),(рТn) и (Счn Счn+1) на рисунке 3.11 слева направо в порядке убывания их частоты использования. После этого счетчики обнуляются и начинается новый отсчет текущего времени Ттек. Тем самым на основе статистической информации, архивируемой в счетчиках Сч1 Счn, через каждый промежуток времени, равный Тзад, происходит перестановка упомянутых выше цепочек операторов с целью минимизации времени, необходимого для фаззификации.
Произведем количественную оценку снижения продолжительности фаззификации, обусловленной использованием ANY-TIME алгоритма. Пусть физическая величина «Параметр р» в результате фаззификации эквивалентно преобразовывается в n четких термов Т1 Тn. Введем следующие обозначения: nt – количество продукционных правил из системы (3.26), отработанных в текущем цикле сканирования алгоритма фаззификции; tу и tз – соответственно время отработки условной и заключительной частей одного продукционного правила; tм – время проверки условия Ттек Тзад.
С учетом принятых обозначений время цикла фаззификации можно выразить следующей формулой:
Тц=nttу+2tз+tм. (3.27)
В выражении (3.27) предполагается, что на исполнение операторов рТiи Счi Счi+1 процессор затрачивает одинаковое время.
При nt=1 из выражения (3.27) получается формула для минимального значения времени цикла:
Тmin=tу+2tз+tм. (3.28)
В этом случае в схеме на рисунке 3.11 последовательно отрабатываются операторы (0 р < р1) – (рТ1) – (Сч1 Сч1+1) – (Ттек Тзад), а в системе продукционных правил (3.26) отрабатывается только первое правило, условная часть которого равна логической единице.
Аналогично из (3.27) при nt=n максимальное время цикла фаззификации
Тmax=ntу+2tз+tм. (3.29)
Применительно к схеме на рисунке 3.11 выражение (3.29) соответствует ситуации, когда последовательно отрабатываются операторы (0 р < р1) – (р1 р < р2) – (р2 р < р,) ÷ (рn-1 р < рn) – (рТn) – (Счn Счn+1) – (Ттек Тзад), а в системе продукционных правил (3.26) условная часть только последнего продукционного правила равна логической единице.
Из (3.28) и (3.29) можно определить, на сколько короткий цикл сканирования меньше длинного
Т1,0= Тmax– Тmin=(n-1) tу (3.30)
Однако в типовых процедурах фаззификации, вырабатывающих четкие термы, даже с ANY-TIME алгоритмом в каждом цикле сканирования отрабатываются (1030)% продукционных правил, относящихся к процедуре фаззификации.
Семейство функций (3.27) Тц=f(nt) для четырех наиболее известных производителей программируемых контроллеров приведено на рисунке 3.12, из которого следует, что наибольшим быстродействием обладает контроллер фирмы YOKOGAWA, а наименьшим – Российский контроллер КР-500. На этом же рисунке указаны минимальные Тmin1÷ Тmin4 (nt=1) и максимальные Тmax1÷ Тmax4 значения циклов сканирования алгоритма фаззификации при nt=8.
Используя те же обозначения, что и в (3.27), получим выражение для цикла сканирования Ттфв типовом фаззификаторе, в котором, как известно [70], при каждом цикле сканирования безусловно, полностью и независимо от логического состояния антецедентов отрабатываются все продукционные правила. Отсюда
Ттф=n(tу+ tз). (3.31)
Рисунок 3.12 – Зависимость длительности цикла Тц сканирования алгоритма фаззификации то числа отработанных продукционных правил nt
Для упрощения выражения (3.31) принимаем tу=tз. Тогда выражение (3.31) принимает следующий вид:
Ттф=2ntу. (3.32)
В свою очередь, выражения (3.30) и (3.32) позволяют определить долю Т1,0 в цикле сканирования Ттф типового фаззификатора:
(3.33)
Как уже отмечалось, при эффективной работе ANY–TIME алгоритма в каждом цикле сканирования отрабатывается не одно, а (0,10,3)n подукционных правила. Поэтому практический интерес представляет получение выражений, аналогичных выражениям (2.11) и (2.14) при nt=0,1n; 0,2n и 0,3n.
Т0,9=(0.9n-1)tу; (3.34)
Т0,8=(0,8n-1)tу; (3.35)
Т0,7=(0,7n-1)tу; (3.36)
Графическое изображение функций (3.33)(3.36) представлено на рисунке 3.13,
Ряд 1 – , Ряд 2 – , Ряд 3 – , Ряд 4 – .
Рисунок 3.13 – Влияние ANY–TIME алгоритма на длительность сканирования алгоритма фаззификации
из которого следует, что наиболее интенсивное снижение времени цикла сканирования алгоритма фаззификации имеет место при малых значениях n. По мере увеличения n эффективность работы ANY–TIME алгоритма вначале снижается, а затем стабилизируется на определенном уровне. Например, из выражений (3.33 3.36) следует, что при n=10 длитедьность сканирования алгоритма фаззификации ДЛР уменьшается на (30 40)%. Оцифровка функций на рисунке 3.13 приведена в таблице 3.3.
Таблица 3.3 – В
Не Пропустите:
- Лабораторная работа №1 по дисциплине «Технологии и методы программирования» на тему: Алгоритмы.
- Р Е Ц Е Н З И Я на дипломный проект студента факультета ИРТ Тема дипломного проекта: Интегрированная система мониторинга телекоммуникационного оборудования компании – оператора связи.
- Вопросы по дисциплине «Гидрогазодинамика»
- ТЕМА 4. ПОТРЕБИТЕЛЬСКИЕ РЫНКИ И ПОКУПАТЕЛЬСКОЕ ПОВЕДЕНИЕ ПОТРЕБИТЕЛЕЙ
- Лекция "Политология как наука и учебная дисциплина."