Lightweight dynamic symmetry breaking

Symmetries in constraint problems present an opportunity for reducing search. This paper presents Lightweight Dynamic Symmetry Breaking, an automatic symmetry breaking method that is efficient enough to be used as a default, since it never yields a major slowdown while often giving major performance improvements. This is achieved by automatically exploiting certain kinds of symmetry that are common, can be compactly represented, easily and efficiently processed, automatically detected, and lead to large reductions in search. Moreover, the method is easy to implement and integrate in any constraint system. Experimental results show the method is competitive with the best symmetry breaking methods without risking poor performance.     

对称在破裂孤立子方程中的应用

首先对带有积分项的破裂孤立子方程（breaking soliton equation）进行变换,然后利用待定系数法求出它的对称,通过验证知道原方程的李群能构成李代数,再利用优化系统对原方程进行约化,求出了原方程的一些新解。     

Static and dynamic structural symmetry breaking

We reconsider the idea of structural symmetry breaking for constraint satisfaction problems (CSPs). We show that the dynamic dominance checks used in symmetry breaking by dominance-detection search for CSPs with piecewise variable and value symmetries have a static counterpart: there exists a set of constraints that can be posted at the root node and that breaks all the compositions of these (unconditional) symmetries. The amount of these symmetry-breaking constraints is linear in the size of the problem, and yet they are able to remove a super-exponential number of symmetries on both values and variables. Moreover, we compare the search trees under static and dynamic structural symmetry breaking when using fixed variable and value orderings. These results are then generalised to wreath-symmetric CSPs with both variable and value symmetries. We show that there also exists a polynomial-time dominance-detection algorithm for this class of CSPs, as well as a linear-sized set of constraints that breaks these symmetries statically.     

Local and global symmetry breaking in itemset mining

The concept of symmetry has been extensively studied in the field of constraint programming and in the propositional satisfiability. Several methods for detection and removal of these symmetries have been developed, and their use in known solvers of these domains improved dramatically their effectiveness on a big variety of problems considered difficult to solve. The concept of symmetry may be exported to other areas where some structures can be exploited effectively. Particularly, in the area of data mining where some tasks can be expressed as constraints or logical formulas. We are interested here, by the detection and elimination of local and global symmetries in the item-set mining problem. Recent works have provided effective encodings as Boolean constraints for these data mining tasks and some idea on symmetry elimination in this area begin to appear, but still few and the techniques presented are often on global symmetry that is detected and eliminated statically in a preprocessing phase. In this work we study the notion of local symmetry and compare it to global symmetry for the itemset mining problem. We show how local symmetries of the boolean encoding can be detected dynamically and give some properties that allow to eliminate theses symmetries in SAT-based itemset mining solvers in order to enhance their efficiency.     

Spontaneous symmetry breaking for long-wave gravitons in the early Universe

It is shown that nonlinear terms in the equations for gravitons in the background of curved space-time of the expanding Universe can solve the problem of the negative effective mass squared, formally arising in the linear approximation for gravitons. Similarly to the well-known spontaneous symmetry breaking in the Goldstone model, one must take another vacuum, so that a nonzero vacuum expectation value of the quantized graviton field leads to a change in the graviton spectrum. There appear two graviton fields, one with positive mass, another with zero mass. The energy density and the density of particles created by gravitation of the expanding Universe are calculated for some special cases of the scale factor. Numerical results are obtained for the case of a dust universe.     

Efficient symmetry breaking formulations for the job grouping problem

The job grouping problem consists of assigning a set of jobs, each with a specific set of tool requirements, to machines with a limited tool capacity in order to minimize the number of machines needed. Traditionally, a formulation has been used that assigns jobs to machines. However, such a formulation contains a lot of symmetry since the machines are identical and they can be permuted in any feasible solution. We propose a new formulation for this problem, based on the asymmetric representatives formulation (ARF) idea. This formulation eliminates the symmetry between the identical machines. We further propose various symmetry breaking constraints, including variable reduction and lexicographic ordering constraints, which can be added to the traditional formulation. These formulations are tested on a data set from the literature and newly generated data sets using a state-of-the-art commercial solver, which includes symmetry breaking features.     

Analysis of emergent symmetry breaking in collective decision making

