Hibridización entre un Algoritmo Evolutivo y un Algoritmo de Estimación de Distribuciones para la solución de FSSP

• Autores: Daniel Raul Pandolfi, Andrea Villagra, Guillermo N. Leguizamón
• Localización: Ciencia y tecnología, ISSN 1850-0870, ISSN-e 2344-9217, Nº. 9, 2009
• Idioma: español
• DOI: 10.18682/cyt.v1i1.783
• Enlaces
  • Texto completo
• Resumen
  • español

    Los Algoritmos Evolutivos (AEs) son una de las metaheurísticas más ampliamente estudiadas. Éstas, pueden sermejoradas en su diseño a fin de realizar una exploración más eficiente del espacio de búsqueda. A su vez, losalgoritmos de Estimación de Distribuciones (EDAs) son una clase de algoritmos basados en el paradigma deComputación Evolutiva que sustituyen los mecanis mos de variación, utilizados en AEs, por la generación deindividuos generados a través de la información producida de la simulación de una distribución de probabilidad.El problema de secuenciamiento de Flow Shop (FSSP) ha convocado la atención de muchos investigadores en losúltimos años. Para la resolución del FSSP y con el objetivo de mejorar la eficiencia de la búsqueda como así elesfuerzo computacional requerido, este trabajo propone un algoritmo híbrido entre estos dos enfoques. Detalles de laimplementación como así las mejoras obtenidas serán discutidas.

  • English

    The Evolutionary Algorithms (EAs) are one of the broadly studied metaheuristics. They can be improved in their design in order to carry out a more efficient exploration of the search space. In turn, the Estimation of Distribution Algorithms (EDAs) are a kind of algorithms based on the Evolutionary Computation paradigm that substitute the variation mechanisms used in EAs by the generation of individuals generated through the produced information of the simulation of a probability distribution.

    The Flow Shop Scheduling Problem (FSSP) has summoned the attention of many researchers in the last years. For the resolution of the FSSP and with the objective of improving the efficiency of the search as well as the computational effort required, this work proposes a hybrid algorithm among these two approaches. Detail of the implementation as well as the obtained improvements will be discussed.

• Referencias bibliográficas
  • Bäck T. “Evolutionary Algorithms in theory and practic”. New York:Oxford University Press, (1996).
  • Baluja, “Population-based incremental learning: A method for integrating genetic search based function optimizationn and competitive learning”....
  • Bosman A.N. and Thierens. D.; “Linkage information processing in distribution estimation algorithms ”. In Proceedings of the Genetic and Evolutionary...
  • Branke J., Mattfeld D.; “Anticipation in Dynamic Optimization: The Scheduling Case”. Procedings of VI PPSN, pp 253-262, (2000).
  • Brucker P., “Scheduling Algorithms ”, 3rd ed. Springer-Verlag New York, (2004).
  • Burke E.K., De Causmaecker P., Petrovic S., Vanden Berghe G., “Fitness Evaluation fon Nurse Scheduling Problems ”, Proc Congress on Evolutionary...
  • Campbell H., Dudek R., Smith M., “A heuristic algorithm for the n job m machine sequencing problem”, Management Science 16, pp. 630-637 (1970).
  • Cook S.A. “The complexity of theorem-proving procedures”, Procedings of 3rd Annual ACM Symposium on Theory of Computing, Association for Computing...
  • Cowling P. Kendall G. Han L.; “An Investigation of a Hyperheuristic Genetic Algorithm Applied to a Trainer Scheduling Problem”, Proc Congress...
  • Davis L., “Handbook of Genetic Algorithms ”, New York: Van Nostrand Reinhold Computer Library, (1991).
  • De Bonet J. S., Isbell C. L., and Viola P.; “MIMIC:Finding optima by estimating probability densities”. Advances in Neural Information Processing...
  • Garey R., Johnson D.; “Computers and Intractability: A Guide to the Theory of NP-Completeness”. Freemann & Co., San Francisco, CA, (1979).
  • Goldberg, D. and Lingle R.; “Alleles, loci and the traveling salesman problem”, in Proceeding of the First International Conference on Genetic...
  • Grefenstette J. J., Gopal R., Rosmaita B., Van Gutch D.; “Genetic Algorithm for the TSP”; Proceedings of the st Int. Conf. on Genetic Algorithms,...
  • Gupta J., “A functional heuristic algorithm for the flowshop scheduling problem”, Operational Research Quarterly 22, pp. 39-48 (1971).
  • Jackson J. R.; “Scheduling a production line to minimize maimum tardiness”, Research Report 43, Management Science Research Project, University...
  • Johnson S. M. “Optimal two and three stage production”; Naval Research Logistics Quaterly, 1, pp 61-67, (1954).
  • Larrañaga P. and Lozano J.A.; “Estimation of Distribution Algorithms ”. A New Tool for Evolutionary Computation. Kluwer Academic Publishers,...
  • Lenstra J. K., Rinnooy Kan A. H., “Computational complexity of scheduling under precedence contrains”, Operations Research, 26, pp 22-35,...
  • Leung Joseph. “Handbook of Scheduling: Algorithms, Models and Performance Analysis ”, Chapman & Hall/CCR Computer and Information Sciences...
  • Madera J., Dorronosoro B.; “Estimation of distribution algorithms, Metaheurístic procedures for training neural networks”; Springer Science...
  • Morton T., Pentico D., “Heuristic scheduling systems”, Wiley series in Engineering and technology management. John Wiley and Sons, INC (1993).
  • Mühlenbein H., Mahnig T., and Ochoa A.; “Schemata, distributions and graphical models in evolutionary optimization”. Journal of Heuristics,...
  • Mühlenbein H. and Paaß G.; “From recombination of genes to the estimation of distributions I. Binary parameters”. In Lecture Notes in Computer...
  • Mühlenbein H. and Voigt H.M.; “Gene pool recombination in genetic algorithms ”. Metaheuristics: Theory and applications, pp 53–62, (1996).
  • Nawaz M., Enscore E., Ham I., “A heuristic algorithm for the m-machine n-job flow shop sequencing problem”. Omega vol II, pp 11-95 (1983).
  • Oliver, I., Smith D., and Holland J.; “A study of permutation crossover operators on the traveling salesman problem”, in European Journal...
  • Palmer D., “Sequencing jobs through a multistage process in the minimum total time - A quick method of obtaining a near optimum”, Operational...
  • Pinedo M.; “Scheduling- Theory, Algorithms, and Systems. Prentice Hall International in Industrial and System Engineering (1995).
  • Reeves C., “A genetic algorithm for flow shop sequencing”, Computers and Operations Research, 22, pp 5-13 (1995).
  • Syswerda G.; “Schedule optimization using genetic algorithms ”, Handbook of Genetic Algorithms , Van Nostrand Reinhold, New York, 21, pp 332-349....
  • Taillard, E. “Benchmarks for basic scheduling problems ”, European Journal of Operational Research, 64, pp -285 (1993).
  • Tsujimura Y., Gen M., Kubota E., “Flow shop scheduling with fuzzy processing time using genetic algorithms ”. The 11th Fuzzy Systems Symposium...