Hidden-Markov-Based Self-adaptive Differential Evolution

Abstract

Heuristic search is an efficient way to solve complex optimization problems, and sometimes it is the only way to do so. Differential Evolution (DE) is a population-based heuristic search suitable mostly for continuous optimization problems. The efficiency of DE to optimize a problem can largely degrade if the right values for its parameters are not chosen. Finding the right values for DE’s parameters is a non-trivial task. Many researchers resort to parameter tuning and self-adaptation mechanisms. Existing methods vary in their performance and design philosophies.

In this thesis, I start by introducing a semantic evolutionary visualization framework to investigate evolutionary dynamics. The different visualizations track the ongoing changes within an evolutionary run by exploring pedigree trees and the fitness landscapes. The visualization alone was not sufficient to shed light on a very high dimensional space. Consequently, I resorted to introducing a new self-adaptive algorithm using Hidden Markov Models (HMMs).

Markov models have been used extensively in the past to analyze convergence of evolutionary optimization methods. I have leveraged this opportunity to introduce a new algorithm that we call DE-HMM, where HMMs is used for real-time learning of evolutionary dynamics to allow for dynamic adjustment of the two intrinsic DE parameters: F and CR.

DE-HMM categorizes each evolutionary transition into two discrete states; low and high, representing the rate of change in a population over time. The HMM posterior and likelihood ratios are estimated to assign the values for F and CR during the evolutionary process. Two unconstrained benchmark set are used to assess DE-HMM performance, demonstrating its overall superiority in terms of solution quality and computational resources, when compared to other state-of-the art algorithms.

The self-adaptive DE-HMM is then augmented with local search to solve constrained optimization problems. A two-stage method is introduced; with the two states being either global or local based on the degree of feasibility and rate of diversity. The methodology demonstrated competitive results when tested on the constrained CEC2010 benchmark dataset.