MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Related Changesets ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0024979Open CASCADE[OCCT] OCCT:Modeling Algorithmspublic2014-05-30 18:202014-11-11 12:53
Reporterdbp 
Assigned Tobugmaster 
PrioritynormalSeverityminor 
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version 
Target Version[OCCT] 6.8.0Fixed in Version[OCCT] 6.8.0 
Summary0024979: Optimize Extrema_GenExtCS
DescriptionRevise grid generation approach used in Perform() method.

The main problem of the previous implementation was related to the convergence of Newton algorithm: slightly incorrect initial approximation leads to divergence or convergence to local minima. This problem has been solved by increasing resolution of sample grid (after each divergence of Newton algorithm). In many cases this leads to costly calculations.

The new approach is an attempt to improve the selection of the initial approximation. This was done using new global optimization method -- particle swarm optimization (PSO). This algorithm is originated as a simulation of a simplified social system with swarm intelligence and having exploring and exploiting characteristics of the particle swarm, is adopted to deal with the global optimization problems. The main advantages are: fast convergence, natural ability to handle simple constraints, good detection of global optima. Please check these papers for more details (there are many others):

Gonzalo NĂ¡poles, Isel Grau, and Rafael Bello
"Constricted Particle Swarm Optimization based Algorithm for Global Optimization"
http://polibits.gelbukh.com/2012_46/Constricted%20Particle%20Swarm%20Optimization%20based%20Algorithm%20for%20Global%20Optimization.pdf [^]

A. Ismael F. Vaz, L. N. Vicente
"A particle swarm pattern search method for bound constrained global optimization"
http://www.mat.uc.pt/~lnv/papers/PSwarm.pdf [^]

Hsin-Chuan Kuo, Jiang-Ren Chang, and Ching-Hsiang Liu
"PARTICLE SWARM OPTIMIZATION FOR GLOBAL OPTIMIZATION PROBLEMS"
http://jmst.ntou.edu.tw/marine/14-3/170-181.pdf [^]

K. E. Parsopoulos and M. N. Vrahatis. 2002. Recent approaches to global optimization problems through Particle Swarm Optimization. 1, 2-3 (June 2002), 235-306.

Simple description from Wikipedia:
Particle swarm optimization
http://en.wikipedia.org/wiki/Particle_swarm_optimization [^]

TagsNo tags attached.
Test case numberNot needed
Attached Files

- Relationships
related to 0024832closedapn Community Performance of new boolean operations has become worse 
related to 0025086closedbugmaster Open CASCADE Implementation PSO in package math 

-  Notes
(0029632)
dbp (developer)
2014-06-02 15:46

Dear abv,

please review the patch.
(0029640)
abv (manager)
2014-06-03 08:22

Please consider a few stylistic remarks:

- put struct Extrema_BasisPoint to anonymous namespace
- use *4 instead of <<2 as the latter will be confusing for most people
- there is no sense in having global variable DEFAULT_POINT; local variable can be used instead with no loss of performance
- method Init() of Array can be used instead of std::fill(); this is not necessary actually because Extrema_BasisPoint has default constructor and all elements of the array are initialized by the time of allocation
- to improve performance (if useful), aTestPnts can be allocated in stack -- either as plain C array or as NCollection_Array1 with C array buffer
- number of candidate points, 3, deserves to be declared as named constant; the same applies to other arbitrary constants like 4 in <<2, 5 in %5, 256, etc.
- please be consistent in iterating by arrays (e.g. aTestPnts) -- either use STL iterators or (standard for OCCT) iteration by index
- static_cast<Standard_Real> is not needed, as variable being divided is double
- there are three very similar code blocks of the kind "if (aPartSU < 256) {...}" -- should not they be made (inline) function?
(0029765)
dbp (developer)
2014-06-11 00:32

Dear abv,

please review the patch in branch CR24979.
(0029781)
abv (manager)
2014-06-16 13:19

No remarks, please test
(0029782)
ifv (developer)
2014-06-16 13:29

I think, it would be nice to implement separate Hooke-Jeeves optimization algo and add it in math package
(0029806)
mkv (tester)
2014-06-18 10:52

