【作者】 张晓明；

【导师】 梅涛； 王儒敬；

【作者基本信息】 中国科学技术大学 ， 模式识别与智能系统， 2011， 博士

【摘要】 智能计算方法的主要构建思想是从自然界的生物系统、生命现象中寻求问题求解的灵感和方法,通过对自然生物系统的生存繁衍过程、生命个体的进化过程、自适应行为等现象和行为的建模和模拟,构建各种智能计算模型,用于求解现实世界中的大规模、高维度、非线性的复杂优化问题。探讨如何从生物适应环境、自主优化过程中获取灵感,构建智能计算方法,将会在很多方面弥补经典最优化方法的不足,对人工智能新原理、新方法的发展将具有很好的推动作用。大量的研究者仍然在致力于发展更高效、更实用的群体智能优化算法。种子优化算法是受自然界种子传播方式和种群分布演化的启发而设计的,它通过模拟植物生存的宏观自适应现象,来解决复杂的优化计算问题。其寻优机理不同于现有群体智能优化算法,主要通过父种选择和种群分布演化两个算子进行寻优。算法结构较简单,实现较容易,对算法的研究和实验也表明:在所开展的实验中,种子优化算法符合我们预期的全局寻优能力强、收敛速度快的特点。本论文的主要贡献和创新点包括以下几个方面:1.借鉴自然界种子传播方式和种群分布演化,本文构建了种子优化算法这一种新的群体智能算法,该算法具有较新颖的设计思想和明确的仿生含义。通过调研和学习生物统计学的相关研究结果,构建了三种BOA的种群分布演化模型,分别是基于分段函数的分布模型、基于正态分布的模型和基于负二项分布的模型。并分别针对上述三种算法模型构建了相应的BOA算法,并针对11个典型的基准函数,开展了函数优化实验,实验结果与粒子群优化算法的结果进行了对比分析,结果表明BOA在所开展的实验中,性能明显优于PSO算法,也验证了这三种算法模型的有效性。同时,还开展了算法自身参数的调整对比实验,初步研究了算法参数对算法性能的影响。2.基于逆推理归纳,构建了初步的BOA算法的优化策略自适应选择机制。列举了现有BOA算法的主要参数,初步确定了一种优化策略分项的调整顺序,并整理出相关的参数调整规则;并构建了一种优化策略性能评价方法,用以综合评价算法的寻优能力和收敛速度,用以评价优化策略的优劣。最后选择了两个500维的多峰基准测试函数进行了自适应优化策略调整的测试,实验结果表明,该优化策略自适应选择机制取得了较好的参数调整表现,求解效果明显优于固定参数的BOA算法。3.对BOA算法中的几个基本定义作了严格的数学描述和重新定义,构建了BOA算法的Markov链模型,明确了相关的算法性质,基于此,依据Solis和Wets提出的随机算法收敛的标准,对BOA算法的收敛性做了初步分析,证明了BOA算法是以概率1全局收敛的。4.应用BOA算法求解了三个典型的最优化问题。其中FM参数合成估计问题是IEEE-CEC2011“应用进化算法求解真实世界优化问题”专题所列举的第一个用于测试智能计算方法应用能力的最优化问题,本文即以该会议的原题为例,应用BOA算法进行了求解,求解结果与CEC公布的DE-RHC算法的求解结果进行了对比,表明了BOA的优越性;然后结合目前正在开展的减灾科技支撑项目,以汶川地震灾后恢复重建为例,构建了项目排序的最优化问题,应用BOA算法进行了优化求解,求解结果兼顾了专家的意见,符合了中国地震灾后恢复重建规划标准和我国政府的以人为本的原则;TSP问题是典型的离散优化问题,机器人全局路径规划问题基本都能转化成TSP问题的求解。本文利用种群迁移和最优信息交叉共享的思想,设计了一种用于离散优化问题求解的种子优化算法,克服了基本BOA算法不适合求解离散优化问题的缺点,通过典型的TSP问题求解实验,并与交叉PSO和MAX-MIN AS进行了实验结果对比,验证了离散BOA的优越性和有效性,深化了BOA算法的理论研究,扩大了BOA算法的应用领域,有望在日后应用于目前正在开展的老人服务机器人的全局路径规划中。更多还原

