Application of stohastic algorithms in extrema

aml's picture

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.

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”
Roman Lygin's picture

questions

Folks,

This sounds very interesting. Congrats on exploring new approach.
Immediate questions off the top of my head.
1. Correctness. The data in the table did not say anything how good, in terms of correctness, the algorithm is. Can you elaborate on that please ?
2. Determinism. Understand it had to be sacrificed in favor of performance and ability to handle some corner cases. However is the solution always within some proximity of a known one ? For instance, how do you test that the result is correctly returned if it may change from run to run ?
3. RND. If interested, you might want to have a look at Intel MKL - there are a few different generators, including scalable and hardware-enabled ones.
4. What will be the way to enable this algorithm from higher level API - say to project a curve on a surface or a point on a surface ? Is there an API way to roll back to previous algorithm (just as a safe bet until the new algorithm gets mature or for any other reason) ?

Again, congratulations!
Roman

aml's picture

Answer

Hello Roman,

1) All OCCT tests are passed including represented "table tests". Number of tests affected by new approach is more than two hundreds.
2) Results can be reproduced due to fixed seed in random number generator.
3) This sounds good. I'll investigate MKL-based generators.
4) Porting new algorithms to PSO approach is easy, you need to describe function (in Extrema curve/surface this function describe distance between point on curve and point on surface), as child of math_MultipleVarFunction and invoke PSO. There is no API to revert to previous algorithm because PSO-based implementation tested enough.

BR,
Alexander

Timo's picture

Can PSO be used to improve BRepOffsetAPI_MakeFilling?

Just wanted to mention an idea:
Couly PSO be used to improve BRepOffsetAPI_MakeFilling?

More specifically, I thought whether the possible improvement mentioned in the end of the article could also be helpful for BRepOffsetAPI_MakeFilling to enable the algorithm to work with heterogeneously parameterized initial surfaces. Currently, the algorithm assumes that the initial surface is homogeneously parameterized, i.e. it has orthogonal local coordinates.

Here is a quote of the part I meant from the article:
“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.”

There might also be other ways in which BRepOffsetAPI_MakeFilling could benefit from PSO.

Kind regards,
Timo

abv's picture

MakeFilling can likely be improved, but PSO is not related

Hello Timo,

Thank you for your suggestion! I deem that BRepOffsetAPI_MakeFilling, just as many other algorithms, can be improved by better handling of unevenly parametrized geometries. This is common problem, and we shall think of how to improve many algorithms in this regard. However, this will likely be done on case-by-case basis.

In any case, for this kind of improvements it is essential to have test cases, thus if you have some issues related to application of BRepOffsetAPI_MakeFilling of heterogeneously parameterized surfaces, I encourage you to report these issues and list them here so that they can be easily found when needed.

Andrey

Timo's picture

Non-uniform parametrization and non-orthogonality

I have a problematic case for BRepOffsetAPI_MakeFilling with non-uniform parameterization and non-orthogonal U,V coordinate lines of the surface. In my post, I wrongly identified non-uniform parametrization and non-orthogonality but they are different things. As I heard from OCCT support, non-orthogonality can't be fixed by scaling. So, probably it's not worth mentioning this case here because the main problem seems to be non-orthogonality.

Regards

www.opencascade.com

Copyright 2011-2016
OPEN CASCADE SAS
Contact us