Dear BugMaster,

Branch CR24979 (and products from GIT master) was compiled on Linux, MacOS and Windows platforms and tested.
SHA-1: cb0c4204ddec3dd3e92496844457a2a0fccbf534

Number of compiler warnings:

occt component :
Linux: 16 (16 on master)
Windows: 0 (0 on master)
MacOS: 200 (203 on master)

products component :
Linux: 11 (11 on master)
Windows: 2 (2 on master)

Regressions/Differences:
http://occt-tests/CR24979-master-occt/Debian60-64/summary.html [^]
http://occt-tests/CR24979-master-occt/Windows-32-VC9/summary.html [^]
Improvements:
  bugs modalg_1(006) buc60462_2
  bugs modalg_4(009) pro19653
Failed:
  boolean bcut_complex(012) O8
  bugs modalg_1(006) bug10160_5, bug10160_7
  bugs modalg_5(010) bug24766
  bugs moddata_3(013) bug23995

Testing cases:
Not needed

Testing on Linux:
Total MEMORY difference: 348231928 / 348749440
Total CPU difference: 47586.25999999984 / 52691.36000000003

Testing on Windows:
Total MEMORY difference: 376093608 / 376723116
Total CPU difference: 38982.6875 / 42235.234375

There are no differences in images found by testdiff.
(0030082)
dbp (developer)
2014-07-11 15:39

Dear abv,

please review the patch in branch CR24979_5.
(0030092)
abv (manager)
2014-07-11 18:36

Reviewed, please test
(0030145)
mkv (tester)
2014-07-14 20:46

Dear BugMaster,

Branch CR24979_5 from occt git-repository (and master from products git-repository) was compiled on Linux and Windows platforms and tested.
SHA-1: 0e7b9c9014e8819c6f8918098026bb0623720e96

Number of compiler warnings:

occt component :
Linux: 15 (15 on master)
Windows: 8 (0 on master)

There are new additional compilation warnings on Windows platform:
http://jenkins-test-02.nnov.opencascade.com:8080/user/mnt/my-views/view/A_mnt_warnings/job/mnt-CR24979_5-master_build_occt_windows/1/warnings30Result/package.892074798/ [^]

Extrema_GenExtCS.cxx:409, MSBuild, Priority: Normal
'initializing' : conversion from 'Standard_Real' to 'const Standard_ShortReal', possible loss of data
Extrema_GenExtCS.cxx:410, MSBuild, Priority: Normal
'initializing' : conversion from 'Standard_Real' to 'const Standard_ShortReal', possible loss of data
Extrema_GenExtCS.cxx:411, MSBuild, Priority: Normal
'initializing' : conversion from 'Standard_Real' to 'const Standard_ShortReal', possible loss of data
Extrema_GenExtCS.cxx:434, MSBuild, Priority: Normal
'initializing' : conversion from 'Standard_Real' to 'const Standard_ShortReal', possible loss of data
Extrema_GenExtCS.cxx:435, MSBuild, Priority: Normal
'initializing' : conversion from 'Standard_Real' to 'const Standard_ShortReal', possible loss of data
Extrema_GenExtCS.cxx:487, MSBuild, Priority: Normal
'initializing' : conversion from 'Standard_Real' to 'const Standard_ShortReal', possible loss of data
Extrema_GenExtCS.cxx:488, MSBuild, Priority: Normal
'initializing' : conversion from 'Standard_Real' to 'const Standard_ShortReal', possible loss of data
Extrema_GenExtCS.cxx:489, MSBuild, Priority: Normal
'initializing' : conversion from 'Standard_Real' to 'const Standard_ShortReal', possible loss of data

products component :
Linux: 11 (11 on master)
Windows: 2 (2 on master)

Regressions/Differences:
http://occt-tests/CR24979-5-master-occt/Debian60-64/summary.html [^]
http://occt-tests/CR24979-5-master-occt/Windows-32-VC9/summary.html [^]
Improvements:
bugs modalg_1(006) buc60462_2
bugs modalg_4(009) pro19653

Testing cases:
Not needed

