In this paper we pursue the use of the Fourier transform for a general analysis of combinatorialoptimizationproblems. While combinatorialoptimizationproblems are defined by means of different notions like weights ...
详细信息
ISBN:
(纸本)9781728183923
In this paper we pursue the use of the Fourier transform for a general analysis of combinatorialoptimizationproblems. While combinatorialoptimizationproblems are defined by means of different notions like weights in a graph, set of numbers, distance between cities, etc., the Fourier transform allows to put all of them in the same framework, the Fourier coefficients. This permits its comparison looking for similarities and differences. Particularly, the Walsh transform has recently been used over pseudo-boolean functions in order to design new surrogate models in the black-box scenario and to generate new algorithms for the linkage discovery problem, among others, presenting very promising results. In this paper we focus on binaryproblems and the Walsh transform. After presenting the Walsh decomposition and some main properties, we compute the transform of the Unconstrained binary Quadratic Problem and several particular cases of this problem such as the Max-Cut Problem and the Number Partitioning Problem. The obtained Walsh coefficients not only reinforce the similarities and differences among the problems which are known in the literature, but given a set of Walsh coefficients we can say whether or not they are produced by any of the problems analyzed. Finally, a geometrical interpretation of the space of Walsh coefficients with maximum order 2 and the subspace of each analyzed problem is presented.
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 rankin...
详细信息
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 .
暂无评论