We investigate a simulated multi-agent system (MAS) that collectively decides to aggregate at an area of high utility. The agents’ control algorithm is based on random agent–agent encounters and is inspired by the aggregation behavior of honeybees. In this article, we define symmetry breaking, several symmetry breaking measures, and report the phenomenon of emergent symmetry breaking within our observed system. The ability of the MAS to successfully break the symmetry depends significantly on a local-neighborhood-based threshold of the agents’ control algorithm that determines at which number of neighbors the agents stop. This dependency is analyzed and two macroscopic features are determined that significantly influence the symmetry breaking behavior. In addition, we investigate the connection between the ability of the MAS to break symmetries and the ability to stay flexible in a dynamic environment.     

Distributing identity [symmetry breaking distributed accessprotocols]

In the next few years, computational, sensory, and communication capabilities will diffuse out of their present home in beige boxes on desktops and into everyday objects such as furniture, clothing, and other non-technological objects. As the cost of electronics continues to drop, the number of activated, networked devices will grow rapidly. Each device sharing a particular multiaccess channel will need a unique identifier for that channel. Present communication protocols such as Ethernet specify that the manufacturers must coordinate with one another in order to avoid assigning the same ID twice. The article explores methods by which the devices could coordinate with one another to manage ID assignment dynamically and automatically. In particular, the article is an investigation of distributed protocols that utilize physical sources of symmetry breaking to enable a network of initially identical units to acquire the unique identities required for point-to-point communication over a shared resource such as a bus or common RF band. It presents several protocols, compares their resource use (time, random bits, space, communication), and notes a trade-off among these measures of algorithm complexity     

Dynamic structural symmetry breaking for constraint satisfaction problems

In recent years, symmetry breaking for constraint satisfaction problems (CSPs) has attracted considerable attention. Various general schemes have been proposed to eliminate symmetries. In general, these schemes may take exponential space or time to eliminate all the symmetries. We identify several classes of CSPs that encompass many practical problems and for which symmetry breaking for various forms of value or variable interchangeability is tractable using dedicated search procedures. We also show the limits of efficient symmetry breaking for such dominance-detection schemes by proving intractability results for some classes of CSPs.     

Lifting symmetry breaking constraints with inductive logic programming

Machine Learning - Efficient omission of symmetric solution candidates is essential for combinatorial problem-solving. Most of the existing approaches are instance-specific and focus on the...     

Subthreshold-seeking local search

Algorithms for parameter optimization display subthreshold-seeking behavior when the majority of the points that the algorithm samples have an evaluation less than some target threshold. We first analyze a simple “subthreshold-seeker” algorithm. Further theoretical analysis details conditions that allow subthreshold-seeking behavior for local search algorithms using Binary and Gray code representations. The analysis also shows that subthreshold-seeking behavior can be increased by using higher bit precision. However, higher precision also can reduce exploration. A simple modification to a bit-climber is proposed that improves its subthreshold-seeking behavior. Experiments show that this modification results in both improved search efficiency and effectiveness on common benchmark problems.     

Phase transitions and symmetry breaking in genetic algorithms with crossover

In this paper, we consider the role of the crossover operator in genetic algorithms. Specifically, we study optimisation problems that exhibit many local optima and consider how crossover affects the rate at which the population breaks the symmetry of the problem. As an example of such a problem, we consider the subset sum problem. In doing so, we demonstrate a previously unobserved phenomenon, whereby the genetic algorithm with crossover exhibits a critical mutation rate, at which its performance sharply diverges from that of the genetic algorithm without crossover. At this critical mutation rate, the genetic algorithm with crossover exhibits a rapid increase in population diversity. We calculate the details of this phenomenon on a simple instance of the subset sum problem and show that it is a classic phase transition between ordered and disordered populations. Finally, we show that this critical mutation rate corresponds to the transition between the genetic algorithm accelerating or preventing symmetry breaking and that the critical mutation rate represents an optimum in terms of the balance of exploration and exploitation within the algorithm.     

Multi-directional local search

This paper introduces multi-directional local search, a metaheuristic for multi-objective optimization. We first motivate the method and present an algorithmic framework for it. We then apply it to several known multi-objective problems such as the multi-objective multi-dimensional knapsack problem, the bi-objective set packing problem and the bi-objective orienteering problem. Experimental results show that our method systematically provides solution sets of comparable quality with state-of-the-art methods applied to benchmark instances of these problems, within reasonable CPU effort. We conclude that the proposed algorithmic framework is a viable option when solving multi-objective optimization problems.     

