The Design of Self-evolving Artificial Immune System II for Permutation Flow-shop Problem

Authors: Meng-Hui Chen, Pei-Chann Chang, Wei-Hsiu Huang

Abstract:

Artificial Immune System is adopted as a Heuristic Algorithm to solve the combinatorial problems for decades. Nevertheless, many of these applications took advantage of the benefit for applications but seldom proposed approaches for enhancing the efficiency. In this paper, we continue the previous research to develop a Self-evolving Artificial Immune System II via coordinating the T and B cell in Immune System and built a block-based artificial chromosome for speeding up the computation time and better performance for different complexities of problems. Through the design of Plasma cell and clonal selection which are relative the function of the Immune Response. The Immune Response will help the AIS have the global and local searching ability and preventing trapped in local optima. From the experimental result, the significant performance validates the SEAIS II is effective when solving the permutation flows-hop problems.

Keywords: Artificial Immune System, Clonal Selection, Immune Response, Permutation Flow-shop Scheduling Problems

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062952

References:

[1] J. T. Tsai, W. H. Ho, T. K. Liu, and J. H. Chou, "Improved immune algorithm for global numerical optimization and job-shop scheduling problems," Applied Mathematics and Computation, Vol. 194, pp. 406-424, Dec. 2007.
[2] J. S. Chun, H. K. Jung and S. Y. Hahn, "A Study on Comparison of Optimization Performances between Immune Algorithm and other Heuristic Algorithms," IEEE Transactions on Magnetics, vol. 34, No. 5, Sept. 1998.
[3] J. H. Holland, "Genetic Algorithms and the Optimal Allocation of Trials," SIAM J. Comput, vol. 2, pp. 88-105, 1973.
[4] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning (Book style). Boston, MA: Addison-Wesley, 1989.
[5] F. Campelo, F. G. Guimar˜aes, and H. Igarashi, "Overview of Artificial Immune Systems for Multi-objective Optimization," Lecture Notes in Computer Science, vol. 4403 , pp. 937-951, 2007.
[6] P. C. Chang, W. H. Huang, and C. J. Ting, "A hybrid genetic-immune algorithm with improved lifespan and elite antigen for flow-shop scheduling problems," International Journal of Production Research, vol. 49, pp. 937-951, Sept. 2007.
[7] K. C. Tan, C. K. Goh, A. A. Mamun, and E. Z. Ei, "An evolutionary artificial immune system for multi-objective optimization," European Journal of Operational Research, vol. 187, pp. 371-392, Jun. 2008.
[8] T. Bagchi, Multiobjective Scheduling by Genetic Algorithms (Book style). New York, 1999.
[9] C. R. Reeves, "A Genetic Algorithm for Flowshop Sequencing," Computers and Operations Research, vol. 5, pp. 5-13, Jan. 1995.
[10] J. D. Farmer, N. Packard, and A. Perelson, "The immune system, adaptation and machine learning," Physica D, vol. 2, pp. 187-204, Oct.-Nov. 1986.
[11] H. Bersini, and F. J. Varela, "Hints for adaptive problem solving gleaned from immune networks," Parallel Problem Solving from Nature, vol. 496, pp. 343-354, 1991.
[12] J. O. Kephart, "A biologically inspired immune system for computers," Proceedings of Artificial Life IV: The Fourth International Workshop on the Synthesis and Simulation of Living Systems, MIT Press. pp. 130-139, 1994.
[13] D. Dasgupta, Artificial Immune Systems and Their Applications (Book style). Berlin : Springer-Verlag, Jan. 1999.
[14] L. N. de Castro and F. J. Von Zuben, Artificial Immune Systems: Part I -Basic Theory and Applications (Book style). Brazil, 1999.
[15] V. Cutello and G. Nicosia, "An Immunological Approach to Combinatorial Optimization Problems," Lecture Notes in Computer Science, vol. 2527, pp. 361-370, 2002.
[16] V. Cutello, G. Nicosia, M. Pavone, and J. Timmis, "An Immune Algorithm for Protein Structure Prediction on Lattice Models," IEEE Transactions on Evolutionary Computation, vol. 11 , pp. 101-117, 2007.
[17] J. Zhang, C. Zhang, and S. Liang, "The circular discrete particle swarm optimization algorithm for flow shop scheduling problem," Expert Systems with Applications, vol. 37, pp. 5827-5834, 2010.
[18] P. C. Chang, W. H. Huang, and C. J. Ting, "Self-evolving Artificial Immune System via Developing T and B Cell for Permutation Flow-shop Scheduling Problems," Proceedings of World Academy of Science, Engineering and Technology, vol. 65, pp. 822-827, May 2010.