检索结果-内蒙古大学图书馆

Computing the moments of k-bounded pseudo-boolean functions over Hamming spheres of arbitrary radius in polynomial time

引用

THEORETICAL COMPUTER SCIENCE 2012年 425卷 58-74页

作者： Sutton, Andrew M. Whitley, L. Darrell Howe, Adele E. Colorado State Univ Dept Comp Sci Ft Collins CO 80523 USA

We show that given a k-bounded pseudo-boolean function f, one can always compute the cth moment off over regions of arbitrary radius in Hamming space in polynomial time using algebraic information from the adjacency structure (where k and c are constants). This result has implications for evolutionary algorithms and local search algorithms because information about promising regions of the search space can be efficiently retrieved, even if the cardinality of the region is exponential in the problem size. Finally, we use our results to introduce a method of efficiently calculating the expected fitness of mutations for evolutionary algorithms. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Fitness landscape analysis pseudo-boolean functions Walsh analysis Elementary landscapes Local search

来源：评论

学校读者我要写书评

暂无评论

Disjunctive analogues of submodular and supermodular pseudo-boolean functions

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期142卷 53-65页

作者： Foldes, S Hammer, PL Tampere Univ Technol Dept Math FIN-33101 Tampere Finland Rutgers State Univ RUTCOR Piscataway NJ 08854 USA

We consider classes of real-valued functions of boolean variables defined by disjunctive analogues of the submodular and supermodular functional inequalities, obtained by replacing in these inequalities addition by disjunction (max operator). The disjunctive analogues of submodular and supermodular functions are completely characterized by the syntax of their disjunctive normal forms. Classes of functions possessing combinations of these properties are also examined. A disjunctive representation theory based on one of these combination classes exhibits syntactic and algorithmic analogies with classical DNF theory. (C) 2003 Published by Elsevier B.V.

关键词： submodularity supermodularity pseudo-boolean functions disjunctive normal form implicents conseusus resolution

来源：评论

学校读者我要写书评

暂无评论

Submodularity, supermodularity, and higher-order monotonicities of pseudo-boolean functions

引用

MATHEMATICS OF OPERATIONS RESEARCH 2005年第2期30卷 453-461页

作者： Foldes, S Hammer, PL Tampere Univ Technol Inst Math Miami FL 33101 USA Rutgers State Univ Rutgers Ctr Operat Res RUTCOR Piscataway NJ 08854 USA

Classes of set functions defined by the positivity or negativity of the higher-order derivatives of their pseudo-boolean polynomial representations generalize those of monotone, supermodular, and submodular functions. In this paper, these classes are characterized by functional inequalities and are shown to be closed both under algebraic closure conditions and a local closure criterion. It is shown that for every m : 1, in addition to the class of all set functions, there are only three other classes satisfying these algebraic and local closure conditions: those having positive, respectively negative, mth-order derivatives, and those having a polynomial representation of degree less than m.

关键词： set functions boolean functions pseudo-boolean functions submodularity supermodularity discrete derivatives Post classes functional inequalities functional equations minors local closure

来源：评论

学校读者我要写书评

暂无评论

Characterization of rankings generated by pseudo-boolean functions

引用

SWARM AND EVOLUTIONARY COMPUTATION 2024年 86卷

作者： Unanue, Imanol Merino, Maria Lozano, Jose A. Univ Basque Country UPV EHU Dept Comp Sci & Artificial Intelligence Manuel Lardizabal Pasealekua 1 Donostia San Sebastian 20018 Spain Univ Basque Country UPV EHU Dept Math Leioa 48940 Spain BCAM Basque Ctr Appl Math Mazarredo Zumarkalea 14 Bilbao 48009 Spain

In this paper we pursue the study of pseudo -boolean functions as ranking generators. The objective of the work is to find new insights between the relation of the degree m of a pseudo -boolean function and the rankings that can be generated by these insights. Based on a characterization theorem for pseudo -boolean functions of degree m, several observations are made. First, we verify that pseudo -boolean functions of degree m < n, where n is the search space dimension, cannot generate all the possible rankings of the solutions. Secondly, the sufficient condition for a ranking to be generated by a pseudo -boolean function of dimension ( n - 1) is presented, and also the necessary condition is conjectured. Finally, we observe that the same argument is not sufficient to prove which ranking can be generated by pseudo -boolean functions of degree m < n - 1 .

