Application of stohastic algorithms in extrema

Starting from version 6.8.0 OCCT will include one more algorithm for solving global optimization problems.

Its development has been triggered by insufficient performance and robustness of the existing algorithm of minimization of curve - surface distance in Extrema package (class Extrema_GenExtCS). Recent attempts to fix problems in that algorithm led to severe reduction of its performance, hence the need of a different approach raised.

break

After some (unsuccessful) experiments with deterministic algorithms, the approach based on Particle Swarm Optimization (PSO) idea [1] has been taken. Algorithms in this family are stochastic, and this feature can be perceived as opposite to robustness. However, we found it was not only much faster than original deterministic one, but also more robust in complex real-world situations. In particular, it has been able to find solution in situations like tangential or degenerated geometries where deterministic algorithms work poor and require extensive oversampling for robust results.

The PSO algorithm has originated as a simulation of a simplified social system with swarm intelligence and having exploring and exploiting characteristics of the particle, adapted to deal with the global optimization problems. The main its advantages are: fast convergence, natural ability to handle simple constraints, good detection of global optimum. Details of the algorithm can be found in the papers [1-3].

Here we give a brief description of the approach, as used in Extrema_GenExtCS:

• At start of computation a number of “particles” are placed in the search space. For the curve - surface extrema, particle is a pair of points: one on curve, another on the surface, defined by their parameters. Currently we take 32 best particles found on the initial grid of seed points put on the curve and surface (this part of the previous algorithm is thus reused, with additional caching of these points for better performance).
• Each particle is assigned a random velocity (discussions on strategies of choice of initial particles position and their count can be found in [4]).
• The particles are moved in cycle, simulating some “social” behavior, so that new position of a particle on each step depends not only on its velocity and previous path, but also on the position of the best particle in the pool. The velocity of the particles is decreased on each step, so that convergence is guaranteed. For the implemented version of the algorithm some kind of convergence to equilibrium is proved, as well as impossibility of oscillations for particles pool.
• Final solution is refined by local optimization (Newton search, just like in previous implementation).

 

The stochastic features of the PSO algorithm are restricted to ensure reproducibility of the results by usage of fixed seed in random number generator.

The following table shows total time and number of evaluations of the distance functional by the old and new algorithm, on a selected subset of test cases

Test	Old algorithm		New algorithm PSO
	Time, sec.	Function evaluations count	Time, sec	Function evaluations count
bugs moddata_2 bug26_1	28.72	66 445 034	5.66	8 775 484
bugs moddata_2 bug26_2	28.87	66 445 034	5.70	8 776 252
bugs moddata_2 bug496	9.01	12 097 826	2.90	1 873 011
bugs modalg_5 bug23853_1	8.26	11 975 926	3.12	2 431 302
bugs modalg_5 bug23884	29.06	2 308 021	18.50	238 617

Note that number of evaluations of the function by PSO algorithm is by the order of magnitude less than by the old algorithm. The effect on performance is visible even on the total time of execution of all tests, which was reduced by 10% after integration of this fix.

Algorithm	Total time, sec.
	Linux	Windows
Old	54 469	38 730
New (PSO)	46 291	34 971
Gain	15%	10%

The PSO algorithm itself is implemented separately from Extrema package so that it can be reused in other places (see class math_PSO).

To conclude, the advantages and disadvantages of the PSO algorithm are:

Advantages:

• One of the fastest algorithms.
• Work over functions with a lot local extremums.
• Does not require calculation of derivatives of the functional.
• Easy to implement and modify.

 

Disadvantages:

• Convergence to global minimum not proved, which is a typical drawback for all stochastic algorithms.
• The result depends on random number generator. For the moment we use simple and fast pseudo-random number generator algorithm implemented ad hoc.

 

Even if good result is achieved, there are possibilities for further improvements. First of all, distribution of initial grid of points can be improved on surfaces and curves with non-even parameterization, to have points distributed more evenly. Then, parametric space can be scaled so as to be more uniform. If this improves convergence of the algorithm on complex cases (as we hope), it will further allow reducing number of particles used. Also, we can try different implementations of random numbers generator.

References:

1. Kennedy J.; Eberhart R. "Particle Swarm Optimization". Proceedings of IEEE International Conference on Neural Networks IV. pp. 1942–1948 (1995)
2. Ismael A., Vaz F., Vicente L. N. "A particle swarm pattern search method for bound constrained global optimization"
3. Hsin-Chuan Kuo, Jiang-Ren Chang, and Ching-Hsiang Liu "PARTICLE SWARM OPTIMIZATION FOR GLOBAL OPTIMIZATION PROBLEMS". Journal of Marine Science and Technology, Vol. 14, No. 3. pp. 170-181 (2006)
4. Richard M., Ventura D. “Choosing a Starting Configuration for Particle Swarm Optimization”