Application of hybrid evolutionary algorithm for solving the Set Covering Problem

被引：0
|
作者：
Lin, Geng [1 ]
机构：
[1] Minjiang Univ, Dept Math, Fuzhou 350108, Peoples R China
来源：
MODERN COMPUTER SCIENCE AND APPLICATIONS II (MCSA 2017) | 2017年
关键词：
set covering problem; evolutionary algorithm; simulated annealing; MEMETIC ALGORITHM;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The set covering problem is an important NP-hard combinatorial optimization problem with a wide range of applications. In this paper, we develop a hybrid evolutionary algorithm to solve the set covering problem. Firstly, a constructive procedure is designed to generate initial solutions. Secondly, we employ a simulated annealing based local search procedure to intensify the search. Finally, a filter mechanism is used to reduce the solution time. The simulation on a set of 25 instances indicates the proposed algorithm is effective.
引用
收藏
页码：46 / 52
页数：7
相关论文
共 50 条
  • [31] Hybrid evolutionary algorithm for solving optimization problems
    Li, Kangshun
    Li, Wei
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2007, 84 (11) : 1591 - 1602
  • [32] Solving the 2D bin packing problem by means of a hybrid evolutionary algorithm
    Blum, Christian
    Schmid, Verena
    2013 INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE, 2013, 18 : 899 - 908
  • [33] Solving the Set Covering Problem with Conflicts on Sets: A new parallel GRASP
    Carrabs, Francesco
    Cerulli, Raffaele
    Mansini, Renata
    Moreschini, Lorenzo
    Serra, Domenico
    COMPUTERS & OPERATIONS RESEARCH, 2024, 166
  • [34] An improved genetic algorithm with conditional genetic operators and its application to set-covering problem
    Wang, Rong-Long
    Okazaki, Kozo
    SOFT COMPUTING, 2007, 11 (07) : 687 - 694
  • [35] An improved genetic algorithm with conditional genetic operators and its application to set-covering problem
    Rong-Long Wang
    Kozo Okazaki
    Soft Computing, 2007, 11 : 687 - 694
  • [36] Solving the Minimum Dominating Set Problem of Partitioned Graphs Using a Hybrid Bat Algorithm
    Abed, Saad Adnan
    Rais, Helmi Md
    EMERGING TRENDS IN INTELLIGENT COMPUTING AND INFORMATICS: DATA SCIENCE, INTELLIGENT INFORMATION SYSTEMS AND SMART COMPUTING, 2020, 1073 : 386 - 395
  • [37] An empirical study of hybrid genetic algorithms for the set covering problem
    Vasko, FJ
    Knolle, PJ
    Spiegel, DS
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2005, 56 (10) : 1213 - 1223
  • [38] A variable neighborhood search algorithm for the multimode set covering problem
    Fabio Colombo
    Roberto Cordone
    Guglielmo Lulli
    Journal of Global Optimization, 2015, 63 : 461 - 480
  • [39] An Improved Heuristic Algorithm for the Special Case of the Set Covering Problem
    Gonen
    Avrahami, T.
    Israeli, U.
    2013 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT (IEEM 2013), 2013, : 93 - 97
  • [40] A Discrete Invasive Weed Optimization Algorithm For The Set Covering Problem
    Crawford, Broderick
    Soto, Ricardo
    Fuenzalida Legue, Ismael
    Olguin, Eduardo
    2016 11TH IBERIAN CONFERENCE ON INFORMATION SYSTEMS AND TECHNOLOGIES (CISTI), 2016,
12345