Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Memetic Algorithm with Filtering Scheme for the Minimum Weighted Edge Dominating Set Problem

Abdulaziz, Shada LU ; Hedar, Abdel-Rahman and Sewisy, Adel (2013) In International Journal of Advanced Research in Artificial Intelligence 2(8). p.44-49
Abstract
The minimum weighted edge dominating set problem (MWEDS) generalizes both the weighted vertex cover problem and the problem of covering the edges of graph by a minimum cost set of both vertices and edges. In this paper, we propose a meta heuristic approach based on genetic algorithm and local search to solve the MWEDS problem. Therefore, the proposed method is considered as a memetic search algorithm which is called Memetic Algorithm with filtering scheme for minimum weighted edge dominating set, and called shortly (MAFS). In the MAFS method, three new fitness functions are invoked to effectively measure the solution qualities. The search process in the proposed method uses intensification scheme, called “filtering”, beside the main... (More)
The minimum weighted edge dominating set problem (MWEDS) generalizes both the weighted vertex cover problem and the problem of covering the edges of graph by a minimum cost set of both vertices and edges. In this paper, we propose a meta heuristic approach based on genetic algorithm and local search to solve the MWEDS problem. Therefore, the proposed method is considered as a memetic search algorithm which is called Memetic Algorithm with filtering scheme for minimum weighted edge dominating set, and called shortly (MAFS). In the MAFS method, three new fitness functions are invoked to effectively measure the solution qualities. The search process in the proposed method uses intensification scheme, called “filtering”, beside the main genetic search operations in order to achieve faster performance. The experimental results proves that the proposed method is promising in solving the MWEDS problem.
(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Minimum weight edge dominating set, Graph theory, Genetic algorithm, Memetic algorithm, Local search
in
International Journal of Advanced Research in Artificial Intelligence
volume
2
issue
8
pages
6 pages
publisher
Science and Information Organization
ISSN
2165-4069
DOI
10.14569/IJARAI.2013.020808
language
English
LU publication?
yes
id
be36ca06-0fbe-42c5-99be-9affcb3d99c7
date added to LUP
2019-09-27 12:20:57
date last changed
2019-09-27 15:17:17
@article{be36ca06-0fbe-42c5-99be-9affcb3d99c7,
  abstract     = {{The minimum weighted edge dominating set problem (MWEDS) generalizes both the weighted vertex cover problem and the problem of covering the edges of graph by a minimum cost set of both vertices and edges. In this paper, we propose a meta heuristic approach based on genetic algorithm and local search to solve the MWEDS problem. Therefore, the proposed method is considered as a memetic search algorithm which is called Memetic Algorithm with filtering scheme for minimum weighted edge dominating set, and called shortly (MAFS). In the MAFS method, three new fitness functions are invoked to effectively measure the solution qualities. The search process in the proposed method uses intensification scheme, called “filtering”, beside the main genetic search operations in order to achieve faster performance. The experimental results proves that the proposed method is promising in solving the MWEDS problem.<br/>}},
  author       = {{Abdulaziz, Shada and Hedar, Abdel-Rahman and Sewisy, Adel}},
  issn         = {{2165-4069}},
  keywords     = {{Minimum weight edge dominating set; Graph theory; Genetic algorithm; Memetic algorithm; Local search}},
  language     = {{eng}},
  number       = {{8}},
  pages        = {{44--49}},
  publisher    = {{Science and Information Organization}},
  series       = {{International Journal of Advanced Research in Artificial Intelligence}},
  title        = {{Memetic Algorithm with Filtering Scheme for the Minimum Weighted Edge Dominating Set Problem}},
  url          = {{http://dx.doi.org/10.14569/IJARAI.2013.020808}},
  doi          = {{10.14569/IJARAI.2013.020808}},
  volume       = {{2}},
  year         = {{2013}},
}