A multiagent reinforcement learning algorithm to solve the maximum independent set problem

Abstract

The Maximum Independent Set Problem (MISP) consists of finding the largest subset of vertices of a graph such that none of the vertices are adjacent. It is well known that the MISP is an NP-Complete problem and usually cannot be solved exactly within a reasonable amount of time. In recent years, various heuristic search techniques, such as tabu search, genetic algorithm, simulated annealing, ant colony optimization and neural network algorithms have been used to solve this problem. In this paper, we propose a new algorithm for the MISP using Multiagent Reinforcement Learning (MARL) approach. In the proposed approach, each agent tries to solve MISP autonomously and improves its local behavior using reinforcement learning (RL) and directly communicates with other agents by sharing successful results. Also, the Exchange 2-1 local search is used to further improvement of the solutions at each step. The experiments were carried out on DIMACS clique instances and p-random graphs. Our experimental results show that the proposed approach is able to compete or even outperform some state-of-the-art algorithms.

Keywords

Maximum independent set problem multiagent systems (MAS)reinforcement learning Q-learning;exchange 2-1 local search maximum clique problem (MCP)

1. Introduction

Given a undirected graph $G=(V,E)$ , an independent set of $G$ is a subset of vertices $S$ such that no two vertices in $S$ are adjacent in $G$ . An independent set of $G$ is maximal if it is not a subset of any larger independent set. A Maximum independent Set of $G$ is a largest maximal independent set contained in $V$ .

The MISP has a close relation to the MCP as it is complementary to the MCP and a maximum independent set of a graph G is the maximum clique of the complement graph of G [1]. The MISP and the MCP have been proved to be NP-Complete problem [2]. These types of problems usually cannot be solved exactly within a reasonable amount of time. Consequently, heuristic approaches must be used to solve them. In recent years, some heuristics, such as tabu search, genetic algorithm, simulated annealing, ant colony optimization and neural network algorithms have been used to solve these NP-hard problems [3, 4, 5].

Applications of the MISP appear in widely divergent fields including information retrieval, coding theory, signal transmission analysis, geometry, classification theory, economics, transport management, scheduling and computer vision [6, 7, 8, 9, 10].

The MAS consists of a group of autonomous intelligent agents which communicate with each other to reach a specific goal. The characteristics of an agent technology application are: being modular, decentralized, robustness, changeable, flexible and complex [11]. The MISP fits these properties well, hence agent technology is a practicable approach and is particularly useful since we can define several agents with independent local memory and different values of learning parameters which improve their local behavior using reinforcement learning, then share successful results between each other to improve the quality of the solution.

In this paper, we propose a new approach to solve MISP using Multiagent Reinforcement Learning. Where in, several independent agents placed at the graph of MISP and each agent tries to solve MISP and then its solution is improved by Exchange 2-1 local search by repeatedly changing the given solution with a better neighborhood solution. In the proposed approach, agents communicate directly with each other and results of successful agent are shared to other agents. Our experimental results indicate that proposed approach has a good performance and enable to compete with some state-of-the-art methods, in terms of solution size and computing times.

The rest of this paper is structured as follows. We mainly review some related work in Section 2. A formulation of the MISP and details of the proposed approach are explained in Section 3 and in Section 4, we evaluate the performance of our approach. Finally, Section 5 summarizes and concludes the paper.

2. Literature review

Andrade et al. proposed a successful iterated local search method to solve the MISP [12]. Their method, often finds optimal solutions in milliseconds for small scale benchmarks that require hours to solve with accurate algorithms. But, their method is outperformed by other algorithms for large scale benchmarks such as social networks [13].

Xu et al. developed an improved simulated annealing (ISA) algorithm for the MCP using a new acceptance function, can find an optimal solution to a given graph with higher probability [14]. They claimed, the ISA has higher convergence rate, than the original simulated annealing and could outperform Jagota’s [4] and Funabiki’s [15] methods.

Thomas et al. gave an evolutionary heuristic for this problem [16]. Aggarawal et al. proposed a genetic algorithm and compared with some state-of-the-art algorithms for the MISP [17]. Mehrabi et al. proposed a hybrid evolutionary algorithm for MISP by creating a new crossover which produces high quality solutions [18].

Barba used randomized parallel genetic for the MISP [19]. Busygin et al. proposed a heuristic approach based on optimization of a quadratic over a sphere [20]. Takefuji et al. developed a Hopfield-type neural network for solving the MISP [21]. Friden et al. developed a tabu search approach and tested to random graphs [22]. Leguizamón et al. proposed an ant colony system [23].

Bansal proposed an approximation for the MISP [24]. Ghaffari developed an improved distributed algorithm [25] and Heydari et al. proposed a method for distributed maximal independent set on scale-free networks [26]. Censor-Hillel and Rabie proposed a distributed reconfiguration of MISP [27]. Gainanov et al. developed a heuristic algorithm for solving the MISP with absolute estimate of the accuracy [28].

With regards to the MCP, Wu and Hao investigated several heuristic methods based on local search, Tabu search and evolutionary techniques [29]. Specifically, they compared the performance of 21 state-of-the-art methods for the MCP in terms of solution quality and runtime, which Tabu search algorithms outperform other methods in terms of solution quality. Grosso et al. proposed a highly successful method for the MCP which, uses different restart rules and diversification operations in plateau search [30].

Belachew and Gillis introduced a new continuous formulation of the MCP using symmetric rank-one non-negative matrix approximation [31]. Also, they proposed a new clique finding method, using a standard projected gradient method. They experimented proposed algorithm on 36 instances from the DIMACS data sets and compared with two other MCP methods. According to the experimental results, their algorithm could outperform the two algorithms.

Maslov et al. presented two branch and bound algorithms for the maximum MCP (ILS&MAXSA) applying a powerful heuristic for obtaining an initial solution of high quality, then this solution is used to prune branches in the main branch and bound algorithm [32]. The ILS&MAXSAT demonstrates the best performance on DIMACS instances among the MCS algorithm by Tomita et al. [33] and MAXSAT algorithm by Li and Quan [34].

