Evolutionary Algorithms for high-quality solutions

It is not uncommon that the solution obtained by an algorithm is not as desired. To overcome this, Stef Maree's PhD research focuses on optimization algorithms for finding not just one solution, but a set of diverse high-quality solutions.

Publication date: 09-03-2021

Our society increasingly relies on algorithms to solve high-impact optimization problems. In practice, it can be difficult to capture all desirable aspects of a solution into a quantitative objective function, however. It is thus not uncommon that the solution obtained by an algorithm is not as desired. To overcome this, Stef Maree focuses in on optimization algorithms for finding not one solution, but a set of diverse high-quality solutions in his thesis. Providing decision makers with multiple high-quality candidate solutions gives them unique insights in the problem and helps them to select the most desirable solution.

Finding multiple high-quality solutions

Real world optimization problems are often fairly complex. To be able to solve these problems, evolutionary algorithms can be employed. These heuristic search algorithms can be applied without assuming any problem specific knowledge, but there are typically no guarantees of finding the optimal solution. In practice it is often more important to obtain a high-quality solution fast  than to obtain a solution that is (provably) optimal. To perform efficient optimization, model-based evolutionary algorithms exploit problem features through learnable models. These algorithms are naturally well-suited for the task of finding multiple high-quality solutions, as they already maintain a population of multiple solutions to guide the search process. What remains is to promote a form of diversity within this population during optimization. Maree achieves this in his thesis via two different approaches: multi-objective optimization, and multimodal optimization.

Multimodal optimization

The aim of multimodal optimization is to obtain all global optima of an optimization problem. This is typically achieved by exploring multiple modes, that is, the high-fitness regions in the search space, hence the name multimodal optimization. Maree developed a new algorithm to perform efficient and effective multimodal optimization, called the Hil-Valley Evolutionary Algorithm (HillVallEA). This algorithm is based on the simple idea that two points belong to a different mode (hill) when there is valley in between. With this algorithm, Maree won the multimodal optimization competition held at the annual Genetic and Evolutionary Computation Conference twice.

Multi-objective optimization of prostate cancer treatments

Maree applies model-based evolutionary algorithms to an optimization problem that arises in the treatment of prostate cancer with high-dose-rate brachytherapy. Brachytherapy is a form of internal radiation therapy, in which a high dose of radiation is used to kill tumor cells. In doing so, radiation dose to nearby healthy tissue can not be avoided however. During the planning of the treatment it is determined how the radiation dose should be delivered such that the tumor is irradiated as much as possible, while surrounding tissue is spared as much as possible. These conflicting aims make treatment planning a multi-objective optimization problem. It is unknown beforehand how these trade-offs should manifest in a desired treatment for a patient. To overcome having to return optimization in order to obtain a desirable solution, multi-objective optimization algorithms can be employed. These algorithms aim to obtain a set solutions, that all have a different trade-off in the objectives. When using only two objectives, this set of solutions can be visualized as a trade-off curve, which can be used by physicians as an insightful tool for selecting the most desirable treatment plan.

In his thesis, Maree validates a novel treatment planning approach, in which a model-based evolutionary algorithm is used to optimize a bi-objective problem formulation. He shows that this approach results in better treatment plans than can be obtained by automatically tuning current established treatment planning methods. Additionally, and even more importantly, Maree shows in an observer study among experienced physicians that plans obtained via this bi-objective approach are retrospectively even preferred over the clinically-used plan in 98% of the cases. The physicians furthermore highly appreciate the possibility to compare high-quality plans with diverse trade-offs and consider the results to be insightful.

A direct impact of Maree’s work is the clinical use of this bi-objective method in the Amsterdam UMC, where it is referred to as “BRachytherapy via artificially Intelligent GOMEA Heuristic based Treatment planning” (BRIGHT). As of spring 2020, prostate cancer patients treated with HDR brachytherapy are treated with plans based on BRIGHT.

PhD defense

Maree defends his thesis at the University of Amsterdam 17 March 2021. His research was supervised by CWI/TU Delft researcher prof. Peter Bosman; prof. Coen Rasch, professor of radiotherapy at the University of Amsterdam; Dr. Tanja Alderliesten, associate professor at Leiden UMC; and dr. A. Bel, head of radiotherapy physics at Amsterdam UMC.

Everyone is welcome to attend the online defense of Stef Maree of his thesis “Model-based evolutionary algorithms for finding diverse high-quality solutions”, which will take place on Wednesday March 17 at 14.00. A live stream for this ceremony will be made available here.