多策略算法（共8篇）
多策略算法 篇1
1 引言
多目标进化算法 (Multi-objective Evolutionary Algorithm, MOEA) 是智能计算领域的研究热点之一[1]。由于智能计算具有本质并行性、 毋须求导、 一次运行产生多个解等优点, 因此它是求解多目标优化问题 (MOP) 的有效方法[2]。目前, 比较有代表性的算法有SPEA[10]、SPEA2、NSGA[1]、NSGA2[9]、PAES[7]、MOPSO[8]等。MOP表示为
其中, 决策向量
在多目标优化问题中, 各个目标之间可能是相互冲突的, 不存在唯一解使所有目标函数同时最优, 可能存在这样一组某种折衷或妥协的非劣解集, 求解MOP就是获得该非劣解集。
多目标优化问题常用的基本概念如下:
①Pareto支配:向量
②Pareto最优解:可行域中一点
③Pareto最优解集:多目标优化问题
④Pareto front:给定多目标优化问题
自由搜索算法 (Free Search Algorithm, FS) [3]是一种性能优良的新的智能计算方法[4,5,6,7]。本文将其拓展到多目标优化领域, 并且在构建新算法时引入变异算子, 提出基于混合策略的多目标自由搜索算法 (Hybird Based Multi-objective Free Search Algorithm, HMOFS) 。最后, 通过数值实验验证了新算法的有效性。
2 基于混合策略的多目标自由搜索算法
2.1 算法描述
基于混合策略的多目标自由搜索算法的具体实现步骤如下:
Step1:参数设定
1.1 设置种群规模POP, 最大迭代次数G, 搜索步数T, 外部档案Archive大小, 最大最小搜索半径Rmin, Rmax等参数
Step2:外部存档控制
2.1 在决策空间随机产生初始种群POP[j];
2.2 计算初始种群的目标向量, 进行非劣比较;
2.3 调用外部存档控制子程序。
Step3:寻优过程
3.1 每个个体在其搜索半径通过寻优方程行走T步;
3.2 释放信息素, 计算灵敏度;
3.3 比较信息素和计算灵敏度, 得到搜索结果;
3.4 调用变异算子, 获得本次结果。
Step4:外部存档控制
4.1 计算种群的目标向量, 进行非劣比较;
4.2 调用外部存档控制子程序。
Step5:终止判断
若迭代次数不大于G, 则g=g+1, 调转至Step3, 否则转至Step6。
Step6:停止迭代, 将Archive内容输出。
2.2 选择机制
(1) 适应值分配
自由搜索算法的寻优方程如式 (2) 所示:
式中, randomtji (0, 1) 是 (0, 1) 内均匀分布的随机数;ximax和ximin是第i维变量的最大值和最小值;j代表第j只个体 (j=1, 2, …, m) ;Rj是第j只个体在搜索空间邻域搜索半径 (Rj∈[Rmin, Rmax]) ;t是搜索步 (walk) 中的当前小步 (t=1, 2, …, T) ;T是搜索步数。
在HMOFS中, 采用基于Pareto支配关系的适应值分配方法。对于要选择移动方向的个体j在搜索半径Rji内, 比较其各搜索步解的Pareto支配关系, 设个体在搜索半径Rji内的分布如图1所示, 其适应值分配见式 (3) 。
(2) 基于信息素的选择机制
在HMOFS算法中, 信息素按照多目标适应值分配机制进行定义:
式中, fitt=max (ftj) , ftj=f (xtji) , 而max (fitj) 是所有个体的当前最佳值。
而HMOFS算法中的灵敏度定义和单目标FS算法类似:
式中, Smin、Smax是灵敏度的最小值和最大值, randomj (0, 1) 是均匀分布的随机数。
信息素的最小值和最大值分别为Pmin、Pmax。规定:Smin=Pmin, Smax=Pmax. 在一轮搜索结束后, 确定下一轮搜索的起始点。
2.3 变异算子
采用多项式变异算子, 如式 (7) 所示:
式中, puj, plj分别是决策空间第j维的上下边界, δj如式 (8) 计算。
式中, μ为rand (0, 1) 的随机数, η为变异分布系数。
2.4 自适应策略
采用实时调整搜索半径的策略, 寻优过程中搜索半径R为搜索代数g的函数。R (g) 的调整策略见式 (9) :
2.5 外部存档机制
外部存档控制采用基于自适应网格的多样性保持策略[8], 其伪代码如下:
3 数值实验
为了测试HMOFS算法的有效性, 采用表1所列5个测试函数, 并将实验结果和MOPSO[9]、NSGA-II[10]、SPEA[11]、PAES[6]进行比较。对于每个测试函数, HMOFS算法独立运行10次, 其参数设置为:T=10, R (0) =1, η=20, pm=1/n, G=250。算法MOPSO、NSGA-II、SPEA、PAES的其它参数设置见文献[10]。
3.1 性能指标
采用文献[9]提出的两个指标来评价算法的性能。
(1) 收敛性指标γ
算法所得解与true Pareto-optimal front之间的最小Euclidean距离的平均值, 即为
具体计算时, 在问题的true Pareto-optimal front上均匀地取一组点H′, 如取H′=500, h′为H′上分布均匀的一组解。H是算法所得的非劣最优目标域, 然后计算由算法获得的解h∈H与这些点h′之间距离的最小值, 所有这些最小值的平均值就是收敛性指标γ.
(2) 多样性指标Δ
式中, di是近似Pareto front相邻两点间的Euclidean距离,
3.2 实验结果与讨论
表2、表3给出了本文算法和其它4钟算法收敛性指标和多样性指标的均值和方差 (每种算法的第一行为均值, 第二行为方差) 。从表2可见, HMOFS算法收敛性指标γ的均值优于MOPSO、 NSGA-II、 SPEA、 PAES。但其方差并非最优, 对于ZDT1、ZDT2和ZDT3, HMOFS列第二, MOPSO列第一; 对于ZDT4, HMOFS列第一; 对于ZDT6, SPEA列第一, HMOFS列第二。从表3可见, HMOFS算法多样性指标Δ的均值优于MOPSO、NSGA-II、SPEA、PAES, 而对于Δ指标的方差, HMOFS与其它算法性能相当。总体而言, HMOFS是一种性能优良的多目标进化算法, 这也可以从该算法获得的近似Pareto front得到直观反映, 见图2～图6。
4 结论
本文提出了基于混合策略的多目标自由搜索算法 (HMOFS) 。将HMOFS应用于5个测试函数, 并与算法MOPSO、NSGA-II、SPEA、PAES进行了对比分析。结果表明, HMOFS算法具有很好的收敛性和多样性, 是解决多目标优化问题的有效方法。
参考文献
[1]Kukkonen S, Deb K.Improved pruning of non-dominated solutions based on crowding distance forbi-objective optimization problems[C]//EvolutionaryComputation, 2006.CEC 2006.IEEE Congress on, 2006:1179~1186.
[2]Chen M R, Lu Y Z.A novel elitist multiobjectiveoptimization algorithm:Multiobjecti extremaloptimization[J].European journal of OperationalResearch, 2008, 188:637~651.
[3]Penev K, Littlefair G.Free search-A comparativeanalysis[J].Information Sciences, 2005, 172:173~193.
[4]周晖, 李丹美, 邵世煌.一种新的群集智能算法——自由搜索[J].东华大学学报 (自然科学版) , 2007:579~583.
[5]周晖, 李丹美, 邵世煌.自适应搜索优化算法[J].计算机科学, 2008, 35 (10) :188~191.
[6]周晖, 邵世煌.基于粗细粒交叉的搜索算法[J].控制与决策, 2008, 23 (9) :1068~1072.
[7]王则林, 罗永平, 陆建德.基于最近邻居选择、信息素动态更新和局部启发搜索的蚁群算法[J].南通大学学报 (自然科学版) , 2006, 5 (12) :71~76.
[8]Knowles J D, Corne D.Approximating the non-dominated front using the pareto archived evolutionstrategy[J].Evolutionary Computation, 2000, 8 (2) :149~172.
[9]Coello C A C, Pulido G T, Lechuga M S.Handlingmultiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computa-tion, 2004, 8 (3) :256~279.
[10]Deb K, et al.A fast and elitist multiobjectivegenetic algorithm:NSGA-II[J].IEEE Transac-tions on Evolutionary Computation, 2002, 6:182~197.
[11]Zitzler E, Thiele L.Multiobjective evolutionaryalgorithms a comparative case study and thestrength pareto approach[J].IEEE Transactionson Evolutionary Computation, 1999, 3:257~271.
多策略算法 篇2
关键词：约束多目标进化算法；种群聚类；聚集密度；分布性
中图分类号：TP3016文献标志码：A文章编号：1672-1098（2016）01-0050-06
Abstract：The constrained multi-objective evolutionary algorithm based on group clustering was improved， and crowding-density was introduced to measure the relationship among individuals and maintain the diversity of population. The basic idea is that the initial population is divided into four groups with different fitness by multi-criterion clustering method， and the crowding-density of each group is calculated. A poset is defined according to the objective function value and crowding-density， and the individuals are selected from poset by the principle of proportion selection， then the elite set is updated. The convergence and distribution of improved algorithm were studied by means of numerical experiments， and the results showed that the convergence of improved algorithm is roughly equal to the conventional multi-objective evolutionary algorithm， but the distribution of improved algorithm is significantly improved.
Key words：constrained multi-objective evolutionary algorithm； group clustering； crowding density； distribution
约束多目标优化问题的关键是对约束条件的处理，目前已有一些典型的带约束多目标进化算法和约束处理机制：文献[1]提出的COMOGA算法，将向量评估遗传算法和Pareto排序分级的方法结合起来处理约束问题。文献[2]提出的约束VEGA，将群体划分成几个子群体来处理。文献[3]提出的约束MOGA，将基于Pareto优胜的选择方案用来处理遗传算法中的约束方程。文献[4]提出了一种基于群体分类的复杂约束多目标进化算法，根据聚类方法来处理复杂约束，算法的基本思想是：按照类内距离平方和最小，类间距离平方和最大等多种判据将种群聚类处理，再按类赋以适当的适应度值。这种算法对于处理Pareto边界比较光滑的三目标的优化问题效果较好，收敛速度较快，基本上二百代即已达到较好的优化效果，但在维持种群的多样性和分布性方面欠佳，现将此算法做了改进，在进化过程中引入聚集密度以调控种群，可以达到维持种群多样性的目的，并根据量化评价指标和数值实验结果对改进算法的性能特别是分布性进行了评测。
1多目标优化问题的相关概念
11多目标优化问题及其最优解
多目标优化问题可表述为[5]
min y=f（x）=（f1（x），f2（x），…，fk（x））
s.t e（x）=（e1（x），e2（x），…，em（x））≤0
x=（x1，x2，…，xn）T∈X
y=（y1，y2，…，yn）∈Y
（1）
式中：x为决策向量，f（x）为目标向量，X表示决策向量x形成的决策空间，Y表示目标向量y形成的目标空间，约束条件e（x）≤0确定决策向量的可行取值范围。
定义1[6]满足式（1）中的约束条件e（x）的决策向量x的集合，即
Xf={x∈X|e（x）≤0} （2）
称为可行解集。
定义2[7]设xA，xB是两个可行解，若f（xA）≤f（xB）， 则称xA比xB优越； 若f（xA） 定义3若可行解x*满足：比x*更优越的可行解不存在，则称x*为弱Pareto最优解； 比x*优越的可行解不存在，则称x*为强Pareto最优解。 定义4Pareto最优解的集合称为Pareto最优解集或非支配解集，记为P*。 定义5Pareto最优解集P*中的所有Pareto最优解集对应的目标向量组成的曲面称为Pareto最优前沿或Pareto最优前端，记为 两目标优化问题的Pareto最优前沿是一条平面曲线，三目标优化问题的Pareto最优前沿则为一张空间曲面。多目标优化问题的结果习惯上多采用Pareto最优前沿表示。
12最优解集的评价标准
多目标优化算法性能的评价包括算法的效率和最优解集的质量。算法的效率主要指算法的复杂性即算法占用的CPU时间，而最优解集的质量包括算法的收敛性和最优解集的分布性。
评价多目标优化算法性能主要依靠量化评价标准和有代表性的测试问题。
常用的量化评价指标有：
1） 世代距离[8]（GD）
GD=∑ni=1d2i n （4）
式中：n为算法所得最优前端PFknown中向量个数，di为PFknown中每一维向量到最优前端PFtrue中最近向量的距离。
GD主要反映了PFknown对PFtrue的逼近程度。
2） 错误率[9]（ER）
ER=∑ni=1ein （5）
式中：n为PFknown中的向量个数，且PFknown={X1，X2，…，Xn，ei定义如下
ei=0， Xi∈PFtrue
1， 其它（6）
ER描述了PFknown对PFtrue的覆盖程度，即最优解集的分布性。
3） 分散性（SP） [10]
SP=1n-1∑ni=1（di-）2 （7）
式中：n和di同GD。
显然，SP即为di的均方差。根据方差的含义，SP反映的是最优解集的均匀性。
2基于聚集密度的约束多目标算法
上述群体分类的复杂约束多目标进化算法具有较好的收敛性，但在分布性方面存在着的一定的缺陷，原因是算法仅考虑了群体中个体的R适应度，并没有考虑群体中个体间的距离，即群体的拥挤程度，这极有可能降低种群的多样性，影响解的分布性。
在进化算法中，保持解的分布性的常用方法有：小生境技术，信息熵，聚集密度，聚类分析等[11]。
本文将聚集密度引入选择过程，改善解的多样性和分布性。
21聚集密度
聚集密度的概念是Deb在[12]中提出来的。聚集密度可以从个体的相似度，影响因子或者聚集距离几个方面来度量，本文选择从聚集距离角度度量。聚集密度与聚集距离成反比关系，聚集距离大的聚集密度小。一个个体的聚集距离可以通过计算其与相邻的两个个体在每个子目标上的距离差之和来求取。
如图1所示，设有两个子目标f1（x）和f2（x），Pm[i]为个体i在子目标m上的函数值，则个体i的聚集距离P[i]d是图中四边形的长与宽之和，即
计算出聚集距离后，再按照个体间的聚集距离越大，则个体的聚集密度就越小的原则，即可定义个体的聚集密度。这里，为了简单起见，定义聚集密度为聚集距离的倒数。
22基于聚集密度的约束多目标进化算法
基于聚集密度的约束多目标进化算法的步骤如下
1） 用多判据聚类方法将整个群体分成四类，不可行群体、可行非Pareto群体、聚类Pareto群体以及聚类Pareto最优群体。分别赋以适应度：R（不可行群体）≤R（可行非Pareto群体） ≤R（聚类Pareto群体）≤R（聚类Pareto最优群体）。
2） 当迭代次数小于最大迭代次数时，构造如下偏序集：① 计算种群中个体的目标函数值；② 计算每个个体的聚集密度；③ 根据目标函数值和聚集密度定义一个偏序集，该偏序集中的元素有两个属性：个体的目标函数值和聚集距离。
3） 根据比例选择原则，依次从偏序集中选择个体。
4） 对群体进行交叉运算。
5） 对群体进行均匀变异运算。
6） 条件终止判断。不满足终止条件，则进行新一轮运算，若满足终止条件，则输出计算结果，算法结束。
算法流程图如下
下面用基于聚集密度的约束多目标进化算法对两个标准约束多目标测试函数Binh4和Viennet 4进行了优化，并将计算结果与文献[12]中的原算法的计算结果进行了比较，从而检验改进算法的性能。
1） Binh4测试函数
F=（f1（x，y），f2（x，y），f3（x，y））
f1（x，y）=15-x（1-y）
f2（x，y）=225-x（1-y2）
f3（x，y）=2625-x（1-y2） （10）
约束条件为
-10≤x，y≤10
x2+（y-05）2≥9
（x-1）2+（y-05）2≤625 （11）
Binh4测试函数的PFlocal如图3所示。
2） Viennet4测试函数
Viennet4测试函数的PFlocal如图4所示。图4Viennet4 PFtrue 图图5Binh4 PFknown 图（改进算法）图6Binh4 PFknown 图（原算法）图7Viennet4 PFknown 图（改进算法）图8Viennet4 PFknown 图（原算法）
图5～图8分别是用改进算法和原算法求出的Binh4和Viennet4的Pareto最优边界。可以很直观地看出，改进算法在解的分布性和均匀性方面均明显优于原算法。
为了更进一步定量地评价改进算法的性能，下面给出改进算法和原算法的世代距离、错误率和分散性指标的对比数据。
考虑到计算结果的随机性，表中给出的是20次实验结果的平均值。
从表1和表2中可以很清楚地看出，原算法和改进算法的GD指标相差不大，但改进算法的ER和SP指标与原算法相比明显占优。
综合图5～图8和表1～表2，可以得出明确的结论：基于聚集密度的改进约束多目标进化算法的收敛性与原算法相当，但分布性和均匀性有了明显的提高。
4结束语
本文根据聚集密度的特点，将聚集密度引入群体聚类约束多目标进化算法，数值实验结果和量化指标表明：与原算法相比，改进算法解的分布性有了明显的提高。
由于多目标进化算法的理论基础目前还很薄弱，收敛性和分布性等关键理论问题无法从理论层次进行证明，所以算法的改进验证只能基于对比实验。
提高多目标优化算法解的分布性和均匀性的方法有多种，如小生境技术，信息熵，聚集密度，聚类分析等。本文采用的聚集密度方法与其它方法相比，优点是既能从宏观上刻画群体的多样性与分布性，也能从微观上描述个体间的内在关系，缺点是计算复杂度偏高。这完全符合优化中的“没有免费的午餐定理（No Free Lunch， NFL）”。
参考文献：
[1]SURRY P D， RADCLIFFE N J. The COMOGA Method： Constrained Optimisation by Multi-objective Genetic Algorithms[J].Control and Cybernetics，1997，26：391-412.
[2]COELLO CAC. Treating Constraints as Objectives for Single-Objective Evolutionary Optimization[J].Engineering Optimization，2000，32：275-308.
[3]COELLO C A C.Constraint-handling using an evolutionary multi-objective optimization technique[J].Civil Engineering and Environmental System，2000，17：319-346.
[4]张丽丽， 许峰. 基于群体分类的复杂约束多目标优化遗传算法[J]. 教育技术导刊， 2009（12）：38-41.
[5]催逊学. 多目标进化算法及其应用[M].北京：国防工业出版社，2008：6.
[6]催逊学. 多目标进化算法及其应用[M].北京：国防工业出版社，2008：7.
[7]郑金华. 多目标进化算法及其应用[M].北京：科学出版社，2010：3-4.
[8]VELDHUIZEN D A， LAMONT G B. Evolutionary computation and convergence to a Pareto front[C]// In John R Koza. Late breaking papers at the genetic programming 1998 conference， Stanford University， California. Stanford Bookstore：221-228.
[9]COELLO COELLO C A. Evolutionary algorithms for solving muli-objective problems [M]. Kluwer Acedemic， 2002：14-18.
[10]E ZITZLER，K DEB，L THIELE.Comparison of multiobective eveolutionary algorithms：Empirical results[J]. Evolutionary Computation，2002，8（2）：173-195.
[11]郑金华. 多目标进化算法及其应用[M]. 北京： 科学出版社， 2007：118-124.
多策略算法 篇3
随着国家电网公司提出建设以特高压为骨干网架,各级电网协调发展的坚强国家电网,促进“大煤电、大水电、大核电、大可再生能源基地”集约化开发的战略思想,输电网规划已成为电力系统优化领域的重要组成部分。根据现有结构进行合理的输电网规划对电力系统安全、经济、可靠运行,乃至国民经济的各项发展都起到举足轻重的作用。
电网建设的复杂化、规模化导致传统数学方法和启发式算法无法求解大规模、复杂化电网规划问题。随着现代启发式算法的提出,输电网规划求解结果和计算速度上都获得了突破性进展。文献[1-8]中分别引入量子进化算法、遗传算法、粒子群算法、人工鱼群算法、蚁群算法,每种方法各有其利弊。但是这些方法的提出扩展了输电网规划求解的思路,有利于快速、精确获得最优规划方案。
标准差分进化算法又称差分进化(DE)算法,是一种新兴的基于群体智能理论的进化计算技术,通过群体内个体间的合作与竞争产生的群体智能指导优化搜索。相比于进化算法,DE算法保留了基于种群的全局搜索策略,采用实数编码基于差分的简单变异操作和一对一的竞争生存策略,降低了遗传操作的复杂性。同时,DE算法特有的记忆能力使其可以动态跟踪当前的搜索情况,以调整其搜索策略,具有较强的全局收敛能力和鲁棒性,且不需要借助问题的特征信息,适于求解一些利用常规数学方法所无法求解的复杂环境中的优化问题。但由于差分进化算法在求解复杂优化问题上还存在早熟、容易陷入局部极值等问题,因此,提出多策略差分进化(MSDE)算法来改善寻优法则,通过动态调整参数及种群优化来快速精确搜索到电网规划全局最优解和最优方案。
1 输电网规划模型
本模型中基于静态规划时,目标函数包括以输电网扩建线路投资费用、网损费用和正常运行时的过负荷费用,同时随着输电走廊费用的日益增加,输电走廊费用在综合成本费用的比重也将逐渐增加,考虑输电走廊因素对规划方案及结果的影响具有合理性,因此目标函数中增加输电走廊费用。扩建后的输电网结构必须是连通的,网络潮流采用直流潮流方程计算,目标函数为:
式中,Y为年费用,包括建设费用和运行费用;k1为支路i新建线路单位公里建设费用;xi为支路i中新建线路公里数;k2为年网损费用系数;ri为支路i的电阻;Pi为正常运行情况下支路i输送的有功功率;k3为过负荷罚系数;W为总过负荷量;B为系统节点导纳矩阵;θ为节点相角矢量;PL为负荷矢量;PG为发电机出力矢量;Bl为由各支路导纳组成的对角矩阵;A为系统关联矩阵;ximax为支路i可以新增线路的上限。
其中总过负荷量
式中,Pi为正常运行方式下线路传输功率;Pimax为线路i的传输功率上限;Ω为过负荷线路集合。
式中,f为输电走廊费用;αi为单位面积输电走廊综合成本;wi为输电走廊宽度;li为支路i线路长度;为所有支路集。
2 差分进化(DE)算法
DE算法是一种基于实数编码的用于优化函数最小值的进化算法。
DE算法流程包括初始化种群、变异、交叉和选择等步骤,具体操作如下:
(1)初始化。同其他智能优化方法一样,DE算法的操作是通过设定一定规模的种群进行的,所以首先建立初始化种群。设初始化种群Ω={X1,X2,X3,…,XNp},其中Np为种群数,Xi={xi,1,xi,2,…,xi,NN},NN为优化问题的解空间维数。种群中每个个体Xi中的各个变量按如下法则产生:
其中,xi,jmax和xi,jmin分别为Xi中第j个分量的上限和下限;rand(0,1)为(0,1)之间的随机数。
(2)变异。经过初始化后对产生的初始值进行变异操作,具体操作方法是:在种群中随机选择三个个体向量,从中选择两个个体向量形成差分向量,再乘上变异因子即形成差分增量,再与待变异个体进行向量合成形成新的个体,如下式:
其中,XGr1、XGr2、XGr3为从父代中选取的三个不同的个体,r1≠r2≠r3≠i。
(3)边界处理。DE算法在经过变异操作后,产生的新的个体种群很有可能不在可行域内,需要对其进行可行性分析和边界处理。
(4)交叉。交叉操作是为了提高后代种群的多样性,交叉操作获得的个体取决于变异得到的新个体和当前个体,通过设定交叉因子参数,以一定的概率分配形成新的个体,操作如下:
式中,CR为交叉因子;vGi,j为第G代变异得到的新种群;xGi,j为第G代种群。
(5)选择。DE算法采用贪婪选择模式,对新的子代种群进行评价,当且仅当新个体的评价函数值优于父代的评价函数值时,才被保留到下一代群体中,否则,父代个体仍然保留在群体中。操作过程如下:
3 改进的差分进化算法
为了提高DE算法的寻优能力和克服启发式算法容易陷入局部极值的问题,需要对某些变量进行改进来提高算法的性能。
DE算法中主要的控制参数为:种群规模Np,变异因子F和交叉因子CR。
(1)Np越大,搜索能力越强,但搜索时间也会增加,一般Np取值[5D,10D],D为优化问题维数。
(2)F控制着种群的多样性,F值越大,种群多样性好,全局搜索能力强。F值越小,种群间个体差异较小,收敛性好,但容易出现早熟现象,一般F的取值为[0,2]。
(3)CR控制着种群的交叉程度,若CR较小,则会使交叉度小,种群新个体少,不利于快速寻优。若CR设置较大,收敛速度快,但容易早熟,通常CR的取值为[0,1]。
(4)变异因子和交叉因子在寻优中的作用明显,对F和CR进行动态调整参照文献[13]。
(5)边界处理:对于越界的个体具体操作如下:
其中,xi,jmax和xi,jmin分别为Xi中第j个分量的上限和下限,电网规划中设定上限为1,下限为0。
(6)变异策略改进。由于差分算法的变异策略在进行变异操作时具有随机性,缺乏主动向最优值逼近的能力,所以通过对差分策略改进来提高寻优的能力。
策略一:
将最优个体引入变异中有利于提高局部寻优能力和收敛速度。
策略二:
差分向量的动态调整有利于寻优方向的多样性,提高全局搜索能力。
策略三:
其中,,Gm为最大迭代次数。
在提高局部寻优的同时保留了差分向量的全局搜索能力。
(7)局部寻优策略。算法寻优中有时容易过早陷入局部极值,造成长时间停留在局部极值点,为此通过对各代最优方案进行局部搜索来提高局部爬山能力,搜索策略如下:
将当前最优方案XGbest的任意两个位置xi,xj进行互换,从而获得新的个体,即
来进行局部爬山,有可能获得更好解。
算法求解流程:
步骤1:设置控制参数Np,Gm,Fmin,Fmax,μ0,CRmin,CRmax等;
步骤2:随机产生初始种群,对种群进行评价,形成初始最优解G=1;
步骤3:根据式(12)~式(14)进行变异操作,产生3个变异个体,随机选出一个体作为变异后新形成的个体;
步骤4:进行交叉操作,通过式(9)形成新的试验个体;
步骤5:进行选择操作,通过式(10)选择出新的最优个体,同时对当前最优个体进行局部搜索见式(15);
步骤6:若选择出的种群评价后的结果满足约束条件,则转步骤8,否则进行步骤7;
步骤7:G=G+1,返回步骤3;
步骤8:输出最优值及最优方案;
算法流程图如图1所示。
4 算例分析
4.1 算例1
采用IEEE Garver-6系统进行试验,算例网络结构及数据参数参见文献[5]。
对于多策略差分进化算法,经多次调试参数设置可取,种群数Np=150;交叉因子CRmin=0.2,CRmax=0.7;变异因子Fmin=0.2,Fmax=2,μ0=0.9;最大迭代次数为Gm=100。对220 kV,根据《国家电网公司输变电工程通用造价220k V输电线路分册造价》及文献[13]相关数据确定α的取值,取单回线输电走廊综合成本为1.45(元/m2),取双回线输电走廊综合成本为1.32(元/m2),取三回线输电走廊综合成本为1.25(元/m2),取四回线输电走廊综合成本为1.20(元/m2)。
应用MATLAB编制多策略差分进化算法程序并求解。最优结果为7985.5万元,其中输电走廊费用为2100.2万元,规划方案如图2所示。
为了论证多策略差分进化算法的优越性,将其与采用单一变异策略的差分进化算法进行比较,最大迭代次数均设为100次,分析结果见表1。
从图3可以看出,MSDE算法在求解Garver-6系统上可以短时间求得最优结果,并且迭代次数少。通过表1可以看出,经过30次运算,无论是在最优解出现代数上还是在运算时间上,MSDE都具有很大的优势,可以快速有效地得到最优结果,同时通过与混合人工鱼算法[7]进行比较可以得出,MSDE算法比混合人工鱼算法在计算时间上更有优势。
4.2 算例2
对IEEE-18节点系统进行试验,该系统共有18个节点,9条已建输电线路及33条待选输电线路,网络结构及相关参数参见文献[5]及算例1。
经过调试,改进差分进化算法各参数取Np=250;交叉因子取CRmin=0.2,CRmax=0.7;变异因子Fmin=0.2,Fmax=2,μ0=0.9;最大迭代次数为Gm=200。最优结果为54426万元,其中输电走廊费用为14051万元,程序规划方案如图4所示。
对于18节点系统采用多策略差分进化算法与采用单一变异策略的差分进化算法进行比较,迭代次数为1000次,分析结果如图5所示。
通过图4可以看出,单一变异策略的DE算法在寻优过程中2次陷入局部极值,在运行期间陷入难以跳出的局部极值点,迭代近40次才跳出,造成运行时间过长。由表2分析可以得出MSDE算法比DE算法在求解时间及精度上都有很大的提升。通过与较为成熟的混合人工鱼算法[7]进行比较分析可以得出,MSDE算法的寻优性优于混合人工鱼算法的寻优性。
虽然由于算例维数的增加和种群数的增加一定程度上影响了MSDE算法求解的时间和最优解出现的代数范围,但是总体寻优性良好。
5 结论
标准差分进化(DE)算法易陷入局部最优解,在迭代中后期,由于越来越多的种群无法有效跳出局部最优点,致使算法寻优能力下降。通过增加多策略变异操作和局部搜索策略提高全局和局部搜索能力,可有效避免陷入局部极值的危险,同时可以有效、快速地得到最优解。通过理论分析和算例测试,证明多策略DE算法比DE算法具有极强的收敛性,并有效提高了处理输电网规划问题的效率。
多策略算法 篇4
目前广东电信的EVDO网络组网和扩容方式为:全网部署EVDO单载频网络, 局部话务热点进行单站点、单扇区多载频扩容, 双载频扇区主要集中在各区、镇中心等EVDO话务密集地区, 呈点状分布。
由于目前的多载频组网采用单点扩容的方式, 以吸收局部热点话务为主要目的;另一方面考虑到数据用户的移动性不强, 因此目前采取的话务分配和切换策略为:
(1) EVDO用户在空闲态采用Hash算法分别驻留在37、78两个频点;
(2) 关闭业务硬指配功能, 用户在业务态仍被分配到空闲态所驻留的频点;
(3) 叠加载频和基本载频使用相同功率发射;
(4) 不进行扩展频点78到基本频点37的异频硬切换。
2 EVDO多载频组网的关键问题和华为相关算法
在EVDO多载频组网中, 终端在不同状态下所关注的问题重点也不同;在空闲态, 主要考虑终端驻留到哪个载频;在接入态, 主要考虑业务指配到哪个载频;在业务态, 主要考虑多载频边界的硬切换问题。
2.1 空闲态驻留问题
(1) 终端在所有载频HASH:
这种驻留策略的优点是:数据配置简单, 公共信道的负荷在各载频间均衡分担;缺点是:在载频边界区域, 终端可能选择不同的载频, 可能发生比较频繁的载频间待机切换。
(2) 终端只待机在基本载频:
这种驻留策略的优点是:终端容易实现寻呼, 可以节省叠加载频的公共信道功率;缺点是:不同载频间覆盖情况不一致, 容易带来基本载频的寻呼过载或接入过载。
2.2 接入态硬指配问题
接入硬指配是多载频组网中话务引导策略之一。目前华为EVDO系统提供反向RSSI硬指配、Rev.A版本优先硬指配、接入优先硬指配、优先级优先硬指配、负荷均衡 (基本) 硬指配五种硬指配算法。
2.3 业务态边界异频硬切换问题
在多载频组网的网络中, 当终端处于叠加载频的边界小区向外移动时, 需要切换到基本载频, 才能继续进行业务。如果系统不配置载频间硬切换, 终端将在叠加载频上进入休眠态, 然后在基本载频重新激活, 继续开展业务。
目前华为EVDO异频硬切换算法有:RTD硬切换、DRC硬切换、RL Link Quality硬切换和OFS硬切换4种。除OFS硬切换外, 其它硬切换算法都为盲切换算法。
3 EVDO多载频组网实战案例分析
3.1 EVDO多载频孤岛站点算法验证
本次测试分别使用关闭硬切换、RTD硬切换算法、OFS硬切换算法进行验证, 比较不同硬切换算法的效果。
3.1.1 关闭异频硬切换测试情况
(1) 测试情况
EVDO终端保持78频点, 向单载频区域行驶, SINR开始恶化, 下载速率开始变低并出现明显波动, 并出现多次速率掉零的情况。最后由于持续15秒无速率, 触发休眠定时器, 终端进入休眠态, 之后在37频点重新激活, 下载速率恢复正常。从信号开始恶化、速率出现降低、波动, 到终端重新在37频点激活、速率恢复的总时间长达2分50秒左右。
(2) 测试结论
在不做异频硬切换的情况下, 即使78频点的信号恶化, 终端也无法切换到覆盖更好的37频点;处于叠加载频覆盖边缘的终端将长期处于信号弱、速率不稳定的状态, 直至信号弱到持续15s无数据流量, 触发去激活定时器进入休眠态为止。
3.1.2 RTD硬切换算法验证
(1) 测试情况
从DT测试数据看, 终端成功从78频点切换到37频点, 硬切换过程中存在较明显的断点。从后台信令跟踪结果看, 在满足RTD硬切换触发条件的情况下, RTD硬切换可以完成。
将RTD硬切换参数按下表设置不同组合进行对比测试, 发现不同参数设置下的RTD硬切换效果存在较大差异。
在当前选择的测试路径下, 默认值配置无法触发异频硬切换, 终端因持续15s速率掉零而触发了休眠重激活流程。
采用优化参数值系列1时, 数据速率在近4分钟内持续偏低, 低于100 kbit/s。
采用优化参数值系列2时, 切换过程掉零时间很短, 速率受影响的时长仅为10秒左右。
采用优化参数值系列3时, 数据速率在近7分钟内持续偏低, 约100～200 kbit/s。
对比三组优化值系列的测试结果, 优化值系列2在该测试路径上性能较好, 而其他3组参数配置值的硬切换性能不佳。
(2) 测试结论
华为RTD硬切换算法可以工作, 信令流程正常;但是在不同的参数配置下, RTD硬切换效果差异非常大;当参数配置合适时, RTD硬切换效果良好, 切换过程中速率波动较小, 而当参数配置不合适时, RTD硬切换效果很差, 掉零时间长达4～7分钟, 比不配置硬切换的掉零时间还长。鉴于该切换算法对参数设置的敏感度过高, 且实际组网中边界环境更加复杂, 参数配置难于在各切换路径同时优化到理想状态, 因此实际组网中不建议使用RTD硬切换算法。
3.1.3 OFS硬切换算法验证
从DT测试数据和后台信令跟踪结果看, 在满足OFS硬切换触发条件的情况下, OFS硬切换可以完成。将OFS硬切换的相关参数按下表设置不同组合进行对比测试, 发现在不同参数设置下, OFS硬切换的效果相近, 且测试效果良好, 仅在切换位置上有少许差异。
3.1.4 小结
通过对关闭异频硬切换、打开RTD硬切换、打开OFS硬切换三种情况的测试比较, 得出以下基本结论:
(1) 关闭异频硬切换会导致载频边界的部分用户长期处于低速和不稳定状态;
(2) RTD硬切换算法对参数设置过于敏感, 不适合现网使用;
(3) OFS硬切换成功率高, 测试效果好, 更适合在现网使用。
3.2 EVDO多载频成片组网研究
3.2.1 成片扩容组网实验目标
本次EVDO成片组网实验以东莞南城区的49个室外双载频DO扇区为研究目标区域。
3.2.2 算法和策略选择
依据单站验证结果, 结合扩容区域实际情况, 本次EVDO成片多载频组网的空闲驻留、硬指配算法、硬切换算法选择以及主要参数设置如下:
(1) 空闲驻留策略:终端在37频点、78频点两个频点进行Hash选择驻留;
(2) 接入硬指配策略:多载频边界扇区关闭硬指配, 多载频核心扇区打开接入优先硬指配, 指配门限设置为12 (等效用户数) ;
(3) 异频硬切换算法:多载频核心扇区关闭硬切换, 边界扇区打开OFS硬切换算法, 切换相对门限设置为2.5dB;打开AN内硬切换宏分集开关。
(4) 功率配置:多载频核心扇区的78频点功率和37频点保持一致, 边界扇区78载频功率在37频点功率的基础上衰减3dB。
(5) 邻区配置:邻区配置主要参考37频点当前的邻区配置, 多载频核心扇区仅配置同频邻区, 边界扇区同时配置同频邻区和异频邻区。
3.2.3 效果评估
(1) 路测情况
OFS硬切换打开后, 在边界区域选取两条道路进行测试, 验证OFS切换在成片组网中的效果。从测试结果看, 都能成功完成硬切换, 且切换过程中SINR值总体较好。
(2) 性能指标跟踪评估
从12月15日成片双载频扩容后, 由于话务负荷的分担, 连接成功率有一定的提升, 从98.9%上升到99.1%左右, 掉话率基本保持不变;12月17日凌晨调整边界扇区功率、关闭硬指配、打开OFS硬切换后, 边界扇区的功率得到有效控制, 且减少了硬指配失败, 连接成功率有较明显的增长, 提升到94%以上, 掉话率指标基本保持在1.5%～3%的日常波动范围内, 并呈现逐渐下降的趋势。
12月17日打开OFS硬切换开关, 经过连续4天观察, 每天的硬切换成功率均保持在92%以上, 平均达到94%以上;该项指标基本达到预期要求。
OFS硬切换是在终端搜索了异频信号后再做出切换选择, 其切换成功率其他盲切换算法高, 但和软切换相比, OFS硬切换成功率还是明显偏低的。
从图1可以看出, 12月15日打开双载频后, 该区域的话务被37、78两个频点分担;12月17日降低边界扇区功率后, 两个载频间的话务分配得到进一步均衡, 载频间的话务差从20%下降到10%左右。
3.2.4 小结
从路测效果和性能统计两方面来看, 本次组网实验选择的驻留策略、硬指配算法、硬切换算法、参数配置均能达到比较良好的效果;多载频组网优化后, 连接成功率上升明显, 载频间话务基本均衡, 掉话率变化不大, 保持在日常波动范围内。
由于各种策略和算法的效果受无线环境因素的影响较大, 在多载频扩容后需要进行针对性的RF优化和参数优化, 优化后各项性能指标将会有进一步提升。
4 研究结论和组网配置建议
4.1 EVDO多载频组网研究结论
本次在东莞进行的EVDO多载频组网研究, 通过孤岛站点、成片站点两种组网场景的模拟、测试和分析优化, 得出结论如下:
(1) HASH驻留策略、硬指配算法的配合使用, 对载频间负荷均衡意义重大。
(2) 处于多载频边界区边缘, 且工作于叠加载频的终端速率会受到影响, 需要进行调整优化。
(3) 现有异频硬切换算法中, RTD算法不适合组网使用, OFS算法是比较适合组网使用的算法, 硬切换成功率和网络性能均达到预期。
(4) 需要控制多载频边界扇区叠加载频的功率和覆盖范围, 能提高接入、切换、速率等性能。
4.2 EVDO多载频组网配置建议
4.2.1 基本组网形式建议
EVDO多载频基本组网形式的选择, 需要结合网络容量需求、用户分布、使用习惯、业务种类等因素进行综合考虑。
(1) 现阶段组网形式建议
目前EVDO业务热点在地理上呈不均匀分布, 局部地区呈现点状或小区域的业务热点;用户使用业务多为BE类下载业务, 暂无VoIP、VT等时延敏感型业务, 用户移动性不强, 且对网络性能的关注主要集中在连接和速率方面, 因此用户对EVDO无线掉话并不敏感。
在EVDO网络建设和业务发展初期, 建议EVDO多载频采用“局部单点扩容+小区域成片组网”的形式, 有针对性地部署多载频站点, 以合理分担局部话务为主要目的, 并提高网络投资的有效性。
(2) 后期组网形式建议
随着3G业务的不断推广, EVDO网络负荷会出现在较大范围内呈现同步上升, 同时存在局部热点的局面;特别是VoIP、VT等新业务推出后, 用户的移动性将显著加强, 用户对无线掉话的关注程度会大幅度提高。
在此情况下, 建议EVDO多载频采用“成片组网+局部再扩容”的形式, 并将多载频边界规划到非话务密集区域;一方面提高大区域的整体网络容量, 另一方面保证叠加载频的连续覆盖, 尽量减少载频间硬切换, 提高用户感知度。
4.2.2 多载频孤岛站点配置建议
(1) 功率配置:叠加载频功率相对基本载频衰减2～4dB, 以确保两个载频的覆盖范围尽量一致, 避免叠加载频因覆盖范围过大而话务负荷超重, 影响该载频用户的网络使用感受。
(2) 驻留策略:终端同时在多个载频进行Hash驻留, 保持公共信道的负荷在各载频间均衡分担, 并和硬指配策略配合保持载频间的业务负荷均衡。
(3) 接入硬指配策略:孤岛多载频站点各载频的覆盖范围一定会存在差异, 为避免频繁的跨载频指配引起的指配失败, 建议关闭接入硬指配。
(4) 异频硬切换策略:孤岛站点叠加载频受到干扰小, 覆盖难以控制, 硬切换效果相对不稳定, 建议孤岛多载频站点慎重开启异频硬切换算法, 如开启需密切观察掉话率指标变化。
4.2.3 多载频成片组网配置建议
(1) 功率配置:多载频核心区域的叠加载频功率设置和基本载频相同, 边界区域的叠加载频功率相对基本载频衰减2～4 dB, 以确保两个载频的覆盖范围尽量保持一致。
(2) 驻留策略:终端同时在多个载频进行Hash驻留, 保持公共信道的负荷在各载频间均衡分担, 并和硬指配策略配合保持载频间的业务负荷均衡。
(3) 接入硬指配策略:多载频核心区域的扇区打开接入优先硬指配算法, 指配门限设为10～15, 尽量实现载频间话务均衡;多载频边界区域的扇区关闭接入硬指配算法, 以提高接入成功率。
(4) 异频切换策略:在已有的算法中, 建议使用OFS异频搜索硬切换算法, 在实际组网中需要结合射频优化, 对硬切换参数、异频邻区配置等方面进行详细优化, 以提高切换性能。
4.3 多载频组网相关算法的开发建议
(1) 尽快实现和完善EVDO伪导频切换算法。
OFS硬切换需要终端搜索异频的信号, 对终端质量要求较高, 有可能造成质量较差的终端在进行异频搜索时掉话。从1X网络异频切换的经验看, 伪导频辅助切换是成功率最高、效果最好的切换方式, 建议华为尽快对EVDO伪导频切换算法进行验证和完善。
(2) 开发基于业务类型的硬指配算法。
从本次研究结果看, 组网策略选择的难点在载频边界的异频硬切换问题;而对于未来的VoIP、VT等新业务, 该问题是无法回避的。假设在多载频网络的接入硬指配过程中, 可以选择将BE类业务优先指配到叠加载频, 而时延敏感型业务优先指配到基本载频, 可以有效地降低用户对载频边界切换的敏感程度。因此, 建议华为开发基于业务类型的接入硬指配算法。
摘要：EVDO商用以来, 用户量和业务量都飞速发展, 纯单载频网络已经无法满足容量的需求。目前广东电信EVDO网络的多载频组网方式多为全网单载频+局部单点双载频部署, 此部署方式长期来看无法满足3G业务的爆发性增长需要, 而且对网络性能存在一定的影响, 特别是对将来要开展的新业务。在成片进行多载频扩容时, 需要对核心区、边界区的驻留、指配策略, 以及载频边缘的异频切换策略进行全面考虑。本论文以东莞EVDO网络多载频单站、成片扩容实践为例, 对华为多载频扩容的相关算法和策略进行研究, 并给出配置建议。
多策略算法 篇5
目前, 在以工期最短或资源均衡为目标的项目调度问题取得了很好的成果。例如, 文献[1]将单种资源均衡问题转化为多种资源均衡问题, 利用启发式算法对其进行求解。文献[2]基于多种优先规则设计启发式算法求解了多项目调度问题。文献[3]以最小时差为优先规则生成项目进度计划, 将任务的优先规则与遗传算法结合, 设计了遗传算法。文献[4]对每个任务进行赋值, 此值代表任务的优先权, 生成进度计划, 并设计了遗传算法。文献[5]引入自适应高斯变异算子, 设计了与遗传算法相结合的改进的免疫算法。文献[6]设计了遗传蚁群融合算法, 此算法克服了遗传算法及蚂蚁算法的不足。文献[7]设计了一种混合遗传算法, 此算法克服了遗传算法局部寻优能力不足的缺陷。文献[8]将各项目视为整体, 以资源均衡为目标建立了数学模型, 并设计了免疫遗传算法。文献[9]在文献[8]的基础上, 针对每个项目内部的工作数相同的情况, 建立了以资源均衡为目标的模型, 同时设计了免疫遗传算法。通过在企业调查发现, 每个项目内部的工作数有可能不同。另外, 由于企业自身资源的限制和外部环境因素的影响, 需要同时考虑资源均衡和工期最短两个问题。因此, 本文采用加权的方法将工期最短和资源均衡问题一起考虑, 建立改进的多项目多工作选择计划的数学模型, 并设计动态克隆选择算法DCSA (Dynamic Colonel Selection Algorithm) 求解。
1 问题描述
设项目集为C={ci|i=1, 2, …, N}, C中项目之间存在承继关系;ci有Mi (i=1, …, N) 个工作, 且在ci内, 工作与工作之间满足时序约束;cij是ci的第j个工作, Qi表示ci的所有紧前项目构成的集合, Pij表示cij的所有紧前工作构成的集合。对于项目ci, bi=1表示ci被选中执行, 否则, bi=0;若ci在第t天被选中执行, 则bit=1, 否则, bit=0;atij=1表示ci的第j个工作cij在第t天被选中执行, 否则, atij=0。ci的开始时间、合同截止日期、执行时间分别记为si、ei、Ti;sij和dij分别表示cij的开始时间和执行时间。企业共有R种资源, Rk、Rtk分别表示第k种资源的总限量、第k种资源第t天的总限量, cij每天使用第k种资源为rijk, 则建立改进的多项目多工作选择计划数学模型 (P) :
式 (1) 为目标函数, α为权重因子, Q为使目标函数第一项和第二项在同等的量级上引入的常数;式 (2) 为每个项目的执行时间;式 (3) 为所有项目的总工期;式 (4) 表示各项目各工作的时序约束;式 (5) 表示项目的合同约束;式 (6) 表示项目的承继约束;式 (7) 表示第k种资源在第t天的资源限制;式 (8) 表示第k种资源的总资源限制;式 (9) 表示第k种资源的资源利用偏差;式 (10) 表示资源的权重之和等于1。
2 动态克隆选择算法
克隆选择体现了生物体免疫系统对自适应抗原刺激的动态过程[10]。应答抗原能力强、亲和力高的免疫细胞通过克隆选择被选择繁殖一些克隆细胞。其基因进行重复突变, 产生应答能力更强、亲和力更高的细胞。借鉴此过程, 设计动态克隆选择算法 (DCSA) 求解上述问题。
2.1 编码
项目调度序列及对应内部工作的调度序列分别记为C=c1c2…cN、J=J1J2…JN, 且项目ci的工作调度序列记为。项目是否被选中执行用0、1字符串表示为B=b1b2…bN。抗体的编码记为Ab= (C;B;J) , 表示最终的调度方案。
2.2 初始抗体的产生规则
由于项目之间、项目内部工作之间不仅需要满足承继约束、时序约束, 而且还需要满足资源的限制。基于此, 采用拓扑排序生成项目及其工作的调度序列, 根据资源限制安排各工作的开始时间, 再由各工作的开始时间及执行时间确定项目的开始时间、完工时间。最后根据项目完工时间确定是否被选中, 从而生成一个抗体。进而产生所有需要的抗体。
2.3 亲和力的设计
项目总数、被选择执行的项目数分别记为N、N1, 抗体Ab在数学模型中的目标函数值记为f (Ab) , 亲和力记为aff (Ab) 。对于最小化问题, 亲和力与目标函数值成反比, 则aff (Ab) 设计为:
2.4 动态繁殖
首先将抗体群按亲和力从大到小排序, 按下式:
将排好序的群体划分成L个子群, Hi (i=1, …, L) 为每个子群的抗体数。对子群i (i=1, …, L) 进行动态繁殖:即对第i个子群中亲和力最好的抗体繁殖Hi-1个替换此子群中其余的抗体。
2.5 一点交叉
针对克隆群中的每个抗体, 生成一个0到1的随机数β, 如果β>0.5, 则从该群中随机选择一个不同的抗体与之进行一点交叉[11]。否则, 从记忆池中任选一个抗体与之进行一点交叉[11]。
2.6 变异
随机生成一个0到1的数β, 若β>Pc (Pc为变异概率) , 随机整数λ (1<λ<N) 作为抗体Ab的项目调度序列基因块C=c1c2…cN的变异点, 对该变异点进行插入式变异[12]。并按初始抗体规则中工作调度序列的产生方式重新生成该变异点对应项目的工作调度序列。若β<Pc, 按初始抗体产生规则重新生成项目及其工作的调度顺序。
2.7 克隆选择
首先将群体按目标函数值进行升幂排序, 按下式:
将排好序的群体划分成M层, 对于前M/2层, 从每层中随机挑选三分之二的抗体进入群体Dn且保证每层最好抗体进入Dn, 对于后M/2层, 从每层中随机选取三分之一的抗体进入Dn且每层最好抗体进入Dn。
2.8 动态克隆选择算法 (DCSA) 描述
Step1n←1, 生成M+m个初始抗体, 随机选取m个抗体进入记忆池Me中, 剩下的N个抗体进入一般抗体群An中;
Step2根据式 (11) 计算Me和An中抗体的亲和力;
Step3将An中抗体进行动态繁殖, 获Bn;
Step4将Bn进行变异、一点交叉操作, 得B'n和C'n;按式 (11) 计算B'n、C'n中抗体的亲和力;
Step5删除An∪B'n∪C'n中相同的个体, 然后进行克隆选择操作, 获Dn;
Step6根据随机抑制半径α, 删除Dn∪Me多余的抗体并对Me进行更新;
Step7对Dn进行更新操作, 得An+1;
Step8若满足终止条件, 则输出Me中最好抗体, 并结束;否则, n←n+1, 转到Step3。
3 数值实验
本文首次将资源均衡和工期最短两个目标一起考虑解决多项目多工作选择计划问题, 选取MaxR、Max TW、Long T、Min LF四种不同优先规则的启发式算法[13]与动态克隆选择算法 (DC-SA) 进行比较。MaxR、Max TW、Long T、Min LF仅各自执行1次;DCSA执行30次;迭代次数Max=300, 一般抗体群规模N=50, 记忆池规模m=15, 变异概率Pc=0.7。
问题企业承接了30个项目, 每个项目的工作数不同, 每个项目的工作数大于等于10小于等于25个, 项目必须在T=150 (天) 中完成, 企业一共有4种资源, 资源的权重分别为0.3, 0.2, 0.3, 0.2, 每天的资源量分别为10、10、10、10、10, 且在T天内的总资源量分别为1450、1400、1450、1400。由于资源的限制, 企业只能选择部分项目执行, 不被选中的项目实行外包 (省略其他相关数据) , 数值实验结果如表1-表3所示。
由表1-表3可知, 当模型的加权因子等于0.5时, 所有算法都获得了问题的决策方案, 并且被选中执行的项目都在合同规定的时间内完成, 各种资源使用量也没有超出限制。在四种启发式算法中, Min LF选中项目最多, MaxR资源利用最好;MaxR和Long T项目选中率相同, 但资源利用率和决策方案的总工期不同;Max TW选中项目最少, 资源利用最差。动态克隆选择算法的项目选中率与Min LF相同, 但是资源利用率为98.7962%, 最好方案的总工期121, 比其它四种启发式算法的结果好。此外, 当模型的加权因子为0时, 此问题就是资源均衡问题, 动态克隆选择算法的项目平均选中率与模型的加权因子为0.5时的选中率相同, 但是资源利用率和最好方案的总工期分别为99.1506%、127, 资源利用上好于模型的加权因子为0.5时的资源利用率;当模型的加权因子为1.0时, 此问题就是工期最短问题, 动态克隆选择算法的项目选中率与模型的加权因子为0.5时的选中率相同, 但是资源利用率和最好方案的总工期分别为98.3567%、118, 工期好于模型的加权因子为0.5时的总工期。不管模型的加权因子取何值, 四种启发式算法仅仅目标函数值发生变化, 最好方案的总工期及资源利用率均不变化。因为启发式算法的优先规则是已经确定的, 所以项目的调度顺序和工作的执行顺序就确定, 不会因模型的加权因子不同而不同。另外, 当项目数和工作数增多时, 本问题就变得更加复杂, 启发式算法很难处理这类复杂问题, 也不能获得较好决策方案, 而本文设计的动态克隆选择算法可以通过动态克隆、交叉、变异、克隆选择算子增加群体的多样性, 也可以扩大动态克隆选择算法的搜索范围, 进而能获得更好的解。
4 结语
机动目标静态多模型算法 篇6
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.
多策略算法 篇7
关键词：粒子群,算法,工程项目,多目标,优化算法
现代工程实践和科学研究中遇到的很多问题都是多目标优化问题, 多个目标之间通过决策变量项目制约, 对于单个目标的优化问题的唯一最优来说, 多目标问题的解并不是唯一的, 而是存在一个最优解结合, 在该集合内的每一个解都称为多目标非支配解。对于工程项目来说, 工期、成本和质量是工程项目的“三大目标”, 也是决定项目成功与否的关键因素, 对于任何一个项目, 即需要在约定时间内完成, 也需要控制项目成本, 同时还必须确保项目质量符合需求。但是工期、成本和质量这三个目标存在相互制约的关系, 一般来说, 工期和成本成正比, 工期和质量成反比, 成本和质量成反比。。因此, 需要采用多目标算法来求解工期、成本和质量三个目标优化问题, 并且从得到的解集中根据需求挑选出最优解作为该项目的最优规划目标解。
1 多目标粒子群算法
1.1 多目标算法
多目标优化算法可以描述为:一个由满足一定约束条件的决策变量组成的向量, 使得一个由多个目标函数组成的向量函数最优化。目标函数组成了性能标准的数学描述, 而性能标准之间通常是互相冲突的。优化意味着要找到一个使得所有目标函数值都可接受的解。
多目标优化问题中的最优概念最先由Francis Ysidro Edgeworth提出, 后来Vilfredo Pareto给出了系统的定义, 通常称为Pareto最优[1,2]。
不失一般性, 在一个有k个目标函数最大化的问题中, 称决策向量x*∈F是Pareto最优的, 当不存在另外一个决策向量x∈F同时满足式1。
同样地, 在最大化问题中称决策向量x优于y, 或者支配y, 需要满足式2。
1.2 多目标粒子群算法
结合粒子群算法搜索思想和多目标算法原理设计多目标粒子群算法, 由于相对于单目标粒子群算法中的个体历史最优和群体历史最优的唯一性, 多目标算法中个体历史最优和群体历史最优均是一个非支配解集, 因此在多目标算法的设计中需要解决从非支配解集中挑选出最优跟踪个体的问题。该文采用了文件记录的方法来记录在算法搜索的过程中找到的所有的非支配解, 并且采用一定的方法来选择个体跟踪的优秀目标。
由于多目标粒子群算法在搜索的过程中同时记录个体全局最优解, 个体最优解和局部最优解, 因此需要三个记录文件来记录。但是由于三个记录文件中的非支配解存在相互交叉支配的现象, 并且为了算法简洁高效, 该文采用一个档案文件同时记录全局最优解, 个体最优解和局部最优解, 档案文件在算法搜索的过程中, 只要发现新得到的搜索解存在支配管理, 就把该解放入记录文件中, 同时根据支配关系, 密度关系等调整记录文件中的最优解。
在记录文件记录所有最优解的基础上, 通过非支配解排序的方法来解决这个每次迭代搜索的时候, 粒子跟随的最优个体问题, 具体思路就是首先评估排序所有的非支配解, 然后从排序好的解集中根据排序的序号, 以选择概率的方法选择排序靠前的非支配解作为个体跟踪对象, 非支配解排序的序号越靠前, 其被选中的概率越大。
2 工程项目多目标建模
2.1 工程项目分解
本文在求解的时候首先采用网络计划技术把整个项目进行工序分解, 并且得到工序流程图, 流程图中的每个工序节点都有多种不同的施工方案, 每个施工方法都对应不同的施工费用、工期和质量。因此项目建设规划便存在多种工期、成本和质量的组合方案, 工程项目网络计划图如图1所示[3]。
其中, Mij表示第i道工序的第j种执行模式, Cij、Tij、Qij为该执行模式需要的执行成本、执行工期以及工序质量。
2.2 模型建立
在多目标模型建立的环节, 首先分别建立工期目标模型、成本目标模型和质量目标模型, 然后把三个模型进行组合, 得到了工程项目工期、成本和质量多目标优化模型[4]。
项目工期模型如式 (3) 所示。
其中, L表示路径集合, Li表示具体的路径, xim为0或者1, 代表是否执行了活动i的第m道执行模式, 其中1表示执行, 0表示没有执行。tim表示执行了活动i的的第m道执行模式所获得的所需工时。
项目成本模型如式 (4) 所示。
其中, xim为0或者1, 代表是否执行了活动i的第m道执行模式。uim, k表示在执行活动i第m道执行模式时, 所耗费的第k项资源的单位费用, rmi, k表示在执行活动耗费的第k项资源的量。idcim, k表示执行活动耗费的第k项间接资源费用。
质量目标模型如式 (5) 所示。
其中, qim表示在子工序i的在第m道执行模式中对应的质量值, 分母表示把所有子工序对应的指标质量值均设为10时的项目总质量值。
因此, 总体的多目标模型如式 (6) 所示。
3 仿真实验
采用工程项目多目标粒子群算法仿真实际工程道路项目, 该道路工程为典型的土方施工项目, 根据项目施工规划要求以及施工地的地质特点, 整个项目可以细化为包括施工准备、路基土方、软土处理、防护工程等在内的15项具体活动, 该连接线工程的网络计划图如图2所示。
采用多目标粒子群算法优化项目工序模式选择, 因为项目工序模式为整数, 所以采用对种群进行离散化, 即每一次迭代得到新的种群后, 都采用四舍五入的方法把新的种群离散化。因为一共有14道施工工序, 所以粒子维数为14, 从而每一个粒子都代表一个施工方案, 其他的参数为种群个数为100, 算法迭代次数为20。算法得到的多目标非支配解如图3所示。
从图3可以看出, 该文提出的多目标粒子群算法搜索性能较高, 算法在运行的时候能够找到较多的非支配解集, 对于每个非支配解集中的解来说, 都代表其中的一个施工方案。
4 小结
针对工程项目建设规划问题中工期-成本-质量三个目标相互制约, 一般算法难以得到三个目标的最优解的问题, 该文采用多目标粒子群算法进行求解, 在建立寻优问题的基础上, 采用粒子群算法搜索多目标问题的非支配解集, 仿真实验表明多目标粒子群算法能够得到工期-成本-质量多目标优化问题的解集, 从而为工程项目规划提供了一个新的参考方法。
参考文献
[1]郑向伟, 刘弘.多目标进化算法研究进展[J].计算机科学, 2007, 34 (7) :187-192.
[2]崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社, 2006:6-12.
[3]曹吉鸣, 徐伟.网络计划技术与施工组织设计[M].上海:同济大学出版社, 2000 (6) .
多策略算法 篇8
随着人工智能技术在交通管理中的应用,智慧交通的建设受到了极大的关注。对车牌的正确识别是建设智慧交通的基石,因此车牌识别成为当前研究的热门领域。目前车牌识别技术已经被运用到违章检测(电子警察)、停车场不停车收费、车辆检测等领域。
车牌定位是车牌识别的关键和重要前提。从复杂的背景中正确定位车牌位置,是成功识别车牌的重要成功率,直接影响最终车牌识别的效果。在车牌定位方面,国内外学者都做了大量的研究,并提出了一些多车牌定位的算法。比较常用的算法有以下几种:
1)基于纹理的分割方法,主要利用车牌区域水平方向的纹理特征进行分割,包括小波纹理、水平梯度差分纹理等[1]。该方法定位成功率不高,因为车牌图像中很可能不止一个区域具有车牌区域的纹理特征,难以准确找到车牌位置;而且对车牌倾斜度有要求,当倾斜度过大时,车牌定位效果明显下降。
2)基于边缘检测的分割方法通过检测车牌字符的边缘特征定位车牌[2]。由于许多汽车前脸栅栏有很多垂直或水平边缘,因此会影响定位成功率。
3)基于神经网络的方法,选取训练样本,将图像的灰度序列采用BP算法进行训练,获得有效的网络权值[3]。该方法用BP网络对灰度图像进行感知,能够获得较好定位效果。
4)基于数学形态算法的方法,利用开运算和闭运算对图像进行处理,得到多个区域,再对这些区域进行判断,找到车牌正确位置[4]。
以上算法在背景不太复杂的情况下,对于单车牌都有比较好的定位成功率。但对于复杂背景下的多车牌定位,则需要综合多种定位方法,排除更多的干扰因素来确定车牌的定位。
基于以上分析,本文采用基于颜色检测、边缘检测与支持向量机相结合的定位方法现多车牌定位。首先针对基于颜色检测车牌候选区域的方法进行改进,并引入了边缘检测的方法来定位,通过颜色与宽高比来选取车牌候选区域,最后基于支持向量机(SVM)完成车牌的精确定位和截取。通过对不同多车牌图片的车牌定位,验证算法的有效性。
2 基于多算法融合的多车牌定位方法
在日常生产生活中,最常见的有小型汽车号牌、大型汽车号牌、警用汽车号牌等。2007年发布的《中华人民共和国公共安全行业标准》(GA36-2007)对我国机动车号牌标准做了详尽规定。小型汽车号牌是蓝底白字白框线的车牌;大型汽车号牌前车牌是黄底黑字黑框线的车牌;警用汽车车牌是白底黑字,红“警”字黑框线车牌。它们的尺寸大小都是440mm×140mm。本文所研究的多车牌定位方法主要是针对小型汽车号牌和大型汽车号牌进行定位。
本文对多车牌定位的流程如下:首先进行车牌候选区的定位;其次进行车牌候选区域的去噪和倾斜校正;最后基于SVM进行车牌精确定位和提取。
2.1 基于颜色和Sobel边缘检测的车牌粗定位方法
RGB颜色模型和HSV颜色模型是数字图像处理中常用的两个颜色模型。RGB彩色模型中,各像素值是由R(红色)、G(绿色)和B(蓝色)三种颜色分量的亮度值叠加来表示。而这三种颜色的亮度值对环境的光照强度比较敏感。当光照强度变化时,这三种亮度值会随之变化。所以,在RGB颜色模型下,很难完成基于颜色的车牌定位。
在HSV颜色模型中,一个像素的颜色特征分别用H(色度)、S(饱和度)和V(亮度)三个分量来表示。亮度分量仅表示亮度信息,不包含颜色信息。如果不考虑亮度分量的信息,使用H和S两个分量就可以实现在各种光照条件下对车牌区域进行初步定位。
2.1.1 RGB模型到HSB模型的转换
普通的车牌图像都是RGB颜色模型,因此需要先将图像从RGB模型转换到HSV模型。
设r,g,b分别是一个像素的红、绿、蓝三个分量的值,它们的值是在0到1之间的实数,max为r,g,b中的最大值,min为这些值中的最小值[5]。则从RGB到HSV的转换公式可用公式表示:
2.1.2 车牌颜色阈值的选择
在我国,常见的车牌底色共有蓝色和黄色两种。在HSV颜色空间中使用H分量能识别出这两种颜色。黄色和蓝色的HSV阈值范围如表1所示。分别用于识别小型汽车和大型汽车的车牌区域。例如,通过蓝色模板的阈值对图片中的像素进行逐个匹配,当图片中的像素能匹配颜色模板的数值时,则置该像素的灰度值设为255,将不匹配的像素灰度值设为0。匹配完成后得到一张包含多个车牌信息的二值图。
2.1.3 基于Sobel边缘检测的车牌候选区方法
在二值图的基础上,通过边缘检测可以得到图片中的所有边缘的信息。本文采用Sobel算子对灰度图进行水平方向的边缘检测。该方法以某一个像素为中心点,对它的周围的八个点的像素值进行加权运算,判断该点是否处于极值状态,若该点处于极值状态,则该点为图像边缘。
车牌存在垂直方向与水平方向的边缘,通过边缘检测,能得到车牌字符的边缘信息。采用Sobel算子对水平方向进行求导,从而得到垂直方向的边缘信息。
2.2 车牌候选区的形态学和矫正操作
形态学运算包括腐蚀、膨胀、开运算和闭运算。腐蚀一种消除边界点,使边界向内部收缩的过程。膨胀是将与物体接触的所有背景点合并到该物体中,使边界向外部扩张的过程。先腐蚀后膨胀的过程称为开运算,用来消除小物体、在纤细点处分离物体、平滑较大物体的边界,同时并不明显改变其面积。先膨胀后腐蚀的过程称为闭运算,用来填充物体内细小空洞、连接邻近物体、平滑其边界,同时并不明显改变其面积。
为了实现更准确的车牌定位和截取,本文对基于颜色和Sobel边缘检测得到的车牌候选区域做闭运算处理,使原本不连续的车牌区域变成一块连同区域。
闭运算处理具体算法如下:
1)设有图像A,B是一个合适的结构元素,先利用公式(4)实现A被结构元素B膨胀,再利用公式(5)实现A对B进行腐蚀操作,这两步的目的是将目标周围的噪声去除。
2)为了将目标内部的噪声去除继续,利用B对A进行腐蚀操作,最后利用B对A进行膨胀操作[6]。
经过闭运算处理之后,车牌的区域能大致从图片中定位出来,但是定位车牌的角度可能会有较大的倾角,这一步需要对图片的倾斜角度进行矫正,以便获取角度正常的字符进行字符的识别处理。
对车牌候选区域进行倾斜矫正的步骤如下:
(1)首先,通过闭运算处理之后的二值图,逐个求出图中连通区域最大外接矩形,并计算最大外接矩形的倾斜角度。
(2)对倾斜角度在-5度到5度之间的图片,可以直接输出。
(3)对倾斜角度在5度到50度,或者-5度到-50度的车牌,需要先调整图片角度。
()调整角度后,判断车牌区域是否为平行四边形。
()如果不是平行四边形,则可以直接输出。
(6)如果是一个平行四边形的区域,再获取平行四边形三个顶点的坐标,通过仿射变换将平行四边形矫正成一个矩形,调整完成,将结果输出。
在输出结果时,需要将图片进行归一化处理,变成宽150像素,高40像素的图片。
2.4 基于SVM的车牌精确定位方法
由于基于颜色的定位会受到与车牌颜色相近的物体的干扰(如图1(a)所示),基于边缘检测的定位会受到汽车车灯等一些边缘信息与车牌相近的物体干扰(如图1(b)所示),影响最终的定位效果。因此引入支持向量机(SVM)来对上面粗选出的候选车牌区域进行判别。
支持向量机是一种基于统计学习理论的机器学习算法,其采用结构风险最小(Sructural Risk Minimization,简称SRM)原则替代传统的经验风险最小(Empirical Risk Minimization,简称ERM)原则进行分类,从而保证了算法具有较强的泛化能力。
SVM的训练过程等价于求解一个线性约束的二次规划问题,其目标是在训练样本集中寻找一个最优的超平面,将样本数据最大限度地分开,使两类数据之间的边界最大且分类误差最小,且能保证得到的解为全局最优解。
在本文中使用图像的直方图特征作为支持向量机的输入特征,输入的特征维度是190。直方图特征的特征量丰富,适用于支持向量机分类,有利于车牌的准确定位。
1)首先,将输入的图像进行二值化处理。
2)统计图像中一行元素中为1的数目,输入的图像共40行,得到40个数据.
3)再统计图像中一列元素中为1的数目,输入图像有150列,得到150个数据。
4)将第二步与第三步得到的这些数据作为SVM的输入特征,输入特征维度为190。
本文使用1000个车牌图像及500个非车牌图像对支持向量机进行训练。
3 实验结果
为了检测本文方法的有效性,本文分别选取了含有两个车牌和三个车牌的图像进行了多车牌定位测试。
经过颜色检测、边缘检测、形态学操作、车牌矫正与SVM筛选等步骤之后,对两个车牌的图像(图2)截取出车牌图片如图3所示。对三个车牌的图像(图4)截取出车牌图片如图5所示。实验表明,本文算法能对包含多车牌图像中车牌的定位的准确率能达到95%以上。
4 结束语
本文提出基于颜色检测、边缘检测和支持向量机(SVM)的多车牌定位综合方法,能从复杂背景中将待识别的多个车牌较准确的定位和截取。该方法首先使用颜色检测和Sobel边缘检测两种方法粗选车牌候选区域,其次对车牌候选区域进行形态学和倾斜矫正处理,最后提取车牌候选区域特征信息利用SVM精确定位车牌区域。实验结果表明,本文所用综合方法能排除背景干扰,多车牌定位效果和成功率较高。
摘要：为了提高多车牌定位和识别效率,本文提出基于颜色检测、边缘检测和支持向量机(SVM)的多车牌定位方法。首先使用颜色检测和Sobel边缘检测两种方法粗选车牌候选区域,其次对车牌候选区域进行形态学和倾斜矫正处理,最后提取车牌候选区域特征信息,采用SVM精确识别和定位车牌区域。实验结果表明,该方法能排除背景干扰,多车牌定位效果和成功率较高。
关键词：多车牌定位,颜色检测,边缘检测,支持向量机
参考文献
[1]郭捷,施鹏飞.基于颜色和纹理分析的车牌定位方法[J].中国图象图形学报,2002,7(5):472-476.
[2]李文举,梁德群,张旗,等.基于边缘颜色对的车牌定位新方法[J].计算机学报,2004,27(2):204-208.
[3]张燕,任安虎.多特征与BP神经网络车牌识别系统研究[J].科学技术与工程,2012,12(22):5644-5648.
[4]戴青云,余英林.一种基于小波与形态学的车牌图像分割方法[J].中国图象图形学报,2000,5(5):411-415.
[5]谭同德,王三刚.基于Open CV的车牌定位方法[J].计算机工程与设计,2013,8(34):2816-2820.
【多策略算法】推荐阅读：
蚁群算法的改进策略05-16
多路径算法06-09
多模型算法08-01
多目标遗传算法06-03
多方法混合算法06-20
多用户调度算法论文06-07
多Agent遗传算法06-09
多目标混合遗传算法06-25
雷达多目标跟踪算法09-11
多目标自适应遗传算法07-19