Сибирский федеральный университет

Перевод названия: О КЛАССАХ ФУНКЦИЙ С БИНАРНЫМИ ПЕРЕМЕННЫМИ

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

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

Ключевые слова: pseudoboolean functions, optimization, псевдобулевые функции, оптимизация

Аннотация: The scheme proposed below is often used for solving problems and developing optimization algorithms. To solve a specific problem an efficient algorithm of optimization has been developed. The proposed algorithm combines several classes of problems by generelasing and determining a function class. For this reason establishing correlation among available classes of functions with binary variables in different experiments allows to apply even not perfect optimization algorithms. In this paper we consider a question on correlation of the function classes based on the different approaches to classification itself. First approach offers classes of separable, modular and submodular function; second one offers function classes based on structural features of the set of binary variables: monotone, unmonotone and w eakly unmonotone functions. It has been proven that separable functions are always unimodal and monotone ones. The results obtained in this study will allow to use a more efficient algorithm for optimization of separable and modular functions. Предлагаемая схема исторически используется для решения задач и разработки алгоритмов оптимизации. Для решения реальной задачи разработан достаточно эффективный алгоритм оптимизации. Рассматриваемый алгоритм объединяет в себе несколько классов задач, обобщая классы функций. Вследствие этого, определение корреляции уже представленных классов функций с бинарными переменными при помощи различных исследований позволяет применять даже не усовершенствованные алгоритмы оптимизации. Рассматривается вопрос о корреляции классов функций при различных подходах классификации. Первый подход включает классы сепарабельных, модулярных и субмодулярных функций, второй - классы функций, которые основываются на структурных свойствах множества бинарных переменных: монотонные, немонотонные и слабо немонотонные функции. На практике доказано, что сепарабельные функции унимодальные и монотонные. Полученные результаты позволяют использовать для оптимизации сепарабельных и модулярных функций более эффективные алгоритмы по сравнению с ранее используемыми.

Журнал: Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева

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

Номера страниц: 47-49

ISSN журнала: 18169724

Место издания: Красноярск

Издатель: Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева

• Antamoshkin A.N.
• Stupina A.A.

• РИНЦ (eLIBRARY.RU)