【作者】 陈晋音；

【导师】 杨东勇；

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

【摘要】 生物启发计算是在生物界自然现象的启示下获得灵感,研究开发智能计算模型和算法的新兴学科,包含遗传算法、粒子群算法、人工免疫算法、蚁群算法、神经网络等算法。生物启发计算作为高效的优化算法广泛应用于数据挖掘、机器人应用和网络入侵检测等领域;也为复杂问题的求解提供了新的解决方法。与成熟学科相比,生物启发计算的研究仍处于初步探索阶段。为提高生物启发计算的应用效率,本文研究生物启发计算的三种典型计算方法:遗传算法、粒子群算法和人工免疫算法,分别提出协作协进化遗传算法、基于惩罚机制的自适应交叉粒子群算法和基于多种群遗传算法的抗体生成算法等,并利用多机器人路径规划和入侵检测系统验证提出算法的有效性,为解决生物启发计算的“早熟”问题、局部收敛问题、降低计算复杂度等关键问题提供了新的思路和方法。本文主要工作包括:1.针对遗传算法求解多目标优化问题中存在的早熟问题,设计了一种染色体长度可变、混合编码的Messy遗传算法(Messy GA),并在此基础上提出全局适应度函数,实现了基于协作协进化的Messy GA(CCMGA)。在传统遗传算法的选择操作、交叉操作和变异操作基础上,利用简化操作、平滑操作和修复操作来辅助目标函数的优化。针对遗传算法容易丧失种群多样性的问题,结合混沌机制提高CCMGA的局部搜索能力。最后利用CCMGA实现多机器人路径规划,通过Matlab的仿真实验模拟多机器人在相对复杂的地图环境下完成动态路径规划,验证算法有效克服早熟问题,并且CCMGA能提高遗传算法的收敛速度和最优解。2.粒子群算法近年出现了多种改进的方案,但均存在易陷入局部收敛的问题。本文提出一种基于惩罚机制的自适应交叉粒子群算法,有效克服局部收敛,并利用参数自适应解决单峰和多峰约束优化问题。根据粒子群进化过程中种群多样性模型,引入交叉操作,利用柯西不等式证明交叉粒子群算法通过保持种群多样性克服早熟和局部收敛,从而得到全局最优解。建立有限状态组成的马尔科夫链模型描述粒子群算法进化状态转换过程,有效控制粒子群算法收敛到全局最优,形成了自适应交叉粒子群算法。基于改进H策略和简化P策略惩罚机制,优化典型的Benchmark函数,分析实验结果得到:根据问题本身单峰和多峰的不同特性,参数设置影响收敛速度和最优解,因此本文提出参数自适应计算公式,有效提高粒子群算法求解单峰和多峰优化问题的性能。3.针对人工免疫算法中抗体抗原最优阈值的求解困难,本文提出了匹配阈值预测模型,分析抗体抗原匹配规律,利用预测模型计算获得最优阈值,提高抗体检测效率。针对抗体生成算法复杂度高、生成抗体检测率低和抗体集合庞大的问题,提出了基于多种群遗传算法的抗体生成算法(MPTMA)。在形态学空间利用覆盖原理分析抗体抗原匹配,有效降低抗体集合的冗余度,减小抗体规模,保持抗体的多样性,提高抗体检测率。从理论和仿真分别证明MPTMA提高了抗体检测率、降低了抗体生成算法的时间复杂度。4.将提出的基于阈值预测模型的MPTMA应用于入侵检测系统,提出了信息预处理机制。利用最小信息熵离散化算法对网络数据进行离散化处理,并结合PCA特征提取算法对数据进行特征提取。结合基于否定选择算法的快速匹配检测器和基于克隆选择算法的智能进化检测器,利用基于克隆选择算法的智能进化自学习得到的入侵特征更新前者的特征库,实现快速匹配检测器和基于克隆选择算法的智能进化检测器的协作,保证了混合检测器的检测实时性和准确性。仿真实验证明基于预测模型的MPTMA生成检测器提高了检测率,与传统的方法相比,在优化结果、收敛速度和稳定性上均有明显提高;同时相对单独使用上述两种检测器,混合检测系统在实时性、检测率和误测率等方面具备更好的性能。本文的主要创新点:1.针对遗传算法求解多目标优化存在早熟的问题,提出了基于协作协进化机制的Messy GA,构建全局适应度函数,利用辅助算子优化,并结合混沌机制提高局部搜索能力。2.针对粒子群算法易陷入局部收敛问题,提出基于惩罚机制的交叉粒子群算法,分析种群收敛规律提出自适应交叉概率模型,求解单峰和多峰优化问题实现参数自适应,有效克服局部收敛,提高优化性能。3.提出匹配阈值的预测模型,克服最优阈值的求解困难,在此基础上提出基于多种群遗传算法的抗体生成算法,在形态学空间利用覆盖原理分析抗体抗原匹配,MPTMA提高抗体检测率、降低抗体生成算法的时间复杂度。4.将MPTMA作为入侵检测系统的检测器生成算法,利用最小信息熵离散化算法和PCA特征提取算法预处理信息,提出了结合基于否定选择算法的快速匹配检测器和基于克隆选择算法的智能进化检测器的混合检测器,在优化结果、收敛速度和稳定性上提高性能。更多还原

