一个基于最小冲突修补的动态约束满足求解算法

约束满足问题是人工智能中一个重要的研究方向,近年来,对动态变化的约束满足问题的研究逐渐成为该领域的热点.在目前该领域最流行的LC算法基础上,引入禁忌搜索策略,提出了一个基于最小冲突修补的算法Tabu_LC.算法在每次冲突调整时将所有冲突变量看成一个整体,并采用分支定界搜索策略求解冲突变量组成的子问题,极大地提高了求解效率.同时,在约束求解系统"明月1.0"架构下给出了算法的具体实现,并针对大量随机问题进行了对比实验.结果表明,Tabu_LC算法在求解效率和解的质量上都明显优于LC算法.     

Solving constraint satisfaction problems using hybrid evolutionarysearch

We combine the concept of evolutionary search with the systematic search concepts of arc revision and hill climbing to form a hybrid system that quickly finds solutions to static and dynamic constraint satisfaction problems (CSPs). Furthermore, we present the results of two experiments. In the first experiment, we show that our evolutionary hybrid outperforms a well-known hill climber, the iterative descent method (IDM), on a test suite of 750 randomly generated static CSPs. These results show the existence of a “mushy region” which contains a phase transition between CSPs that are based on constraint networks that have one or more solutions and those based on networks that have no solution. In the second experiment, we use a test suite of 250 additional randomly generated CSPs to compare two approaches for solving CSPs. In the first method, all the constraints of a CSP are known by the hybrid at run-time. We refer to this method as the static method for solving CSPs. In the second method, only half of the constraints of a CSPs are known at run-time. Each time that our hybrid system discovers a solution that satisfies all of the constraints of the current network, one additional constraint is added. This process of incrementally adding constraints is continued until all the constraints of a CSP are known by the algorithm or until the maximum number of individuals has been created. We refer to this second method as the dynamic method for solving CSPs. Our results show hybrid evolutionary search performs exceptionally well in the presence of dynamic (incremental) constraints, then also illuminate a potential hazard with solving dynamic CSPs     

Viral systems: A new bio-inspired optimisation approach

The paper presents a new approach to deal with combinatorial problems. It makes use of a biological analogy inspired by the performance of viruses. The replication mechanism, as well as the hosts’ infection processes is used to generate a metaheuristic that allows the obtention of valuable results. The viral system (VS) theoretical context is described and it is applied to a library of medium-to-large-sized cases of the Steiner problem for which the optimal solution is known. The method is compared with the metaheuristics that have provided the best results for the Steiner problem. The VS provides better solutions than genetic algorithms and certain tabu search approaches. For the most sophisticated tabu search approaches (the best metaheuristic approximations to the Steiner problem solution) VS provides solutions of similar quality.     

A new evolutionary approach to cutting stock problems with and without contiguity

Evolutionary algorithms (EAs) have been applied to many optimization problems successfully in recent years. The genetic algorithm (GAs) and evolutionary programming (EP) are two different types of EAs. GAs use crossover as the primary search operator and mutation as a background operator, while EP uses mutation as the primary search operator and does not employ any crossover. This paper proposes a novel EP algorithm for cutting stock problems with and without contiguity. Two new mutation operators are proposed. Experimental studies have been carried out to examine the effectiveness of the EP algorithm. They show that EP can provide a simple yet more effective alternative to GAs in solving cutting stock problems with and without contiguity. The solutions found by EP are significantly better (in most cases) than or comparable to those found by GAs.Scope and purposeThe one-dimensional cutting stock problem (CSP) is one of the classical combinatorial optimization problems. While most previous work only considered minimizing trim loss, this paper considers CSPs with two objectives. One is the minimization of trim loss (i.e., wastage). The other is the minimization of the number of stocks with wastage, or the number of partially finished items (pattern sequencing or contiguity problem). Although some traditional OR techniques (e.g., programming based approaches) can find the global optimum for small CSPs, they are impractical to find the exact global optimum for large problems due to combinatorial explosion. Heuristic techniques (such as various hill-climbing algorithms) need to be used for large CSPs. One of the heuristic algorithms which have been applied to CSPs recently with success is the genetic algorithm (GA). This paper proposes a much simpler evolutionary algorithm than the GA, based on evolutionary programming (EP). The EP algorithm has been shown to perform significantly better than the GA for most benchmark problems we used and to be comparable to the GA for other problems.     

A CSP Search Algorithm with Responsibility Sets and Kernels

