View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0024979 | Open CASCADE | OCCT:Modeling Algorithms | public | 2014-05-30 18:20 | 2014-11-11 12:53 |
| Reporter | Assigned To | bugmaster | |||
| Priority | normal | Severity | minor | ||
| Status | closed | Resolution | fixed | ||
| Target Version | 6.8.0 | Fixed in Version | 6.8.0 | ||
| Summary | 0024979: Optimize Extrema_GenExtCS | ||||
| Description | Revise 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 | ||||
| Tags | No tags attached. | ||||
| Test case number | Not needed | ||||
|
|
Dear abv, please review the patch. |
|
|
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? |
|
|
Dear abv, please review the patch in branch CR24979. |
|
|
No remarks, please test |
|
|
I think, it would be nice to implement separate Hooke-Jeeves optimization algo and add it in math package |
|
|
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. |
|
|
Dear abv, please review the patch in branch CR24979_5. |
|
|
Reviewed, please test |
|
|
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 |
|
|
Branch CR24979_6 has been created by dbp. SHA-1: ba472dedb63b0d33ec40c86159ebad72c3e1261a |
|
|
Dear abv, Compilation warnings were fixed. Please review re-based patch in branch CR24979_6. |
|
|
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 |
|
|
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 |
|
|
Branch CR24979_6 has been updated by mkv. SHA-1: 8cc49e1d7233e5b3eba9ffc865b25b78962f13c8 |
|
|
Branch CR24979 has been deleted by inv. SHA-1: 101c647cf9c210cf07637e7de7f8de5d0ea0f400 |
|
|
Branch CR24979_1 has been deleted by inv. SHA-1: 167d9232d8b14d4b24cbc50f32d3e20000000cc8 |
|
|
Branch CR24979_2 has been deleted by inv. SHA-1: c216ddc0ea97ee186255fe285f75a52bad43e8ab |
|
|
Branch CR24979_3 has been deleted by inv. SHA-1: f2ffe568f3fe96c8dc10210497035a0d111cb6f0 |
|
|
Branch CR24979_5 has been deleted by inv. SHA-1: 0e7b9c9014e8819c6f8918098026bb0623720e96 |
|
|
Branch CR24979_6 has been deleted by inv. SHA-1: 8cc49e1d7233e5b3eba9ffc865b25b78962f13c8 |
|
occt: master 113493b0 2014-07-15 08:11:24
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. |
Affected Issues 0024979 |
|
| mod - src/Extrema/Extrema_GenExtCS.cdl | Diff File | ||
| mod - src/Extrema/Extrema_GenExtCS.cxx | Diff File | ||
| mod - tests/bugs/moddata_3/bug23995 | Diff File | ||
| Date Modified | Username | Field | Change |
|---|---|---|---|
| 2014-05-30 18:20 |
|
New Issue | |
| 2014-05-30 18:20 |
|
Assigned To | => dbp |
| 2014-06-02 15:46 |
|
Note Added: 0029632 | |
| 2014-06-02 15:46 |
|
Assigned To | dbp => abv |
| 2014-06-02 15:46 |
|
Status | new => feedback |
| 2014-06-02 15:56 |
|
Additional Information Updated | |
| 2014-06-03 08:22 |
|
Note Added: 0029640 | |
| 2014-06-03 08:22 |
|
Assigned To | abv => dbp |
| 2014-06-03 08:22 |
|
Status | feedback => assigned |
| 2014-06-11 00:32 |
|
Note Added: 0029765 | |
| 2014-06-11 00:32 |
|
Assigned To | dbp => abv |
| 2014-06-11 00:32 |
|
Status | assigned => resolved |
| 2014-06-16 13:18 |
|
Relationship added | related to 0024832 |
| 2014-06-16 13:19 |
|
Note Added: 0029781 | |
| 2014-06-16 13:19 |
|
Assigned To | abv => bugmaster |
| 2014-06-16 13:19 |
|
Status | resolved => reviewed |
| 2014-06-16 13:29 |
|
Note Added: 0029782 | |
| 2014-06-16 18:07 |
|
Assigned To | bugmaster => mkv |
| 2014-06-18 10:52 |
|
Note Added: 0029806 | |
| 2014-06-18 10:53 |
|
Test case number | => Not needed |
| 2014-06-18 10:53 |
|
Assigned To | mkv => dbp |
| 2014-06-18 10:53 |
|
Status | reviewed => assigned |
| 2014-07-11 15:39 |
|
Note Added: 0030082 | |
| 2014-07-11 15:39 |
|
Assigned To | dbp => abv |
| 2014-07-11 15:39 |
|
Status | assigned => feedback |
| 2014-07-11 15:40 |
|
Additional Information Updated | |
| 2014-07-11 16:43 | kgv | Target Version | => 6.8.0 |
| 2014-07-11 18:00 |
|
Description Updated | |
| 2014-07-11 18:36 |
|
Note Added: 0030092 | |
| 2014-07-11 18:36 |
|
Assigned To | abv => bugmaster |
| 2014-07-11 18:36 |
|
Status | feedback => reviewed |
| 2014-07-11 19:37 |
|
Assigned To | bugmaster => mkv |
| 2014-07-14 20:46 |
|
Note Added: 0030145 | |
| 2014-07-14 20:47 |
|
Assigned To | mkv => dbp |
| 2014-07-14 20:47 |
|
Status | reviewed => assigned |
| 2014-07-15 12:11 | git | Note Added: 0030155 | |
| 2014-07-15 12:15 |
|
Note Added: 0030156 | |
| 2014-07-15 12:15 |
|
Assigned To | dbp => abv |
| 2014-07-15 12:15 |
|
Status | assigned => resolved |
| 2014-07-16 09:27 |
|
Note Added: 0030178 | |
| 2014-07-16 09:27 |
|
Assigned To | abv => bugmaster |
| 2014-07-16 09:27 |
|
Status | resolved => reviewed |
| 2014-07-16 09:53 |
|
Relationship added | related to 0025086 |
| 2014-07-17 12:32 |
|
Note Added: 0030222 | |
| 2014-07-17 12:32 | git | Note Added: 0030223 | |
| 2014-07-17 12:33 |
|
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 |
|
Fixed in Version | => 6.8.0 |
| 2014-11-11 12:53 |
|
Status | verified => closed |
