Chemical Reaction Optimization Algorithm to Find Maximum Independent Set in a Graph
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2019, Vol 10, Issue 9
Abstract
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.
Authors and Affiliations
Mohammad A. Asmaran, Ahmad A. Sharieh, Basel A. Mahafzah
Keywords
Related Articles
- EP ID EP645807
- DOI 10.14569/IJACSA.2019.0100912
- Views 118
- Downloads 0
Nonlinear Identification and Control of Coupled Mass-Spring-Damper System using Polynomial Structures
The paper aims to identify and control the coupled mass-spring-damper system. A nonlinear discrete polynomial structure is elaborated. Its parameters are estimated using Recursive Least Squares (RLS) algorithm. Moreover,...
Clustering based Max-Min Scheduling in Cloud Environment
Cloud Computing ensures Service Level Agreement (SLA) by provisioning of resources to cloudlets. This provisioning can be achieved through scheduling algorithms that properly maps given tasks considering different heuris...
Comparative Analysis of Online Rating Systems
Online rating systems serve as decision support tool for choosing the right transactions on the internet. Consumers usually rely on others’ experiences when do transaction on the internet, therefore their feedbacks are h...
Smart Sustainable Agriculture (SSA) Solution Underpinned by Internet of Things (IoT) and Artificial Intelligence (AI)
The Internet of Things (IoT) and Artificial Intelligence (AI) have been employed in agriculture over a long period of time, alongside other advanced computing technologies. However, increased attention is currently being...
A General Evaluation Framework for Text Based Conversational Agent
This paper details the development of a new evaluation framework for a text based Conversational Agent (CA). A CA is an intelligent system that handle spoken or/and text based conversations between machine and human. Gen...