Страница публикации

Merging Variables: One Technique of Search in Pseudo-Boolean Optimization

Тип публикации: Статья в журнале

Тип материала: Текст

Авторы: Semenov A.

Журнал: Communications in Computer and Information Science: Proc. of the Intern. Conf. on Mathematical Optimization Theory and Operations Research (MOTOR'2019)

Язык публикации: english

Серия книг: Communications in Computer and Information Science

Том: 1090

Номера страниц: 86-102

Количество страниц: 17

Год публикации: 2019

Отчетный год: 2019

Аннотация: In the present paper we describe new heuristic technique, which can be applied to the optimization of pseudo-Boolean functions including Black-Box functions. This technique is based on a simple procedure which consists in transition from the optimization problem over Boolean hypercube to the optimization problem of auxiliary function in a specially constructed metric space. It is shown that there is a natural connection between the points of the original Boolean hypercube and points from new metric space. For a Boolean hypercube with fixed dimension it is possible to construct a number of such metric spaces. The proposed technique can be considered as a special case of Variable Neighborhood Search, which is focused on pseudo-Boolean optimization. Preliminary computational results show high efficiency of the proposed technique on some reasonably hard problems. Also it is shown that the described technique in combination with the well-known (1+1)-Evolutionary Algorithm allows to decrease the upper bound on the runtime of this algorithm for arbitrary pseudo-Boolean functions.

Индексируется WOS: Q5

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Нет

Индексируется ВАК: Нет

Индексируется CORE: Нет