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

• Автор: Ковель, Иван Владимирович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Краснодар
• Количество страниц: 153 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.

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

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

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

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

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

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

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

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

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

2.3 Пространство поиска цепей
2.4 Оюхасчичсскис ранжированные цени.
2.5 Постановка задачи вероятностного поиска оптимального потребления ресурсов.
2.6 Частные задачи поиска оптимальных цепей.
Выводы но главе 2
3 МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ СТОХАСТИЧЕСКОЙ ИНТЕЛЛЕКУТАЛЫЮЙ СИСТЕМЫ1.
3.1 Недетерминированные интеллектуальные системы.
3.1.1 Операции модификации цепей.
3.1.2 Структура и правила работы недетерминированных интеллектуальных систем
3.2 Функционирование недетерминированных интеллектуальных систем
3.2.1 Модель потребления ресурсов с регистром памяти состояния.
3.2.2 Генератор стохастических ранжированных цепей.
3.2.3 Описание алгоритмов поиска решений в терминах модели управления ресурсами с регистром памяти состояния
3.2.4 Характеристики вычислительной сложноеги алгоритмов поиска решений па модели недетерминированной интеллектуальной системы
Выводы по главе 3
4 СТРУКТУРА СТОХАСТИЧЕСКОЙ ИНТЕЛЛЕКТУАЛЬНОЙ СИСТЕМЫ .
4.1 Функционирование интеллектуальной системы в режиме анализа решений
4.2 Функционирование стохастической интеллектуальной систем в режиме синтеза решений
4.3 Постановка задачи ортогонального раскроя со сквозным резом.
4.4 Исследование распределений весов решений в зависимости от рангов локальных решений
4.5 Определение параметров распределения рангов субонтимальных решений
4.6 Оценка эффективности функционирования стохастической интеллектуальной системы
4.7 Реализация прикладной интеллектуальной системы ортогонального
раскроя со сквозным резом.
Выводы по главе 4.
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
ПРИЛОЖЕНИЯ
ВВЕДЕНИЕ


Объектом настоящего исследования являются системы декомпозиции объектов с псвозобиовлясмыми ресурсами. Результаты теоретических и экспериментальных исследований легли в основу построения интеллектуальной системы, позволяющей повысить экономию ресурсов и сократить время технологического цикла декомпозиции, в чем и заключается практическая ценность работы. Метод вероятноегного поиска ранжированных субонтимальных решений. Модель интеллектуальной системы. Методика определении диапазонов генерации рангов. Вероятность того, что последний ранг цепи равен единице, является нижней границей для вероятностей остальных рангов, что определяет верхнюю границу генерации рангов. Теоретические положения работы внедрены ООО Бакаут при разработке интеллектуальной системы оптимизации раскрояупаковки плоских изделий мебельной промышленности. Достоверность и обоснованность полученных результатов основывается па промышленной эксплуатации прикладной интеллектуальной системы ортогонального раскрояупаковки на предприятии г. Краснодара ООО Бакаут, а также компьютерными экспериментами по сравнению результатов решения ряда КРСзадач разработанной интеллектуальной системой и специализированными для э тих задач мет одами. Результаты исследований докладывались и обсуждались на международных и Всероссийских конференциях. ВАК РФ, работ в сборниках трудов международных и Всероссийских конференций. Диссертация выполнена на кафедре вычислительной техники и автоматизированных систем управления ВТ и АСУ ГОУ НПО Кубанский государственный технологический университет КубГТУ. Диссертация состоит из введения, четырех разделов, заключения, списка использованных источников из 3 наименований и приложений, содержит 3 страницы машинописного текста и включает рисунок и 6 таблиц. В современной теории алгоритмов известны доказательства нижних границ временной сложности для целого ряда задач дискретной оптимизации 4, . Результаты, полученные в области практической разработки алгорит
мов, позволяют указать наиболее асимптотически эффективные на данный момент алгоритмы. В связи с этим вычислительные задачи классифицируются как по чеорсзичсски доказанной нижней границе сложности задачи, если такопая известна или по тривиальной эвристической нижней границе,гп сложности задачи, так и по сложности 7 наилучшего для данной задачи алгоритма 1,, п размерность входных данных. Под сложностью алгоритма понимается верхняя граница числа операций, необходимых для получения результата , . По скорости роста сложности различают три класса алгоритмов , , . Класс Р составляют задачи, имеющие полиномиальную границу временной сложности и решаемые полиномиальными алгоритмами 4, . Этот класс задач довольно узок. Сортировка множества из п чисел. Поиск эйлерова цикла на рафс из п рбер. Поиск в списке заданного подсписка. Построение покрывающего дерева минимальной стоимости. Поиск кратчайшего пути па графе. Поиск связанных компонент. Транзитивное замыкание. Максимальное паросочетапис. Максимальный ноток па графе. Проверка планарности графов. Задачи линейного программирования. Из них задачи 4, 5, 8, 9 относятся к задачам дискретной оптимизации и
моуг иметь прикладную постановку как задачи оптимального потребления ресурсов. Однако на практике класс задач, не решаемых за полиномиальное время намного шире класса полиномиальных задач. Класс Б содержит задачи, имеющие экспоненциальную границу временной сложности и решаемые экспоненциальными алгоритмами 4, . Комбинаторный перебор альтернатив в общем случае представляется экспоненциальной функцией Г где Г константа или полином от п. Для наглядного сравнения классов Р и В в таблицах 1. Существенные отличия наступают уже при п , когда большинство экспоненциальных алгоритмов не применимо изза большой продолжительности их работы. Таблица 1. Класс Функция сложности Время сек. С другой стороны, полиномиальные алгоритмы со сложностью я0 или 1 0УУ 2 тоже не могут считаться эффективными. Наряду с этим существуют экспоненциальные алгоритмы, хорошо зарекомендовавшие себя на практике еи.