Введение к работе
Оптимальное распределение и потребление ресурсов является одним из определяющих факторов в жизни современного общества. Для ряда задач оптимизации потребления материальных, энергетических и информационных ресурсов характерен такой отличительный признак как принадлежность к классу NPC-задач, допускающих приближённое решение. Представителями указанного класса задач являются задачи оптимизации плоского ортогонального и криволинейного раскроя-упаковки, распределения персонала, перевозок, размещения предприятий, управления производством, а также проектирование в области электроники и архитектуры.
С одной стороны для решения NPC-задач дискретной оптимизации с произвольной размерностью исходных данных в настоящее время не существует методов получения точного решения за время, ограниченное техническими условиями функционирования информационной системы или продолжительностью технологических операций. Поэтому суть современных методов заключается в выборе лучшего варианта при проверке чрезвычайно узкого подмножества всех возможных альтернатив в надежде на то, что ошибка найденного решения не слишком велика и решение будет субоптимальным. При этом величина ошибки приближённого решения принципиально не определяема. Сформированные к настоящему времени направления исследований в этой области имеют ряд особенностей.
1) Методы динамического программирования, основанные на принципе локальной оптимальности Беллмана, не содержат научно обоснованных критериев локализации субоптимальных решений в пространстве поиска NPC-задач.
2) Эвристики ограничения перебора дерева решений (имитация отжига, муравьиная колония, генетические алгоритмы и др.) в большей мере определяются творческими способностями и талантом исполнителя, нежели формализмами указанных алгоритмов.
3) Вероятностные алгоритмы (Монте-Карло, Лас-Вегас, Шервудские) не гарантируют стабильность решения NPC-задач по причине возможного отказа или заведомо усреднённого результата.
С другой стороны современная вычислительная техника, благодаря недостижимому ранее быстродействию, позволяет исследовать NPC-задачи оптимизации декомпозиции малой размерности, выявлять закономерности распределения субоптимальных решений в пространстве решений, строить на их основе статистически обоснованные эвристики управления поиском, и, полагаясь на то, что выявленные закономерности сохраняются в задачах с большой размерностью исходных данных, использовать найденные эвристики в практике оптимизации декомпозиции объектов с произвольной размерностью.
Таким образом, диссертационная работа посвящена актуальным вопросам разработки структуры и правил функционирования интеллектуальной системы декомпозиции объектов на основе статистически определённой функции вероятности рангов локальных решений. Такой подход позволяет решать прикладные NPC-задачи оптимального потребления ресурсов путём выборки только субоптимальных по вероятности решений из окрестности глобального оптимума (ГО).
Целью настоящей работы является оптимизация потребления ресурсов на основе использования статистически обоснованной функции вероятности рангов локальных решений из окрестности ГО.
Для достижения указанной цели в работе были поставлены и решены следующие задачи.
-
Провести анализ методов оптимизации потребления ресурсов.
-
Представить ранжированные решения NPC-задач оптимизации потребления ресурсов функциями вероятности рангов локальных решений.
-
Разработать генератор стохастических ранжированных решений NPC-задач на основе генераторов псевдослучайных рангов локальных решений.
-
Разработать структуру стохастической интеллектуальной системы с ранжированными решениями.
-
Разработать методику определения диапазонов генерации рангов.
-
Оценить эффективность использования интеллектуальной системы.
Для решения поставленных задач в диссертации использованы методы системного анализа, дискретной оптимизации, теории автоматов и вычислений, теории вероятностей и математической статистики, теории графов, теории множеств.
Объектом настоящего исследования являются системы декомпозиции объектов с невозобновляемыми ресурсами. Предмет исследования – вероятностный поиск субоптимальных решений в пространстве состояний интеллектуальных систем.
Научная новизна работы заключается в следующем:
решение NPC-задач потребления ресурсов представлено в ранжированной форме, в которой ранги локальных решений выражены функциями вероятности и реализованы генераторами псевдослучайных чисел, что позволяет использовать обоснованное распределение рангов для сокращения пространства поиска;
механизм поиска решений в структуре интеллектуальной системы декомпозиции объектов реализован генератором ранжированных решений, что сокращает удельные вычислительные затраты на получение субоптимального решения;
разработана методика определения диапазонов генерации рангов, заключающаяся в определении верхней границы изменения рангов и ограничения диапазона изменения его значений.
Результаты теоретических и экспериментальных исследований легли в основу построения интеллектуальной системы, позволяющей повысить экономию ресурсов и сократить время технологического цикла декомпозиции, в чём и заключается практическая ценность работы.
Положения, выносимые на защиту:
Метод вероятностного поиска ранжированных субоптимальных решений. Представление ранжированных решений NPC-задач декомпозиции объектов функциями вероятности рангов локальных решений позволяет использовать генераторы псевдослучайных чисел с геометрическим распределением для быстрого перебора субоптимальных решений;
Модель интеллектуальной системы. Использование генератора ранжированных решений с геометрическим распределением рангов сокращает удельные вычислительные затраты на получение субоптимального решения в условиях ограниченного времени решения;
Методика определения диапазонов генерации рангов. Вероятность того, что последний ранг цепи равен единице, является нижней границей для вероятностей остальных рангов, что определяет верхнюю границу генерации рангов.
Теоретические положения работы внедрены в ООО “Бакаут” при разработке интеллектуальной системы оптимизации раскроя-упаковки плоских изделий мебельной промышленности.
Достоверность и обоснованность полученных результатов основывается на промышленной эксплуатации прикладной интеллектуальной системы ортогонального раскроя-упаковки на предприятии г. Краснодара ООО “Бакаут”, а также компьютерными экспериментами по сравнению результатов решения ряда NPC-задач разработанной интеллектуальной системой и специализированными для этих задач методами.
Апробация и публикации. Результаты исследований докладывались и обсуждались на международных и Всероссийских конференциях. Результаты диссертации опубликованы в 13 работах, из них одна в ведущем периодическом издании, рекомендованном ВАК РФ, 12 работ в сборниках трудов международных и Всероссийских конференций.
Структура и объём диссертации. Диссертация состоит из введения, четырёх разделов, заключения, списка использованных источников из 103 наименований и приложений, содержит 153 страницы машинописного текста и включает 21 рисунок и 6 таблиц.
