【作者】 刘小龙；

【导师】 李荣钧；

【作者基本信息】 华南理工大学 ， 管理决策与系统理论， 2011， 博士

【摘要】 优化问题是人们在科学研究和生产实践中经常遇到的问题,人们已经对大量的最优化问题进行了深入的研究,并将其拓展成为了一门重要的学科门类。传统以梯度为基础的最速下降法、线性规划、单纯形方法等优化方法,在问题的目标函数是凸集、连续可微可导等情况下,具有较高的计算效率。但在实际应用的物流配送中心的选址、设备资源的最优分配、车间在制品的产品调度与布局等领域中,出现了许多大规模、非线性、多极值、多约束、非凸性等现象,这就使得传统的优化方法难以进行数学建模,从而给以仿生为特征的群智能计算方法提供了广阔的应用舞台,并诞生了一批模拟生物行为的“启发式方法”,这其中的典型代表包括遗传算法GA、蚁群优化算法ACO、粒子群优化算法PSO和细菌觅食优化算法BFO等。相关研究表明,现有群智能算法或多或少地存在着“早熟”、“晚熟”甚至“不熟”的收敛性缺陷与问题,因此许多学者将视角瞄向了在不同的群智能算法之间取长补短,确定改进各种优化算法性能的方式与途径。在以上主要的群体智能优化算法中,GA、ACO、PSO都是基于高等生物作为启发对象,形成的一种“生成+检验”为特征的自适应人工智能计算技术,而BFO等算法,则是从微生物的行为机制出发,通过模拟细菌对环境感知的变化,而形成的一种新优化方法。由于微生物智能仿生技术问世的时间太短,国际学术界目前对BFO等相关研究尚有许多空白,这一新型的智能仿生算法还远未获得学术界应有的足够重视。因此,本文尝试对微生物的行为机制及其生理特性进行建模仿真,探讨这一新型智能计算方法的改进方式,从而丰富仿生优化算法中的微生物智能计算这一领域,继而对其他仿生优化算法提供一定意义上的技术借鉴,为本文提供针对现有生物体系优化算法融合改进的新途径、新视角。本研究采用规范分析和实验研究为主的研究方法,对仿生优化的思想基础、主要门类和算法框架程式进行了探讨,阐述了仿生优化算法性能比较的问题测试函数、算法优劣的性能比较指标和算法迭代中的种群多样性度量指标,并对基本的BFO算法原理、实现步骤进行了深入分析,讨论了BFO算法中现有趋化算子、繁殖算子和迁移算子在程序执行中表现出的主要问题,进而利用测试函数对算法的各种参数设置进行了实验,提出了BFO算法参数设置的部分规律,基于最优觅食理论对BFO算法进行了实验,讨论了细菌在趋化过程中的不同觅食方式对算法性能的主要影响。在以上理论分析的基础上,本文尝试对群智能算法进行算法思想的理论融合,试图分析现有不同群智能算法的特征,基于高等生物的群体协作、生物种群的基因进化和统计学习的分布估计三个层面,对现有算法的微观行为层面、基因改进层面和宏观指导层面进行改进,以提高BFO基本算法的测试性能,并使之具备协调进化和学习适应等多重智能,从而达到提高算法的搜索速度和精度的目的。本文尝试构建的改进BFO算法不仅具有方法上的创新,而且对现有智能计算技术具有较为积极的思想参考,从而具有一定意义上的理论创新。论文的主要研究成果表现在以下几个方面:(1)系统总结了仿生优化群智能计算的基本原理和主要方法,分析了现有算法性能比较的无免费午餐定理(NFL),阐述了算法性能比较所使用的标准测试函数、性能比较和种群多样性评价指标,揭示了各种群智能计算方法的思想基础,为后续文章所提及的算法优化及其改进研究提供评价体系和理论上的参照。(2)深入研究了细菌觅食优化算法的基本原理,分析了现有的趋化、繁殖和迁移算子在算法寻优中的局限性,对算法中的基本参数进行了分析,讨论了相关参数设置的经验和取值借鉴,比较了PSO和BFO中的两种觅食行为策略,分别利用细菌能量和适应度来模拟非常规和常规觅食策略,验证了不同觅食策略对算法性能的影响,最后提出了针对细菌觅食优化的四个方面的改进目标和具体改进行为策略。(3)分析了生物在觅食过程中的竞争和协作两种主要行为,探讨了基于协作思想的鱼群算法和学习思想的粒子群算法的主要思想。基于鱼群算法的思想,赋予细菌感知群体状态的能力,可以进行优值跟踪(追尾群体最优)和聚群(向群体中心位置好的靠拢),提出了环境感知BFO算法,提高了问题求解的精度。基于PSO的自我学习和社会学习思想,提出了协作BFO,使得算法具有更大概率获得全局最优解。(4)分析了生物进化的适者生存、物种选择和遗传学说理论,讨论了基于生物进化的广义进化计算方法,分析了以进化思想为基础的遗传算法及其进化计算的基本思想。基于差分进化的思想,在细菌繁殖时通过群体内个体间的差分合作与竞争,来实现细菌群体的优化,从而对趋化周期结束后的维度退化现象进行修正,差分算子明显提高了BFO算法的精度、鲁棒性和全局最优获取能力。基于生命体免疫系统的思想,设置了基于免疫体的克隆繁殖算子,在趋化周期完成后对精英细菌进行克隆、高频变异和随机交叉,从而引导算子搜索,使得算法对部分测试函数具有很好的适用性,并能快速收敛,找到全局最优解。(5)分析了最新出现的智能计算的分布估计的方法,探讨了分布估计引入智能计算的可能性,从而可以充分利用实际问题的先验信息,完成从宏观指导思想上的建模。基于分布估计中的高斯分布思想,在细菌趋化周期结束后的繁殖环节,引入了高斯分布繁殖的概念,从宏观上对较优秀的部分细菌进行统计建模,明显提高了BFO算法的精度和鲁棒性,对部分测试函数具有很大的适应性。基于现有细菌繁殖的真实生长曲线,打破BFO算法的三层嵌套框架,模拟了细菌在优化过程中的菌群自由分布规律,建立了细菌自我繁殖和消亡的系统模型,进而从另一个侧面对前述BFO算法的相关性能进行佐证。(6)利用标准测试函数对改进细菌觅食优化的算法性能进行测试验证,在MATLAB软件平台上设计和开发了相应的计算机程序附后,针对实际优化中的连续空间和离散空间,采用神经网络预测问题和车间作业调度问题对算法性能进行验证,拓展了连续性BFO的应用空间,为神经网络的权重求解和作业调度优化提供了一种新的信息处理和智能计算工具。更多还原

