NSGAII With Local Search Based Heavy Perturbation for Bi-Objective Weighted Clique Problem
This paper focuses on the clique problem of a weighted graph where weights of vertices can be either positive or negative (WG-PN). Two objectives, the size and the total weight of a clique, are considered. In particular, the larger size in terms of set inclusion and the higher total weight a clique...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2018-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8463462/ |
| _version_ | 1818556889636536320 |
|---|---|
| author | Dunbo Cai Yuhui Gao Minghao Yin |
| author_facet | Dunbo Cai Yuhui Gao Minghao Yin |
| author_sort | Dunbo Cai |
| collection | DOAJ |
| description | This paper focuses on the clique problem of a weighted graph where weights of vertices can be either positive or negative (WG-PN). Two objectives, the size and the total weight of a clique, are considered. In particular, the larger size in terms of set inclusion and the higher total weight a clique is, the better it is. This problem is termed BiOWCP which is a multi-objective combinatorial optimization problem that contains conflict objectives. We show that BiOWCP cannot be translated into the clique problem of a weighted graph with positive vertex weights (WG-P) via a straight forward transformation, which highlights the difficulty of BiOWCP. We propose a heavy perturbation (HP)-based NSGAII (nondominated sorting genetic algorithm II) algorithm HP-NSGAII for the problem, where the perturbation is done by either improving a selected elitist with a local search procedure or swapping its left and right parts. Benchmarks for BiOWCP were adapted from the DIMACS set. Extensive experiments were carried out for different ratios of the heavy perturbation effort to the total search effort. Computational results show that HP-NSGAII is superior to NSGAII on many problems with respect to the hyper volume indicator and the set coverage indicator. |
| first_indexed | 2024-12-13T23:53:03Z |
| format | Article |
| id | doaj.art-54355d62b25447ba8b94fc883635e3ee |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-13T23:53:03Z |
| publishDate | 2018-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-54355d62b25447ba8b94fc883635e3ee2022-12-21T23:26:42ZengIEEEIEEE Access2169-35362018-01-016512535126110.1109/ACCESS.2018.28697328463462NSGAII With Local Search Based Heavy Perturbation for Bi-Objective Weighted Clique ProblemDunbo Cai0https://orcid.org/0000-0002-0653-3663Yuhui Gao1Minghao Yin2Hubei Provincial Key Laboratory of Intelligent Robot, Wuhan Institute of Technology, Wuhan, ChinaNational Key Laboratory of Science and Technology on Aerospace Flight Dynamics, Beijing, ChinaSchool of Computer Science and Information Technology, Northeast Normal University, Changchun, ChinaThis paper focuses on the clique problem of a weighted graph where weights of vertices can be either positive or negative (WG-PN). Two objectives, the size and the total weight of a clique, are considered. In particular, the larger size in terms of set inclusion and the higher total weight a clique is, the better it is. This problem is termed BiOWCP which is a multi-objective combinatorial optimization problem that contains conflict objectives. We show that BiOWCP cannot be translated into the clique problem of a weighted graph with positive vertex weights (WG-P) via a straight forward transformation, which highlights the difficulty of BiOWCP. We propose a heavy perturbation (HP)-based NSGAII (nondominated sorting genetic algorithm II) algorithm HP-NSGAII for the problem, where the perturbation is done by either improving a selected elitist with a local search procedure or swapping its left and right parts. Benchmarks for BiOWCP were adapted from the DIMACS set. Extensive experiments were carried out for different ratios of the heavy perturbation effort to the total search effort. Computational results show that HP-NSGAII is superior to NSGAII on many problems with respect to the hyper volume indicator and the set coverage indicator.https://ieeexplore.ieee.org/document/8463462/Clique problemevolutionary algorithmmulti-objective combinatorial optimizationnegative vertex weightweighted graph |
| spellingShingle | Dunbo Cai Yuhui Gao Minghao Yin NSGAII With Local Search Based Heavy Perturbation for Bi-Objective Weighted Clique Problem IEEE Access Clique problem evolutionary algorithm multi-objective combinatorial optimization negative vertex weight weighted graph |
| title | NSGAII With Local Search Based Heavy Perturbation for Bi-Objective Weighted Clique Problem |
| title_full | NSGAII With Local Search Based Heavy Perturbation for Bi-Objective Weighted Clique Problem |
| title_fullStr | NSGAII With Local Search Based Heavy Perturbation for Bi-Objective Weighted Clique Problem |
| title_full_unstemmed | NSGAII With Local Search Based Heavy Perturbation for Bi-Objective Weighted Clique Problem |
| title_short | NSGAII With Local Search Based Heavy Perturbation for Bi-Objective Weighted Clique Problem |
| title_sort | nsgaii with local search based heavy perturbation for bi objective weighted clique problem |
| topic | Clique problem evolutionary algorithm multi-objective combinatorial optimization negative vertex weight weighted graph |
| url | https://ieeexplore.ieee.org/document/8463462/ |
| work_keys_str_mv | AT dunbocai nsgaiiwithlocalsearchbasedheavyperturbationforbiobjectiveweightedcliqueproblem AT yuhuigao nsgaiiwithlocalsearchbasedheavyperturbationforbiobjectiveweightedcliqueproblem AT minghaoyin nsgaiiwithlocalsearchbasedheavyperturbationforbiobjectiveweightedcliqueproblem |