Email this article ON CLASES OF FUNCTIONS WITH BINARY VARIABLES
- Authors: Antamoshkin AN1, Stupina AA1
-
Affiliations:
- Issue: Vol 10, No 2 (2009)
- Pages: 47-49
- Section: Articles
- URL: https://journals.eco-vector.com/2712-8970/article/view/504894
- ID: 504894
Cite item
Full Text
Abstract
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.
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.
Keywords
References
- Antamoshkin, A. N. Optimization of unimodal pseudoboolean functions / A. N. Antamoshkin, V. Saraev, E. S. Se menkin // K y bernetika. 1990. V ol. 26, № 5. P . 432-442.
- Droste, S. A r igor ius complexity analy sis of the (1+1) evolutionary algorithm for separable functions with boolean inputs / S. Droste, T. Jansen, I. Wegener. Technical Report. № CI-6/1997 ; University of Dortmund, 1997.
- Stupina, A. Optimization of separable pseudoboolean functions / A. Stupina // Lehtstuhl fuer Sistemanalyse. Jahresbericht 1998/1999 / ed. by Prof. Dr.-Ing. H.-P . Schwefel, Prof. Dr. W. Banzhaf ; Universitaet Dortmund. Dortmund, 1999. Р. 29-40.
Supplementary files
