SMCB-E-03172004-0141.R2 1 A Multiagent Evolutionary algorithm for Constraint Satisfaction Problems Weicai Zhong,Jing Liu,and Licheng Jiao,Senior Member,IEEE subspace from the Cartesian product of all the variable domains. Abstract-With the intrinsic properties of constraint the computational complexity for solving most nontrivia satisfaction problems (CSPs)in mind,we divide CSPs into two problems remains exponential.Many studies have been types,namely,permutation CSPs and non-permutation CSPs. conducted to investigate various ways of improving the According to their characteristics,several behaviors are designed for agents by making use of the ability of agents to sense and act on backtracking method,such as consistency techniques [4],[5], the environment.These behaviors are controlled by means of the dependency-directed backtracking scheme [6],[7]. evolution,so that the multiagent evolutionary algorithm for Nevertheless,it is still unable to solve nontrivial large-scale constraint satisfaction problems (MAEA-CSPs)results.To CSPs in a reasonable runtime. overcome the disadvantages of the general encoding methods,the For the generate-and-test method,one of the most popular minimum conflict encoding is also proposed.Theoretical analyses show that MAEA-CSPs has a linear space complexity and ideas is to employ a local search technique [8]-[10].It generates converges to the global optimum.The first part of the experiments an initial configuration and then incrementally uses"repair"or uses 250 benchmark binary CSPs and 79 graph coloring problems "hill climbing"to modify the inconsistent configuration to move from the DIMACS challenge to test the performance of to a neighborhood configuration having the best or better MAEA-CSPs for non-permutation CSPs.MAEA-CSPs is evaluation value among the neighbors,until a solution is found. compared with six well-defined algorithms and the effect of the As related to the idea of local search.other heuristics have also parameters is analyzed systematically.The second part of the been developed,such as the min-conflicts heuristic [11],[12], experiments uses a classical CSP,n-queen problems,and a more practical case,job-shop scheduling problems (JSPs),to test the GSAT [13].In addition,local search techniques are often performance of MAEA-CSPs for permutation CSPs.The combined with Evolutionary Algorithms(EAs),another popular scalability of MAEA-CSPs along n for n-queen problems is studied kind of method for solving CSPs. with great care.The results show that MAEA-CSPs achieves good Historically,CSPs have been approached from many angles performance when n increases from 10 to 107,and has a linear by EAs.In this field,the method used to treat the constraints is time complexity.Even for 10'-queen problems,MAEA-CSPs finds the solutions by only 150 seconds.For JSPs,59 benchmark very important.The constraints can be handled directly. problems are used,and good performance is also obtained. indirectly or by mixed methods [14].Among the available methods,some put the emphasis on the usage of heuristics,such Index Terms-Constraint satisfaction problems,evolutionary as ARC-GA [15],[16],COE-H GA [17],[18],Glass-Box [19], algorithms,graph coloring problems,job-shop scheduling H-GA [20],[21],whereas others handle the constraints by problems,multiagent systems,n-queen problems. fitness function adaptation,such as CCS [22],[23],MID [24]-[26],SAW [27],[28].These methods dealt with CSPs by EAs from different angles and boosted the development of this I.INTRODUCTION field.Reference [29]has made an extensive performance large number of problems coming from artificial Aintelligence as well as other areas of computer science an comparison of all these EAs on a systematically generated test suite. engineering can be stated as Constraint Satisfaction Problems Agent-based computation has been studied for several years (CSPs)[1]-[3].A CSP has three components:variables,values, in the field of distributed artificial intelligence [30],[31]and has and constraints.The purpose is to find an assignment of values been widely used in other branches of computer science to variables such that all constraints are satisfied.Many methods [32]-[35].Problem solving is an area with which many have been proposed to deal with CSPs,where backtracking and multiagent-based applications are concerned.It includes generate-and-test methods are well-known traditional distributed solutions to problems,solving distributed problems approaches [1].Although the backtracking method eliminates a and distributed techniques for problem solving [30],[31]. Reference [33]introduced an application of distributed Manuscript received March 17,2004.This work is supported by the techniques for solving constraint satisfaction problems.They National Natural Science Foundation of China under Grant 60133010 and solved 7000-queen problems by an energy-based multiagent 60372045,and the "863"project under Grant 2002AA135080. model.In [34],multiagent systems and genetic algorithms(GAs) The authors are with the Institute of Intelligent Information Processing, Xidian University,Xi'an,710071,China are integrated to solve global numerical optimization problems, Jing Liu,corresponding author,phone:86-029-88202661;fax: and the method can find high quality solutions at a low 86-029-88201023,e-mail:neouma@163.com
SMCB-E-03172004-0141.R2 1 Abstract—With the intrinsic properties of constraint satisfaction problems (CSPs) in mind, we divide CSPs into two types, namely, permutation CSPs and non-permutation CSPs. According to their characteristics, several behaviors are designed for agents by making use of the ability of agents to sense and act on the environment. These behaviors are controlled by means of evolution, so that the multiagent evolutionary algorithm for constraint satisfaction problems (MAEA-CSPs) results. To overcome the disadvantages of the general encoding methods, the minimum conflict encoding is also proposed. Theoretical analyses show that MAEA-CSPs has a linear space complexity and converges to the global optimum. The first part of the experiments uses 250 benchmark binary CSPs and 79 graph coloring problems from the DIMACS challenge to test the performance of MAEA-CSPs for non-permutation CSPs. MAEA-CSPs is compared with six well-defined algorithms and the effect of the parameters is analyzed systematically. The second part of the experiments uses a classical CSP, n-queen problems, and a more practical case, job-shop scheduling problems (JSPs), to test the performance of MAEA-CSPs for permutation CSPs. The scalability of MAEA-CSPs along n for n-queen problems is studied with great care. The results show that MAEA-CSPs achieves good performance when n increases from 104 to 107 , and has a linear time complexity. Even for 107 -queen problems, MAEA-CSPs finds the solutions by only 150 seconds. For JSPs, 59 benchmark problems are used, and good performance is also obtained. Index Terms—Constraint satisfaction problems, evolutionary algorithms, graph coloring problems, job-shop scheduling problems, multiagent systems, n-queen problems. I. INTRODUCTION large number of problems coming from artificial intelligence as well as other areas of computer science and engineering can be stated as Constraint Satisfaction Problems (CSPs) [1]-[3]. A CSP has three components: variables, values, and constraints. The purpose is to find an assignment of values to variables such that all constraints are satisfied. Many methods have been proposed to deal with CSPs, where backtracking and generate-and-test methods are well-known traditional approaches [1]. Although the backtracking method eliminates a Manuscript received March 17, 2004. This work is supported by the National Natural Science Foundation of China under Grant 60133010 and 60372045, and the “863” project under Grant 2002AA135080. The authors are with the Institute of Intelligent Information Processing, Xidian University, Xi’an, 710071, China Jing Liu, corresponding author, phone: 86-029-88202661; fax: 86-029-88201023; e-mail: neouma@163.com. subspace from the Cartesian product of all the variable domains, the computational complexity for solving most nontrivial problems remains exponential. Many studies have been conducted to investigate various ways of improving the backtracking method, such as consistency techniques [4], [5], the dependency-directed backtracking scheme [6], [7]. Nevertheless, it is still unable to solve nontrivial large-scale CSPs in a reasonable runtime. For the generate-and-test method, one of the most popular ideas is to employ a local search technique [8]-[10]. It generates an initial configuration and then incrementally uses “repair” or “hill climbing” to modify the inconsistent configuration to move to a neighborhood configuration having the best or better evaluation value among the neighbors, until a solution is found. As related to the idea of local search, other heuristics have also been developed, such as the min-conflicts heuristic [11], [12], GSAT [13]. In addition, local search techniques are often combined with Evolutionary Algorithms (EAs), another popular kind of method for solving CSPs. Historically, CSPs have been approached from many angles by EAs. In this field, the method used to treat the constraints is very important. The constraints can be handled directly, indirectly or by mixed methods [14]. Among the available methods, some put the emphasis on the usage of heuristics, such as ARC-GA [15], [16], COE-H GA [17], [18], Glass-Box [19], H-GA [20], [21], whereas others handle the constraints by fitness function adaptation, such as CCS [22], [23], MID [24]-[26], SAW [27], [28]. These methods dealt with CSPs by EAs from different angles and boosted the development of this field. Reference [29] has made an extensive performance comparison of all these EAs on a systematically generated test suite. Agent-based computation has been studied for several years in the field of distributed artificial intelligence [30], [31] and has been widely used in other branches of computer science [32]-[35]. Problem solving is an area with which many multiagent-based applications are concerned. It includes distributed solutions to problems, solving distributed problems, and distributed techniques for problem solving [30], [31]. Reference [33] introduced an application of distributed techniques for solving constraint satisfaction problems. They solved 7000-queen problems by an energy-based multiagent model. In [34], multiagent systems and genetic algorithms (GAs) are integrated to solve global numerical optimization problems, and the method can find high quality solutions at a low A Multiagent Evolutionary Algorithm for Constraint Satisfaction Problems Weicai Zhong, Jing Liu, and Licheng Jiao, Senior Member, IEEE A
SMCB-E-03172004-0141.R2 2 computational cost even for the functions with 10 000 should be defined when multiagent systems are used to solve dimensions.All these results show that both agents and EAs problems.The first is the meaning and the purpose ofeach agent have a high potential in solving complex and ill-defined The second is the environment in which all agents live.Since problems. each agent has only local perceptivity,so the third is the local In this paper,with the intrinsic properties of CSPs in mind, environment.The last is the behaviors that each agent can take we divide CSPs into two types,namely,permutation CSPs and to achieve the purpose. non-permutation CSPs.According to the different A.Constraint satisfaction problems characteristics of the two types of problems,several behaviors are designed for agents.Furthermore,all such behaviors are A CSP has three components: controlled by means of evolution,so that a new algorithm, 1 A finite set of variables,x=,x2,.., multiagent evolutionary algorithm for constraint satisfaction 2)A domain set D,containing a finite and discrete domain for problems(MAEA-CSPs),results.In MAEA-CSPs,all agents each variable: live in a latticelike environment.Making use of the designed D=DD.DD=d,ddo,=1.2.n(1) behaviors,MAEA-CSPs realizes the ability of agents to sense where stands for the number of elements in the set; and act on the environment in which they live.During the process of interacting with the environment and the other agents, 3)A constraint set,C=(Ci(x),C2(x),..Cm(x")),wherex, each agent increases energy as much as possible,so that i=1,2,...,m is a subset ofx,and C)denotes the values that MAEA-CSPs can find solutions.Experimental results show that the variables in x'cannot take simultaneously.For example, MAEA-CSPs provides good performance. given a constraint C(1,x2))=(di,d2),it means when xi=di,d2 From another viewpoint,since MAEA-CSPs uses a cannot be assigned to x2,and whenx2=d2,di cannot be assigned lattice-based population,it can be also considered as a kind of toxi fined-grained parallel GA.Fined-grained parallel GAs are a Thus,the search space ofa CSP,S,is a Cartesian product of kind of parallel implementation of GAs [36]-[45],and have the n sets of finite domains,namely,S=DxD2x...xD.A been applied to many problems,such as combinatorial solution for a CSP,=s,52,S,is an assignment to all optimization [46],function optimization [47],[48],scheduling variables such that the values satisfy all constraints.Here is a problems [49].But since they are just parallel techniques,they simple example: often present the same problem of premature convergence as Example 1:A CSP is described as follows: traditional GAs [50].MAEA-CSPs makes use of the ability of x={x1,X2,X3} agents in sensing and acting on the environment,and puts D={D,D2,D},D,={12,3},i=1,2,3 emphasis on designing behaviors for agents.The experimental C={C({,x)=1,3》,C2({:,x2})=3,3》, results show that MAEA-CSPs achieves good performance for various CSPs,that is,binary CSPs,graph coloring problems C({x,3)=(2,1),C4({3,3)=(2,3》 (GCPs),n-queen problems,and job-shop scheduling problems C({x1,x3)=(3,1),C6({x1x3})=3,3》, (2) (JSPs).Therefore,MAEA-CSPs is a successful development of fined-grained parallel GAs. C,({x2,x3})=1,1),Cg({x2,x)=1,2), The rest of this paper is organized as follows:Section II C,({x2,)=1,3》,Co({x2,x3)=2,1), describes the agents designed for CSPs.Section III describes C({x2,s3)=3,1} the implementation of MAEA-CSPs,and analyzes the space complexity and convergence.Section IV uses binary CSPs and All solutions for this CSP are (1,2,2),(1,2,3),(2,2,2),(2, GCPs to investigate the performance of MAEA-CSPs on 3.2).(3.2.2) non-permutation CSPs,whereas Section V uses n-queen One may be interested in finding one solution,all solutions or problems and JSPs to investigate the performance on in proving that no solution exists.In the last case,one may want permutation CSPs.Finally,conclusions are presented in Section to find a partial solution optimizing certain criteria,for example, VI as many satisfied constraints as possible.We restrict our discussion in finding one solution. II.CONSTRAINT SATISFACTION AGENTS B.Definition of constraint satisfaction agents According to [31]and [33],an agent is a physical or virtual An agent used to solve CSPs is represented as a constraint entity essentially having the following properties:(a)it is able to satisfaction agent(CSAgent),and is defined as follows: live and act in the environment:(b)it is able to sense the local Definition /A constraint satisfaction agent,a,represents an environment;(c)it is driven by certain purposes and (d)it has element in the search space,S,with energy being equal to some reactive behaviors.Multiagent systems are computational VaeS,Energy(a)=-mx(a,C) (3) systems in which several agents interact or work together in order to achieve purposes.As can be seen,the meaning of an [1 a violates C where x(a,C.)= The purpose of each agent is very comprehensive,and what an agent represents is 0 otherwise different for different problems.In general,four elements CSAgent is to maximize the energy by the behaviors it can take
SMCB-E-03172004-0141.R2 2 computational cost even for the functions with 10 000 dimensions. All these results show that both agents and EAs have a high potential in solving complex and ill-defined problems. In this paper, with the intrinsic properties of CSPs in mind, we divide CSPs into two types, namely, permutation CSPs and non-permutation CSPs. According to the different characteristics of the two types of problems, several behaviors are designed for agents. Furthermore, all such behaviors are controlled by means of evolution, so that a new algorithm, multiagent evolutionary algorithm for constraint satisfaction problems (MAEA-CSPs), results. In MAEA-CSPs, all agents live in a latticelike environment. Making use of the designed behaviors, MAEA-CSPs realizes the ability of agents to sense and act on the environment in which they live. During the process of interacting with the environment and the other agents, each agent increases energy as much as possible, so that MAEA-CSPs can find solutions. Experimental results show that MAEA-CSPs provides good performance. From another viewpoint, since MAEA-CSPs uses a lattice-based population, it can be also considered as a kind of fined-grained parallel GA. Fined-grained parallel GAs are a kind of parallel implementation of GAs [36]-[45], and have been applied to many problems, such as combinatorial optimization [46], function optimization [47], [48], scheduling problems [49]. But since they are just parallel techniques, they often present the same problem of premature convergence as traditional GAs [50]. MAEA-CSPs makes use of the ability of agents in sensing and acting on the environment, and puts emphasis on designing behaviors for agents. The experimental results show that MAEA-CSPs achieves good performance for various CSPs, that is, binary CSPs, graph coloring problems (GCPs), n-queen problems, and job-shop scheduling problems (JSPs). Therefore, MAEA-CSPs is a successful development of fined-grained parallel GAs. The rest of this paper is organized as follows: Section II describes the agents designed for CSPs. Section III describes the implementation of MAEA-CSPs, and analyzes the space complexity and convergence. Section IV uses binary CSPs and GCPs to investigate the performance of MAEA-CSPs on non-permutation CSPs, whereas Section V uses n-queen problems and JSPs to investigate the performance on permutation CSPs. Finally, conclusions are presented in Section VI. II. CONSTRAINT SATISFACTION AGENTS According to [31] and [33], an agent is a physical or virtual entity essentially having the following properties: (a) it is able to live and act in the environment; (b) it is able to sense the local environment; (c) it is driven by certain purposes and (d) it has some reactive behaviors. Multiagent systems are computational systems in which several agents interact or work together in order to achieve purposes. As can be seen, the meaning of an agent is very comprehensive, and what an agent represents is different for different problems. In general, four elements should be defined when multiagent systems are used to solve problems. The first is the meaning and the purpose of each agent. The second is the environment in which all agents live. Since each agent has only local perceptivity, so the third is the local environment. The last is the behaviors that each agent can take to achieve the purpose. A. Constraint satisfaction problems A CSP has three components: 1) A finite set of variables, x={x1, x2, …, xn}; 2) A domain set D, containing a finite and discrete domain for each variable: D={D1, D2, …, Dn}, xi∈Di ={dd d 1 2 || , , , Di } , i=1, 2, …, n (1) where |•| stands for the number of elements in the set; 3) A constraint set, C={C1(x1 ), C2(x2 ), …, Cm(xm)}, where xi , i=1, 2, …, m is a subset of x, and Ci(xi ) denotes the values that the variables in xi cannot take simultaneously. For example, given a constraint C({x1, x2})=〈d1, d2〉, it means when x1=d1, d2 cannot be assigned to x2, and when x2=d2, d1 cannot be assigned to x1. Thus, the search space of a CSP, S, is a Cartesian product of the n sets of finite domains, namely, S=D1×D2×…×Dn. A solution for a CSP, s=〈s1, s2, …, sn〉∈S, is an assignment to all variables such that the values satisfy all constraints. Here is a simple example: Example 1: A CSP is described as follows: { () () () () () () ( ) 123 123 1 12 2 12 3 13 4 13 5 13 6 13 7 23 8 2 { , , } { , , }, {1, 2, 3}, 1,2,3 { , } 1,3 , { , } 3,3 , { , } 2,1 , { , } 2,3 , { , } 3,1 , { , } 3,3 , { , } 1,1 , { i xxx DDD D i C xx C xx C xx C xx C xx C xx C xx C x = = == = = ∑ ⌡ = ∑ ⌡ = ∑ ⌡ = ∑ ⌡ = ∑ ⌡ = ∑ ⌡ = ∑ ⌡ x D C ( ) () () ( ) } 3 9 2 3 10 2 3 11 2 3 , } 1, 2 , { , } 1,3 , { , } 2,1 , { , } 3,1 x C xx C xx C xx ⌠ ⌠ ⌠ ⌠ ⌠ ⌠ 〉 ⌠ ⌠ = ∑ ⌡ ⌠ ⌠ = ∑ ⌡ = ∑ ⌡ ⌠ ⌠ = ∑ ⌡ ∫ (2) All solutions for this CSP are 〈1, 2, 2〉, 〈1, 2, 3〉, 〈2, 2, 2〉, 〈2, 3, 2〉, 〈3, 2, 2〉. One may be interested in finding one solution, all solutions or in proving that no solution exists. In the last case, one may want to find a partial solution optimizing certain criteria, for example, as many satisfied constraints as possible. We restrict our discussion in finding one solution. B. Definition of constraint satisfaction agents An agent used to solve CSPs is represented as a constraint satisfaction agent (CSAgent), and is defined as follows: Definition 1: A constraint satisfaction agent, a, represents an element in the search space, S, with energy being equal to ∀a∈S, 1 ( ) ( , ) m E i i nergy C a a = − = χ (3) where 1 violates ( , ) 0 otherwise i i C χ C = a a . The purpose of each CSAgent is to maximize the energy by the behaviors it can take.
SMCB-E-03172004-0141.R2 As can be seen,the energy of each CSAgent is the negative Example 2:The CSP is given in Example 1 with the value of the number of violated constraints.Therefore,the following S? higher the energy is,the better the CSAgent is.When the energy of a CSAgent increases to 0.the CSAgent becomes a solution. S={《,3,x）,,3,),(2,,x (6) The domain for each variable is finite and discrete,thus the (2,3,x）2〈3,1，x2）2(3,2,x} elements can be numbered by natural numbers,that is to say,the According to Decoderl,each element in S can be domain D=(di,d2,...,dop is equivalent to D=(1,2,...Dl). When all domains are transformed to the sets of natural numbers, transformed to a partial instantiation of the variables,namely, the solutions of some CSPs take on specific characteristics.On ,x2,x〉→1)(，x,x2〉→11，) the basis of them,CSPs can be divided into two types: 在，x,〉→（在1〉(2，，x）→在来 (7) Definition 2:Let S be the set of solutions for a CSP and all domain sets be represented by the sets of natural numbers.If x3,x,x2〉→(1,1〉(3，x2,x〉→(1*，) VseS is a permutation of 1,2,...,n,the CSP is defined as a where the"*"represents that the corresponding variable is left permutation CSP;otherwise it is defined as a uninstantiated.As can be seen,no element in S can be non-permutation CSP. transformed to a solution for the CSP by Decoderl. For a non-permutation CSP,the search space is still S.Since For CSAgents,we want to design an encoding method that permutation CSPs are a special case of non-permutation CSPs, not only covers solutions for any CSPs,but also maintains a the search space can be reduced to the set of all permutations of manageable search space.Therefore,on the basis of Decoder1, 1,2,...,n,that is, we propose minimum conflict encoding(MCE).In MCE,each s={B,,Pn}andP=(g,P2,,),1≤i≤nl CSAgent is represented as not only an element of S,but also andP∈{l,2,,n,1≤j≤n an element of S,so that some behaviors can be designed to deal with the values of the variables directly.As a result,each andk,1∈{l,2,,n川，(k≠)= 「P+B CSAgent must record some information,and is represented by e≠p the following structure: (4) When one uses EAs to solve problems,the search space must CSAgent Record be encoded such that individuals can be represented in a P:A permutation,PeS for permutation uniform encoding.For example,GAs usually encode the search CSPs,and PeS for non-permutation space by the binary coding,thus,each individual is a bit CSPs; sequence.For permutation CSPs,it is natural to represent each V:VeS,the value for each variable,and individual as a permutation of 1,2,....n.The search space is S for non-permutation CSPs only; with size of n!. E:The energy of the CSAgent,E=Energv(P) For non-permutation CSPs,the most straightforward for permutation CSPs,and E=Energu(V) encoding method is to represent each individual as an element for non-permutation CSPs; of S,which is used by most existing algorithms.Under this SL:The flag for the self-learning method,the search space is DD2x...xD,l.Meanwhile,some behavior,which will be defined later. methods use a permutation coding with a corresponding If SLis True,the self-learning decoder.For example,in [27],[28],each individual is behavior can be performed on the represented by a permutation of the variables,and the CSAgent;otherwise cannot; permutation is transformed to a partial instantiation by a simple End decoder that considers the variables in the order they occur in the permutation and assigns the first possible domain value to In the following text,CSAgent)is used to represent the that variable.If no value is possible without introducing a corresponding component in the above structure.By MCE,each constraint violation,the variable is left uninstantiated.In what CSAgent includes both a permutation and an assignment to all follows,this decoder is labeled as Decoderl and all variables.In fact,the assignment is what we need.So minimum permutations of the variables is labeled as S.In fact, conflict decoding(MCD)is designed corresponding to MCE, which transforms P to V.The main idea of MCD is to assign the xn,x3,…,x）eS→(《，B,…,P〉eS”） (5) value violating minimum number of constraints to a variable. Therefore,S is equivalent to S,and the size of the search The variables are considered in the order they occur in the permutation,and only the constraints between the variable and space is also n!.Decoderl uses a greedy algorithm,thus a those previously assigned values are taken into account.After serious problem exists.That is,for some CSPs,Decoderl MCD is performed,no variable is left uninstantiated.The cannot decode any permutation to a solution.As a result,the details of MCD are shown in Algorithm 1. algorithms based on Decoderl may not find solutions at all. Here is a simple example: Algorithm 1 Minimum conflict decoding
SMCB-E-03172004-0141.R2 3 As can be seen, the energy of each CSAgent is the negative value of the number of violated constraints. Therefore, the higher the energy is, the better the CSAgent is. When the energy of a CSAgent increases to 0, the CSAgent becomes a solution. The domain for each variable is finite and discrete, thus the elements can be numbered by natural numbers, that is to say, the domain D={d1, d2, …, d|D| } is equivalent to D={1, 2, …, |D|}. When all domains are transformed to the sets of natural numbers, the solutions of some CSPs take on specific characteristics. On the basis of them, CSPs can be divided into two types: Definition 2: Let S be the set of solutions for a CSP and all domain sets be represented by the sets of natural numbers. If ∀s∈S is a permutation of 1, 2, …, n, the CSP is defined as a permutation CSP; otherwise it is defined as a non-permutation CSP. For a non-permutation CSP, the search space is still S. Since permutation CSPs are a special case of non-permutation CSPs, the search space can be reduced to the set of all permutations of 1, 2, …, n, that is, { } { } { }( ) 1 2 12 ! , , ..., and , , ..., , 1 ! and 1, 2, ..., , 1 and , 1, 2, ..., , P n n i ii i j i k l k l i i PP P in P n jn kl n k l P P = = 〈 〉 ≤ ≤ ∈ ≤≤ ≠ ∀∈ ≠ ⇒ ≠ S PP P P P P (4) When one uses EAs to solve problems, the search space must be encoded such that individuals can be represented in a uniform encoding. For example, GAs usually encode the search space by the binary coding, thus, each individual is a bit sequence. For permutation CSPs, it is natural to represent each individual as a permutation of 1, 2, …, n. The search space is SP with size of n!. For non-permutation CSPs, the most straightforward encoding method is to represent each individual as an element of S, which is used by most existing algorithms. Under this method, the search space is |D1|×|D2|×…×|Dn|. Meanwhile, some methods use a permutation coding with a corresponding decoder. For example, in [27], [28], each individual is represented by a permutation of the variables, and the permutation is transformed to a partial instantiation by a simple decoder that considers the variables in the order they occur in the permutation and assigns the first possible domain value to that variable. If no value is possible without introducing a constraint violation, the variable is left uninstantiated. In what follows, this decoder is labeled as Decoder1 and all permutations of the variables is labeled as P Sx . In fact, ( ) ( ) 1 2 1 2 , ,, ,,, n P P PP P x n ∀∑ ⌡ x x x PP P ∈S S ∑ ⌡ ∈ (5) Therefore, P Sx is equivalent to SP , and the size of the search space is also n!. Decoder1 uses a greedy algorithm, thus a serious problem exists. That is, for some CSPs, Decoder1 cannot decode any permutation to a solution. As a result, the algorithms based on Decoder1 may not find solutions at all. Here is a simple example: Example 2: The CSP is given in Example 1 with the following P Sx { } 123 132 213 231 312 321 , , , , , , , , , , , , , , , , , P x xxx xxx xxx xxx xxx xxx = ∑ ⌡∑ ⌡∑ ⌡ ∑ ⌡∑ ⌡∑ ⌡ S . (6) According to Decoder1, each element in P Sx can be transformed to a partial instantiation of the variables, namely, 123 132 213 231 312 3 21 , , 1, 1, * , , 1, 1, * , , 1, 1, * , , 1, *, 1 , , 1, 1, * , , 1, *, 1 xxx xxx xxx xxx xxx xxx → → → → → → (7) where the “*” represents that the corresponding variable is left uninstantiated. As can be seen, no element in P Sx can be transformed to a solution for the CSP by Decoder1. For CSAgents, we want to design an encoding method that not only covers solutions for any CSPs, but also maintains a manageable search space. Therefore, on the basis of Decoder1, we propose minimum conflict encoding (MCE). In MCE, each CSAgent is represented as not only an element of P Sx , but also an element of S, so that some behaviors can be designed to deal with the values of the variables directly. As a result, each CSAgent must record some information, and is represented by the following structure: CSAgent = Record P: A permutation, P∈SP for permutation CSPs, and P P ∈Sx for non-permutation CSPs; V: V∈S, the value for each variable, and for non-permutation CSPs only; E: The energy of the CSAgent, E=Energy(P) for permutation CSPs, and E=Energy(V) for non-permutation CSPs; SL: The flag for the self-learning behavior, which will be defined later. If SL is True, the self-learning behavior can be performed on the CSAgent; otherwise cannot; End. In the following text, CSAgent(•) is used to represent the corresponding component in the above structure. By MCE, each CSAgent includes both a permutation and an assignment to all variables. In fact, the assignment is what we need. So minimum conflict decoding (MCD) is designed corresponding to MCE, which transforms P to V. The main idea of MCD is to assign the value violating minimum number of constraints to a variable. The variables are considered in the order they occur in the permutation, and only the constraints between the variable and those previously assigned values are taken into account. After MCD is performed, no variable is left uninstantiated. The details of MCD are shown in Algorithm 1. Algorithm 1 Minimum conflict decoding
SMCB-E-03172004-0141.R2 Input:CSAgent:the CSAgent needs to be information generated by /-behaviors can be preserved.For a decoded; new CSAgent,Pos is set to 1.MCD(CSAgent,Pos)represents Pos:the position to start MCD is performed on CSAgent. decoding; In fact,Algorithm I is just a general implementation of the Output:CSAgent(V; idea of MCD,and can be used to all kinds of CSPs.However, Let CSAgent(P)=R,xa,…,xg）,CSAgent(=(, for specific CSPs,the idea of MCD can be combined with the 2,.,vm》,and knowledge of the problems,with a more efficient implementation obtained.For example,the degree of each Conflicts(,)=∑y,C) (8) vertex can be used when dealing with GCPs,and the details will where x(v,,C,)= [1 v;violates C be shown in Section IV.B.1. Conflicts(）only 0 otherwise C.Environment of constraint satisfaction agents considers the variables assigned values.Minc In order to realize the local perceptivity of agents,the and Miny are the current minimum number of environment is organized as a latticelike structure,which is conflicts and the corresponding value. similar to our previous work in [34]. Definition 3:All CSAgents live in a latticelike environment, begin L,which is called an agent lattice.The size of L isL if (Pos=1)then where Lie is an integer.Each CSAgent is fixed on a begin lattice-point and can only interact with the neighbors.Suppose yn=1: that the CSAgent located at (i,)is represented asL, i=2: j=1,2....,Lse,then the neighbors of Lu,Neighbors are end defined as follows: else i:=Pos; Neighbors={L,L,4,Lw】 (9) repeat g=1 [i+li≠L 11 i=Lse Minc Conflicts(vp); Miny :1; j:=2; repeat The agent lattice can be represented as the one in Fig.1.Each Vr=ji circle represents a CSAgent,the data represent the position in the lattice,and two CSAgents can interact with each other if and if Conflicts(vp)<Minc then only if there is a line connecting them. begin In traditional EAs,those individuals used to generate Mine=Conflicts(vg）: offspring are usually selected from all individuals according to Miny:=j; their fitness.Therefore,the global fitness distribution of a end; population must be determined.But in nature,a global selection j=t1; does not exist,and the global fitness distribution cannot be until (jD 1) determined either.In fact,the real natural selection only occurs in a local environment,and each individual can only interact Ve Miny i with those around it.That is,in each phase,the natural evolution i:=t1: is just a kind of local phenomenon.The information can be until (in); shared globally only after a process of diffusion. end. In the aforementioned agent lattice,to achieve their purposes, CSAgents will compete with others so that they can gain more Two kinds of behaviors are designed for CSAgents,namely, resources.Since each CSAgent can only sense the local the behaviors performing on P(P-behavior)and the behaviors environment,the behaviors can only take place between the performing on V(V-behavior).When V-behaviors are CSAgent and the neighbors.There is no global selection at all, performed on a CSAgent,the energy can be updated directly. so the global fitness distribution is not required.A CSAgent But when P-behaviors are performed on a CSAgent,it must be interacts with the neighbors so that information is transferred to decoded by MCD before updating the energy.If MCD starts to them.In such a manner,the information is diffused to the whole decode from the first variable in the permutation for any agent lattice.As can be seen,the model of the agent lattice is CSAgent,the information generated by V-behaviors would loss. closer to the real evolutionary mechanism in nature than the Therefore,we set a parameter,Pos,for MCD,which is the first model of the population in traditional EAs. position changed by P-behaviors.Thus,the value of the variables before Pos is left untouched such that some
SMCB-E-03172004-0141.R2 4 Input: CSAgent: the CSAgent needs to be decoded; Pos: the position to start decoding; Output: CSAgent(V); Let 1 2 ( ) , , , PP Pn CSAgent P = ∑ ⌡ xx x , CSAgent(V)=〈v1, v2, …, vn〉, and 1 ( ) ( , ) m i ij j Conflicts v v C χ= = ∑ (8) where 1 violates ( , ) 0 otherwise i j i j v C χ v C = . Conflicts(vi ) only considers the variables assigned values. MinC and MinV are the current minimum number of conflicts and the corresponding value. begin if (Pos=1) then begin 1 : 1 Pv = ; i := 2; end else i := Pos; repeat : 1 Pi v = ; : () Min Conflicts v C Pi = ; MinV := 1; j := 2; repeat : Pi v j = ; if ( ( ) P C i Conflicts v Min < ) then begin : () M C Pi in Conflicts v = ; MinV := j; end; j := j+1; until ( | | Pi j D > ); : P V i v Min = ; i := i+1; until (i>n); end. Two kinds of behaviors are designed for CSAgents, namely, the behaviors performing on P (P-behavior) and the behaviors performing on V (V-behavior). When V-behaviors are performed on a CSAgent, the energy can be updated directly. But when P-behaviors are performed on a CSAgent, it must be decoded by MCD before updating the energy. If MCD starts to decode from the first variable in the permutation for any CSAgent, the information generated by V-behaviors would loss. Therefore, we set a parameter, Pos, for MCD, which is the first position changed by P-behaviors. Thus, the value of the variables before Pos is left untouched such that some information generated by V-behaviors can be preserved. For a new CSAgent, Pos is set to 1. MCD(CSAgent, Pos) represents MCD is performed on CSAgent. In fact, Algorithm 1 is just a general implementation of the idea of MCD, and can be used to all kinds of CSPs. However, for specific CSPs, the idea of MCD can be combined with the knowledge of the problems, with a more efficient implementation obtained. For example, the degree of each vertex can be used when dealing with GCPs, and the details will be shown in Section IV.B.1. C. Environment of constraint satisfaction agents In order to realize the local perceptivity of agents, the environment is organized as a latticelike structure, which is similar to our previous work in [34]. Definition 3: All CSAgents live in a latticelike environment, L, which is called an agent lattice. The size of L is Lsize×Lsize, where Lsize is an integer. Each CSAgent is fixed on a lattice-point and can only interact with the neighbors. Suppose that the CSAgent located at (i, j) is represented as Li,j, i, j=1,2,…,Lsize, then the neighbors of Li,j, Neighborsi,j, are defined as follows: Neighbors L L L L ij i j ij i j ij , ,, ,, = { ′ ′ ′′ ′′ , , , } (9) where 1 1 1 size i i i L i − ≠ ′ = = , 1 1 1 size j j j L j − ≠ ′ = = , 1 1 size size i iL i i L + ≠ ′′ = = , 1 1 size size j jL j j L + ≠ ′′ = = . The agent lattice can be represented as the one in Fig.1. Each circle represents a CSAgent, the data represent the position in the lattice, and two CSAgents can interact with each other if and only if there is a line connecting them. In traditional EAs, those individuals used to generate offspring are usually selected from all individuals according to their fitness. Therefore, the global fitness distribution of a population must be determined. But in nature, a global selection does not exist, and the global fitness distribution cannot be determined either. In fact, the real natural selection only occurs in a local environment, and each individual can only interact with those around it. That is, in each phase, the natural evolution is just a kind of local phenomenon. The information can be shared globally only after a process of diffusion. In the aforementioned agent lattice, to achieve their purposes, CSAgents will compete with others so that they can gain more resources. Since each CSAgent can only sense the local environment, the behaviors can only take place between the CSAgent and the neighbors. There is no global selection at all, so the global fitness distribution is not required. A CSAgent interacts with the neighbors so that information is transferred to them. In such a manner, the information is diffused to the whole agent lattice. As can be seen, the model of the agent lattice is closer to the real evolutionary mechanism in nature than the model of the population in traditional EAs
SMCB-E-03172004-0141.R2 D.Behaviors of constraint satisfaction agents end The purpose of an algorithm for solving CSPs is to find else Swap(ci c); solutions at a low computational cost as much as possible.So end; the computational cost can be considered as the resources of the i:=il; environment in which all CSAgents live.Since the resources are until (i>n); limited and the behaviors of the CSAgents are driven by their if (non-permutation CSPs)then purposes,a CSAgent will compete with others to gain more MCD(Child Pos); resources.On the bases of this,three behaviors are designed for Child(SL):=True; CSAgents to realize their purposes,that is,the competitive end. behavior,the self-learning behavior,and the mutation behavior. The former two belong to P-behaviors,whereas the last belongs In fact,Child,is generated by exchanging a small part of to V-behaviors Max and is equivalent to performing a local search around Competitive behavior:In this behavior,the energy of a Max The purpose of the competitive behavior is to eliminate CSAgent is compared with those of the neighbors.The CSAgent the CSAgents with low energy,and give more chances to the can survive if the energy is maximum;otherwise the CSAgent potential CSAgents. must die,and the child of the one with maximum energy among Self-learning behavior:As well-known,integrating local the neighbors will take up the lattice-point. searches with EAs can improve the performance.Moreover. Suppose that the competitive behavior is performed on the agents have the knowledge relating to the problems.Therefore, CSAgent located at(i,),LandM is the CSAgent with inspired by the min-conflicts heuristic [11],[12]and taking into maximum energy among the neighbors of L namely, account the encoding methods of the CSAgents,we design the MaxE Neighbors and VCSAgente Neighborsi then self-learning behavior.Suppose that this behavior is performed CSAgent(E)<Max E).If LE)<Max(E),then Max onL The details are shown in Algorithm 3. generates a child CSAgent,Child,to replace Ly,and the method is shown in Algorithm 2;otherwise L is left untouched. Algorithm 3 Self-learning behavior Input: Lij:LiP)(m1,m2,....mn)for Algorithm 2 Competitive behavior permutation CSPs,and Input:Maxu:Max/(P)=(m,m2,..,mn)for L(P)=〈xm,xm,…,Xm）for permutation CSPs,and non-permutation CSPs; Mac(P)=xmx%,…,Xm〉for L(-(v1,2,,i non-permutation CSPs; Output:Lui Pe:A predefined parameter,and a real number between 0-1; begin Output:Child:Child(P)=(c1,c2,...,cn for repeat permutation CSPs,and Repeat :False; Child,(P)=a,xa,…,x）for k=1: Iteration:=1; non-permutation CSPs; while(k≤☒n)do Swap(x,y)exchanges the values of x and y.U(0, begin 1)is a uniform random number between 0 and 1.Random(n,i)is a random integer among 1,2,..., if(Con时flicts(vm）≠0)then n and is not equal to i.Min(i,j)is the smaller begin one between i and j. Energyold=Lu/E); I:=Random(n,k); begin if (non-permutation CSPs)then Child,(P):=MaxAP); begin i:=1: Swap(x,xm）i Pos:=n+1; MCD(L Min(k,D)); repeat end if (U(0,1)<pe)then else Swap(mg,mi); begin Energynew =LuE); 1:=Random(n,i); if (Energynen<Energyold)then if (non-permutation CSPs)then begin begin Swap(x,x)i Svap(mk,ml）(Swap(xm,xm）: if (non-permutation CSPs)then if (Min(l,i)<Pos)then Pos:=Min(l,i); MCD(Li Min(k,D));
SMCB-E-03172004-0141.R2 5 D. Behaviors of constraint satisfaction agents The purpose of an algorithm for solving CSPs is to find solutions at a low computational cost as much as possible. So the computational cost can be considered as the resources of the environment in which all CSAgents live. Since the resources are limited and the behaviors of the CSAgents are driven by their purposes, a CSAgent will compete with others to gain more resources. On the bases of this, three behaviors are designed for CSAgents to realize their purposes, that is, the competitive behavior, the self-learning behavior, and the mutation behavior. The former two belong to P-behaviors, whereas the last belongs to V-behaviors. Competitive behavior: In this behavior, the energy of a CSAgent is compared with those of the neighbors. The CSAgent can survive if the energy is maximum; otherwise the CSAgent must die, and the child of the one with maximum energy among the neighbors will take up the lattice-point. Suppose that the competitive behavior is performed on the CSAgent located at (i, j), Li,j, and Maxi,j is the CSAgent with maximum energy among the neighbors of Li,j, namely, Maxi,j∈Neighborsi,j and ∀CSAgent∈Neighborsi,j, then CSAgent(E)≤Maxi,j(E). If Li,j(E) ≤ Maxi,j(E), then Maxi,j generates a child CSAgent, Childi,j, to replace Li,j, and the method is shown in Algorithm 2; otherwise Li,j is left untouched. Algorithm 2 Competitive behavior Input: Maxi,j: Maxi,j(P)=〈m1, m2, …, mn〉 for permutation CSPs, and 1 2 , ( ) , , , n ij m m m Max P = ∑ ⌡ xx x for non-permutation CSPs; pc: A predefined parameter, and a real number between 0-1; Output: Childi,j: Childi,j(P)=〈c1, c2, …, cn〉 for permutation CSPs, and 1 2 , ( ) , , , n ij c c c Child P = ∑ ⌡ xx x for non-permutation CSPs; Swap(x, y) exchanges the values of x and y. U(0, 1) is a uniform random number between 0 and 1. Random(n, i) is a random integer among 1, 2, …, n and is not equal to i. Min(i, j) is the smaller one between i and j. begin Childi,j(P) := Maxi,j(P); i := 1; Pos := n+1; repeat if (U(0, 1)<pc) then begin l := Random(n, i); if (non-permutation CSPs) then begin ( , ) i l c c Swap x x ; if (Min(l, i)<Pos) then Pos := Min(l, i); end else Swap(ci, cl); end; i := i+1; until (i>n); if (non-permutation CSPs) then MCD(Childi,j, Pos); Childi,j(SL) := True; end. In fact, Childi,j is generated by exchanging a small part of Maxi,j, and is equivalent to performing a local search around Maxi,j. The purpose of the competitive behavior is to eliminate the CSAgents with low energy, and give more chances to the potential CSAgents. Self-learning behavior: As well-known, integrating local searches with EAs can improve the performance. Moreover, agents have the knowledge relating to the problems. Therefore, inspired by the min-conflicts heuristic [11], [12] and taking into account the encoding methods of the CSAgents, we design the self-learning behavior. Suppose that this behavior is performed on Li,j. The details are shown in Algorithm 3. Algorithm 3 Self-learning behavior Input: Li,j: Li,j(P)=〈m1, m2, …, mn〉 for permutation CSPs, and 1 2 , ( ) , , , n ij m m m L P = ∑ ⌡ xx x for non-permutation CSPs; Li,j(V)=〈v1, v2, …, vn〉; Output: Li,j; begin repeat Repeat := False; k := 1; Iteration := 1; while (k≤n) do begin if ( ( )0 mk Conflicts v ≠ ) then begin Energyold := Li,j(E); l := Random(n, k); if (non-permutation CSPs) then begin ( , ) m m k l Swap x x ; MCD(Li,j, Min(k, l)); end else Swap(mk, ml ); Energynew := Li,j(E); if (Energynew≤Energyold) then begin Swap(mk, ml) ( ( , ) m m k l Swap x x ); if (non-permutation CSPs) then MCD(Li,j, Min(k, l));