关键词： Binary-based combinatorial optimization problems pseudo-boolean functions Rankings Dyck Theoretical analysis

来源：评论

学校读者我要写书评

暂无评论

Algebraic and topological closure conditions for classes of pseudo-boolean functions

引用

DISCRETE APPLIED MATHEMATICS 2009年第13期157卷 2818-2827页

作者： Foldes, Stephan Hammer, Peter L. Tampere Univ Technol Inst Math FIN-33101 Tampere Finland

We examine classes of real-valued functions of 0-1 variables closed under algebraic operations as well as topological convergence, and having a certain local characteristic (requiring that any function not in the class should have a k-variable minor not belonging to this class). It is shown that for k = 2, the only 4 maximal classes with these properties are those of submodular, supermodular, monotone increasing and monotone decreasing functions. All the 13 locally defined closed classes are determined and shown to be intersections of the 4 maximal ones. All maximal classes for k >= 3 are determined and characterized by the sign of higher order derivatives of the functions in the class. (C) 2009 Published by Elsevier B.V.

关键词： pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

Compact quadratizations for pseudo-boolean functions

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第3期39卷 687-707页

作者： Boros, Endre Crama, Yves Rodriguez-Heck, Elisabeth Rutgers State Univ MSIS Dept Piscataway NJ USA Rutgers State Univ RUTCOR Piscataway NJ USA Univ Liege HEC Liege QuantOM Liege Belgium Rhein Westfal TH Aachen Aachen Germany

The problem of minimizing a pseudo-boolean function, that is, a real-valued function of 0-1 variables, arises in many applications. A quadratization is a reformulation of this nonlinear problem into a quadratic one, obtained by introducing a set of auxiliary binary variables. A desirable property for a quadratization is to introduce a small number of auxiliary variables. We present upper and lower bounds on the number of auxiliary variables required to define a quadratization for several classes of specially structured functions, such as functions with many zeros, symmetric, exact k-out-of-n, at least k-out-of-n and parity functions, and monomials with a positive coefficient, also called positive monomials. Most of these bounds are logarithmic in the number of original variables, and we prove that they are best possible for several of the classes under consideration. For positive monomials and for some other symmetric functions, a logarithmic bound represents a significant improvement with respect to the best bounds previously published, which are linear in the number of original variables. Moreover, the case of positive monomials is particularly interesting: indeed, when a pseudo-boolean function is represented by its unique multilinear polynomial expression, a quadratization can be obtained by separately quadratizing its monomials.

关键词： Nonlinear binary optimization Quadratic binary optimization pseudo-boolean functions Reformulation methods

来源：评论

学校读者我要写书评

暂无评论

The influence of variables on pseudo-boolean functions with applications to game theory and multicriteria decision making

引用

DISCRETE APPLIED MATHEMATICS 2000年第1-3期107卷 139-164页

作者： Marichal, JL Univ Liege Fac Econ Dept Management B-4000 Liege Belgium

The power of players in a collective decision process is a central issue in game theory. For this reason. the concept of influence of players on a simple game has been introduced. More generally, the influence of variables on boolean functions has been defined and studied. We extend this concept to pseudo-boolean functions, thus making it possible to appraise the degree of influence of any coalition of players in cooperative games. In the case of monotone games, we also point out the links with the concept of interaction among players. Although they do not have the same meaning at all, both influence and interaction functions coincide on singletons with the so-called Banzhaf power index. We also define the influence of variables on continuous extensions of pseudo-boolean functions. In particular, the Lovasz extension, also called discrete Choquet integral, is used in multicriteria decision making problems as an aggregation operator. In such problems, the degree of influence of decision criteria on the aggregation process can then be quite relevant information. We give the explicit form of this influence for the Choquet integral and its classical particular cases. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： pseudo-boolean functions game theory power and interaction indices multicriteria decision making

