An Integrated Framework for the Realtime Investigation of State Space Exploration

Authors: Jörg Lassig, Stefanie Thiem

Abstract:

The objective of this paper is the introduction to a unified optimization framework for research and education. The OPTILIB framework implements different general purpose algorithms for combinatorial optimization and minimum search on standard continuous test functions. The preferences of this library are the straightforward integration of new optimization algorithms and problems as well as the visualization of the optimization process of different methods exploring the search space exclusively or for the real time visualization of different methods in parallel. Further the usage of several implemented methods is presented on the basis of two use cases, where the focus is especially on the algorithm visualization. First it is demonstrated how different methods can be compared conveniently using OPTILIB on the example of different iterative improvement schemes for the TRAVELING SALESMAN PROBLEM. A second study emphasizes how the framework can be used to find global minima in the continuous domain.

Keywords: Global Optimization Heuristics, Particle Swarm Optimization, Ensemble Based Threshold Accepting, Ruin and Recreate

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1075895

References:

[1] G. Reinelt. TSPLIB95. http://www.iwr.uni-heidelberg.de/groups/comopt/ software/TSPLIB95/, 1995.
[Online; accessed 22-November-2007].
[2] A. Franz, K. H. Hoffmann, and P. Salamon. Best Possible Strategy for Finding Ground States. Physical Review Letters, 86(23):5219-5222, June 2001.
[3] E. Schneburg, F. Heinzmann, and S. Feddersen. Genetische Algorithmen und Evolutionsstrategien - Eine Einfhrung in Theorie und Praxis der simulierten Evolution. Addison-Wesley, Bonn, 1994. ISBN 3-89319-4932.
[4] G. Reinelt. The Traveling Salesman, Computational Solutions for TSP Applications. Springer, New York, Berlin, Heidelberg, 1994. ISBN 0- 387-58334-3.
[5] P. Salamon, P. Sibani, and R. Frost. Facts, Conjectures and Improvements for Simulated Annealing. SIAM, Society for Industrial and Applied Mathematics, Philadelphia, 2002. ISBN 0-898-71508-3.
[6] G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, and G. Dueck. Record Breaking Optimization Results Using the Ruin and Recreate Principle. Journal of Computational Physics, 159:139-171, 2000.
[7] A. Carlisle and G. Dozier. An off-the-shelf PSO. Proceedings of the Workshop on Particle Swarm Optimization, 1:1-6, Apr 2001.
[8] Open Source Physics Library. http://www.opensourcephysics.org, 2007.
[Online; accessed 10-October-2007].
[9] S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi. Optimization by Simulated Annealing. Science, 220(4598):671-680, May 1983.
[10] G. Dueck and T. Scheuer. Threshold Accepting: a General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing. Journal of Computational Physics, 90(1):161-175, Sept 1990.
[11] A. Colorni, M. Dorigo, and V. Maniezzo. Towards a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life, chapter Distributed Optimization by Ant Colonies, pages 134-142. MIT Press, 1992.
[12] J. Kennedy and R. Eberhart. Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks, 4:1942-1948, Nov/Dec 1995.
[13] G. Dueck. New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel. Journal of Computation Physics, 104(1):86-92, Jan 1993.