Testing on Linux:
Total MEMORY difference: 352041948 / 352116884
Total CPU difference: 55858.49999999989 / 54361.94999999987

Testing on Windows:
Total MEMORY difference: 378110964 / 378442136
Total CPU difference: 36915.984375 / 46737.046875

There are following differences in images found by testdiff:
http://occt-tests/CR24979-5-master-occt/Debian60-64/diff-Debian60-64.html [^]
http://occt-tests/CR24979-5-master-occt/Windows-32-VC9/diff-Windows-32-VC9.html [^]
IMAGE bugs moddata_3 bug23995: bug23995.png differs
(0030155)
git (administrator)
2014-07-15 12:11

Branch CR24979_6 has been created by dbp.

SHA-1: ba472dedb63b0d33ec40c86159ebad72c3e1261a
(0030156)
dbp (developer)
2014-07-15 12:15

Dear abv,

Compilation warnings were fixed. Please review re-based patch in branch CR24979_6.
(0030178)
abv (manager)
2014-07-16 09:27

No remarks, please check compilation and consider integration. No new testing is needed; if previous tests should be analyzed, please provide logs, as the links given in the test report are broken
(0030222)
mkv (tester)
2014-07-17 12:32

Dear BugMaster,

Branch CR24979_6 from occt git-repository (and master from products git-repository) was compiled on Linux and Windows platforms and tested.
SHA-1: ba472dedb63b0d33ec40c86159ebad72c3e1261a

Number of compiler warnings:

occt component :
Linux: 15 (15 on master)
Windows: 0 (0 on master)

products component :
Linux: 11 (11 on master)
Windows: 2 (2 on master)

Regressions/Differences:

Are modified, now its are OK:
bugs modalg_1(006) buc60462_2
bugs modalg_4(009) pro19653

Testing cases:
Not needed
(0030223)
git (administrator)
2014-07-17 12:32

Branch CR24979_6 has been updated by mkv.

SHA-1: 8cc49e1d7233e5b3eba9ffc865b25b78962f13c8
(0030301)
git (administrator)
2014-07-22 15:52

Branch CR24979 has been deleted by inv.

SHA-1: 101c647cf9c210cf07637e7de7f8de5d0ea0f400
(0030302)
git (administrator)
2014-07-22 15:52

Branch CR24979_1 has been deleted by inv.

SHA-1: 167d9232d8b14d4b24cbc50f32d3e20000000cc8
(0030303)
git (administrator)
2014-07-22 15:52

Branch CR24979_2 has been deleted by inv.

SHA-1: c216ddc0ea97ee186255fe285f75a52bad43e8ab
(0030304)
git (administrator)
2014-07-22 15:52

Branch CR24979_3 has been deleted by inv.

SHA-1: f2ffe568f3fe96c8dc10210497035a0d111cb6f0
(0030305)
git (administrator)
2014-07-22 15:52

Branch CR24979_5 has been deleted by inv.

SHA-1: 0e7b9c9014e8819c6f8918098026bb0623720e96
(0030306)
git (administrator)
2014-07-22 15:52

Branch CR24979_6 has been deleted by inv.

SHA-1: 8cc49e1d7233e5b3eba9ffc865b25b78962f13c8

- Related Changesets
occt: master 113493b0
Timestamp: 2014-07-15 08:11:24
Author: dbp
Committer: bugmaster
Details ] Diff ]
0024979: Optimize Extrema_GenExtCS

The patch changes the algorithm of choosing the initial approximation for Newton's method. Instead of searching for a point on the fine shifted grid, the algorithm performs initial search for candidate points in the original coarse grid (which is cached in new version). After that particle swarm optimization (PSO) is used to localize the global minimum. This algorithm optimizes a problem by having a population of candidate solutions ("particles"), and moving these particles around in the search-space according to simple mathematical formula over the particle's position and velocity. Each particle's movement is influenced by its local best known position but, is also guided toward the best known positions in the search-space, which are updated as better positions are found by other particles. This strategy has reported good results in solving complex global optimization problems.

