https://www.mdu.se/

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. 

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.

Differential Evolution (DE) is a population-based algorithm that belongs to the Evolutionary algorithm family. During recent years, DE has become a popular algorithm in optimization due to its strength solving different types of optimization problems and due to its easy usage and implementation.

However, how to choose proper mutation strategy and control parameters for DE presents a major difficulty in many real applications. Since both mutation strategy and DE control parameters are highly problem dependent, they have to be adapted to suite different search spaces and different problems. Failure in proper assignment for them will cause slow convergence in search or stagnation with a local optimum.

Many researches have been conducted to tackle the above issues. The major efforts have been made in the following three directions. First, some works have been proposed that adapt the selection between various mutation strategies. But the choice of strategies in these methods has not considered the difference of quality of individuals in the population, which means that all individuals will acquire the same probability to select a mutation strategy from the candidates. This does not seem a very desired practice since solutions of large difference would require different mutation operators to reach improvement. Second, many works have been focusing on the adaptation of the control parameters of DE (mutation factor (F) and crossover rate (CR)). They mainly rely on previous successful F and CR values to update the probability functions that are used to generate new F and CR values. By doing this, they ignore the stochastic nature of the operators in DE such that weak F and CR values can also get success in producing better trial solutions. The use of such imprecise experiences of success would prevent the DE parameters from being adapted towards the most effective values in coming generations. Third, various local search methods have been incorporated into DE to enhance exploitation in promising regions so as to speed up the convergence to optima. It is important to properly adjust the characteristics of the local search in DE to achieve well balanced exploratory/exploitative behavior to solve complex optimization problems.

This thesis aims to further improve the performance of DE by new adaptation and local search methods. The main results can be summarized in the following three aspects:

1) Proposal of a new rank-based mutation adaptation method, which takes into account the quality of solutions in the population when adapting the selection probabilities of mutation strategies. This makes possible to treat solutions with distinct ranks (in quality) differently by using different selection probabilities for mutation operators.

2) Development of improved parameter adaptation methods for DE, which emphasizes more reliable and fair evaluation of candidates (F and CR assignments) during the search process. It is suggested that greedy search being used as a fast and cheap technique to look for better parameter assignment for F and CR respectively in the neighborhood of a current candidate. Further, a joint parameter adaptation method is proposed that enables continuous update of the selection probabilities for F and CR pairs based on feedback acquired during the search.

3) Proposal of new methods for better incorporation of local search into a DE algorithm. The Eager Random Search method is investigated as local search inside DE, which exhibits different exploratory-exploitative characteristics by using different probability density functions. More importantly, we propose a novel memetic framework in which Alopex local search (ALS) is performed in collaboration with a DE algorithm. The framework favors seamless connection between exploration and exploitation in the sense that the behavior of exploitation by ALS can be controlled by the status of global exploration by DE.

The proposed methods and algorithms have been tested in a number of benchmark problems, obtaining competitive results compared with the state-of-the-art algorithms. Additionally, the Greedy Adaptive DE (GADE) algorithm (developed based on greedy search for DE parameters) has been tested in a real industrial problem, i.e., finding best component parameters to optimize the performance of harmonic filters for power transmission. GADE is shown to produce better harmonic filter systems with lower harmonic distortion than the standard DE.