Combinatorial optimization problems cover a wide range of real-world problems. A large number of these problems, called NP-hard problems, are computationally hard to deal with. Although these problems have been proposed for decades, they are still attractive to alGorithm designers. Traditional approaches for solving an NP-hard combinatorial optimization problem are classified into exact algorithms, approximate algorithms, and meta-heuristic algorithms. Despite the capabilities of these approaches, each of them has its weaknesses. Due to the weaknesses of the traditional methods and the end of research in artificial intelligence, machine learning approaches have become popular. Machine learning approaches can be divided into three cateGories: supervised, unsupervised, and reinforcement learning. In recent years, to solve combinatorial optimization problems, supervised learning algorithms and reinforcement learning have attracted the attention of researchers. Due to their focus on data distribution, Supervised learning algorithms are ineffective for interactive problems. On the other hand, reinforcement learning algorithms do not have the weakness of supervised algorithms. During the last few years, reinforcement learning algorithms have achieved promising results in solving combinatorial optimization problems. CombOpt Zero is one such approach. Abe and his colleagues have proposed this approach for solving several NP-hard combinatorial optimization problems on graphs in 2019. This approach is a combination of reinforcement learning and graph embedding. The authors inspired this approach from the AlphaGo Zero approach, a superhumanly successful framework for the game Go. The authors have used this approach to solve the minimum vertex cover problem, the maximum cut problem, the maximum clique problem and the maximum independent set problem. Simulations show that the CombOpt Zero approach is promising for the investigated problems. In this thesis, the CombOpt Zero approach is investigated. Moreover, this approach has been used to solve new combinatorial optimization problems, which are: the d-distance independent set problem, weighted maximum Boolean satisfiability problem and minimum dominating set problem. To eva‎luate the results, the solutions of the CombOpt Zero approach are compared with the exact solution obtained from integer linear programming. The results obtained using this approach are very close to the optimal solution. Also, we compare the solution of the CombOpt Zero approach for the weighted maximum boolean satisfiability problem with the solution of two local search approaches known as IRoTS and Novelty++ and the MDS problem with a greedy approach. We will see that the CombOpt Zero approach returns solutions close to the optimal solution for all three problems. Also, the results show that the CombOpt Zero approach provides acceptable solutions for the weighted maximum Boolean satisfiability problem compared to the IRoTS and Novelty++ local search approaches. In addition, this approach provides excellent and near-optimal results in much less time for challenging examples of weighted maximum Boolean satisfiability problems whose ILP solution is time-consuming. Also, for the MDS problem, the error percentage of the greedy approach is about 30% higher than the CombOpt Zero approach.

حسين فلسفين

مهران صفاياني

زينب مالكي، سمانه حسيني