<p>Finding a specific-sized set of vertices with the highest pairwise distance from a given graph is known as the Maximum Diversity Problem (MDP). So, the goal of MDP is to determine the largest diverse set of a particular size from a given weighted graph. Multiple metaheuristic approaches were proposed to solve the problem as it is an NP-hard problem. This paper presents a metaheuristic method based on the chemical reaction optimization (CRO) algorithm to solve the problem. CRO is a population-based metaheuristic algorithm to solve optimization problems. Over the past few years, it has effectively solved numerous optimization problems with better results than other metaheuristic algorithms in use. With the help of its four reaction operators, it can explore the solution space locally and globally over the population. Our proposal involves redesigning the four elementary reaction operators of the CRO algorithm and fine-tuning the initial parameters to solve MDP efficiently, as well as building an extra repair operator to increase the quality of the solution in less computational time. A dataset with more than 150 instances is used to observe the performance of our proposed method. The proposed method gives better results with fewer average errors in comparison to methods in the literature. For most of the graphs, the algorithm gives the best-known results mentioned in the datasets. To determine the statistical significance of the difference between our method and other methods, we utilized the Wilcoxon Signed Rank Test on two parts of the dataset, and the results of the tests are significant in both cases.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Chemical reaction optimization for solving maximum diversity problem

  • Mahmudul Hasan,
  • Md. Rafiqul Islam

摘要

Finding a specific-sized set of vertices with the highest pairwise distance from a given graph is known as the Maximum Diversity Problem (MDP). So, the goal of MDP is to determine the largest diverse set of a particular size from a given weighted graph. Multiple metaheuristic approaches were proposed to solve the problem as it is an NP-hard problem. This paper presents a metaheuristic method based on the chemical reaction optimization (CRO) algorithm to solve the problem. CRO is a population-based metaheuristic algorithm to solve optimization problems. Over the past few years, it has effectively solved numerous optimization problems with better results than other metaheuristic algorithms in use. With the help of its four reaction operators, it can explore the solution space locally and globally over the population. Our proposal involves redesigning the four elementary reaction operators of the CRO algorithm and fine-tuning the initial parameters to solve MDP efficiently, as well as building an extra repair operator to increase the quality of the solution in less computational time. A dataset with more than 150 instances is used to observe the performance of our proposed method. The proposed method gives better results with fewer average errors in comparison to methods in the literature. For most of the graphs, the algorithm gives the best-known results mentioned in the datasets. To determine the statistical significance of the difference between our method and other methods, we utilized the Wilcoxon Signed Rank Test on two parts of the dataset, and the results of the tests are significant in both cases.