Subpopulation Algorithm based on Novelty

Subpopulation Algorithm based on Novelty (SAN) is a multi-objective algorithm created using the General Subpopulation Framework. This algorithm was developed by Danilo Vasconcellos Vargas et al based on the idea that multi-objective search can be broken down into a single objective search for each objective plus novelty search in objective space (searching for solutions to compose the Pareto front).
Overview
The algorithm is basically made of <math>n+1</math> subpopulations where <math>n</math> is the number of objectives. Each of the <math>n</math> subpopulations are made of single-objective Differential evolution algorithms (although in principle it could be any other single objective algorithm) with the <math>n+1</math> subpopulation being a novelty based population. This novelty based population is built by sampling uniformly from an archive of novel individuals. To build this archive, every generated individual is tested against a novel threshold, if it surpasses the threshold it is inserted in the archive and the threshold increases (becoming difficult to insert another individual), otherwise the individual is not inserted and the threshold decreases (becoming easier to insert another individual).
Results
There are results in both 2 objectives and 5 objectives versions of the WFG Toolkit.
SAN surpassed GDE3 on the most difficult problems of the WFG Toolkit with 2 objectives. Recall that NSGAII, which was originally used in WFG Toolkit's original paper, can barely arrive at the Pareto front in some of these problems. Therefore, GDE3 is shown to behave better than NSGAII while SAN surpasses both on the most difficult problems (problems with bias and difficult Pareto fronts) as well as have similar performance on easier problems.
Regarding 5 objectives, SAN gets even better. All quality indicators used show that SAN is without doubt many times better than GDE3 in all problems when the number of objectives grows in size.
Analysis
It was shown by using the concept of Optimization Forces that without a division into subpopulations, usual multi-objective methods have a deleterious competition inside populations. This happens because populations usually have many conflicting forces inside, e.g., (1) a population want to have diverse individuals (good covering of the Pareto front) while (2) it also wants to be full of nondominated individuals (closer to the Pareto front). (1) and (2) are conflicting forces which have different degrees of difficulty depending on the problem. Consequently, even if forces (1) and (2) are well balanced inside an algorithm, depending on the problem if whichever of these forces are easier to achieve it will become more predominant. This predominance of some forces over others is unavoidable unless a clear division in subpopulations is done (see General Subpopulation Framework).
Code
The code is available inside the zweifel library.

Main Menu

See Also

Main Menu