Self-evolving Artificial Immune System via Developing T and B Cell for Permutation Flow-shop Scheduling Problems

Authors: Pei-Chann Chang, Wei-Hsiu Huang, Ching-Jung Ting, Hwei-Wen Luo, Yu-Peng Yu

Abstract:

Artificial Immune System is applied as a Heuristic Algorithm for decades. Nevertheless, many of these applications took advantage of the benefit of this algorithm but seldom proposed approaches for enhancing the efficiency. In this paper, a Self-evolving Artificial Immune System is proposed via developing the T and B cell in Immune System and built a self-evolving mechanism for the complexities of different problems. In this research, it focuses on enhancing the efficiency of Clonal selection which is responsible for producing Affinities to resist the invading of Antigens. T and B cell are the main mechanisms for Clonal Selection to produce different combinations of Antibodies. Therefore, the development of T and B cell will influence the efficiency of Clonal Selection for searching better solution. Furthermore, for better cooperation of the two cells, a co-evolutional strategy is applied to coordinate for more effective productions of Antibodies. This work finally adopts Flow-shop scheduling instances in OR-library to validate the proposed algorithm.

Keywords: Artificial Immune System, Clonal Selection, Flow-shop Scheduling Problems, Co-evolutional strategy

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

References:

[1] F. Campelo, F. G. Guimar˜aes, and H. Igarashi, "Overview of Artificial Immune Systems for Multi-objective Optimization," EMO 2007, Lecture Notes in Computer Science, pp. 937-951, 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, September 1998.
[3] J. T. Tsai, W. H. Ho, and T. K. Liu, and J. H. Chou, "Improved immune algorithm for global numerical optimization and job-shop scheduling problems," Applied Mathematics and Computation 194 (2007) pp. 406-424, 2007.
[4] V. Cutello, G. Nicosia, M. Pavone, J. Timmis, "An Immune Algorithm for Protein Structure Prediction on Lattice Models," IEEE Transactions on Evolutionary Computation, vol. 11, no. 1, pp. 101-117, 2007.
[5] 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.
[6] L. N. de Castro, J. Timmis, "Artificial Immune Systems: A New Computational Intelligence Approach," Springer. pp. 57-58, 2002.
[7] C.A.C. Coello, N.C. Cortés, "Hybridizing A Genetic Algorithm with An Artificial Immune System for Global Optimization," Engineering Optimization, Volume 36, Number 5, pp. 607-634(28), 2004.
[8] J. D. Farmer, N. Packard, A. Perelson, "The immune system, adaptation and machine learning," Physica D, vol. 2, pp. 187-204, 1986.
[9] H. Bersini, F. J. Varela, "Hints for adaptive problem solving gleaned from immune networks," Parallel Problem Solving from Nature, vol. 496, pp. 343-354, 1991.
[10] P.C. Chang, S.H. Chen and K.L. Lin, " Two Phase Sub-Population Genetic Algorithm for Parallel Machine Scheduling problem" Expert Systems with Applications, vol. 29(3), pp. 705-712, 2005.
[11] S. H. Chen, "The Self-Guided Genetic Algorithm," PhD thesis, Yuan Ze University, Taoyuan, 2008.
[12] D. Dasgupta (Editor), "Artificial Immune Systems and Their Applications," Springer-Verlag, Inc. Berlin, January 1999.
[13] C. R. Reeves, "A Genetic Algorithm for Flowshop Sequencing," Computers and Operations Research, vol. 5, pp. 5-13, 1995.
[14] T. Bagchi, "Multiobjective Scheduling by Genetic Algorithms," Springer ,1999.
[15] K. Baker, "Introduction to sequencing and scheduling," Wiley, 1974.
[16] J. Framinan, J. Gupta, R. Leisten, "A review and classification of heuristics for permutation flow-shop scheduling with makespan objective," Journal of the Operational Research Society, vol. 55(12), pp.1243-1255, 2004.
[17] D. Zheng, L. Wang, "An Effective Hybrid Heuristic for Flow Shop Scheduling," The International Journal of Advanced Manufacturing Technology, vol. 21(1), pp. 38-44, 2003.
[18] S. R. Hejazi, S. Saghafian, "Flowshop-scheduling problems with makespan criterion: a review," International Journal of Production Research, vol. 43(14), pp. 2895-2929, 2005.
[19] R. Ruiz, C. Maroto, "A comprehensive review and evaluation of permutation flowshop heuristics," European Journal of Operational Research, vol. 165(2), pp. 479-494, 2005.
[20] C. Reeves, T. Yamada, "Genetic Algorithms, Path Relinking, and the Flowshop Sequencing Problem," Evolutionary Computation, vol. 6(1), pp. 45-60, 1998.
[21] S. Iyer, B. Saxena, "Improved genetic algorithm for the permutation flowshop scheduling problem," Computers and Operations Research, vol. 31(4), pp. 593-606, 2004.
[22] X. Wang, T. C. E. Cheng, "A heuristic approach for tow-machine no-wait flowshop scheduling with due dates and class setups," Computers and Operations Research, vol. 33(5), pp. 1326-1344, 2006.
[23] A. Jaszkiewicz, "Genetic local search for multi-objective combinatorial optimization," European Journal of Operational Research, vol. 137(1), pp. 50-71, 2002.
[24] H. Ishibuchi, T. Yoshida, T. Murata, "Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling," Evolutionary Computation, IEEE Transactions on vol. 7(2), pp. 204-223, 2003.
[25] T. Muruta, H. Ishibuchi, "Performance evolution of genetic algorithms for flowshop scheduling problems," Proceedings of First IEEE International Conference on Evolutionary Computation, 1994.
[26] C. L. Chen, R. V. Neppalli, N. Aljaber, "Genetic algorithms applied to the continuous flow shop problem," Computers & Industrial Engineering, vol. 30(4), pp. 919-929, 1996.
[27] P. C. Chang, J. C. Hsieh, C. H. Liu, "A case-injected genetic algorithm for single machine scheduling problems with release time," International Journal of Production Economics, vol. 103(2), pp. 551-564, 2006.
[28] P. C. Chang, S. H. Chen, V. Mani, "Parametric Analysis of Bi-criterion Single Machine Scheduling with a Learning Effect," International Journal of Innovative Computing, Information and Control, vol. 4(8), pp. 2033-2043, 2008.
[29] V. Cutello and G. Nicosia, "An Immunological Approach to Combinatorial Optimization Problems," Lecture Notes in Computer Science, Springer vol. 2527, pp. 361-370, 2002.
[30] L. N. de Castro and F. J. Von Zuben, "Artificial Immune Systems: Part I -Basic Theory and Applications," School of Computing and Electrical Engineering, State University of Campinas, Brazil, No. DCA-RT 01/99, 1999.
[31] J. H. Holland, "Genetic Algorithms and the Optimal Allocation of Trials,". SIAM J. Comput, vol. 2(2), pp. 88-105, 1973.
[32] D. E. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning," Addison-Wesley, Reading, MA , 1989.