Введение к работе
Актуальность Рост потребления ресурсов является одним из определяющих факторов в жизни современного общества Для ряда задач оптимизации потребления ресурсов характерны такие отличительные признаки как принадлежность к NP-полным и более сложным задачам, а также допустимость приближенного решения Представителями указанного класса задач являются задачи оптимизации раскроя-упаковки, распределения персонала, перевозок, размещения предприятий, управления произведет-
4 вом, а также проектирование в области электроники и архитектуры и др
С одной стороны для решения NP-полных задач дискретной оптимизации с произвольной размерностью исходных данных в настоящее время не существует методов получения точного решения за время, ограниченное техническими условиями функционирования информационной системы или продолжительностью технологических операций Поэтому суть современных методов заключается в выборе лучшего варианта при проверке чрезвычайно узкого подмножества всех возможных альтернатив в надежде на то, что ошибка найденного решения не слишком велика и решение будет субоптимальным При этом величина ошибки приближённого решения принципиально не определяема Сформированные к настоящему времени направления исследований в этой области имеют ряд особенностей I) Методы динамического программирования, основанные на принципе локальной оптимальности Беллмана, не содержат обоснованных критериев локализации субоптимальных решении в пространстве поиска 2) Существующие методы управления поиском в пространстве решений (имитация отжига, муравьиная колония, генетичес кие алгоритмы и др ) в разной мере используют математическую конструкцию цепей Маркова и сводятся к описанию состояния вычислительной модели уравнениями Колмогорова При этом поиск эвристик и метаэвристик ограничения перебора не формализован, является своего рода искусством и определяется творческими способностями и талантом исполнителя 3) Вероятностные методы не гарантируют стабильность решения по причине возможного отказа или заведомо усредненного результата
С другой стороны современная вычислительная техника, благодаря недостижимому ранее быстродействию, позволяет исследовать NP-полные задачи на данных сравнительно малой размерности, выявлять закономерности распределения оптимальных решений в пространстве поиска решений для целых классов прикладных задач, синтезировать на их основе статистически обоснованные эвристики управления поиском, и, полагаясь на
5 то, что выявленные закономерности сохраняются в задачах с большой размерностью исходных данных, использовать найденные эвристики в практике решения NP-полных задач с произвольной размерностью
Таким образом, диссертационная работа посвящена актуальным вопросам разработки теоретических основ построения интеллектуальных систем, обеспечивающих эффективное решение прикладных NP-полных задач оптимального потребления ресурсов произвольной природы путем локализации субоптимальных решений в окрестности статистического глобального оптимума, а также путем повышения многообразия форм представления решений
Цель: оптимизация потребления ресурсов на основе разработки специальной теории синтеза интеллектуальных систем дискретной оптимизации
Задачи:
-
Декомпозиция формы представления решений NP-полных задач дискретной оптимизации потребления ресурсов на компоненты и независимое исследование влияния каждого компонента на вес субоптимальных решений и их распределение в пространстве поиска
-
Введение метрики в пространство поиска решений и экспериментальное исследование распределения оптимальных решений
-
Идентификация свойств пространства поиска и разработка методов эффективного поиска субоптимальных решений на основе расширения окрестности статистического глобального оптимума (СГО) с минимальными вычислительными затратами
-
Разработка основ теории синтеза интеллектуальных NP-полных систем
-
Разработка методов синтеза прикладных интеллектуальных NP-полных систем и конструкторов решений задач 2DCSP, 2DBPP и нестинга
-
Оценивание эффективности использования интеллектуальных NP-полных систем по технико-экономическим показателям
Методы исследования В диссертации использованы методы системного анализа, дискретной оптимизации, теории автоматов и вычислений, теории вероятностей и математической статистики, теории чисел, теории фафов, теории множеств, а также многосортные алгебры и исчисление предикатов
Объект исследования дискретные системы оптимизации потребления ресурсов
Предмет исследования оптимальный поиск субоптимальных решений в пространстве состояний дискретных систем
Проблемные факторы экспоненциальный рост вычислительной сложности, отсутствие модели представления решений в формальной постановке прикладных NP-полных задач, отсутствие метрики пространства поиска и теоретических оценок распределения оптимальных решений в нем, величина ошибки субоитимальных решений принципиально не определяема
Научная новизна Все теоретические результаты и обобщения получены на основе исследования пространства поиска, представленного в новой двухкомпонентной форме - в виде ранжированных цепей переходов состояний дискретной системы и многообразия структур решений, адаптированных для ряда задач раскроя-упаковки
В работе впервые
- произведена декомпозиция структур представления решений на два
независимых компонента 1) носитель структур в виде ранжирован
ных цепей переходов состояний дискретной системы и 2) конструк
тор структур в виде семейства уравнений над носителем, что позво
лило исследовать влияние и получить закономерности вклада каждо
го компонента в оценку веса оптимальных решений и их распределе
ние,
— на основе интерпретации ранжированных цепей как чисел фактори-
альной системы счисления с рангами переходов в качестве значений
7 разрядов и шагом оптимизаци л в качестве индексов разрядов введена метрика пространства поиска с двумя координатами - ранг перехода и шаг оптимизации, что позволяет посредством алгебраических операций оценивать расстояние между двумя произвольными состояниями, вычислять удаление от статистического глобального оптимума, а также задавать размеры области поиска функциями от указанных координат;
функция вероятности групп оптимальных цепей с равной суммой рангов аппроксимирована распределением Пуассона, случайная функция рангов на каждом шаге оптимизации - геометрическим распределением, на основе чего сформулирован ряд закономерностей локализации субоптимальных решений,
найдена декомпозиция пространства поиска на упорядоченную последовательность непересекающихся областей по признаку равенства суммы весовых коэффициентов факториальных форм цепей, что привело к монотонному уменьшению вероятности наличия оптимального решения в последовательности проверяемых областей,
найдена оценка веса ранжированных цепей в виде аддитивной функции от отношения ранга перехода к шаг)' оптимизации, которая позволяет обоснованно задавать ширину поиска на дереве решений, а также определен нижний порог этой оценки, определяющий направление на локальный и глобальный оптимум в пространстве поиска,
для ряда задач двухмерного раскроя-упаковки и несгинга найдены конструкторы структур в виде семейства уравнений над цепями, а также методы повышения многообразия решений на основе кортежей экспертных коэффициентов введенных структурных характеристик карт раскроя, благодаря чему оценки карт раскроя перераспределяются в пользу тех карт, которые содержат крупногабаритные детали и остатки, что в целом увеличивает коэффициент раскроя-упаковки, даже за счет его уменьшения на отдельных ^рта\ раскроя.
8 при этом полученная зависимость структурных показателей карт раскроя от разнообразия размеров исходных данных позволяет автоматически адаптировать стратегию раскроя к конкретным исходным данным
Достоверность и обоснованность научных положений основывается на многолетней промышленной эксплуатации прикладных интеллектуальных систем ортогонального раскроя-упаковки и нестинга на предприятиях г Краснодара и Краснодарского края, а также на сравнении результатов компьютерного эксперимента по решению ряда NP-полных задач интеллектуальной NP-полной системой и специализированными для этих задач методами
Практическая значимость и внедрение Результаты теоретических и экспериментальных исследований легли в основу построения интеллектуальных систем, позволяющих существенно повысить экономию ресурсов и сократить время технологического цикла производства
Интеллектуальная система оптимального раскроя плоских материалов (ДСП, ДВП, МДФ, фанера, ст екло и др ) со сквозным резом внедрена в г Краснодаре в компании "СБС", ООО ПКП "БАКАУТ" и мебельных предприятиях Краснодарского края.
Интеллектуальная система упаковки плоских криволинейных материалов из природных минералов и полудрагоценных камней внедрена в г КрасЕюдаре на предприятии "Хозяйка медной горы" Основные положения, выносимые на защиту - метрика пространства поиска решений, основанная на представлении носителя структуры решений в виде факториальных форм цепей, дает возможность посредством алгебраических операций вычислять координаты нового состояния, удаленного от текущего на заданное расстояние, задавать рекуррентный перебор субоптимальных решений и регулировать размеры области поиска, при этом факториаль-
9 пая форма цепи, ведущая к статистическому глобальному оптимуму, соответствует принципу оптимальности Беллмана,
методы построения окрестностей глобального оптимума, основанные на свойствах пространства поиска решений, основными из которых являются случайная функция ранга шага оптимизации, аппроксимированная геометрическим распределением и функция вероятности групп ранжированных цепей с равной суммой рангов, аппроксимированная распределением Пуассона, позволяют для заданной размерности исходных данных и длины цепи обоснованно определять наиболее вероятные координаты субоптимальных решений,
метод расширения ранжированной окрестности, использующий оценку приращения веса ранжированной цепи в виде функции от отношения ранга перехода к его индексу, позволяет по заданному превышению над нижним порогом оценочной функции точно определять наиболее вероятные координаты субоптимальных решений,
метод оптимизации раскроя по явно введенным в целевую фунь цию структурным показателям карт раскроя, использующим нелинейные оценки веса решений от размеров деталей и остатков, позволяет избегать притяжения локальных оптимумов при поиске глобального,
метод автоматической адаптации интеллектуальной системы к исходным данным, основанный на преобразовании декартова произведения показателей крупности деталей и их разнообразия в кортежи весовых коэффициентов, задающих приоритеты структурных и неструктурных показателей карт раскроя, позвоіяет повысить коэффициент раскроя-упаковки за счет автоматического выбора наилучших стратегий раскроя для заданного набора деталей и материалов,
модель карт двухмерного гильотинного раскроя, представленная в виде семейства рекурсивных уравнечий, гильотинно разделяющих по одной и двум координатам области размещения на слои и домены соответственно, при этом выбор размещаемых деталей осуществля-
10 ется в пределах статистически обоснованной границы ранжированной окрестности локального оптимума для каждого шага оптимизации, что позволяет увеличить многообразие представления компонентов субоптимальных карт раскроя и за счет этого повысить коэффициент раскроя, - модель карт двухмерной негильотинной упаковки, представленная криволинейной трапецией и ортогональной ломаной линией реза, а также модель конструктора структур карт раскроя, представленная иерархической системой уравнений, осуществляющих декомпозицию пространства поиска решений на страты, модели карты раскроя — на домены, а множества исходных данных - на подмножества по заданным критериям, а также синтез решения путем композиции указанных компонентов, что повышает коэффициент упаковки Апробация. Результаты исследований докладывались и обсуждались на международных симпозиумах и конференциях, в том числе за рубежом
Публикации. Результаты диссертации опубликованы в 21 работе, из них шесть в ведущих периодических изданиях, рекомендованных ВАК РФ, четыре статьи в сборниках трудов ВУЗов, 11 работ в сборниках трудов международных симпозиумов и конференций
Структура и объём диссертации. Диссертация состоит из введения, шести глав, заключения и приложений Общий объем работы 370 страниц Основная часть диссертации содержит 322 страницы машинописного текста, в том числе 51 рисунок и 16 таблиц Список использованных источников включает 242 наименования Приложения приведены на 48 страницах
