Automatic generation of algorithms for robust optimisation problems using Grammar-Guided Genetic Programming. (September 2021)

• Record Type: Journal Article
• Authors: Hughes, Martin; Goerigk, Marc; Dokka, Trivikram
• Is Part Of: Computers & operations research. Volume 133(2021)
• Publication Date: 2021-09
• Subjects: Robust optimisation -- Implementation uncertainty -- Metaheuristics -- Global optimisation -- Genetic programming; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105364
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: We develop algorithms capable of tackling robust black-box optimisation problems, where the number of model runs is limited. When a desired solution cannot be implemented exactly the aim is to find a robust one, where the worst case in an uncertainty neighbourhood around a solution still performs well. To investigate improved methods we employ an automatic generation of algorithms approach: Grammar-Guided Genetic Programming. We develop algorithmic building blocks in a Particle Swarm Optimisation framework, define the rules for constructing heuristics from these components, and evolve populations of search algorithms for robust problems. Our algorithmic building blocks combine elements of existing techniques and new features, resulting in the investigation of a novel heuristic solution space. We obtain algorithms which improve upon the current state of the art. We also analyse the component level breakdowns of the populations of algorithms developed against their performance, to identify high-performing heuristic components for robust problems. Highlights: Using genetic programming we evolve metaheuristics for robust global optimisation. The developed approaches are generic, with no assumptions on the objective structure. We use a grammar of a PSO framework and numerous robust heuristic sub-algorithms. We compare against the best current method on multiple test instances. Experiments reveal a strong performance, giving insight into algorithmic efficacy.