论文部分内容阅读
随着人类生存空间的扩大,以及认识世界视野的扩宽和改造世界要求的深入,从理论研究和工业生产中产生了越来越多的更加复杂的优化问题,传统的优化方法已不再适用。20世纪90年代生物学家及计算专家通过对社会型生物的观察和研究提出了许多基于模拟生物行为特征的智能优化算法。由于此类算法在传统NP问题和实际复杂优化问题的求解中显示出了强大的生命力和进一步发展的潜力,因此目前已成为人工智能、经济、社会、生物等交叉学科的研究热点和前沿领域。
本论文的研究目的一方面针对传统基于生物行为启发的优化算法中存在的缺点,从生物学的角度给出其改进方法或提出新的优化算法,使之更为有效可靠;另一方面,将提出的新算法应用于实际工程,拓展群智能优化算法的应用领域。
研究内容包括:基于方向引导的菌群算法、子群协作群搜索算法及其应用、求解车辆路径问题的两阶段遗传算法、基于生物生命周期特征的群搜索算法及其应用。具体的研究内容和创新性成果概括如下:
在标准菌群算法中,细菌在趋化过程中的翻转方向随机性导致了算法收敛速度较慢且较难寻到全局最优解。本文从生物学的角度出发提出了改进的菌群算法;BF-PSO。根据细菌的生物特性,细菌在游动时会发出自诱导分子,同时,他也会根据周围自诱导分子浓度来决定下一步的游动方向。在改进算法中,个体在趋化过程中,其翻转方向会受到全局最优个体分泌自诱导分子浓度的影响。此机制的引入旨在提高算法的收敛速度。实验研究表明,提出的改进算法在一定程度上解决了标准菌群算法寻优速度较慢问题。
约束条件的存在使搜索空间新增了不可行域,优化也变得相对困难。针对传统群体智能优化模型中个体信息交互单一易产生群体“趋同”的问题,启发于生物共生现象,基于标准群搜索算法,设计了子群协作群搜索算法;iGSO。算法将种群按照约束条件分为可行子群和不可行子群,每个子群都有各自不同的生存模式。子群协作模式实现了子群间可以进行信息交流,避免了种群内部单一信息交流引起的误判,确保提出算法的开发能力与探测能力之间的平衡。实验结果表明子群协作群搜索算法较好的解决了附有约束条件的机械优化设计问题。
车辆路径问题是典型的组合优化问题,现已被证明是NP难问题。针对此问题,本文提出了两阶段遗传算法。算法在第一阶段,试图在全局范围内寻找可行解;在第二阶段,种群邻域结构发生改变,算法只在局部搜索空间进行下一步的精确寻优。实验结果表明,两阶段遗传算法能很好的求解小规模及中等规模带容量约束车辆路径问题。
通过考察生物生命周期特征,采用基于个体建模方法,提出了一种新的群体智能优化算法:生命周期群搜索算法(Life-cycle Swarm Optimization,LSO)。该算法对生物的生命周期过程进行了模拟,主要考虑了生物生命周期的四个特征:生长、发育、繁殖和死亡。在该算法中,个体所处环境的适应度用其能量来表示,个体通过选择趋化机制、同化机制或换位机制来逐渐增强个体适应度,从而实现不断的生长发育。个体通过交叉配对实现繁殖。生物生存环境中的资源是有限的,按照“适者生存”理论,种群中适应度低的个体将会被淘汰,即死亡。当一部分个体死亡后,则会产生新的生命继续执行生命交替现象。此外,还引入了生物变异特征,以加强群体的多样性,避免陷入局部最优。LSO算法基于典型的无约束优化问题和约束优化问题进行了测试,分析并讨论了LSO算法在这两类问题中求解效果,并与其它的算法进行了性能比较。
本论文将LSO算法分别应用于多目标优化和带时间窗车辆路径两类问题。针对多目标优化问题,基于非支配排序提出了NLSO算法,并对NLSO算法基于ZDT多目标函数进行了测试。与传统进化计算方法相比较,NLSO在最优非劣解集的逼近性和复杂多目标问题的解的均匀性均获得了令人满意的结果。带时间窗车辆路径问题是典型的NP难问题,本文将LSO算法用于求解小规模的时间窗车辆路径问题,并与其它算法进行了结果比较,结果显示LSO具有较好的求解组合优化问题竞争力。