Wu and Hao proposed Adaptive Multistart Tabu Search (AMTS) algorithm represents a new approach for approximating the MCP which combines a Tabu Search with a guided restart strategy [35]. As they reported on the experimental results, AMTS shows an excellent performance on the complete set of 80 standard DIMACS benchmark instances. Its competitiveness is confirmed when AMTS were compared with five state-of-the-art MCP methods.

Tomita et al. proposed a depth-first method using the engineering techniques for finding all maximal cliques, which generates a tree-like output [36]. Then, they designed a branch-and-bound technique based on a new approximate coloring method to speed up the algorithm [33]. Also, they proposed several improvements for the branch-and-bound algorithm in [37]. Smith and Perkins presented a hybrid algorithm for the MCP, where a heuristic method is used to construct the initial cliques, then tabu search and several optimizations techniques are invoked to improve the initial cliques [38].

There are also others approaches such as, learning heuristics [39] and MAS can be used for solving NP-Complete problems [40, 41, 42, 43]. In MAS approach, the problem search space is represented as an environment in which agents interact and work together to achieve a predefined objective and their activities are coordinated by heuristic methods inspired by collective intelligence [44].

3. Multiagent reinforcement learning algorithm for the MISP

The formulation of the MISP for combinatorial optimization problems is as follows [45].

Let $G=(V,E)$ be the undirected graph with vertex set $V=\{1,2,\ldots,n\}$ and $E\subseteq V\times V$ is the set of edges. An edge between vertices $i$ and $j$ is represented by $(i,\ j)\in E$ and the binary variables $d_{ij}$ form the adjacency matrix of the $G$ :

