Change search
ReferencesLink to record
Permanent link

Direct link
Enhancing Differential Evolution Algorithm for Solving Continuous Optimization Problems
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. (Intelligent Systems)ORCID iD: 0000-0002-3425-3837
2016 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Differential Evolution (DE) has become one of the most important metaheuristics during the recent years, obtaining attractive results in solving many engineering optimization problems. However, the performance of DE is not always strong when seeking optimal solutions. It has two major problems in real world applications. First, it can easily get stuck in a local optimum or fail to generate better solutions before the population has converged. Secondly, its performance is significantly influenced by the control parameters, which are problem dependent and which vary in different regions of space under exploration.  It usually entails a time consuming trial-and-error procedure to set suitable parameters for DE in a specific problem, particularly for those practioners with limited knowledge and experience of using this technique.

 

This thesis aims to develop new DE algorithms to address the two aforementioned problems. To mitigate the first problem, we studied the hybridization of DE with local search techniques to enhance the efficiency of search. The main idea is to apply a local search mechanism to the best individual in each generation of DE to exploit the most promising regions during the evolutionary processs so as to speed up the convergence or increase the chance to scape from local optima. Four local search strategies have been integrated  and tested in the global DE framework, leading to variants of the memetic DE algorithms with different properties concerning diversification and intensification. For tackling the second problem, we propose a greedy adaptation method for dynamic adjustment of the control parameters in DE. It is implemented by conducting greedy search repeatedly during the run of DE to reach better parameter assignments in the neighborhood of a current candidate. The candidates are assessed by considering both, the success rate and also fitness improvement of trial solutions against the target ones. The incorporation of this greedy parameter adaptation method into standard DE has led to a new adaptive DE algorithm, referred to as Greedy Adaptive Differential Evolution (GADE).

 

The methods proposed in this thesis have been tested in different benchmark problems and compared with the state of the art algorithms, obtaining competitive results. Furthermore, the proposed GADE algorithm has been applied in an industrial scenario achieving more accurate results than those obtained by a standard DE algorithm. 

Abstract [sv]

Differential Evolution (DE) har blivit en av de viktigaste metaheuristikerna under de senaste åren och har uppnått attraktiva resultat för att lösa många optimeringsproblem inom teknik. Dock är prestationen hos DE inte alltid framgångsrik när man söker optimala lösningar. Det finns två huvudsakliga problem för applikationer i den verkliga världen. Det första är att den lätt kan fastna i lokala optimum eller misslyckas att generera bättre lösningar före det att populationen (en grupp av lösningar) har hunnit konvergera. Det andra är att prestandan påverkas märkvärdigt av kontrollparametrar, vilkas optimala värden beror på problem som ska lösas och varierar mellan regioner i sökrymden. Detta innebär oftast ett tidskrävande trial-and-error förfarande för att hitta lämpliga parametrar till ett specifikt DE-problem, framför allt för utövare med begränsad kunskap och erfarenhet av DE.

 

Syftet med denna licentiatavhandling är att utveckla nya DE-algoritmer för att behandla de ovannämnda problemen. För att möta det första problemet så studerades hybridisering av DE och lokala söktekniker för att effektivisera sökningen. Tanken är att använda en lokal sökmekanism på den bästa individen i varje generation i DE-algoritmen och utnyttja de mest lovande regionerna under evolutionsprocessen för att snabba på konvergensen eller öka chansen att undvika lokala optimum. Fyra lokala sökstrategier har integrerats och testats i det globala DE-ramverket vilket har lett till fyra varianter av DE-algoritmerna med olika egenskaper beträffande diversifiering och intensifiering. Till det andra problemet föreslås en greedy adaptation method för dynamisk justering av kontrollparametrarna i DE. Den implementeras genom att utföra greedy search upprepade gånger under körningen av DE för att hitta bättre värden till kontrollparametrarna. Utvärderingen av parameterval baseras på både success rate och fitness improvement av trial lösningar jämfört med target lösningar. Sammanslagningen av DE och denna greedy parameter adaptation har lett till en ny adaptiv DE-algoritm som kallas Greedy Adaptive Differential Evolution (GADE).

 

