Идентификация и синтез интеллектуальных NP-полных систем

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

1. ОБЩАЯ ПОСТАНОВКА ПРИКЛАДНЫХ МРПОЛНЫХ ЗАДАЧ С НЕЯВНОЙ ФОРМОЙ ПРЕДСТАВЛЕНИЯ РЕШЕНИЯ.

1.1. Класс ЫРполных задач, допускающих приближенное решение

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

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

1.2. Анализ методов решения ИРполных задач

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

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

1.3.1Остановка задачи оптимального поиска решения

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

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

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

1.3.4 Постановка задачи оптимального потребления ресурсов
1.3.5 Частные задачи поиска оптимальных цепей
Выводы по главе 1
2 НЕДЕТЕРМИНИРОВАНЫЕ ЫРИОЛНЫЕ СИСТЕМЫ.
2.1 Идентификаторы недетерминированных ЫРполных систем
2.1.1 Алгебра цепей
2.1.2 Идентификаторы недетерминированных МРиолных систем
2.2 Идентификация недетерминированных ЫРполных систем.
2.2.1 Модель потребления ресурсов со стековой памятью состояний
2.2.2 Описание типовых алгоритмов поиска решений в терминах модели управления ресурсами со стековой памятью.
2.2.3 Характеристики вычислительной сложности алгоритмов поиска решений на модели ЫРполной системы
Выводы по главе
3 АППАРАТ ФАКТОРИАЛЬНЫХ ФОРМ ЦЕПЕЙ.
3.1 Ранжированные цепи.
3.1.1 Ранжирование окрестности концевой вершины цепи.
3.1.2 Ранжирование окрестности состояния дискретной системы
3.1.3 Ранжирование цепей.
3.1.4 Ранжированный граф переходов дискретной системы
3.2 Факториальная форма представления цепей
3.2.1 Арифметизация ранжированных цепей с переменным количеством разрядов
3.2.2 Факториальная форма цепей
3.2.3 Восстановление ФФЦ цепей по индексу
3.3 Алгебра ранжированных цепей
3.3.1 Алгебра факториальных форм ранжированных цепей.
3.3.2 Метрика пространство поиска
Выводы по главе
4 ОСНОВЫ ТЕОРИИ СИНТЕЗА ИНТЕЛЛЕКТУАЛЬНЫХ ИРПОЛНЫХ СИСТЕМ
4.1 Синтез структуры интеллектуальных ЫРполных систем
4.1.1 Режим анализа решений ПЗ.
4.1.2 Режим синтеза решений ПЗ
4.2 Анализ решений 3
4.2.1 Исследование распределений весов решений
4.2.2 Свойства пространства поиска.
4.2.3 Методы построения окрестностей СТО
4.3 Метод расширения ранжированной окрестности статистического глобального оптимума.
4.3.1 Приведнное приращение весовой функции
4.3.2 Оценка весовой функции
4.3.3 Расширение ранжированной окрестности СТО
4.3.4 Оценка состояний дискретной системы по уравнениям состояний Колмогорова.
4.3.5 Оценка эффективности метода расширения ранжированной окрестности
Выводы по главе 4.
5 МЕТОДЫ СИНТЕЗА ПРИКЛАДНЫХ ИНТЕЛЛЕКТУАЛЬНЫХ ЫРПОЛНЫХ СИСТЕМ
5.1 Метод оптимизации по структурным показателям.
5.2 Метод адаптации весовых коэффициентов к исходным данным
5.3 Метод повышения многообразия решений.
Выводы по главе 5
6 СИНТЕЗ ПРИКЛАДНЫХ 1МРПОЛНЫХ СИСТЕМ
6.1 Синтез интеллектуальных ЫРполных систем ортогонального гильотинного раскрояупаковки.
6.1.1 Послойные схемы
6.1.2 Доменные схемы.
6.1.3 Оценка вычислительной сложности
6.1.4 Реализация интеллектуальной системы 2БС5Р
6.2 Синтез интеллектуальных ЫРполных систем ортогонального негильотинного раскрояупаковки.
6.2.1 Модель раскраиваемого материала
6.2.2 Иерархия правил базы знаний
6.2.3 Оценка вычислительной сложности
6.2.4 Реализация интеллектуальной системы ВРР
6.3 Синтез интеллектуальных ЫРполных систем криволинейного раскроя 5 Выводы по главе 6
ЗАКЛЮЧЕНИЕ.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.
ПРИЛОЖЕНИЯ.
ВВЕДЕНИЕ


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