【Abstract】 Many complex self-adaptive phenomena in the nature often give us inspiration. Some scholars were inspired from these natural bio-based phenomena and many nature-inspired optimization algorithms have been proposed by them. When solving some complex problems which the traditional optimization algorithm can not solve easily, the nature-inspired optimization algorithms have its own unique advantages. Inspired by the transmission mode of seeds, a novel evolutionary algorithm named Bean Optimization Algorithm (BOA) is proposed, which can be used to solve complex optimization problems by simulating the adaptive phenomenon of plants in the nature. BOA is the combination of nature evolutionary tactic and limited random search. BOA has stable robust behavior on explored tests and stands out as a promising alternative to existing optimization methods for engineering designs or applications. This thesis carries out a comprehensive research on BOA.The main work of this thesis can be introduced as follows:1. Learn from the seed dispersal mode and population distribution of evolution in nature, this thesis proposes a novel swarm intelligence algorithm-BOA. This optimization algorithm is provided with relatively new design ideas and clear meaning of bionic. Through research and study on the relevant research results of biostatistics, three distribution models of population evolution for BOA are built. These three models are respectively distribution model based on piecewise function, normal distribution model and negative binomial distribution model. Three kinds of BOA algorithms are presented based on the three distribution models respectively. In order to verify the validity of the three algorithms, function optimization experiments are carried out, which include eleven typical benchmark functions. The results of BOA in the experiments are made a comparative analysis with that of particle swarm optimization. From the results analysis, we can see that BOA is significantly better than PSO algorithm. We also research on the characters of BOA. A contrast experiment is carried out to verify the research conclusions about the relations between the algorithm parameters and its performance.2. A preliminary adaptive optimization strategy selection mechanism of BOA is proposed based on inductive reasoning. This thesis firstly lists the main parameters of the existing BOA algorithms and develops a kind of adjusting order of sub options in optimal strategy. Then the relevant parameter adjustment rules are sort out. This thesis also builds a performance evaluation method to evaluate the ability of optimization and convergence speed of the selected optimization strategy. Finally, two 500-dimensional multi-peak benchmark functions are used in the experiments to verify the validity of the adaptive optimization strategy of BOA. The experimental results show that the adaptive selection mechanism for optimal strategy can adjust the parameters to achieve a better performance than that of the BOA algorithm with fixed parameters.3. As BOA is a novel proposed optimization algorithm, theoretical analysis for the algorithm is still very preliminary at present. This thesis carries out the research on the state transfer process and the convergence behavior of BOA. Firstly several basic definitions of BOA are re-defined in strict mathematical description. Then the Markov chain model of BOA is established and the analysis of the Markov chain is made. Then I prove that BOA satisfies the two convergence conditions of the random search algorithms. Finally according to Global Search Convergence Theorem, BOA will converge to the global optimal solution with probability 1. The research conclusion is of great significance for BOA’s understanding, improvement and application.4. Algorithm application is the best way to test the algorithm. So in this thesis, BOA algorithm is applied to solve three typical optimization problems. The problem of parameter estimation for frequency-modulated (FM) sound waves is to generate a sound similar to target sound. It is a six dimensional optimization problem with the properties of highly complex multimodal and strong epistasis. It is also the No.1 problem of“Testing Evolutionary Algorithms on Real World Optimization Problems”in IEEE-CEC2011. BOA is used to solve the FM problem and the result is compared with that of DE-RHC. By comparing the results, we can see that BOA is better than DE-RHC. In China, it is important to establish a complete post-disaster reconstruction and rehabilitation system to respond to sudden natural disasters. In order to get post-disaster restoration items scheduling, we invited experts to give the fuzzy preference relation coefficients on the restoration items. Then an optimization model was proposed based on the fuzzy preference relation. BOA is proposed to solve the model and obtain ranking values of the items. The experimental result gives priority to the restoration of basic livelihood of the people and public service facilities. TSP is a typical discrete optimization problem. This thesis presents a discrete BOA for solving discrete optimization problems based on the ideas of population migration and information cross-sharing. This method overcomes the defect of basic BOA algorithms which do not suit for solving discrete optimization problems. Finanlly, five typical TSP problems are used to verify the validity of discrete BOA. The results of the experiments compared with that of the Cross-PSO and MAX-MIN AS show that discrete BOA gets better results than that of the other two algorithms and it suits for solving the discrete optimization problems. This research also deepens the BOA algorithm theory and expands the application areas of it.更多还原