A CSP search algorithm, like FC or MAC, explores a search tree during its run. Every node of the search tree can be associated with a CSP created by the refined domains of unassigned variables. If the algorithm detects that the CSP associated with a node is insoluble, the node becomes a dead-end. A strategy of pruning “by analogy” states that the current node of the search tree can be discarded if the CSP associated with it is “more constrained” than a CSP associated with some dead-end node. In this paper we present a method of pruning based on the above strategy. The information about the CSPs associated with dead-end nodes is kept in the structures called responsibility sets and kernels. We term the method that uses these structures for pruning RKP, which is abbreviation of Responsibility set, Kernel, Propagation. We combine the pruning method with algorithms FC and MAC. We call the resulting solvers FC-RKP and MAC-RKP, respectively. Experimental evaluation shows that MAC-RKP outperforms MAC-CBJ on random CSPs and on random graph coloring problems. The RKP-method also has theoretical interest. We show that under certain restrictions FC-RKP simulates FC-CBJ. It follows from the fact that intelligent backtracking implicitly uses the strategy of pruning “by analogy.”     

The distributed constraint satisfaction problem: formalization andalgorithms

We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems     

GENETIC ALGORITHM APPROACH TO A LUMBER CUTTING OPTIMIZATION PROBLEM

Genetic algorithms are a technique for search and optimization based on the Darwinian principle of natural selection. They are iterative search procedures that maintain a population of candidate solutions. The best or most fit solutions in that population are then used as the basis for the next generation of solutions. The next generation is formed using the genetic operators reproduction, crossover, and mutation. Genetic algorithms have been successfully applied to engineering search and optimization problems. This paper presents a discussion of the basic theory of genetic algorithms and presents a genetic algorithm solution of a lumber cutting optimization problem. Dimensional lumber is assigned a grade that represents its physical properties. A grade is assigned to every board segment of a specific length. The board is then cut in various locations in order to maximize its value, A genetic algorithm was used to determine the cutting patterns that would maximize the board value.     

Algorithms for Distributed Constraint Satisfaction: A Review

When multiple agents are in a shared environment, there usually exist constraints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to find a consistent combination of actions that satisfies these inter-agent constraints. Various application problems in multi-agent systems can be formalized as distributed CSPs. This paper gives an overview of the existing research on distributed CSPs. First, we briefly describe the problem formalization and algorithms of normal, centralized CSPs. Then, we show the problem formalization and several MAS application problems of distributed CSPs. Furthermore, we describe a series of algorithms for solving distributed CSPs, i.e., the asynchronous backtracking, the asynchronous weak-commitment search, the distributed breakout, and distributed consistency algorithms. Finally, we show two extensions of the basic problem formalization of distributed CSPs, i.e., handling multiple local variables, and dealing with over-constrained problems.     

Structural decompositions for problems with global constraints

A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or implicitly, by special-purpose algorithms provided by a solver. Such implicitly represented constraints, known as global constraints, are widely used; indeed, they are one of the key reasons for the success of constraint programming in solving real-world problems. In recent years, a variety of restrictions on the structure of CSP instances have been shown to yield tractable classes of CSPs. However, most such restrictions fail to guarantee tractability for CSPs with global constraints. We therefore study the applicability of structural restrictions to instances with such constraints. We show that when the number of solutions to a CSP instance is bounded in key parts of the problem, structural restrictions can be used to derive new tractable classes. Furthermore, we show that this result extends to combinations of instances drawn from known tractable classes, as well as to CSP instances where constraints assign costs to satisfying assignments.     

Chain-reaction solution update in MOEA/D and its effects on multi- and many-objective optimization

MOEA/D is one of the promising evolutionary algorithms for multi- and many-objective optimization. To improve the search performance of MOEA/D, this work focuses on the solution update method in the conventional MOEA/D and proposes its alternative, the chain-reaction solution update. The proposed method is designed to maintain and improve the variable (genetic) diversity in the population by avoiding duplication of solutions in the population. In addition, the proposed method determines the order of existing solutions to be updated depending on the location of each offspring in the objective space. Furthermore, when an existing solution in the population is replaced by a new offspring, the proposed method tries to reutilize the existing solution for other search directions by recursively performing the proposed chain-reaction update procedure. This work uses discrete knapsack and continuous WFG4 problems with 2–8 objectives. Experimental results using knapsack problems show the proposed chain-reaction update contributes to improving the search performance of MOEA/D by enhancing the diversity of solutions in the objective space. In addition, experimental results using WFG4 problems show that the search performance of MOEA/D can be further improved using the proposed method.     

Network-based heuristics for constraint-satisfaction problems

Many AI tasks can be formulated as constraint-satisfaction problems (CSP), i.e., the assignment of values to variables subject to a set of constraints. While some CSPs are hard, those that are easy can often be mapped into sparse networks of constraints which, in the extreme case, are trees. This paper identifies classes of problems that lend themselves to easy solutions, and develops algorithms that solve these problems optimally. The paper then presents a method of generating heuristic advice to guide the order of value assignments based on both the sparseness found in the constraint network and the simplicity of tree-structured CSPs. The advice is generated by simplifying the pending subproblems into trees, counting the number of consistent solutions in each simplified subproblem, and comparing these counts to decide among the choices pending in the original problem.     

