Advertisement

Learning with Delayed Rewards in Ant Systems for the Job-Shop Scheduling Problem

  • Urszula Boryczka
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 1424)

Abstract

We apply the idea of learning with delayed rewards to improve performance of the Ant System. We will mention different mechanisms of delayed rewards in the Ant Algorithm (AA). The AA for JSP was first applied in classical form by A. Colorni and M. Dorigo. We adapt an idea of an evolution of the algorithm itself using the methods of the learning process. We accentuate the co-operation and stigmergy effect in this algorithm. We propose the optimal values of the parameters used in this version of the AA, derived as a result of our experiments.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. [BORY97]
    Boryczka M., Boryczka U.: Generative policies in ant system. In: Proceedings of the EUFIT’97 Conference, Aachen, September, 1997, 857–861.Google Scholar
  2. [COLO92]
    Colorni A., Dorigo M., Maniezzo U.: An Investigation of same Properties of an Ant Algorithm. In: Proceedings of the Parallel Problem Solving from Nature Conference (PPSN 92), Brussels, Belgium, Elsevier Publishing, 1992.Google Scholar
  3. [COLO94]
    Colorni A., Dorigo M., Maniezzo U., Trubian M.: Ant system for Job-shop Scheduling, Belgian Journal of Operations Research, Statistic and Computer Science, 1994.Google Scholar
  4. [DORI94]
    Dorigo M., Bersini H.: A comparison of Q-learning and classifier systems. In: Proceedings of From Animats to Animals Third International Conference on Simulation of Adaptive Behavior (SAB 94), Brighton UK, August 8–12, 1994.Google Scholar
  5. [GAMB95]
    Gambarella L.M., Dorigo M.: AntQ: A Reinforcement Learning approach to the travelling salesman problem. Proceedings of ML-95, Twelfth International Conference On Machine Learning, Morgan Kaufmann Publishers, 1995, 252–260.Google Scholar
  6. [GRAH79]
    Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5 (1979), 287–326.zbMATHCrossRefMathSciNetGoogle Scholar
  7. [MICH96]
    Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs. Berlin: Springer Verlag, 1996.zbMATHGoogle Scholar
  8. [SING97]
    Singh S., Norving P., Cohn D.: Agents and Reinforcement Learning. Dr. Dobb’s Journal, March, 1997.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1998

Authors and Affiliations

  • Urszula Boryczka
    • 1
  1. 1.Institute of Computer ScienceUniversity of SilesiaSosnowiecPoland

Personalised recommendations