SMCB-E-03172004-0141.R2 6 end generation.At each generation,the competitive behavior is else Repeat:=True; performed on each CSAgent first.As a result,the CSAgents if (Iteration<n-1)then with low energy are cleaned out from the agent lattice so that Iteration :Iteration+l there is more space developed for the CSAgents with higher else begin energy.Then,the self-learning behavior and the mutation Iteration:=1; behavior are performed according to the type of the problems k=k+1: and the state of the CSAgent.In order to reduce the end; computational cost,the two behaviors are only performed on the end best CSAgent in the current agent lattice.The process is else k:=k+l; performed iteratively until a CSAgent with zero energy is found end; or the maximum computational cost is reached. until (Repeat=True); LLASL):=False; Algorithm 4 Multiagent evolutionary end. algorithm for constraint satisfaction problems The purpose of Algorithm 3 is to find a swap for the Input: Evaluationm:The maximum number of components violating constraints in the permutation,such that evaluations for the the energy of L increases after the swap is performed.For a energy; component,the algorithm iteratively performs a swap until no Lae:The scale of the agent lattice; constraint is violated or the predefined iterative count, pe:The parameter used in the Iteration=(n-1),is achieved.Then,the algorithm goes on to deal competitive behavior; with the next component.Iteration can prevent the algorithm Pm:The parameter used in the from repeating infinitely.After the self-learning behavior has mutation behavior,and only been performed on a CSAgent,the probability that the energy of for non-permutation CSPs; Output:A solution or an approximate the CSAgent can be increased by this behavior again is very low, solution; thus LSL)is set to False in the last step. L'represents the agent lattice in the ith Although the self-learning behavior is inspired by the min-conflicts heuristic [11],[12],they are different in essence. generation.CSAgenthe is the best in Lo,L,..., First,the min-conflicts heuristic performs on the values of the L',and CSAgentiner is the best in L'. variables directly,whereas the self-learning behavior performs on the permutation.Thus the main operation of the self-learning begin behavior is swapping.Second,the min-conflicts heuristic wants for i:=1 to Lose do to find a value that minimizes the number of conflicts,whereas for j:=1 to Lsse do the self-learning behavior just improves the energy of the begin CSAgent as much as possible.Since the self-learning behavior Generate a permutation randomly and aims at a permutation,an example of the performing process assign it to Lo,(P); will be given in Section V.A.I for permutation CSPs. if (non-permutation CSPs)then Mutation behavior:This behavior is similar to the mutation MCD(L 1) operator used in traditional GAs.The function is to assist the above behaviors.It can enlarge the search area so as to make up Compute L(E); the disadvantage of the decoding method.Suppose that the L (SL)=True mutation behavior is performed on L,and Lvi,v2,.. end; v).Then,the following operation is performed onLi Evaluations:=Lex LEe: if U(0,1)pm,then v-Random(IDa) (10) Update CSAgenter Where k=1,2,...,n,and U(0,1)represents the new random t=0: number for each k.p is a predefined parameter,and is a real repeat number between 0-1.Random(D)is a random integer in 1. 2,,D for i:=1 to Lase do for j:=1 to Lste do begin III.MULTIAGENT EVOLUTIONARY ALGORITHM FOR CONSTRAINT SATISFACTION PROBLEMS if (L,wins in the competitive behavior)then A.Implementation of MAEA-CSPs 瑞= To solve CSPs,all CSAgents must orderly adopt the three behaviors.Here these behaviors are controlled by means of else:=Child (generated according evolution so that the agent lattice can evolve generation by to Algorithm 2);
SMCB-E-03172004-0141.R2 6 end else Repeat := True; if (Iteration<n-1) then Iteration := Iteration+1 else begin Iteration := 1; k := k+1; end; end else k := k+1; end; until (Repeat=True); Li,j(SL) := False; end. The purpose of Algorithm 3 is to find a swap for the components violating constraints in the permutation, such that the energy of Li,j increases after the swap is performed. For a component, the algorithm iteratively performs a swap until no constraint is violated or the predefined iterative count, Iteration=(n-1), is achieved. Then, the algorithm goes on to deal with the next component. Iteration can prevent the algorithm from repeating infinitely. After the self-learning behavior has been performed on a CSAgent, the probability that the energy of the CSAgent can be increased by this behavior again is very low, thus Li,j(SL) is set to False in the last step. Although the self-learning behavior is inspired by the min-conflicts heuristic [11], [12], they are different in essence. First, the min-conflicts heuristic performs on the values of the variables directly, whereas the self-learning behavior performs on the permutation. Thus the main operation of the self-learning behavior is swapping. Second, the min-conflicts heuristic wants to find a value that minimizes the number of conflicts, whereas the self-learning behavior just improves the energy of the CSAgent as much as possible. Since the self-learning behavior aims at a permutation, an example of the performing process will be given in Section V.A.1 for permutation CSPs. Mutation behavior: This behavior is similar to the mutation operator used in traditional GAs. The function is to assist the above behaviors. It can enlarge the search area so as to make up the disadvantage of the decoding method. Suppose that the mutation behavior is performed on Li,j, and Li,j(V)=〈v1, v2, …, vn〉. Then, the following operation is performed on Li,j. if Uk(0, 1)<pm, then vk←Random(|Dk|) (10) Where k=1, 2, …, n, and Uk(0, 1) represents the new random number for each k. pm is a predefined parameter, and is a real number between 0-1. Random(|Dk|) is a random integer in 1, 2, …, |Dk|. III. MULTIAGENT EVOLUTIONARY ALGORITHM FOR CONSTRAINT SATISFACTION PROBLEMS A. Implementation of MAEA-CSPs To solve CSPs, all CSAgents must orderly adopt the three behaviors. Here these behaviors are controlled by means of evolution so that the agent lattice can evolve generation by generation. At each generation, the competitive behavior is performed on each CSAgent first. As a result, the CSAgents with low energy are cleaned out from the agent lattice so that there is more space developed for the CSAgents with higher energy. Then, the self-learning behavior and the mutation behavior are performed according to the type of the problems and the state of the CSAgent. In order to reduce the computational cost, the two behaviors are only performed on the best CSAgent in the current agent lattice. The process is performed iteratively until a CSAgent with zero energy is found or the maximum computational cost is reached. Algorithm 4 Multiagent evolutionary algorithm for constraint satisfaction problems Input: EvaluationMax: The maximum number of evaluations for the energy; Lsize: The scale of the agent lattice; pc: The parameter used in the competitive behavior; pm: The parameter used in the mutation behavior, and only for non-permutation CSPs; Output: A solution or an approximate solution; Lt represents the agent lattice in the tth generation. t CSA Best gent is the best in L0 , L1 , …, Lt , and t CSA tBest gent is the best in Lt . begin for i:=1 to Lsize do for j:=1 to Lsize do begin Generate a permutation randomly and assign it to 0 , ( ) L P i j ; if (non-permutation CSPs) then 0 MCD( , 1) Li j , ; Compute 0 , ( ) Li j E ; 0 , ( ): i j L SL True = ; end; Evaluations := Lsize× Lsize; Update 0 CSA Best gent ; t := 0; repeat for i:=1 to Lsize do for j:=1 to Lsize do begin if ( , t Li j wins in the competitive behavior) then 1 , , : t t ij ij + L L = else 1 , : t i j i, j + L Child = (generated according to Algorithm 2);
SMCB-E-03172004-0141.R2 7 Compute (E); [2n+2 for non-permutation CSPs UnitscsAgemt (12) Evaluations:=Evaluations+1; n+2 for permutation CSPs end; The number of space units required by MAEA-CSPs in total is Update CSAgent Numuin=NumcsAgemt XUnits sAgem= if (CSAgent(SL)=True)then (+2)n+(4L+)for non-permutation CSPs (13) Perform the self-learning behavior on (2L+1)n+(4L+2)for permutation CSPs CSAgentne Since (2+1)is independent of n,the space complexity else if (non-permutation CSP)then of multiagent evolutionary algorithm for constraint satisfaction begin Perform the mutation behavior on problems is O(n). CSAgent Theorem 1 shows that the space required by MAEA-CSPs increases linearly with the scale of the problem.Ifa unit requires Compute CSAgente(E)i 4 bytes and Lse is set to 3,MAEA-CSPs requires 725M for a Evaluations :Evaluations+1; 10-queen problem since n-queen problems belong to end; non-permutation CSPs. if(CSAgent(E)<CSAgent(E))then C.Convergence of MAEA-CSPs begin In practical cases,one is interested in knowing the likelihood CSAgentge=CSAgentei of an algorithm in finding solutions for CSPs.Most existing CSAgent=CSAgentso CSAgent is algorithms based on local searches do not guarantee that randomly selected from L and is solutions can be found.When they are trapped in local optima, different from CSAgent) they always restart.MAEA-CSPs starts from a randomly generated agent lattice,and evolves the agent lattice generation end by generation with three behaviors.It has no restarting step.Can else CSAgentc=CSAgente MAEA-CSPs find solutions? 1:=h1: The search space of non-permutation CSPs with n variables has Dx D2x...xD elements,and that of permutation CSPs until (CSAgentien (E)=0)or with n variables has n!elements.Let E=(Energy(a)I aeS). (Evaluations2 EvaluationMax): Since the energy describes the negative value of the number of end. constraints not satisfied by a CSAgent and the number of all B.Space complexity of MAEA-CSPs constraints is m,E is equal to (m+1)and E can be represented When dealing with a large-scale problem,the memory as E=f-m,-m+1,...,-2,-1,0).This immediately gives us the required by an algorithm must be taken into account.For opportunity to partition S into a collection of nonempty subsets, example,although the method proposed in [33]obtained good (S'l i=m,-m+1,...,-2,-1,0),where performance,it needs to store a nxn lattice to record the number S=al aeS and Energy(a)-i) (14) of collisions in each grid and the space complexity is O(n). Thus,even if each grid is recorded by an integer with 4 bytes, ∑°1sHss+0, (15) 38,147M memory locations are still required for a 102-queen sns1=o,i≠方U8s=s problem.Therefore,the method proposed in [33]has resource Obviously,any CSAgent belonging to So is a solution. requirements exceeding those currently available from PC Suppose that the energy of an agent lattice,L,is equal to computers. Theorem I:The space complexity of multiagent evolutionary Energv(L),which is determined by, Energy(L)=max(LE)ij=1,2...,Lse) (16) algorithm for constraint satisfaction problems is O(n). Proof:The main contribution to the space complexity is from Let L stand for the set of all agent lattices.Thus,VLeL, the storage for the agent lattices in the current generation and the -m<Energv(L)<0.Therefore,L can be partitioned into a next generation and the best CSAgent.So the number of collection of nonempty subsets(L=-m,-m+1,..,-2,-1,0), CSAgents recorded is where NumcsAgenf-2XLsEeXLe+1 (11) L←{LlL∈L and Energy(L)-i} (17) For non-permutation CSPs,P,V,E,and SL should be recorded for each CSAgent.For permutation CSPs,P,E,and SL ∑IHL北上≠o, (18) should be recoded for each CSAgent.So the number of space LnL=②i≠方U°L=L units each CSAgent required is L consists of all agent lattices with zero energy. Let L,i=-m,-m+1,...,-2,-1,0,j=1,2,...,IL,stand for the ith agent lattice in L'.In any generation,the three behaviors
SMCB-E-03172004-0141.R2 7 Compute 1 , ( ) t i j E + L ; Evaluations := Evaluations+1; end; Update 1 ( 1) t t Best + CSAgent + ; if ( ) 1 ( 1) ( ) t t Best SL True + CSAgent + = then Perform the self-learning behavior on 1 ( 1) t t Best + CSAgent + else if (non-permutation CSP) then begin Perform the mutation behavior on 1 ( 1) t t Best + CSAgent + ; Compute 1 ( 1) ( ) t t Best E + CSAgent + ; Evaluations := Evaluations+1; end; if ( 1 ( 1) () () t t t Best Best E E + CSAgent CSAgent + < ) then begin 1 : t t Best Best + CSAgent CSA = gent ; 1 : t t Random Best + CSAgent CSA = gent ( t 1 Random + CSAgent is randomly selected from Lt and is different from 1 ( 1) t t Best + CSAgent + ); end else 1 1 ( 1) : t t Best t Best + + CSAgent CSAgent = + ; t := t+1; until ( ) 1 () 0 t Best E + CSAgent = or (Evaluations ≥ EvaluationMax); end. B. Space complexity of MAEA-CSPs When dealing with a large-scale problem, the memory required by an algorithm must be taken into account. For example, although the method proposed in [33] obtained good performance, it needs to store a n×n lattice to record the number of collisions in each grid and the space complexity is O(n2 ). Thus, even if each grid is recorded by an integer with 4 bytes, 38,147M memory locations are still required for a 105 -queen problem. Therefore, the method proposed in [33] has resource requirements exceeding those currently available from PC computers. Theorem 1: The space complexity of multiagent evolutionary algorithm for constraint satisfaction problems is O(n). Proof: The main contribution to the space complexity is from the storage for the agent lattices in the current generation and the next generation and the best CSAgent. So the number of CSAgents recorded is NumCSAgent=2×Lsize×Lsize+1 (11) For non-permutation CSPs, P, V, E, and SL should be recorded for each CSAgent. For permutation CSPs, P, E, and SL should be recoded for each CSAgent. So the number of space units each CSAgent required is 2 2 for non-permutation CSPs 2 for permutation CSPs n Units n + = + CSAgent (12) The number of space units required by MAEA-CSPs in total is 2 2 2 2 (4 2) (4 2) for non-permutation CSPs (2 1) (4 2) for permutation CSPs Units size size size size Num Num Units L nL L nL =× = ++ + ++ + CSAgent CSAgent (13) Since 2 (2 1) Lsize + is independent of n, the space complexity of multiagent evolutionary algorithm for constraint satisfaction problems is O(n). Theorem 1 shows that the space required by MAEA-CSPs increases linearly with the scale of the problem. If a unit requires 4 bytes and Lsize is set to 3, MAEA-CSPs requires 725M for a 107 -queen problem since n-queen problems belong to non-permutation CSPs. C. Convergence of MAEA-CSPs In practical cases, one is interested in knowing the likelihood of an algorithm in finding solutions for CSPs. Most existing algorithms based on local searches do not guarantee that solutions can be found. When they are trapped in local optima, they always restart. MAEA-CSPs starts from a randomly generated agent lattice, and evolves the agent lattice generation by generation with three behaviors. It has no restarting step. Can MAEA-CSPs find solutions? The search space of non-permutation CSPs with n variables has |D1|×|D2|×…×|Dn| elements, and that of permutation CSPs with n variables has n! elements. Let E={Energy(a) | a∈S}. Since the energy describes the negative value of the number of constraints not satisfied by a CSAgent and the number of all constraints is m, |E| is equal to (m+1) and E can be represented as E={-m, -m+1, …, -2, -1, 0}. This immediately gives us the opportunity to partition S into a collection of nonempty subsets, {Si | i=-m, -m+1, …, -2, -1, 0}, where Si ={a | a∈S and Energy(a)=i} (14) 0 - 0 - | | | |; ; , ; i i i m ij i i m i j = = = ≠∅ =∅ ∀ ≠ = ∑ SSS SS SS (15) Obviously, any CSAgent belonging to S0 is a solution. Suppose that the energy of an agent lattice, L, is equal to Energy(L), which is determined by, Energy(L)=max{Li,j(E) | i,j=1, 2, …, Lsize} (16) Let L stand for the set of all agent lattices. Thus, ∀L∈L, -m≤Energy(L)≤0. Therefore, L can be partitioned into a collection of nonempty subsets {Li | i=-m, -m+1, …, -2, -1, 0}, where Li ={L | L∈L and Energy(L)=i} (17) 0 - 0 - | | | |; ; , ; i i i m ij i i m i j = = = ≠∅ =∅ ∀ ≠ = ∑ LLL LL LL (18) L0 consists of all agent lattices with zero energy. Let Lij , i=-m, -m+1, …, -2, -1, 0, j=1, 2, …, |Li |, stand for the jth agent lattice in Li . In any generation, the three behaviors
SMCB-E-03172004-0141.R2 transform the agent lattice,L,to another one,L,and this CSAgentines and CSAgentine (E)=i.Then,(24)can be process can be viewed as a transition from LtoL Letp be obtained according to Algorithm 4. the probability oftransition fromLtoLPbe the probability Energy(L)≥Energy(L)→Vk<i,Py.-0 of transition from L to any agent lattice in L,and pu be the probability of transition from any agent lattice in L'to any agent Vk<i.pu-p0Vk<i.pu-0 (24) lattice in L.It is obvious that Suppose that 3CSAgent,CSAgent(E)=k>i.For permutation A=∑，∑8P=1,pup (19) CSPs,since CSAgent is the best CSAgent in L',it must win On the basis of the concepts above and [51],[52],the over the neighbors in the competitive behavior,and will convergence of MAEA-CSPs is proved. generate a child according to Algorithm 2.According to Theorem 2:[53]Let P n'xn'be a reducible stochastic matrix theorem 3,the probability of generating CSAgent'from which means that by applying the same permutations to rows CSAgent Be is and columns,P can be brought into the form where C: Pc4 getS4eamr之 R T (25) m'xm'is a primitive stochastic matrix and R.T0.Then -p(p.会1>0 C 0 For non-permutation CSPs,the self-learning behavior or the p'=lim p=lim 0 (20) mutation behavior will perform on CSAgent Obviously, 0 P0 if it is the self-learning behavior to is a stable stochastic matrix with p=1p",where p"ppis perform on CSAgen If it is the mutation behavior to unique regardless of the initial distribution,and psatisfies: perform on CSAgent,suppose that there are m variables in p.>0forl≤sism'and p°=0form<ism. Since the competitive behavior performs swap operations on CSAgent(V)which are different from the corresponding permutations for both non-permutation and permutation CSPs. ones in CSAgent().Then,the probability of generating the probability of transforming a permutation to another one by CSAgent from CSAgent by the mutation behavior is: the this behavior is analyzed in theorem 3. Pc4gemn→c4gm=pR·(（l-Pn）r-4>0 (26) Theorem 3:Let P=(P1,P2....,Pes,=(... )S,and PO.Let pobe the probability of transforming So the probability of transition from Lto any agent lattice in L 2 to P by Algorithm 2. Suppose that Pgh≥Pcs4>0 (27) DifB={g,lie{L,2,…,n and P.≠Q} and 口 Same =to lie(1,2,.,n)and P=0).Then Therefore,Vkzi,Pu2py>0. It follows from this theorem that there is always a positive Pe-p21-p.)1.(p.1 (21) probability to transit from an agent lattice to the one with Proof:When performing Algorithm 2 on O,the probability of identical or higher energy and a zero probability to the one with the elements in Same are left untouched is lower energy.Thus,once MAEA-CSPs enters Lo,it will never escape Pae=(（l-p)m8别 (22) Theorem 5:Multiagent evolutionary algorithm for constraint For each element in Diff,if (0,1)is smaller than pe it satisfaction problems converges to the global optimum as time tends to infinity would be swapped with another elements in 2.If for Proof:It is clear that one can consider each L',ie E,as a state vOE Dife,the swap operation selectso,e Diff and O=P, in a homogeneous finite Markov chain.According to theorem 4, Same will be left untouched.Such swaps can let the last two the transition matrix of the Markov chain can be written as follows: elements in Dife become identical with the corresponding Poo 0 ones in P by one swap.Therefore,the maximum number of 1 swap operations is Diffe-1.Then, p'= P.1.0 (28) Pgp≥p(n.1.1-p.) P.m. (23)a P.m.o =-p.)1.(p.yH Obviously,R=-p.10p20…P.m0)>0,T0,C-(po.0)(1)0. Theorem 4:In multiagent evolutionary algorithm for According to theorem 2,Pis given by, constraint satisfaction problems,i,=0. >0,k2i C P =lim p"=lim k-o 0) (29) Proof:Let L,iE=1,2,...,Lbe the agent lattice in the th generation,and be labeled as L'.The best CSAgent among L'be where C=(1),R=(1 1...1).Thus,P'is a stable stochastic
SMCB-E-03172004-0141.R2 8 transform the agent lattice, Lij , to another one, Lkl, and this process can be viewed as a transition from Lij to Lkl. Let pij.kl be the probability of transition from Lij to Lkl, pij.k be the probability of transition from Lij to any agent lattice in Lk , and pi.k be the probability of transition from any agent lattice in Li to any agent lattice in Lk . It is obvious that | | . . 1 k ij k ij kl l p p = = ∑ L , 0 . - 1 ij k k mp = ∑ = , pi.k≥pij.k (19) On the basis of the concepts above and [51], [52], the convergence of MAEA-CSPs is proved. Theorem 2: [53] Let P′: n′×n′ be a reducible stochastic matrix which means that by applying the same permutations to rows and columns, P′ can be brought into the form C 0 R T , where C: m′×m′ is a primitive stochastic matrix and R, T≠0. Then 1 =0 lim lim k k k - k k i ki k i ∞ ∞ →∞ →∞ − ∞ ′ ′ = = ∑ 0 0 0 C C P= P T RC T R (20) is a stable stochastic matrix with P′ ∞=1′p∞, where p∞=p0 P′ ∞ is unique regardless of the initial distribution, and p∞ satisfies: 0 i p∞ > for 1≤i≤m′ and 0 i p∞ = for m′<i≤ n′. Since the competitive behavior performs swap operations on permutations for both non-permutation and permutation CSPs, the probability of transforming a permutation to another one by the this behavior is analyzed in theorem 3. Theorem 3: Let P=〈P1, P2, …, Pn〉∈SP , Q=〈Q1, Q2, …, Qn〉∈SP , and P≠Q. Let pQ→P be the probability of transforming Q to P by Algorithm 2. Suppose that Diff Q i n P Q =∈ ≠ { i ii | {1, 2, , } and } Q P and Same Q i n P Q =∈ = { i ii | {1, 2, , } and } Q P . Then | |1 | |1 1 (1 ) ( ) Same Diff c c n ppp + − → ≥− ⋅ ⋅ Q Q P P Q P . (21) Proof: When performing Algorithm 2 on Q, the probability of the elements in SameQ P are left untouched is | | (1 ) Same same c p p = − Q P (22) For each element in Diff Q P , if U(0, 1) is smaller than pc, it would be swapped with another elements in Q. If for ∀ ∈ Q Diff i Q P , the swap operation selectsQ Diff j ∈ Q P and Qj=Pi, SameQ P will be left untouched. Such swaps can let the last two elements in Diff Q P become identical with the corresponding ones in P by one swap. Therefore, the maximum number of swap operations is Diff −1 Q P . Then, 1 | |1 | |1 | |1 1 ( ) (1 ) (1 ) ( ) Diff same c c n Same Diff c c n p pp p p p − → + − ≥ ⋅ ⋅ ⋅− =− ⋅ ⋅ Q P Q Q P P Q P (23) Theorem 4: In multiagent evolutionary algorithm for constraint satisfaction problems, ∀i, k∈E, , 0, 0, i k k i p k i > ≥ = = < . Proof: Let Lij , i∈E, j=1, 2, …, |Li | be the agent lattice in the tth generation, and be labeled as Lt . The best CSAgent among Lt be t CSA tBest gent , and ( ) t CSAgenttBest E = i . Then, (24) can be obtained according to Algorithm 4. Energy(Lt+1) ≥ Energy(Lt ) ⇒ ∀k<i, pij.kl=0 ⇒ ∀k<i, pij.k= | | . 1 k ij kl l p ∑ = L =0 ⇒ ∀k<i, pi.k=0 (24) Suppose that ∃CSAgent′, CSAgent′(E)=k>i. For permutation CSPs, since t CSA tBest gent is the best CSAgent in Lt , it must win over the neighbors in the competitive behavior, and will generate a child according to Algorithm 2. According to theorem 3, the probability of generating CSAgent′ from t CSA tBest gent is | |1 | |1 1 (1 ) ( ) 0 t tBest t t tBest tBest Same Diff c c n p p p ′ ′ → ′ + − ≥ − ⋅⋅ > CSAgent CSAgent CSAgent CSAgent CSAgent CSAgent (25) For non-permutation CSPs, the self-learning behavior or the mutation behavior will perform on t CSA tBest gent . Obviously, t 0 tBest p → ′ > CSAgent CSAgent if it is the self-learning behavior to perform on t CSA tBest gent . If it is the mutation behavior to perform on t CSA tBest gent , suppose that there are n1 variables in ( ) t CSA tBest gent V which are different from the corresponding ones in CSAgent′(V). Then, the probability of generating CSAgent′ from t CSA tBest gent by the mutation behavior is: 1 1 t (1 ) 0 tBest n nn m m p pp − → ′ = ⋅− > CSAgent CSAgent (26) So the probability of transition from Lij to any agent lattice in Lk is . t 0 tBest ij k p p → ′ ≥ > CSAgent CSAgent (27) Therefore, ∀k≥i, pi.k≥pij.k>0. It follows from this theorem that there is always a positive probability to transit from an agent lattice to the one with identical or higher energy and a zero probability to the one with lower energy. Thus, once MAEA-CSPs enters L0 , it will never escape. Theorem 5: Multiagent evolutionary algorithm for constraint satisfaction problems converges to the global optimum as time tends to infinity. Proof: It is clear that one can consider each Li , i∈E, as a state in a homogeneous finite Markov chain. According to theorem 4, the transition matrix of the Markov chain can be written as follows: 0.0 -1.0 -1.-1 - .0 - .-1 - .- 0 0 0 m m mm p p p pp p ′ = 0 C P = R T (28) Obviously, R=(p-1.0 p-2.0 … p-m.0) T >0, T≠0, C=(p0.0)=(1)≠0. According to theorem 2, P′ ∞ is given by, 1 =0 lim lim k k k - i ki k k k i ∞ ∞ →∞ →∞ − ∞ ′ ′ = = ∑ 0 0 0 C C P= P T RC T R (29) where C∞=(1), R∞=(1 1 … 1)T . Thus, P′∞ is a stable stochastic