Evolutionary Algorithms for Dynamic Optimisation Problems: Design, Analysis and Applications

Lead Research Organisation: University of Birmingham
Department Name: School of Computer Science

Abstract

Evolutionary algorithms (EAs) have been applied to solve many stationary problems. However, real-world problems are usually more complex and dynamic, where the objective function, decision variables, and environmental parameters may change over time. In this project, we will investigate novel EA approaches to address dynamic optimisation problems (DOPs), a challenging but very important research area. The proposed research has three main aspects: (1) designing and evaluating new EAs for DOPs in collaboration with researchers from Honda Research Institute Europe, (2) theoretically analysing EAs for DOPs, and (3) adapting developed EA approaches to solve dynamic telecommunication optimisation problems. In this project, we will first construct standardised, both discrete and continuous, dynamic test environments based on the concept of problem difficulty, scalability, cyclicity and noise of environments, and standardised performance measures for evaluating EAs for DOPs. Based on the standardised dynamic test and evaluation environment, we will then design and evaluate novel EAs and their hybridisation, e.g., Estimation of Distribution Algorithms (EDAs), Genetic Algorithms, Swarm Intelligence and Adaptive Evolutionary Algorithms, for DOPs based on our previous research. A guiding idea here is to improve EA's adaptability to different degrees of environmental change in the genotypic space, be it binary or not. Systematically and adaptively combining dualism-like schemes for significant changes, random immigration-like schemes for medium changes, and general mutation or variation schemes for small changes, is expected to greatly improve EA's performance in different dynamic environments. And memory schemes can be used when the environment involves cyclic changes. In order to better understand the fundamental issues, theoretical analysis of EAs for DOPs will be pursued in this project. We will apply drift analysis and martingale theory as the starting point to analyse the computational time complexity of EAs for DOPs and the dynamic behaviour of EAs for DOPs regarding such properties as tracking error, tracking velocity, and reliability of arriving at optima. Based on the above EA design, experimental evaluation, and formal analysis, we will then develop a generic framework of EAs for DOPs by extracting key techniques/properties of efficient EAs for DOPs and studying the relationship between them and the characteristics of DOPs being solved with respect to the environmental dynamics in the genotypic space. Another key aspect of this project is to apply and adapt developed EAs for general DOPs to solve core dynamic telecommunications problems, e.g., dynamic frequency assignment problems and dynamic call routing problems, in the real world. We will closely collaborate with researchers from British Telecommunications (BT) to extract domain-specific knowledge and model dynamic telecommunication problems using proper mathematical and graph representations. The obtained domain knowledge will be integrated into our EAs for increased efficiency and effectiveness. All algorithms and software developed in this project will be made available publicly to benefit as many users as possible, whether they are from academe or industry.

Publications

10 25 50

publication icon
Ke Tang (2009) Memetic Algorithm With Extended Neighborhood Search for Capacitated Arc Routing Problems in IEEE Transactions on Evolutionary Computation

publication icon
Li-Ning Xing (2011) A Hybrid Ant Colony Optimization Algorithm for the Extended Capacitated Arc Routing Problem. in IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society

publication icon
Lining Xing (2010) An Evolutionary Approach to the Multidepot Capacitated Arc Routing Problem in IEEE Transactions on Evolutionary Computation

publication icon
Mei Y (2011) Decomposition-Based Memetic Algorithm for Multiobjective Capacitated Arc Routing Problem in IEEE Transactions on Evolutionary Computation

publication icon
Mei Y (2009) A global repair operator for capacitated arc routing problem. in IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society

publication icon
Nguyen T (2012) Continuous Dynamic Constrained Optimization-The Challenges in IEEE Transactions on Evolutionary Computation

 
Description There are a number of significant new results that were obtained from this project.



First, we have developed a series of novel algorithms for complex capacitated arc routing problems, including problems with multiple depots and heterogeneous truck capacities. These problems occur frequently in the real world, e.g., in route optimisation of winter gritting/salting trucks. We have obtained the best results in the literature using our new algorithms.



Second, we have studied theoretically dynamic optimisation and its difficulties, and published one of the first theoretical results on analysing the computation time of evolutionary dynamic optimisation algorithms. The results showed some surprising results and won the Best Paper Award in the Theory Track of GECCO'2009.



Third, we pioneered the study of dynamic constraints in evolutionary dynamic optimisation. A detailed analysis of real-world situations was conducted so that a set of characteristics were identified. Effective new algorithms were developed to handle dynamic optimisation problems that have dynamic objective functions as well as dynamic constraints.



Fourth, we identified for the first time a new type of dynamic optimisation problems, roboust optimisation over time (ROOT), which had not been considered before in spite of its very practical considerations.
Exploitation Route The work has led to new contacts with Vaisala, Network Rail, and SAIC (Shanghai Automotive Industry Corp) in Birmingham, in addition to original project partners of Honda and BT. A follow on project, funded by the EPSRC Knowledge Secondment Scheme (managed by the University of Birmingham), was set up with SAIC to explore the the potentials of applying dynamic optimisation techniques in engine management system. After the secondment scheme was ended, the seconded research fellow was offered a job by a company specialising in automotive software. This is an excellent route of knowledge transfer, because the research fellow is a specialist in evolutionary optimisation, whose expertise was sought by the company. This EPSRC project and our research outcomes have attracted interested from outside the academic world. We were invited to give a talk at Vaisala Ltd, describing our new algorithms for route optimisation. The work has also attracted interests from Network Rail, who becomes the new project partner for our new EPSRC grant in this area. The primary route that we are keen on exploring is to partner with a commercial partner in transferring the knowledge to industry.
Sectors Digital/Communication/Information Technologies (including Software)

URL http://www.cercia.ac.uk/projects/eadop/
 
Description DEFENCE SCIENCE AND TECHNOLOGY ORG
Amount £62,360 (GBP)
Funding ID DSTO Stage 2 
Organisation Australian Government 
Department Defence Science and Technology Group
Sector Public
Country Australia
Start  
 
Description British Telecommunications Plc 
Organisation BT Group
Country United Kingdom 
Sector Private 
Start Year 2004
 
Description Honda Research Institute Europe GmbH 
Organisation Honda Research Institute Europe GmbH
Country Germany 
Sector Private 
PI Contribution We co-authored papers with the industrial partner.
Collaborator Contribution We co-authored papers with the industrial partner. The partner also funded a student separately from the EPSRC project.
Impact H. Fu, B. Sendhoff, K. Tang and X. Yao, ``Robust Optimization Over Time: Problem Difficulties and Benchmark Problems,'' IEEE Transactions on Evolutionary Computation, 19(5):731-745, October 2015. X. Lu, K. Tang, B. Sendhoff and X. Yao, ``A New Self-adaptation Scheme for Differential Evolution,'' Neurocomputing, 146:2-16, 25 December 2014. X. Lu, K. Tang, B. Sendhoff and X. Yao, ``A review of concurrent optimisation methods,'' International Journal of Bio-Inspired Computation, 6(1):22-31, January 2014. Y. Jin, K. Tang, X. Yu, B. Sendhoff and X. Yao, ``A framework for finding robust optimal solutions over time,'' Memetic Computing, 5(1):3-18, March 2013.
Start Year 2007