Fitness Landscape Analysis for Capacitated Vehicle Routing Problem
This paper studies the fitness landscape characteristics for capacitated vehicle routing problem (CVRP). Fitness distance correlation analysis and autocorrelation analysis are used to investigate the global and local features of a fitness landscape, respe
- PDF / 177,011 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 43 Downloads / 230 Views
Fitness Landscape Analysis for Capacitated Vehicle Routing Problem Lin Tian
Abstract This paper studies the fitness landscape characteristics for capacitated vehicle routing problem (CVRP). Fitness distance correlation analysis and autocorrelation analysis are used to investigate the global and local features of a fitness landscape, respectively. As for global features, we investigate to which degree the fitness of a solution to CVRP is related to the distance which is between the solution and the global optimum. As for local features, the ruggedness of the investigated landscape is concerned and to measure it random walks are conducted based on three popularly used mutation operators. A number of benchmark instances are investigated and the results show that: (1) there is no significant correlation between fitness and distance in most of the instances, and (2) different mutation operators may result in different ruggedness of a search space. Keywords Vehicle routing problem • Fitness distance correlation analysis • Autocorrelation analysis
16.1
Introduction
Capacitated vehicle routing problem (CVRP) is one of the well-known combinatorial optimization problems [1–3]. Due to the wide-ranging applications in logistic planning, CVPR has received a great amount of consideration from both academia and industry. Many optimization algorithms are adopted to find a good solution to CVPR, including variants of genetic algorithm (GA) [4, 5]. Whilst designing GAs for a certain type of optimization problem, it is worth analyzing the features of fitness landscape of the problem concerned. This work is quite essential to show how difficult the problem itself is. For a given landscape,
L. Tian (*) Business School, Zhengzhou University, Zhengzhou 450001, People’s Republic of China e-mail: [email protected] S. Zhong (ed.), Proceedings of the 2012 International Conference on Cybernetics 119 and Informatics, Lecture Notes in Electrical Engineering 163, DOI 10.1007/978-1-4614-3872-4_16, # Springer Science+Business Media New York 2014
120
L. Tian
two important features are usually investigated, i.e. global and local features. To measure the global feature, fitness distance correlation (FDC) analysis is the most commonly used metric [6–8]. FDC has been used for predicting the difficulty of many optimization problems including CVPR [8]. On the other hand, to measure the local feature, autocorrelation (AC) analysis is often chosen to show the ruggedness of a search space [7, 9, 10]. Knowing local feature is very helpful to design appropriate local search operators such as mutation. However, FDC and AC analysis has not received enough research attention. In this paper, we use FDC and AC analysis to investigate the fitness landscape characteristics of ten CVRP benchmark instances. In FDC analysis, we not only plot distance vs. fitness of a large amount of random samples in solution space but also calculate the FDC coefficient which quantitatively unveils the difficulty of a certain instance. The results show that CVRP is a difficu
Data Loading...
