Перевод названия: Search Algorithms for Constrained Pseudo-Boolean Optimization
Тип публикации: статья из журнала
Год издания: 2016
Ключевые слова: Pseudo-Boolean functions, optimization, random search, greedy algorithm, regular optimization algorithm, псевдобулевые функции, оптимизация, случайный поиск, гриди алгоритм, регулярный алгоритм оптимизации
Аннотация: Постановка проблемы: рассматриваются задачи оптимизации вещественных функций бинарных переменных - так называемые задачи псевдобулевой оптимизации. В большинстве практических задач на комбинации значений переменных накладываются ограничения, сужающие множество допустимых значений управляющих переменных. В то же время эти ограничениПоказать полностьюя, как и сама целевая функция, зачастую обладают конструктивными свойствами, учет которых в процессе оптимизации способен повысить эффективность решения таких задач. Кроме того, во многих реальных задачах оптимизации часть функций (критерии и ограничения), либо все функции, заданы алгоритмически, что делает невозможным применение к ним стандартных алгоритмов и требует разработки поисковых процедур оптимизации. Цель работы - обоснование, построение и исследование методов решения задач условной псевдобулевой оптимизации с алгоритмически заданными функциями. Используемые методы: исследуются свойства пространства булевых переменных и выявляются закономерности поведения псевдобулевых функций в пространстве булевых переменных. Разрабатываются точные регулярные алгоритмы, реализующие свойства конкретных классов задач. При построении регулярных алгоритмов рассматриваются классы унимодальных, монотонных и структурно монотонных псевдобулевых функций. Для задач больших размерностей исследуются алгоритмы оптимизации на основе метода случайного поиска, осуществляющие поиск среди граничных точек допустимой области. Результаты: разработаны новые точные алгоритмы с аналитическими оценками трудоемкости для решения задач условной псевдобулевой оптимизации, реализующие информационную сложность классов задач. Также построены новые приближенные алгоритмы для условной оптимизации монотонных псевдобулевых функций с большим числом переменных. Практическая значимость: разработанные алгоритмы применимы для решения любых практических задач, сводящихся к задачам оптимизации псевдобулевых функций. Так, решена задача оптимизации загрузки производственных мощностей литейного производства. Разработанные алгоритмы применяются для нахождения логических закономерностей (используемых для построения классификаторов) в данных, что представляет собой задачу условной псевдобулевой оптимизации большой размерности. Problem statement. The issue is the problem of optimizing real functions of binary variables that is the so-called pseudo-Boolean optimization problem. In many practical problems, possible combinations of variables are restricted by constraints that narrow the set of admissible values of the control variables. At the same time these constraints (and an objective function) often have structural properties, inclusion of which in the optimization process can improve the efficiency of solving such problems. Furthermore, in many real problems of optimization a part of functions (criteria and constraints) or all functions are defined algorithmically, which makes it impossible to apply the standard algorithms and requires the development of search optimization procedures. Purpose. To justify, construct and research methods for constrained pseudo-Boolean optimization problems with algorithmically given functions. Methods. Research of properties of the space of Boolean variables and detection of patterns for behavior of pseudo-Boolean functions in the space of Boolean variables. Development of exact regular algorithms that implement properties of specific classes of problems. In the development of regular algorithms, the classes of unimodal, monotone and structurally monotone pseudo-Boolean functions are considered. For large-scale problems research of algorithms based on a random search method that search among the boundary points of the feasible set. Results. The new exact algorithms with analytical estimates of complexity for solving the constrained pseudo-Boolean optimization problems. These algorithms realize information complexity of the problem classes. As well the new approximate algorithms are constructed for constrained optimization of monotone pseudo-Boolean functions with a large number of variables. Practical relevance. The developed algorithms are useful for solving all practical problems which are reduced to optimization problems of pseudo-Boolean functions. So, the problem of optimizing the capacity utilization of foundry is solved. The developed algorithms are used for finding logical patterns (used for building classifiers) in data that is the constraint pseudo-Boolean optimization problem of large dimension.
Журнал: Системы управления, связи и безопасности
Выпуск журнала: № 1
Номера страниц: 103-145
ISSN журнала: 24109916
Место издания: Санкт-Петербург
Издатель: Общество с ограниченной ответственностью "Корпорация "Интел Групп"