【Abstract】 Optimization is the problems that people encountered frequently in the scientific research and production practice, and a large number of optimization problems has been researched in-depth, then develop its been an important disciplines. Conventional optimization such as steepest descent method, linear programming, simplex method that method gradient-based have high computational efficiency when its objective function of the problem is such circumstances as convex, continuous and differentiable. But in the practical application of logistics distribution center location, the optimal allocation of resources, equipment, plant products, products in areas such as scheduling and layout, there were many large-scale, nonlinear, and more extreme, more constrained, non-convex and other phenomena, which makes it difficult for traditional optimization methods of mathematical modeling to give a group of intelligent bionic characterized by calculation to provide a broad application of the stage, and the birth of a number of simulated biological behavior of the "heuristics", This is one of the typical including genetic algorithms, ant optimization algorithms, particle swarm optimization and bacterial foraging algorithm and so on. Research shows that these group intelligent algorithms more or less exist some convergence defects and problems of"premature", "late" or even "familiar", so many scholars view aimed at the different groups intelligent algorithms in the between each other and determine various ways and means to improve the performance of the optimal algorithm.The main groups in the above intelligent optimization algorithm, GA, ACO, PSO is inspired by objects based on higher organisms, and its form an adaptive artificial intelligence computing technology characterized by "generation + test", but BFO is an algorithms starting from the mechanism of microbial behavior, simulating the bacteria perception to the environment changes, forming a new optimization method. Since the time was too short that micro-organisms intelligent bionic technology advents, there are many gaps in this new type of intelligent bionic algorithm in the international academic community, and it’s far from the adequate attention should receive from academic community. Therefore, this article attempts to analyze the microbial mechanisms and physiological characteristics for modeling and simulation, and to explore the improvement way of this new calculation method, for enriching the bionic optimization algorithm in the field of microbial intelligent computing, and then provided a sense of technology learn to other bionic optimization algorithm, provided us with new ways and new perspectives for the existing biological systems optimization approaches. This research based in normative analysis and experimental research methods, analyze the ideological basis, the main categories and algorithms program of the bionic optimization; and its also discussed the performance comparison test function, the merits of the algorithm performance comparison index and the diversity of the population algorithm iteration metrics of bionic optimization problem. and then we discussed the basic principles and achievement steps of BFO algorithm, analysis and discuss the main problems in the execution of a program showing in BFO algorithm existing operator chemokine breeding and migration, then the algorithm was experimentally proposed algorithm parameter settings useing the test function. Finally, the article seting some experiments to the BFO algorithm based on optimal foraging theory, discussed different feeding methods algorithm performance that the bacteria effects in the process of chemotaxis.Based on above theoretical analysis, the article attempts to implyment algorithm Theoretical integration in swarm intelligence algorithm, attempts to analyze the different features of existing swarm intelligence algorithm, based on group collaboration in higher organisms, the genetic evolution of biological populations and statistical study of the distribution estimated three levels, to improve the test performance of basic BFO from the micro-behavior, genetic improvement and macro guidance, and make it evolve with the coordination of multiple intelligence and learning to adapt, so as to improve the algorithm search speed and accuracy purposes. This paper attempts to build the BFO algorithm not only has some innovation in method, but also has some sense of the theoretical innovation with more positive thinking for the existing smart computing reference. The main thesis research in the following areas:(1) summarizes the basic principles and the main method of group intelligent computing in bionic optimization, analyze the no free lunch theorems (NFL) of existing algorithms to compare the performance, describes the standard test functions and the indicators that the algorithm used to compare the performance and to assessment population diversity, revealing the ideological basis of the group intelligent calculation, giving some evaluation system and theoretical reference for algorithm optimization and its improvement for the follow-up article. (2) study the basic principles in-depth of bacterial foraging optimization, analyze the algorithm limitations in algorithm optimization of the current trend, breeding and migration operator, getting some experience and learn from the analysis and discussion, compare the PSO and BFO in the foraging behavior of the two strategies, use the bacteria energy and fitness to simulate unconventional and conventional feeding strategies to verify the different feeding strategies on the performance of the algorithm impact, concludes with four improvement goals and improving behavioral strategies in bacterial foraging optimization.(3) analyzed the two main acts of competition and collaboration in biological food processes in the food, discussed the collaborative and learning idea of fish-based algorithm and particle swarm algorithm. Algorithm based on the idea of fish group, giving the bacteria the ability to perceive the state population, can tracking the excellent value and move closer to the community center, presented environmental awareness BFO algorithm to improve the problem solution accuracy. PSO-based self-learning and social learning ideas, put forward the collaboration BFO, makes the algorithm has a greater probability to obtain the global optimal solution.(4) analyzed the survival of the fittest, species selection and the genetics theory of biological evolution, discussed a broad evolutionary computation method,and analyzed the main ideas based on genetic algorithms and evolutionary computation. Bacteria based on differential evolution ideas to achieve bacterial population optimal through the difference between individuals within the group cooperation and competition, thus to amend the dimensions degradation of cycle, the differential operator improved significantly BFO algorithm accuracy, robustness and the ability to obtain the global optimum. Based on the idea of life immune system, this article set up clonal reproduction operator based on immune-body, and to clone elite bacteria, to variate high-frequency and to cross random after the period of chemotactic completion, so to guide the operator search, making the algorithm has good applicability on some test function, and can converge quickly to find the global optimum.(5) analyzeing the latest smart way of distribution of estimates, discussing the possibility of estimates algorithms of distribution introducing to intelligent computing, which can take full advantage of the practical problems of prior information, to complete the model from the guiding in the macro ideology. Based on the Gaussian distribution ideas, in the breeding cycle after the end of bacteria chemotaxis, we introducting the concept of Gaussian distribution breeding which to build statistical modeling from the macro based the best part of the bacteria, new algorithm improves significantly the BFO accuracy and robustness, and has great adaptability to some test function. Based on the real bacteria growth curve, breaking three nested frames of BFO algorithm, this article simulate the law of bacterial flora free distribution in the optimization process, established the system model of self-reproduction and self-demise of the bacteria, then privoded some evidence for the above BFO algorithm related to performance from another side. (6) use standard test functions to test the validation of the performance for bacteria foraging optimization algorithm improvement, and designed and developed a corresponding computer program in the MATLAB software platform that attached. For the actual optimization of continuous space and discrete space, we use neural networks prediction model and job shop scheduling problem to verify the performance of the new algorithm, extends the application space of the continuity BFO, and provides a new information processing and intelligent computing tools for weight optimization of neural network model and the job scheduling solution optimization.更多还原