Predicting Genetic Algorithm Performance on the Vehicle Routing Problem Using Information Theoretic Landscape Measures

1. Alander, J.T., Zinchenko, L.A., Sorokin, S.N.: Analysis of fitness landscape properties for evolutionary antenna design. In: IEEE International Conference on Artificial Intelligence Systems, pp. 363–368 (2002)

   Google Scholar 

2. Barnett, L.: Netcrawling-Optimal Evolutionary Search with Neutral Networks. In: Congress on Evolutionary Computation, pp. 30–37 (2001)

   Google Scholar 

3. Braysy, O., Gendreau, M.: Vehicle routing problem with time windows, part ii: Metaheuristics. Transportation Science 39, 119–139 (2005)

   Article  Google Scholar 

4. Caramia, M., Onori, R.: Experimenting crossover operators to solve the vehicle routing problem with time windows by genetic algorithms. International Journal of Operational Research 3(5), 497–514 (2008)

   Article  MATH  Google Scholar 

5. Czech, Z.J.: Statistical measures of a fitness landscape for the vehicle routing problem. In: IEEE International Symposium on Parallel and Distributed Processing, pp. 1–8 (2008)

   Google Scholar 

6. Czech, Z.J.: A parallel simulated annealing algorithm as a tool for fitness landscape exploration. In: Ros, A. (ed.) Parallel and Distributed Processing, pp. 247–271. In-Tech (2010)

   Google Scholar 

7. Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W. H. Freeman and Company (1979)

   Google Scholar 

8. Jones, T.: Evolutionary Algorithms, Fitness Landscapes and Search. PhD thesis, University of New Mexico (1995)

   Google Scholar 

9. Kubiak, M.: Distance measures and fitness-distance analysis for the capacitated vehicle routing problem. In: Doerner, K.F., Gendreau, M., Greistorfer, P., Gutjahr, W., Hartl, R.F., Reimann, M. (eds.) Metaheuristics. Operations Research Computer Science Interfaces, vol. 39, pp. 345–364. Springer (2007)

   Google Scholar 

10. Laporte, G.: Fifty years of vehicle routing. Transportation Science 43, 408–416 (2009)

    Article  MathSciNet  Google Scholar 

11. Mattfeld, D.C., Bierwirth, C., Kopfer, H.: A search space analysis of the job shop scheduling problem. Annals of Operations Research 86, 441–453 (1999)

    Article  MathSciNet  MATH  Google Scholar 

12. Merz, P., Freisleben, B.: Memetic Algorithms and the Fitness Landscape of the Graph Bi-Partitioning Problem. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 765–774. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

13. Merz, P., Freisleben, B.: Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Transactions on Evolutionary Computation 4(4), 337–352 (2000)

    Article  Google Scholar 

14. Naudts, B., Kallel, L.: A Comparison of Predictive Measures of Problem Difficulty in Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation 4(1), 1–16 (2000)

    Article  Google Scholar 

15. Nazif, H., Lee, L.S.: Optimized crossover genetic algorithm for vehicle routing problem with time windows. American Journal of Applied Sciences 7(1), 95–101 (2010)

    Article  Google Scholar 

16. Ombuki-Berman, B., Ventresca, M.: Search difficulty of two-connected ring-based topological network designs. In: IEEE Symposium on Foundations of Computational Intelligence, pp. 267–274 (2007)

    Google Scholar 

17. Potvin, J.: State-of-the art review evolutionary algorithms for vehicle routing. INFORMS Journal on Computing 21, 518–548 (2009)

    Article  MathSciNet  MATH  Google Scholar 

18. Reeves, C.: Direct statistical estimation of GA landscape properties. In: Foundations of Genetic Algorithms 6, pp. 91–107 (2000)

    Google Scholar 

19. Runka, A., Ombuki-Berman, B., Ventresca, M.: A search space analysis for the waste collection vehicle routing problem with time windows. In: Genetic and Evolutionary Computation Conference, pp. 1813–1814 (2009)

    Google Scholar 

20. Schiavinotto, T., Stutzle, T.: A review of metrics on permutations for search landscape analysis. Computers and Operations Research 34(10), 3143–3153 (2007)

    Article  MATH  Google Scholar 

21. Tavares, J., Pereira, B., Costa, E.: Multidimensional knapsack problem: A fitness landscape analysis. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cynernetics 38(3), 604–616 (2008)

    Article  Google Scholar 

22. Toth, P., Vigo, D.: The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications (2002)

    Google Scholar 

23. Vassilev, V.K., Fogarty, T.C., Miller, J.F.: Information Characteristics and the Structure of Landscapes. Evolutionary Computation 8(1), 31–60 (2000)

    Article  Google Scholar 

24. Vassilev, V.K., Fogarty, T.C., Miller, J.F.: Fitness Landscapes: from Theory to Application. In: Advances in Evolutionary Computation: Theory and Applications, pp. 3–44. Springer (2003)

    Google Scholar 

25. Ventresca, M., Ombuki-Berman, B.: Search space analysis of recurrent spiking and continuous-time neural networks. In: IEEE International Joint Conference on Neural Networks, pp. 8947–8954 (2006)

    Google Scholar 

26. Weinberger, E.: Correlated and Uncorrelated Landscapes and How to Tell the Difference. Biological Cybernetics 63, 325–336 (1990)

    Article  MATH  Google Scholar 

Download references