Den föreslagna metoden i denna licentiatavhandling har testats i olika prestandamätningar och jämförts med state-of-the-art-algoritmer, med goda resultat. Dessutom har den föreslagna GADE-algoritmen använts i ett industriellt scenario och uppnådde då mer exakta resultat än den med en standard DE-algoritm.

Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2016.
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 246
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:mdh:diva-33466ISBN: 978-91-7485-299-8OAI: oai:DiVA.org:mdh-33466DiVA: diva2:1040125
Presentation
2016-12-15, Delta, Mälardalens högskola, Västerås, 13:15 (English)
Opponent
Supervisors
Available from: 2016-10-26 Created: 2016-10-25 Last updated: 2016-11-25Bibliographically approved
List of papers
1. Greedy adaptation of control parameters in differential evolution for global optimization problems
Open this publication in new window or tab >>Greedy adaptation of control parameters in differential evolution for global optimization problems
2015 (English)In: IEEE Conference on Evolutionary Computation 2015 ICEC15, 2015, 385-392 p.Conference paper (Refereed)
Abstract [en]

Differential evolution (DE) is a very attractive evolutionary and meta-heuristic technique to solve many optimization problems in various real-world scenarios. However, the proper setting of control parameters of DE is highly dependent on the problem to solve as well as on the different stages of the search process. This paper proposes a new greedy adaptation method for dynamic adjustment of mutation factor and crossover rate in DE. The proposed method is based on the idea of greedy search to find better parameter assignment in the neighborhood of a current candidate. Our work emphasizes reliable evaluation of candidates via applying a candidate with a number of times in the search process. As our purpose is not merely to increase the success rate (the survival of more trial solutions) but also to accelerate the speed of fitness improvement, we suggest a new metric termed as progress rate to access the quality of candidates in support of the greedy search. This greedy parameter adaptation method has been incorporated into basic DE, leading to a new DE algorithm called Greedy Adaptive Differential Evolution (GADE). GADE was tested on 25 benchmark functions in comparison with five other DE variants. The results of evaluation demonstrate that GADE is strongly competitive: it obtains the best ranking among the counterparts in terms of the summation of relative errors across the benchmark functions.

National Category
Computer and Information Science
Identifiers
urn:nbn:se:mdh:diva-28154 (URN)10.1109/CEC.2015.7256916 (DOI)2-s2.0-84963593375 (ScopusID)9781479974924 (ISBN)
Conference
IEEE Conference on Evolutionary Computation 2015 ICEC15, 25-28 May 2015, SENDAI, Japan
Projects
EMOPAC - Evolutionary Multi-Objective Optimization and Its Applications in Analog Circuit Design
Available from: 2015-06-12 Created: 2015-06-08 Last updated: 2016-10-26Bibliographically approved
2. Adaptive Differential Evolution Supports Automatic Model Calibration in Furnace Optimized Control System
Open this publication in new window or tab >>Adaptive Differential Evolution Supports Automatic Model Calibration in Furnace Optimized Control System
2017 (English)In: Computational Intelligence / [ed] Agostinho Rosa, Juan Julian Merelo, António Dourado, José M. Cadenas, Kurosh Madani, António Ruano and Joaquim Filipe, Germany: Springer, 2017, Vol. 669Chapter in book (Other academic)
Abstract [en]

Model calibration represents the task of estimating the parameters of a process model to obtain a good match between observed and simulated behaviours. This can be considered as an optimization problem to search for model parameters that minimize the discrepancy between the model outputs and the corresponding features from the historical empirical data. This chapter investigates the use of Differential Evolution (DE), a competitive class of evolutionary algorithms, to solve calibration problems for nonlinear process models. The merits of DE include simple and compact structure, easy implementation, as well as high convergence speed. However, the good performance of DE relies on proper setting of its running parameters such as scaling factor and crossover probability, which are problem dependent and which can even vary in the different stages of the search. To mitigate this issue, we propose a new adaptive DE algorithm that dynamically adjusts its running parameters during its execution. The core of this new algorithm is the incorporated greedy local search, which is conducted in successive learning periods to continuously locate better parameter assignments in the optimization process. In case studies, we have applied our proposed adaptive DE algorithm for model calibration in a Furnace Optimized Control System. The statistical analysis of experimental results demonstrate that the proposed DE algorithm can support the creation of process models that are more accurate than those produced by standard DE.