【Abstract】 Bio-inspired computing, enlightened by natural intelligence of biological world, is a novel science for research and development of intelligent computing models and algorithms. Bio-inspired computing, including genetic algorithm, particle swarm optimization, artificial immune algorithm, ant clonal algorithm, neural network algorithm and etc., is considered as efficient optimizing algorithms widely applied in areas as artificial intelligence, machine learning, data mining, robots, network intrusion detection and etc. It provides novel solutions for complex problems. Compared with matured sciences, bio-inspired computing is still young which needs further discuss and research. In order to improve the efficiency, this paper is focused on three classic Bio-inspired computing algorithms: genetic algorithm, particle swarm optimization and artificial immune computing. CCMGA, penalty mechanism based crossover PSO and MPTMA are brought up, and the put forward algorithms are applied to multiple robots path planning and intrusion detection system to testify their efficiency. This paper provides novel ideas and methods for solving premature, local convergence and algorithm complexity problems in Bio-inspired computing.The main work of this thesis can be concluded as:1. Aiming at premature problem of GA optimizing multiple objective problems, drawbacks of traditional coding and fitness function definition in GA are pointed out. Messy GA with variable length of chromosome and hybrid coding is brought up, based on which a global fitness function is defined to implement cooperative co-evolution Messy GA (CCMGA). Besides operations of selection, crossover and mutation in traditional GA, simplify, smooth and repair operators are adopted to assist optimizing objective functions. Aiming at population diversity lost in GA, chaotic mechanism is applied to improve local search ability of CCMGA. Finally CCMGA is applied for multiple robots path planning. Matlab simulation results testify that multiple robots are able to optimize paths in various complicated maps. CCMGA is proved be capable of overcoming premature problem in GA, on basis of which convergence speed and optimized results are improved. 2. Particle swarm optimization (PSO) has obvious shortcoming: local convergence. In this paper, penalty mechanism based self-adaptive crossover PSO is put forward to overcome local convergence problem Based on population diversity model in evolutionary process for particles, crossover operation applied into PSO proved by Cauchy inequality is used to maintain population diversity to overcome problem of premature and local convergence and achieve global optimum solution. Evolutionary state transition process is depicted by Markov model consisted with finite-states, and self-adaptive crossover PSO is implemented. Penalty mechanism based Self-adaptive crossover PSO is designed for solving constrained optimization problems. Based on improved H strategy and simplified P strategy, experiments on benchmark functions demonstrate that parameters affect performance when optimizing unimodal and multimodal problems. A general calculating formula is put forward to control parameters for optimizing unimodal and multi-modal function optimizations respectively, which overcomes the in prior parameter setting difficulty.3. Aiming at optimal matching threshold of antibody generation, a matching threshold prediction model is brought up in this paper. Analyzing antigen and antibody matching principle, optimized threshold is calculated by prediction model. In order to decrease complexity of antibody maturation algorithm, improve detection rate and smaller antibody set, multiple population GA based antibody maturation algorithm (MPTMA) is put forward. Antibody and antigen matching principle is analyzed in morphological space, it’s proved that antibody set and redundancy are efficiently decreased by MPTMA, and antibody diversity is maintained, detection rate is improved. MPTMA is proved by theory and simulations that detection rate is improved and time complexity id decreased.4. MPTMA with threshold prediction is applied to intrusion detection system (IDS), so a hybrid intrusion detection system (HIDS) is put forward. Minimal information disperse algorithm is adopted to disperse information and features of original data is extracted by PC A to implement IDS. This thesis puts forward hybrid intrusion detection system (HIDS) which compromise NSA based fast detectors and clonal selection algorithm based intelligent detectors, and the new features concluded by latter detectors are used to update database for better NSA based detection. The cooperation of the two kind detectors promises real-time and high detection rate. By simulation on our lib network, the better performance of brought up HIDS compared with NSA based IDS or clonal selection algorithm based IDS is testified in aspect of real-time, detection rate and false detection rate.The main contributions of this thesis can be concluded as:1. Aiming at premature problem of GA solving multi-objective optimizing problems, a cooperative co-evolution Messy GA is put forward. Global fitness function is defined, assistant operations are used, and chaotic mechanism is adopted to improve local search ability.2. Aiming at local convergence problem of particle swarm optimization, penalty mechanism based crossover PSO is brought up. Self-adaptive crossover models are designed on basis of population convergence principle. Optimized parameters are calculated by designed formula to solve unimodal and multimodal optimizations.3. For antibody maturation algorithm in artificial immune, a matching threshold prediction model is put forward, and tests prove that it overcomes optimal threshold difficulty. And multiple population GA based antibody maturation algorithm is brought up, whose detection rate is improved and time complexity is decreased.4. MPTMA is applied as detector generation algorithm for IDS. Minimal information disperse algorithm and PCA feature extraction algorithm are adopted to realize IDS. A novel HIDS combining NSA based detectors and clonal selection algorithm based detectors is designed. Its performance in optimizing results, convergence results and stability are improved.更多还原