Thu, 08/28/2014  10:16
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 realworld 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 [13].
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 pseudorandom 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 noneven 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:
 Kennedy J.; Eberhart R. "Particle Swarm Optimization". Proceedings of IEEE International Conference on Neural Networks IV. pp. 1942вЂ“1948 (1995)
 Ismael A., Vaz F., Vicente L. N. "A particle swarm pattern search method for bound constrained global optimization"
 HsinChuan Kuo, JiangRen Chang, and ChingHsiang Liu "PARTICLE SWARM OPTIMIZATION FOR GLOBAL OPTIMIZATION PROBLEMS". Journal of Marine Science and Technology, Vol. 14, No. 3. pp. 170181 (2006)
 Richard M., Ventura D. вЂњChoosing a Starting Configuration for Particle Swarm OptimizationвЂќ
Thu, 08/28/2014  14:23
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 hardwareenabled 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
Mon, 09/01/2014  13:58
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 MKLbased 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 PSObased implementation tested enough.
BR,
Alexander
Mon, 09/01/2014  16:17
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 noneven 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
Thu, 09/04/2014  11:12
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 casebycase 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
Thu, 09/04/2014  12:44
I have a problematic case for BRepOffsetAPI_MakeFilling with nonuniform parameterization and nonorthogonal U,V coordinate lines of the surface. In my post, I wrongly identified nonuniform parametrization and nonorthogonality but they are different things. As I heard from OCCT support, nonorthogonality can't be fixed by scaling. So, probably it's not worth mentioning this case here because the main problem seems to be nonorthogonality.
Regards