Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis

Lead Research Organisation: Aberystwyth University
Department Name: Computer Science

Abstract

Abstracts are not currently available in GtR for all funded research. This is normally because the abstract was not required at the time of proposal submission, but may be because it included sensitive information such as personal details.
 
Description (1) We have proposed average drift analysis as a theoretical tool for comparing the computational time of different evolutionary algorithms. Using this tool, we have answered several theoretical questions in evolutionary computation, such as which fitness functions are the easiest or hardest to evolutionary algorithms are; how the computational time of evolutionary algorithms is related to the population size; and when a mixed search strategy may outperform a pure search strategy.

(2) We have introduced a new index to measure the approximation performance of evolutionary algorithms, called average convergence rate. The rate provides a new way to understand the approximation solution quality in evolutionary algorithms. For evolutionary algorithms, a matrix analysis tool is presented as a tool for estimating the average convergence rate.

(3) We have investigated the approximation performance of evolutionary algorithms on several combinatorial optimization problems, including the minimum label spanning tree problem, single machine scheduling problem and knapsack problem. We rigorously showed the effectiveness of two strategies in designing evolutionary approximation algorithms: hybridization and multi-objective optimization.
Exploitation Route (1) The analytical tools developed in the project can help other researchers in evolutionary computation to carry out further analysis of different evolutionary algorithms on different problems. The tools have been applied to a rigorous proof of "that the unimodal functions are the easiest and deceptive functions are the hardest in terms of the time-fitness landscape" [https://doi.org/10.1016/j.ins.2017.10.038] and the results have been adopted as the theoretical assumption in the constructing of benchmark problems in evolutionary computation [https://doi.org/10.1016/j.swevo.2018.04.005]. The contribution has been recognised in [https://doi.org/10.1109/TEVC.2019.2921547] as it "rigorously analyzed the effect of population size on the computation time of EAs using mutation and elitist selection".

(2) The proposed average convergence rate has been become "the fourth type of convergence representation" "that specifically measures the rate of fitness change" [https://doi.org/10.1007/s10462-020-09906-6]. "Convergence ratio can be evaluated by Markow chain analysis, however, this process is complicated from theoretical and practical point of view" [https://doi.org/10.1016/j.petrol.2018.10.005]. "For this reason," the new convergence rate has been adopted in quantifying, visualising and comparing the convergence rate of evolutionary algorithms in computer simulation, such as [https://doi.org/10.1109/ACCESS.2019.2900078, https://doi.org/10.1016/j.asoc.2017.12.048, https://doi.org/10.1007/s00500-018-3218-6, https://doi.org/10.1631/FITEE.1601553, https://doi.org/10.1002/ett.3827, https://doi.org/10.2166/hydro.2020.016].

(2) The two strategies rigorously analysed in the project (hybridization and multi-objective optimization) could be helpful in designing efficient evolutionary approximation algorithms for optimization problems in different areas. Based on multi-objective optimization, we propose a new approach of designing efficient multiobjective evolutionary algorithms for solving constrained optimization problems through combining helper and equivalent objectives together. The designed algorithm was ranked 1st in the IEEE Congress on Evolutionary Computation Competition on Constrained Real Parameter Optimization [https://github.com/P-N-Suganthan/CEC2017].
Sectors Digital/Communication/Information Technologies (including Software)
 
Description Please refer to the impact description provided for the lead grant EP/I010297/1, of which this project a part.
First Year Of Impact 2022
Sector Digital/Communication/Information Technologies (including Software)
 
Description Collaboration with University of Birmingham 
Organisation University of Birmingham
Department School of Computer Science
Country United Kingdom 
Sector Academic/University 
PI Contribution Research partner in this joint project. Co-organise workshop.
Collaborator Contribution Research partner in this joint project. Co-organise workshop.
Impact 10.1109/TEVC.2014.2318025 7th Workshop on Theory of Randomised Search Heuristics