Affiliations: [a] Department of Computer Engineering, University of Bonab, Bonab, Iran | [b] Department of Mathematics, Faculty of Basic Science, University of Bonab, Bonab, Iran
Correspondence:
[*]
Corresponding author: Mir Mohammad Alipour, Department of Computer Engineering, University of Bonab, Bonab, Iran. E-mail: alipour@ubonab.ac.ir.
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)
