【作者】 王炼红；

【导师】 章兢；

【作者基本信息】 湖南大学 ， 控制理论与控制工程， 2009， 博士

【摘要】 人工免疫系统(AIS:Artificial Immune System)是一类基于生物免疫系统的功能、原理、基本特征以及相关理论免疫学说而建立的用于解决各种复杂问题的计算系统,是继人工神经网络、进化计算之后新的计算智能研究方向。本论文旨在深入探索和研究生物免疫系统中蕴含的进化学习机制,设计高效的人工免疫算法,并用其解决工业中的组合优化问题以及数据挖掘中的分类问题。本论文的主要研究工作包括以下几个方面:1.一般克隆选择算法(CSA)求解函数优化问题时,虽然表现出了比遗传算法更好的全局寻优能力,能有效克服遗传算法早熟现象。但是,在解决诸如背包问题等组合优化问题时收敛速度缓慢,解波动较大且难搜到最优解。为此,对一般克隆选择算法进行了改进,提出了带受体编辑的克隆选择算法(RECSA)。该算法受生物免疫系统机理的启发,不仅通过体细胞高频变异还引入了受体编辑操作实现亲和力的成熟,使抗体达到与抗原的高度匹配,同时增加一个历史至当前代最佳个体记忆单元防止种群退化。针对背包问题,采用贪婪策略和宽限边界值相结合的方式,对每代抗体群进行受体编辑操作。在对背包问题的两个算例求解中表明:与一般CSA算法和遗传算法相比,RECSA算法能提高种群质量和算法的收敛速度,在随机搜索期望最优值方面能力更强,而且算法更加稳定可靠,鲁棒性更好。2.针对组合优化问题,建立了一般CSA和RECSA算法的有限时齐马尔可夫链模型,定义了种群状态并构造了马尔可夫链的状态转移矩阵,然后采用马尔可夫链理论对两算法的收敛性进行了证明。理论推导表明,当迭代次数趋于无穷大时,马尔可夫链中的任意种群初始态是以概率1收敛到最优态,即至少有一个最优解能被寻到。最后,采用马尔可夫链平均吸收时间定理,证明了RECSA算法的平均收敛代数小于一般的CSA的平均收敛代数,从理论上说明了RECSA算法的收敛速度更快。3.为了说明RECSA算法解决组合优化问题的普遍有效性,我们将其用于组播路由问题当中。针对时延受限的组播路由,根据代价最小化原则和延时要求对个体的基因片段进行两次受体编辑,采用RECSA算法对其进行求解表明,在无需先求解备选路径的情况下能快速找到最优解,算法复杂度低且稳定可靠。本文还将RECSA算法用于解决组播路由的QoS问题,在首先满足延时约束的条件下,再综合考虑延时、带宽、代价这三个性能指标,引入了一个参数Q来衡量组播路由综合性能,使算法在这三者之间进行权衡约束,克服了目前传统的组播路由算法的一种性能参数的改善是以另一种或几种性能参数的退化作为代价,过于厚此薄彼的作法。仿真实验表明:该算法收敛速度快,能从整体上把握组播路由的综合性能,大大改善了组播路由的服务质量。将该算法用于长沙移动网的LAC优化中,实现了在不增减LAC区的情况下尽量减小LAC区边界处位置更新次数。4.从免疫进化网络理论着手,在研究了aiNET聚类模型和AIRS、AINMC等分类算法基础上,提出了基于免疫进化网络理论的分类器(IENC)。该算法主要采用记忆细胞池间与记忆细胞池内的两次网络抑制操作来改善网络结构,使记忆细胞在特异性与“通用性”之间得到平衡,从而提高分类准确率。对UCI中的Iris、Ionospere、Sonar和Pima的四个标准数据集的测试表明, IENC分类器比AIRS和AINMC更好,分类准确率更高。5.最后,将IENC分类器用于DNA序列和电能质量扰动分类中同样得到了比较满意的分类准确率。以上测试中,分类器的亲和力度量均采用常用的欧式距离。而在DNA序列的分类中发现, DNA序列的特征提取和亲和力度量方法对分类性能有较大影响。为此,对算法进行改进,采用离散增量度量亲和力,所获得的分类器泛化性能更好,能更好地衡量序列之间的相似性,将其用于线虫、酵母和拟南芥三类模式生物基因的识别中获得了更好的分类准确率。更多还原

