An Integrated Framework for the Realtime Investigation of State Space Exploration

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.

Authors:

• Jörg Lassig
• Stefanie Thiem

Keywords:

• Global Optimization Heuristics
• Particle Swarm Optimization
• Ensemble Based Threshold Accepting
• Ruin and Recreate

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.