SIA OpenIR  > 工业信息学研究室
基于生物行为的复杂系统优化算法与应用研究
Alternative TitleResearch on Complex System Optimization Algorithms and their Applications based on Biological Behaviors
申海1,2
Department工业信息学研究室
Thesis Advisor朱云龙 ; 吴青华
ClassificationN945.15
Keyword生物启发式计算 群体智能 菌群算法 群搜索算法 遗传算法
Call NumberN945.15/S38/2011
Pages121页
Degree Discipline机械电子工程
Degree Name博士
2011-03-18
Degree Grantor中国科学院沈阳自动化研究所
Place of Conferral沈阳
Abstract随着人类生存空间的扩大,以及认识世界视野的扩宽和改造世界要求的深入,从理论研究和工业生产中产生了越来越多的更加复杂的优化问题,传统的优化方法已不再适用。20世纪90年代生物学家及计算专家通过对社会型生物的观察和研究提出了许多基于模拟生物行为特征的智能优化算法。由于此类算法在传统NP问题和实际复杂优化问题的求解中显示出了强大的生命力和进一步发展的潜力,因此目前已成为人工智能、经济、社会、生物等交叉学科的研究热点和前沿领域。    本论文的研究目的一方面针对传统基于生物行为启发的优化算法中存在的缺点,从生物学的角度给出其改进方法或提出新的优化算法,使之更为有效可靠;另一方面,将提出的新算法应用于实际工程,拓展群智能优化算法的应用领域。 研究内容包括:基于方向引导的菌群算法、子群协作群搜索算法及其应用、求解车辆路径问题的两阶段遗传算法、基于生物生命周期特征的群搜索算法及其应用。具体的研究内容和创新性成果概括如下:    在标准菌群算法中,细菌在趋化过程中的翻转方向随机性导致了算法收敛速度较慢且较难寻到全局最优解。本文从生物学的角度出发提出了改进的菌群算法:BF-PSO。根据细菌的生物特性,细菌在游动时会发出自诱导分子,同时,他也会根据周围自诱导分子浓度来决定下一步的游动方向。在改进算法中,个体在趋化过程中,其翻转方向会受到全局最优个体分泌自诱导分子浓度的影响。此机制的引入旨在提高算法的收敛速度。实验研究表明,提出的改进算法在一定程度上解决了标准菌群算法寻优速度较慢问题。     约束条件的存在使搜索空间新增了不可行域,优化也变得相对困难。针对传统群体智能优化模型中个体信息交互单一易产生群体“趋同”的问题,启发于生物共生现象,基于标准群搜索算法,设计了子群协作群搜索算法:iGSO。算法将种群按照约束条件分为可行子群和不可行子群,每个子群都有各自不同的生存模式。子群协作模式实现了子群间可以进行信息交流,避免了种群内部单一信息交流引起的误判,确保提出算法的开发能力与探测能力之间的平衡。实验结果表明子群协作群搜索算法较好的解决了附有约束条件的机械优化设计问题。    车辆路径问题是典型的组合优化问题,现已被证明是NP难问题。针对此问题,本文提出了两阶段遗传算法。算法在第一阶段,试图在全局范围内寻找可行解;在第二阶段,种群邻域结构发生改变,算法只在局部搜索空间进行下一步的精确寻优。实验结果表明,两阶段遗传算法能很好的求解小规模及中等规模带容量约束车辆路径问题。    通过考察生物生命周期特征,采用基于个体建模方法,提出了一种新的群体智能优化算法:生命周期群搜索算法(Life-cycle Swarm Optimization, LSO)。该算法对生物的生命周期过程进行了模拟,主要考虑了生物生命周期的四个特征:生长、发育、繁殖和死亡。在该算法中,个体所处环境的适应度用其能量来表示,个体通过选择趋化机制、同化机制或换位机制来逐渐增强个体适应度,从而实现不断的生长发育。个体通过交叉配对实现繁殖。生物生存环境中的资源是有限的,按照“适者生存”理论,种群中适应度低的个体将会被淘汰,即死亡。当一部分个体死亡后,则会产生新的生命继续执行生命交替现象。此外,还引入了生物变异特征,以加强群体的多样性,避免陷入局部最优。LSO算法基于典型的无约束优化问题和约束优化问题进行了测试,分析并讨论了LSO算法在这两类问题中求解效果,并与其它的算法进行了性能比较。    本论文将LSO算法分别应用于多目标优化和带时间窗车辆路径两类问题。针对多目标优化问题,基于非支配排序提出了NLSO算法,并对NLSO算法基于ZDT多目标函数进行了测试。与传统进化计算方法相比较,NLSO在最优非劣解集的逼近性和复杂多目标问题的解的均匀性均获得了令人满意的结果。带时间窗车辆路径问题是典型的NP难问题,本文将LSO算法用于求解小规模的时间窗车辆路径问题,并与其它算法进行了结果比较,结果显示LSO具有较好的求解组合优化问题竞争力。
Other AbstractWith the expansion of human living space, and the widening vision of understand the world and the deepening of requirements to change the world, emergence more and more complex optimization problems from the theoretical research and industrial production, now traditional optimization methods are no longer applicable. In the 1990s, biologists and computational experts propose a number of intelligent optimization algorithms based on the simulation bio-behavioral characteristics through observation and researching social-type organisms. Since these algorithms shows strong vitality and potential for further development in the traditional NP optimization problems and practical complex optimization problems, Intelligent optimization algorithms based on the simulation bio-behavioral is a rising front field, and have become a and research focus in some interdisciplinary fields, such as artificial intelligence, economic, social, and biological and so on.      On one hand, the purpose of this research is want to aim for the shortcomings existing traditional intelligent optimization algorithm inspired by biological behavior, and give its improved methods or propose new optimization algorithm in order to make them more effective and reliable. On the other hand, the presented new algorithm will be applied to reality engineering problem, and expanding the application field of intelligent optimization algorithms.  Research content include: bacterial foraging optimization algorithm with direction guide strategy, subpopulation cooperation group search optimizer algorithm and its application, the two-stage genetic algorithm for solving vehicle routing problem, life-cycle swarm optimization based on the characteristics of biological life cycle and its application. Specific research content and innovative achievements summarized as follows:      During the process of individual chemotaxis of the standard Bacterial Foraging Optimization Algorithm, the bacterial chemotaxis behavior depends on random search directions, which may lead to delay in reaching the global solution. From the biological point of view, this paper proposed an improved algorithm: BF-PSO. According to the bacterial biological characteristics, bacteria will issue self-induced molecules in swimming, and at the same time, the bacteria would determine the swimming direction of the next step based on the self-induced molecules concentration surrounding it. For BF-PSO, in the process of individual chemotaxis, the tumble direction of individual will be affected by self-induced molecular concentration of the global best individual. This employed mechanism enhances the convergence speed. Experimental studies show that the improved algorithm solves the problem that the optimization speed of standard bacterial foraging optimization algorithm is slowly on some extent.       The existence of constraints make search space appeared infeasible region, and optimization work has become relatively difficult. According to traditional swarm intelligence optimization method was easy to produce population "convergence" problem because of the singleness of information exchange among individuals, based on standard Group Search Optimizer and inspired by biological symbiosis, this paper proposed subpopulation cooperation group search algorithm: iGSO. iGSO algorithm divided the whole population into two subpopulations in accordance with the constraints: feasible subpopulation and infeasible subpopulation, each subpopulation group has its own evolutionary process. Subpopulations cooperation evolutionary strategy make the subpopulations can exchange information among each other,and avoid the misjudge caused by a singleness of information exchange, and ensure the balance between the development capacity and detection capability of iGSO. Experimental results show that iGSO can better solve mechanical optimization problems with constraints.       Vehicle routing problem is a typical combinatorial optimization problem, and has been proved to be an NP hard problem. In order to solve this problem, this paper proposes a two-stage genetic algorithm. In the first stage of, this algorithm trying to find a feasible solution within the global scope; in the second stage, population neighborhood structure is different, the algorithm proposed begin its further accuracy optimization in the local search space for further. Experimental results show that two-stage genetic algorithm can solve the capacity vehicle routing problem with small-scale and middle-scale.       By studying the characteristics of biological life-cycle and adopting the individual-based modeling method, this paper proposes a new swarm intelligence optimization algorithm-the life cycle swarm optimization (LSO) technique. LSO simulates the biological life-cycle, and mainly considering four characteristics of the biological life cycle: birth, growth, reproduction and death. In this algorithm, the fitness of individuals in their living environment was express using their energy,in order to achieve continuous growth and development, individual need select foraging mechanism: chemotactic, assimilation or transposition, which can gradually enhance the individual fitness. Individuals will reproduce offspring via crossover. Living environment of biological resources is limited, in accordance with the "survival of the fittest" theory, the individual with low fitness will be eliminated, and that is death. When an original life ends, a new life generated will repeat "life and death alternation" cycle process. In addition, LSO also employ mutation characteristic which was used to enhance the population diversity and avoid trapping in local extreme. LSO algorithm was test on a typical unconstrained optimization and constrained optimization problems, the experimental results were analyzed and discussed.     In this paper, LSO algorithm was applied to two types of problems: multi-objective optimization problem and the vehicle routing problem with time windows. Aiming at the first type of test problems, this paper proposes NLSO algorithm based on the non-dominated sorting, and the NLSO was test on ZDT multi-objective test functions. Compared with the traditional evolutionary computation methods, NLSO obtained satisfactory experimental results on two performance index: generational distance and the spacing. Vehicle routing problem with time windows is a typical NP-hard problem, use the LSO algorithm was test on small-scale VRPTW in this paper, the experimental results show LSO has good competition ability for solving combinatorial optimization problems.
Language中文
Contribution Rank1
Document Type学位论文
Identifierhttp://ir.sia.cn/handle/173321/9354
Collection工业信息学研究室
Affiliation1.中国科学院沈阳自动化研究所
2.中国科学院研究生院
Recommended Citation
GB/T 7714
申海. 基于生物行为的复杂系统优化算法与应用研究[D]. 沈阳. 中国科学院沈阳自动化研究所,2011.
Files in This Item:
File Name/Size DocType Version Access License
基于生物行为的复杂系统优化算法与应用研究(2496KB) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[申海]'s Articles
Baidu academic
Similar articles in Baidu academic
[申海]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[申海]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.