来源：评论

学校读者我要写书评

暂无评论

CUT-POLYTOPES, boolean QUADRIC POLYTOPES AND NONNEGATIVE QUADRATIC pseudo-boolean functions

引用

MATHEMATICS OF OPERATIONS RESEARCH 1993年第1期18卷 245-253页

作者： BOROS, E HAMMER, PL RUTCOR Rutgers University New Brunswick New Jersey 08903

In this paper we present a class of valid inequalities as well as a class of facets for the cut-polytope of the complete graph. It is shown that many of the known classes of valid inequalities, e.g., triangle, hypermetric and cycle inequalities, belong to this class. By specializing some of the parameters, large classes of facets can be defined. It is shown that each of these classes contains at least (n/3)n/3 facets, where n greater-than-or-equal-to 10 denotes the number of vertices, and that the corresponding separation problems are polynomially solvable. These results are based on a one-to-one correspondence established between the set of valid inequalities (facets) for the cut-polytope of K(n+1), and the set of nonnegative (extremal) quadratic pseudo-boolean functions in n variables.

关键词： CUT POLYTOPE QUADRATIC 0-1 PROGRAMMING pseudo-boolean functions VALID INEQUALITIES FACETS

来源：评论

学校读者我要写书评

暂无评论

Approximations of pseudo-boolean functions;applications to game theory

引用

ZOR Zeitschrift für Operations Research Methods and Models of Operations Research 1992年第1期36卷 3-21页

作者： Hammer, P.L. Holzman, R. RUTCOR Rutgers Center for Operations Research Rutgers University NewBrunswick 08903 NJ United States Department of Applied Mathematics and Computer Science The Weizmann Institute of Science Rehovot 76100 Israel

This paper studies the approximation of pseudo-boolean functions by linear functions and more generally by functions of (at most) a specified degree. Here a pseudo-boolean function means a real valued function defined on {0,1}ⁿ, and its degree is that of the unique multilinear polynomial that expresses it;linear functions are those of degree at most one. The approximation consists in choosing among all linear functions the one which is closest to a given function, where distance is measured by the Euclidean metric on R^{2 n}. A characterization of the best linear approximation is obtained in terms of the average value of the function and its first derivatives. This leads to an explicit formula for computing the approximation from the polynomial expression of the given function. These results are later generalized to handle approximations of higher degrees, and further results are obtained regarding the interaction of approximations of different degrees. For the linear case, a certain constrained version of the approximation problem is also studied. Special attention is given to some important properties of pseudo-boolean functions and the extent to which they are preserved in the approximation. A separate section points out the relevance of linear approximations to game theory and shows that the well known Banzhaf power index and Shapley value are obtained as best linear approximations of the game (each in a suitably defined sense). © 1992 Physica-Verlag.

关键词： best kth approximations least squares linear approximations power indices pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

Understanding Transforms of pseudo-boolean functions

Understanding Transforms of Pseudo-Boolean Functions

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Whitley, Darrell Aguirre, Hernan Sutton, Andrew Colorado State Univ Ft Collins CO 80523 USA Shinshu Univ Nagano Japan Univ Minnesota Duluth MN 55812 USA

ISBN: (纸本)9781450371285

There exist general transforms that convert pseudo-boolean functions into k-bounded pseudo-boolean functions, for all k >= 2. In addition to these general transforms, there can also exist specialized transforms that can be applied in special cases. New results are presented examining what happens to the "bit flip" neighborhood when transforms are applied. Transforms condense variables in a particular order. We show that different variable orderings produce different results in terms of problem difficulty. We also prove new results about the embedding of the original function in the new k-bounded function. Finally, this paper also looks at how parameter optimization problems can be expressed as high precision k-bounded pseudo-boolean functions. This paper lays a foundation for the wider application of evolutionary algorithms to k-bounded pseudo-boolean functions.

关键词： combinatorial optimization pseudo-boolean functions bit representations epistatsis

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：