Combinatorial Multimodal Optimization using Swarm Intelligence

Zain Hassan

Zain Hassan did his Honour’s project at the Associate Professorship of Computational Mechanics (TUM) and
was supervised by Gesche Fender Dipl.-Ing. and Prof. Dr.-Ing. habil. Fabian Duddeck.

For complex systems, multi-fidelity modelling is used to reduce the computational effort required by optimization. For creating a low-fidelity model often some parameters are set to fixed values, which leads to a combinatorial optimization problem. To address the problems of multimodal nature, several candidate solutions can be created. Attaining several good solutions each with some distance in the search space is appreciated in a practical design context. Moreover, this also increases the chances of locating the global optimum. Hence, multimodal optimization is attractive in practical problems. Together this leads to combinatorial multimodal optimization. Although combinatorial optimization and multimodal optimization are not new research fields, the combination of combinatorial and multimodal optimization is relatively novel, especially using swarm intelligence.

Several methods have been described in literature to deal with such optimization problems, of which Genetic Algorithm and Evolutionary Strategies are the most popular. The focus of this project is to explore the methods under the category of swarm intelligence, as an alternative to the other existing methods. A comparison of the performance of several methods for simple combinatorial problems revealed that Particle Swarm Optimization out-performs the other methods and has very good scalability. Hence in this work, the well-known Particle Swarm Optimization (PSO) is extended to target problems of combinatorial and multimodal character.

The optimization problem dealt with here is the minimization of noise level at a point in the cabin of a vehicle calculated using a Patch Transfer Function [1], which is based on experimental data. The design variable is the position of damping patches on a plate which emits the noise. The use of patch transfer function allows the placement of these damping patches only in a regular mesh-like pattern. Every cell in this pattern can either have a damping patch or not, hence the combinatorial nature of the problem.

Fig.1: Block diagram for Species-based Combinatorial Particle Swarm Optimization with Fitness Sharing and Dynamic Inertia Algorithm

A combinatorial version of PSO [2] is extended to address multimodal problems by initializing several sub-warms (species) instead of only one [3], which search the design space simultaneously. The diversity of the sub-swarms is kept by using fitness sharing [4], so that no two sub-swarms explore the same basin. Additionally, the convergence of each sub-swarm is accelerated by use of dynamic inertia [5]. The block diagram of the developed algorithm is shown in Figure 1.

Fig.2: Local optima for the noise level minimization problem using 5 sub-swarms

The developed algorithm, Species-based Combinatorial Particle Swarm Optimization with Fitness Sharing (FS-SCPSO), is first applied to test functions for which the local and global optima are known, such as Rastrigin function and Schwefel function, to measure both unimodal and multimodal performance. In addition to finding local optima, it is able to identify the basin containing the global optimum as well.

The application of the algorithm to the noise level minimization problem, also shows satisfactory performance. Five different local optima found for a plate of size 4*8 are shown in Figure 2. The multimodal performance is measured using Sum of distances (SD) and Sum of distances to nearest neighbor (SDNN) which shows that all 5 designs are diverse. The evolution of the best position found by each particle (pbest) in all sub-swarms over the generations is shown in Figure 3. In most of the runs the algorithm is able to find as many basins as the number of initialized sub-swarms and shows significant improvement in the fitness value.

Fig.3: The evolution of sub-swarms with generations


[1] G. Albert, Christopher; Veronesi, Giorgio; Nijman, Eugène; Rejlek, Jan
Prediction of the vibro-acoustic response of a structure-liner-fluid system based on a patch transfer function approach and direct experimental subsystem characterisation
Applied Acoustics, 112:14-24, 2016.
[2] Jarboui, B.; Cheikh, M.; Siarry, P.; Rebai, A.
Combinatorial Particle Swarm Optimization for partitional clustering problem.
Applied Mathematics and Computation, 192:337-345, 2007.
[3] Li, Xiaodong
Adaptively Choosing Neighbourhood Bests Using Species in a Particle Swarm Optimizer for Multimodal Function Optimization
Genetic and Evolution Computation Conference, LNCS 3102:105-116, 2004.
[4] Li, Tao; Wei, Chengjian; Pei, Wenjang
PSO with sharing for Multimodal function optimization
IEEE International Conference in Neural Networks and Signal Processing, 2003.
[4] Jiao, Bin; Lian, Zhigang; Gu, Xingsheng
A Dynamic Inertia weight particle swarm optimization algorithm
Chaos, Solitons and Fractals, 37:698-705, 2008.