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

На правах рукописи

Ковель Иван Владимирович

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ ДЕКОМПОЗИЦИИ ОБЪЕКТОВ С НЕВОЮБНОВЛЯЕМЫМИ РЕСУРСАМИ

Специальность 05.13.01 - «Системный анализ, управление и обработка информации (информационные и технические системы)»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Краснодар - 2011

4856230

Работа выполнена в ГОУ ВПО «Кубанский государственный технологический университет»

Научный руководитель: доктор технических наук, профессор

Ключко Владимир Игнатьевич

Официальные оппоненты: доктор технических наук, профессор

Хисамов Франгиз Гильфанетдинович

кандидат технических наук, доцент Григорьев Николай Федорович

Ведущая организация: Кубанский государственный университет

Защита состоится «18» февраля 2011 года в 13.00 на заседании диссертационного совета Д 212.100.04 в Кубанском государственном технологическом университете по адресу: 350072, г. Краснодар, ул. Московская, 2, ауд. Г-251

С диссертацией можно ознакомиться в библиотеке Кубанского государственного технологического университета Автореферат разослан "17" января 2011 г.

Ученый секретарь диссертационного совета, канд. техн. наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

1) Методы динамического программирования, основанные на принципе локальной оптимальности Беллмана, не содержат научно обоснованных критериев локализации субоптимальных решений в пространстве поиска N РС-задач.

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

3) Вероятностные алгоритмы (Монте-Карло, Лас-Вегас, Шервудские) не гарантируют стабильность решения №С-задач по причине возможного отказа или заведомо усреднённого результата.

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

Таким образом, диссертационная работа посвящена актуальным вопросам разработки структуры и правил функционирования

интеллектуальной системы декомпозиции объектов на основе статистически определённой функции вероятности рангов локальных решений. Такой подход позволяет решать прикладные №С-задачи оптимального потребления ресурсов путём выборки только субоптимальных по вероятности решений из окрестности глобального оптимума (ГО).

Целыо настоящей работы является оптимизация потребления ресурсов на основе использования статистически обоснованной функции вероятности рангов локальных решений из окрестности ГО.

Для достижения указанной цели в работе были поставлены и решены следующие задачи.

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

2. Представить ранжированные решения ОТС-задач оптимизации потребления ресурсов функциями вероятности рангов локальных решений.

3. Разработать генератор стохастических ранжированных решений ЫРС-задач на основе генераторов псевдослучайных рангов локальных решений.

4. Разработать структуру стохастической интеллектуальной системы с ранжированными решениями.

5. Разработать методику определения диапазонов генерации рангов.

6. Оценить эффективность использования интеллектуальной системы.

Для решения поставленных задач в диссертации использованы

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

Объектом настоящего исследования являются системы декомпозиции объектов с невозобновляемыми ресурсами. Предмет исследования - вероятностный поиск субоптимальных решений в пространстве состояний интеллектуальных систем.

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

• решение ЫРС-задач потребления ресурсов представлено в ранжированной форме, в которой ранги локальных решений выражены функциями вероятности и реализованы генераторами псевдослучайных чисел, что позволяет использовать обоснованное распределение рангов для сокращения пространства поиска;

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

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

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

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

• Метод вероятностного поиска ранжированных субоптимальных решений. Представление ранжированных решений ЫРС-задач декомпозиции объектов функциями вероятности рангов локальных решений позволяет использовать генераторы псевдослучайных чисел с геометрическим распределением для быстрого перебора субоптимальных решений;

• Модель интеллектуальной системы. Использование генератора ранжированных решений с геометрическим распределением рангов сокращает удельные вычислительные затраты на получение субоптимального решения в условиях ограниченного времени решения;

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

Теоретические положения работы внедрены в ООО "Бакаут" при разработке интеллектуальной системы оптимизации раскроя-упаковки плоских изделий мебельной промышленности.

Достоверность и обоснованность полученных результатов основывается на промышленной эксплуатации прикладной

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

Апробация и публикации. Результаты исследований докладывались и обсуждались на международных и Всероссийских конференциях. Результаты диссертации опубликованы в 13 работах, из них одна в ведущем периодическом издании, рекомендованном ВАК РФ, 12 работ в сборниках трудов международных и Всероссийских конференций.

Структура и объём диссертации. Диссертация состоит из введения, четырёх разделов, заключения, списка использованных источников из 103 наименований и приложений, содержит 153 страницы машинописного текста и включает 21 рисунок и 6 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ Во введении обоснована актуальность диссертации, сформулированы цель и задачи исследования, изложены полученные автором основные результаты проведенных исследований, показана их научная новизна, практическая значимость, указаны основные положения, выносимые на защиту, и дана общая характеристика работы.

В первом разделе «Анализ методов оптимизации потребления ресурсов» рассмотрены основные понятия и определения теории решения

ИР-задач. Произведена характеристика вычислительной сложности задачи оптимального потребления ресурсов как ИР-задачи. Рассмотрены проблемные факторы: экспоненциальный рост вычислительной сложности, отсутствие модели представления решений в формальной постановке прикладных ОТ-задач, принципиальная недетерминированность величины ошибки субоптимальных решений и невозможность проверки оптимальности полученного каким-либо способом решения. Произведён анализ универсальных методов искусственного интеллекта для приближённого решения ЫР-задач, а также анализ специальных методов оптимальной декомпозиции плоских объектов. Определён один из перспективных путей решения задач оптимального потребления ресурсов -построение интеллектуальных систем с ограничением ширины поиска в пространстве ранжированных решений на основе использования функциональной зависимости ранга локального решения от его координат. Такой способ усекает поиск до априорно заданной окрестности глобального оптимума, которым является решение Беллмана.

