Abstract
Estimation of distribution algorithms (EDAs) are a set of algorithms that belong to the field of Evolutionary Computation. Characterized by the use of probabilistic models to represent the solutions and the dependencies between the variables of the problem, these algorithms have been applied to a wide set of academic and real-world optimization problems, achieving competitive results in most scenarios. Nevertheless, there are some optimization problems, whose solutions can be naturally represented as permutations, for which EDAs have not been extensively developed. Although some work has been carried out in this direction, most of the approaches are adaptations of EDAs designed for problems based on integer or real domains, and only a few algorithms have been specifically designed to deal with permutation-based problems. In order to set the basis for a development of EDAs in permutation-based problems similar to that which occurred in other optimization fields (integer and real-value problems), in this paper we carry out a thorough review of state-of-the-art EDAs applied to permutation-based problems. Furthermore, we provide some ideas on probabilistic modeling over permutation spaces that could inspire the researchers of EDAs to design new approaches for these kinds of problems.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Agrawal, S., Wang, Z., Ye, Y.: Parimutuel betting on permutations. In: Internet and Network Economics. Lecture Notes in Computer Science, vol. 5385, pp. 126–137. Springer, Berlin (2008)
Bean C.J.: Genetic algorithms and random keys for sequencing and optimization. INFORMS J. Comput. 6(2), 154–160 (1994)
Bengoetxea E., Larrañaga P., Bloch I., Perchant A., Boeres C.: Inexact graph matching by means of estimation of distribution algorithms. Pattern Recognit. 35(12), 2867–2880 (2002)
Bosman P.A.N., Thierens D.: Expanding from discrete to continuous estimation of distribution algorithms: the IDEA. In: Schoenauer, M., Deb, K., Rudolph, G., Yao, X., Lutton, E., Guervós, J.J.M., Schwefel, H.P (eds) PPSN. Lecture Notes in Computer Science vol. 1917., pp. 767–776. Springer, Berlin (2000)
Bosman P.A.N., Thierens D. et al.: Crossing the road to efficient IDEAs for permutation problems. In: Spector, L. (eds) Genetic and Evolutionary Computation Conference, GECCO 2001, Proceedings, San Francisco, California, USA, 2001., pp. 219–226. Morgan Kaufmann, Massachusetts (2001)
Brownlee A.E.I., Pelikan M., McCall J.A.W., Petrovski A.: An application of a multivariate estimation of distribution algorithm to cancer chemotherapy. In: Ryan, C., Keijzer, M. (eds) GECCO., pp. 463–464. ACM, New York (2008)
Chen, S., Chen, M.: Bi-variate artificial chromosomes with genetic algorithm for single machine scheduling problems with sequence-dependent setup times. In: Proceedings of the Congress on Evolutionary Computation (2011)
Chow C., Liu C.: Approximating discrete probability distributions with dependence trees. IEEE Trans. Inf. Theory 14(3), 462–467 (1968)
Cohen, W.W., Schapire, R. E., Singer, Y.: Learning to order things. In: Proceedings of the 1997 Conference on Advances in Neural Information Processing Systems 10, NIPS ’97, pp. 451–457. MIT Press, Cambridge (1998)
De Bonet J.S., Isbell C.L., Viola P.: MIMIC: Finding optima by estimating probability densities. In: Mozer, M., Jordan, M., Petsche, Th (eds) Advances in Neural Information Processing Systems vol 9., MIT Press, Cambridge (1997)
Fligner A.M., Verducci S.J. Verducci: Distance based ranking Models. J. Royal Stat. Soc. 48(3), 359–369 (1986)
Garcia S., Herrera F.: An extension on “Statistical Comparisons of Classifiers over Multiple Data Set” for all pairwise comparisons. J. Mach. Learn. Res. 9, 2677–2694 (2008)
Garcia S., Molina D., Lozano M., Herrera F.: A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 Special Session on Real Parameter Optimization. J. Heuristics 15(6), 617–644 (2009)
Goldberg D.E.: Genetic algorithms in search optimization and machine learning. Addison/Wesley, Reading (1989)
Goldberg, D.E., Lingle Jr., R.: Alleles Loci and the traveling salesman problem. In: ICGA, pp. 154–159 (1985)
Guiver, J., Snelson, E.: Bayesian inference for Plackett-Luce ranking models. In: International Conference on Machine Learning (ICML 2009), ICML’09, pp. 377–384. ACM, New York (2009)
Gupta J., Stafford E.J. Stafford: Flow shop scheduling research after five decades. Eur. J. Oper. Res. 169, 699–711 (2006)
Henrion M.: Propagating uncertainty in Bayesian networks by probabilistic logic sampling. In: Lemmer, J.F., Kanal, L.N. (eds) UAI., pp. 149–164. Elsevier, Amsterdam (1986)
Hunter R.D. Hunter: MM Algorithms for generalized Bradley–Terry models. Ann. Stat. 32(1), 384–406 (2004)
Jarboui B., Eddaly M., Siarry P.: An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems. Comput. OR 36(9), 2638–2646 (2009)
Jiang S., Ziver A., Carter J., Pain C., Goddard A., Franklin S., Phillips H.: Estimation of distribution algorithms for nuclear reactor fuel management optimisation. Ann. Nuclear Energy 33(11–12), 1039–1057 (2006)
Knjazew, D., Goldberg, D.E.: Omega—ordering messy ga: solving permutation problems with the fast genetic algorithm and random keys. In: GECCO, pp. 181–188 (2000)
Koopmans, T.C., Beckmann, M.J.: Assignment problems and the location of economic activities. Cowles Foundation Discussion Papers 4, Cowles Foundation for Research in Economics, Yale University. http://ideas.repec.org/p/cwl/cwldpp/4.html (1955)
Larrañaga, P., Etxeberria, R., Lozano, J.A., Peña, J.M.: Combinatorial optimization by learning and simulation of Bayesian networks. In: Proceedings of the Conference on Uncertainty in Artificial Intelligence, UAI 2000, pp. 343–352, Stanford (2000)
Larrañaga, P., Etxeberria, R., Lozano, J.A., Peña J.M.: Optimization in continuous domains by learning and simulation of Gaussian networks. In: Proceedings of the Workshop in Optimization by Building and using Probabilistic Models. A Workshop within the 2000 Genetic and Evolutionary Computation Conference, GECCO 2000, pp. 201–204, Las Vegas (2000)
Larrañaga P., Lozano J.A.: Estimation of distribution algorithms a new tool for evolutionary computation. Kluwer, Dordrecht (2002)
Lebanon G., Mao Y.: Non-Parametric modeling of partially ranked data. J. Mach. Learn. Res. (JMLR) 9, 2401–2429 (2008)
Liu H., Gao L., Pan Q.: A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem. Expert Syst. Appl. 38, 4348–4360 (2011)
Lozano, J.A., Larrañaga, P., Inza, I., Bengoetxea, E.: Towards a new evolutionary computation: advances on estimation of distribution algorithms (Studies in Fuzziness and Soft Computing). Springer, New York (2006)
Lozano J.A., Mendiburu A.: Estimation of Distribution Algorithms applied to the job schedulling problem. In: Larrañaga, P., Lozano, J.A. (eds) Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation., pp. 1–2. Kluwer, Dordrecht (2002)
Luce R.D.: Individual Choice Behavior. Wiley, New York (1959)
Mallows L.C. Mallows: Non-null ranking models. Biometrika 44(1–2), 114–130 (1957)
Mandhani, B., Meila, M.: Tractable search for learning exponential models of rankings. In: Artificial Intelligence and Statistics (AISTATS), April (2009)
Mendiburu A., Lozano J.A., Miguel-Alonso J.: Parallel implementation of EDAs based on probabilistic graphical models. IEEE Trans. Evol. Comput. 9(4), 406–423 (2005)
Mendiburu A., Miguel-Alonso J., Lozano J.A., Ostra M., Ubide C.: Parallel EDAs to create multivariate calibration models for quantitative chemical applications. J. Parallel Distrib. Comput. 66(8), 1002–1013 (2006)
Mühlenbein, H., Paaß, G.: From recombination of genes to the estimation of distributions I. Binary parameters. In: Lecture Notes in Computer Science 1411: Parallel Problem Solving from Nature—PPSN IV, pp. 178–187 (1996)
Pelikan, M., Goldberg, D.E.: Hierarchical problem solving and the Bayesian optimization algorithm. In: Whitley, D., Goldberg, D.E., Cantú-Paz, E., Spector, L., Parmee, I., Beyer, H.G. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco, vol. 1, pp. 267–274. Morgan Kaufmann Publishers, Menlo Park (2000)
Pelikan M., Goldberg D.E., Lobo F.G.: A survey of optimization by building and using probabilistic models. Comput. Optim. Appl. 21(1), 5–20 (2002)
Pelikan, M., Sastry, K., Cantú-Paz, E.: Scalable optimization via probabilistic modeling: from algorithms to applications (Studies in Computational Intelligence). Springer, New York (2006)
Pelikan, M., Tsutsui, S., Kalapala, R.: Dependency trees, permutations, and quadratic assignment problem. Technical report, Medal Report No. 2007003 (2007)
Plackett R.L.: The analysis of permutations. J. Royal Stat. Soc. 24(10), 193–202 (1975)
Robles V., de Miguel P., Larrañaga P.: Solving the traveling salesman problem with EDAs. In: Larrañaga, P., Lozano, J.A. (eds) Estimation of distribution algorithms a new tool for evolutionary computation., Kluwer, Dordrecht (2002)
Romero T., Larrañaga P.: Triangulation of Bayesian networks with recursive estimation of distribution algorithms. Int. J. Approx. Reason. 50(3), 472–484 (2009)
Sagarna R., Lozano J.A.: Scatter Search in software testing, comparison and collaboration with estimation of distribution algorithms. Eur. J. Oper. Res. 169(2), 392–412 (2006)
Santana R., Larrañaga P., Lozano J.A.: Protein folding in simplified models with estimation of distribution algorithms. IEEE Trans. Evol. Comput. 12(4), 418–438 (2008)
Tsutsui, S.: Probabilistic model-building genetic algorithms in permutation representation domain using edge histogram. In: PPSN, pp. 224–233 (2002)
Tsutsui, S.: A comparative study of sampling methods in node histogram models with probabilistic model-building genetic algorithms. In: IEEE International Conference on Systems, Man, and Cybernetics. 8–11 October 2006, Taipei, vol. 4, pp. 3132–3137 (2006)
Tsutsui, S.: Effect of using partial solutions in edge histogram sampling algorithms with different local searches. In: SMC, pp. 2137–2142 (2009)
Tsutsui, S., Miki, M.: Solving flow shop scheduling problems with probabilistic model-building genetic algorithms using edge histograms. In: 4th Asia-Pacific Conference on Simulated Evolution And Learning (SEAL 02), pp. 776–780 (2002)
Tsutsui, S., Pelikan, M., Goldberg, D.E.: Using edge histogram models to solve permutation problems with probabilistic model-building genetic algorithms. Technical report, IlliGAL Report No. 2003022 (2003)
Tsutsui, S., Pelikan, M., Goldberg, D.E.: Node histogram vs. edge histogram: a comparison of PMBGAs in permutation domains. Technical report, Medal (2006)
Tsutsui, S., Wilson, G.: Solving capacitated vehicle routing problems using edge histogram based sampling algorithms. In: Proceedings of the IEEE Conference on Evolutionary Computation, Portland, Oregon (USA), pp. 1150–1157 (2004)
Yuan, B., Orlowska, M.E., Sadiq, S.W.: Finding the optimal path in 3d spaces using EDAs—the wireless sensor networks scenario. In: ICANNGA (1), pp. 536–545 (2007)
Zhang, Q., Sun, J., Tsang, E., Ford, J.: Combination of guided local search and estimation of distribution algorithm for solving quadratic assignment problem. In: Proceedings of the Bird of a Feather Workshops, Genetic and Evolutionary Computation Conference, pp. 42–48 (2004)
Zhang, Q., Sun, J., Tsang, E., Ford, J.: Estimation of distribution algorithm with 2-opt local search for the quadratic assignment problem. Stud. Fuzziness Soft Comput. 192/2006:281–292 (2006)
Zhigljavsky A.A.: Theory of Global Random Search. Kluwer, Dordrecht (1991)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ceberio, J., Irurozki, E., Mendiburu, A. et al. A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems. Prog Artif Intell 1, 103–117 (2012). https://doi.org/10.1007/s13748-011-0005-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13748-011-0005-3