Fitness-distance analysis of a car sequencing problem

• Autorzy: Kubiak M. , Jaszkiewicz A. , Kominek P.
• Języki publikacji: EN

Abstrakty

EN

The paper describes a fitness-distance analysis of a car sequencing problem. It defines 5 similarity measures for solutions of the problem, describes computational experiments and provides values of determination coefficients between fitness and similarity, which are an indicator of fitness-distance correlation (or 'big valley'). The analysis reveals certain correlations of fitness and two types of similarity for 4 of 5 types of available instances. This results might motivate such designs of metaheuristics for these types of instances which would exploit the structure in fitness landscapes.

Słowa kluczowe

EN

similarity measure; fitness-distance correlation; metaheuristic; combinatorial optimisation

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2006
• Tom: Vol. 31, No. 3-4
• Strony: 263--276
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Kubiak M.

autor

Jaszkiewicz A.

autor

Kominek P.

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznań, Poland,

Bibliografia

• [1] Altenberg, L. (1997): "Fitness distance correlation analysis: an instructive counterexample". In: Baeck. T. (ed.), Proceedings of the 7th Int. Con/, on Genetic Algorithms, Morgan Kaufmann.
• [2] Boese, K. D. (1995): "Cost versus distance in trie traveling salesman problem". Technical Report [TR-950018J. UCLA CS Department, California.
• [3] Finger. T., Stiitzle, T.. and Lourengo, H. (2002): "Exploiting fitness distance correlation of set covering problems". In: Applications of Evolutionary Computing: EvoWorkshops 2002, Kinsale, Ireland, April 3-4. 2002, LNCS 2279, Springer-Verlag.
• [4] Gottlieb, J., Puchta, M., and Solnon. Ch. (2003): "A study of greedy, local search and ant colony optimization aproaches for car sequencing problems". In: Applications of Evolutionary Computing: EvoWorshops 2003. Essex, UK, April 14-16. 2003, LNCS 2611, Springer-Verlag.
• [5] http://www.prism.uvsq.fr/~vdc/ROADEF/CHALLEXGES/2005/, last access: April 2006.
• [6] Jaszkiewicz, A., and Kominek, P. (2003): "Genetic local search with distance preserving recombination operator for a vehicle routing problem". In: European Journal of Operational Research 151, 352-364.
• [7] Jaszkiewicz, A.. Kominek, P., and Kubiak. M. (2004): "Adaptation of the genetic local search algorithm to a car sequencing problem". In: 7th National Conference on Evolutionary Computation and Global Optimization, Kazimierz Dolny, Poland, 2004, 75-82.
• [8] Jones, T., and Forrest, S. (1995): "Fitness distance correlation as a measure of problem difficulty for genetic algorithms". In: L. J. Eshelman (ed.), Proceedings of the 6th Int. Conf. on Genetic Algorithms, Kaufmann. 184-192.
• [9] Kubiak, M. (2004): "Systematic construction of recombination operators for the vehicle routing problem". In: Foundations of Computing and Decision Sciences 29 (3), 205-226.
• [10] Mattiusi, C., Waibel, M., and Floreano, D. (2004): "Measures of diversity for populations and distances between individuals with highly reorganizable genomes". In: Evolutionary Computation 12 (3), 495-515.
• [11] Merz, P. (2004): "Advanced fitness landscape analysis and the performance of memetic algorithms". In: Evolutionary Computation 12 (3). 303-325.
• [12] Merz, P., and Freisleben, B. (1999): "Fitness landscapes and memetic algorithms design". In: D. Corne, et al. (eds.). New Ideas in Optimization, McGraw-HilL
• [13] Puchta, M., and Gottlieb, J. (2002): "Solving car sequencing problems by local optimization". In: Applications of Evolutionary Computing: Evo Workshops 2002, Kinsale, Ireland, April 3-4, 2002, LNCS 2279, Springer-Verlag.
• [14] Reeves, C. R. (1999): "Landscapes, operators and heuristic search'. In: Annals of Operations Research 86, 473-490.
• [15] Watson, J.-P. (2005): "On metaheuristic 'failure modes': a case study in tabu search for job-shop scheduling". Presented at the 6th Metaheuristics International Conference, MIC2005, Vienna, Austria, August 22-26, 2005, 910-915.