求解整数规划的一种仿生类全局优化算法——模拟植物生长算法

针对整数规划全局优化问题所首次提出的模拟植物生长算法,是一种源于大自然的仿生类随机算法.该算法从植物的向光性特点出发,将整数规划的可行域作为植物的生长环境,根据各可行解目标函数的变化情况确定植物的生长信息(形态素浓度),进而模拟出向光源(全局最优解)迅速生长的植物生长动力学模型.经过对无约束和有约束两类具有多个全局最优解的非线性整数规划问题的具体求解,取得了满意的效果.     

模拟植物生长算法的原理及应用

为解决国外主流智能算法普遍存在的参数选择难题,模拟植物生长算法(PGSA)以植物独有的向性运动为启发式准则,将优化问题的解空间当做植物的生长环境,通过生长信息和分枝模式(L-系统)构造出依赖优化环境而不断生长的人工植物分枝生长模式,建立了跳出局部最优解并迅速求出全局最优解的遍历搜索机制和智能算法体系.模拟植物生长算法开拓了"无参数智能优化算法"研究的新领域,本文从该算法的思想源头进行阐述,对国内外学者近年来在不同研究领域应用该算法的情况进行了分析和评述,指出了植物生长原理对智能优化领域的影响以及未来的发展方向.     

模拟植物生长算法在设施选址问题中的应用

以模拟植物生长算法为工具,提出了一种解决设施选址问题的智能优化算法, 结合配送中心选址的实际案例,将模拟植物生长算法与遗传算法的计算结果进行比较,结果表明该算法比遗传算法在精度上有所提高;在此基础上,以50个随机选取的用户为背景,解决了韦伯型多设施选址问题, 不同于其它启发式算法,模拟植物生长算法在得到全局最优解的同时,还可以根据设施数量的不同,将全局最优解与局部最优解进行组合,可以建立整体最优的设施布局, 本算法在应用中显示了精确性、稳定性和通用性特点,是模拟植物生长算法在解决选址问题上的具体应用。     

基于模拟植物生长算法的易腐物品物流中心选址

配送中心作为物流系统的枢纽,其位置的选取直接影响总消耗成本的高低.本文提出了基于模拟植物生长算法求解易腐物品配送中心选址问题的新方法.通过对系统数学建模,利用改进的模拟植物生长算法来求解最优解.最后通过对实倒进行仿真实验,结果表明本算法不仅可获得配送中心的最优解,算法精度也有提高,明显优于其它方法.     

基于模拟植物生长算法的车辆调度问题

基于配送企业车辆资源的限制和客户需求时间窗的要求,在考虑外包车辆和配送入员加班的情况下,对带时间窗的车辆调度问题进行扩展研究.根据客户需求的随机性特点构建以最小化车辆配送总成本为目标的机会约束规划模型,并设计求解该问题的模拟植物生长算法.结合车辆调度具体实例,将模拟植物生长算法与遗传算法进行比较,结果表明该算法不仅可以获得最优解,而且提高了求解效率,是一种有效的方法.     

大型城市地下物流网络优化布局的模拟植物生长算法

交通拥堵问题的加剧使传统物流网络在我国大型城市已达到极限, 未来地面物流系统将逐步向地下不同层次里转移并释放出城市地上空间.本文以斯坦纳最小树(SMT)为理论模型, 建立了符合我国大型城市不断扩展这一特点的树状地下物流网络布局模型. 由于 SMT 为 NP-完全问题, 因此算法的寻优能力是研究的关键. 本文所采用的模拟植物生长算法(PGSA)是以植物向光性理论为启发式准则的智能算法, 该算法是利用人工植物在给定物流节点集解空间中的生长过程得到城市地下物流网络的最优布局. 通过对国际公布的STEINLIB实例数据计算并与蚁群算法和模拟退火算法进行比较, 表明模拟植物生长算法具有较强的精确性、稳定性和全局搜索能力.     

PGAs求解双层规划及其在分销系统优化设计中的应用

