多模型算法（精选11篇）
多模型算法 篇1
机动目标跟踪问题一直是军用领域热切关注的问题。机动目标跟踪在现代战争和国防领域的地位至关重要[1,2]。目标跟踪和定位是火力控制系统的核心,它直接关系到系统的反应时间、跟踪精度和武器的命中率。因此,对目标的跟踪问题进行理论研究和推广应用,具有重大的理论和实际意义。该文主要就静态多模型方法及其在机动目标跟踪中的应用展开了研究,首先引入了机动目标跟踪常用的两种模型:近似匀速模型(CV)和近似匀加速模型(CA);其次重点讨论了静态多模型算法的基本原理、算法流程,通过与GBP1算法的比较,揭示了静态多模型算法的缺陷。GBP1
1 跟踪模型
1.1 运动模型
假设任意时刻,目标服从以下两种运动模型的一种:(1) 匀速直线运动CV模型;(2)匀加速直线运动CA模型。考虑目标在x - 平面运动,运动方程为:
其中X(k+ 1) =[xk xk xk]表示目标的位置、速度及加速度,w(k) 为随机噪声,Φ为状态转移矩阵。(1)CV
根据式(1),对应的CV模型为:
CA模型为:
1.2 量测模型
2 多模型(MM)算法[3]
2.1 静态多模型算法(SMM)
在固定模型中静态多模型算法我们可以用以下统计特性表示。
首先根据Bayes公式,下一时刻j正确的模型概率被统计为:
同时计算与mjk匹配的似然函数
当从模型匹配符合模型j时,则将更新vj与Sj以及它们的协方差
最终融合估计
以上为静态多模型算法(SMM)的基本步骤,从以上几个公式中可以看出静态多模型算法较为简便,实现也较为简便。
2.2 GPB1算法
如图2,与静态多模型算法相比,GPB1算法把上次总体的状态估计xk - 1|k - 1以及估计误差的协方差Pk - 1k - 1作为公共的初始条件,然后各个模型按照基本的Kalman算法进行各自的状态估计,计算各个模型的概率。最后利用加权和求出本次的总体状态估计xk|k及其协方差阵Pk|k。
重新初始化:
条件滤波和模型的概率更新与SMM算法类似。
估计合成:
3仿真
假设目标的起始位置在笛卡尔坐标的位置(2200,100),目标在t = 0 - 50s的时间内做初始速度为vx= -10,vy= 10 ,的匀速直线运动,在t = 50 - 70s的时间内做加速度为ax= -1,ay= 1的匀加速运动,接着在t = 70 - 100s的时间内做匀速直线运动。仿真的观测量为目标的与雷达(位于坐标原点)的距离r ,与目标的方位角θ。观测模型:Zk= h(Xk)+ vk,其中vk满足零均值高斯白噪声分布。设定模型观测噪声标准差R_Q = 50,Th ETA_Q = 0.01。
下面,通过GPB1算法对已建立的目标场景进行仿真并与SMM算法比较。
从图3-1可以看出,相同场景下GPB1与SMM都能跟踪运动目标,但是从图3-2可以看出GPB1算法的跟踪误差明显小于SMM的跟踪误差。这也从实例上验证了GPB1算法要优于SMM算法。
4 结论
本文针对机动目标跟踪算法进行研究:首先详细介绍了两种基本的运动模型即CV模型和CA模型,其次介绍了非线性量测模型。在多模型算法中介绍了静态多模型算法(SMM),同时结合扩展卡尔曼滤波对其进行了仿真实验,通过与GPB1算法对比分析静态多模型算法(SMM)的缺陷。
摘要：目标跟踪是指利用传感器测量对目标运动状态进行估计。该文针对这一问题,首先建立机动目标跟踪模型;然后实现了基于扩展卡尔曼滤波的静态多模型算法,并对静态多模型与GPB1算法进行了比较。
关键词：机动目标跟踪,扩展卡尔曼滤波,静态多模型算法
参考文献
[1]周宏仁.机动目标跟踪[M].北京:国防工业出版社,1991:2-8.
[2]党建武.水下多目标跟踪理论[M].西安:西北工业大学出版社,2009:26-27.
[3]许江湖.目标跟踪中的多模型估计算法综述[J].情报指挥控制系统与仿真技术,2002(5)26-29.
[4]嵇成新,徐江湖,陈康.跟踪机动目标的多模型算法进展[J].系统工程与电子技术,2003,25(7):882-888.
多模型算法 篇2
2 多岛遗传算法
遗传算法是一类借鉴生物界的进化规律演化而来的非经典优化算法。与传统的优化算法相比，遗传算法不存在求导和目标函数连续性的限定，且具有全局寻优能力。但传统的遗传算法在优化过程中基因突变的概率较低，容易在进化几代后出现早熟现象，导致优化结果收敛于局部最优解。
3 数值算例
以某飞行器为例，依据其一级满油、一级空油、二级满油、二级空油 4 种典型飞行状态下的前两阶模态频率和振型试验结果，选取各舱段材料的弹性模量为优化变量，数值分析与试验结果差异为优化目标，采用本文方法进行动力学模型修正。
4 结 论
a)提出了基于多岛遗传算法的多状态结构动力学模型并行修正方法，改进了传统方法针对同一产品不同试验状态分别修正模型，导致同一产品模型参数不一致的不足，更符合工程实际;
b)动力学模型并行修正方法中各试验状态的残差之间相互独立，且对残差的物理意义没有约束，可以同时对动力学特性和动力学响应模型进行修正;
c)采用多岛遗传算法驱动优化流程，避免了经典优化算法需要对目标函数求导的限制，同时保证了设计参数收敛于全局最优解;
智能算法解决多目标问题的应用 篇3
关键词：智能算法；最优解；多目标问题
一、多目标优化遗传算法的基本理论
多目标遗传算法（multi-objective genetic algorithm，MOGA）作为一种模拟生物自然选择的随机搜索算法，适用于求解高度复杂的非线性问题得到了非常广泛的应用，同时又具有较好的通用性。
多目标优化问题可描述为：求解一个决策变量向量，它满足所有约束并且使得由目标函数组成的向量最优化。可以描述如下：
求一个决策变量向量X=[x1，x2，…，xn]T，满足k个不等式约束：gi（X）≧ 0 i = 1，2，…，k。同时满足m个等式约束：hi（X）= 0 i = 1，2，…，m。
设有r个优化目标，且这r个目标是相互冲突的，可表示为：f（X）=（f1（X），f2（X），…fr（X））
二、Pareto最优的定义
多目标优化中的最优解通常称为Pareto最优解，一般进行如下描述：设X1，X2∈Ω，对所有i（1≤i≤m），有fi（X1）≤fi（X2），且对于任意i，Fi（X1）≤Fi（X2）则称X1支配X2。如果一个可行解Xp没有被任何X∈Ω支配，就称Xp为Pareto 最优解。
三、适应度函数的设计
定義个体适应度函数为：
四、智能混合遗传算法的步骤
（1） 初始化群体。随机选取初始化种群F（x）。（2） 评价个体的优劣，计算当前种群每个个体对应的目标函数的函数值，然后对Pareto最优解临时储备库进行更新操作。（3） 选择操作。随机确定各目标函数权值wi=randi/randj，根据选择概率选择一对父代个体。（4） 交叉和变异，对N-Nelite对父代个体的每对执行交叉操作，每对父代个体通过交叉产生一个新个体，然后对新个体执行变异操作。（5） 从临时非劣解集中随机选出Nelite个个体与前面产生的N-Nelite个个体一起构成新的群体F′（x）。（6） 对群体中的所有解进行局部搜索，局部搜索方向由第（3）步父代个体选择时确定的权值决定，并由局部搜索产生的N个新解代替当前种群。p（x）=。公式中f为种群P中最劣个体的适应度值，在第（1）步中，各个目标函数的取值随机确定，每一组权值都将对应一种搜索方向。因此局部搜索的方向是多样的。
五、实验结果分析
通过实验可以看出：智能混合遗传算法能够有效地得到问题的pareto最优解，而且解的分布情况良好。
参考文献：
[1] 雷德明，严新平.多目标智能优化算法及其应用[M].北京：科学出版社，2009.
一种多算法协同定位模型 篇4
数据融合技术是结合有关先验信息, 综合不同处理方法和技术的优点对不同类型的数据进行融合, 从而获得比单一处理方法和技术更优数据输出的技术[1]。目前, 一些研究者已经在基于JDL数据融合模型上面做了很多的工作[2,3,4,5]。文献[2,3,4,5]包括有综合利用到TOA, TDOA, AOA三种测量值来进行融合技术, 但是由于要进行不同参数的测量, 限制了这些方法的实用化;文献[6]虽然单独利用TDOA进行融合, 实现容易, 但对于移动台某一个确定位置, 其定位结果有较大的误差。
由于基于TDOA的定位方法不需要基站与移动台之间严格的同步, 因此在基于蜂窝网的移动台定位技术中, 大部分无线定位算法都是基于TDOA的, 其中比较经典的算法有Chan算法和泰勒序列展开法。在不同的信道环境中他们各自具有其特有的优点, 同时也存在局限性。为了提高移动台的定位准确度, 将综合这两种算法, 并且结合了简单的残差加权算法, 构造先验信息, 对Kleine-Ostmarm数据融合模型[7,8]进行改进, 提出一种无需先验信息的, 利用Chan算法和泰勒序列展开法定位结果进行融合的算法协同定位模型。由于在数据融合过程中需要利用简单的残差加权算法, 因此下面先对之进行较为详细的介绍。
1 简单的残差加权算法
设参与定位的基站个数为M≥4, 待定位的移动台坐标为 (x, y) , (xi, yi) 为第i个基站发射机的已知位置。根据测量得到的TDOA测量值可以得到下式:
式中:xi, 1=xi-x1;yi, 1=yi-y1;Ki = x
所有的残差平方和为:
对所有的
2 融合方法
各种算法都有其自身的优缺点, Chan算法和泰勒序列展开法都需要先验信息, 在无法知道先验信息的情况下, 都假设TDOA测量值的协方差矩阵为单位矩阵。因此, 先用简单的残差加权法构造TDOA测量值的协方差矩阵[9] (见式 (5) ) , 代入这两种基本算法中, 以减少NLOS误差。此外, 对于泰勒序列展开法, 先通过其他算法进行初始定位, 再将定位结果作为初始值代入其中进行定位计算。本文提出的多算法协同定位的数据融合模型, 如图1所示, 该模型特点如下。
(1) 因为没有任何有关TDOA测量值的先验信息, 所以Chan算法和泰勒序列展开法中的TDOA测量值的协方差矩阵Q是未知的。可以由前面定义的残差函数, 将MS位置初始估计值
将构造后的Q值代入Chan算法和泰勒序列展开法中作为TDOA的协方差矩阵。文献[9]中对此做了详细的分析, 且结果表明, 将与真实位置比较接近的初始值代入残差函数, 构造TDOA的协方差矩阵, 可以有效改善NLOS误差对定位带来的不利影响。
(2) 对于TDOA测量值, 分别采用简单残差加权法、Chan算法、泰勒序列展开法、第一层数据融合和第二层数据融合, 产生五种定位估计, 其中泰勒序列展开法的初值由简单残差加权法产生。
(3) 第一层数据融合
对于同一组TDOA测量值分别采用简单残差加权法、Chan算法和泰勒序列展开法进行定位估计, 每种算法的加权系数Rk, 则:
式中:
式中:K为算法数目。
(4) 第二层数据融合
该层依旧采用加权方式进行数据融合, 在这层进行融合的定位估计有3种, 设每种的加权系数为Rk′, 则定义:
式中:
(5) 第四层数据融合
该层数据融合采用文献[10]方法进行加权处理, 假定Chan算法、泰勒序列展开法、第一层数据融合和第二层数据融合的定位估计值的均值和方差分别为Xcm, Xtm, X1m, X2m和σ2c, σ
3 算法仿真及性能讨论
采用标准7基站/小区蜂窝网络, 小区半径为3 000 m。其中第一个基站为服务基站, 如图2所示。
信道模型采用C0ST259, 环境分别为闹市区、一般市区、郊区和远郊。由于该算法主要是为了减少非视距对定位精度的影响, 因此这里主要对在闹市区的情况进行较为详细的分析。为了验证该模型的性能, 在服务基站的第一扇区内随机选择了12个待定位点, 这12个点随机分布在相邻距离为200 m的同心圆上, 每个点重复仿真200次, 将数据融合各层定位结果定位均方根误差和均值误差与融合结果比较, 以及将数据融合各层误差小于150 m和小于300 m的概率进行比较, 最后比较本融合结果与传统的Chan算法比较。
如图3所示, 得到:经过融合以后, 融合结果相对于参与融合的各层, 其定位均方根误差有明显的减小, 但均值误差并不是最低, 这是因为决策层是用基于最小均方误差的最优线性融合的方法来进行融合的。它只能保证融合后的结果比参与融合各层的均方根误差都小, 而无法保证定位的均值误差也比各层的都小。
如图4所示, 得到, 在定位误差小于150 m概率比较时, 第一层和第二层融合出现了融合结果的概率小于Chan算法。这是因为这两层都是利用线性加权的方法进行融合的, 如果有一个或者若干基站的定位结果较差, 那么就会导致这层融合结果较差。当初始值定位较差时候, 也可能会导致泰勒序列展开法在闹市环境下比Chan算法差。
从图5可以看到, 融合结果无论在定位误差均值还是在均方根误差指标上都比传统的Chan算法优越。在较为严重的非视距环境下, 该算法具有较好的适应性。第一层和第二层都是采用的残差融合方法可以对非视距影响较大的估计分配较小的加权因子, 因而也可以减小非视距的影响, 并且非视距影响越大, 这种效果就越明显。因此本融合模型的定位精度要比Chan算法高, 具有一定的实用性。
4 结 语
在蜂窝网络定位系统中, 由于基于单个测量值的定位方法以及单个算法的定位精度有限, 因此Kleine-Ostmann提出了一种基于JDL的三层定位数据融合模型。为了在没有任何信道环境先验信息的情况下, 融合不同TDOA定位算法的优点, 讨论了一种针对不同TDOA定位算法融合的新型数据融合模型, 利用简单的残差加权算法得到第一步定位估计值, 构造TDOA协方差矩阵和作为泰勒序列展开法的初始值, 并且利用线性加权和贝叶斯推论等融合方法, 得到最好定位结果。仿真结果表明, 在非视距环境下, 该模型有效提高了移动台的定位精度, 且不需要先验信息。
参考文献
[1]Ostmann T Kleine, Bell A.A Data Fusion Architecture forEnhanced Position Estimation in Wireless Networks[J].IEEE Communication Letters, 2001, 5 (8) :343-345.
[2]杜海兵, 王民北.数据融合技术在无线移动定位中的应用[J].计算机工程与应用, 2005 (16) :153-155, 161.
[3]孙国林, 郭伟.基于数据融合的蜂窝无线定位算法研究[J].通信学报, 2003, 24 (1) :137-142.
[4]刘军民, 张展, 刘石.基于数据融合技术的TDOA移动台定位方法[J].大连理工大学学报, 2005, 45 (1) :138-141.
[5]陈朝, 昂志敏.一种基于数据融合的蜂窝无线定位算法模型[J].国外电子测量技术, 2008, 27 (3) :27-30.
[6]邓平, 刘林, 范平志.移动台定位估计数据融合增强模型及其仿真研究[J].通信学报, 2003, 24 (11) :165-17.
[7]范平志, 邓平, 刘林.蜂窝网络无线定位[M].北京:电子工业出版社, 2002.
[8]袁登科.蜂窝网络消除非视距传播误差影响的定位算法研究[D].成都:西南交通大学, 2005.
多模型算法 篇5
Pareto基因算法多目标翼型优化设计
基于Pareto 最优解的定义,通过构造新型的联赛式选择复制等算子而发展了一种适合于求解多目标优化设计的Pareto基因算法.通过等级法来正确识别每一代中近Pareto波阵面的解,从而消除选择误差达到快速收敛的目的.为提高解的`分布性:采用小生境技术解决了基因材料多样性损失问题;采用常规实数编码方式配合平均交叉算子解决了编码端点效应问题.将所发展的方法应用于多目标翼型优化设计中,获得了理想的Pareto波阵面,为决策者提供了一个可选的有效解数据库.
作 者：隋洪涛 陈红全 黄明恪 作者单位：南京航空航天大学,601教研室,江苏,南京,210016刊 名：航空学报 ISTIC EI PKU英文刊名：ACTA AERONAUTICA ET ASTRONAUTICA SINICA年，卷(期)：23(2)分类号：V224关键词：基因算法 Pareto最优解 多目标优化设计 翼型
改进的自适应多目标粒子群算法 篇6
关键词：多目标优化；粒子群优化；帕累托最优；约束控制；边界处理；全局最优选择；自适应控制； 最大传输能力
摘要：边界处理和全局最优引导者选择操作对多目标粒子群算法的性能有重要影响，在考虑不同操作方法特征的基础上，提出了改进的自适应多目标粒子群（multiobjective particle swarm optimization， MOPSO）算法.当算法陷入局部最优时，启用交叉变异操作；当算法收敛性停滞时，轮换修剪边界处理和指数分布边界处理操作；当算法多样性停滞时，轮换反比于拥挤距离和反比于控制粒子数目的全局最优引导者概率选择操作.标准测试函数以及柔性交流输电系统（flexible AC transmission system， FACTS）装置优化配置问题的仿真结果验证了所提算法的有效性.
关键词：多目标优化；粒子群优化；帕累托最优；约束控制；边界处理；全局最优选择；自适应控制； 最大传输能力
摘要：边界处理和全局最优引导者选择操作对多目标粒子群算法的性能有重要影响，在考虑不同操作方法特征的基础上，提出了改进的自适应多目标粒子群（multiobjective particle swarm optimization， MOPSO）算法.当算法陷入局部最优时，启用交叉变异操作；当算法收敛性停滞时，轮换修剪边界处理和指数分布边界处理操作；当算法多样性停滞时，轮换反比于拥挤距离和反比于控制粒子数目的全局最优引导者概率选择操作.标准测试函数以及柔性交流输电系统（flexible AC transmission system， FACTS）装置优化配置问题的仿真结果验证了所提算法的有效性.
多出口建筑人员疏散模型与算法 篇7
关键词：火灾,多出口建筑,人员疏散,启发式算法,疏散模型
随着经济发展,各类建筑的数量与日俱增,但同时伴随建筑功能多样性、人员密集性、疏散通道复杂性等特点,使得建筑的人员疏散问题更加突出。一旦发生火灾等公共突发事件往往会导致人群拥堵,若不能及时进行疏散,极易造成群死群伤事故的发生。因此,火灾发生后,如何及时有效地对人员进行疏散、确定最优的疏散方案尤为必要。
近年来,国内外诸多学者基于不同的实际背景采用不同方法对人员疏散进行研究,主要分为数学分析法和计算机仿真。其中数学分析法是以数学模型为基础,将实际疏散中的各项参数转化为一个可以求解的数学模型,在疏散的数学模型中可以分为微观模型和宏观模型两大类。微观模型主要研究人员的行为特征与心理因素对疏散的影响,宋卫国、房志明、Hamacher H W等人分别通过元胞自动机模型、多格子模型、概率模型等进行了详细的研究,但是由于建筑物体量普遍较大,不能将疏散区域内人员的路径选择较好地反映出来。宏观模型则可以较好地解决这一问题,Tjandra S A等人通过利用动态网络流的方法,建立单源点疏散模型解决了疏散路径的问题。谢旭阳等在考虑建筑物内有害气体体积分数与人群密度的基础上,提出了最短疏散路径的数学模型。袁媛等人通过考虑烟气的扩散影响,将疏散网络中每条弧的疏散速度表示为以时间为变量的函数,并提出了最佳疏散路径算法。而在实际疏散中,路径的容量限制及优先性等因素同样影响路径的选择,Chen P H考虑通过快速流的控制算法计算疏散路径及疏散总人数,从而确定多条最优疏散路径和对应路径上的最佳疏散人员数量。杨建芳等人考虑路径和节点容量受制约的条件下,优先饱和疏散所需时间短的路径,建立以疏散结束时间最小为目标的数学模型。
上述研究在模型的建立和算法上都考虑了动态性与不确定性,从而选择最优路径,但基于不同实际背景往往需要建立不同的具体模型,笔者主要针对建筑人员密集、通道复杂等特点,在考虑火灾中烟气对疏散影响的同时,结合路径和节点饱和的情况,以疏散时间最少为目标,确定疏散中的最优路径,并探究当求解实际参与路径式不成立的条件下,确定疏散方案的方法,以及确定疏散路径中 “重要弧”的意义。
1 问题描述
1.1 问题假设
不同突发灾害事故具有不同的特性,考虑火灾情况下需要将被困人员及时疏散到安全区域,所考虑的疏散模型有如下假设:
(1)全体被困待疏散人员都可以服从指挥,能够完全按照疏散方案疏散;
(2)模型中只有一个受灾点,多个出口,且每个出口存在容量限制;
(3)疏散网络中每条弧都存在容量限制,且对应的疏散路径同样存在容量限制;
(4)出口点有容量限制并将其转化为一条弧,其余点都没有容量;
(5)疏散网络中每条弧上的疏散速度不固定,通过每条弧的时间由弧长和疏散速度决定;
(6)路段满足先进先出规则;
(7)疏散过程不允许发生中途返回和原地绕圈情况。
1.2 符号和决策变量
G=(V,E):疏散网络;
V:节点集,其中包括了三个子集,受灾点S,出口点集D={Dk|k=1,2,…,K},中间点集N={Vn|N=1,2,…,N};
E:弧集,其中eij表示在节点i、j之间的弧(i、j∈V);
lij:表示eij的长度;
hij(t):表示在弧eij上的疏散速度,随着时间的变化而改变,在这里假设hij(t)=h0·αij·e-β(ij)t,其中h0为正常情况下的疏散速度,αij和β(ij)为侵害系数,在不同eij上对速度产生不同的减弱效果;
tij:表示在弧eij上的疏散时间;
cij:表示在弧eij上单位时间内可以通过的最大容量;
Pl:表示可以供疏散人员所选择的路径,l=1,2,…,L;
PCl:表示路径Pl上最大的通行容量,由该路径上每条弧最大容量cij的最小值确定;
fl:表示通过路径Pl的实际人数;
x:表示全部待疏散人数;
xkl:表示通过路径Pl从k出口疏散的待疏散人数;
TPl:待疏散人员通过路径Pl疏散所需时间,
T:全部人员疏散结束所用时间。
1.3 模型建立
在上述符号和决策变量定义的基础上,以在最短的时间内将全体疏散人员安全疏散为目标,同时考虑火灾烟气扩散与路径容量的制约,建立解决该问题的数学模型如下:
其中式(1)为目标函数,表示疏散网络中全体人员全部疏散且用时最少。式(2)、(3)为疏散时间的递推方程式,表示疏散人员在弧lij的路径上以hij的速度通行所需的时间tij。式(4)弧上的通行速度受到烟气扩散影响随时间不断变慢。式(5)、(6)为各条疏散路径上的疏散人员在全部疏散时间内完成疏散,且保证整个疏散网络流量守恒。式(7)表示在路径上的全部通行时间包括人员在弧上的通行时间和在出口的疏散时间。式(8)表示疏散参数不可为负。
2 算法
2.1 算法思路
基于图论中的网络优化算法,针对所构建的数学模型中目标函数以及约束函数,设计在考虑烟气影响因素的情况下从一个受灾点向多出口疏散的启发式算法,用以解决此类非确定性多项式问题。该算法在执行过程中优先选择到达出口所用时间最短的路径,使其路径容量得到最充分的利用。但在寻找出口的问题中,由于考虑了多出口的情况,若将每个出口分别计算并加以比较,无疑会增加算法的计算量与复杂度,故引入超级终点进行简化。
将每个有容量限制的出口节点转变成一段具有同等容量限制、路径长度为零的弧进行处理,形成的每条弧再次汇集到一个新的虚拟出口节点,这一节点称之为超级终点。如图1所示,S1为受灾点,D1和D2为安全出口,V表示途中经过的点,括号中的数字分别表示每段弧的路径长度和最大路径容量,其中D1和D2出口单位时间内允许的最大通行流量分别为8和9。如图2所示,在引入超级终点D0后,将D1和D2与D0相连接,转换成新的疏散网络图。需要说明的是,超级终点的应用是建立在研究的疏散过程中沿途通过的节点不存在容量限制,拥堵仅发生在出口节点与每条弧之间。
算法的基本思想:在考虑烟气因素对疏散速度影响的条件下,运用Dijkstra算法寻找受灾点到超级终点的最优路径,记录下得到的路径以及所用时间和最大通行容量,更新疏散网络中的路径容量,不断在新的疏散网络中寻找从受灾点到超级终点的最短路径,直至找到全部疏散路径。
2.2 算法步骤
根据算法的基本思路,构造如下的算法:
步骤1:初始化,输入经转化的疏散网络G(V,E),令路径编号l=1,路径集合P=ф,疏散时间集合TP=ф,路径的流量集合F=ф。
步骤2:路径疏散时间的集合TPl= ф,标记点集合X0={S},其中n=1,T(vk)=+∞,λ(vk)=N。
步骤3:当D0∈X0,则表示找到当前的最优路径,记录下TPl为该路径下的疏散时间,转入步骤6,否则转入步骤4。
步骤4:对于[vm·vj]∈A且vj∈Xi的vj,令tn=tjTPl,由方程可解出tj;若tj≥T(vj)则转步ti骤5,否则令Tvj=tj,λ(vj)=m后转入步骤5。
步骤5:令T(vji)=min{Tvj},Pvji=Tvji,Xi+1=Xi∪{vji},n=i,i=i+1,hij=hnj·αij·e-β(ij)·[T(vji)-T(vjn)],转回步骤3。
步骤6:记录下该路径为Pl,令P=P∪(Pl),TP=TP∪{TPl},转入步骤7。
步骤7 :计算路径的最大通行容量PCl,PCl=min{cij|eij∈Pl},令fl=PCl,F=F∪{fl}。转入步骤8。
步骤8:更新每一条弧上的最大容量,,若cij=0,则说明该弧容量已经饱和,将该弧删除。转入步骤9。
步骤9:如果更新后的疏散网络内出现中断,则转入步骤10,否则令l=l+1,转到步骤2。
步骤10:输出路径集合P,疏散时间集TP以及路径流量集合F。
通过上述的算法步骤,可以求解出M条疏散路径,且满足TP1≤TP2≤TP3≤ …,≤TPM,但是所求解出的M条疏散路径在实际的应急疏散中未必会全部使用,而通常只会选择m(m≤M)条路径进行人群疏散,这就需要在选择路径的同时对疏散人员进行分组。原则上对于疏散用时较短的路径分配较多的人员,就如何对人数定量化的问题上,有人提出通过使每条疏散路径完成疏散所需要的时间相等,从而达到最优的疏散方案。由此可得有关待疏散总人数与完成疏散所需时间的关系函数:
通过有关文献可以得出,在此类涉及最小瓶颈疏散问题上,可通过不等式组(10)计算:
利用已知的数据在不等式中进行枚举,将疏散分组数求解出来,将式(9)变形后得到完成疏散所需时间:
3 应用实例
建立如下的疏散网络如图3 所示,通过上述建立的疏散模型对其进行计算,验证算法的可行性与有效性。在受灾点S处共有待疏散人员70人,两个出口D1和D2的单位时间最大允许通过量分别为10和8,从初始点开始的初始速度h0为15,各节点之间的路径长度lij、侵害系数αij和β(ij)、最大容量cij如表1所示。
将各项数据代入该算法内输出路径集合P、疏散时间集TP以及路径流量集合F,如表2所示。
将表2中的数据代入式(10)中枚举得到m=4,在可行路径中P1、P2、P3、P4为实际参与疏散的路径,再通过式(11),接触完成全部疏散所需要的时间T=29.5,对照路径P5、P6,路径上的疏散时间均大于疏散所需时间,证明其有效性。通过式(9)计算出每条路径的疏散人数xP1=41,xP2=24,xP3=4,xP4=1,与待疏散人数保持一致,证明其可行性。
在计算过程中发现实际路径数目m的值域为[2,l-1],当受灾点处待疏散人数发生改变过少或过多时,m的值也会发生改变,出现x<∑ml=1fl(TPm-TPl)或x>∑l=1m+1fl(TPm+1-TPl),则式(10)失效。针对这一问题,提出了相应的解决方法:当出现令m =2,人数x<∑ml=1fl(TPm-TPl)时,优先选择疏散时间较短、路径容量较大的路径,若实例中的待疏散人数为6,选择路径S-2-5-6-D1,完成疏散用时为17.7,符合T=TPl+x/fl最小,故为最优路径;当出现令m=l-1,人数x >∑l=1m+1fl(TPm+1-TPl)时,应首先计算式(10)成立的极限条件,即可以计算的最大待疏散人数,将解出的可计算的最大待疏散人数max(x)通过式(9)采用同样分配方法沿用路径P1、P2、…、Pm进行疏散,并求出该部分完成时间T',其中T'=TPM,证明如下:
已知:当m=M-1,有,根据式,则:
整体完成疏散时间还取决于剩余人数及对应的增加时间 ΔT,由于T'=TPM,则剩余人数 Δx如何分配给P1、P2、……、PM路径,决定了 ΔT的大与小。为了达到时间最短,各组人员应同时到达,即分配人数应与各路径的流量成正比。若实例中的待疏散人数为171,令m=4,令max(x)=∑l=1m+1fl(TPm+1-TPl)=160,T'=40.4,Δx=x-max(x)=11,将这11个待疏散人员以3、2、2、1、2、1的方式分配给路径P1、P2、……,PM,ΔT=1,则T=T'+ΔT=40.4+1=41.4,每条路径的疏散人数xP1=77,xP2=48,xP3=28,xP4=12,xP5=5,xP6=1为最优疏散路径。
在实例计算中,实际参与疏散路径P1、P2、P3、P4里有3条路径都包括了弧5-6和6-D1,其承载的人员流量为6,占疏散总流量的75%,对于此类弧段应定义为“重要弧”,在应急疏散中起到重要的作用,因此在日常的防火检查中,在类似该弧上的通道需要特别注意,防止杂物堵塞、照明设施故障等情况的发生;在应急疏散中,宜在类似该弧上的通道上增加专门的管理人员,起到引导与指挥的作用,防止发生意外事故造成滞留,从而影响整体疏散。
4 结论
研究了在火灾烟气和容量限制条件下多出口的疏散问题,建立了一个启发式算法与网络流控制结合的疏散模型,该模型以疏散网络中全体人员完成疏散时间最短作为目标,将待疏散人员以合理的方式分配到计算过的路线内。考虑到受路径容量的约束,将疏散用时最短的路径充分利用,并不断更新整个疏散网络,达到可以循环查找最优路径的效果,从而得出疏散网络的最优疏散路径组、疏散时间及路径上的疏散人数。
(1)通过实例计算,其结果验证了算法的可行性与有效性,同时通过对待疏散人数的改变,探究了当求解实际参与路径计算式不成立的情况下,如何确定最优疏散方案的方法。
多模型算法 篇8
随着信息技术的快速发展和现代军事及民用需求的不断提高,对目标跟踪的精度也相应地提出了更高的要求。在真实的目标跟踪系统中[1,2],目标的状态总是处在不断变化中,当目标真实运动模型与算法模型不匹配时,跟踪精度会明显下降,此时采用多模型(Multiple Model,MM)机动目标跟踪算法将会成为最佳选择。然而,当今的多模型目标跟踪方法[3]大都停留在理论层面,对于多模型的实际应用价值及各模型的应用场合都需要做进一步的研究。
本文选用当今最为流行、应用最广泛的雷达和红外作为传感器,在红外/雷达双模导引头[4]平台下开展对交互式多模型[5]机动目标跟踪算法的研究,并加入噪声干扰,更接近真实的军事与民用环境。首先搭建红外/雷达双模导引头仿真平台[6],进而设计基于多传感器[7,8]的多模型机动目标跟踪算法,采用扩展卡尔曼滤波[9],最终实现算法的软件仿真及跟踪性能评估[10],验证了所设计方法的有效性和实用性。
1 多传感器平台搭建
雷达和红外传感器是目前常用的两种目标探测和跟踪传感器,采用雷达为主、红外成像传感器探测为辅的信息融合系统进行目标跟踪能够使系统降低对敌方干扰的脆弱性,提高系统可靠性,现已广泛应用于各个领域。因此,本文选取雷达与红外双模导引头作为传感器,模拟生成多传感器的数据生成模块,为多模型机动目标跟踪算法提供良好的检测平台。
毫米波雷达导引头的观测数据包括观测系下的视线方位角、视线俯仰角、弹目距离、多普勒频率、雷达信噪比等信号。经过坐标转换,得到的参考系下的雷达观测数据,建立如下雷达观测方程:
式中:Z1(k)=[φR,θR,r]T,表示雷达导引头的观测向量;φR为雷达视线方位角,θR为雷达视线俯仰角,r为弹目距离。V1(k)是均值为零、协方差阵为R1(k)的白高斯噪声向量。
红外成像导引头的观测数据包括观测系下的视线方位角,视线俯仰角等信号。经坐标转换得到参考系下的红外观测数据,建立如下红外观测方程:
式中:Z2(k)=[φIR,θIR]T,表示红外导引头观测向量,φIR为红外视线方位角,θIR为红外视线俯仰角;V2(k)是均值为零、协方差阵为的白高斯噪声向量。
本文综合应用点迹合并方法和点迹串行处理方法,搭建毫米波雷达和红外数据融合的多传感器平台。假设雷达的扫描周期为5 ms,红外的扫描周期为10 ms,所以首先将雷达和红外点迹数据串行合并成为点迹数据流,进行点迹—航迹相关;对于在10 ms时刻,若雷达点迹和多个红外点迹均与航迹相关上,则对这些点迹进行点迹压缩合并,如图1所示。
2 多模型跟踪算法设计
本文选取目标跟踪中经常使用的几种目标运动模型组成模型集,然后根据模型间的配合规则设计多模型选取算法,如去掉不可能模型,合并相似模型,最可能模型选择算法以及基于期望最大算法的迭代策略等,进而对所得到的融合数据应用扩展卡尔曼滤波算法建立外推点迹,最终形成新航迹。设计框图如图2所示。
2.1 模型集的确定
大部分的跟踪算法都是基于模型的,因此目标运动模型设计是机动目标跟踪的基本要素之一,也是一个关键的问题。在建立机动目标模型时,一般的原则是所建立的模型既要符合实际机动模式,又要便于数据处理。本文选取目标跟踪中常用的几种运动模型组成模型集,包括CV模型、CA模型和当前统计模型。
2.2 配合规则
多模型算法按配合规则基本上可分为三代,静态多模型算法(SMM)、交互式多模型算法(IMM)、变结构多模型算法(FSMM)。以上三代多模型算法跟踪精度逐渐升高,同时算法的复杂度也依次升高、可实现性逐步变差。综合考虑算法的实用性和代价,IMM算法的交互方式更合理有效一些,是目前研究应用最多、被认为是最成功的一种算法。
因此,本文采用IMM算法作为模型之间的配合规则,完成多模型跟踪算法的设计。
2.3 滤波处理
本文选用扩展卡尔曼滤波方法对融合后的数据进行滤波处理。首先建立状态方程和观测方程,根据前一个估计值和最近一个观测数据来估计信号的当前值,并用状态方程和递推方法来进行估计,其解是以估计值形式给出的。由于滤波是采用递推算法,所以数据存储量少,运算量小,非常适合实时处理系统的应用。
3 跟踪效果仿真
选取扫描周期TIR=0.02s对目标进行跟踪模拟。目标初始位置为(1 000,1 000,1 000)m,初始运动速度为(300,300,300)m/s,初始加速度为(10,10,10)m/s2。
图3分别为x方向,y方向,z方向位置估计误差。
图4反映了位置估计误差的RMSE。
图5为目标运动轨迹和跟踪轨迹的三维仿真示意图。
仿真结果显示:在基于雷达/红外双模导引的多传感器仿真平台下,所设计的多模型机动目标跟踪算法跟踪精度相对较高,收敛较快,迟滞较小。
4 结语
本文主要研究基于多传感器的多模型机动目标跟踪算法,在更加接近真实环境的雷达红外双模导引模拟仿真平台下设计了多模型机动目标跟踪算法,并对其跟踪性能进行仿真验证,仿真结果证实了该算法的有效性和实用性。
摘要：多模型目标跟踪算法由于其独特的处理未知结构和可变参数的优点,已成为当前目标跟踪研究领域的一个重要方向。然而当今的多模型目标跟踪方法大都停留在理论层面,因此在实际应用层面上研究并设计多模型目标跟踪算法,并实现稳定、可靠而精确的目标跟踪意义重大。选用当今最为流行、应用最广泛的雷达和红外作为传感器,在红外/雷达双模导引头的多传感器平台下展开研究,设计并仿真实现了更接近真实的军事与民用环境的多模型机动目标跟踪算法。仿真结果验证了该算法跟踪性能的有效性。
关键词：目标跟踪,多模型算法,多传感器平台,数据融合
参考文献
[1]周宏任.机动目标跟踪[M].北京:国防工业出版社,1991.
[2]BAR SHALOM Y.Multitarget multisensor tracking[M].Bos ton:Artech House,1992.
[3]韩宏亮.基于IMM的雷达目标跟踪算法研究[D].南京:南京信息工程大学,2011.
[4]朱志宇.基于红外和雷达数据融合的机动目标跟踪方法[J].激光与红外,2007,37(2):170-174.
[5]BLOM H A P,BLOEM E A.Interacting multiple model jointprobabilistic data association avoiding track coalescence[C]//Proceedings of the 41st IEEE Conference on Decision and Control.Las Vegas,NV,USA:IEEE,2002:3408-3415.
[6]罗寰,于雷,陈中起,等.基于多模型交互的红外目标跟踪方法研究[J].激光与红外,2009,39(7):776-779.
[7]张红霞.基于多源传感器信息融合的目标跟踪算法研究[D].成都:电子科技大学,2011.
[8]潘丽娜.基于扩展卡尔曼滤波的多传感器目标跟踪[J].舰船电子工程,2010,30(12):71-73.
[9]苏峰,王国宏,何友.修正的逻辑航迹起始算法[J].现代防御技术,2004,32(5):66-68.
多模型算法 篇9
关键词：投资组合模型,非线性规划,多目标优化,进化算法
引言
投资组合就是如何配置各种有价证券的头寸来最好地符合投资者对风险和收益的权衡。Markowitz利用证劵收益的方差度量风险提出了M-V模型。该模型要求效用函数是二次的或者收益满足正态分布, 故在实际应用中受到较多限制, 若问题规模较大, 则需要解决一个带有稠密协方差矩阵的二次规划问题, 这给问题的求解带来高度的复杂性。
继Markowitz之后, 大量的模型及求解算法被提出[1]。2008年, Dellino等[2]基于遗传算法设计出一种动态目标聚集算法求解投资组合优化模型;Kawakami等[3]以信息率为目标函数建立了动态资产投资组合模型, 并利用遗传算法求解。
综上, 大量的投资组合优化模型及算法被提出。然而, 在实践中, 投资者频繁地进行交易, 交易费对收益的影响也是投资者不容忽视的问题。已有的求解方法主要是固定风险或效益使效益最大或风险最小, 需经过多次迭代才能获得不同要求下的最优投资组合。本文主要针对含交易费的投资组合模型, 从智能优化角度设计求解算法直接对模型求解。
一、投资组合模型
假设有n种资产可供投资, 现用数额为M的资金作一个时期的投资, 投资过程中存在一定的风险, 总体风险用投资项目中最大的一个风险度量。假设购买资产时要付一定的交易费, 当项目i投资额不超过给定值时, 交易费按投资额计算, 另外, 假定存入银行存款利率为定值。建立如下多目标投资组合模型 (POM) [4]。
为资产i交易费, x= (x1, x2, ……, xn) T∈Rn为投资权重向量, μi、pi、ri、qi分别表资产i的投资定额、交易率、平均收益率和风险损失率。
二、求解算法
K.Deb提出了NSGAII解决多目标优化问题, 该算法已广泛应用于求解各类多目标数值优化问题, 但其设计时只是针对无约束的多目标优化模型。在此, 基于NSGAII给予改进使其适合该模型的求解, 获得一种提高的多目标约束进化算法 (INSGAII) 用于模型POM的求解。
设最大迭代数为N, 当前代数为k, 算法步骤描述为:
Step1:随机产生初始可行个体群A (|A|=P) 及外部集S (S=Φ) , 置初始代数k=1;
Step2:若k≤N, 则输出结果, 算法结束;否则, 进入Step3;
Step3:群体A经由Pareto非控关系获Pareto个体集S, 若|S|≥S0, 则利用浓度抑制删去冗余的|S|-S0个个体;否则, 转入Step4。并获可行群B及非可行群C;
Step4:可行群B与非可行群C经交叉, 获群体D;
Step5:群体D经突变获群体E, 并对E中非可行个体修正, 获群体F;
Step6:置k←k+1, A←F, 转入Step2。
三、数值仿真
根据初始样本空间中投资项目数定义染色体 (个体) 的长度, 染色体上每一基因代表一个项目, 基因的数值表示投资比例, 一个个体x= (x1, x2, ……, xn) ∈Rn代表一种投资组合。采用数术交叉和多项式变异策略, 对不可行的个体进行修正使其可行[5]。
现设有5种投资项目供选择, 总投资金额M设为1, 各自的交易率、收益率等信息详见表1, 其中S1为无风险资产。
线性规划[4] (LP) 、GA和INSGAII应用于算例求解分析, 两种进化算法的最大迭代数N=200, 交叉概率为0.8, 变异概率为1/n, 群体规模P=100, GA利用权重系数法将模型转化为单目标求解。
由于交易费是分段函数, 已有的LP方法无法直接求解, 在此首先不考虑交易费为分段函数, 直接设为线性函数Ti= (xiM) pi获得如图1和表2比较结果。若交易费为分段函数, 获图2比较结果, 此时LP无法获得Pareto面, 故未画出。
图1中“-”为利用Matlab软件, 在风险固定的情况下算法LP所获风险-收益Pareto面, 虽然能得到较好的收益率, 但由于该方法通过固定风险使收益最大, 故需经过不同的固定风险才能获得不同的最大收益, 算法需经过多次运算。而GA在风险较小时能获得较好的收益, 当风险稍大时, 对收益率的收索较困难。INSGAII通过一次循环即可得出多组风险——收益Pareto面, 而且由图获知收索效果较好, 速度快捷。表2为各算法在获相同的风险——收益点对下所需的平均时间, 可见LP及GA所需的时间较长。特别, 在交易函数为分段函数时LP无法获风险-收益Pareto面 (图2) , 故未能描绘, 而与GA比较易知, GA获点较少, 且收敛性较差, 而INS-GAII获得pareto面较均匀, 效果较好。
四、结论及进一步研究
在交易费为线性函数时, INSGAII较其他两算法获较均匀的pareto面;在交易费为分段函数时, 算法LP便无法获得风险-收益点对, 而GA所获效果劣于INSGAII。对于INSGA在资产数量较大的情况的性能有待于进一步研究。
参考文献
[1]H.Konno, H.Yamazaki.Mean-absolute deviation portfolio optimization model and its application to Tokyo stock marcher[J].Management Science.1991, 37 (5) :519-531.
[2]G.Dellino, M.Fedele, C..Meloni.DOAM for Evolutionary Portfolio Optimization:a computational study[J].New economics pa-per, 2008:253-266.
[3]A.Kawakami, Y.Orito, M.Inoguchi.Dynamic Asset Portfolio Optimization by Using Genetic Algorithm[C].IEEE.Transactions onElectronics, Information and Systems, 2009, 129 (7) :1348-1355.
[4]赵静, 但琦.数学建模与数学实验[M].北京:高等教育出版社, 2008.
多模型算法 篇10
在科学技术及生产实践中, 许多问题的求解最终往往是转化成求解非线性方程或非线性方程组。非线性方程或非线性方程组的求解是数值计算领域中较困难的问题, 传统的解法如牛顿迭代法的收敛性和性能特征在很大程度上依赖于初始点的选择, 对于许多复杂的非线性方程组, 要选择一个较好的初始点是一件非常困难的事情。
微粒群优化算法[2、3] (Particle Swarm Optimization, PSO) 是由美国社会心理学家James Kennedy和电气工程师Russell Eberhart根据鸟群觅食行为模拟, 于1995年共同提出的一种新的演化计算技术。该新的优化算法具有许多特点如:实现容易、收敛性强、性能良好等。
多阶段多模型的微粒群优化算法[4] (MM-PSO) 是一种改进的微粒群优化算法, 将微粒群分多个阶段利用多种进化模型迭代进化, 该改进算法具有比标准微粒群优化算法更容易找到全局最优解的优点。
本文利用多阶段多模型的微粒群优化算法求解非线性方程组, 首先将求解非线性方程或非线性方程组的问题转化为函数的优化问题, 然后利用转化过来的优化函数当作PSO算法的适应度函数进行优化求解, 方程的求解不依赖于初始点和目标函数的导数信息。实验结果表明, 应用多阶段多模型的微粒群优化算法对转化过来的函数进行优化求解, 求解的结果是非线性方程或非线性方程组的有效解。
1 多阶段多模型的微粒群优化算法
微粒群优化算法基于群体与适应度的优化算法, 是通过对鸟群觅食行为的模拟得来。首先系统初始化微粒为一组随机解, 所有微粒有位置和速度两个特征, 微粒的适应度值是由其位置决定的, 通过迭代来改变其速度与位置求出问题的解。其数学表述为:由N个微粒组成的群体, 在D维的目标搜索空间中, 第i (i=1, 2, …, N) 个微粒在第t代的位置坐标可表成向量xit= (xi1, xi2, …, xid, …, xi D) T, 速度可表示为:vit= (vti1, vti2, …, vtid, …, vti D) T, 个体最优位置pBest可表示为:pit= (pti1, pti2, …, ptid, …, pti D) T, 种群的全局最优g Best可表示为:pgt= (ptg1, ptg2, …, ptgd, …, ptg D) T。
对于第i个微粒的第d维在第t+1代根据如下公式迭代更新:
其中, vtid—当前的速度,
—粒子i在第t次迭代后的新速度,
ω—惯性权重,
c1, c2—加速 (学习) 因子,
r1, r2—0到1之间均匀分布的随机数,
xtid—粒子i当前的位置,
—粒子i第t次迭代后的新位置。
加速因子c1, c2是调整微粒的自身经验与社会经验在其速度中所起作用的权重。如果c2=0, 则微粒没有群体共享信息, 只有自身经验, 微粒个体之间没有交互, 每个微粒仅受自己的飞行经验的影响, 不受其它微粒的影响。它的特点是:微粒在目标空间里大范围搜索, 不容易陷入局部最优点。此模型称之为Cognition Only模型[5], 其迭代公式为:
算法迭代的终止条件一般根据具体问题选为最大迭代次数或者微粒搜索到的最优位置满足预先设定的最小适应阈值。
在应用微粒群优化算法求解普通问题时比较简单, 容易求得满意的解。但是人们发现在实际应用过程中, PSO算法对于复杂优化问题求解时容易陷入局部极值[5]。针对微粒群优化算法求解复杂问题时易出现“早熟”收敛的现象, 文献【4】提出了一种多阶段多模型的改进微粒群优化算法。考虑到寻优过程中不同阶段的开发与探测能力需求的差异, 算法将寻优过程分成三个阶段, 不同阶段采用不同的模型。
第一阶段利用标准微粒群优化算法发现局部极值的邻域, 第二阶段利用Cognition Only模型快速找到局部极值点, 以提高寻优效率, 第三阶段, 利用新的模型跳出局部极值点, 以便寻找全局最优点。
其中第三阶段新的模型设计原理是为保证模型和标准PSO算法的结构形式一致并考虑微粒群算法的统计规律性, 定义一个减速因子 (与加速因子c1, c2对应) 和一个0到1之间均匀分布的随机数 (与r1, r2对应) 。
模型迭代公式为:
其中ω, c1, c2, r1, r2与式 (1) , (2) 定义相同,
c3—减速因子,
r3—0~1之间均匀分布的随机数。
2 求解非线性方程组的MM-P S O算法
2.1 非线性方程组的描述与转化
非线性方程或非线性方程组的求解问题是一个比较古老的数学问题, 其数学模型一般可表示为:
在式 (8) 中, 一般X被认为是在实数范围内待求解的n个未知量, 可转换表示为f (x) =[f1 (x) , f2 (x) , …, fm (x) ]T变量X的m维向量函数。将此方程写成分量的形式表示, 即:
因此, 原非线性方程或非线性方程组的求解问题, 可等价于求解函数:
应用多阶段多模型的微粒群优化算法对非线性方程或非线性方程组的求解, 可令转化过来的函数作为微粒群优化算法的适应度函数。
2.2 求解非线性方程及方程组的流程
步骤1 初始化设置微粒群微粒的个数、最大迭代次数、惯性权重, 加速因子、减速因子、标准PSO迭代阈值σ、模型迭代次数ε、各粒子初始位置和初始速度等。
步骤2 将要求解的非线性方程或非线性方程组转化成要优化的函数。
步骤3 评价各微粒的初始适应值、保存初始最好位置及初始最优适应值。
步骤4 根据式 (1) 计算各微粒新的速度, 根据式 (2) 计算各微粒新的位置、并对各微粒新的速度和位置进行限幅处理。
步骤5 更新各微粒的个体历史最好适应值和个体历史最好位置;更新全局历史最好适应值和全局历史最好位置。
步骤6 比较前后两次全局历史最好适应值的差, 如果该差值大于我们事先设定标准PSO迭代阈值σ, 返回步骤4, 否则进入步骤7。
步骤7 采用Cognition Only模型对粒子的速度和位置进行进化, 并更新各微粒的个体历史最好适应值和个体历史最好位置;更新全局历史最好适应值和全局历史最好位置, 按照设定的参数重复步骤7ε次后, 转入步骤8。
步骤8 采用式 (5) 与式 (6) 对粒子的速度和位置进行进化, 并更新各微粒的个体历史最好适应值和个体历史最好位置;更新全局历史最好适应值和全局历史最好位置, 按照设定的参数重复步骤8ε次后, 转入步骤9。
步骤9 若满足停止条件 (迭代次数超过最大允许迭代次数) , 搜索停止, 输出全局历史最好位置和全局历史最好适应值;否则, 返回步骤7继续搜索。
3 实验结果
将多阶段多模型的微粒群优化算法应用于非线性方程或非线性方程组的求解。多阶段多模型的微粒群优化算法的参数按文献【4】的设置为:ω取值从0.9线性衰变至0.4, 加速因子c1, c2为2, 减速因子c3为2, 最大迭代次数为2000, 微粒的数量为60, 第三阶段模型的迭代次数ε为25。最小适应度阈值设为|f (x) |<1.0×10-6。
多阶段多模型的微粒群优化算法是一种随机搜索算法, 为了验证算法的有效性, 对于每个算例都应用MM-PSO算法独立运行50次, 将这50次运行的最终结果统计如表1所示:
应用多阶段多模型的微粒群优化算法求解以上三个算例每次都收敛, 运算速度快, 算法编程实现简单, 并且每次都求得满意精度的解。
4 结束语
多阶段多模型的微粒群优化算法是一种改进的微粒群优化算法, 该改进算法具有更好的全局搜索寻优性能, 本文应用多阶段多模型的微粒群优化算法对非线性方程及非线性方程组进行了求解。
对于非线性方程或非线性方程组的求解, 传统数值方法一般都要应用到初始点信息和目标函数的导数信息, 而一个好的初始点的选择是一件困难的事情。本文将非线性方程及非线性方程组的求解问题转化为函数优化问题, 应用多阶段多模型的微粒群优化算法进行求解。该方法不需要初始点的信息和目标函数的导数信息, 不易陷入局部解。测试实验的结果表明:该方法有效、求解精度高、算法实现简单。
参考文献
[1]李庆扬, 莫孜中, 祁力群.非线性方程组的数值解法[M].北京:科学出版社, 1999.
[2]Kennedy J, Eberhart R.Particle Swarm Optimization[C].IEEEInt'1 Conf.on Neural Networks.Perth, Australia, IEEE ServiceCenter Piscataway NJ, 1995.1942~1948.
[3]Eberhart R, Kennedy J.A New Optimizer Using ParticleSwarm Theory[C].Proc.of the 6th International Symposiumon Micro Machine and Human Science, Nagoya, Japan:IEEEService Center Piscataway NJ, 1995.39~43.
[4]赵嘉, 孙辉.多阶段多模型的改进微粒群优化算法[J].计算机工程与应用, 2010,
[5]Eberhart R.Shi Y, Particle Swarm Optimization:Developments, applications and resources[C].Proceedings of theIEEE congress on Evolutionary Computation (CEC2001) , Seoul, Korea, 2001.81~84.
[6]孙志忠, 袁慰平, 闻震初.数值分析[M].南京:东南大学出版社, 2002.
[7]臧明磊, 杨士俊.用遗传算法解一元非线性方程[J].济宁师专学报, 1998, 19 (6) :
多模型算法 篇11
自20世纪70年代以后,很多学者在优化理论和应用方面做了大量的研究工作,但是针对钢铁行业冷轧生产多机组协调的综合计划编制与生产调度的研究成果并不多见。文献[3]提出了冷轧薄板企业的多级计划与调度体系结构,但未给出具体实现方法;文献[4]建立了以最小化合同总拖期为目标的混合整数规划模型;文献[5]提出了基于一种多弧网络的最大流模型,并考虑了合同优先级;文献[6]建立了具有模糊处理时间的冷轧生产线合同组批调度模型并采用单亲遗传算法求解,提高了交货期满意度; 文献[7]对某钢铁产品生产线建立了混合Flow Shop调度模型并采用基于派发规则的启发式方法求解。以上文献对生产成本的考虑均较少。文献[8]在某钢铁企业冷轧生产线针对四个机组的计划排产实现了多目标优化,但机组较少且未包括工艺较特殊的罩式炉退火机组。
本文以某冷轧薄板厂的生产实际为背景,研究了冷轧生产线中多机组的合同生产计划编制和调度问题。首先建立了冷轧多机组整体优化模型;接着通过引入生产切换的虚拟成本并设计时间窗推理算法将各机组计划调度转化为CNRMTSP(受约束无返回多旅行商问题)和TSPTW(带时间窗的旅行商问题),采用改进蚁群算法分别求解;最后利用现场实际数据对模型和算法的有效性进行了验证,结果表明本文模型及其求解方法能够应用于实际生产,以解决冷轧多机组的合同优化排产问题。
1 问题描述
冷轧薄板生产具有多装置、多过程、多工序、并行生产等特征,属于流程工业中半连续生产方式。对于单个机组属于连续生产,对于机组和机组之间属于半连续式生产。某冷轧薄板厂的生产工艺路线如图1所示。
从图1中可以看出,冷轧生产有如下特点:
(1)由于生产产品的种类各异,其生产路线各不相同。该厂几种代表性产品加工工序如下:
冷轧卷 酸洗-冷轧-脱脂-罩式炉退火-二次冷轧与平整-纵切;
1#镀锡卷 酸洗-冷轧-脱脂-罩式炉退火-二次冷轧与平整-1#镀锡;
2#镀锡卷 酸洗-冷轧-连退-2#镀锡;
镀铬卷 酸洗-冷轧-连退-镀铬。
(2)前驱工序约束。即必须保证前道工序结束,后道工序才可进行,如冷轧机组加工的产品必须经过酸洗机组。
(3)生产过程中不仅有多机串行,也有多机并行。上游机组的物料分配均衡与否将直接影响上下游机组的正常生产。因此多机组计划编制工作之一就是通过制定合理的生产计划来平衡上下游机组的物料,以保证整个生产线的正常生产。
任一钢卷都有一系列的属性,包括下放期、交
货期、合同优先级、产品等级、宽度、厚度、硬度、重量、粗糙度、退火温度等。各机组作业调度时一般将属性相似的钢卷组批,同一批次的钢卷首尾相连焊接在一起连续生产(罩退机组除外)。组批时要求相邻钢卷某些属性尽量平滑变化,并对变化的范围做出了规定,以保证产品质量和减少机械磨损。例如,一般要求钢卷宽度由宽到窄,避免钢卷表面印痕;宽度、厚度、硬度不能同时变化等。同时,批次的长度也有相应的限定。不同类型组批的钢卷连续生产时,中间需要一定调整时间。由于各机组对钢卷各项属性的工艺约束有不同侧重,所以在一个机组组成一批的钢卷在后续机组未必能够组成同一个批次生产。
冷轧多机组的计划编制问题可描述如下:已知冷轧生产线产品生产流程、各机组工艺约束、前库等待排产钢卷、当前生产状态、计划停机时间,要求给出在计划时间跨度范围内各机组生产计划安排、钢卷具体加工次序和具体加工时间,在符合工艺规则的前提下保证生产线上下游产能平衡、满足合同交货期要求的同时,尽量减少生产成本。
2 冷轧多机组计划排产模型
冷轧多机组计划编制涉及两个相关问题:垂直问题和水平问题[8]。垂直问题解决的是上下游生产机组之间的平衡问题以及交货期预测,所关心的是资源的粗分配。首先,为了减小问题规模,将属性相近、在各机组均能作为一个整体连续生产的钢卷合并为簇,下文中钢卷均代表钢卷簇。然后,为了方便解决问题,对合同钢卷进行初始分类,根据宽度、厚度、机组产能和工艺要求,将具有同一交货期和产品类型的合同钢卷,划分成若干种粗计划合同组类型。水平问题即作业调度问题,指的是对每个机组安排具体的钢卷生产顺序,实现作业的具体安排和资源的细分配。机组共线生产不同类型的产品,原料钢卷的切换过程中出现的机械磨损和时间损耗,本文定义为虚拟成本。利用不同类型钢卷之间的差异作为惩罚值,表示钢卷切换过程的虚拟成本。生产调度的目标是使每个机组生产不同合同钢卷时,切换成本最小,即总惩罚值最小。
根据上述对冷轧多机组生产流程及其计划编制问题的分析,考虑该冷轧薄板厂每个机组都只有一条生产线(罩退机组除外)的情况,抽象出冷轧多机组的计划排产模型如下:
undefined
式中,a,b为转化成本系数,将合同延期成本、粗计划合同转换虚拟成本转化为同类型的成本;P为冷轧生产线的所有机组集合(酸洗、冷轧、脱脂、连退、罩退、二次冷轧和平整、镀铬、1#镀锡、2#镀锡、纵切),以p为索引;Cp为在机组p生产的钢卷集合,以i为索引;ri为钢卷i的合同优先级系数;ξi为钢卷i的开始加工时间;ti为钢卷i的加工时间;用时间窗TESTi, TLFTi表示待排产合同钢卷i的合理加工时间范围,其中TESTi为钢卷i的最早开始加工时间,TLFTi为钢卷i的最晚加工完成时间;Kp为在机组p生产的粗计划合同集合,以k为索引,粗计划合同k的时间窗为TESTk, TLFTk;puv为粗计划之间切换的惩罚系数;ui为钢卷i所对应的上游机组钢卷;t(ui,i) 为钢卷i从其上游机组到本机组的传递时间;Пk(i)为粗计划合同k中的钢卷排序;ξk为粗计划合同k的开始生产时间;tk为粗计划合同k的生产时间;t(k1,k2) 为在两个粗计划合同k1和k2之间的切换时间;Ck为粗计划合同k中的钢卷集合;TPDSj为第j次停机开始时间,TPDEj为第j次停机结束时间;Jp为机组p的计划停机时间集合,以j为索引;lk和sk分别为一个粗计划合同k的类型和长度。
式(1)为模型总体优化目标函数,即合同钢卷延期惩罚和生产调度虚拟成本的加权和;式(2)为钢卷生产时间受下放时间的限制;式(3)为钢卷上下游机组之间的垂直生产约束关系;式(4)为粗计划合同内钢卷的连续生产关系;式(5)为相邻粗计划合同之间的开始生产时间关系;式(6)为粗计划合同加工时间与其中钢卷加工时间的约束关系;式(7)为粗计划合同调度受计划停机的限制条件;式(8)为粗计划合同的大小受计划类型的限制条件;式(9)和式(10)表示粗计划合同的时间窗与其中钢卷时间窗的约束关系。同时,还有各机组其他的具体工艺约束没有一一列出。需要注意的是罩退机组合同钢卷组批生产方式与其他机组有较大不同,诸如式(4)、式(6)等约束条件将不适用。本文采用罩退机组原有的计划排产软件进行生产调度[9],只是附加了时间窗约束,并在其优化目标函数上增加了合同超期惩罚项。
3 冷轧多机组计划排产模型求解框架
鉴于冷轧多机组计划编制问题的复杂性,直接求解有很大困难,本文求解框架将其分解为三步:第一,通过推理算法将机组间前驱约束转化为时间窗约束,解除垂直方向和水平方向的耦合,便于单机组生产调度;第二,对各单机组将合同钢卷分类组批为粗计划合同,减小问题规模,同类钢卷先行调度;第三,对各单机组粗计划合同最后进行作业调度。
3.1 基于时间窗的推理算法
在实际生产过程中,如果产品的加工完成时间过早,则企业需长时间使用仓库而增加生产成本;如果产品的加工完成时间过晚,可能造成下游机组供料不足而停产,或者超过了合同的交货期需对客户做出相应赔偿。因此要求兼顾以上因素,在保证上下游机组产能平衡和合同交货期的前提下,尽量缩短产品在库时间。本文首先以合同钢卷下放期和交货期为基础对其建立初始时间窗;然后在初始时间窗的基础上建立传递时间窗;
最后按照生产流程结合各机组的作业调度对时间窗逐级递推修正。
由于冷轧生产机组众多,本文选择酸洗-冷轧-连退-镀铬产品生产流程为例,说明模型中引入的时间窗及递推过程,具体步骤如下。
步骤1 在需要计划编制时间段内搜索出所有合同钢卷,由本文给出经验公式(11)用于计算钢卷在各机组的加工时间(罩退机组的钢卷加工时间采用机组产能平均效率公式进行计算[6]):
undefined
式中,tip为合同钢卷i在机组p的加工时间;mi为合同钢卷i的质量;wi为合同钢卷i的宽度;di为合同钢卷i的厚度;ρi为合同钢卷i的密度;sp为机组p的轧辊运行速度;cip为合同钢卷i在机组p的补偿因子;σip为合同钢卷i在机组p的加工时间系数。
步骤2 以合同钢卷下放期、交货期为基准,根据钢卷加工时间及其在机组间的传递时间建立初始时间窗,如图2所示。图中下标AP,CM,CA,EG分别为酸洗、冷轧、连退和镀铬机组;TP-AP为钢卷在酸洗机组的加工时间;Tundefined为钢卷从酸洗机组至冷轧机组的传递时间;Tundefined和Tundefined分别为酸洗机组初始时间窗的最早开始加工时间和最晚加工完成时间。其他依此类推。需要注意的是不同钢卷在相同的机组间传递时间是不同的。这是因为实际生产各机组相对独立,并且存在一定的物理位置差距。钢卷的实时传递除了在某些综合
集成机组(例如平整和二次冷轧综合机组)内可以基本实现外,上游机组生产完成的钢卷都是分批次传送到其下游机组继续加工。钢卷实际传递时间只有调度方案给出之后才能确定,所以此处取现场批量钢卷传递时间的平均值。
步骤3 从图2可以看出,初始时间窗跨度很大,并且相互重叠。一方面它对作业调度寻优的指导作用有限,另一方面应用在机组生产调度时不能保证钢卷垂直方向的前驱约束关系。针对这
些问题,在初始时间窗的基础上建立互不重叠的传递时间窗,如图3所示。图中Tundefined和Tundefined分别为连退机组传递时间窗的最早开始加工时间和最晚加工完成时间,其他依此类推。各机组传递时间窗跨度的确定是由总传递时间减去各机组之间的传递时间,然后依照此生产流程各机组的产能按比例分配,产能越低的机组时间窗的跨度越大。对于每个机组,利用传递时间窗可以独立制定水平计划且不用考虑上下游机组垂直方向的前驱约束问题。
步骤4 传递时间窗仍然是比较“粗糙”的作业调度指导,需要进一步精细化。冷轧多机组生产对钢卷数量与完成时间的要求是由下游机组的运行情况决定的。例如,如果镀铬机组由于某些原因产能降低,那么其上游机组连退、冷轧机组等必须做出相应的调整以达到上下游产能平衡的目的。所以,从镀铬机组开始向上逐级进行计划编制,以逆推的方式精细化时间窗,向上游机组反馈下游机组的生产需求。首先应用下文3.2和3.3中算法对镀铬机组粗计划合同组在其时间窗下进行作业调度,然后根据调度结果修正上游连退机组对应钢卷传递时间窗的最晚加工完成时间,如图4所示。图中TS-CM和TF-CM分别为钢卷在冷轧机组的实际开始加工时间和加工完成时间;Tundefined为冷轧机组钢卷传递时间窗修正后的最晚加工完成时间。其他依此类推。将修正后的传递时间窗应用于连退机组的作业调度,同理上推至冷轧机组和酸洗机组。
步骤5 从酸洗机组开始向下进行计划编制,类似步骤4。通过各机组水平方向调度结果逐级修正下游机组传递时间窗的最早开始加工时间,如图5所示。图中Tundefined为冷轧机组钢卷传递时间窗修正后的最早开始加工时间。其他依此类推。在修正后的传递时间窗Tundefined,Tundefined下进行各机组水平方向的作业调度。
步骤6 重复步骤4和5,不断精细化时间窗并优化各机组生产调度,直至获得满意结果或达到迭代次数,则此分支生产流程的计划排产完成。冷轧多机组其他生产流程的计划编制同理。
摘要：为解决钢铁冷轧多机组的排产问题,建立了一个实现合同生产计划和作业调度的整体优化模型。模型以最小化各机组合同延期惩罚和生产类型切换虚拟成本为优化目标。首先,针对上下游机组的物流平衡及保证交货期问题,根据合同钢卷在生产流程各机组间的传递构造基于时间窗的推理算法,确定钢卷的合理加工范围。在传递时间窗下各机组生产调度可以不必考虑机组的前驱约束。然后,根据合同交货期、产品种类以及工艺约束等将合同钢卷在各机组划分为不同的粗计划类型。同一类型粗计划合同钢卷的批次作业调度可以归结为多约束无返回多旅行商问题,通过一种启发式分组蚁群算法优化求解。最后,将机组的粗计划合同调度抽象为带时间窗旅行商问题,采用一种改进的自适应蚁群算法求解。通过现场实际数据试运行,结果表明所建模型与算法是有效可行的,为冷轧企业多机组的合同计划和调度提供了合理指导。
关键词：冷轧,生产调度,时间窗推理,旅行商问题,蚁群算法
参考文献
[1]李耀华,张大波,宁树实,等.单亲遗传算法求解冷轧厂合同优化组合问题[C]//第五届全球智能控制与自动化大会论文集.杭州:浙江大学,2004.
[2]王文鹏,杨再步,李铁克.冷轧生产线的批量计划与调度方法[J].冶金自动化,2006,30(5):11-15.WANG Wen-peng,YANG Zai-bu,LI Tie-ke.Batch plan-ning and scheduling method for cold rolling production line[J].Metallurgical Industry Automation,2006,30(5):11-15.
[3]史海波,马玉林,刘爱国.冶金冷轧薄板企业生产计划调度体系结构及方法研究[J].信息与控制,2004,33(1):31-35.SHI Hai-bo,MA Yu-lin,LIU Ai-guo.Research on thestructure and method of production planning and schedu-ling for cold-rolled sheets plant[J].Information and Con-trol,2004,33(1):31-35.
[4]Redwine C N,Wismer D A.A mixed integer programmingmodel for scheduling orders in a steel mill[J].Journal ofOptimization Theory and Applications,1974,14(3):305-318.
[5]Sasidhar B.Multiple arc network model of production plan-ning in a steel mill[J].International Journal of ProductionEconomics,1991,22(3):195-202.
[6]赵珺,王伟,刘全利.冷轧薄板生产线组批调度模型与算法[J].计算机集成制造系统,2008,14(10):1 957-1 965.ZHAO Jun,WANG Wei,LIU Quan-li.Model and algo-rithm of grouping batch scheduling for cold rolling sheetproduction line[J].Computer Integrated ManufacturingSystems,2008,14(10):1 957-1 965.
[7]Voss S,Witt A.Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching re-quirements:a real-world application[J].InternationalJournal of Production Economics,2007,105(2):445-458.
[8]Okano H,Davenport A J,Trumbo M,et al.Finishing linescheduling in the steel industry[J].IBM Journal of Re-search and Development,2004,48(5-6):811-830.