基于对称破坏的子图同构约束求解算法

为避免子图同构问题求解中重复解的产生,提高子图同构问题的约束求解效率,提出一种基于对称破坏的子图同构约束求解算法。基于解的对称破坏思想,改进自同构检测过程,通过置换群操作生成对称破坏字典序约束,构建子图同构问题的一种约束满足问题(CSP)模型,结合CSP的回溯算法对其求解。实验结果表明,该算法有效减少了对重复解的搜索,与传统算法相比明显提高了搜索效率。     

Glass transition and the replica symmetry breaking in vortex matter: MC study

We investigate effects of disorder and thermal fluctuations on the Abrikosov state of type II superconductors applying the Monte Carlo method to Ginzburg–Landau theory to confirm earlier replica calculation. The vortex phase diagram has two transition lines, the melting line and the vortex glass transition lines in both crystalline and homogeneous states. The glass line is always a continuous transition, while the melting line is the first order.     

Agent-based guided local search

The main contribution of the paper is to propose and validate a new hybrid approach for solving combinatorial optimization problems in which guided local search metaheuristic is incorporated into a cooperative multi-agent framework based on the concept of asynchronous teams (A-Teams). Generally, an A-Team assumes that a collection of software agents, each representing a particular problem solving method, cooperate to solve a problem by dynamically evolving a population of solutions. In the suggested implementation each software agent carries out a guided local search. The proposed approach has been extensively validated experimentally on one of the best known combinatorial optimization problem – the vehicle routing problem. The promising results of experiments have confirmed the effectiveness of the suggested approach.     

Chaotic local search algorithm

The steepest descent search algorithm is modified in conjunction withchaos to solve the optimization problem of an unstructured search space. The problem is that given only the gradient information of the quality function at the present configuration,X(t), we must find the value of a configuration vector that minimizes the quality function. The proposed algorithm starts basically from the steepest descent search technique but at the prescribed points, i.e., local minimum points, the chaotic jump is performed by the dynamics of a chaotic neuron. Chaotic motions are mainly caused because the Gaussian function has a hysteresis as a refractoriness. An adaptation mechanism to adjust the size of the chaotic jump is also given. In order to enhance the probability of finding the global minimum, a parallel search strategy is developed. The validity of the proposed method is verified in simulation examples of the function minimization problem and the motion planning problem of a mobile robot. This work was presented, in part, at the International Symposium on Artificial Life and Robotics, Oita, Japan, February 18–20, 1996     

Hypervolume-based multi-objective local search

This paper presents a multi-objective local search, where the selection is realized according to the hypervolume contribution of solutions. The HBMOLS algorithm proposed is inspired from the IBEA algorithm, an indicator-based multi-objective evolutionary algorithm proposed by Zitzler and Künzli in 2004, where the optimization goal is defined in terms of a binary indicator defining the selection operator. In this paper, we use the indicator optimization principle, and we apply it to an iterated local search algorithm, using hypervolume contribution indicator as selection mechanism. The methodology proposed here has been defined in order to be easily adaptable and to be as parameter-independent as possible. We carry out a range of experiments on the multi-objective flow shop problem and the multi-objective quadratic assignment problem, using the hypervolume contribution selection as well as two different binary indicators which were initially proposed in the IBEA algorithm. Experimental results indicate that the HBMOLS algorithm is highly effective in comparison with the algorithms based on binary indicators.     

On the symmetry group of the Mollard code

We study the symmetry group of a binary perfect Mollard code M(C,D) of length tm + t + m containing as its subcodes the codes C ¹ and D ² formed from perfect codes C and D of lengths t and m, respectively, by adding an appropriate number of zeros. For the Mollard codes, we generalize the result obtained in [1] for the symmetry group of Vasil’ev codes; namely, we describe the stabilizer

$$Sta{b_{{D^2}}}$$

Sym(M(C,D)) of the subcode D ² in the symmetry group of the code M(C,D) (with the trivial function). Thus we obtain a new lower bound on the order of the symmetry group of the Mollard code. A similar result is established for the automorphism group of Steiner triple systems obtained by the Mollard construction but not necessarily associated with perfect codes. To obtain this result, we essentially use the notions of “linearity” of coordinate positions (points) of a nonlinear perfect code and a nonprojective Steiner triple system.