Поисковые алгоритмы решения задач условной псевдобулевой оптимизации

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

Содержание
Введение

1 Постановка задачи. Необходимый математический аппарат

1.1 Состояние проблемы

1.2 Свойства пространства булевых переменных

1.3 Классы псевдобулевых функций

1.4 Постановка задачи оптимизации

1.5 Свойства множества допустимых решений задачи

1.6 Идентификация свойств псевдобулевых функций

1.6.1 Применение регулярного алгоритма оптимизации для идентификации свойств

1.6.2 Идентификация свойств посредством квадратичной аппроксимации

1.6.2.1 Способы квадратичной аппроксимации псевдобулевых функций
1.6.2.2 Определение свойств квадратичной функции Выводы
2 Эффективность известных методов решении задач условной пссвдобулсвой оптимизации
2.1 Составление обобщенной функции со штрафом
2.2 Регулярные точные алгоритмы безусловной оптимизации
2.3 Локальный поиск
2.3.1 Алгоритмы локального поиска для оптимизации псевдобулевых функций
2.3.2 Локальный поиск для условной оптимизации
2.4 Схема метода ветвей и границ
2.4.1 Общая схема метода ветвей и границ
2.4.2 Алгоритм метода ветвей и границ для задачи с неявно заданными функциями
2.4.3 Приближенные алгоритмы метода ветвей и границ
2.4.4 Условная оптимизация изотонных псевдобулевых функций Выводы
3 Регулярные точные процедуры оптимизации, реализующие свойства классов задач
3.1 Классы задач условной псевдобулевой оптимизации
3.1.1 Свойства функций ограничений
3.1.2 Свойства целевых функций
3.2 Алгоритмы псевдобулевой оптимизации со структурно монотонными целевыми функциями и функциями ограничений
3.3 Алгоритмы псевдобулевой оптимизации с монотонными функциями ограничений
3.3.1 Случай монотонной целевой функции
3.3.2 Случай унимодальной целевой функции
3.3.3 Случай целевой функции общего вида
3.4 Алгоритмы псевдобулевой оптимизации с унимодальными функциями ограничений
3.4.1 Случай монотонной целевой функции
3.4.2 Случай унимодальной целевой функции
3.4.3 Случай целевой функции общего вида
3.5 Алгоритмы псевдобулевой оптимизации с функциями ограничений общего вида
3.5.1 Случай монотонной целевой функции
3.5.2 Случай унимодальной целевой функции
3.5.3 Случай целевой функции общего вида
3.6 Системьгограничений Выводы
4 Приближенныдалгоритмы условной псевдобулевой оптимизации
4.1 Случайный поиск граничных точек
4.2 Гриди алгоритмы
4.2.1 Основные принципы и обоснование гриди эвристики
4.2.2 Гриди алгоритмы для условной псевдобулевой оптимизации
4.2.3 Оценка точности гриди алгоритмов
4.3 Адаптивный случайный поиск
4.4 Экспериментальные исследования приближенных алгоритмов 8 Выводы
Заключение
Список использованных источников


Построенная схема ветвления по подкубам исключает неперспективные подкубы при минимальных вычислительных затратах; основанный на этой схеме алгоритм метода ветвей и границ не требует явного задания функций. Алгоритм- случайного поиска граничных точек с адаптацией, представляющий собой объединение случайного поиска граничных точек и гриди эвристики, является более эффективным, чем каждый из них отдельно. Апробации работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на всероссийских конференциях «Решетневские чтения» (- гг. САКС-” (г. Красноярск), на ХЬ международной^ научной конференции “Студент и научно-технический ^ прогресс” (г. Интеллектуальнкте- системы 1МТЕЬ8’» (г. Калуга), на всероссийских конференциях «Туполевские чтения» (г. Казань) в - гг. Совершенствование технологии поиска и разведки, добычи и переработки полезных ископаемых» (г. Красноярск) в году, на всероссийской научной конференции «Королевские чтения» (г. Самара)- в г. Наука. Технологии. Инновации» (г. Новосибирск) в г. Основные положения диссертационной работы и работа в целом обсуждались на научных семинарах кафедры системного анализа и исследования -операций Сибирского государственного аэрокосмического университета. ПубликацшиЛЗо теме диссертации автором опубликовано девятнадцать работ. Структура и объем работы. Диссертация изложена на 1 странице машинописного текста. Состоит из введения, четырех глав, заключения и списка использованных источников, содержащего 6 наименований. Постановка задачи. Вещественные функции, определенные на множестве булевых переменных, по аналогии с булевыми функциями принято называть псевдобулевыми [1]. Соответственно задачи оптимизации: псевдобулевых функций называются задачами псевдобулевой оптимизации. Многие проблемы в экономике, банковском деле, промышленности, а также проблемы управления сложными техническими объектами приводят к необходимости решения- задач условной оптимизации с булевыми переменными. В [] рассматривается проблема автоматизации планирования товарного ассортимента торговых предприятий, которая сводится к решению многокритериальной задачи псевдобулевой оптимизации с ограничениями. Задача нахождения-набора кредитных заявок (задача формирования кредитного портфеля банка) в [] решается как поток задач условной оптимизации псевдобулевых функций. Для ее решения построен ряд оптимизационных моделей, в которых максимизируется критерий надежности с учетом стоимостного ограничения. Структура определяется набором булевых переменных, по которым и происходит максимизация критерия. В основном для решения таких задач нашли применение алгоритмы случайного поиска, например, алгоритмы схемы МИВЕР 0, 1]. Псевдобулевые функции играют важную роль в оптимизационных моделях в различных областях, таких как проектирование [I, , , , 9], теория надежности [7], теория вычислительных систем [8], статистика (классификация) [2, 3], экономика [2], финансы [6, 5, 6], менеджмент (выбор проекта [3]), исследование операций [3, 9,. Помимо задач оптимизации, псевдобулевые функции также появились во многих других моделях, представляющих интерес в настоящее время. Они составляют, к примеру, основной объект исследования в теории кооперативных игр, где они рассматриваются как характеристические функции игр с побочными платежами [, , 8, 0, 1, 3, 6]. Они* встречаются в. Впервые задачи-, псевдобулевой оптимизации подробно исследовались в монографии [1]. В этой работе также были1 разработаны методы решения аналитически заданных задач псевдобулевой оптимизации. В работе ^] псевдобулевые функции рассматриваются как функции множеств, т. Функции множеств зачастую рассматриваются заданными» алгоритмом, способным» выдавать их значения, для любого подмножества заданного конечного исходного множества. В некоторых задачах функция множества может быть определена аналитическим выражением, что является весьма благоприятным случаем. Явное задание функций множеств делает возможным применение большого числа методов для их анализа и оптимизации.