Current patch implements initial version of PSO for using in Extrema_GenExtCS class. Typically new approach allows to reduce the number of evaluations by 5-10 times. There are only few cases there the numbers of evaluations are comparable.
mod - src/Extrema/Extrema_GenExtCS.cdl Diff ] File ]
mod - src/Extrema/Extrema_GenExtCS.cxx Diff ] File ]
mod - tests/bugs/moddata_3/bug23995 Diff ] File ]

- Issue History
Date Modified Username Field Change
2014-05-30 18:20 dbp New Issue
2014-05-30 18:20 dbp Assigned To => dbp
2014-06-02 15:46 dbp Note Added: 0029632
2014-06-02 15:46 dbp Assigned To dbp => abv
2014-06-02 15:46 dbp Status new => feedback
2014-06-02 15:56 dbp Additional Information Updated View Revisions
2014-06-03 08:22 abv Note Added: 0029640
2014-06-03 08:22 abv Assigned To abv => dbp
2014-06-03 08:22 abv Status feedback => assigned
2014-06-11 00:32 dbp Note Added: 0029765
2014-06-11 00:32 dbp Assigned To dbp => abv
2014-06-11 00:32 dbp Status assigned => resolved
2014-06-16 13:12 abv Relationship added related to 0024896
2014-06-16 13:13 abv Relationship added related to 0023830
2014-06-16 13:18 abv Relationship added related to 0024832
2014-06-16 13:19 abv Note Added: 0029781
2014-06-16 13:19 abv Assigned To abv => bugmaster
2014-06-16 13:19 abv Status resolved => reviewed
2014-06-16 13:29 ifv Note Added: 0029782
2014-06-16 18:07 mkv Assigned To bugmaster => mkv
2014-06-18 10:52 mkv Note Added: 0029806
2014-06-18 10:53 mkv Test case number => Not needed
2014-06-18 10:53 mkv Assigned To mkv => dbp
2014-06-18 10:53 mkv Status reviewed => assigned
2014-07-11 15:39 dbp Note Added: 0030082
2014-07-11 15:39 dbp Assigned To dbp => abv
2014-07-11 15:39 dbp Status assigned => feedback
2014-07-11 15:40 dbp Additional Information Updated View Revisions
2014-07-11 16:43 kgv Target Version => 6.8.0
2014-07-11 18:00 dbp Description Updated View Revisions
2014-07-11 18:36 abv Note Added: 0030092
2014-07-11 18:36 abv Assigned To abv => bugmaster
2014-07-11 18:36 abv Status feedback => reviewed
2014-07-11 19:37 mkv Assigned To bugmaster => mkv
2014-07-14 20:46 mkv Note Added: 0030145
2014-07-14 20:47 mkv Assigned To mkv => dbp
2014-07-14 20:47 mkv Status reviewed => assigned
2014-07-15 12:11 git Note Added: 0030155
2014-07-15 12:15 dbp Note Added: 0030156
2014-07-15 12:15 dbp Assigned To dbp => abv
2014-07-15 12:15 dbp Status assigned => resolved
2014-07-16 09:27 abv Note Added: 0030178
2014-07-16 09:27 abv Assigned To abv => bugmaster
2014-07-16 09:27 abv Status resolved => reviewed
2014-07-16 09:53 abv Relationship added related to 0025086
2014-07-17 12:32 mkv Note Added: 0030222
2014-07-17 12:32 git Note Added: 0030223
2014-07-17 12:33 mkv Status reviewed => tested
2014-07-22 15:13 bugmaster Changeset attached => occt master 113493b0
2014-07-22 15:13 bugmaster Status tested => verified
2014-07-22 15:13 bugmaster Resolution open => fixed
2014-07-22 15:52 git Note Added: 0030301
2014-07-22 15:52 git Note Added: 0030302
2014-07-22 15:52 git Note Added: 0030303
2014-07-22 15:52 git Note Added: 0030304
2014-07-22 15:52 git Note Added: 0030305
2014-07-22 15:52 git Note Added: 0030306
2014-11-11 12:46 aiv Fixed in Version => 6.8.0
2014-11-11 12:53 aiv Status verified => closed


Copyright © 2000 - 2020 MantisBT Team
Powered by Mantis Bugtracker