【Abstract】 Artificial Immune System (AIS) is a computing system that solves various complex problems based on the functions, disciplines, characteristics and other related immune theories of biological immune system. The system is a novel field of intelligent computing research after Artificial Neural Network (ANN) and Evolutionary Computation (EC). The objective of this study is to explore the evolutionary learning mechanisms contained in biological immune system and to apply them to the design of effective artificial immune models and algorithms for solutions of combination optimization problems in industries, and classification problems in Data Mining as well. The study focuses on the following aspects:1. The usual Clonal Selection Algorithm (CSA) is better than the Genetic Algorithm (GA) in global searching abilities, overcoming the problem of early-ripeness in function optimization. However, previous research demonstrates that when applying CSA to combination optimization problems such as 0-1 kidnap problems, it is incompetent of searching the best solution, slow of the processing speed of convergence and the solutions may fluctuate in a large scope. A Clonal Selection Algorithm with Receptor Editing (RECSA) is proposed, inspired by the biology immunity system mechanism. It makes use of not only cellular hypermutation but also receptor editing operation to realize affinity mature that will lead to the best match between the antibody and the antigen, Meanwhile a memory cell of the best individual descended is added to the mechanism to avoid population devolution. Aimed at the solution kidnap problems, the algorithm combines greedy strategy with an extended boundary to complete the receptor editing operation of each generation antibodies population. Applying RECSA to two 0-1 Kidnap Problems show that it can improve the population quality and search for the best solution more quickly than CSA. Its efficiency is higher and its stability and robustness is better than CSA and GA.2. Aimed at combinatorial optimization problems, a homogeneous finite Markov Chain Model using CSA and RECSA is constructed. The population state in Markov Chain is defined and a step transition probability matrix of system state is deduced. Then the convergence properties of the two algorithms are testified by the C-K equation properties in Markov chain theory. The testification process proved that the antibodies’population state can transit from arbitrarily beginning state to the best state when generation number is large enough, which means at least one best solution can be searched out in the final antibodies population. Lastly, testification based on the average absorbability time theorem in Markov Chain proves that the average generation number of convergence in RECSA is smaller than that in CSA, providing theoretical proof for the quicker convergence speed of RECSA in comparison with CSA.3. To show its universal validity of solving combined optimization problems, RECSA was further applied in the multicast routing field. In the case of multicast routing with delay constrain, the good gene segment in the immaturity subpopulation was adopted and receptor editing was conducted based on the principle of minimum cost and delay constrain separately. Results show that RECSA can search promptly for optimum solution without a prepared routing set. The process is also featured lower computational complexity and higher stability. RECSA has also been applied to the solution of the QoS problems in multicast routing. After fulfilling the condition of the time delay restraint, a parameter Q, which considers the balance the three performance including time delay, band width and the expense, is defined and introduced to measure the overall performance, maintaining the compromise and balance among the three Indies. This overcomes the problem in traditional solutions to multicast routing, namely the improvement of a performance parameter resulted in serious degeneration of other parameters. The results of simulation tests indicate its high searching efficiency, capable of adjusting the whole performance of the multicast routing and improved service quality of the QoS. At last, RECSA is applied to optimize LAC of Changsha mobile network so that number of times for LAC boundary locations update decrease while LAC sum is not changed.4. A classifier based on immune evolutionary network theories (IENC) has been proposed combining findings from studies on algorithms such as aiNET, AIRS and AINMC, and the immune evolutionary network theories. The classifier, based on the two network suppression operations within each memory cell pool and between memory cell pools, improves the network structure. Hence, the memory cellules can reach balance between peculiarity and universality, and eventually, improve the accuracy of classification. The results of tests on the four standard datasets of Iris, Ionosphere, Sonar and Pima in UCI indicate that IENC has better and higher accuracy than AIRS and AINMC .5. At last, satisfactory classification accuracy is achieved when applying IENC to DNA sequences and power quality disturbances detection. Euclid-distance was adopted for the affinity measurement of the classifier in all tests mentioned above. However, it was found that the eigenvalue extraction and the affinity measurement can negatively influence the classifier’s characteristics in DNA sequence tests. IENC has therefore been improved as follows: the diversity increment was adopted to measure the affinity measurement, and a group of status parameters of the source of diversity are added to the respective frequency of the 64 codons of a sequence using sliding calculation, the improved classifier had resulted in better performance and higher accuracy. It is also more capable of judging similarities among sequences when applied to DNA sequences discrimination of three model species including C. elegans, S. cerevisiae and A. thaliana .更多还原