基于等级制度的病毒进化遗传算法

按照适应度将主群体分成高等主子群和低等主子群,病毒也相应地分为小病毒群和大病毒群。高等主子群个体感染小病毒后其显性值产生小尺度变化,低等主子群个体感染大病毒后其显性值产生大尺度变化,使优良个体在自身区域小范围内搜索,而不良个体则远离自身区域进行搜索,从而提高其搜索速度和精度。实例证明,改进算法在性能上优于传统病毒进化遗传算法。     

Efficient flexible planning via dynamic flexible constraint satisfaction

Recent advances in AI planning have centred upon the reduction of planning to a constraint satisfaction problem (CSP) enabling the application of the efficient search algorithms available in this area. This paper continues this approach, presenting a novel technique which exploits (restriction/relaxation-based) dynamic CSP (rrDCSP) in order to further improve planner performance. Using the standard Graphplan framework, it is shown how significant efficiency gains may be obtained by viewing plan extraction as the solution of a hierarchy of such rrDCSPs. Furthermore, by using flexible constraints as a formal foundation, it is shown how the traditional boolean notion of planning can be extended to incorporate prioritised and preference-based information. Plan extraction in this context is shown to generalise the Boolean rrDCSP approach, being systematically supported by the recently developed solution techniques for dynamic flexible CSPs (DFCSPs). The proposed techniques are evaluated via benchmark boolean problems and a novel flexible benchmark problem. Results obtained are very encouraging.     

Lexicographically-ordered constraint satisfaction problems

We describe a simple CSP formalism for handling multi-attribute preference problems with hard constraints, one that combines hard constraints and preferences so the two are easily distinguished conceptually and for purposes of problem solving. Preferences are represented as a lexicographic order over complete assignments based on variable importance and rankings of values in each domain. Feasibility constraints are treated in the usual manner. Since the preference representation is ordinal in character, these problems can be solved with algorithms that do not require evaluations to be represented explicitly. This includes ordinary CSP algorithms, although these cannot stop searching until all solutions have been checked, with the important exception of heuristics that follow the preference order (lexical variable and value ordering). We describe relations between lexicographic CSPs and more general soft constraint formalisms and show how a full lexicographic ordering can be expressed in the latter. We discuss relations with (T)CP-nets, highlighting the advantages of the present formulation, and we discuss the use of lexicographic ordering in multiobjective optimisation. We also consider strengths and limitations of this form of representation with respect to expressiveness and usability. We then show how the simple structure of lexicographic CSPs can support specialised algorithms: a branch and bound algorithm with an implicit cost function, and an iterative algorithm that obtains optimal values for successive variables in the importance ordering, both of which can be combined with appropriate variable ordering heuristics to improve performance. We show experimentally that with these procedures a variety of problems can be solved efficiently, including some for which the basic lexically ordered search is infeasible in practice.     

Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty

In classical Constraint Satisfaction Problems (CSPs) knowledge is embedded in a set of hard constraints, each one restricting the possible values of a set of variables. However constraints in real world problems are seldom hard, and CSP's are often idealizations that do not account for the preference among feasible solutions. Moreover some constraints may have priority over others. Lastly, constraints may involve uncertain parameters. This paper advocates the use of fuzzy sets and possibility theory as a realistic approach for the representation of these three aspects. Fuzzy constraints encompass both preference relations among possible instantiations and priorities among constraints. In a Fuzzy Constraint Satisfaction Problem (FCSP), a constraint is satisfied to a degree (rather than satisfied or not satisfied) and the acceptability of a potential solution becomes a gradual notion. Even if the FCSP is partially inconsistent, best instantiations are provided owing to the relaxation of some constraints. Fuzzy constraints are thus flexible. CSP notions of consistency and k-consistency can be extended to this framework and the classical algorithms used in CSP resolution (e.g., tree search and filtering) can be adapted without losing much of their efficiency. Most classical theoretical results remain applicable to FCSPs. In the paper, various types of constraints are modelled in the same framework. The handling of uncertain parameters is carried out in the same setting because possibility theory can account for both preference and uncertainty. The presence of uncertain parameters leads to ill-defined CSPs, where the set of constraints which defines the problem is not precisely known.     

Nogood-FC for solving partitionable constraint satisfaction problems

Many real problems can be naturally modelled as constraint satisfaction problems (CSPs). However, some of these problems are of a distributed nature, which requires problems of this kind to be modelled as distributed constraint satisfaction problems (DCSPs). In this work, we present a distributed model for solving CSPs. Our technique carries out a partition over the constraint network using a graph partitioning software; after partitioning, each sub-CSP is arranged into a DFS-tree CSP structure that is used as a hierarchy of communication by our distributed algorithm. We show that our distributed algorithm outperforms well-known centralized algorithms solving partitionable CSPs.     