研究并行基因算法求解双层规划问题及其在供应链物流分销系统优化设计中的应用.利用下层优化问题的KKT条件把双层规划问题转化为等价的单层规划问题,再利用并行基因算法对得到的单层规划问题进行全局优化,从而得到双层规划问题的全局最优解,最后,通过具体案例研究了上述算法在供应链物流分销系统优化设计中的应用.结果表明,并行基因算法求解双层规划,充分利用了现有计算环境的并行能力,加快了收敛速度,改善了基因算法的全局收敛性能,算法达到了实用化的规模,是一种很有应用前景的计算方法.     

基于分布式协商进化算法的多Agent目标冲突消解

针对多Agent系统研究中的目标冲突消解问题,建立了在多个Agent的局部目标和系统全局目标间进行协调优化的多目标优化模型.在多Agent分布式规划的框架下,提出了一种基于遗传算法(genetic algorithm,GA)的分布式协商进化算法,用于求解多目标规划模型.针对GA搜索中保持解的多样性、提高收敛速度等问题,对选择算子进行了设计.通过仿真实验,证明新的选择算子能有效提高解的质量.最后将该算法应用于部队机动协同路线规划的目标冲突消解问题,验证了其有效性.     

协同粒子群-模拟退火算法求解VRPSPD问题

研究逆向物流车辆路径(VRPSPD)问题,建立了VRPSPD问题的混合整数规划模型.利用启发式算法的特点构造求解VRPSPD问题的一种协同PSO_SA算法,设计了该算法初始种群的编码规则、信息交换策略、2-opt邻域解生成策略和SA算法中的冷却进度表规则.实验过程以典型算例为例进行了实验,并对重要参数进行了分析.实验结果表明,该算法对于求解VRPSPD 问题,可以有效提高车辆的负载使用率,避免因负载波动和最大负载能力约束而增加车辆总行程,在可以接受的迭代次数限制内可以收敛到满意解.     

多车型电动汽车车辆路径问题的分支定价算法研究

随着环境意识的日益提升和电动汽车的逐渐普及,考虑到物流企业中不同类型的电动汽车的电池最大容量、电池充电率、电量单位消耗率、最大载重量、固定成本和可变成本不同,本文研究含时间窗的多车型电动汽车车辆路径问题,建立了一个混合整数规划模型,并利用分支定价算法求其最优解.为了加快算法的求解速度,本文提出生成下界值的方法以对车辆类型进行预处理操作,并制定了生成整数解上界的策略以压缩解空间.然后,通过用多组算例验证了模型和算法结果的准确性,同时也证明了本文提出的加速过程能有效地提高算法的求解速率.最后,通过不同规模的算例分析了车辆可变成本的变化对结果的影响.     

一种新的免疫进化算法及其性能分析

基于免疫系统中的进化机理，提出了一种免疫进化算法。首先引入了邻域概念，并通过定义扩展半径和突变半径两个新算法参数而构造了较小和较大两个邻域。进而给出了扩展和突变操作分别利用这两个邻域进行局部和全局搜索，实现了从全局到局部的两层邻域搜索机制。分析了算法的优化机理和收敛性。仿真结果表明该算法具有不易陷入局部最优、解的精度高、收敛速度快等优点。     

An Approximate Algorithm for a Class of Nonlinear Bilevel Integer Programming

The algorithm for a class of nonlinear bilevel integer programming is discussed in this paper. It is based on the theory and algorithm for nonlinear integer programming. The continuity methods for integer programming are studied in this paper. After simulated annealing algorithm is applied to the upper-level programming problem and the thought of filled function method for continuous global optimization is applied to the corresponding lower-level programming, an approximate algorithm is established. The satisfactory algorithm is elaborated in the following example.     

Solving function optimization problems with the immune principle

