eTheses Repository

Adaptive operator search for the capacitated arc routine problem

Consoli, Pietro A. (2018)
Ph.D. thesis, University of Birmingham.

Loading
PDF (2877Kb)Accepted Version

Abstract

Evolutionary Computation approaches for Combinatorial Optimization have been successfully proposed for a plethora of different NP-Hard Problems. This research area has achieved acknowledgeable results and obtained remarkable progresses, and it has ultimately established itself as one of the most studied in AI. Yet, predicting the approximation ability of Evolutionary Algorithms (EAs) on novel problem instances remains a difficult easy task. As a consequence, their application in a real-world optimization context is reduced, as EAs are often considered not reliable and mature enough to be adopted in an industrial scenario. This thesis proposes new approaches to endow such meta-heuristics with a mechanism that would allow them to extract information during the search and to adaptively use such information in order to modify their behaviour and ultimately improve their performances. We consider the case study of the Capacitated Arc Routing Problem (CARP), to demonstrate the effectiveness of adaptive search techniques in a complex problem deeply connected with real-world scenarios. In particular, the main contributions of this thesis are:

1. An investigation of the adoption of a Parameter Tuning mechanism to adaptively choose the crossover operator that is used during the search;

2. The study of a novel Adaptive Operator Selection technique based on the use of Fitness Landscape Analysis techniques and on Online Learning;

3. A novel approach based on Knowledge Incorporation focusing on the reuse of information learned from the execution of a meta-heuristic on past instances, that is later used to improve the performances on the newly encountered.

Type of Work:Ph.D. thesis.
Supervisor(s):Yao, Xin (1962-)
School/Faculty:Colleges (2008 onwards) > College of Engineering & Physical Sciences
Department:School of Computer Science
Additional Information:

Publications arising from thesis:

Consoli, P., & Yao, X. (2014, April). Diversity-driven selection of multiple crossover operators for the capacitated arc routing problem. In European Conference on Evolutionary Computation in Combinatorial Optimization (pp. 97-108). Springer Berlin Heidelberg;
http://dx.doi.org/10.1007/978-3-662-44320-0_9

Consoli, P. A., Minku, L. L., & Yao, X. (2014, December). Dynamic selection of evolutionary algorithm operators based on online learning and fitness landscape metrics. In Asia-Pacific Conference on Simulated Evolution and Learning (pp. 359-370). Springer International Publishing;
http://dx.doi.org/10.1007/978-3-319-13563-2_31

Consoli, P. A., Mei, Y., Minku, L. L., & Yao, X. (2016). Dynamic selection of evolutionary operators based on online learning and fitness landscape analysis. Soft Computing, 20(10), 3889-3914.
http://dx.doi.org/10.1007/s00500-016-2126-x

Wu, X., Consoli, P., Minku, L., Ochoa, G., & Yao, X. (2016, September). An Evolutionary Hyper-heuristic for the Software Project Scheduling Problem. In International Conference on Parallel Problem Solving from Nature (pp. 37-47). Springer International Publishing.
http://dx.doi.org/10.1007/978-3-319-45823-6_4

Subjects:QA75 Electronic computers. Computer science
Institution:University of Birmingham
ID Code:8208
This unpublished thesis/dissertation is copyright of the author and/or third parties. The intellectual property rights of the author or third parties in respect of this work are as defined by The Copyright Designs and Patents Act 1988 or as modified by any successor legislation. Any use made of information contained in this thesis/dissertation must be in accordance with that legislation and must be properly acknowledged. Further distribution or reproduction in any format is prohibited without the permission of the copyright holder.
Export Reference As : ASCII + BibTeX + Dublin Core + EndNote + HTML + METS + MODS + OpenURL Object + Reference Manager + Refer + RefWorks
Share this item :
QR Code for this page

Repository Staff Only: item control page