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

Описание

Перевод названия: Search Algorithms for Constrained Pseudo-Boolean Optimization

Тип публикации: статья из журнала

Год издания: 2016

Ключевые слова: Pseudo-Boolean functions, optimization, random search, greedy algorithm, regular optimization algorithm, псевдобулевые функции, оптимизация, случайный поиск, гриди алгоритм, регулярный алгоритм оптимизации

Аннотация: Постановка проблемы: рассматриваются задачи оптимизации вещественных функций бинарных переменных - так называемые задачи псевдобулевой оптимизации. В большинстве практических задач на комбинации значений переменных накладываются ограничения, сужающие множество допустимых значений управляющих переменных. В то же время эти ограничениПоказать полностьюя, как и сама целевая функция, зачастую обладают конструктивными свойствами, учет которых в процессе оптимизации способен повысить эффективность решения таких задач. Кроме того, во многих реальных задачах оптимизации часть функций (критерии и ограничения), либо все функции, заданы алгоритмически, что делает невозможным применение к ним стандартных алгоритмов и требует разработки поисковых процедур оптимизации. Цель работы - обоснование, построение и исследование методов решения задач условной псевдобулевой оптимизации с алгоритмически заданными функциями. Используемые методы: исследуются свойства пространства булевых переменных и выявляются закономерности поведения псевдобулевых функций в пространстве булевых переменных. Разрабатываются точные регулярные алгоритмы, реализующие свойства конкретных классов задач. При построении регулярных алгоритмов рассматриваются классы унимодальных, монотонных и структурно монотонных псевдобулевых функций. Для задач больших размерностей исследуются алгоритмы оптимизации на основе метода случайного поиска, осуществляющие поиск среди граничных точек допустимой области. Результаты: разработаны новые точные алгоритмы с аналитическими оценками трудоемкости для решения задач условной псевдобулевой оптимизации, реализующие информационную сложность классов задач. Также построены новые приближенные алгоритмы для условной оптимизации монотонных псевдобулевых функций с большим числом переменных. Практическая значимость: разработанные алгоритмы применимы для решения любых практических задач, сводящихся к задачам оптимизации псевдобулевых функций. Так, решена задача оптимизации загрузки производственных мощностей литейного производства. Разработанные алгоритмы применяются для нахождения логических закономерностей (используемых для построения классификаторов) в данных, что представляет собой задачу условной псевдобулевой оптимизации большой размерности.

Ссылки на полный текст

Издание

Журнал: Системы управления, связи и безопасности

Выпуск журнала: 1

Номера страниц: 103-145

ISSN журнала: 24109916

Место издания: Санкт-Петербург

Издатель: Общество с ограниченной ответственностью "Корпорация "Интел Групп"

Авторы

Вхождение в базы данных