Noisy Combinatorial Optimisation by Evolutionary Algorithms

被引：4
|
作者：
Aishwaryaprajna [1 ]
Rowe, Jonathan E. [1 ]
机构：
[1] Univ Birmingham, Sch Comp Sci, Birmingham, W Midlands, England
来源：
PROCEEDINGS OF THE 2019 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE COMPANION (GECCCO'19 COMPANION) | 2019年
关键词：
Noisy combinatorial optimisation; Gaussian noise; Expected runtime;
D O I：
10.1145/3319619.3321955
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We investigate the effectiveness of a set of evolutionary algorithms on noisy combinatorial optimisation problems. Despite some of these having polynomial runtime bounds for noisy ONEMAX, we find that in practice they are not able to solve this problem in reasonable time, with the exception of the Paired Crossover EA, and UMDA. We further study the performance of these two algorithms on noisy versions of SUBSETSUM and KNAPSACK.
引用
收藏
页码：139 / 140
页数：2
相关论文
共 50 条
  • [41] Genetic algorithms solve combinatorial optimisation problems in the calibration of combustion engines
    Knödler, K
    Poland, J
    Mitterer, A
    Zell, A
    OPTIMAIZATION IN INDUSTRY, 2002, : 45 - 56
  • [42] Micro-genetic algorithms (μGAs) for hard combinatorial optimisation problems
    Kim, Y
    Gotoh, K
    Toyosada, M
    Park, J
    PROCEEDINGS OF THE TWELFTH (2002) INTERNATIONAL OFFSHORE AND POLAR ENGINEERING CONFERENCE, VOL 4, 2002, : 230 - 235
  • [43] A data mining approach to evolutionary optimisation of noisy multi-objective problems
    Chia, J. Y.
    Goh, C. K.
    Shim, V. A.
    Tan, K. C.
    INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 2012, 43 (07) : 1217 - 1247
  • [44] Genetic diversity: applications of evolutionary algorithms to combinatorial library design
    Brown, RD
    Clark, DE
    EXPERT OPINION ON THERAPEUTIC PATENTS, 1998, 8 (11) : 1447 - 1459
  • [45] The Importance of Proper Diversity Management in Evolutionary Algorithms for Combinatorial Optimization
    Segura, Carlos
    Hernandez Aguirre, Arturo
    Valdez Pena, Sergio Ivvan
    Botello Rionda, Salvador
    NEO 2015, 2017, 663 : 121 - 148
  • [46] Adaptive Evolutionary Genetic Algorithms on a Class of Combinatorial Optimization Problems
    Zhong, Sheng
    Zhang, Baihai
    Li, Qiao
    Li, Jun
    Lin, Zhiwei
    ICNC 2008: FOURTH INTERNATIONAL CONFERENCE ON NATURAL COMPUTATION, VOL 1, PROCEEDINGS, 2008, : 166 - +
  • [47] Time Complexity of Evolutionary Algorithms for Combinatorial Optimization: A Decade of Results
    Oliveto, Pietro S.
    He, Jun
    Yao, Xin
    INTERNATIONAL JOURNAL OF AUTOMATION AND COMPUTING, 2007, 4 (03) : 281 - 293
  • [48] Visualisation of the combinatorial effects within evolutionary algorithms: the compass plot
    Wang, Qi
    Guan, Miaoting
    Huang, Wen
    Wang, Libing
    Wang, Zhihong
    Liu, Shuming
    Savic, Dragan
    JOURNAL OF HYDROINFORMATICS, 2021, 23 (03) : 517 - 528
  • [49] Time Complexity of Evolutionary Algorithms for Combinatorial Optimization:A Decade of Results
    Pietro S.Oliveto
    International Journal of Automation & Computing, 2007, (03) : 281 - 293
  • [50] Stereo-Matching Techniques Optimisation Using Evolutionary Algorithms
    Bevilacqua, Vitoantonio
    Mastronardi, Giuseppe
    Menolascina, Filippo
    Nitti, Davide
    INTELLIGENT COMPUTING, PART I: INTERNATIONAL CONFERENCE ON INTELLIGENT COMPUTING, ICIC 2006, PART I, 2006, 4113 : 612 - 621
12345