Во втором разделе произведена постановка задачи стохастического поиска в пространстве ранжированных решений. Исходные данные описаны в виде графов без петель и кратных рёбер (7 = (К, Е, с/), где V -множество вершин-ресурсов V,- произвольной природы, \У] = п. Каждая вершина V, характеризуется вектором параметров ресурсов = (р\,рг,---,р4), определённых на множестве 1е IV, ¿/-размерность

ресурсов, определённая на множестве Е- множество рёбер-ресурсов с,у, задающих отношение смежности произвольной природы между вершинами V, и у,-, си = су„ / *). Множество Е определено на множестве 11+

и его мощность |£] < —-—.

Решение МР-задачи оптимального потребления ресурса представлено в виде структуры г,- А'(л, г,), содержащей носитель структуры - цепи л е П и конструктор структуры К. Структура г представляет собой дерево, подобное введённому Марковым В.Н. меченому упорядоченному дереву при решении задач гильотинного раскроя. Конструктор К - семейство уравнений {К\, К2,..., К/},

описывающих отображение П х М —-—» А/, удовлетворяющее условию С,

где П - множество носителей структуры, роль которого играет множество цепей ж на графе С, используемых Касьяновым В.Н. и Евстигнеевым В.А. для анализа свойств графов. Метками на дереве являются конструкторы ЛТ„ рекурсивно упорядочивающие структуру дерева. Построение дерева г разделено на построение структуры дерева посредством фиксированного конструктора К и наполнение дерева конкретным содержанием -носителем П. Новизна подхода заключается в том, что декомпозиция решения позволяет отдельно друг от друга исследовать влияние формы представления решения, то есть семейства уравнений {К), К2,К,}, и содержания решения, то есть цепей п, на вес получаемого решения

Потребление ресурсов заключается в пошаговом исключении из графа С выбираемых по определённому критерию ресурсов u¡ и формирования на их основе структуры решения г, по эвристическим правилам z¡ = К(п, Zj).

Пространство поиска цепей п(п,к) на полном графе представлено в виде множества П„1= {я(п,к) \0 < к< л+1}, где п - количество вершин, к - длина

цепи. Мощность Г\„к растёт факториально П к = Ап =-. Приведены и

1 ' (п-к)1

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

факториальную сложность задачи поиска оптимальной цепи (П^ ~ п\ е, где

|П| - количество вершин в дереве поиска при произвольном п.

Цепи п(п, к) = (vi, v2,..., v¡,..., vk) представлены ранжированными цепями /с) = (ль r2,..., rh..., rt). Введено понятие стохастических

ранжированных цепей посредством замены рангов r¡ функцией вероятности этих рангов %¡{ 9), где 9 - параметр распределения.

Постановка задачи вероятностного поиска оптимального потребления ресурсов имеет следующий вид. Вес вершины v графа G d

выражен функцией q(v) = p¡, определённой на R+, вес ребра - функцией

/=|

iv(c,y), огфеделённой на R+, а вес цепи л (и,/с) - в общем случае выражением

к к-1 Л(ЯГ) = kyXq(v¡) + kg • 2>0„+|), (1)

í=i /=1

где ку, кц - коэффициенты, характеризующие веса вершин и рёбер соответственно, ку > 0,кЕ> 0.

Вес решения g(z) равен суммарному весу носителя =

/