Tractable classes for CSPs of arbitrary arity: from theory to practice

The research of this thesis focuses on the analysis of polynomial classes and their practical exploitation for solving constraint satisfaction problems (CSPs) with finite domains. In particular, I worked on bridging the gap between theoretical works and practical results in constraint solvers. Specifically, the goal of this thesis is to find explanation for the effectiveness of solvers, and also to show that studied tractable classes are not artificial since several real-problems among the ones used in the CSP 2008 Competition belong to them.Our work is organized into three main parts. In the first part, we proposed several types of microstructures for CSPs of arbitrary arity which are based on some knwon binary encoding of non-binary CSPs like, dual encoding, hidden-variable transformation and mixed (or double) encoding. These theoretical tools are designed to facilitate the study of tractable classes, sets of CSP instances which can be solved in polytime, when the constraints are non-binary. After that, we propose a new tractable classes of CSPs whose the highlighting should allow on the one hand to explain the effectiveness of solvers of the state of the art namely FC, MAC, RFL and on the second hand to provide the opportunities for easy integration in these solvers. These would include the definition of new tractable classes without using of an ad hoc algorithms as in the traditional case. These new tractable classes are related to the number of maximal cliques in the microstructure of binary or non-binary CSP. In the last part, we focus on the presence of instances belonging to polynomial classes in classical benchmarks used by the CP community. We study in particular the Broken-Triangle Property (BTP) and its extension DBTP to CSP of arbitrary arity. Next, we prove that BTP can also be used to reduce the size of the search space by merging pairs of values on which no broken triangle exists. Finally, we introduce a formal framework, called transformation, and we develop the concept of hidden tractable class that we exploit from an experimental point of view.     

A new approach to partial constraint satisfaction problems

A finite binary Constraint Satisfaction Problem (CSPs) is defined as consisting of a set of n problem variables, a domain of d potential values for each variable and a set of m binary constraints involving only two variables at a time. A solution to such a CSP is specified by assignment of a value to each variable that does not violate any of the constraints. The CSPs belong to the class of NP-Complete Problems. Backtracking and its variants have been generally used for solving CSPs. The class of Partial Constraint Satisfaction Problems (PCSPs) is a subclass of CSPs that are either too difficult to solve or are unsolvable. Near optimal solutions are always desired to these problems.

In this article, we have considered only finite binary CSPs or PCSPs and developed a method of time complexity O(n ² d ²) to obtain a near optimal solution for them. The performance of the method in terms of the average number of consistency checks and the average number of constraint violations is measured on various randomly generated binary CSPs and compared with the Branch and Bound (BB) method used to obtain the same solution. The BB method is a widely used optimization technique that may be viewed as a variation of backtracking. Thus, it was a natural choice in seeking an analog of backtracking to find optimal partial solutions for PCSPs. The proposed method moves much faster to the solution. The performance results indicate that in terms of the number of consistency checks, the proposed method has much less consistency checks than BB whereas in terms of average number of constraint violations both methods are same. An upper bound on the distance of the solution from the optimal solution is obtained analytically as ?n(n???2)(d???2)/(d???1)?.     

随机约束满足问题的回溯算法分析

提出一种新的随机CSP(constraint sa tisfaction problem)模型,并且通过研究搜索树的平均节点数,分析了回溯算法求解该模型 的平均复杂性.结果表明,这种模型能够生成难解的CSP实例,找到所有的解或证明无解所需的 平均节点数即随变量数的增加而指数增长.因此,该模型可以用来研究难解实例的性质和CSP 算法的性能等问题,从而有助于设计出更为高效的算法.     

Genetic algorithms and neural networks: optimizing connections and connectivity

Genetic algorithms are a robust adaptive optimization method based on biological principles. A population of strings representing possible problem solutions is maintained. Search proceeds by recombining strings in the population. The theoretical foundations of genetic algorithms are based on the notion that selective reproduction and recombination of binary strings changes the sampling rate of hyperplanes in the search space so as to reflect the average fitness of strings that reside in any particular hyperplane. Thus, genetic algorithms need not search along the contours of the function being optimized and tend not to become trapped in local minima. This paper is an overview of several different experiments applying genetic algorithms to neural network problems. These problems include

1. (1) optimizing the weighted connections in feed-forward neural networks using both binary and real-valued representations, and

2. (2) using a genetic algorithm to discover novel architectures in the form of connectivity patterns for neural networks that learn using error propagation.

Future applications in neural network optimization in which genetic algorithm can perhaps play a significant role are also presented.