Adaptive immune evolutionary algorithm is proposed based on the principle of adaptive immune response. Two new algorithm parameters of expansion radius and mutation radius are defined to construct a small neighborhood and a large neighborhood, then expansion and mutation operations are designed to search the local and global regions of solution space simultaneously by using the two neighborhoods, thus, two-level neighborhood search mechanism is realized. The degree of the diversity in the population is described with the average Euclideandistance among all individuals, and it is used to adjust algorithm parameters adaptively to accelerate convergence and avoid getting stuck at local optima. The algorithm is proved to be convergent and its optimization principle is analyzed. The experiment results of multi-modal function optimization show that the algorithm is effective.     

基于蜂群-粒子群算法的天然林空间结构优化

天然林空间结构包含林木的空间位置信息,影响着林木的生长、竞争、林分的稳定及森林的发展,其优化是个多目标规划问题。提出一种蜂群-粒子群(ABC-PSO)混合算法,该算法在初始粒子产生机制、随蜂数量及循环机制上对蜂群算法做了改进,并将其应用到天然林空间结构多目标优化中,最终建立能够兼顾林木分布格局、林木大小分割、林木竞争的优化模型。仿真实验表明,蜂群-粒子群算法提升了森林健康等级,解决了森林空间结构多目标优化问题。     

一种求解连续空间优化问题的改进蚁群算法

蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智能进化算法,该算法采用分布式并行计算和正反馈机制,易于与其它方法结合,目前虽然已经在离散空间优化领域中得到了广泛应用,但是在求解连续空间优化问题方面的研究相对较少。在介绍基本蚁群算法机制原理和数学模型的基础上,提出了一种用于求解连续空间优化问题的改进蚁群算法。将连续空间优化问题的解向量分解成有限个网格,同时构造了一个与蚁群转移概率相关的评价函数,并借助相遇搜索策略对蚁群算法进行了改进,将各条寻优路径上可能的残留信息素数量限制在一个最大最小区间,以提高改进后蚁群算法的全局收敛性能。仿真实验表明,提出的改进蚁群算法较文献[11]所提出的自适应蚁群算法能更快地找到连续空间优化问题更优良的全局解,从而为蚁群算法求解这类问题提供了一条可行有效的新途径。     

基于改进狼群算法与仿真的单元调度优化

单元制造是现代生产系统的重要组织形式。对制造单元的调度过程中,机器故障与中断是很常见的问题,机器空转造成的能源浪费也不可忽视,相关研究具有重要现实意义。考虑单元调度中的机器中断和能耗,建立了一个最小化所有工件完工时间及机器闲置能源消耗和中断成本的整数规划模型,并提出了一种基于改进狼群算法和离散事件仿真的混合优化方法加以求解,有效提高了算法的寻优能力。数值实验表明,提出的算法具有良好的收敛性,可以在合理的迭代次数内找到问题的满意解。     

基于混合优化方法的立体匹配算法

为了改善线性生长算法获得视差图可靠性差的问题,提出了一种基于混合优化方法的立体匹配算法。该算法综合考虑了计算效率和图像可靠性,将视差匹配转换为多目标优化问题,通过提出的基于模拟退火的鸽群优化算法求解此优化问题,从而实现视差阈值的自适应调节,并获取相应的根点的最优视差值。所提出的混合优化方法较好地克服了局部寻优和全局寻优方法易受初值影响且收敛速度慢的缺点。此外,为了进一步提高视差图可靠性,利用滤波法去除不可靠的视差。仿真结果表明,该算法可以获得更多深度信息,提高了线性生长算法计算视差图的可靠性和鲁棒性。     

基于混合优化方法的立体匹配算法

为了改善线性生长算法获得视差图可靠性差的问题,提出了一种基于混合优化方法的立体匹配算法。该算法综合考虑了计算效率和图像可靠性,将视差匹配转换为多目标优化问题,通过提出的基于模拟退火的鸽群优化算法求解此优化问题,从而实现视差阈值的自适应调节,并获取相应的根点的最优视差值。所提出的混合优化方法较好地克服了局部寻优和全局寻优方法易受初值影响且收敛速度慢的缺点。此外,为了进一步提高视差图可靠性,利用滤波法去除不可靠的视差。仿真结果表明,该算法可以获得更多深度信息,提高了线性生长算法计算视差图的可靠性和鲁棒性。