Структура оптимального носителя определяется деревом г = ЛГ( я,-, г), меченым конструкторами из семейства {К^, Кг,..., Для заданной структуры г его носители в работе называются решениями.

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

/»(/) = тт(Л(я,.)) (2)

п;„

ы

Хр.(ям,я,)£р.........(3)

где р„(т1/.ь я,-) - вычислительная сложность перехода от цепи тг,ч к цепи 7г„ получаемая как сумма вычислительных затрат на переходы из концевой вершины цепи лм в концевую вершину цепи я,-.

В разделе также поставлена частная задача исследования - задача оптимального ортогонального раскроя со сквозным резом:

Исходные данные: X, У- размеры листов материала (ресурсов); х,-, у,-, /и„ и, - длина, ширина, количество, ориентация ;'-й детали; п - суммарное количество деталей.

Целевая функция:

(

1

г) = т ах

(ЛГ-О-Л'-Г

(4)

V

где И-количество востребованных ресурсов, I</ <Ы.

Ограничения: раскрой - ортогональный, гильотинный.

Требуется найти: такое функциональное представление вероятности ранга выбора /-й детали Р(г,), при которой цепь выбора деталей п(п,к) = (Р(/-|),Р(г2),...,Р{>\)) максимизирует целевую функцию г|, где

к ~ количество деталей в полосе размещения.

В третьем разделе "Математическое обеспечение стохастической интеллектуальной системы" разработаны элементы структуры и формализованы правила функционирования стохастической интеллектуальной системы. Определён метод вероятностного поиска субоптимальных решений №-задач в терминах модели управления ресурсами. Недетерминизм функционирования данных систем заключается в неопределённости перехода состояний при потреблении единичного ресурса и,. /УР-полнота систем определяется тем, что граф переходов состояний таких систем гомоморфен дереву поиска решений. Интеллектуальность систем определяется наличием базы знаний правил компоновки карт раскроя (семейство конструкторов !{), которые являются, по сути, экспертными правилами базы знаний.

Структурная схема стохастического генератора цепей (рис.1),

содержит 1с последовательно соединённых комбинационных устройств, выполняющих операцию выбора ¡>cl \ (v;, G*1', C)-»(v,n, G""'), которая по случайной функции управления %,-ц, возвращающей ранг выбирает удовлетворяющую условиям С смежную к v, вершину v,h и усечённый граф <jt0\{t/,-}, а также к последовательно соединённых

комбинационных устройств, выполняющих операцию

& : (Jt(n,/), v,+i)-»(n(/i,/'+l)) поэлементного построения цепи т\{п,к).

Рисунок 1 - Структурная схема стохастического генератора цепей

Параметр Э геометрического распределения Р, = Э(1 - 9)' определяется на основании переменных п, к, i состояния дискретной системы. Блоки Р; па основании параметра 9 и номера шага решения i вычисляют разрешённую верхнюю границу ГПСЧ,. Генераторы псевдослучайных чисел ГПСЧ, функционируют на основании равномерного закона распределения целых чисел в диапазоне [0, ..., Р,].

На входы генератора ранжированных цепей поступают:

- начальная вершина v0. служащая корнем дерева переходов системы,

- условия С, налагаемые на носитель структуры п,

На выходах генератора выставляются:

- цепь Kj(/!,k),

- вес цепи/г(тг,).

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

Конвертер преобразует ранжированную цепь 7i(n,k) = [гь г2,..., гн] в цепь вершин п(п,к) = [vb v;, ..., vt] с целью последующего вычисления её веса Л(л') как суммы весов вершин и/или рёбер. Селектор субоптимальной цени сохраняет в своём регистре наилучшую текущую цепь я*, т.е. цепь с минимальным весом среди прочих построенных, и выдаёт сигнал на разрешение генерации следующей ранжированной цепи.

Рисунок 2 - Структурная схема генератора цепей в окрестности

ГО

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

В четвёртом разделе "Структура стохастической интеллектуальной системы" рассмотрены структура стохастической интеллектуальной системы и правила функционирования в режимах анализа и синтеза.

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

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

Рисунок 3 - Структурная схема интеллектуальной системы в режиме

анализа

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

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

Рисунок 4 - Структурная схема стохастической интеллектуальной системы в режиме синтеза

Новизну предлагаемого подхода к построению решателей №-задач определяет использование для управления поиском решения с

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

Достоинства вероятностного метода поиска субоптимальных ранжированных цепей:

• Отсутствие притяжения к локальным оптимумам.

• Большой объём поиска.

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

• Возможность останова либо по времени, либо по заданному объёму поиска, либо при достижении заданного порога веса решения.

• Возможность повторного запуска алгоритма.

• Недостатки вероятностного метода:

• Повтор наиболее вероятных субоптимальных решений.

• Эффективность решения пропорциональна времени работы алгоритма.

На рис.5 представлена структурная схема интеллектуальной стохастической системы для решения задачи ортогонального раскроя со сквозным резом. Описанная система была реализована программным способом в среде Visual Prolog 5.2. и внедрена на предприятии мебельной промышленности ООО "БАКАУТ" г. Краснодар в 2009 г.

Достигаемый коэффициент использования ресурсов па отдельных картах раскроя /7 = 97%, относительный полезный эффект в сравнении с

существующими многочисленными системами оптимизации 20СБР на мелко и среднесерийном производстве с большим ассортиментом деталей Д»7„рог - 3%, относительный полезный эффект в сравнении с ручным кроем -2 -М1 % в зависимости от размерности исходных данных. Время кроя сокращено в десятки раз по сравнению с ручным кроем. Рекомендация по условиям эффективного использования: мелко и среднесерийное производство, высокая стоимость ресурсов, большой производственный оборот.

Рисунок 5 - Структурная схема стохастической интеллектуальной системы ортогонального гильотинного раскроя

В заключение диссертации приведены основные результаты и выводы.

Основные выводы и результаты работы

1. Проведён сравнительный анализ общих методов решения ИР-задач дискретной оптимизации, а также специальных методов оптимизации раскроя-упаковки. На основании анализа сделан вывод о том, что один из перспективных путей решения №-задач оптимизации раскроя-упаковки - использование зависимости оценки веса субоптимальных решений от рангов локальных решений.

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

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

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

5. Произведена оценка эффективности использования стохастической интеллектуальной системы.

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

Публикации по теме диссертации

1. Ковель И.В. Вероятностный метод построения окрестности статистического глобального оптимума 1\РС-задач // Интеллектуальные технологии. 2010. №2 - с. 38-41.

2. Ковель И.В. Интеллектуальная система раскроя-упаковки с ранжированным управлением шириной поиска // Сборник трудов V Всероссийской научной конференции. «Информационные технологии в промышленности» Ниж. Новгород. 2008. с. 422-424

3. Ковель И.В., Марков В.Н. Метод адаптации весовых коэффициентов к исходным данным в задачах раскроя-упаковки // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. -с.105-110.

4. Ковель И.В. Синтез базы знаний прикладной интеллектуальной системы негильотинного раскроя-упаковки // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. - с.111-113.

5. Ковель И.В. Вероятностный способ перебора ранжированных решений задачи раскроя-упаковки // Сборник научных трудов НТК «Современные информационные технологий» Пенза. 2008. - с. 192-193.

6. Ковель И.В. Ключко В.И., Марков В.Н. Интеллектуальная система для приближённого решения прикладных ^С-задач // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. -с. 194-199.

7. Ковель И.В. Ключко В.И., Марков В.Н. Свойства пространства поиска решений в дискретных задачах управления невозобновляемыми ресурсами // Сборник трудов 7 Международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности», Санкт-Петербург. 2009. - с.397-398.

8. Ковель И.В. Управление шириной поиска в ранжированном пространстве решений // Сборник трудов 7 Международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности», Санкт-Петербург. 2009. - с.399-400.

9. Ковель И.В. Оценка ширины поиска в ранжированном пространстве решений // Сборник трудов VI Всероссийской научной конференции молодых ученых и студентов «Современное состояние и приоритеты развития фундаментальных наук в регионах» Анапа. 2009. с. 253-254.

10. Ковель И.В. Проблемный подход в преподавании дисциплины «Структуры и алгоритмы обработки данных» II Сборник научных трудов XVI Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». КубГТУ. 2009.

11. Ковель И.В. Интеллектуальная система с ранжированным деревом решений // Сборник трудов 8 Международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности», Санкт-Петербург. 2009. - с.24!-242

12. Ковель И.В. Способ логической адаптации весовых коэффициентов к исходным данным в задачах раскроя-упаковки // Сборник трудов V Всероссийской научной конференции молодых ученых и студентов «Современное состояние и приоритеты развития фундаментальных наук в регионах» Анапа. 2008. с. 117-118.

13. Ковель И.В. Проблемный подход в преподавании дисциплины «Системы искусственного интеллекта» // Сборник научных трудов XVI Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». КубГТУ. 2010.

Подписано н печать 14.01.2011. Печать трафаретная. Формат 60x84 1/16, Усл. псч. л. 1,35. Тираж 100 экз. Закат №422. ООО «Издательский Дом-Юг» 350072, г. Краснодар, ул. Московская 2, корп. «В», оф. В-120 тел. 8-918-41-50-571 e-mail: olfomenko@yandcx.ru Сайг: l\Up://id-yug.narod2.ru

ВВЕДЕНИЕ.

1 АНАЛИЗ МЕТОДОВ ОПТИМИЗАЦИИ ПОТРЕБЛЕНИЯ РЕСУРСОВ.

1.1 Характеристика вычислительной сложности.

1.2 Классы труднорсшасмых задач

1.3 Анализ общих методов приближенного решения.

1.4 Анализ специальных методов оптимизации раскроя-упаковки.

Выводы по главе

2 ПОС ТАНОВКА ЗАДАЧИ СТОХАСТИЧЕСКОГО ПОИСКА В ПРОСТРАНСТВЕ PAÍ ЖИРОВАННЫХ PEI ПЕНИЙ.

2.1 Исходные данные.

2.2 Представление решения ММрудпой задачи потребления ресурсов.

2.3 Пространство поиска цепей.

2.4 Стохастические ранжированные цепи.

2.5 Постановка задачи вероятностного поиска оптимального потребления ресурсов.

2.6 Частные задачи поиска оптимальных цепей.J.

Выводы по главе 2.

3 МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ СТОХАСТИЧЕСКОЙ ИНТЕЛ-ЛЕКУ ТАЛЬМОЙ сиси <;мы.

3.1 Недетерминированные интеллектуальные системы.

3.1.1 Операции модификации цепей.

3.1.2 Структура и правила работы недетерминированных интеллектуальных систем.

3.2 Функционирование недетерминированных интеллектуальных систем

3.2.1 Модель потребления ресурсов с регистром памяти состояния.

3.2.2 Генератор стохастических ранжированных цепей.

3.2.3 Описание алгоритмов поиска решений в терминах модели управления ресурсами с регистром памяти состояния.

3.2.4 Характеристики вычислительной сложности алгоритмов поиска решений на модели недетерминированной интеллектуальной системы.

Выводы по главе

4 СТРУКТУРА СТОХАСТИЧЕСКОЙ ИНТЕЛЛЕКТУАЛЬНОЙ СИСТЕМЫ

4.1 Функционирование интеллектуальной системы в режиме анализа решений

4.2 Функционирование стохастической интеллектуальной систем в режиме синтеза решений.

4.3 Постановка задачи ортогонального раскроя со сквозным резом.

4.4 Исследование распределений весов решений в зависимости от рангов локальных решений.

4.5 Определение параметров распределения рангов субоптимальных решений.:.

4.6 Оценка эффективности функционирования стохастической интеллектуальной системы.

4.7 Реализация прикладной интеллектуальной системы ортогонального раскроя со сквозным резом.

Выводы по главе 4.

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

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

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

1) Методы динамического программирования, основанные па принципе локальной оптимальности Бсллмана, пс содержат научно обоснованных критериев локализации субоптимальных решений в пространстве поиска МРС-задач.

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

3) Вероятностные алгоритмы (Монте-Карло, Лас-Вегас, Шсрвудские) не гарантируют стабильность решения 1\[РС-задач по причине возможного отказа или заведомо усреднённого результата.

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

Таким образом, диссертационная работа посвящена актуальным вопросам разработки структуры и правил функционирования интеллектуальной системы декомпозиции объектов на основе статистически определённой функции вероятности рангов локальных решений. Такой подход позволяет решать прикладные НРС-задачи оптимального потребления ресурсов путём выборки только субоптимальных по вероятности решений из окрестности глобального оптимума (ГО).

Целыо настоящей работы является оптимизация потребления ресурсов на основе использования статистически обоснованной функции вероятности рангов локальных решений из окрестности ГО.

Для достижения указанной цели в работе были поставлены и решены следующие задачи.

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

2. Представить ранжированные решения КРС-задач оптимизации потреблеI пия ресурсов функциями вероятности рангов локальных решений.

3. Разработать генератор стохастических ранжированных решений ЫРС-задач на основе генераторов псевдослучайных рангов локальных решений.

4. Разработать структуру стохастической интеллектуальной системы с ранжированными решениями.

5. Разработать методику определения диапазонов генерации рангов.

6. Оцепить эффективность использования интеллектуальной системы.

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

Объектом настоящего исследования являются системы декомпозиции объектов с певозобповляемыми ресурсами. Предмет исследования — вероятностиый поиск субоптимальных решений в пространстве состояний интеллектуальных систем.

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

- решение 1чПРС-задач потребления ресурсов представлено в ранжированной форме, в которой ранги локальных решений выражены функциями вероятности и реализованы генераторами псевдослучайных чисел, что позволяет использовать обоснованное распределение рангов для сокращения пространства поиска;

- механизм поиска решений в структуре интеллектуальной системы декомпозиции объектов реализован генератором ранжированных решений, что сокращает удельные вычислительные затраты на получение субоптимальпого решения;

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

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

- Метод вероятностного поиска ранжированных субоптимальных решений. Представление ранжированных решений КРС-задач декомпозиции объектов функциями вероятности рангов локальных решений позволяет использовать генераторы псевдослучайных чисел с геометрическим распределением для быстрого перебора субоптимальиых решений;

- Модель интеллектуальной системы. Использование генератора ранжированных решений с геометрическим распределением рангов сокращает удельные вычислительные затраты на получение субоптимальио! о решения в условиях ограниченного времени решения;

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

Теоретические положения работы внедрены в ООО "Бакаут" при разработке интеллектуальной системы оптимизации раскроя-упаковки плоских изделий мебельной промышленности. г'

Достоверность и обоснованность полученных результатов основывается па промышленной эксплуатации прикладной интеллектуальной системы ортогонального раскроя-упаковки па предприятии г. Краснодара ООО "Бакаут", а также компьютерными экспериментами по сравнению результатов решения ряда ЫРС-задач разработанной интеллектуальной системой и специализированными для этих задач методами.

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

ВАК РФ, 12 работ в сборниках трудов международных и Всероссийских конференций.

Диссертация выполнена на кафедре вычислительной техники и автоматизированных систем управления (ВТ и АСУ) ГОУ ВПО "Кубанский государственный технологический университет" (КубГТУ). Диссертация состоит из введения, четырёх разделов, заключения, списка использованных источников из 103 наименований и приложений, содержит 153 страницы машинописного текста и включает 21 рисуиок и 6 таблиц.

Выводы по главе 4

Для ряда задач двухмерного раскроя-упаковки найдены конструкторы структур в виде семейства уравнений над цепями. В задаче двухмерного гильотинного раскроя решения представлены семейством уравнений, гильотинно разделяющих области размещения — домены, при этом выбор размещаемых деталей осуществляется в пределах статистически обоснованной границы ранжированной окрестности локального оптимума для каждого шага оптимизации, что позволяет повысить коэффициент раскроя на А г/« 1,5%.

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

127

ЗАКЛЮЧЕНИЕ

1. В диссертации проведён сравнительный анализ общих методов решения ЫРС-задач дискретной оптимизации, а также специальных методов оптимизации раскроя-упаковки. На основании анализа сделан вывод о том^ что перспективный путь решения М^С-задач оптимизации раскроя-упаковки — использование зависимости оценки веса субоптимальных решений от рангов локальных решений. Это позволяет обоснованно сократить дерево поиска решений.

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

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

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

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

5. Произведена оценка эффективности использования стохастической иителлск 1 уальпой системы.

Для задачи двухмерного гильотинного раскроя введено рекурсивное описание схемы карт раскроя с использованием ранжированных цепей, что повысило коэффициент раскроя до величины ц « 97% для исходных наборов деталей с большим ассортиментом на одинаковых заготовках, и привело к превышению: среднего коэффициента раскроя по сравнению с существующими методами решения задач 2ПС8Р до А /; и 1,5% па отдельных листах.

Эксплуатация стохастической интеллектуальной системы раскроя-упаковки показала повышение коэффициента использования ресурсов па 11% по сравнению с ручной оптимизацией па исходных данных большой размерности.

Результаты теоретических и экспериментальных исследований легли в основу построения сюхастичсской интеллектуальной системы декомпозиции объектов па основе вероятностного выбора рангов локальных решений. Предложенный подход к построению интеллектуальных систем позволяет эффективно применять их при решении ряда ЫРС-задач оптимизации потребления материальных, энергетических и информационных ресурсов, допускающих субоптимальное решение: оптимизация плоского ортогонального и криволинейного раскроя-упаковки, распределение персонала и перевозок, размещения предприятий, управления производством, проектирование в области электроники и архитектуры, оптимальная декомпозиция площадей земельных участков при разработке земельного кадастра. Экспериментальные исследования показали повышение экономии ресурсов и сокращение времени технологического цикла декомпозиции, в чём и заключается практическая ценность работы.

1. Адамснко А.Н., Кучуков A.M. Логическое программирование и Visual Prolog. СПб.: БХВ-Петербург, 2003. - 992 с.

2. Акимов O.E. Дискретная математика: логика, группы, графы — 2-е .изд., доп. М.: Лаборатория базовых знаний, 2003. - 376 с.

3. Андерсон Джеймс А. Дискретная математика-и комбинаторика: Пер. с англ. — М. : Издательский дом «Вильяме», 2003. — 960 с.1

4. Ахо А., Хопкрофт Д.Э., Ульман Д.Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 276 с.

5. Беллмаи Р. Динамическое программирование. М.: ИЛ, 1960. - 412 с.

6. Беллмап Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. — 565 с.

7. Валсева А.Ф. Применение конструктивных эвристик в задачах раскроя упаковки // Информационные технологии. 2006. №11. Приложение. 24 с.

8. Валсева А.Ф. Применение метаэвристики муравьиной колонии к задачам двухмерной упаковки //Информационные технологии'. 2005. №10. с. 36-43.

9. Валесва А.Ф., Гаресв И.Р., Мухачева Э.А. Задача одномерной упаковки: рандомизированный метод динамического перебора с усечением // Информационные технологии. 2003. №10. Приложение. — 24 с.

10. Ващспко И.В. Марков В.Н. Идентификация NP-полпых систем // СовреIменпые информационные технологии: Сборник статей международной НТК.

11. Выпуск 5. Пенза. 2007. с. 103-107. '

12. Вептцсль Е.С. Исследование операций. — М.: Сов. Радио, 1972. — 362 с.

13. Вептцсль Е.С. Исследование операций: задачи, принципы, методология. — 2-е изд., стер. М.: Наука, Гл. ред. физ.-мат. лит., 1988. - 208 с.

14. Верхотуров М.А. Задача нерегулярного раскроя плоских геометрических объектов: моделирование и расчёт рационального раскроя // Информационные технологии. 2000. №5. с. 37-42.

15. Власспко A.B., Марков В.Н. Интеллектуальная NPC-систсма // Перспективы науки. 2010. №1(03). с.55-60.

16. Власспко A.B., Марков В.Н. Метод построения окрестности глобального оптимума NPC-задач на ранжированном дереве поиска решения // Программные продукты и системы. 2010. №1(89). с.6-10. ?.'

17. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПб.: Питер, 2001. - 384 с.

18. Гаврилова Т.А., Чсрвинская K.P. Извлечение и структурирование знаний для экспертных систем. — М.: Радио и связь, 1992. — 199 с.

19. Гашков С.Б., Чубариков В.Н. Арифметика. Алгоритмы. Сложность вычислений. 2-е изд., перераб. — М.: Высш. шк., 2000. 320 с.

20. Гери М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи. М.: Мир, 1982. - 416 с.

21. Гончаров E.H. Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения // Дискретный анализ и исследоваиие операций. 1999. Сер. 2. Т. 6. №1. с. 12-32.

22. Гэри М., Джонсон Д. Вычислительные машины и трудпорешаемыс задачи. -М.: Мир, 1982.-416 с.

23. Джойс М.Т. Пр01раммироваиие искусственного интеллекта в приложениях. Пер. с англ. М.: ДМК Пресс, 2004. - 312 с.

24. Дистсль Р. Теория графов. Новосибирск: Изд-во ИМ СО РАН, 2002.

25. Евстигнеев В.Л. О некоторых свойствах локальных алгоритмов на графах // Комбинаторно-алгебраические методы в прикладной математике. — Горький, 1983.-е. 72-105.

26. Гвсшгиеев В.Л. Применение теории графов в программировании. — М.: Паука, 1985. — 352 с.

27. Евстигнеев В.Л., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. Новосибирск: Паука, 1994.

28. Искусственный интеллект: В 3 кн. Кп. 1. Системы общения и экспертные системы: Справочник. / Под ред. Попова Э.В. М.: Радио и связь, 1990. - 464 с.

29. Искусственный интеллект: В З.кн. Кн. 2. Модели и методы: Справочник. / Под ред. Поспелова Д.Л. М.: Радио и связь, 1990. — 304 с.

30. Искусственный интеллект: В 3 кн. Кп. 3. Программные и аппаратные средства: Справочник / Под ред. Захарова В.Н., Хорошевского В.Ф. М.: Радио и связь, 1990.-368 с.

31. Исследования по прикладной теории графов / Под ред. Л.С. Алексеева. -Новосибирск: Наука, 1986.

32. Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. — Новосибирск: Наука, 1971. -299 с.

33. Касьянов В.П., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. 1104 с.

34. Ковель И.В. Интеллектуальная система раскроя-упаковки с ранжированным управлением шириной поиска // Сборник трудов V Всероссийской научной конференции. «Информационные технологии в промышленности» Пиж. Новгород. 2008. с. 422-424

35. Ковель И.В., Марков В.Н. Метод адаптации весовых коэффициентов к исходным данным в задачах раскроя-упаковки // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. — с. 105-110.

36. Ковель И.В. Синтез базы знаний прикладной интеллектуальной системы непшьотишюго раскроя-упаковки // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. — с. 111 -113.

37. Ковель И.В. Вероятностный способ перебора ранжированных решений задачи раскроя-упаковки // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. — с. 192-193.

38. Ковсль И.13. Кшочко В.И., Марков В.II. Интеллектуальная система для приближённого решения прикладных КРС-задач // Сборник научных трудов НТК «Современные информационные технологии» Пенза. 2008. — с. 194-199.

39. Ковсль И.В. Управление шириной поиска в ранжированном пространстве решений // Сборник трудов 7 Международной иаучио-ирактической конференции "Исследование, разработка и применение высоких технологий в промышленности», Санкт-Петербург. 2009. с.399-400.

40. Ковель И.В. Проблемный подход в преподавании дисциплины «Структуры и алгоритмы обработки данных» // Сборник научных трудов XVI Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». КубГТУ. 2009.

41. Ковсль И.В. Интеллектуальная система с ранжированным деревом решений // Сборник трудов 8 Международной паучпо-практичсской конференции

42. Исследование, разработка и применение высоких технологий в промышленности», Санкт-Петербург. 2009. — с.241-242

43. Ковель И.В. Вероя тностный метод построения окрестности статистического глобального оптимума ЫРС-задач // Интеллектуальные технологии. 2010. №2 -с. 38-41.

44. Ковель И.В. Проблемный подход в преподавании дисциплины «Системы искусственного интеллекта» // Сборник научных трудов XVI Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». Куб! ТУ. 2010.

45. Юпочко В.И., Марков В.Н. Решение ЫР-проблем в алгебре компактных контейнеров // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2005. Приложение №2. с. 54-58.

46. Юпочко В.И., Марков В.Н. Субоптимальные решения ЫР-задач за полиномиальное время // Информатика и управление: Труды КубГТУ. Том XXV. Краснодар. 2005. с. 153-156.

47. Кокотов В.З. Алгоритм плотного размещения разногабаритных элементов на плате // Информационные технологии. 1998. №11. с. 16-21.

48. Колмогоров А.П. Основные понятия теории вероятностей. М.: Паука, 1974.-371 с.

49. Кори Г, Корн Т. Справочник по математике (для научных работников и инженеров). Определения, теоремы, формулы. 6-е из/1., стер. СПб.: Издательство «Лань», 2003. - 832 е.

50. Кочетов Ю., Младепович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Сер. 2. 2003. Т. 10. №1. с. 11-43.

51. Кочетов Ю., Усмаиова А. Вероятностный поиск с запретами для задачи упаковки в контейнеры // XII Байкальская международная конференция. Иркутск. 2001. с. 22-27.

52. Лорьср Ж.-Л. Системы искусственного интеллекта: Пер. с франц. М.: Мир, 1991. - 568 с.

53. Люгср Дж.Ф. Искусственный интеллект: Стратегии и методы решения сложных проблем. 4-е изд.: Пер. с англ. — М.: Издательский дом «Вильяме», 2003.- 864 с.

54. Макконслл Дж. Основы современных алгоритмов. 2-е дополненное издание: Пер. с англ. -М.: Техносфера, 2004. 368 с.

55. Малпас Дж. Реляционный язык Пролог и его применение: Пер с англ. — М.: Паука, Гл. ред. физ.-мат. лит., 1990. —464 с.

56. Марков В.П. База знаний для негильотипиого раскроя-упаковки // Информационные технологии. 2007. №4. с. 17-23.

57. Марков В.Ы. Идентификация интеллектуальных NP-гюлных систем // Кибернетика и высокие технологии XXI века: Сборник трудов VIII Международной конференции. Воронеж. 2007. с. 114-122.

58. Марков В.Н. Принципы построения экспертной системы гильотинного раскроя // Информационные технологии. 2005. №4. с. 53-57.

59. Марков В.Н. Способ порождения эвристик для решения NP-трудных задач // Информационные технологии. 2006. №6. с. 21-25.

60. Молокова О.С., Уварова Т.Г. Методология анализа предметных знаний // Новости искусственного интеллекта. 1992. №3. с. 11-60.

61. Мухачева A.C., Чиглинцев A.B. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя // Информационные технологии. 2001. №3. с. 27-32.

62. Мухачева A.C., Чиглинцев A.B., Смагип М.А., Мухачева Э.А. Задачи двумерной упаковки: развитие генетических алгоритмов па базе смешанных процедур локального поиска оптимального решения // Информационные технологии. Приложение. 2001. №9.-24 с.

63. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. — М.: Машиностроение, 1984. 176 с.

64. Мухачева Э.А., Валссва А.Ф. Метод.; динамического перебора в задаче двумерной упаковки//Информационные технологии. 2000. №5. с. 30-37.

65. Мухачева Э.А., Валсева А.Ф., Картак В.М., Мухачева A.C. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор иновая технология блочных структур // Информационные технологии. 2004. №5. Приложение.

66. Мухачева Э.Л., Ермаченко Л.И., Сиразетдипов Т.М., Усманова А.Р. Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя // Информационные технологии. 2001. №6. с. 25-31.

67. Мухачева Э.А., Картак В.М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя // Информационные технологии. 2000. №9. с. 15-22.

68. Мухачева A.C., Курелеиков С.Х., Смагин М.А., Ширгазии P.P. Методы локального поиска оптимума прямоугольной упаковки с использованием двойственной схемы // Информационные технологии. 2002. №10. с. 26-3 1.

69. Мухачева Э.А., Мухачева A.C. Метод перестройки для решения задачи прямоугольной упаковки // Информационные технологии. 2000. №4. с. 30-36.

70. Мухачева Э.Л., Мухачева A.C., Белов Г.Н. Метод последовательного уточнения оценок: алгоритм и числсииыи эксперимент для задачи одномерного раскроя // Информационные технологии. 2000. №2. с. 11-17.

71. Мухачева ЭЛ., Мухачева A.C., Чиглшщсв A.B. Генетический алгоритм блочной структуры в задачах двумерной упаковки. // Информационные технологии. 1999. №11. с. 13-18.

72. Мухачева A.C., Ширгазии P.P. Задачи упаковки прямоугольников: рандомизированная эвристика па базе двойственной схемы локального поиска оптимума // Информационные технологии. 2003. №5. с. 18-23.

73. Осуга С. Обработка знаний: Пер. с япоп. — М.: Мир, 1989. — 293 с.

74. Норепков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации // Информационные технологии. 1999. №1. с. 2-7.

75. Норепков И.П., Косачевский О.Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации // Информационные технологии. 1999. №2. с. 2-8.

76. Поспелов Д.Л. Ситуационное управление. Теория и практика. М.: Наука, 1986.-284 с.

77. Построение экспертных систем: Пер. с англ. / Цод ред.Ф. Хсйеса-Рота, Д. Уотсрмапа, Д. Лсната. М.: Мир, 1987. - 441 с.

78. Приобретение знаний / Осуга С., Саэки Ю., Судзуки X. и др.: Пер. с япоп. -М.: Мир, 1990.-304 с.

79. Рейнгольд Э. Нивергельт Ю. Део Н. Комбинаторные алгоритмы: теория и практика. М.: Мир, 1980.

80. Свами М.П., Тхуласираман К. Графы, сети и алгоритмы: Пер. с аигл. — М.: Мир, 1984.-454 с.

81. Слиссико Д.О. Сложпостные задачи теории вычислений // Успехи мат. Паук. 1981. - Т. 36. № 6. - с. 21-103.

82. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог: — Пер. с англ. М.: Мир, 1990. - 235 с.

83. Taxa Х.А. Введение в исследование операций, 6-е изд.: М.: Издательский дом «Вильяме», 2001. - 912 с.

84. Толковый словарь по искусственному интеллекту / Аверкии Л.Н., Гаазе-Рапопорт М.Г., Поспелов Д.Л. М.: Радио и связь, 1992. — 256 с.

85. Уотермси Д. Руководство по экспертным системам: Пер. с англ. М.: Мир, 1989.-388 с.

86. Усманова А.Р. Вероятностные жадные эвристики для задачи упаковки в контейнеры. Спб: ОПТИМ-2001. с. 141-146.

87. Усманова Л.Р. Экспоненциальная окрестность решений для задачи упаковки в контейнеры//Информационные технологии. 2005. №6. с. 48-51.

88. Хопкрофт Д.Э., MoiBaira Р., Ульман Д.Д. Введение в теорию автоматов, языков и вычислений, 2-е изд.: — М.: Издательский дом «Вильяме», 2002. 528 с.

89. Чистяков В .П. Курс теории вероятностей. М.: Высш. школа, 1982. - 356 с.

90. Шайтхауэр Г., Мухачсва Л.С. Белов Г.П., Мухачсва Э.Л. Планирование одномерного раскроя материала различной длины на базе непрерывной релаксации и метода отсекающих плоскостей. // Информационные технологии. 2004. №1. с. 28-35.

91. Ясницкий JI.H. Введение в искусственный интеллект: Учеб. пособие для студ. вузов. М.: Издательский центр «Академия», 2005. — 176 с.

92. Belov G. Л branch-and price algorithm for one-and-two dimensional two-stage cutting (stock) problems // Technical report MATH-NM-03-03. Dresden University. 2003. url: http://www.math.tu-drcsden.de/~capad

93. Dorigo M. Ant Algorithms for Discrete Optimization, 1999. url: http://citeseer.nj.nec.con/420280.html

94. DykhofflL A typology of cutting and packing problems // European Journal of Operational Research. 1990. Vol. 141. P. 274-294.

95. Hopper E., Turton B. An empirical investigation of mcta-heuristic and heuristic algorithms for a 2D packing problem // EJOR. 2001. Vol. 128. P. 34-57.

96. Kendal 1G. Simulated Annealing, 2002.iurl: http://www.cs.nott.ac.ul<y~gxk/aim/notes/simulatedannealing.doc

97. Eiu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles // EJOR. 1999. Vol. 112. P. 413-420.

98. Eodi Д., Martcllo S., Vigo D. Heuristic and mcta-heuristic approaches for a class of two-dimensional bin packing problems Algorithms // INFORMS J. Comput. 1999. Vol. 11. P. 345-357.

99. Luke B.T. Simulated Annealing Cooling Schedule, 2001. url: http://membcrs.aol.com/btlukc/simanfl.htm

100. Shaffer II. Practical Guide to Genetic Algorithms, 1993. http://chemdiv-www.nrl.navy.mil/6110/6112/sensors/chemomctrics/practga.html142