Hibridización entre un Algoritmo Evolutivo y un Algoritmo de Estimación de Distribuciones para la solución de FSSP
Resumen
Los Algoritmos Evolutivos (AEs) son una de las metaheurísticas más ampliamente estudiadas. Éstas, pueden ser
mejoradas en su diseño a fin de realizar una exploración más eficiente del espacio de búsqueda. A su vez, los
algoritmos de Estimación de Distribuciones (EDAs) son una clase de algoritmos basados en el paradigma de
Computación Evolutiva que sustituyen los mecanis mos de variación, utilizados en AEs, por la generación de
individuos 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í el
esfuerzo computacional requerido, este trabajo propone un algoritmo híbrido entre estos dos enfoques. Detalles de la
implementación como así las mejoras obtenidas serán discutidas.
Descargas
Citas
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”. Technical Report CMU-CS, pp. 94-163, Carnegie Mellon University,
(1994).
Bosman A.N. and Thierens. D.; “Linkage information processing in distribution estimation algorithms ”. In
Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99, 1, pp 60–67. Morgan
Kaufmann Publishers, San Francisco, LA. (1999).
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 Computation, CEC2001, Seoul, IEEE Press, pp 1139-1146, (2001).
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 Machinery, New York, pp 151-158 (1971).
Cowling P. Kendall G. Han L.; “An Investigation of a Hyperheuristic Genetic Algorithm Applied to a Trainer
Scheduling Problem”, Proc Congress on Evolutionary Computation, CEC2002, Hawaii, IEEE Press, pp 1185-
, (2002).
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 Systems, 9. (1997).
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 Algorithms, Lawrence Eribaum Associates, pp. 154-159, Hillsdale, NJ,
(1987).
Grefenstette J. J., Gopal R., Rosmaita B., Van Gutch D.; “Genetic Algorithm for the TSP”; Proceedings of the
st Int. Conf. on Genetic Algorithms, Pittsburgh , PA. (1991).
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 of California; Los Angeles, (1955).
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, (2002).
Lenstra J. K., Rinnooy Kan A. H., “Computational complexity of scheduling under precedence contrains”,
Operations Research, 26, pp 22-35, (1978).
Leung Joseph. “Handbook of Scheduling: Algorithms, Models and Performance Analysis ”, Chapman &
Hall/CCR Computer and Information Sciences Series (2004).
Madera J., Dorronosoro B.; “Estimation of distribution algorithms, Metaheurístic procedures for training neural
networks”; Springer Science and Business Media, (2006).
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, 5, pp 215–247, (1999).
Mühlenbein H. and 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).
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 of Operational Research, pp. 224-230 (1986).
Palmer D., “Sequencing jobs through a multistage process in the minimum total time - A quick method of
obtaining a near optimum”, Operational Research Quarterly 16, pp 101-107 (1965).
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. 1991.
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 pp 248-252. Okinawa (1995).
Los artículos publicados en la Revista Ciencia y Tecnología son de exclusiva propiedad de sus autores. Las opiniones y el contenido de los mismos pertenecen a sus autores, declinando la Universidad de Palermo toda responsabilidad por los derechos que pudiera derivarse de la lectura y/o interpretación del contenido de los artículos publicados.
No se autoriza la reproducción, utilización ni explotación por parte de ningún tercero de los artículos publicados. Sólo se autoriza su uso para fines exclusivamente académicos y/o de investigación.