Place, publisher, year, edition, pages
Germany: Springer, 2017
Keyword
Differential Evolution, Optimization, Model Identifi cation, Temperature estimation
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-33465 (URN)
Projects
EMOPAC - Evolutionary Multi-Objective Optimization and Its Applications in Analog Circuit Design
Available from: 2016-10-25 Created: 2016-10-25 Last updated: 2016-10-26
3. Differential evolution enhanced with eager random search for solving real-parameter optimization problems
Open this publication in new window or tab >>Differential evolution enhanced with eager random search for solving real-parameter optimization problems
2015 (English)In: International Journal of Advanced Research in Artificial Intelligence, 2015 IJARAI-15, ISSN 2165-4050, Vol. 4, no 12, 49-57 p.Article in journal (Refereed) Published
Abstract [en]

Differential evolution (DE) presents a class of evolutionary computing techniques that appear effective to handle real parameter optimization tasks in many practical applications. However, the performance of DE is not always perfect to ensure fast convergence to the global optimum. It can easily get stagnation resulting in low precision of acquired results or even failure. This paper proposes a new memetic DE algorithm by incorporating Eager Random Search (ERS) to enhance the performance of a basic DE algorithm. ERS is a local search method that is eager to replace the current solution by a better candidate in the neighborhood. Three concrete local search strategies for ERS are further introduced and discussed, leading to variants of the proposed memetic DE algorithm. In addition, only a small subset of randomly selected variables is used in each step of the local search for randomly deciding the next trial solution. The results of tests on a set of benchmark problems have demonstrated that the hybridization of DE with Eager Random Search can substantially augment DE algorithms to find better or more precise solutions while not requiring extra computing resources.

Place, publisher, year, edition, pages
Sweden: , 2015
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-32785 (URN)10.14569/IJARAI.2015.041208 (DOI)
External cooperation:
Projects
ESS-H - Embedded Sensor Systems for Health Research ProfileEMOPAC - Evolutionary Multi-Objective Optimization and Its Applications in Analog Circuit Design
Available from: 2016-08-26 Created: 2016-08-24 Last updated: 2016-10-26Bibliographically approved
4. A new differential evolution algorithm with Alopex-based local search
Open this publication in new window or tab >>A new differential evolution algorithm with Alopex-based local search
2016 (English)In: Lecture Notes in Computer Science, Volume 9692, 2016, 420-431 p.Conference paper (Refereed)
Abstract [en]

Differential evolution (DE), as a class of biologically inspired and meta-heuristic techniques, has attained increasing popularity in solving many real world optimization problems. However, DE is not always successful. It can easily get stuck in a local optimum or an undesired stagnation condition. This paper proposes a new DE algorithm Differential Evolution with Alopex-Based Local Search (DEALS), for enhancing DE performance. Alopex uses local correlations between changes in individual parameters and changes in function values to estimate the gradient of the landscape. It also contains the idea of simulated annealing that uses temperature to control the probability of move directions during the search process. The results from experiments demonstrate that the use of Alopex as local search in DE brings substantial performance improvement over the standard DE algorithm. The proposed DEALS algorithm has also been shown to be strongly competitive (best rank) against several other DE variants with local search. 

Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9692
Keyword
Alopex, Differential evolution, Local search, Memetic algorithm, Optimization, Algorithms, Artificial intelligence, Evolutionary algorithms, Heuristic methods, Local search (optimization), Simulated annealing, Soft computing, Biologically inspired, Differential evolution algorithms, Memetic algorithms, Meta-heuristic techniques, Real-world optimization
National Category
Computer and Information Science
Identifiers
urn:nbn:se:mdh:diva-32383 (URN)10.1007/978-3-319-39378-0_37 (DOI)2-s2.0-84976613386 (ScopusID)9783319393773 (ISBN)
Conference
15th International Conference on Artificial Intelligence and Soft Computing, ICAISC 2016; Zakopane; Poland; 12 June 2016 through 16 June 2016
Available from: 2016-07-14 Created: 2016-07-14 Last updated: 2016-10-26Bibliographically approved

Open Access in DiVA

fulltext(388 kB)18 downloads
File information
File name FULLTEXT02.pdfFile size 388 kBChecksum SHA-512
2ecbbe28c410805db95968a41b6e18ce809c8f61a93f777564673db9ff137820f36786b42ceb6550f0dc26748d183f7214f0ae3693f83362ea711d7d02352784
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Leon, Miguel
By organisation
Embedded Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 18 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 327 hits
ReferencesLink to record
Permanent link

Direct link