Hyperion2: a toolkit for {meta-, hyper-} heuristic research

ABSTRACT

In order for appropriate meta-heuristics to be chosen and tuned for specific problems, it is critical that we better understand the problems themselves and how algorithms solve them. This is particularly important as we seek to automate the process of choosing and tuning algorithms and their operators via hyper-heuristics. If meta-heuristics are viewed as sampling algorithms, they can be classified by the trajectory taken through the search space. We term this trajectory a trace. In this paper, we present Hyperion², a Java™ framework for meta- and hyper- heuristics which allows the analysis of the trace taken by an algorithm and its constituent components through the search space. Built with the principles of interoperability, generality and efficiency, we intend that this framework will be a useful aid to scientific research in this domain.

References

1. E. K. Burke, G. Kendall, Search methodologies, Springer, 2005.
2. E. K. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, J. R. Woodward, A classification of hyper-heuristic approaches, in: M. Gendreau, J.-Y. Potvin (Eds.), Handbook of Metaheuristics, Vol. 146 of International Series in Operations Research and Management Science, Springer US, 2010, pp. 449--468.
3. J. R. Woodward, J. Swan, Why classifying search algorithms is essential, in: Progress in Informatics and Computing (PIC), 2010 IEEE International Conference on, Vol. 1, IEEE, 2010, pp. 285--289.
4. P. Ross, S. Schulenburg, J. G. Marín-Blázquez, E. Hart, Hyper-heuristics: Learning to combine simple heuristics in bin-packing problems, in: Proceedings of the Genetic and Evolutionary Computation Conference 2002, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2002, pp. 942--948.
5. S. Luke, Essentials of Metaheuristics, 2nd Edition, Lulu, 2013, available for free at http://cs.gmu.edu/~sean/book/metaheuristics/.
6. A. J. Parkes, Combined Blackbox and AlgebRaic Architecture (CBRA), in: Proc. of PATAT 2010 (extended abstract), 2010, pp. 535--538.
7. F. Glover, Tabu Search - Part I, INFORMS Journal on Computing 1 (3) (1989) 190--206.
8. J. R. Woodward, J. Swan, The automatic generation of mutation operators for genetic algorithms, in: Proceedings of the 14th Genetic and Evolutionary Computation Conference Companion, GECCO Companion '12, ACM, New York, NY, USA, 2012, pp. 67--74. doi: 10.1145/2330784.2330796.
9. J. R. Woodward, J. Swan, Automatically designing selection heuristics, in: Proceedings of the 13th Conference Companion on Genetic and Evolutionary Computation, GECCO '11, ACM, New York, NY, USA, 2011, pp. 583--590. doi: 10.1145/2001858.2002052.
10. K. Krawiec, J. Swan, Pattern-guided genetic programming, in: Proceeding of the 15th Genetic and Evolutionary Computation Conference, GECCO '13, ACM, New York, NY, USA, 2013, pp. 949--956. doi: 10.1145/2463372.2463496.
11. K. Krawiec, J. Swan, Guiding evolutionary learning by searching for regularities in behavioral trajectories: A case for representation agnosticism, in: 2013 AAAI Fall Symposium Series, 2013, pp. 41--46.
12. J. Swan, E. Özcan, G. Kendall, Hyperion: a recursive hyper-heuristic framework, in: Proceedings of the 5th international conference on Learning and Intelligent Optimization, LION'05, Springer-Verlag, Berlin, Heidelberg, 2011, pp. 616--630.
13. C. Voudouris, R. Dorne, D. Lesaint, A. Liret, iOpt: A Software Toolkit for Heuristic Search Methods, in: T. Walsh (Ed.), Principles and Practice of Constraint Programming CP 2001, Vol. 2239 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2001, pp. 716--729.
14. L. D. Gaspero, A. Schaerf, Easylocal++: An Object-oriented Framework for the flexible design of Local-Search Algorithms, Softw., Pract. Exper. 33 (8) (2003) 733--765.
15. A. Fink, S. Voß, Hotframe: A heuristic optimization framework, in: S. Voß, D. Woodruff (Eds.), Optimization Software Class Libraries, OR/CS Interfaces Series, Kluwer Academic Publishers, Boston, 2002, pp. 81--154.
16. M. Mitchell, An Introduction to Genetic Algorithms, The MIT Press, 1998.
17. J. A. Parejo, A. Ruiz-Cortés, S. Lozano, P. Fernandez, Metaheuristic optimization frameworks: a survey and benchmarking, Soft Computing 16 (3) (2012) 527--561.
18. S. Wagner, G. Kronberger, A. Beham, M. Kommenda, A. Scheibenpflug, E. Pitzer, S. Vonolfen, M. Kofler, S. Winkler, V. Dorfer, M. Affenzeller, Advanced Methods and Applications in Computational Intelligence, Vol. 6 of Topics in Intelligent Engineering and Informatics, Springer, 2014, Ch. Architecture and Design of the HeuristicLab Optimization Environment, pp. 197--261. URL http://link.springer.com/chapter/10.1007/978-3-319-01436-4_10
19. S. Luke, L. Panait, G. Balan, S. Paus, Z. Skolicki, E. Popovici, S. K, J. Harrison, J. Bassett, R. Hubley, A. Chircop, H. W. Compton J, S. Donnelly, B. Jamil, J. O'Beirne, ECJ: A Java based evolutionary computation research system (2009). URL http://cs.gmu.edu/~eclab/projects/ecj/
20. F. Otero, T. Castle, C. Johnson, EpochX: Genetic programming in java with statistics and event monitoring, in: Proceedings of the 14th genetic and evolutionary computation conference companion, ACM, 2012, pp. 93--100.
21. E. K. Burke, T. Curtois, M. Hyde, G. Kendall, G. Ochoa, S. Petrovic, J. A. Vazquez-Rodriguez, HyFlex: A Flexible Framework for the Design and Analysis of Hyper-heuristics, in: Multidisciplinary International Scheduling Conference (MISTA 2009), Dublin, Ireland, Dublin, Ireland, 2009, pp. 790--797. URL http://www.asap.cs.nott.ac.uk/publications/pdf/MISTA09HyFlex.pdf
22. E. Urra, D. Cabrera-Paniagua, C. Cubillos, Towards an object-oriented pattern proposal for heuristic structures of diverse abstraction levels, in: Workshop on Agents and Collaborative Systems (WACS), School of Computer Engineering, Catholic University of Temuco, 2013. URL jcc2013.inf.uct.cl
23. A. Elyasaf, M. Sipper, HH-evolver: a system for domain-specific, hyper-heuristic evolution, in: Proceeding of the 15th conference companion on Genetic and evolutionary computation conference companion, ACM, 2013, pp. 1285--1292.
24. H. K. Cora, H. T. Uyar, A. Ş. Etaner-Uyar, HH-DSL: a domain specific language for selection hyper-heuristics, in: Proceeding of the 15th Genetic and evolutionary computation conference companion, ACM, 2013, pp. 1317--1324.
25. Lindawati, H. Lau, D. Lo, Instance-based parameter tuning via search trajectory similarity clustering, in: C. Coello (Ed.), Learning and Intelligent Optimization, Vol. 6683 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2011, pp. 131--145. doi: 10.1007/978-3-642-25566-3_10.
26. Lindawati, H. Lau, F. Zhu, Instance-specific parameter tuning via constraint-based clustering, in: Proc. of the 1st Int. Workshop on COmbining COnstraint solving with MIning and LEarning (CoCoMile' 12), joint with ECAI, Montpellier, France, 2012.
27. L. Lindawati, F. ZHU, H. C. LAU, FloTra: Flower-shape trajectory mining for instance-specific parameter tuning, 10th edition of the Metaheuristics International Conference (MIC 2013), 2013.
28. E. Gamma, R. Helm, R. E. Johnson, J. M. Vlissides, Design patterns: Abstraction and reuse of object-oriented design, in: ECOOP '93: Proceedings of the 7th European Conference on Object-Oriented Programming, Springer-Verlag, London, UK, 1993, pp. 406--431.
29. J. O. Coplien, Curiously recurring template patterns, C++ Rep. 7 (2) (1995) 24--27. URL http://dl.acm.org/citation.cfm?id=229227.229229
30. J. Swan, J. Woodward, E. Özcan, G. Kendall, E. Burke, Searching the hyper-heuristic design space, Cognitive Computation 6 (1) (2014) 66--73.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Heuristic function construction

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types

        • Object oriented languages