摘要
许多实际工程问题可以抽象为相应的函数优化问题。目前己经有很多启发式算法用于解决函数优化问题。遗传算法就是其中的一种，但由于在实际应用中遗传算法早熟收敛，收敛速度慢的现象时有发生，这在一定程度上限制了遗传算法的发展和应用。而免疫系统是一个分布式、自组织和具有动态平衡能力的自适应复杂系统。人工免疫系统是与生物免疫系统相对应的工程概念，人们从免疫系统中提取、发现有用机制用来解决工程和科学问题，研究如何根据免疫优化理论以及模拟生物免疫优化行为来设计新的有效优化算法是非常有意义的科研课题。
本文首先回顾了进化算法的发展历程，尤其是遗传算法分支领域。然后详细介绍了自然免疫系统基本原理、人工免疫系统及各种免疫算法。其中克隆选择原理是人工免疫系统中非常重要的一个原理，由此启发而得出的免疫算法，能够比较好地解决函数优化问题。最后在分析克隆选择算法的优越性与其不足的基础上，借鉴自然界共享小生境机制，提出了对克隆选择算法的改进算法——基于小生境的克隆选择算法。
针对克隆选择算法的漏峰问题，小生境克隆选择算法重新设计了评价函数。本文通过引入共享函数来确定群体中个体之间的物种相似度，再以共享函数为基础设计评价函数，替代原先简单的以适应度值为唯一标准的评价函数，对群体中聚集成小块的个体可以通过施加共享函数进行惩罚，使其适应值减小，这样就使得小规模物种的被选择概率会比适应值共享之前有所提高，从而维护群体中小规模低适应度物种生存，使其也能顺利进入下一代。小生境技术通过维护群体中小规模低适应度物种的生存，增加了物种多样性，使群体向优质个体分布良好的方向进化。
最后经过测试，表明该改进算法与标准遗传算法和克隆选择算法相比，具有快速收敛、全局寻优能力强、增加种群多样性等优点。针对算法中的某些步骤和参数，通过实验统计结果给出合理调整。
总之，优化问题是一个古老的问题，同时它也是一个困难的问题，而自然界中包含着丰富有效的信息处理机制。我们可以模拟自然进化原理与机制，模拟生物智能的生成过程，并用以求解问题，进而融合数学、生物、计算机技术等各个领域的原理与技巧，使所设计的算法策略更为有效。这是当前国际计算智能研究领域的热点之一。本文将生物免疫和生物小生境技术相结合，建立了新型算法模型，而深入研究其理论基础和开拓算法的应用领域将是我们下一步的研究重点和发展方向。
Many practical problems can be formulated as problems of optimizing functions for which there are numerous heuristic algorithms so far. The genetic algorithm is one of such algorithms. However, the development and applications of the genetic algorithm are to certain extent limited by its premature convergence and low convergent speed that occur frequently in applications of this algorithm. But the immune system is a distributed, self-adapted complex system. Form such a system, useful strategies can be found to solve problems in engineering and sciences. And it is a significant subject to design effective algorithms for optimization problems by simulating biological immune activities.
In this paper, we first review the development of the evolutionary algorithms, in particular of the genetic algorithm. Following this, we describe the basic principles of natural immune systems, the artificial immune system and various kinds of immune algorithms. Among these principles, the clonal selection principle is the most important for the artificial immune system. The immune algorithm can be derived from this principle and used to solve the problems of optimizing functions in an effective way. Finally, on the basis of analyzing the advantages and disadvantages and by referring to the natural sharing niche mechanism, we present for the clonal selection algorithm an improved algorithm called niche clonal selection algorithm.
The niche clonal selection algorithm is an algorithm that redesigns the evaluation function with regard to "peak leaking" in the clonal selection algorithm. This paper will first introduce the sharing function to determine species similarity between the individuals of a community, and then use this function as a basis to design the evaluation function in place of the original simple evaluation function that is based on the fitness value as its sole standard. For the individuals of the community that gather into a scrap, the fitness value is reduced by applying the sharing function to penalize the scrap; thus the probability of selection is enhanced for this small-scale species, and is greater than the probability when the original adaptation value is shared. Hence it is possible for the small-scale species with low fitness to survive and to enter into the next generation smoothly. In this way, the niche technology will increase the diversity of the species and cause community to evolve in the direction of individual distributions with high qualities.
Finally, after the experiment, it indicates that, compared with the standard genetic algorithm and the clonal selection algorithm, the improvement algorithm has the superiority of rapid convergence, strong ability for overall situation optimization and increase in population diversity. In view of some steps and parameter, it will give reasonable adjustment counting on the experiment result.
In sum, optimization is an old and difficult problem. And the nature abounds with effective information-processing mechanisms. Therefore, we can simulate the principle and mechanism of natural evolution and the process of the development of biological intelligence in order to solve problems and take a step further to integrate the principles and techniques from mathematics, biology, and computer science so that the algorithms designed are more effective. This is one of the focuses in the international research on computer intelligence. We will combine the biological immune and the niche technology to develop new models for algorithms in this paper. And in the future, the theoretical bases will be explored and the applications will be extended.
引文
[1] Chun Jang-Sung, KimMin-Kyu, Jang Hyun-Kyo. Shape optimization of electromagnetic devices using immue algorithm [J]. IEEE Transaction on Magnetics, 1997, 33 (2): 1876-1879
[2] Wolpert D. H., Maceady W. G., No Free Lunch Theorems for Search. IEEE Transactions on Evolutionary Computation. 1997, 1(1): 67-82
[3] D.B.Fogel and L.J.Fogel eds.: Special Issue on Evolutionary Computation, IEEE Transactions on Neural Networks, Vol.5, No. 1, 1-148, 1994
[4] 周家驹，何险峰译，演化程序-遗传算法和数据编码的结合[M]，北京，科学出版社，2000
[5] 丁永生，计算智能-理论、技术与应用[M]，科学出版社，上海市研究生教学用书
[6] J. Holland, Adaptation in natural and artificial systems, Ann. Arbor: The University of Michigan Press, 1975, MIT Press, 1992
[7] De Jong K A. An Analysis of the Behavior of a Class of Genetic Adaptive System:[ph D Dissertation]. University of Michigan, No.76-9381, 1975
[8] Bagley J D. The Behavior of Adaptive System which Employ Genetic and Correlations Algorithm: [Ph D Dissertation]. University of Michigan, No. 68-7556,1976
[9] Cavicchio D J. Adaptive Search Using Simulated Evolution: Doctoral Dissertation. University of Michigan, Ann, Arbor, 1970
[10] Hollstien R B. Aritifical Genetic Adaptation in Computer Control Systems:[Ph D Dissertation]. University of Michigan, No. 71-23773,1971
[11] 张可村，工程优化的算法与分析[M]，西安交通大学出版社，249-261，1988．1
[12] 王小平，曹立明，遗传算法-理论、应用与软件实现[M]，第1版，西安，西安交通大学出版社，2002
[13] D. Dasgupta. An Overview of Artificial Immune Systems and their Applications . D. Dasgupta. Artificial Immune Systems and their Applications.S pringer-Verlag, 1998: 3-22
[14] P. M．利迪亚德，A．惠兰，M．W．范杰，林慰慈，薛彬，魏雪涛，免疫学[M]，第1版，科学出版社，2001
[15] 葛红，免疫算法及核聚类人工免疫网络应用研究[D]，华南理工大学博士论文，2003
[16] 刘克胜，人工免疫模型及其应用[D]，中国科学技术大学博士学位论文，2000，12-14
[17] 莫宏伟，人工免疫系统原理与应用[M]，哈尔滨工业大学出版社，2003．1～390
[18] 龚非力，医学免疫学[M]，北京：科学出版社，2003．1．1～27
[19] Ge Hong, Mao Zong-Yuan. Immune Algorithm, Proceedings of the 4th World Congress on Intelligent Control and Automation. 2002.6. 1784～1787
[20] 付朋辉，基于免疫原理的遗传算法及其在优化问题中的应用[D]，武汉大学硕士学位论文，2003，3-28
[21] Forrest S. Hofmeyr S A., Immunology as information processing. Design Principles for Immune System & Other Distributed Autonomous Systems. L.A.Segel and I. R. Cohen, eds. Oxford Univ. Press 2000
[22] Burnet F M. The Clonal Selection Theory of Acquired Immunity. Cambridge University Press. 1959. 1～50
[23] Jerne N K. Towards a Network Theory of the Immune System[J]. Annual Immunology. 1974. 373～389
[24] 罗小平，人工免疫遗传学习算法及其工程应用研究[D]，浙江大学，2002．7
[25] 漆安慎，杜婵英，免疫的非线性模型[M]，上海：上海科技教育出版社，1998．1～46
[26] Farmer, J. D., Packard, N. H. & Perelson, A. S. (1986), "The Immune System, Adaptation, and Machine Learning."[J], Physica 22D, pp 187-204.
[27] 肖人彬，王磊，人工免疫系统：原理、模型、分析及展望[J]，计算机学报，2002．12． Vol．25．No．12．1281～1291
[28] Borland/Inprise Company. VisiBroker for Java Reference & Visibroker for java Programmer's Guide[M]．北京，机械工业出版社，2000．11～70
[29] 丁永生，任立红，人工免疫系统：理论与应用[J]，模式识别与人工智能，2000．3．Vol．13．No．1．52～57
[30] 孙勇智，韦巍，人工免疫系统及其应用[J]，计算机工程，2003．9．Vol．29．No．15．1～2
[31] Ishida Y. & Adachi N. Active Noise Control by an Immune Algorithm.. Adaptation in Immune System as an Evolution[J]. Proc. ICEC 96, 150～153, 1996
[32] Leandro Nunes de Castro, Fernando Jose Von Zubenmm Artificial Immune Systems: PartⅠ-Basic Theory and Applications [D]. 1999. 1.76～85
[33] Dasgupta D. Artificial Immune Systems and Their Applications Berlin Heidelberg: Springer-Verlang,1999
[34] Okamoto T, Ishida Y. A distributed approach to computer Virus detection and neutralization by autonomous and heterogeneous agents[J]. In: Proce 4th International Symposium on Autonomous Decentralized Systems, Tokyo, Japan,1999. 328-331
[35] Dasgupta D, Forrest S. Artificial immune systems in industrial applications[J]. In: Proc 2nd International Conference on Intelligent Processing and Manufacturing of Materials, Honolulu,1999.257-267
[36] Kim J, Bentley P. The artificial immune model for network intrusion detection[J]. In: Proc 7th European Congress on Intelligent Techniques and Soft Computing, Aachen, Germany, 1999.13-19
[37] Kim J, Bentley P. Towards an artificial immune system for network intrusion detection: An investigation of clonal selection with a negative selection operator[J]. In: Proc Congress on Evolutionary Computation, Seoul, Korea,2001.27-30
[38] 王磊，免疫进化计算理论及应用[D]，西安电子科技大学博士学位论文，2001
[39] 曹先彬，刘克胜，王煦法，基于免疫遗传算法的装箱问题求解[J]，小型微型计算机系统，2000．4．Vol．21．No．4．362～363
[40] Ishida Y. Fully distributed diagnosis by PDP learning algorithm towards immune network PDP model[J]. In: Proc International Joint Conference on Neural Networks, SanDiego, CA, USA, 1990.777-782
[41] Deaton R, Murphy RC, Garzon Metal. DNA based artificial immune system for self-nonself discrimination [C]. In: Proceedings of the IEEE International Conference on System, Man and Cyhernetics, 1997:862-865
[42] Dorigo M, Bonabeau E, Theraulaz G.Ant algorithm and stigmery[J]. Future Generation Computer Systems, 2000, 16(8): 851-871
[43] Leandro N de Castro, Jonathan Timmis. Artificial immune systems: a new computational intelligence approach [M].Bdtish : Springer Press, 2002:77
[44] Goldberg D E, Richardson J. Genetic algorithms with sharing for multimodal function optimization[C].In: Proceedings of the second International Conference on Genetic Algorithms, the Massachusetts Institute of Technology, Cambridge, MA, 1987-07:41-49
[45] Cavicchio D J. Reproductive Adaptive Plans. In: Proc. of the ACM 1972 Annual Conf, 1972, 1-11
[46] 孙瑞祥，屈梁生，进化计算的过去、现在与未来[C]，“遗传算法／进化计算研究生学 术论坛”论文集，2000
[47] 王琼，基于人工免疫系统的函数优化问题研究[D]，武汉理工大学学位论文，2005
[48] 谢凯，排挤小生境遗传算法的研究与应用[D]，安徽理工大学学位论文，2005
[49] 周泉，人工免疫系统理论及免疫克隆优化算法研究[D]，湖南大学学位论文，2005