Chemical Reaction Optimization Algorithm to Find Maximum Independent Set in a Graph

Finding maximum independent set (MIS) in a graph is considered one of the fundamental problems in the computer science field, where it can be used to provide solutions for various real life applications. For example, it can be used to provide solutions in scheduling and prioritization problems. Unfortunately, this problem is one of the NP-problems of computer science, which limit its usage in providing solution for such problems with large sizes. This leads the scientists to find a way to provide solutions of such problems using fast algorithms to provide some near optimal solutions. One of the techniques used to provide solutions is to use metaheuristic algorithms. In this paper, a metaheuristic algorithm based on Chemical Reaction Optimization (CRO) is applied with various techniques to find MIS for application represented by a graph. The suggested CRO algorithm achieves accuracy percentages that reach 100% in some cases. This variation depends on the overall structure of the graph along with the picked parameters and colliding molecule selection criteria during the reaction operations of the CRO algorithm.

@article{Asmaran2019,
  title     = {Chemical Reaction Optimization Algorithm to Find Maximum Independent Set in a Graph},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {10},
  number    = {9},
  year      = {2019},
  publisher = {The Science and Information Organization},
  author    = {Mohammad A Asmaran and Ahmad A. Sharieh and Basel A. Mahafzah},
  doi       = {10.14569/IJACSA.2019.0100912},
  url       = {https://doi.org/10.14569/IJACSA.2019.0100912}
}