Skip to main content

2016 | OriginalPaper | Buchkapitel

Iterative Cartesian Genetic Programming: Creating General Algorithms for Solving Travelling Salesman Problems

verfasst von : Patricia Ryser-Welch, Julian F. Miller, Jerry Swan, Martin A. Trefzer

Erschienen in: Genetic Programming

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Evolutionary algorithms have been widely used to optimise or design search algorithms, however, very few have considered evolving iterative algorithms. In this paper, we introduce a novel extension to Cartesian Genetic Programming that allows it to encode iterative algorithms. We apply this technique to the Traveling Salesman Problem to produce human-readable solvers which can be then be independently implemented. Our experimental results demonstrate that the evolved solvers scale well to much larger TSP instances than those used for training.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
d1291, u2152, usa23505 and d18512 are benchmarks from the well-known TSPLIB. The remaining instances are benchmarks from real-life geographical data; these are wi29, dj38, qa194, zi929, ca4663, ym7663, ja9874, gr9882, sw24978. All these instances can be found at http://​www.​math.​uwaterloo.​ca/​tsp/​world/​countries.​html and http://​comopt.​ifi.​uni-heidelberg.​de/​software/​TSPLIB95/​STSP.​html.
 
Literatur
1.
Zurück zum Zitat Alexander, B., Zacher, B.: Boosting search for recursive functions using partial call-trees. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 384–393. Springer, Heidelberg (2014) Alexander, B., Zacher, B.: Boosting search for recursive functions using partial call-trees. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 384–393. Springer, Heidelberg (2014)
2.
Zurück zum Zitat Banzhaf, W.: The “molecular” traveling salesman. Biol. Cybern. 64(1), 7–14 (1990)CrossRefMATH Banzhaf, W.: The “molecular” traveling salesman. Biol. Cybern. 64(1), 7–14 (1990)CrossRefMATH
3.
Zurück zum Zitat Brave, S.: Evolving Recusive Programs for Tree Search. MIT Press, Cambridge (1996) Brave, S.: Evolving Recusive Programs for Tree Search. MIT Press, Cambridge (1996)
4.
Zurück zum Zitat Brownlee, A.E., Swan, J., Özcan, E., Parkes, A.J.: Hyperion\(^2\): A toolkit for Meta-, Hyper- heuristic research. In: Proceedings of the 2014 Conference Companion on Genetic and Evolutionary Computation Companion, GECCO Comp 2014, NY, USA, pp. 1133–1140. ACM, New York (2014) Brownlee, A.E., Swan, J., Özcan, E., Parkes, A.J.: Hyperion\(^2\): A toolkit for Meta-, Hyper- heuristic research. In: Proceedings of the 2014 Conference Companion on Genetic and Evolutionary Computation Companion, GECCO Comp 2014, NY, USA, pp. 1133–1140. ACM, New York (2014)
5.
Zurück zum Zitat Burke, E.K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., Qu, R.: Hyper-heuristics: a survey of the state of the art. J. Oper. Res. Soc. 64(12), 1695–1724 (2013)CrossRef Burke, E.K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., Qu, R.: Hyper-heuristics: a survey of the state of the art. J. Oper. Res. Soc. 64(12), 1695–1724 (2013)CrossRef
6.
Zurück zum Zitat Davis, L., et al.: Handbook of Genetic Algorithms, vol. 115. Van Nostrand Reinhold, New York (1991) Davis, L., et al.: Handbook of Genetic Algorithms, vol. 115. Van Nostrand Reinhold, New York (1991)
7.
Zurück zum Zitat Fogel, D.B.: An evolutionary approach to the traveling salesman problem. Biol. Cybern. 60(2), 139–144 (1988)MathSciNetCrossRef Fogel, D.B.: An evolutionary approach to the traveling salesman problem. Biol. Cybern. 60(2), 139–144 (1988)MathSciNetCrossRef
8.
Zurück zum Zitat Goldberg, D.E., Lingle, R.: Alleles, loci, and the traveling salesman problem. In: Proceedings of an International Conference on Genetic Algorithms and Their Applications, vol. 154, Lawrence Erlbaum, Hillsdale, NJ (1985) Goldberg, D.E., Lingle, R.: Alleles, loci, and the traveling salesman problem. In: Proceedings of an International Conference on Genetic Algorithms and Their Applications, vol. 154, Lawrence Erlbaum, Hillsdale, NJ (1985)
9.
Zurück zum Zitat Grefenstette, J.J.: Incorporating problem specific knowledge into genetic algorithms. Genet. Algorithms Simulated Annealing 4, 42–60 (1987) Grefenstette, J.J.: Incorporating problem specific knowledge into genetic algorithms. Genet. Algorithms Simulated Annealing 4, 42–60 (1987)
10.
Zurück zum Zitat Gutin, G., Karapetyan, D.: A memetic algorithm for the generalized traveling salesman problem. Nat. Comput. 9(1), 47–60 (2010)MathSciNetCrossRefMATH Gutin, G., Karapetyan, D.: A memetic algorithm for the generalized traveling salesman problem. Nat. Comput. 9(1), 47–60 (2010)MathSciNetCrossRefMATH
11.
Zurück zum Zitat Helsgaun, K.: An effective implementation of the lin-kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106–130 (2000)MathSciNetCrossRefMATH Helsgaun, K.: An effective implementation of the lin-kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106–130 (2000)MathSciNetCrossRefMATH
12.
Zurück zum Zitat Hoos, H.H.: Programming by optimization. Commun. ACM 55(2), 70–80 (2012)CrossRef Hoos, H.H.: Programming by optimization. Commun. ACM 55(2), 70–80 (2012)CrossRef
13.
Zurück zum Zitat Kant, E.: Understanding and automating algorithm design. IEEE Trans. Softw. Eng. SE–11(11), 1361–1374 (1985)MathSciNetCrossRef Kant, E.: Understanding and automating algorithm design. IEEE Trans. Softw. Eng. SE–11(11), 1361–1374 (1985)MathSciNetCrossRef
14.
Zurück zum Zitat Kasturi, E., Narayanan, S.L.: A novel approach to hybrid genetic algorithms to solve symmetric TSP. Int. J. 2(2) (2014) Kasturi, E., Narayanan, S.L.: A novel approach to hybrid genetic algorithms to solve symmetric TSP. Int. J. 2(2) (2014)
15.
Zurück zum Zitat Katayama, K., Sakamoto, H., Narihisa, H.: The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem. Math. Comput. Model. 31(10), 197–203 (2000)MathSciNetCrossRefMATH Katayama, K., Sakamoto, H., Narihisa, H.: The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem. Math. Comput. Model. 31(10), 197–203 (2000)MathSciNetCrossRefMATH
16.
Zurück zum Zitat Koza, J.R., Andre, D.: Evolution of iteration in genetic programming. In: Evolutionary Programming, pp. 469–478 (1996) Koza, J.R., Andre, D.: Evolution of iteration in genetic programming. In: Evolutionary Programming, pp. 469–478 (1996)
17.
Zurück zum Zitat Langdon, W.B.: Genetic programming and data structures. Ph.D. thesis, University College London (1996) Langdon, W.B.: Genetic programming and data structures. Ph.D. thesis, University College London (1996)
18.
Zurück zum Zitat Larres, J., Zhang, M., Browne, W.N.: Using unrestricted loops in genetic programming for image classification. In: 2010 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE (2010) Larres, J., Zhang, M., Browne, W.N.: Using unrestricted loops in genetic programming for image classification. In: 2010 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE (2010)
19.
Zurück zum Zitat Lin, S., Kernighan, B.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2), 498–516 (1973)MathSciNetCrossRefMATH Lin, S., Kernighan, B.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2), 498–516 (1973)MathSciNetCrossRefMATH
20.
Zurück zum Zitat López-Ibánez, M., Dubois-Lacoste, J., Stützle, T., Birattari, M.: The irace package, iterated race for automatic algorithm configuration. Technical report, Citeseer (2011) López-Ibánez, M., Dubois-Lacoste, J., Stützle, T., Birattari, M.: The irace package, iterated race for automatic algorithm configuration. Technical report, Citeseer (2011)
21.
Zurück zum Zitat López-Ibánez, M., Stützle, T.: The automatic design of multiobjective ant colony optimization algorithms. IEEE Trans. Evol. Comput. 16(6), 861–875 (2012)CrossRef López-Ibánez, M., Stützle, T.: The automatic design of multiobjective ant colony optimization algorithms. IEEE Trans. Evol. Comput. 16(6), 861–875 (2012)CrossRef
23.
Zurück zum Zitat Miihlenbein, H., Kindermann, J.: The dynamics of evolution and learning-towards genetic neural networks. Connectionism Perspect. pp. 173–197 (1989) Miihlenbein, H., Kindermann, J.: The dynamics of evolution and learning-towards genetic neural networks. Connectionism Perspect. pp. 173–197 (1989)
24.
Zurück zum Zitat Miller, J.: What bloat? cartesian genetic programming on boolean problems. In: 2001 Genetic and Evolutionary Computation Conference Late Breaking Papers, pp. 295–302 (2001) Miller, J.: What bloat? cartesian genetic programming on boolean problems. In: 2001 Genetic and Evolutionary Computation Conference Late Breaking Papers, pp. 295–302 (2001)
25.
Zurück zum Zitat Miller, J.F. (ed.): Cartesian Genetic Programming. Springer, Heidelberg (2011)MATH Miller, J.F. (ed.): Cartesian Genetic Programming. Springer, Heidelberg (2011)MATH
26.
Zurück zum Zitat Nagata, Y., Soler, D.: A new genetic algorithm for the asymmetric traveling salesman problem. Expert Syst. Appl. 39(10), 8947–8953 (2012)CrossRef Nagata, Y., Soler, D.: A new genetic algorithm for the asymmetric traveling salesman problem. Expert Syst. Appl. 39(10), 8947–8953 (2012)CrossRef
27.
Zurück zum Zitat Ozcan, E., Erenturk, M.: A brief review of memetic algorithms for solving Euclidean 2D traveling salesrep problem. In: Proceedings of the 13th Turkish Symposium on Artificial Intelligence and Neural Networks, pp. 99–108 (2004) Ozcan, E., Erenturk, M.: A brief review of memetic algorithms for solving Euclidean 2D traveling salesrep problem. In: Proceedings of the 13th Turkish Symposium on Artificial Intelligence and Neural Networks, pp. 99–108 (2004)
28.
Zurück zum Zitat Pillay, N.: A review of hyper-heuristics for educational timetabling. Ann. Oper. Res. pp. 1–36 (2014) Pillay, N.: A review of hyper-heuristics for educational timetabling. Ann. Oper. Res. pp. 1–36 (2014)
29.
Zurück zum Zitat Rokbani, N., Abraham, A., Alimil, A.M.: Fuzzy ant supervised by PSO and simplified ant supervised PSO applied to TSP. In: 2013 13th International Conference on Hybrid Intelligent Systems (HIS), pp. 251–255. IEEE (2013) Rokbani, N., Abraham, A., Alimil, A.M.: Fuzzy ant supervised by PSO and simplified ant supervised PSO applied to TSP. In: 2013 13th International Conference on Hybrid Intelligent Systems (HIS), pp. 251–255. IEEE (2013)
30.
Zurück zum Zitat Ross, P.: Hyper-heuristics. In: Burke, E.K., Kendall, G. (eds.) Search Methodologies, pp. 529–556. Springer, US (2005)CrossRef Ross, P.: Hyper-heuristics. In: Burke, E.K., Kendall, G. (eds.) Search Methodologies, pp. 529–556. Springer, US (2005)CrossRef
31.
Zurück zum Zitat Ross, P.: Hyper-heuristics. In: Burke, E.K., Kendall, G. (eds.) Search Methodologies, pp. 611–638. Springer, US (2005) Ross, P.: Hyper-heuristics. In: Burke, E.K., Kendall, G. (eds.) Search Methodologies, pp. 611–638. Springer, US (2005)
32.
Zurück zum Zitat Ross, P., Schulenburg, S., Marín-Blázquez, J.G., Hart, E.: Hyper-heuristics: learning to combine simple heuristics in bin-packing problems. In: GECCO 2002, Proceedings of the Genetic and Evolutionary Computation Conference, pp. 942–948. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2002) Ross, P., Schulenburg, S., Marín-Blázquez, J.G., Hart, E.: Hyper-heuristics: learning to combine simple heuristics in bin-packing problems. In: GECCO 2002, Proceedings of the Genetic and Evolutionary Computation Conference, pp. 942–948. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2002)
33.
Zurück zum Zitat Ryser-Welch, P., Miller, J.F.: A review of hyper-heuristic frameworks. In: Proceedings of the 50th Anniversary Convention of the AISB, London, 1–4 April 2014 Ryser-Welch, P., Miller, J.F.: A review of hyper-heuristic frameworks. In: Proceedings of the 50th Anniversary Convention of the AISB, London, 1–4 April 2014
34.
Zurück zum Zitat Ryser-Welch, P., Miller, J.F., Asta, S.: Generating human-readable algorithms for the travelling salesman problem using hyper-heuristics. In: GECCO Companion 2015, Proceedings of the Companion Publication of the 2015 on Genetic and Evolutionary Computation Conference, pp. 1067–1074. ACM, New York, NY, USA (2015). http://doi.acm.org/10.1145/2739482.2768459 Ryser-Welch, P., Miller, J.F., Asta, S.: Generating human-readable algorithms for the travelling salesman problem using hyper-heuristics. In: GECCO Companion 2015, Proceedings of the Companion Publication of the 2015 on Genetic and Evolutionary Computation Conference, pp. 1067–1074. ACM, New York, NY, USA (2015). http://​doi.​acm.​org/​10.​1145/​2739482.​2768459
35.
Zurück zum Zitat Shirakawa, S., Nagao, T.: Graph structured program evolution with automatically defined nodes. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, pp. 1107–1114. ACM (2009) Shirakawa, S., Nagao, T.: Graph structured program evolution with automatically defined nodes. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, pp. 1107–1114. ACM (2009)
36.
Zurück zum Zitat Swan, J., Woodward, J.R., Özcan, E., Kendall, G., Burke, E.K.: Searching the hyper-heuristic design space. Cogn. Comput. 6(1), 66–73 (2014)CrossRef Swan, J., Woodward, J.R., Özcan, E., Kendall, G., Burke, E.K.: Searching the hyper-heuristic design space. Cogn. Comput. 6(1), 66–73 (2014)CrossRef
37.
Zurück zum Zitat Swan, J., Burles, N.: Templar - a framework for template-method hyper-heuristics. In: Machado, P., et al. (eds.) Genetic Programming. Lecture Notes in Computer Science, vol. 9025, pp. 205–216. Springer, Switzerland (2015) Swan, J., Burles, N.: Templar - a framework for template-method hyper-heuristics. In: Machado, P., et al. (eds.) Genetic Programming. Lecture Notes in Computer Science, vol. 9025, pp. 205–216. Springer, Switzerland (2015)
38.
Zurück zum Zitat Swan, J., Özcan, E., Kendall, G.: Hyperion – a recursive hyper-heuristic framework. In: Coello, C.A.C. (ed.) LION 2011. LNCS, vol. 6683, pp. 616–630. Springer, Heidelberg (2011)CrossRef Swan, J., Özcan, E., Kendall, G.: Hyperion – a recursive hyper-heuristic framework. In: Coello, C.A.C. (ed.) LION 2011. LNCS, vol. 6683, pp. 616–630. Springer, Heidelberg (2011)CrossRef
39.
Zurück zum Zitat Tavares, J., Pereira, F.B.: Automatic design of ant algorithms with grammatical evolution. In: Moraglio, A., Silva, S., Krawiec, K., Machado, P., Cotta, C. (eds.) EuroGP 2012. LNCS, vol. 7244, pp. 206–217. Springer, Heidelberg (2012)CrossRef Tavares, J., Pereira, F.B.: Automatic design of ant algorithms with grammatical evolution. In: Moraglio, A., Silva, S., Krawiec, K., Machado, P., Cotta, C. (eds.) EuroGP 2012. LNCS, vol. 7244, pp. 206–217. Springer, Heidelberg (2012)CrossRef
40.
Zurück zum Zitat Turner, A.J., Miller, J.F.: Neutral genetic drift: an investigation using cartesian genetic programming. Genet. Program. Evolvable Mach. 16(4), 531–558 (2015)CrossRef Turner, A.J., Miller, J.F.: Neutral genetic drift: an investigation using cartesian genetic programming. Genet. Program. Evolvable Mach. 16(4), 531–558 (2015)CrossRef
41.
Zurück zum Zitat Walker, J.A., Liu, Y., Tempesti, G., Timmis, J., Tyrrell, A.M.: Automatic machine code generation for a transport triggered architecture using cartesian genetic programming. Int. J. Adapt. Resilient Auton. Syst. (IJARAS) 3(4), 32–50 (2012)CrossRef Walker, J.A., Liu, Y., Tempesti, G., Timmis, J., Tyrrell, A.M.: Automatic machine code generation for a transport triggered architecture using cartesian genetic programming. Int. J. Adapt. Resilient Auton. Syst. (IJARAS) 3(4), 32–50 (2012)CrossRef
42.
Zurück zum Zitat Wijesinghe, G., Ciesielski, V.: Evolving programs with parameters and loops. In: 2010 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE (2010) Wijesinghe, G., Ciesielski, V.: Evolving programs with parameters and loops. In: 2010 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE (2010)
43.
Zurück zum Zitat Yu, T., Clack, C.: Recursion, lambda-abstractions and genetic programming. In: Poli, R., Langdon, W.B., Schoenauer, M., Fogarty, T., Banzhaf, W. (eds.) Late Breaking Papers at EuroGP 1998: The First European Workshop on Genetic Programming, CSRP-98-10, pp. 26–30. The University of Birmingham, UK, Paris, France, 14–15 April 1998 Yu, T., Clack, C.: Recursion, lambda-abstractions and genetic programming. In: Poli, R., Langdon, W.B., Schoenauer, M., Fogarty, T., Banzhaf, W. (eds.) Late Breaking Papers at EuroGP 1998: The First European Workshop on Genetic Programming, CSRP-98-10, pp. 26–30. The University of Birmingham, UK, Paris, France, 14–15 April 1998
Metadaten
Titel
Iterative Cartesian Genetic Programming: Creating General Algorithms for Solving Travelling Salesman Problems
verfasst von
Patricia Ryser-Welch
Julian F. Miller
Jerry Swan
Martin A. Trefzer
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-30668-1_19