{'fraction_non_alphanumeric': 0.03612431868259307, 'fraction_numerical': 0.013133480227299084, 'mean_word_length': 4.335344160866202, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
AED: An Anytime Evolutionary DCOP Algorithm

Evolutionary optimization is a generic population-based metaheuristic that can be adapted to solve a wide variety of optimization problems and has proven very effective for combinatorial optimization problems. However, the potential of this metaheuristic has not been utilized in Distributed Constraint Optimization Problems (DCOPs), a well-known class of combinatorial optimization problems. In this paper, we present a new population-based algorithm, namely Anytime Evolutionary DCOP (AED), that adapts evolutionary optimization to solve DCOPs. In AED, the agents cooperatively construct an initial set of random solutions and gradually improve them through a new mechanism that considers the optimistic approximation of local benefits. Moreover, we propose a new anytime update mechanism for AED that identifies the best among a distributed set of candidate solutions and notifies all the agents when a new best is found. In our theoretical analysis, we prove that AED is anytime. Finally, we present empirical results indicating AED outperforms the state-of-the-art DCOP algorithms in terms of solution quality.


Introduction
Distributed Constraint Optimization Problems (DCOPs) are a widely used framework to model constraint handling problems in cooperative Multi-agent Systems (MAS). In particular, agents in this framework need to coordinate value assignments to their variables in such a way that minimize constraint violations by optimizing their aggregated costs (Yokoo et al. 1998). This framework has been applied to various area of multi-agent coordination including distributed meeting scheduling (Maheswaran et al. 2004), sensor networks (Farinelli, Rogers, and Jennings 2014) and smart grids (Fioretto et al. 2017).
Over the last two decades, a number of algorithms have been proposed to solve DCOPs, and they can be broadly classified into two classes: exact and non-exact. The former always provide an optimal solution of a given DCOP. Among the exact algorithms, ADOPT (Modi et al. 2005), DPOP (Petcu and Faltings 2005), and PT-FB (Litov and Meisels 2017) are widely used. Since solving DCOPs optimally is NP-hard, scalability becomes an issue as the system grows. In contrast, non-exact algorithms compromise some solution quality for scalability. As a consequence, diverse classes of non-exact algorithms have been developed to deal with large-scale DCOPs. Among them, local search based algorithms are generally most inexpensive in terms of computational and communication cost. Some well-known algorithms of this class are DSA (Zhang et al. 2005), MGM & MGM2 (Maheswaran, Pearce, and Tambe 2004), and GDBA (Okamoto et al. 2016). Also, in order to further enhance solution quality and incorporate anytime property in local search based algorithms, Anytime Local Search (ALS) framework (Zivan, Okamoto, and Peled 2014) is introduced. While inference based non-exact approaches such as Max-Sum (Farinelli et al. 2008) and Max-Sum ADVP (Zivan and Peled 2012) have also gained attention due to their ability to explicitly handle n-ary constraints and guarantee optimality on an acyclic constraint graphical representations of DCOPs. The third class of non-exact approaches that have been developed are sample-based algorithms (e.g. DUCT (Ottens, Dimitrakakis, and Faltings 2012) and PD-Gibbs (Thien et al. 2019)) in which the cooperative agents sample the search space in a decentralized manner to solve DCOPs.
More recently, a new class of non-exact DCOP algorithms have emerged in the literature through the introduction of a population-based algorithm ACO DCOP (Chen et al. 2018). ACO DCOP is derived from a centralized population-based approach called Ant Colony Optimization (ACO) (Dorigo, Birattari, and Stützle 2006). It has been empirically shown that ACO DCOP produces solution with better quality than the state-of-the-art DCOP solvers of the previous three classes. It is worth noting that although a wide variety of centralized population-based algorithms exist, ACO is the only such method that has been adapted to solve DCOPs. Among the remaining centralized populationbased algorithms, a large portion is considered as evolutionary optimization techniques (e.g. Genetic Algorithm (Holland and others 1975), Evolutionary Programming (Fogel 1966)). Evolutionary optimization, as a population-based metaheuristic, has proven very effective in solving combinatorial optimization problems such as Traveling Salesman Problem (Fogel 1988), Constraint Satisfaction Problem (Tsang and Warwick 1990), and many other besides. However, no prior work exists that adapts evolutionary optimization techniques to solve DCOPs. Considering the effectiveness of evolutionary optimization techniques in solving combinatorial optimization problems along with the potential of population-based DCOP solver demonstrated by ACO DCOP motivates us to explore this unexplored area.
Against this background, this paper proposes a new population-based algorithm that adapts evolutionary optimization to solve DCOPs, that we call Anytime Evolution-ary DCOP (AED). In more detail, AED maintains a set of candidate solutions that are distributed among the agents, and the agents search for new improved solutions by modifying the candidate solutions. This modification is done through a new mechanism that considers optimistic approximation of local benefits and utilizes cooperative nature of the agents. Moreover, we introduce a new anytime update mechanism in order to identify the best among this distributed set of candidate solutions and help the agents to coordinate value assignments to their variables based on the best candidate solution. Additionally, our theoretical analysis proves the anytime property of AED. Finally, we empirically evaluate AED that shows superior solution quality compared to the state-of-the-art non-exact DCOP algorithms.

Background
In this section, we first describe DCOPs and Evolutionary Optimization in more details. Then, we discuss challenges that need to be addressed in order to effectively adapt evolutionary optimization in the context of DCOPs.

Distributed Constraint Optimization Problems
Formally, a DCOP is defined by a tuple X, D, F, A, δ (Modi et al. 2005) where, • A is a set of agents {a 1 , a 2 , ..., a n }.
• X is a set of discrete variables {x 1 , x 2 , ..., x m }, which are being controlled by the set of agents A.
• D is a set of discrete and finite variable domains {D 1 , D 2 , ..., D m }, where each D i is a set containing values which may be assigned to its associated variable x i .
• F is a set of constraints {f 1 , f 2 , ..., f l }, where f i ∈ F is a function of a subset of variables x i ⊆ X defining the relationship among the variables in x i . Thus, the function f i : × xj ∈x i D j → R denotes the cost for each possible assignment of the variables in x i .
• δ : X → A is a variable-to-agent mapping function which assigns the control of each variable x i ∈ X to an agent of A. Each variable is controlled by a single agent. However, each agent can hold several variables.
Within the framework, the objective of a DCOP algorithm is to produce X * ; an assignment to all the variables that minimize 1 the aggregated cost of the constraints as shown in Equation 1.
For ease of understanding, we assume that each agent controls one variable and constraints are binary. Thus, the terms 'variable' and 'agent' are used interchangeably throughout this paper. Figure 1a illustrates a sample example of DCOP using a constraint graph where each node represents an agent a i ∈ A labeled by a variable x i ∈ X that it controls and each edge represents a function f i ∈ F connecting all x j ∈ x i . Figure 1b shows corresponding cost tables.
1 For a maximization problem the argmin operator should be replaced with argmax in Equation 1.

Evolutionary Optimization
Evolutionary optimization is a generic population-based metaheuristic inspired by biological evolutionary mechanisms such as Selection, Reproduction, Migration. The core mechanism of evolutionary optimization techniques can be summarized in three steps. In the first step, an initial population is generated randomly. A population is a set of 'individuals', each of which is a candidate solution of the corresponding optimization problem. In addition, a fitness function is defined to evaluate the quality of an individual with respect to global objective. Fitness of all the individuals in the initial population is also calculated. In the second step, a subset of the population is selected based on their fitness to reproduce new individuals. This process is known as Selection. In the final step, new individuals are created using the selected subset of the population and their fitness are evaluated. A subset of the old individuals is then replaced by the new individuals. Evolutionary optimization performs both the second and the third steps iteratively, which results in a gradual improvement in the quality of individuals. An additional step is performed at regular intervals by some parallel/distributed evolutionary optimization models that concurrently maintain multiple sub-populations instead of a single population. In this step, individuals are exchanged between sub-populations. This process is known as Migration and this interval is known as the Migration Interval.

Challenges
We need to address the following challenges in order to develop an effective anytime algorithm that adapts evolutionary optimization to solve DCOPs: • Individual and fitness: We need to define an individual that represents a solution of a DCOP along with a fitness function to evaluate its quality with respect to Equation 1. We also need to provide a method for calculating this fitness function in a distributed manner.
• Population: We need to provide a strategy to maintain the population collectively among the agents. Although creating an initial random population is a trivial task for centralized problems, we need to find a distributed method to construct an initial random population for a DCOP.
• Reproduction mechanism: In the DCOP framework, information related to the entire problem is not available to any single agent. So it is necessary to design a Reproduction method that can utilize information available to a single agent along with the cooperative nature of the agents.

Figure 2: BFS Pseudo-Tree
• Anytime update mechanism: We need to design an anytime update mechanism that can successfully perform following tasks -(i) Identify the best individual in a population that is distributed among the agents. (ii) Notify all the agents when a new best individual is found. (iii) Help coordinate the variable assignment decision based on the best individual in a population.
In the following section, we describe our method that addresses the above challenges.

Anytime Evolutionary DCOP Algorithm
AED is a synchronous iterative algorithm that consists of two phases: Initialization and Optimization. During the former, agents initially order themselves into a pseudo-tree, then initialize necessary variables and parameters. Finally, they make a random assignment to the variables they control and cooperatively construct the initial population. During the latter phase, agents iteratively improve this initial set of solutions. When an agent detects a better solution, it notifies other agents. Moreover, all the agents synchronously update their assignments based on the best of the individuals reported to them so far, resulting in a monotonous improvement of the global objective. Algorithm 1 shows the pseudo-code for AED. For ease of understanding, we show the process of initialization and anytime update separately in Procedure 1 and Procedure 2, respectively. Note that the initialization phase addresses the first two of our challenges, while optimization phase addresses the rest. Initialization Phase of AED consists of two parts; pseudo-tree construction and running INIT (Procedure 1) that initializes the population, parameters and variables (Algorithm 1: Line 1-2). This phase starts by ordering the agents into a Pseudo-Tree. This ordering serves two purposes− helps in the construction of the initial population and facilitates ANYTIME-UPDATE (Procedure 2) during the optimization phase. Even though either of the BFS or DFS pseudo-tree can be used, AED uses BFS Pseudo-tree. This is because it generally, produce pseudo-tree with smaller height (Chen, He, and He 2017), which improves performance of ANYTIME-UPDATE (see Theoretical Analysis for details). Figure 2 shows an example of a BFS pseudo-tree constructed from constraint graph shown in Figure 1a having x 4 as root. Here, the height 2 (i.e. H = 2) of this pseudo-tree is calculated during the time of construction and is maintained by all agents. From this point, N i refers to the set of neighbours; C i ⊆ N i refers to the set of child nodes and P R i refers to parent of an agent a i in the pseudo-tree. For instance, we can see in Figure 2 that N 2 = {a 1 , a 3 , a 4 }, C 2 = {a 1 , a 3 } and P R 2 = a 4 for agent a 2 . After the 2 Length of the longest path in the pseudo-tree.
pseudo-tree construction, all the agents synchronously call the procedure INIT (Algorithm 1: Line 2).
INIT starts by initializing all the parameters and variables to their default values 3 . Then each agent a i sets its variable x i to a random value from its domain D i . Lines 3 to 25 of Procedure 1 describe the initial population construction process. In AED, we define population P as a set of individuals that are collectively maintained by all the agents and local population P ai ⊆ P as the subset of the population maintained by agent a i . An individual in AED is represented by a complete assignment of variables in X and fitness calculated using a fitness function shown in Equation 2. This function calculates the aggregated cost of constraints yielded by the assignment. Hence, optimizing this fitness function results in an optimal solution for the corresponding DCOP.
Note that the fitness function can not be calculated by a single agent rather it is calculated in parts with cooperation of all the agents during the construction process. Moreover, the fitness value is added in the representation of an individual because it enables an agent to recalculate the fitness when a new individual is constructed only using local information. We take I = {x 1 = 1, x 2 = 2, x 3 = 1, x 4 = 2, f itness = 38} as an example of a complete individual from the DCOP shown in Figure 1. We use dot(.) notation to refer to a specific element of an individual. For example I.x 1 refers to x 1 in I. Additionally, we define a Merger operation of two individuals under construction, I 1 , I 2 as Merge(I 1 , I 2 ). This operation constructs a new individual I 3 by aggregating the assignment and setting I 3 .f itness = I 1 .f itness + I 2 .f itness. We define an extended Merge operation for two ordered sets of individuals S 1 and S 2 as At the beginning of the construction process, each agent a i sets P ai to a set of empty individuals 4 . The size of the initial P ai is defined by parameter IN. Then for each individual I ∈ P ai , agent a i makes a random assignment to I.x i . After that each agent a i executes merger operation on P ai with each local population maintained by agents in N i (Procedure 1: Line 2-8). At this point, an individual I ∈ P ai consists of an assignment of variables controlled by a i , and agents in N i with fitness set to zero. For example, I = {x 1 = 1, x 2 = 2, x 3 = 1, f itness = 0} represents an individual of P a3 . The fitness of each individual is then set to the local cost according to their current assignment (Procedure 1: Line 9-10). Hence, the individual I from the previous ex- In the next step, each agent a i executes a merger operation on P ai with each local population that are maintained by agent in C i . Then each agent a i sends P ai to P R i apart from root (Procedure 1: Line 11-18). At the end of this step, the local population maintained by root consists of complete individuals. However, their fitness is twice its actual value since each constraint is calculated twice. Therefore, the root agent at this stage corrects all the fitness values (Procedure 1: Lines 20-21). Finally, the local population of the root agent is distributed through the network so that agents can initialize their local population (Procedure 1: Line 22-25). This concludes the initialization phase and after that, all the agents synchronously start the optimization phase in order to iteratively improve this initial set of population.
Optimization Phase of AED consists of five steps, namely Selection, Reproduction, ANYTIME-UPDATE, local population update and Migration. An agent a i begins an iteration of this phase by selecting individuals from P ai for the Reproduction step (Algorithm 1: Line 4). Prior to this selection, all the individuals are ranked from (0, R max ] based on their relative fitness in the local population P ai . The rank R j of a individual I j ∈ P ai is calculated using Equation 3. Here, I best and I worst are the individuals with the lowest and highest fitness in P ai respectively 5 . We define Select rp (S) as the process of taking a sample with replacement 6 of size S from population P ai based on the probability calculated using Equation 4. As α increases in Equation 4, the fitness vs. selection probability curve gets steeper. As a consequence, individuals with better fitness get selected more often. In this way, α controls the exploration and exploitation dynamics in the Selection mechanism. For example, assume P ai consist of 3 individuals I 1 , I 2 , I 3 with fitness 16, 30, 40 respectively and R max = 5. Then Equations 3 and 4 will yield, P (I 1 ) = 0.705, P (I 2 ) = 0.295, P (I 3 ) = 0 if α = 1 and P (I 1 ) = 0.932, P (I 2 ) = 0.068, P (I 3 ) = 0 if α = 3. During this step, each agent a i selects |N i | * ER individuals 4 Individuals with no assignment and fitness set to 0. 5 For minimization problems, lower value of fitness is better. 6 Any individual can be selected more than once. Send Pa i to all agent in Ci from P ai which we define as P selected .
Now, lines 5 to 11 of Algorithm 1 illustrate our proposed Reproduction mechanism. Agents start this step by partitioning P selected into |N i | subsets of size ER. Then each subset is randomly assigninged to an unique neighbour. The subset assigned to n j ∈ N i is denoted by P nj new . An agent a i creates new individual from each I ∈ P nj new with cooperation of neighbour n j . Initially, agent a i changes assignment I.x i by sampling from its domain D i using Equations 5 and 6. Then, P nj new is sent to n j . Agent n j updates its assignment of I.x j for each I ∈ P ai received (i.e. P nj new ) using Equation 7. Additionally, both agents a i and n j update the fitness of the individual I by adding δ i and δ j to I.fitness, respectively. Here, δ * is calculated using Equation 8 where I.x new * and I.x old * are the old and new values of I.x * , respectively.
To summarize the Reproduction mechanism, each agent a i picks a neighbour n j randomly for each I ∈ P selected . Agent a i then updates I.x i by sampling based on the most optimistic cost (i.e. the lowest cost) of the constraint between a i and n j and aggregated cost of the remaining local constraints. This cost represents the optimistic local benefit for each domain value. Then n j sets I.x j to a value that complements the optimistic change in I.x i most. The key insight of this mechanism is that it not only takes into account the improvement in fitness that the change in I.x i will bring but also considers the potential improvement the change in I.x j will bring. Moreover, note that the parameter β in Equation 6 plays a similar role as parameter α in Equation 3. After the newly constructed individuals added to P ai , the best individual B is sent for ANYTIME-UPDATE (Algorithm 1: Line 12-14).
To facilitate the anytime update mechanism, each agent maintains four variables LB, GB, FM, UM. LB (Local Best) and GB (Global Best) is initialized to empty individuals with fitness set to infinity. FM and UM are initialized to ∅. Additionally, GB is stored with a version tag and each agent maintains previous versions of GB having version tags in the range [Itr − H + 1, Itr] (see theoretical section for details). Here, Itr refers to the current iteration number. We use GB j to refer to the latest version of GB with version tag not exceeding j. Our proposed anytime update mechanism works as follows. Each agent keeps track of two different best, LB and GB. Whenever fitness of LB becomes less than GB it has the potential to be the global best solution. So it gets reported to the root through the propagation of a Found message up to the pseudo-tree. Since the root gets reports from all the agents, it can identify the true global best solution, and notify all the agents by propagating an Update message down to the pseudo tree. The root also adds the version tag in the Update message to help coordinate variable assignment. Now, ANYTIME-UPDATE starts by keeping LB updated with the best individual B in P ai . In line 3 of Procedure 2, agents try to identify whether LB is the potential global best. When identified and if the identifying agent is the root, it is the true global best and an Update message UM is constructed. If the agent is not root, it is a potential global best and a Found message FM is constructed (Procedure 2: Lines 4-8). Each agent forwards the message UM to agents in C i and the message FM to the P R i . Upon receiving these messages, an agent takes the following actions: • If an Update message is received then an agent updates both its GB and LB. Additionally, the agent saves the Update message in UM and sends it to all the agents in C i during the next iteration (Procedure 2: Lines 12-15).
• If a Found message is received and it is better than LB, only LB is updated. If this remains a potential global best it will be sent to P R i during next iteration (Procedure 2: Lines 16-17). An agent a i then updates the assignment of x i using GB Itr−H+1 (Procedure 2: Lines 18-19). Agents make decisions based on GB Itr−H+1 instead of potentially newer GB Itr so that decisions are made based on the same version of GB. GB Itr−H+1 will be same for all agents since it takes at most H iterations for an Update message to propagate to all the agents. For example, assume agent a 1 from Figure 2 finds a potential best individual I at Itr = 3. Unless it gets replaced by a better individual, it will reach the root a 4 via agent a 2 through a Found message at Itr = 4. Then a 4 constructs an Update message {V ersion : 5, Individual : I} at Itr = 5. This message will reach all the agents by Itr = 6 and the agents save it as GB 5 = I. Finally, at Itr = 6 agents assign their variables using GB 6−2+1 = GB 5 which is the best individual found at Itr = 3.
After ANYTIME-UPDATE, each agent a i updates their P ai by keeping a sample of size |N i | * ER and discard the rest. This sample is taken using Select wrp (S) which is the same as Select rp (S, ) except agents sample without replacement 7 . This sampling method keeps population P ai diverse by selecting a unique set of individuals.
Finally, Migration step takes place on every MI iteration which we sketch in lines 16-20 of Algorithm 1. For this step, we define Itr M as iteration number when the last Migration occurred. Migration is a simple process of local population exchange among neighbours through which individuals get to traverse around the network. Since the Reproduction mechanism only utilizes local information and local cooperation, this step plays an important role in the global optimization process. During this step, an agent a i selects a sample of size ER using Select wrp (S) for each n j ∈ N i , and sends a copy of those individual to that neighbour. Upon collecting individuals from all the neighbours, an agent a i adds them to its local population P ai . This concludes an iteration of the optimization phase and every step repeats during the following iteration.

Theoretical Analysis
As discussed in the previous section, we introduce a new mechanism that incorporates anytime property with AED. In this section, we first prove that AED is anytime, that is the quality of solutions found by AED increase monotonically. Then we analyze the complexity of AED in terms of communication, computation, and memory requirements.
Lemma 1. At iteration i+H, the root agent is aware of the best individual in P at least up to iteration i.
Suppose, the best individual up to iteration i is found at iteration i ≤ i by agent a x at level l . Afterwards, one of the following 2 cases will occur at each iteration.
• Case 1. This individual will be reported to the parent of the current agent through a Found message.
• Case 2. This individual gets replaced by a better individual on its way to root at iteration i * > i by agent a y at level l * . When only case 1 occurs, the individual will reach the root at iteration i + l ≤ i + H (since l can be at most H). If case 2 occurs, the replaced individual will reach the root agent by i * + l * = {i * − (l − l * )} + {(l − l * ) + l * } = i + l ≤ i + H. The same can be shown when the new individual gets replaced. In either case, at iteration i+H, the root will become aware of the best individual in P up to iteration i or will become aware of a better individual in P found at iteration i * > i; meaning root will be aware of the best individual in P at least up to iteration i. Lemma 2. The variable assignment decision taken by all the agents at iteration i+2H-1 yield a global cost equal to fitness of the best individual in P at least up to iteration i.
At iteration i+2H-1, all the agents take decision about variable assignment using GB i+H . However, GB i+H is the best individual known to the root up to iteration i+H. We know from Lemma 1 that, at iteration i+H, the root is aware of the best individual in P at least up to iteration i. Hence, the fitness of GB i+H is at least equal to the best individual in P up to iteration i. Hence, at iteration i+2H-1, it yields global cost equal to the fitness of the best individual in P at least up to iteration i.
Proposition 1. AED is anytime. From Lemma 2, the decision regarding the variable assignment at iteration i + 2H − 1 and i + 2H − 1 + δ yield global cost equal to the fitness of the best individual in P at least up to iteration i and i + δ (δ ≥ 0), respectively. Now, the fitness of the best individual in P up to iteration i + δ ≤ iteration i. So the global cost at iteration i + δ is less than equal to the same cost at iteration i. As a consequence, the quality of the solution monotonically improves as the number of iteration increases. Hence, AED is anytime.

Complexity Analysis
Assume, n is the number of agents, |N| is the number of neighbours and |D| is the domain size of an agent. In every iteration, an agent sends 2|N | messages during the Reproduction step. Additionally, at most |N | messages are passed for ANYTIME-UPDATE and Migration step. Now, |N | can be at most n (complete graph). Hence, the total number of messages transmitted per agent during an iteration is O(4|N |) = O(n). Since the main component of a message in AED is the set of individuals, the size of a single message can be calculated as the size of an individual multiplied by the number of individuals. During the Reproduction, Migration and ANYTIME-UPDATE steps, at most ER individuals, each of which has size O(n), is sent in a single message. As a result, the size of a single message is O(ER * n). Which makes the total message size per agent during an iteration O(ER * n * n) = O(n 2 ).
Before Reproduction, |P ai | can be at most 2ER * |N | (if Migration occurred in the previous iteration) and Reproduction will add ER * |N | individuals. So the memory requirement per agent is O(3 * ER * |N | * n) = O(n 2 ). Finally, Reproduction using Equation 5, 6, 7, and 8 requires |D i | * |N | operations and in total ER * |N | individuals are reproduced during an iteration per agent. Hence, the total computation complexity per agent during an iteration is O(ER * |N | * |D| * |N |) = O(|D| * n 2 ).

Experimental Results
In the previous section, we prove AED is anytime. Now, we empirically evaluate the quality of anytime solution produced by AED compared to six different state-of-the-art DCOP algorithms. We select these algorithms to represent all four classes of non-exact algorithms. Firstly, among the local search algorithms, we pick DSA (P = 0.8, this value of P yielded the best performance in our settings), MGM2 and GDBA (N,NM,T;reported to perform best (Okamoto et al. 2016)). Secondly, among the inference-based nonexact algorithms, we compare with Max-Sum ADVP− as it has empirically shown to perform significantly better than Max-Sum (Zivan and Peled 2012). Thirdly, we consider a sampling-based algorithm, namely PD-Gibbs, which is the only such algorithm that is suitable for large-scale DCOPs (Thien et al. 2019). Finally, we compare with ACO DCOP (i.e. the pipe-lined version) as it is only available populationbased DCOP algorithm. To evaluate ACO DCOP, we use the same values of the parameters as recommended in (Chen et al. 2018). For our proposed algorithm AED, we set IN = 100, ER = 50, M I = 5, α = 1, β = −1 for all experimental settings since they yielded the best results. Additionally, the ALS framework is used for non-monotonic algorithms having no anytime update mechanism.
We compare these algorithms on three different experimental settings. We consider random DCOPs for our first setting. Specifically, we set the number of agents to 70 and Our second setting is identical to the first setting except the value of p = 0.6 (i.e. dense graph). For our final setting, we consider weighted graph coloring problems with the number of agents 120, 3 colors per agent, Erdős-Rényi topology with p = 0.05 and constraint violation cost selected uniformly from [1,100]. In all three settings, we run all algorithms on 50 independently generated problems and 30 times on each problem. Moreover, we stop each of the algorithms after 1000-th iteration. It is worth noting that all differences shown in Figures 3, 4, and 5 at the 1000-th iteration are statistically significant for p − value < 0.01. Figure 3 shows a comparison between AED and the benchmarking algorithms on the sparse random DCOP setting. The closest competitor to AED is ACO DCOP which provides slightly better anytime solution till 230 iterations. Although both of the algorithms keep on improving the solution, the improvement rate of AED stays steadier than ACO DCOP. This trend helps AED to produce a 1.8% better solution by 1000th iteration. On the other hand, most of the local search algorithms converge to local optima after 400 iterations -with GDBA producing the best performance. AED starts outperforming GDBA after 90 iterations and finds a 9.3% improved solution. Finally, the other two representative algorithms, Max-Sum ADVP and PD-Gibbs are outperformed by 11.3% − 15%. The superiority of AED in this experiment indicates that the Selection method along with the new Reproduction mechanism based on optimistic local benefit achieves a better balance between exploration and exploitation than other state-of-the-art algorithms. It is worth noting that we have further experimented with different values of the parameters α and β. With the change of α and β, the steepness of the curve and solution quality changes, which indicates that dynamics between exploration and exploitation can be tuned using α and β. Figure 4 shows a comparison between AED and other competing algorithms on dense random DCOP setting. It clearly shows the advantage of AED over its competitors. To be exact, it outperforms the benchmarking algorithms by a margin of 1.5% − 3.2%. In this setting, most of the algorithms find results of similar quality with a slight variation. Among the competitors, GDBA outperforms ACO DCOP by a slight margin, and is the closest to AED with AED improving solution quality by 1.5%. PD-Gibbs fails to explore much through sampling and converge quickly while producing the largest performance difference with AED. It is also worth noting that AED produces a better solution than ACO DCOP from the beginning in this setting. Figure 5 shows a comparison between AED and other competing algorithms on weighted graph coloring problems. In this experiment, AED demonstrates its excellent performance by outperforming other algorithms by a significant margin. Among the competing algorithms, ACO DCOP comes the closest but is still outperformed by AED over 30% margin. Even though for the first 250 iterations ACO DCOP produces better anytime cost, AED starts outperforming ACO DCOP afterwards. This because the initial heuristic value of ACO DCOP is able to construct good solution from the start. On the other hand, AED starts from an initial random solution and has to improve gradually. Among the local search algorithms, GDBA is the most competitive, but AED still finds solutions that are 53% better. Finally, it improves the quality of solution around 2.18 − 2.65 times over some of its competitors namely DSA, Max-Sum ADVP and PD-Gibbs. Through this experiment, it is also evident that AED is an effective algorithm for DCSPs.

Conclusions
In this paper, we introduce a new algorithm called AED that effectively adapts evolutionary optimization to solve DCOPs. For Reproduction in AED, we devise a new mechanism that not only captures local benefits but also the potential benefits resulting from neighbour's cooperation. We also develop a new anytime update mechanism to incorporate anytime property in AED. In our theoretical evaluation, we prove that AED is anytime. Finally, we present empirical results that show that AED produces about 1.5% − 15% improved solutions on random DCOPs and 0.3 − 2.65 times better solutions on weighted graph coloring problems, compared to the state-of-the-art non-exact DCOP algorithms. These results demonstrates the significance of applying evolutionary optimization techniques in solving DCOPs. In the future, we intend to investigate whether this algorithm can be applied to solve continuous-valued and multi-objective DCOPs. We would also like to explore ways to adapt evolutionary optimization to solve asymmetric DCOPs.