Connecting Automatic Parameter Tuning, Genetic Programming as a Hyper-heuristic, and Genetic Improvement Programming

ABSTRACT

Automatically designing algorithms has long been a dream of computer scientists. Early attempts which generate computer programs from scratch, have failed to meet this goal. However, in recent years there have been a number of different technologies with an alternative goal of taking existing programs and attempting to improving them.

These methods form a range of methodologies, from the "limited" ability to change (for example only the parameters) to the "complete" ability to change the whole program. These include; automatic parameter tuning (APT), using GP as a hyper-heuristic (GPHH), and GI, which we will now briefly review. Part of research is building links between existing work, and the aim of this paper is to bring together these currently separate approaches.

References

1. M. Birattari. Tuning metaheuristics: a machine learning perspective, volume 197. Springer, 2009.
2. C. Giraud-Carrier and F. Provost. Toward a Justification of Meta-learning: Is the No Free Lunch Theorem a Show-stopper? In Proceedings of the ICML-2005 Workshop on Meta-learning, pages 12--19, 2005.
3. M. Harman, W. B. Langdon, Y. Jia, D. R. White, A. Arcuri, and J. A. Clark. The gismoe challenge: Constructing the pareto program surface using genetic programming to find better programs (keynote paper). In Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering, ASE 2012, pages 1--14, New York, NY, USA, 2012. ACM.
4. L. Hong, J. Woodward, J. Li, and E. Ozcan. Automated design of probability distributions as mutation operators for evolutionary programming using genetic programming. In K. Krawiec, A. Moraglio, T. Hu, A. S. Uyar, and B. Hu, editors, Proceedings of the 16th European Conference on Genetic Programming, EuroGP 2013, volume 7831 of LNCS, pages 85--96, Vienna, Austria, 3-5 Apr. 2013. Springer Verlag.
5. H. H. Hoos. Programming by optimization. Commun. ACM, 55(2):70--80, Feb. 2012.
6. W. B. Langdon and M. Harman. Genetically improving 50000 lines of C++. Research Note RN/12/09, Department of Computer Science, University College London, Gower Street, London WC1E 6BT, UK, 19 Sept. 2012.
7. J. Petke, M. Harman, W. B. Langdon, and W. Weimer. Using genetic improvement and code transplants to specialise a C++ program to a problem class. In M. Nicolau, K. Krawiec, M. I. Heywood, M. Castelli, P. Garcia-Sanchez, J. J. Merelo, V. M. Rivas Santos, and K. Sim, editors, 17th European Conference on Genetic Programming, volume 8599 of LNCS, pages 137--149, Granada, Spain, 23-25 Apr. 2014. Springer.
8. E. K. Smith, E. T. Barr, C. Le Goues, and Y. Brun. Is the cure worse than the disease? overfitting in automated program repair. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2015, pages 532--543, New York, NY, USA, 2015. ACM.
9. T. Stützle and M. López-Ibáñez. Automatic (offline) configuration of algorithms. In Proceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computation, GECCO '13 Companion, pages 893--918, New York, NY, USA, 2013. ACM.
10. J. R. Woodward and J. Swan. Automatically designing selection heuristics. In G. L. Pappa, A. A. Freitas, J. Swan, and J. Woodward, editors, GECCO 2011 1st workshop on evolutionary computation for designing generic algorithms, pages 583--590, Dublin, Ireland, 12-16 July 2011. ACM.
11. J. R. Woodward and J. Swan. The automatic generation of mutation operators for genetic algorithms. In G. L. Pappa, J. Woodward, M. R. Hyde, and J. Swan, editors, GECCO 2012 2nd Workshop on Evolutionary Computation for the Automated Design of Algorithms, pages 67--74, Philadelphia, Pennsylvania, USA, 7-11 July 2012. ACM.
12. J. R. Woodward and J. Swan. Template method hyper-heuristics. In J. Swan, K. Krawiec, J. Woodward, C. Simons, and J. Clark, editors, GECCO 2014 Workshop on Metaheuristic Design Patterns (MetaDeeP), pages 1437--1438, Vancouver, BC, Canada, 12-16 July 2014. ACM.
13. F. Wu, W. Weimer, M. Harman, Y. Jia, and J. Krinke. Deep parameter optimisation. In Proceedings of the 2015 on Genetic and Evolutionary Computation Conference, pages 1375--1382. ACM, 2015.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Search methodologies