$\displaystyle d_{ij}=\left\{\begin{array}[]{cl}1&\text{if}\ (i,\ j)\in E\\ 0&\text{otherwise}\end{array}\right.$ (1)

where $i,j=1,2,\dots,n$ .

A $S\subseteq V$ is an independent set, if $\forall i,j\in S,(i,j)\notin E$ , ( $d_{i,j}=$ 0), and $|S|$ is the cardinality of the $S$ . The MISP is then the problem of finding an independent set with maximum cardinality, in other words, an independent set $S$ that maximizes $|S|$ . The cardinality of a maximum independent set in a graph is called the stability number of it. A small instance of the MISP is shown in Fig. 1.

Let $\overline{G}=(V,\overline{E})$ be the complement of a graph $G$ , where $\overline{E}$ is the complement of $E$ . A $C\subseteq V$ is a clique, if $\forall i,j\in C,(i,j)\in E$ , ( $d_{i,j}=$ 1). We can say, $S$ is an independent set of the $G$ if and only if $S$ is a clique of the $\overline{G}$ . A clique $C A$ in $G$ is maximal if there does not exist any vertex $v$ such that $C\cup\{v\}$ is a clique. A maximum clique is a clique which has the largest number of vertices.

Figure 1.

A graph and its Maximum Independent Set is illustrated in blue [19].

The proposed MARL method for the MISP (MARL-MISP), starts by creating a graph of MISP instance and placing m agents at that graph. In other word, m agents are placed randomly at m nodes of the MISP graph. The proposed model consists of three parts:

•

The learning environment: includes m independent agents placed at MISP graph. These agents differ in learning parameters, such as learning rate, degree ratio and so on (see experimental results section);

•

The learning algorithm: comprised policy and Q-Learning;

•

A reward function: to assessment the effectiveness of the agents’ learning.

The policy is implemented using a lookup table such that, maintains an updated evaluation of all the possible actions for each node. Since MISP graph has $n$ nodes (states), so there are $n$ possible states and because each state has possible $n-1$ neighbors, there are $n-1$ actions for each agent at each state, thus the size of the policy is $n*(n-1)$ state-action values. The proposed approach iteratively approximates the state-action value depending on the Q-learning and then use these values to take next actions. After each agent solved its own MISP and created its own mis_set (approximate solution of the MISP at current round), the solution is optimized by Exchange 2-1 local search and then, the environment uses the cardinality of each agent’s mis_set to produce its response.

Now we can precisely describe the details of each round for each agent. Initially, an agent randomly placed at one of the graph’s nodes as a first member of the mis_set. Then, the agent chooses one of its $n-1$ valid actions list based on $\epsilon$ -greedy method with the probability of EM% and Softmax method with the probability of SM%. Valid actions list include remaining actions that are not yet been selected by an agent at each round, in other words, if an action is selected by an agent at one state, then it will be removed from valid actions list of all other states. However, at the next round of the algorithm, all actions will be returned to the valid actions list.

In $\epsilon$ -greedy method, most of the time a greedy action is selected from valid actions list which has the greater value of $P(a|s_{c})$ as defined in Eq. (2) and using a small probability, a random action, $a$ is chosen in state $s_{c}$ from valid actions list. This ensures that after many learning episodes, all of the possible actions will be tried in most cases, which leads to an optimal policy.

$\displaystyle P(a|s_{c})=\frac{Q(s_{c},a)*(D^{-1}(s_{a}))^{\beta}}{\sum_{\hat{% a}\neq a}Q(s_{c},\hat{a})*(D^{-1}(s_{\hat{a}}))^{\beta}}$ (2)

where $a$ is one of the agent’s valid actions list, $\hat{a}\neq a$ denotes to other actions of the valid actions list of the agent, $s_{c}$ is the current state which agent placed at it, $s_{a}$ is the state correspond to action $a$ , $Q(s_{c},a)$ is the Q-value of action $a$ at state $s_{c}$ . $P(a|s_{c})$ is the probability which the agent at state $s_{c}$ selects action $a$ , $D^{-1}(s_{a})$ is the inverse of the degree of state $s_{a}$ and $\beta>1$ is a parameter called degree ratio, which determines the relative importance of $Q(s_{c},a)$ versus degree. In Eq. (2) we multiply the $Q(s_{c},a)$ by the corresponding value $D^{-1}(s_{a})$ , in this way we favor the choice of nodes which have smaller degrees and greater $P(a|s_{c})s$ . Note that, whenever the degree of a node is zero, we consider a very small value for its degree (D).

Algorithm 1: The MARL method for the MISP (MARL-MISP)
repeat // for MNLR rounds
for all $m$ agents do
for $s\in S$ ; $a\in A$ do $Q(s,a)=$ 1;
end for // Q-values of m agents are initialized.
for all m agents do // m agents creates their own mis_sets.
$s_{c}=$ A random state of the MISP graph;
$\textit{mis\_set}=\{s_{c}\}$
Remove action correspond to $s_{c}$ from valid actions list of all states;
while there is a valid action do
$P(a\|s_{c})=\frac{Q(s_{c},a)(D^{-1}(s_{a}))^{\beta}}{\sum_{\hat{a}\neq a}Q(s_{% c},\hat{a})(D^{-1}(s_{\hat{a}}))^{\beta}}$
Select action $a$ based on $\left\{\begin{array}[]{cl}\text{EG\%}&\epsilon-\text{greedy method}\\ \text{SM{\%}}&\text{Softmax\ method}\end{array}\right.$ // where EG $+$ SM $=$ 1;
$a_{s}=$ state correspond to action $a$ ;
Remove action correspond to $a_{s}$ of all states;
if $\forall i\in\textit{mis\_set}\Longrightarrow d_{i,a_{s}}=0$ Then
$\textit{mis\_set}=\textit{mis\_set}\cup\{a_{s}\}$
end if
$s_{c}=a_{s}$ // place agent at state $s_{c}$ ;
end while
mis_set $=$ Exhg-LS(mis_set);
// Local $Q\left(S,a_{s}\right)$ updating of current agent:
if cardinality(mis_set) $<$ cardinality(local_best_mis_set) Then
$Q(S,a_{s})\leftarrow Q(S,a_{s})+\alpha*rd$ ;
local_best_mis_set $=$ mis_set
end if
end for
// m agents creates their own mis_sets.
mis_set $=$ best mis_set of the current round;
// Global $Q(S,a_{s})$ updating of all agents for current round:
if cardinality(mis_set) $>$ cardinality(global_ best_mis_set) Then
$Q(S,a_{s})\leftarrow Q(S,a_{s})+\alpha*rd$ ;
global_ best_mis_set $=$ mis_set;
end if
Return all actions of the all states to the valid actions list
until Learning is stopped.
Output: global_ best_mis_set

Algorithm 2: Exchange 2-1 Local Search (Exhg-LS)
Exhg-LS (MS)
$V^{\prime}=V-\textit{MS}$ ; // $V$ is the vertex set
For all $x\in\textit{MS}$ Do
$\textit{Adj(x)}=\emptyset$
For all $y\in\ V^{\prime}$ Do // from vertex with lower id to higher id
If $d_{x,y}=1$ Then
$\textit{Adj}(x)=\textit{Adj}(x)\cup\{y\}$ ;
End if
End for
If $\exists y,z\in\textit{Adj}(x)\ s.t.d_{y,z}=0$ Then
$\textit{MS}=\textit{MS}\cup\{y,z\}$ ;
$V^{\prime}=V^{\prime}\cup\{x\}$ ;
$V^{\prime}=V^{\prime}-\{y,z\}$ ;
End if
End for
Output: MS
end

In Softmax method, a weight is assigned to each actions of the valid actions list based on $P(a|s_{c})$ values. Then, a random action is selected depending on the weight associated with it, ensuring that worst actions are unlikely to be selected. When using Softmax, an agent selects a random action $a$ while in state $s_{c}$ with a probability of $P(a|s_{c})$ .

Then agent placed at the selected state and if the selected node (action) is not adjacent to none of the nodes in mis_set, then inserted to it. The process of selecting an action from the valid actions list and placing the agent at that state is repeated until a round terminated, this means, all possible nodes of the graph are selected and a mis_set is created. The task of an agent is a sequence of actions (selecting nodes of the MISP graph) that creates a mis_set. A round is finished, once all of the m agents have created their own mis_sets. Then the environment uses the cardinality of each agent’s mis_set to produce its response. If cardinality of the produced mis_set by each agent is greater than the cardinality of its best mis_set (the mis_set that has been created so far by that agent, called local best mis_set), then all actions of that agent along current mis_set is rewarded based on the Q-learning algorithm as defined in Eq. (3), called local $Q(s_{c},a)$ updating. The objective of the reward function is to encourage the actions which increase the mis_set’s cardinality.

$\displaystyle Q(S,a_{s})\leftarrow Q(S,a_{s})+\alpha*r$ (3)

where $Q(S,a_{s})$ is the new Q-value of state $S$ corresponding to action $a_{s}$ , $r$ is the reward obtained from selecting the action $a_{s}$ while in state $S$ and the parameter $0\ll\alpha\leqslant 1$ is referred to as learning rate, which determines how fast learning occurs.

Also, if in any round of the algorithm, one of the agents creates a mis_set which its cardinality is greater than the best mis_set created so far by all of the agents (called global best mis_set), then corresponding actions on all agents is rewarded based on Eq. (3), called global $Q(s_{c},a)$ updating. In other words, agents communicate directly with each other and results of successful agent are shared to other agents.

This process is repeated for a predetermined number of rounds (Maximum number of learning rounds, MNLR times) and after that, the best solution (mis_set) from all of the rounds is presented as output of the proposed approach (MARL-MISP). Algorithm 1 implements the MARL-MISP.

The proposed Exchange 2-1 Local Search (Exhg-LS) is a faster implementation of 2-improvements local search developed by Feo et al. [46]. The Exhg-LS (Algorithm 2) repeatedly changes the given solution with a better neighborhood solution and stops when given solution cannot be further improved. Whereas the produced solutions by MARL-MISP are not guaranteed to be globally optimal, so this local search is useful. This local search exchanges vertex $x$ of the given solution MS ( $x\in\textit{MS}$ ), with two new vertices $y$ and $z$ ( $y,z\notin\textit{MS}$ ), so increasing the cardinality of the MS by one. For each $x\in\textit{MS}$ , it tries to find two not adjacent vertices $y$ and z which $y,z\notin\textit{MS}$ and both vertices are adjacent to $x$ ( $d_{x,y}=1,\ d_{x,z}=1$ ), when such two vertices were found, then $x$ is removed from MS and $y$ and $z$ are inserted into the MS ( $y$ and $z$ are replaced with $x$ ). It is easy to prove that the Exhg-LS works in $O(n^{2})$ time.

The working diagram of the MARL-MISP for any agent $x$ is shown in Fig. 2.

Figure 2.

Working diagram of the MARL-MISP.

4. Experimental results

Experimental results of the MARL-MISP are presented in this section and are compared with those of other well-known methods. We used Microsoft Visual studio.net 2017 under 64-bit Windows 8.1 operating system, running on a laptop with Intel Core-i5-4200U, 1.6 GHz CPU and 4 GB of RAM to perform all tests. In order to assess the effectiveness of the proposed algorithm, extensive simulations were carried out on two type graphs: some benchmark graphs and $p$ -random graphs. To test the performance of the MARL-MISP, we used two types of graphs: benchmark graphs and $p$ -random graphs. The first type of benchmark graphs are the complement graphs of the DIMACS clique instances [47]. Each instance of the DIMACS benchmark has a special structure with respect to some specific real problem. The second type of graphs we used to evaluate our approach are complement graph of $p$ -random graphs. A $p$ -random graph of size $n$ is a graph $(V,E)$ , where $V=\{1,\ 2,\ \ldots,\ n\}$ and $E$ is produced by selecting $\{i,\ j\}$ as an edge with probability $p$ , ( $0<p<$ 1). For these graph, we can estimate the maximum clique size [16, 17, 18, 19, 20, 21, 22, 23]. For fixed value of $p$ and sufficiently large $n$ , the expected number of cliques of size $k$ in a $p$ -random graph of size $n$ is calculated using Eq. (4).

$\displaystyle\left(\begin{array}[]{c}n\\ k\end{array}\right)p^{\frac{k(k-1)}{2}}$ (4)

Let $C(n,\ p)=k$ ( $k$ is a real number), such that $\binom{n}{k}p^{\frac{k(k-1)}{2}}=1$ , so $C(n,p)$ estimates the maximum clique size. Since the MARL-MISP has a stochastic component, thus may produce different results over multiple runs on the same graph. Therefore, each experiment was performed 20 independent runs, and the best and average were recorded for each run. Table 1 summarized the parameters settings of the MARL-MISP. In the proposed algorithm, we set the values of parameters depending on some preliminary trials and are those values that gave the best results concerning both the solution quality and the computational time required to reach these results.

Table 1

Parameter settings for the MARL-MISP

Parameter	Value	Meaning
$\beta$	[1.5,2.5]	Degree ratio
EG	[0.8,0.9]	$\epsilon$ -greedy action selection method probability
SM	1-EG	Softmax action selection method probability
$r$	[0.8,1.2]	Reward
$\alpha$	[0.6,0.8]	Learning rate
MNLR	5000	Maximum Number of Learning Rounds
$m$	3	Number of agents

When developing a MARL, its performance crucially depends on the selection of appropriate learning parameters. Generally speaking, it is important that all the learning parameters are carefully tuned to get good performance in reinforcement learning [48]. Figure 3 illustrates the results of running MARL-MISP on instance p_hat1500_1 with different values of learning parameters.

Figure 3a shows the results obtained by MARL-MISP with different values of learning rates ( $\alpha\in[0,1]$ ). A too small value of $\alpha$ means the learning process will proceed at a low speed, while a high value of $\alpha$ might affect the convergence rate of the MARL-MISP. Depending on the results, MARL-MISP performs better for a particular range of the $\alpha$ and the performance increases as $\alpha$ is increased to 0.75 and as $\alpha$ is increased to more than 0.75, the performance decreased gradually. Therefore, we set the value of the $\alpha$ at the range of 0.6 to 0.8. According to Fig. 3b, when reward ( $r$ ) is around 1, the MARL-MISP is showing good results. Therefore, we experimented the value of reward at the range of 0.8 to 1.2. Beta ( $\beta$ ) is a parameter which determines the relative importance of the degree of a node versus the Q-values. When $\beta=$ 0, only Q-value affects on $P(a|s_{c})$ , and when increasing the value of $\beta$ , we favor the choice of the nodes which have less degrees. According to Fig. 3c, when $\beta$ is around 2, the MARL-MISP shows better results, so we set the parameter $\beta$ at the range of 1.5 to 2.5. In the proposed approach, each agent takes one of its actions based on the $\epsilon$ -greedy with probability of EG% and the Softmax with probability of SM% (equal to 1- EG). As shown in Fig. 3d, when the EG is around 0.8 to 0.9, the MARL-MISP is showing good results. Therefore, we set the parameter EG at the range of 0.8 to 0.9.

Figure 3.

Results of running MARL-MISP on dataset p_hat1500_1 with different values of learning rate ( $\alpha$ ), reward ( $r$ ), Beta ( $\beta$ ) and $\epsilon$ -greedy action selection probability (EG).

Let us see Fig. 4, which contains the convergence graph of the MARL-MISP on the instance p_hat1500_1 with different values of the MNLR. In this graph, average running times in seconds are shown above the data label. As we can see, after 5000-th round of the MARL-MISP, there are not notable improvements in the results proportional to the relatively high increase in the running time of the MARL-MISP. For this reason, we experimented in MNLR 5000 in the proposed approach.

The performance of the MARL-MISP on the DIMACS benchmark is illustrated in Table 2. Columns ‘instance’, ‘n’, ‘ed.’, ‘b.k.s.’, ‘best’, ‘avg.’, ‘std.’ and ‘time(s)’ respectively represent the name of the graph, the number of nodes, the number of edges, best known solution, size of the best solution found by MARL-MISP, the average solution size, the standard deviation and the average time in seconds. Recall that our algorithm solve MISP, so it works with the complement graphs of the DIMACS benchmark and the p-random graphs.

Table 2

The performance of the MARL-MISP on the DIMACS benchmark

Instance	$n$	ed.	b.k.s.	Best	Avg.	Std.	Time (s)
brock200_1	200	14834	21	21	19.81	0.15	0.04
brock400_1	400	59723	27	26	24.14	0.27	8.48
brock800_1	800	207505	23	23	21.26	0.17	46.51
c-fat200-1	200	1534	12	12	12.00	0.00	0.01
c-fat500-1	500	4459	14	14	14.00	0.00	0.01
hamming10-2	1024	518656	512	512	512.00	0.00	2.32
hamming8-2	256	31616	128	128	128.00	0.00	1.11
johnson16-2-4	120	5460	8	8	8.00	0.00	0.01
johnson32-2-4	496	107880	16	16	16.00	0.00	0.01
keller4	171	9435	11	11	11.00	0.00	0.23
keller5	776	225990	27	27	24.63	0.17	1.45
MANN_a27	378	70551	126	125	125.32	0.18	1.25
MANN_a45	1035	533115	345	344	340.84	0.42	2.36
p_hat300_1	300	10933	8	8	7.84	0.08	0.49
p_hat300_2	300	21928	25	25	25	0.00	0.62
p_hat300_3	300	33390	36	34	32.94	0.23	0.66
p_hat500_1	500	31569	9	9	8.80	0.31	1.62
p_hat500_2	500	62946	36	36	33.14	0.47	2.49
p_hat700_1	700	60999	11	11	9.21	0.45	1.81
p_hat1000_1	1000	122253	10	10	9.07	0.16	2.85
p_hat1500_1	1500	284923	12	11	10.71	0.29	3.64
san200_0.7_1	200	13930	30	30	23.24	0.85	0.17
san200_0.9_1	200	17910	70	70	59.32	0.87	1.15
san200_0.9_2	200	17910	60	60	52.33	1.79	1.24
san200_0.9_3	200	17910	44	42	40.60	0.96	1.87
san400_0.5_1	400	39900	13	13	13.00	0.00	8.95
san400_0.9_1	400	71820	100	100	87.29	3.18	1.17
sanr200_0.7	200	13868	18	18	18.00	0.00	0.08
sanr400_0.5	400	39984	13	13	11.48	0.34	0.09
san1000	1000	250500	15	15	13.57	0.20	50.85

Figure 4.

Convergence of the MARL-MISP on dataset p_hat1500_1 with different values the MNLR.

Table 2 shows that MARL-MISP can find maximal independent set of the best known solution for 24 out of the 30 instances of the DIMACS. The instances for which MARL-MISP fails to find the best known solution are brock400_1, MANN_a27, MANN_a45, p_hat300_3, p_hat1500_1 and san200_0.9_3. For these instance, its convergence rate is near 100%. In 24 instances for which MARL-MISP achieves the best known solution, in 10 instances it can find such a result with a success rate of 100%. As a result, one single run may suffice for MARL-MISP to find a maximal independent set of the best known solution and in 16 instances, each run of the MARL-MISP can reach either a best known solution or solutions of sizes very close to the best known solution. If we check the running times in Table 2, we observe that for 12 out of the 30 DIMACS instances (40% cases), the average running time for reaching the best known solution is less than 1 second and running times of less than one minute are needed for all of the 18 remaining instances. In Table 3, we used 12 instances from the p-random graphs, for $n=$ 100, 200, 300, 500 and $p=$ 0.5, 0.8, 0.9. The meanings of the columns in Table 3 are same as those in Table 2. Furthermore, columns ‘p’ and ‘e.s.c.’ respectively represent the value of parameter p and the expected size of the maximum clique.

Table 3

The performance of the MARL-MISP on the p-random graphs

Instance	$n$	ed.	$p$	e.s.c.	Best	Avg.	Std.	Time(s)
G_100_0.5	100	2475	0.5	9.9	9	9.00	0.08	0.12
G_100_0.8	100	3960	0.8	21.66	20	18.53	0.14	0.14
G_100_0.9	100	4455	0.9	34.82	33	31.35	0.27	0.15
G_200_0.5	200	9950	0.5	11.60	11	10.05	0.39	2.34
G_200_0.8	200	15920	0.8	26.63	25	23.41	0.51	2.38
G_200_0.9	200	17910	0.9	44.90	42	40.12	0.19	3.07
G_300_0.5	300	22425	0.5	12.60	12	11.18	0.41	12.45
G_300_0.8	300	35880	0.8	29.57	28	23.97	1.04	11.47
G_300_0.9	300	40365	0.9	50.93	48	43.55	0.23	15.26
G_500_0.5	500	62375	0.5	13.87	12	10.78	0.61	64.47
G_500_0.8	500	99800	0.8	33.32	32	31.16	0.15	66.31
G_500_0.9	500	112275	0.9	58.64	57	55.48	0.22	69.13

From Table 3, we can say that, in all 12 different instances from p-graphs, the proposed algorithm can reach the solutions that their size is very close to their expected size in reasonable computing times. In summary, considering Tables 2 and 3, the MARL-MISP can achieve the acceptable results with high convergence rate in examined instances of small to large scales with different densities.

Now, we compare the MARL-MISP with several state-of-the-art approaches, some of these methods have been proposed for the MCP. As mentioned earlier, it is possible to get instances of MISP for which the size of the maximum independent set is the same as the maximum clique of the complement graph. Consequently, we can compare the results of the MISP approaches with the results of the MCP methods. The comparison is based on the size of the solutions found in terms of the largest maximal independent set or maximum clique size. According to the differences among the computers, programming languages and so on, so we have illustrated the computing times only for indicative purposes. The comparison of the MARL-MISP with SRON of Belachew and Gillis [31], ILS&MAXSAT of Maslov et al. [32], KLS5 of Tomita et al. [37] and HTS of Smith and Perkins [38] on 26 DIMACS benchmark instances is illustrated in Table 4. SRON used a laptop Intel(R) Core(TM) i7-6500U CPU 2.50 GHz and 8 GB RAM, ILS&MAXSAT used Intel Core i7 CPU 2.3 GHz machine with 8 Gb of memory, KLS5 used a PC with Intel Core i7-4790 CPU 3.6 GHz and 8 GB RAM and HTS used an Intel Pentium 4 3.40 GHz or Celeron (R) 2.79 GHz CPU machine with 4 GB of RAM.

Table 4

The comparison of the MARL-MISP with 4 methods on 26 DIMACS benchmark instances

Instance	b.k.s.	MARL-MISP		SRON		ILS&MAXSAT		KLS5		HTS
		Best	Time (s)	Best	Time (s)	Best	Time (s)	Best	Time (s)	Best	Time (s)
brock200_1	21	21	0.04	19	0.05	21	6.47	21	0.09	21	24.20
brock400_1	27	26	8.48	24	0.08	27	250.79	25	0.41	27	730.40
brock800_1	23	23	46.51	18	0.36	23	5059.95	21	1.07	22	115.00
hamming10-2	512	512	2.32	512	0.13	512	5.89	512	3.46	512	63.21
hamming8-2	128	128	1.11			128	1.22	127	1.04	127	49.58
keller4	11	11	0.23			11	6.62	10	1.06	11	18.51
keller5	27	27	1.45			27	5397.85	27	1.65	27	26.49
MANN_a27	126	125	1.25	123	0.10	126	1.80	126	2.60	125	33.67
MANN_a45	345	344	2.36	333	0.91	345	34.10	344	79	345	352.00
p_hat300_1	8	8	0.49			8	27.34			8	12.88
p_hat300_2	25	25	0.62			25	16.54			24	11.46
p_hat300_3	36	34	0.66			36	10.75	36	0.31	35	17.35
p_hat500_1	9	9	1.62			9	75.47			9	67.42
p_hat500_2	36	36	2.49			36	41.23	35	1.92	36	95.71
p_hat700_1	11	11	1.81			11	147.34			11	56.00
p_hat1000_1	10	10	2.85			10	303.89	10	0.02	10	86.52
p_hat1500_1	12	11	3.64			12	703.17	11	0.08	11	112.20
san200_0.7_1	30	30	0.17			30	6.41			30	41.73
san200_0.9_1	70	70	1.15			70	1.81			70	46.95
san200_0.9_2	60	60	1.24			60	2.02	60	0.32	60	51.30
san200_0.9_3	44	42	1.87			44	2.36			43	94.26
san400_0.5_1	13	13	8.95	7	0.04	13	64.65			13	212.54
san400_0.9_1	100	100	1.17	53	0.04	100	6.38	99	3.81	99	78.59
sanr200_0.7	18	18	0.08			18	7.46	18	0.07	18	25.37
sanr400_0.5	13	13	0.09	13	0.10	13	50.02	13	0.07	13	22.46
san1000	15	15	50.85	8	0.23	15	464.69	15	0.23	15	387.53

Table 4 shows that MARL-MISP finds larger solutions than SRON for 8 instances and for 2 instances both methods can find the best known solution. While SRON solves most of the instances faster than MARL-MISP. Only one instances is solved by MARL-MISP faster. However, the quality of the SRON’s solutions are poor. The next compared method is ILS&MAXSAT, which is an exact method, so it find best known solution solutions of all 26 instances. But its running times are very expensive and in average the MARL-MISP running times are almost 88 times faster than the ILS&MAXSAT. Comparing with KLS5, the MARL-MISP obtains better result for six instances, whereas the KLS5 obtains better results for 2 instances and other results are the same for two these methods, but the KLS5 needs less computing time. Also, the HTS obtains better results for 3 instances, whereas the MARL-MISP obtains better result for four instances and other results are the same for these two methods. But in average running times, the MARL-MISP is almost 8 times faster than the HTS.

In Table 5 the MARL-MISP is compare with ISA of Xu et al. [14], KLS5 of Tomita et al. [37] and HTS of Smith and Perkins [38] on 12 instances from the p-random graphs. None of these methods reported any information about their used computer.

Table 5

The comparison of the MARL-MISP with 3 methods on 12 instances from the p-random graphs

Instance	e.s.c.	MARL-MISP		ISA		KLS5		HTS
		Best	Time (s)	Best	Time (s)	Best	Time (s)	Best	Time (s)
G_100_0.5	9.9	9	0.12	9	1.29	9	0.09	9	4.58
G_100_0.8	21.66	20	0.14	19	1.31	19	0.11	20	10.42
G_100_0.9	34.82	33	0.15	32	1.74	33	0.17	34	54.79
G_200_0.5	11.60	11	2.34	11	10.91	11	1.25	11	23.11
G_200_0.8	26.63	25	2.38	23	11.23	24	1.38	25	33.59
G_200_0.9	44.90	42	3.07	41	11.82	42	2.67	43	51.20
G_300_0.5	12.60	12	12.45	11	50.12	12	11.03	11	46.13
G_300_0.8	29.57	28	11.47	27	51.57	28	12.32	28	44.62
G_300_0.9	50.93	48	15.26	47	53.84	49	16.51	48	89.11
G_500_0.5	13.87	12	64.47	12	150.92	12	33.85	12	215.47
G_500_0.8	33.32	32	66.31	31	153.44	32	72.04	32	241.60
G_500_0.9	58.64	57	69.13	57	167.31	56	41.59	56	302.85

Table 5 shows that MARL-MISP obtains better solutions than ISA for 8 instances and for other instances, it finds solutions as good as ISA. Comparing with KLS5, the MARL-MISP outperforms this method on 3 instances and for other 8 instances it finds solutions as good as KLS5, whereas the KLS5 obtains better results for 1 instance. However, average running time of the KLS5 is more than 1.66 times faster than the MARL-MISP. Comparing with HTS, the MARL-MISP outperforms this method on 2 instances and for other 7 instances it finds solutions as good as HTS, whereas the HTS obtains better results for 3 instances. However, average running time of the MARL-MISP is more than 4 times faster than the HTS.

In summary, considering the results presented in Tables 2 to 5, on a wide range of instances from small to large scales with varying densities showed that despite its simplicity, MARL-MISP is capable of competing with, and even outperforming state-of-the-art methods for the MISP and MCP. Specifically, MARL-MISP is able to obtain the best current solution for all instances of DIMACS except for 6 instances, and can reach the high quality solutions for 12 instances from the p-graphs in reasonable computing times. Only rare methods can achieve such performance on both DIMACS and p-graphs without any primary adaptation.

5. Conclusion

In this paper we presented a new multiagent reinforcement learning algorithm to solve the maximal independent set problem, a well-known NP-Complete problem. In the proposed multiagent system, each agent is an autonomous entity with different learning parameters and directly communicates with other agents by sharing successful results. Experimental evaluations on two benchmark sets showed that despite of its simplicity, MARL-MISP finds the current best known solutions for 24 out of 30 instances of the DIMACS and can reach the solutions of the p-random graphs that their size is very close to their expected size in a very reasonable time. The competitiveness of the MARL-MISP is confirmed when it was compared with several state-of-the-art maximal independent set and maximum clique methods and it outperform most of these methods in terms of the solutions’ quality and convergence rate.

Footnotes

Authors’ Bios

Mir Mohammad Alipour received his B.Sc. degree in Computer Engineering in 2001 from University of Isfahan, Isfahan, Iran, and received his M.Sc. degree in Computer Engineering in 2004 from Amirkabir University of Technology, Tehran, Iran, and Ph.D. degree in Artificial Intelligence from University of Tabriz, Tabriz, Iran, in 2019. Currently he is working as an Assistant Professor of Computer Engineering Department in University of Bonab, Bonab, Iran. His main researches focus on machine learning, heuristics, swarm intelligence, combinatorial optimization and specifically multiagent learning and its applications.

Mohsen Abdolhossienzadeh has obtained his PhD in Operational research. He is familiar with some optimization areas especially Combinatorial Optimization, Meta-heuristic Methods, Markov Chain Stochastic Process, Online Optimization. He is a faculty member of the University of Bonab, and also he is a member of the Iranian Operations Research Society. There are numerous researches by Dr. Abdolhossienzadeh with a concentration on some routing problem. He currently studies swarm optimization methods for swarm robotics.

References

Book

R.V.

Karp

R.M.

, Reducibility among combinatorial problems. Complexity of computer computations, Proceedings of a Symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Center, Yorktown Heights, New York, edited by Raymond E. Miller and James W. Thatcher, Plenum Press, New York and London 1972, pp. 85–103, The Journal of Symbolic Logic, vol. 40, pp. 618–619, 1975.

Johnson

D.S.

and Garey

M.R.

, Computers and intractability: A guide to the theory of NP-completeness vol. 1: WH Freeman San Francisco, 1979.

Hifi

, A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems, Journal of the Operational Research Society 48 (1997), 612–622.

Jagota

, Approximating maximum clique with a Hopfield network, IEEE Transactions on Neural Networks 6 (1995), 724–735.

Beasley

J.E.

and Chu

P.C.

, A genetic algorithm for the set covering problem, European Journal of Operational Research 94 (1996), 392–404.

Pardalos

and Resende

, On maximum clique problems in very large graphs, DIMACS Series 50 (1999), 119–130.

Bomze

I.M.

Budinich

Pardalos

P.M.

and Pelillo

, The maximum clique problem, in Handbook of combinatorial optimization, ed: Springer, 1999, pp. 1–74.

Bui

T.N.

and Strite

L.C.

, An ant system algorithm for graph bisection, in Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation, 2002, pp. 43–51.

Corrádi

and Szabó

, A combinatorial approach for Keller’s conjecture, Periodica Mathematica Hungarica 21 (1990), 95–100.

10.

Lagarias

J.C.

and Shor

P.W.

, Keller’s cube-tiling conjecture is false in high dimensions, Bulletin of the American Mathematical Society 27 (1992), 279–283.

11.

Parunak

H.V.D.

, Industrial and practical applications of DAI, Multiagent systems: a modern approach to distributed artificial intelligence, 1999, pp. 337–421.

12.

Andrade

D.V.

Resende

M.G.

and Werneck

R.F.

, Fast local search for the maximum independent set problem, Journal of Heuristics 18 (2012), 525–547.

13.

Lamm

Sanders

Schulz

Strash

and Werneck

R.F.

, Finding near-optimal independent sets at scale, Journal of Heuristics 23 (2017), 207–229.

14.

and Wang

, An improved simulated annealing algorithm for the maximum independent set problem, in International Conference on Intelligent Computing, 2006, pp. 822–831.

15.

Funabiki

and Nishikawa

, Comparisons of energy-descent optimization algorithms for maximum clique problems, IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences 79 (1996), 452–460.

16.

Back

and Khuri

, An evolutionary heuristic for the maximum independent set problem, in Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, 1994, pp. 531–535.

17.

Aggarwal

C.C.

Orlin

J.B.

and Tai

R.P.

, Optimized crossover for the independent set problem, Operations Research 45 (1997), 226–234.

18.

Mehrabi

and Mehrabi

A.D.

, A New Hybrid Genetic Algorithm for Maximum Independent Set Problem, in ICSOFT (2), 2009, pp. 314–317.

19.

Barba

, Parallel algorithms for the maximal independent set problem in graphs, School of Computer Science Carleton university, Ottawa, Canada, 2012.

20.

Busygin

Butenko

and Pardalos

P.M.

, A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere, Journal of Combinatorial Optimization 6 (2002), 287–297.

21.

Takefuji

Chen

L.-L.

Lee

K.-C.

and Huffman

, Parallel algorithms for finding a near-maximum independent set of a circle graph, IEEE Transactions on Neural Networks 1 (1990), 263–267.

22.

Friden

Hertz

and de Werra

, Stabulus: a technique for finding stable sets in large graphs with tabu search, Computing 42 (1989), 35–44.

23.

Leguizamón

Michalewicz

and Schutz

, An ant system for the maximum independent set problem, in VII Congreso Argentino de Ciencias de la Computación, 2001.

24.

Bansal

, Approximating independent sets in sparse graphs, in Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, 2014, pp. 1–8.

25.

Ghaffari

, An improved distributed algorithm for maximal independent set, in Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, 2016, pp. 270–277.

26.

Heydari

Taheri

S.M.

and Kavousi

, Distributed Maximal Independent Set on Scale-Free Networks, arXiv preprint arXiv:1804.02513, 2018.

27.

Censor-Hillel

and Rabie

, Distributed Reconfiguration of Maximal Independent Sets, arXiv preprint arXiv:1810.02106, 2018.

28.

Gainanov

D.N.

Mladenovic

Rasskazova

and Urosevic

, Heuristic Algorithm for Finding the Maximum Independent Set with Absolute Estimate of the Accuracy, in CEUR Workshop Proceedings. (submitted), 2018.

29.

and Hao

J.-K.

, A review on algorithms for maximum clique problems, European Journal of Operational Research 242 (2015), 693–709.

30.

Grosso

Locatelli

and Pullan

, Simple ingredients leading to very efficient heuristics for the maximum clique problem, Journal of Heuristics 14 (2008), 587–612.

31.

Belachew

M.T.

and Gillis

, Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation, Journal of Optimization Theory and Applications 173 (2017), 279–296.

32.

Maslov

Batsyn

and Pardalos

P.M.

, Speeding up branch and bound algorithms for solving the maximum clique problem, Journal of Global Optimization 59 (2014), 1–21.

33.

Tomita

Sutani

Higashi

Takahashi

and Wakatsuki

, A simple and faster branch-and-bound algorithm for finding a maximum clique, in International Workshop on Algorithms and Computation, 2010, pp.191–203.

34.

C.-M.

and Quan

, Combining graph structure exploitation and propositional reasoning for the maximum clique problem, in 2010 22nd IEEE International Conference on Tools with Artificial Intelligence, 2010, pp. 344–351.

35.

and Hao

J.-K.

, An adaptive multistart tabu search approach to solve the maximum clique problem, Journal of Combinatorial Optimization 26 (2013), 86–108.

36.

Tomita

Tanaka

and Takahashi

, The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science 363 (2006), 28–42.

37.

Tomita

Matsuzaki

Nagao

Ito

and Wakatsuki

, A much faster algorithm for finding a maximum clique with computational experiments, Journal of Information Processing 25 (2017), 667–677.

38.

Smith

D.H.

Perkins

and Montemanni

, Solving the maximum clique problem with a hybrid algorithm, International Journal of Metaheuristics 7 (2019), 152–175.

39.

Serban

and Pintea

, Heuristics and learning approaches for solving the Travling Salesman Problem, Studia Universitatis Babes-Bolyai Informatica 49 (2004), 27–36.

40.

Souza

G.R.

Goldbarg

E.F.

Goldbarg

M.C.

and Canuto

A.M.

, A multiagent approach for metaheuristics hybridization applied to the traveling salesman problem, in Neural Networks (SBRN), 2012 Brazilian Symposium on, 2012, pp. 208–213.

41.

Júnior

F.C.D.L.

Neto

A.D.D.

and De Melo

J.D.

, Hybrid metaheuristics using reinforcement learning applied to salesman traveling problem, in Traveling Salesman Problem, Theory and Applications, ed: InTech, 2010.

42.

Alipour

M.M.

and Razavi

S.N.

, A new multiagent reinforcement learning algorithm to solve the symmetric traveling salesman problem, Multiagent and Grid Systems 11 (2015), 107–119.

43.

Alipour

M.M.

Razavi

S.N.

Derakhshi

M.R.F.

and Balafar

M.A.

, A hybrid algorithm using a genetic algorithm and multiagent reinforcement learning heuristic to solve the traveling salesman problem, Neural Computing and Applications (2018), pp. 1–17.

44.

Glover

and Kochenberger

G.A.

, Handbook of metaheuristics, Springer, 2003.

45.

Centre

C.B.R.

, An introduction to the Design and Analysis of Algorithms: Charles Babbage Research Centre, 1985.

46.

Feo

T.A.

Resende

M.G.

and Smith

S.H.

, A greedy randomized adaptive search procedure for maximum independent set, Operations Research 42 (1994), 860–878.

47.

Johnson

D.S.

and Trick

M.A.

, Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11–13, 1993 vol. 26: American Mathematical Soc., 1996.

48.

Tokic

Schwenker

and Palm

, Meta-learning of exploration and exploitation parameters with replacing eligibility traces, presented at the In IAPR International Workshop on Partially Supervised Springer Berlin Heidelberg, 2013 May, pp. 68–79.