×

ParadisEO-MO: from fitness landscape analysis to efficient local search algorithms. (English) Zbl 1365.90008

Summary: This paper presents a general-purpose software framework dedicated to the design, the analysis and the implementation of local search metaheuristics: ParadisEO-MO. A substantial number of single solution-based local search metaheuristics has been proposed so far, and an attempt of unifying existing approaches is here presented. Based on a fine-grained decomposition, a conceptual model is proposed and is validated by regarding a number of state-of-the-art methodologies as simple variants of the same structure. This model is then incorporated into the ParadisEO-MO software framework. This framework has proven its efficiency and high flexibility by enabling the resolution of many academic and real-world optimization problems from science and industry.

MSC:

90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E.H.L., Lenstra, J.K.: Local Search in Combinatorial Optimization. Wiley, New York (1997) · Zbl 0869.00019
[2] Adenso-Díaz, B., Laguna, M.: Fine-tuning of algorithms using fractional experimental designs and local search. Oper. Res. 54(1), 99-114 (2006) · Zbl 1167.90654 · doi:10.1287/opre.1050.0243
[3] Alba, E., Almeida, F., Blesa, M., Cotta, C., Díaz, M., Dorta, I., Gabarró, J., González, J., León, C., Moreno, L., Petit, J., Roda, J., Rojas, A., Xhafa, F., (2002) MALLBA: A library of skeletons for combinatorial optimisation. In: Parallel Processing Conference (Euro-Par, 2002). Lecture Notes in Computer Science, vol. 2400, pp. 927-932. Springer, Berlin (2002) · Zbl 1068.68699
[4] Altenberg, L.: Fitness distance correlation analysis: an instructive counterexemple. In: Bäck T (ed.) Seventh International Conference on Genetic Algorithms, pp. 57-64. Morgan Kaufmann, San Francisco (1997) · Zbl 0967.90086
[5] Bastolla, U., Porto, M., Roman, H.E., Vendruscolo, M.: Statiscal properties of neutral evolution. J. Mol. Evol. 57(S), 103-119 (2003) · doi:10.1007/s00239-003-0013-4
[6] Benoist, T., Estellon, B., Gardi, F., Megel, R., Nouioua, K.: LocalSolver 1.x: a black-box local-search solver for 0-1 programming. Q. J. Oper. Res. 9, 299-316 (2011) · Zbl 1231.90318 · doi:10.1007/s10288-011-0165-9
[7] Birattari, M., Stützle, T., Paquete, L., Varrentrapp, K.: A racing algorithm for configuring metaheuristics. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 11-18. Morgan Kaufmann Publishers Inc., San Francisco, GECCO ’02 (2002)
[8] Bleuler, S., Laumanns, M., Thiele, L., Zitzler, E.: PISA—a platform and programming language independent interface for search algorithms. In: Second International Conference on Evolutionary Multi-Criterion Optimization (EMO 2003), pp. 494-508. Faro (2003). · Zbl 1037.68743
[9] Boisson, J.C., Jourdan, L., Talbi, E.G.: Metaheuristics based de novo protein sequencing: a new approach. Appl. Soft Comput. 11(2), 2271-2278 (2011) · doi:10.1016/j.asoc.2010.08.007
[10] Burke, E., Newall, J.: (2002) Enhancing timetable solutions with local search methods. In: Practise and Theory of Automated Timetabling IV (PATAT 2002, Gent, Belgium). Lecture Notes in Computer Science, vol. 2740, pp. 195-206. IEEE Press, Springer (2002)
[11] Cahon, S., Melab, N., Talbi, E.G.: ParadisEO: a framework for the reusable design of parallel and distributed metaheuristics. J. Heuristics 10(3), 357-380 (2004) · Zbl 1098.68644
[12] Cerny, V.: A thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J. Optim. Theory Appl. 45, 41-51 (1985) · Zbl 0534.90091 · doi:10.1007/BF00940812
[13] Charon, I., Hudry, O.: The noising method: a new method for combinatorial optimization. Oper. Res. Lett. 14, 133-137 (1993) · Zbl 0798.90118 · doi:10.1016/0167-6377(93)90023-A
[14] Clergue, M., Collard, P.: GA-hard functions built by combination of trap functions. In: Proceedings of the 2002 Congress on Evolutionary Computation (CEC 2002), pp. 249-254. IEEE Press (2002)
[15] Daolio, F., Verel, S., Ochoa, G., Tomassini, M.: Local optima networks of the quadratic assignment problem. In: Proceeding of IEEE world conference on computational intelligence (WCCI), pp. 3145-3152. Barcelona, Spain (2010)
[16] Dekkers, A., Aarts, E.: Global optimization and simulated annealing. Math. Program. 50, 367-393 (1991) · Zbl 0753.90060 · doi:10.1007/BF01594945
[17] Di Gaspero, L., Roli, A., Schaerf, A.: Easyanalyzer: an object-oriented framework for the experimental analysis of stochastic local search algorithms. In: International Conference on Engineering Stochastic Local Search Algorithms SLS: Springer, pp. 76-90. Heidelberg. Lecture Notes in Computer Science, Berlin (2007)
[18] Eiben, A.E., Michalewicz, Z., Schoenauer, M., Smith, J.E. Parameter control in evolutionary algorithms. In: Lobo, F.G., Lima, C.F., Michalewicz, Z. (eds.) Parameter Setting in Evolutionary Algorithms, Studies in Computational Intelligence, vol. 54, pp. 19-46. Springer, Berlin (2007)
[19] Feo, T.A., Resende, M.G.C.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8, 67-71 (1989) · Zbl 0675.90073 · doi:10.1016/0167-6377(89)90002-3
[20] Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. J. Glob. Optim. 6, 109-133 (1995) · Zbl 0822.90110 · doi:10.1007/BF01096763
[21] Gaspero, L.D., Schaerf, A.: EasyLocal++: an object-oriented framework for flexible design of local search algorithms. Softw. Pract. Experience 33(8), 733-765 (2003) · doi:10.1002/spe.524
[22] Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533-549 (1986) · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
[23] Glover, F., Laguna, M.: Tabu Search. Kluwer Academic, Dordrecht (1997) · Zbl 0930.90083 · doi:10.1007/978-1-4615-6089-0
[24] Glover, F., Millan, C.M.: The general employee scheduling problem: an integration of MS and AI. Comput. Oper. Res. 13(5), 563-573 (1986) · doi:10.1016/0305-0548(86)90050-X
[25] Gu, J., Huang, X.: Efficient local search with search space smoothing: a case study of the traveling salesman problem. IEEE Trans. Syst. Man Cybern. 24(5), 728-735 (1994) · doi:10.1109/21.293486
[26] Halim, S., Yap, R.H.C., Lau, H.C.: An integrated white+black box approach for designing and tuning stochastic local search. In: 13th International Conference on Principles and Practice of Constraint Programming (CP 2007). Lecture Notes in Computer Science, vol. 4741, pp. 332-347. Springer, Berlin (2007)
[27] Hansen, P.: The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming, Congress on Numerical Methods in Combinatorial Optimization. Capri (1986)
[28] Hart, J.P., Shogan, A.W.: Semi-greedy heuristics: an empirical study. Oper. Res. Lett. 6(3), 107-114 (1987) · Zbl 0615.90082 · doi:10.1016/0167-6377(87)90021-6
[29] Hoos, H., Stützle, T.: Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, San Francisco (2004) · Zbl 1126.68032
[30] Hoos, H.H.: Programming by optimization. Commun. ACM 55(2), 70-80 (2012)
[31] Hutter, F., Hoos, H.H., Leyton-Brown, K., Stützle, T.: ParamILS: an automatic algorithm configuration framework. J. Artif. Int. Res. 36(1), 267-306 (2009) · Zbl 1192.68831
[32] Johnson, D.S.: Local optimization and the travelling salesman problem. In: 17th Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science vol. 443, pp. 446-461. Springer, Berlin (1990) · Zbl 0766.90079
[33] Jones, M.: A object-oriented framework for the implementation of search techniques. Ph.D. Thesis, University of East Anglia (2000)
[34] Jones, M., McKeown, G., Rayward-Smith, V.: Templar: a object-oriented framework for distributed combinatorial optimization. In: Proceedings of the UNICOM Seminar on Modern Heuristics for Decision Support. UNICOM Ltd, Brunel university (1998)
[35] Jones, T.: Evolutionary algorithms, fitness landscapes and search. Ph.D. Thesis, University of New Mexico, Albuquerque (1995) · Zbl 1231.90318
[36] Keijzer, M., Merelo, J.J., Romero, G., Schoenauer, M.: Evolving objects: a general purpose evolutionary computation library. In: 5th International Conference on Artificial Evolution (EA 2001), pp. 231-244. Le Creusot, France (2001) · Zbl 1054.68540
[37] Khanafer, A., Clautiaux, F., Hanafi, S., El-Ghazali, T.: The min-conflict packing problem. Comput. Oper. Res. 39, 2122-2132 (2012) · Zbl 1251.90326 · doi:10.1016/j.cor.2011.10.021
[38] Kimura, M.: The Neutral Theory of Molecular Evolution. Cambridge University Press, Cambridge (1983) · doi:10.1017/CBO9780511623486
[39] Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671-680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[40] Krasnogor, N., Smith, J.:MAFRA: A Java memetic algorithms framework. In: Data Mining with Evolutionary Algorithms, pp. 125-131. Las Vegas (2000)
[41] Lecron, F., Manneback, P., Tuyttens, D.: Exploiting grid computation for solving the vehicle routing problem. In: 2010 IEEE/ACS International Conference on Computer Systems and Applications (AICCSA), pp. 1-6 (2010)
[42] Liefooghe, A., Jourdan, L., Talbi, E.G.: A software framework based on a conceptual unified model for evolutionary multiobjective optimization: ParadisEO-MOEO. Eur. J. Oper. Res. 209(2), 104-112 (2011) · doi:10.1016/j.ejor.2010.07.023
[43] Liefooghe, A., Humeau, J., Mesmoudi, S., Jourdan, L., Talbi, E.G.: On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems. J. Heuristics 18(2), 317-352 (2012) · Zbl 1358.90046 · doi:10.1007/s10732-011-9181-3
[44] Locatelli, M.: Simulated annealing algorithms for continuous global optimization: convergence conditions. J. Optim. Theory Appl. 29(1), 87-102 (2000) · Zbl 0970.90102
[45] Lourenco, H.R., Martin, O., Stutzle, T.: Handbook of Metaheuristics, Operations Research and Management Science, vol. 57, pp. 321-353. Kluwer Academic Publishers, chap Iterated local search (2002)
[46] Lukasiewycz, M., Glaß, M., Reimann, F., Teich, J.: Opt4J—a modular framework for meta-heuristic optimization. In: Proceedings of the Genetic and Evolutionary Computing Conference (GECCO 2011). Dublin (2011)
[47] Madras, N.: Lectures on Monte Carlo Methods. American Mathematical Society, Providence (2002) · Zbl 0987.65003
[48] Marmion, M.E., Dhaenens, C., Jourdan, L., Liefooghe, A., Verel, S.: NILS: a Neutrality-based Iterated Local Search and its application to Flowshop Scheduling. In: Merz, P., Hao, J.K. (eds.) Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, vol. 6622, pp. 191-202. Springer, Turino (2011a)
[49] Marmion, M.E., Dhaenens, C., Jourdan, L., Liefooghe, A., Verel, S.: On the neutrality of flowshop scheduling fitness landscapes. In: 5th Learning and Intelligent OptimizatioN Conference (LION 5). Lecture Notes in Computer Science, vol. 6683, pp. 238-252. Springer, Rome (2011b)
[50] Marmion, M.E., Mascia, F., López-Ibáñez, M., Stützle, T. (to appear): Automatic design of hybrid stochastic local search metaheuristics. Hybrid Metaheuristics (HM 2013). Lecture Notes in Computer Science. Springer, Berlin (2013)
[51] Martin, O., Otto, S., Felten, E.W.: Large-step markov chains for the traveling salesman problem. Complex Syst. 5(3), 299-326 (1991) · Zbl 0736.90063
[52] Melab, N., Luong, T.V., Karima, B., Talbi, E.G.: Towards ParadisEO-MO-GPU: a framework for GPU-based Local Search Metaheuristics. 11th International Work-Conference on Artificial Neural Networks, Torremolinos-Málaga, Espagne. Lecture Notes in Computer Science, vol. 6691. Springer (2011)
[53] Michel, L., Hentenryck, P.V.: Localizer++: an open library for local search. Technical Report CS-01-02. Brown University, Computer Science (2001)
[54] Michel, L., See, A., Hentenryck, P.V.: Parallel and distributed local search in COMET. Comput. Oper. Res. 36(8), 2357-2375 (2009) · Zbl 1179.90288 · doi:10.1016/j.cor.2008.08.014
[55] Mladenovic, M., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24, 1097-1100 (1997) · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2
[56] Nannen, V., Eiben, A.E.: Relevance estimation and value calibration of evolutionary algorithm parameters. In: Proceedings of the 20th International Joint Conference on Artifical Intelligence, pp. 975-980. Morgan Kaufmann Publishers Inc., San Francisco, IJCAI’07 (2007) · Zbl 1179.90288
[57] Ochoa, G., Tomassini, M., Verel, S., Darabos, C.: A study of NK landscapes’ basins and local optima networks. In: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, pp. 555-562. ACM, New York (2008)
[58] Ochoa, G., Verel, S., Tomassini, M. First-improvement vs. best-improvement local optima networks of nk landscapes. In: Proceedings of the 11th International Conference on Parallel Problem Solving From Nature, Krakow, Poland, pp. 104-113.
[59] Ozdamar, L., Demirhan, M.: Experiments with new stochastic global optimization search techniques. Comput. Oper. Res. 27(9), 841-865 (2000) · Zbl 0967.90086 · doi:10.1016/S0305-0548(99)00054-4
[60] Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization Algorithms and Complexity. Prentice-Hall, Inc., Englewood Cliffs (1982) · Zbl 0503.90060
[61] Parejo, J.A., Ruiz-Cortés, A., Lozano, S., Fernández, P.: Metaheuristic optimization frameworks: a survey and benchmarking. Soft Comput. 16(3), 527-561 (2012) · doi:10.1007/s00500-011-0754-8
[62] Quick, R., Rayward-Smith, V., Smith, G.: Fitness distance correlation and ridge functions. In: Fifth Conference on Parallel Problems Solving from Nature (PPSN’98). Lecture Notes in Computer Science, vol. 1498, pp. 77-86. Springer, Heidelberg (1998)
[63] Reidys, C.M., Stadler, P.F.: Neutrality in fitness landscapes. Appl. Math. Comput. 117(2-3), 321-350 (2001) · Zbl 1113.92314 · doi:10.1016/S0096-3003(99)00166-6
[64] Rodriguez-Tello, E., Hao, J.K., Torres-Jimenez, J.: An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem. Comput. Oper. Res. 35(10), 3331-3346 (2008) · Zbl 1133.90424 · doi:10.1016/j.cor.2007.03.001
[65] Rosé, H., Ebeling, W., Asselmeyer, T.: The density of states—a measure of the difficulty of optimisation problems. Parallel Problem Solving from Nature (PPSN 1996), pp. 208-217 (1996)
[66] Rothlauf, F.: Representations for genetic and evolutionary algorithms, 2nd edn. Springer, Berlin (2006) · Zbl 1030.68083
[67] Sendhoff, B., Kreutz, M., von Seelen, W.: A condition for the genotype-phenotype mapping: causality. In: Proceedings of the 7th International Conference on Genetic Algorithms, pp. 73-80. East Lansing (1997)
[68] Stadler, P.F.: Fitness landscapes. In: Biological Evolution and Statistical Physics. Lecture Notes Physics, vol. 585, pp. 187-207. Springer, Heidelberg (2002)
[69] Stutzle, T.: Local search algorithms for combinatorial problems—analysis, algorithms and new applications. Ph.D. Thesis, DISKI—Dissertationen zur Kunstliken Intelligenz., Sankt augustin (1999) · Zbl 0995.68031
[70] Talbi, E.G.: Metaheuristics from Design to Implementation. Wiley, Chichester (2009) · Zbl 1190.90293
[71] Talbi, E.G., Hafidi, Z., Geib, J.M.: A parallel adaptive tabu search approach. Parallel comput. 24(14), 2003-2019 (1998) · Zbl 0908.68044 · doi:10.1016/S0167-8191(98)00086-6
[72] Van Nimwegen, E., Crutchfield, J., Huynen, M.: Neutral evolution of mutational robustness. Proc. Nat. Acad. Sci. USA 96, 9716-9720 (1999) · doi:10.1073/pnas.96.17.9716
[73] Verel, S.: Fitness landscapes and graphs: multimodularity, ruggedness and neutrality. In: 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference (GECCO), pp. 3593-3656. ACM, Montreal (2009)
[74] Verel, S., Collard, P., Clergue, M.: Where are bottleneck in NK fitness landscapes? In: Proceedings of the 2003 Congress on Evolutionary Computation (CEC 2003), pp. 273-280. IEEE Press, Canberra (2003)
[75] Voss, S., Woodruff, D.L.: Optimization software class librairies. Kluwer, Boston (2002) · Zbl 1055.68044
[76] Voudouris, C.: Guided local search—an illustrative example in function optimization. BT Technol. J. 16(3), 46-50 (1998) · doi:10.1023/A:1009665513140
[77] Voudouris, C., Tsang, E.: Guided local search. Eur. J. Oper. Res. 113(2), 469-499 (1999) · Zbl 0937.90094 · doi:10.1016/S0377-2217(98)00099-X
[78] Weinberger, E.D.: Correlated and uncorrelatated fitness landscapes and how to tell the difference. Biol. Cybern. 63, 325-336 (1990) · Zbl 0703.92016 · doi:10.1007/BF00202749
[79] Weinberger, E.D.: Local properties of Kauffman’s NK model, a tuneably rugged energy landscape. Phys. Rev. A 44(10), 6399-6413 (1991) · doi:10.1103/PhysRevA.44.6399
[80] White, D.R.: Software review: the ECJ toolkit. Genet. Program. Evolv. Mach. 13(1), 65-67 (2012) · doi:10.1007/s10710-011-9148-z
[81] Wilke, C.O.: Adaptative evolution on neutral networks. Bull. Math. Biol. 63, 715-730 (2001) · Zbl 1323.92144 · doi:10.1006/bulm.2001.0244
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.