Математическое обеспечение интеллектуальных систем декомпозиции объектов с невозобновляемыми ресурсами
На правах рукописи
Ковель Иван Владимирович
МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ ДЕКОМПОЗИЦИИ ОБЪЕКТОВ С НЕВОЗОБНОВЛЯЕМЫМИ РЕСУРСАМИ
Специальность 05.13.01 – «Системный анализ, управление и обработка информации (информационные и технические системы)»
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Краснодар – 2011
Работа выполнена в ГОУ ВПО «Кубанский государственный технологический университет»
| Научный руководитель: | доктор технических наук, профессор Ключко Владимир Игнатьевич |
| Официальные оппоненты: | доктор технических наук, профессор Хисамов Франгиз Гильфанетдинович кандидат технических наук, доцент Григорьев Николай Федорович |
| Ведущая организация: | Кубанский государственный университет |
Защита состоится «18» февраля 2011 года в 13.00 на заседании диссертационного совета Д 212.100.04 в Кубанском государственном технологическом университете по адресу: 350072, г. Краснодар, ул. Московская, 2, ауд. Г-251
С диссертацией можно ознакомиться в библиотеке Кубанского государственного технологического университета
Автореферат разослан “17” января 2011 г.
Ученый секретарь
диссертационного совета,
канд. техн. наук, доцент А.В. Власенко
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Оптимальное распределение и потребление ресурсов является одним из определяющих факторов в жизни современного общества. Для ряда задач оптимизации потребления материальных, энергетических и информационных ресурсов характерен такой отличительный признак как принадлежность к классу NPCзадач, допускающих приближённое решение. Представителями указанного класса задач являются задачи оптимизации плоского ортогонального и криволинейного раскроя-упаковки, распределения персонала, перевозок, размещения предприятий, управления производством, а также проектирование в области электроники и архитектуры.
С одной стороны для решения NPCзадач дискретной оптимизации с произвольной размерностью исходных данных в настоящее время не существует методов получения точного решения за время, ограниченное техническими условиями функционирования информационной системы или продолжительностью технологических операций. Поэтому суть современных методов заключается в выборе лучшего варианта при проверке чрезвычайно узкого подмножества всех возможных альтернатив в надежде на то, что ошибка найденного решения не слишком велика и решение будет субоптимальным. При этом величина ошибки приближённого решения принципиально не определяема. Сформированные к настоящему времени направления исследований в этой области имеют ряд особенностей.
1) Методы динамического программирования, основанные на принципе локальной оптимальности Беллмана, не содержат научно обоснованных критериев локализации субоптимальных решений в пространстве поиска NPCзадач.
2) Эвристики ограничения перебора дерева решений (имитация отжига, муравьиная колония, генетические алгоритмы и др.) в большей мере определяются творческими способностями и талантом исполнителя, нежели формализмами указанных алгоритмов.
3) Вероятностные алгоритмы (Монте-Карло, Лас-Вегас, Шервудские) не гарантируют стабильность решения NPCзадач по причине возможного отказа или заведомо усреднённого результата.
С другой стороны современная вычислительная техника, благодаря недостижимому ранее быстродействию, позволяет исследовать NPCзадачи оптимизации декомпозиции малой размерности, выявлять закономерности распределения субоптимальных решений в пространстве решений, строить на их основе статистически обоснованные эвристики управления поиском, и, полагаясь на то, что выявленные закономерности сохраняются в задачах с большой размерностью исходных данных, использовать найденные эвристики в практике оптимизации декомпозиции объектов с произвольной размерностью.
Таким образом, диссертационная работа посвящена актуальным вопросам разработки структуры и правил функционирования интеллектуальной системы декомпозиции объектов на основе статистически определённой функции вероятности рангов локальных решений. Такой подход позволяет решать прикладные NPCзадачи оптимального потребления ресурсов путём выборки только субоптимальных по вероятности решений из окрестности глобального оптимума (ГО).
Целью настоящей работы является оптимизация потребления ресурсов на основе использования статистически обоснованной функции вероятности рангов локальных решений из окрестности ГО.
Для достижения указанной цели в работе были поставлены и решены следующие задачи.
- Провести анализ методов оптимизации потребления ресурсов.
- Представить ранжированные решения NPCзадач оптимизации потребления ресурсов функциями вероятности рангов локальных решений.
- Разработать генератор стохастических ранжированных решений NPCзадач на основе генераторов псевдослучайных рангов локальных решений.
- Разработать структуру стохастической интеллектуальной системы с ранжированными решениями.
- Разработать методику определения диапазонов генерации рангов.
- Оценить эффективность использования интеллектуальной системы.
Для решения поставленных задач в диссертации использованы методы системного анализа, дискретной оптимизации, теории автоматов и вычислений, теории вероятностей и математической статистики, теории графов, теории множеств.
Объектом настоящего исследования являются системы декомпозиции объектов с невозобновляемыми ресурсами. Предмет исследования – вероятностный поиск субоптимальных решений в пространстве состояний интеллектуальных систем.
Научная новизна работы заключается в следующем:
- решение NPCзадач потребления ресурсов представлено в ранжированной форме, в которой ранги локальных решений выражены функциями вероятности и реализованы генераторами псевдослучайных чисел, что позволяет использовать обоснованное распределение рангов для сокращения пространства поиска;
- механизм поиска решений в структуре интеллектуальной системы декомпозиции объектов реализован генератором ранжированных решений, что сокращает удельные вычислительные затраты на получение субоптимального решения;
- разработана методика определения диапазонов генерации рангов, заключающаяся в определении верхней границы изменения рангов и ограничения диапазона изменения его значений.
Результаты теоретических и экспериментальных исследований легли в основу построения интеллектуальной системы, позволяющей повысить экономию ресурсов и сократить время технологического цикла декомпозиции, в чём и заключается практическая ценность работы.
Положения, выносимые на защиту:
- Метод вероятностного поиска ранжированных субоптимальных решений. Представление ранжированных решений NPCзадач декомпозиции объектов функциями вероятности рангов локальных решений позволяет использовать генераторы псевдослучайных чисел с геометрическим распределением для быстрого перебора субоптимальных решений;
- Модель интеллектуальной системы. Использование генератора ранжированных решений с геометрическим распределением рангов сокращает удельные вычислительные затраты на получение субоптимального решения в условиях ограниченного времени решения;
- Методика определения диапазонов генерации рангов. Вероятность того, что последний ранг цепи равен единице, является нижней границей для вероятностей остальных рангов, что определяет верхнюю границу генерации рангов.
Теоретические положения работы внедрены в ООО “Бакаут” при разработке интеллектуальной системы оптимизации раскроя-упаковки плоских изделий мебельной промышленности.
Достоверность и обоснованность полученных результатов основывается на промышленной эксплуатации прикладной интеллектуальной системы ортогонального раскроя-упаковки на предприятии г. Краснодара ООО “Бакаут”, а также компьютерными экспериментами по сравнению результатов решения ряда NPCзадач разработанной интеллектуальной системой и специализированными для этих задач методами.
Апробация и публикации. Результаты исследований докладывались и обсуждались на международных и Всероссийских конференциях. Результаты диссертации опубликованы в 13 работах, из них одна в ведущем периодическом издании, рекомендованном ВАК РФ, 12 работ в сборниках трудов международных и Всероссийских конференций.
Структура и объём диссертации. Диссертация состоит из введения, четырёх разделов, заключения, списка использованных источников из 103 наименований и приложений, содержит 153 страницы машинописного текста и включает 21 рисунок и 6 таблиц.
ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ
Во введении обоснована актуальность диссертации, сформулированы цель и задачи исследования, изложены полученные автором основные результаты проведенных исследований, показана их научная новизна, практическая значимость, указаны основные положения, выносимые на защиту, и дана общая характеристика работы.
В первом разделе «Анализ методов оптимизации потребления ресурсов» рассмотрены основные понятия и определения теории решения NP-задач. Произведена характеристика вычислительной сложности задачи оптимального потребления ресурсов как NP-задачи. Рассмотрены проблемные факторы: экспоненциальный рост вычислительной сложности, отсутствие модели представления решений в формальной постановке прикладных NPзадач, принципиальная недетерминированность величины ошибки субоптимальных решений и невозможность проверки оптимальности полученного каким-либо способом решения. Произведён анализ универсальных методов искусственного интеллекта для приближённого решения NP-задач, а также анализ специальных методов оптимальной декомпозиции плоских объектов. Определён один из перспективных путей решения задач оптимального потребления ресурсов – построение интеллектуальных систем с ограничением ширины поиска в пространстве ранжированных решений на основе использования функциональной зависимости ранга локального решения от его координат. Такой способ усекает поиск до априорно заданной окрестности глобального оптимума, которым является решение Беллмана.
Во втором разделе произведена постановка задачи стохастического поиска в пространстве ранжированных решений. Исходные данные описаны в виде графов без петель и кратных рёбер G = (V, E, d), где V – множество вершин-ресурсов vi произвольной природы, |V| = n. Каждая вершина vi характеризуется вектором параметров ресурсов Pi = (p1, p2,…, pd), определённых на множестве +, pi +, d – размерность ресурсов, определённая на множестве +. E – множество рёбер-ресурсов eij, задающих отношение смежности произвольной природы между вершинами vi и vj, eij = eji, i j. Множество E определено на множестве + и его мощность 
.
Решение NPзадачи оптимального потребления ресурса представлено в виде структуры zi = K(, zj), содержащей носитель структуры – цепи П и конструктор структуры K. Структура z представляет собой дерево, подобное введённому Марковым В.Н. меченому упорядоченному дереву при решении задач гильотинного раскроя. Конструктор K – семейство уравнений {K1, K2, …, Ki}, описывающих отображение П 
, удовлетворяющее условию C, где П – множество носителей структуры, роль которого играет множество цепей на графе G, используемых Касьяновым В.Н. и Евстигнеевым В.А. для анализа свойств графов. Метками на дереве являются конструкторы Ki, рекурсивно упорядочивающие структуру дерева. Построение дерева z разделено на построение структуры дерева посредством фиксированного конструктора К и наполнение дерева конкретным содержанием – носителем П. Новизна подхода заключается в том, что декомпозиция решения позволяет отдельно друг от друга исследовать влияние формы представления решения, то есть семейства уравнений {K1, K2, …, Ki}, и содержания решения, то есть цепей, на вес получаемого решения g(z). Потребление ресурсов заключается в пошаговом исключении из графа G выбираемых по определённому критерию ресурсов ui и формирования на их основе структуры решения zi по эвристическим правилам zi = K(, zj).
Пространство поиска цепей (n,k) на полном графе представлено в виде множества n,k = {(n,k) | 0 < k n+1}, где n – количество вершин, k – длина цепи. Мощность n,k растёт факториально 
. Приведены и рассмотрены структурные свойства дерева поиска цепей, определяющие факториальную сложность задачи поиска оптимальной цепи 
, где 
– количество вершин в дереве поиска при произвольном n.
Цепи (n, k) = (v1, v2,…, vi,…, vk) представлены ранжированными цепями (n, k) = (r1, r2,…, ri,…, rk). Введено понятие стохастических ранжированных цепей посредством замены рангов ri функцией вероятности этих рангов i(), где - параметр распределения.
Постановка задачи вероятностного поиска оптимального потребления ресурсов имеет следующий вид. Вес вершины v графа G выражен функцией 
, определённой на +, вес ребра – функцией w(eij), определённой на +, а вес цепи (n,k) – в общем случае выражением
, (1)
где kV, kE – коэффициенты, характеризующие веса вершин и рёбер соответственно, kV 0, kE 0.
Вес решения g(z) равен суммарному весу носителя 
. Структура оптимального носителя определяется деревом z = K(i, z), меченым конструкторами из семейства {K1, K2, …, Kj}. Для заданной структуры z его носители в работе называются решениями.
Для фиксированной пары (K, C) задача сводится к поиску цепи с минимальным весом в пределах заданной верхней границы max вычислительных затрат
(2)
, (3)
где (i-1, i) – вычислительная сложность перехода от цепи i-1 к цепи i, получаемая как сумма вычислительных затрат на переходы из концевой вершины цепи i-1 в концевую вершину цепи i.
В разделе также поставлена частная задача исследования – задача оптимального ортогонального раскроя со сквозным резом:
Исходные данные:
X, Y – размеры листов материала (ресурсов);
xi, yi, mi, ui – длина, ширина, количество, ориентация i-й детали;
n – суммарное количество деталей.
Целевая функция:
(4)
где N – количество востребованных ресурсов, 1j N.
Ограничения: раскрой – ортогональный, гильотинный.
Требуется найти: такое функциональное представление вероятности ранга выбора i-й детали P(ri), при которой цепь выбора деталей 
максимизирует целевую функцию, где k – количество деталей в полосе размещения.
В третьем разделе “Математическое обеспечение стохастической интеллектуальной системы” разработаны элементы структуры и формализованы правила функционирования стохастической интеллектуальной системы. Определён метод вероятностного поиска субоптимальных решений NP-задач в терминах модели управления ресурсами. Недетерминизм функционирования данных систем заключается в неопределённости перехода состояний при потреблении единичного ресурса ui. NPполнота систем определяется тем, что граф переходов состояний таких систем гомоморфен дереву поиска решений. Интеллектуальность систем определяется наличием базы знаний правил компоновки карт раскроя (семейство конструкторов К), которые являются, по сути, экспертными правилами базы знаний.
Структурная схема стохастического генератора цепей (рис.1), содержит k последовательно соединённых комбинационных устройств, выполняющих операцию выбора sel : (vi, G(i), C) (vi+1, G(i+1)), которая по случайной функции управления i+1, возвращающей ранг ri+1, выбирает удовлетворяющую условиям C смежную к vi вершину vi+1 и усечённый граф G(i+1) = G(i)\{ui}, а также k последовательно соединённых комбинационных устройств, выполняющих операцию & : ((n,i), vi+1) ((n,i+1)) поэлементного построения цепи (n,k).
Параметр геометрического распределения 
определяется на основании переменных n, k, i состояния дискретной системы. Блоки Pi на основании параметра и номера шага решения i вычисляют разрешённую верхнюю границу ГПСЧi. Генераторы псевдослучайных чисел ГПСЧi функционируют на основании равномерного закона распределения целых чисел в диапазоне [0, …, Pi].
На входы генератора ранжированных цепей поступают:
- начальная вершина v0, служащая корнем дерева переходов системы,
- условия C, налагаемые на носитель структуры,
На выходах генератора выставляются:
- цепь i(n,k),
- вес цепи h(i).
Для построения окрестности глобального оптимума предложено использовать генератор цепей (рис.2), что и является сутью метода вероятностного поиска.
Конвертер преобразует ранжированную цепь (n,k) = [r1, r2, …, rk-1] в цепь вершин (n,k) = [v1, v2, …, vk] с целью последующего вычисления её веса h() как суммы весов вершин и/или рёбер. Селектор субоптимальной цепи сохраняет в своём регистре наилучшую текущую цепь *, т.е. цепь с минимальным весом среди прочих построенных, и выдаёт сигнал на разрешение генерации следующей ранжированной цепи.
В разделе описаны алгоритмы поиска решений в терминах модели управления ресурсами с регистром памяти состояния и приведены характеристики их вычислительной сложности.
В четвёртом разделе “Структура стохастической интеллектуальной системы” рассмотрены структура стохастической интеллектуальной системы и правила функционирования в режимах анализа и синтеза.
На рис.3 изображена структурная схема интеллектуальной системы, функционирующей в режиме анализа решений NP-задач. Режим анализа интеллектуальной системы предназначен для решения NP-задач малой размерности способом полного перебора всех ранжированных решений с целью определения статистических характеристик веса ранжированных решений. Режим анализа позволяет описать зависимость распределения веса ранжированных решений от рангов локальных решений и выявить ту область вариации рангов локальных решений, которая допускается только для субоптимальных решений. Допущением является предположение о том, что такая зависимость сохранится в задачах большой размерности.
На рис.4 изображена структурная схема стохастической интеллектуальной системы, функционирующей в режиме синтеза решений NP-задач. Отличием работы стохастической интеллектуальной системы от известных методов решения является наличие эвристической функции hr(m), управляющей генератором рангов таким образом, что генерируются только такие ранги, при которых полученные цепи имеют высокую вероятность того, что данная цепь оптимальна.
Новизну предлагаемого подхода к построению решателей NP-задач определяет использование для управления поиском решения с произвольным размером исходных данных вероятностных функций именно от рангов локальных решений. Указанные функции отражают в той или иной мере распределение оптимальных решений на всём множестве решений, которое получено на основе статистического анализа всех ранжированных решений ПЗ на данных малого размера.
Достоинства вероятностного метода поиска субоптимальных ранжированных цепей:
- Отсутствие притяжения к локальным оптимумам.
- Большой объём поиска.
- Наиболее часто проверяются субоптимальные по вероятности решения, так как правило, генерации рангов цепей соответствует закону распределении рангов субоптимальных цепей.
- Возможность останова либо по времени, либо по заданному объёму поиска, либо при достижении заданного порога веса решения.
- Возможность повторного запуска алгоритма.
- Недостатки вероятностного метода:
- Повтор наиболее вероятных субоптимальных решений.
- Эффективность решения пропорциональна времени работы алгоритма.
На рис.5 представлена структурная схема интеллектуальной стохастической системы для решения задачи ортогонального раскроя со сквозным резом. Описанная система была реализована программным способом в среде Visual Prolog 5.2. и внедрена на предприятии мебельной промышленности ООО “БАКАУТ” г. Краснодар в 2009 г.
Достигаемый коэффициент использования ресурсов на отдельных картах раскроя 97%, относительный полезный эффект в сравнении с существующими многочисленными системами оптимизации 2DCSP на мелко и среднесерийном производстве с большим ассортиментом деталей прог 3%, относительный полезный эффект в сравнении с ручным кроем ручн 2 11% в зависимости от размерности исходных данных. Время кроя сокращено в десятки раз по сравнению с ручным кроем. Рекомендация по условиям эффективного использования: мелко и среднесерийное производство, высокая стоимость ресурсов, большой производственный оборот.
В заключение диссертации приведены основные результаты и выводы.
Основные выводы и результаты работы
- Проведён сравнительный анализ общих методов решения NP-задач дискретной оптимизации, а также специальных методов оптимизации раскроя-упаковки. На основании анализа сделан вывод о том, что один из перспективных путей решения NP-задач оптимизации раскроя-упаковки – использование зависимости оценки веса субоптимальных решений от рангов локальных решений.
- Разработан метод вероятностного поиска субоптимальных решений NP-задач оптимизации раскроя-упаковки на основе использования геометрической функции распределения рангов локальных решений, составляющих глобальные субоптимальные решения.
- Разработан генератор стохастических ранжированных решений NPзадач с использованием генераторов псевдослучайных рангов локальных решений, работающих на основе геометрического распределения.
- Разработана структура стохастической интеллектуальной системы с ранжированными решениями и алгоритмы её функционирования в режиме анализа и синтеза решений NPCзадач раскроя-упаковки. Разработаны быстрые алгоритмы декодирования ранжированных решений, которые позволяют сократить время получение субоптимальных решений.
- Произведена оценка эффективности использования стохастической интеллектуальной системы.
Предложенный подход к построению интеллектуальных систем позволяет эффективно применять их при решении ряда NPзадач оптимизации потребления материальных, энергетических и информационных ресурсов, допускающих субоптимальное решение: оптимизация плоского ортогонального и криволинейного раскроя-упаковки, распределение персонала и перевозок, размещения предприятий, управления производством, проектирование в области электроники и архитектуры, оптимальная декомпозиция площадей земельных участков при разработке земельного кадастра и пр. Экспериментальные исследования показали повышение экономии ресурсов и сокращение времени технологического цикла декомпозиции, в чём и заключается практическая ценность работы.
Публикации по теме диссертации
1. Ковель И.В. Вероятностный метод построения окрестности статистического глобального оптимума NPC-задач // Интеллектуальные технологии. 2010. №2 - с. 38 – 41.
2. Ковель И.В. Интеллектуальная система раскроя-упаковки с ранжированным управлением шириной поиска // Сборник трудов V Всероссийской научной конференции. «Информационные технологии в промышленности» Ниж. Новгород. 2008. с. 422-424
3. Ковель И.В., Марков В.Н. Метод адаптации весовых коэффициентов к исходным данным в задачах раскроя-упаковки // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. – с.105-110.
4. Ковель И.В. Синтез базы знаний прикладной интеллектуальной системы негильотинного раскроя-упаковки // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. – с.111-113.
5. Ковель И.В. Вероятностный способ перебора ранжированных решений задачи раскроя-упаковки // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. – с.192-193.
6. Ковель И.В. Ключко В.И., Марков В.Н. Интеллектуальная система для приближённого решения прикладных NPC-задач // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. – с.194-199.
7. Ковель И.В. Ключко В.И., Марков В.Н. Свойства пространства поиска решений в дискретных задачах управления невозобновляемыми ресурсами // Сборник трудов 7 Международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности», Санкт-Петербург. 2009. – с.397-398.
8. Ковель И.В. Управление шириной поиска в ранжированном пространстве решений // Сборник трудов 7 Международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности», Санкт-Петербург. 2009. – с.399-400.
9. Ковель И.В. Оценка ширины поиска в ранжированном пространстве решений // Сборник трудов VI Всероссийской научной конференции молодых ученых и студентов «Современное состояние и приоритеты развития фундаментальных наук в регионах» Анапа. 2009. с. 253-254.
10. Ковель И.В. Проблемный подход в преподавании дисциплины «Структуры и алгоритмы обработки данных» // Сборник научных трудов XVI Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». КубГТУ. 2009.
11. Ковель И.В. Интеллектуальная система с ранжированным деревом решений // Сборник трудов 8 Международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности», Санкт-Петербург. 2009. – с.241-242
12. Ковель И.В. Способ логической адаптации весовых коэффициентов к исходным данным в задачах раскроя-упаковки // Сборник трудов V Всероссийской научной конференции молодых ученых и студентов «Современное состояние и приоритеты развития фундаментальных наук в регионах» Анапа. 2008. с. 117-118.
13. Ковель И.В. Проблемный подход в преподавании дисциплины «Системы искусственного интеллекта» // Сборник научных трудов XVI Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». КубГТУ. 2010.
