多目标中长期优化

2024-06-02

多目标中长期优化（精选十篇）

多目标中长期优化篇1

关键词：TD-LTE网络,网络规划,多目标,遗传算法

在无线网络规划中，基站是无线网络部署中最为灵活的单位，其价值占网络设备总投资的60%以上。科学的基站选址能够有效地扩大基站无线覆盖范围，吸收更多的用户和话务量，降低建设成本，提高收益，无论在技术实现上还是在降低整个网络的建设难度上都有十分重要的意义。

基站规划主要通过建立数学模型和设计符合该模型的求解算法，求出基站的位置和相应的配置。目前，已有人提出了一些相关的3G和4G的基站规划的模型和相应的求解算法。文献[1]提出了一种基于遗传算法的3G网络的规划方法，以建设成本和覆盖率为目标建立数学模型，采用加入局部搜索的遗传算法对模型进行求解。但是，该模型只适用于有呼吸效应的3G系统，对不存在呼吸效应的4G系统不再适用。文献[2]提出了一种采用增强型树算法和图论思想解决LTE网络中继基站规划的问题。但是，该模型只适合对已经建设好的LTE网络进行扩容，而不适合LTE网络的大规模规划。文献[3]从建设成本和覆盖率两个方面定性分析了4G网络基站选址问题。由于当时4G技术还没有成熟，所以建立的模型都是基于以前基站规划问题上考虑的没有结合到现有4G网络中的关键技术，而且其所设计算法没有针对具体问题。针对4G网络的同频干扰，文献[4]提出了4G网络规划中的基站功率分配模型。基于博弈论思想进行迭代从而求出每个基站的发射功率。但是，该模型只是考虑了网络规划中的功率因素，没有考虑网络的整体性能，不符合网络规划的长期发展原则。

基于对上述文献的研究，可以发现模型都是没有考虑到4G通信系统里面最重要的:小区之间的同频干扰[5]、子载波分配[6]、边缘用户速率要求[7]、系统吞吐量[8]等重要因素。所设计的算法没有考虑到4G基站的覆盖半径小、密度大、配置多所面临的计算量大的问题。为解决以上问题，提出一个基于TD-LTE网络系统的基站规划模型，并设计了一个适用于该模型的快速遗传算法。本文的规划模型以4G网络的同频干扰为主要因素综合考虑网络边缘用户的数据速率、小区的峰值吞吐量、用户峰值吞吐量、基站站址密度，并根据业务需求量把覆盖区域分为重点覆盖区域和普通覆盖区域，有效地提高资源利用率，并在模型的算法中加入局部搜索对过量重叠覆盖的基站进行调整，使得整个网络能够获得非常好的分布性。通过该算法快速求出以最少的建设成本，达到覆盖最大，并且同时满足小区边缘用户速率要求、站址密度和系统吞吐量的基站建设的位置和配置。并以某区域为例进行实验仿真，从建设成本、覆盖率、吞吐量和求解时间等方面验证了规划模型的合理性和算法的有效性。

1 站址规划模型

LTE的一大特点就是提供高速的数据服务，当语音为主要业务时，容量为上行受限的，而当数据业务为主时，容量转为下行受限，所以，仅考虑上行链路或者仅考虑下行链路，这样虽然计算简单，但体现不出LTE系统的优越性，特别是在城市中还普遍存在移动台切换基站的现象。因此，在建模时不仅考虑到上行，下行链路预算情况，移动台到基站的功率切换特性，同时考虑了4G网络的几个核心因素:同频干扰、RSRP、边缘速率、上行功率控制和下行功率分配等，充分利用已有2G、3G基站，在覆盖和容量之间达到一种平衡，建立能准确反映LTE基站位置和各个基站所用参数配置的数学模型。

1.1 基站位置和配置问题

假设一系列的候选基站建设地址为j∈{1,2，…，J}，在每个候选站址都最多只能建设一个基站。每个候选站址的基站建设费用为Cjk，跟该站址的位置和配置有关，当候选基站和已有的2G、3G基站共址时基站建设费用将会降低。其中，每一个候选站址建设时都可以选择不同的基站配置，例如:天线挂高、天线类型、扇区类型。这些基站配置共有K种，k∈{1,2，…，K}。为了便于数学计算，参考文献[9]将所要覆盖的地区进行栅格化，把一片地区分成许多小的方格块，在方格块的中央用一个测试点(TP)来代表这一片小区域的业务量和覆盖情况，一共有T个，t∈{1,2，…，T}。在这T个测试点中，又分类有:(1)普通测试点T1个，是普通区域的测试点;(2)重点覆盖点T2个。强制测试点是业务需求大的地方是需要重点覆盖的区域，例如:精品示范区、中央商务区、政务区、车站等。当该测试点达到所要求的最低的RSRP和移动台的最大发射功率时，认为该测试点被当前基站所覆盖。否则，认为该测试点没有被覆盖到。各个候选基站到测试点的路径损耗PL，可以通过传播模型提前算出来。

1.2 多目标站址规划模型

在无线网络规划中，基站建在哪里，如何配置，是至关重要的问题。同时要考虑到建设成本，尽量在成本较低的情况下达到较优的覆盖率[10]和小区容量。综合考虑这几个因素，现建立如下模型。

用yjk,t、xjk、wjk分别等于1或0来描述基站的建与否、测试点被覆盖与否、是否是边缘测试点。

将基站覆盖率、系统容量、链路预算三个目标联合考虑。并根据基站规划目标，建立目标函数

表示测试点TPt同一时刻只能被一个激活基站所覆盖。

式(5)表示候选基站yj没有被选中时，是不能够覆盖任何测试点的。

式(6)表示每个建设基站只能有一种配置。

式(7)在上行链路中用户发射功率总和要小于最大发射功率。

式(8)、式(9)表示在下行链路中，保证基站到达测试点后的信号强度达到最低要求。

式(10)、式(11)表示整个网络必须满足覆盖率和站址密度条件

式(12)表示子载波数不超过可用子载波数，η是用户启动系数。

式(13)～式(16)分别表示缘用户上行比特率、边缘用户下行比特率、小区下行平均比特率和小区上行比特率必须满足大于最小值。

假设下行每个子载波的功率为同频干扰系数为δ，子载波平均热噪声功率为σ[2]。nkb,t表示第t个测试点的用户分配到的RB数。所有基站都采用相同的时隙配置。R1、R2、R3、R4分别表示的是边缘用户最小上行比特率、边缘用户下行最小比特率、最小小区下行平均比特率和最小小区上行比特率。

2 用遗传算法求解

本文的模型求解算法采用遗传算法求解，由于模型比较复杂，候选解集太大，基站规划问题是一个NP-Hard问题，求出最优解的难度很大，因此使用局部搜索来搜出次优解。采用文献[11]的编码方法进行编码，为了加快算法的收敛速度，避免大幅度的波动，交叉方式采用经典的单点交叉法进行交叉。

算法求解主要步骤如下:

Step1:输入地理信息和网络建设指标;

Step2:设置种群规模Popsize、当前进化代数gen=0，最大进化代数Maxgen，交叉概率Pc和变异概率Pm;

Step3:对需要规划的区域进行站点和测试点位置的确定。计算各候选站点之间和候选站点到测试点的距离。各个候选站点的建设成本进行赋值;

Step4:设置权重w[1],w[2],w[3]，…，wN，初始化种群;

Step5:对种群进行交叉变异和局部搜索，利用权重向量进行选择、更新种群。gen=gen+1;

Step6:如果gen<Maxgen，转到Step4，否则结束。

在站址规划中，站间距是一个影响网络建设质量的重要因素，站间距太远或者太近都不好，为了专门解决站间距问题，在遗传算法中又加入局部搜索算法[12]。每一代杂交变异产生的新的个体都通过局部搜索进行局部调整。

局部搜索算法以解决添加或者减少激活基站的数量为主要目标，当基站的站址密度过大时需要去掉一些激活基站，当密度过小时增加一些激活基站。在添加激活基站的时候，首先要找到与激活基站距离最远的未激活基站，当该未激活基站激活后所覆盖的测试点数达到所要求的最小值时就添加该基站，否则寻找下一个距离最远的未激活基站。具体步骤如下:

Step1:计算激活基站所能够覆盖到的数目测试点的矩阵Q和基站单独覆盖到的测试点的数目的矩阵M;

Step2:求出Mj/Qj<0.75的所有激活基站，如果有则执行下一步，否则执行Step4;

Step3:剔除Mj/Qj最小的一个激活基站。回到Step1;

Step4:判断是否满足最小覆盖率，是就转到Step6，否则进行下一步;

Step5:寻找与激活基站相邻的未激活基站中距离最远的一个基站，并预测该基站激活后覆盖的测试点数目是否到达所要求的最小数，是则添加该基站，否则寻找下一个未激活基站。回到Step4;

Step6:结束。

3 仿真分析

本文以某区域案例进行实例分析。该区域建设面积为15.7 km[2]，测试点进行等间隔取点，每隔25 m取一个测试点代表该区域的用户，每个50 m放置一个候选站点。如图1所示，绿色的十字‘+’代表普通测试点，蓝色的实心点‘.’代表重点覆盖点，红色圆圈‘。’则代表候选站点。

初始化种群个体和种群规模。根据区域类型的站址密度ρ要求，和区域面积S估算出激活基站的数目ρS。假如基站j被激活，从基站配置集合里面给它随机选择一种配置。种群规模为50，最大进化代数为50交叉概率pc和变异概率pm的设置和参考文献[13]一样。

当种群为50，没有局部搜索时，运行50代的时间为192.79 s，平均每代运行时间3.86 s。添加局部搜索后，种群规模50，运行50代的时间为917.522 761 s，平均每代运行时间为19.81 s。可以得到一系列覆盖在95%以上的有效解。分别取R1=512 Kb/s;R2=4 Mb/s;R3=8 Mb/s;R4=20 Mb/s。N=1 200是系统子载波总数，噪声功率为σ[2]=-105 dBm，同频干扰系数δ=0.2，用户激活系数η=0.5。

算法使用局部搜索的具有代表性的7个有效解表1所示。从表中可以看出建设基站的数目与覆盖率并不是简单的成比例关系，而且还和小区吞吐量有关，是一个相互制约的关系。表2给出了算法没有使用局部搜索时的6个有效解。从表2可以看出，算法没有使用局部搜索算法时的建设费用比使用局部搜索的算法的费用要明显多大很多，而且小区容量并没有明显的增加。这是由于没有使用局部搜索是算法的求解速度大大减低，还没有求得最优解的原因。局部搜索不但提高了算法的效率，而且还改善了网络的分布性。

图2和图3分别是算法不使用局部搜索和使用局部搜索的一个有效解的典型代表。由图可以得到，不使用局部搜索时的基站有很多的重复覆盖区，分布性非常的差，这都是算法没有收敛造成的，不使用局部搜索需要增加运行时间才能够求得较好的解。而算法使用局部搜索时能够快速地求出一个覆盖、容量和建设成本达到均衡的完美的解。

4 总结

基于多目标优化的供应商绩效评估篇2

基于多目标优化的供应商绩效评估

考虑到供应商绩效评估指标体系的多目标性,给出了一种基于可行域为有限集的多目标问题的优序解法和改进优序法,快速有效地对评估方案进行排序为决策提供依据.

作者：徐国平宗蓓华 XU Guo-ping ZONG Bei-hua 作者单位：徐国平,XU Guo-ping(上海海事大学,交通运输学院,上海,35;宁波大学,海运学院,宁波,315211)

宗蓓华,ZONG Bei-hua(上海海事大学,交通运输学院,上海,200135)

刊名：系统管理学报 ISTIC PKU英文刊名：JOURNAL OF SYSTEMS & MANAGEMENT 年，卷(期)： 17(2) 分类号：O227 关键词：绩效评估优序法多目标优化

盾构刀盘多目标优化设计篇3

关键词：盾构刀盘；优化设计

盾构机是一种地下隧道挖掘专用的大型、成套施工设备，其主要优点有质优、安全、经济效益高、开挖快、有利环境保护、降低劳动强度等，在城市施工、隧道挖掘中得到广泛应用。盾构机在施工过程中可能遇到各种不同的地质环境，从粘土、与你、砂层到软岩、硬岩等。在盾构机使用过程中，其关键部位就是盾构刀盘。盾構刀盘质量好坏直接关系到盾构机的工作效率、使用寿命和工程的成败。因此，盾构刀盘的设计和地质工程有着紧密的关系，不同的地质类型要选择不同的刀盘结构，进而盾构刀盘的设计也应该采取多目标优化设计，提高盾构机的工作效率。

1.盾构机刀盘结构形式

盾构刀盘主要具备稳定掌子面、搅拌渣土、挖掘三大功能。观察刀盘的结构，主要由辐条式和面板是两种，具体使用哪一种应该根据现场的施工条件和地质条件决定。泥水盾构主要使用面板是刀盘，如果是土压平衡盾构则考虑采用辐条式或者面板式，当然，辐条式刀盘明显优于面板式。对于土压平衡盾构来说，使用面板式的盾构刀盘时，当泥土流经刀盘面板的时候，泥土可能进入土仓开口，进而导致盾构机挖掘的过程中舱内土压和挖掘面土压之间产生压力，导致挖掘面不易控制。而辐条式的刀盘结构辐条较少，切削下来的土体可能直接进入到设备土仓当中，没有压力损失，而且在辐条后面设有搅拌的叶片，在搅拌砂土过程中可以流畅工作。所以，辐条式的刀盘比面板式刀盘的适应性强。但是辐条式的刀盘不能安装滚刀，这也是其缺陷之一，在风化后的岩石或者软硬质地不均的地方使用，还是应该选择面板式刀盘。

2.盾构刀盘结构设计

2.1开口率设计

盾构刀盘的开口率是面板式刀盘开口部分的面积和刀盘面积的比率，其实质上指的是刀盘切削下来的碎土要经过刀盘开口槽进入土仓。因此，在进行刀盘开口设计的时候，必须要考虑到盾构机使用的土壤环境、开挖面的稳定性、开挖效率，并以此作为根据选择尺寸、形状及其他条件相符的刀盘。例如对水泥盾构的时候，盾构刀盘的开口率一般设计在10%-30%之间；对土压平衡盾构的刀盘设计，开口率较小；对于粘性土质盾构来说，刀盘的开口率应该加大；对于较容易坍塌的地质结构进行盾构的时候，刀盘的开口率必须慎重选择。此外，盾构刀盘的开口位置要紧靠刀盘的中心，避免工作室切削下来的渣土掉落在中心部位，造成运行不畅。

2.2泡沫管的设计

实施土压平衡盾构主要使用于土质相对粘稠的施工地点，如果施工地点的含沙量超过限度，泥土的可塑性降低，而且土仓内的土会因为凝固而被压得紧密，仓内的土渣就无法排除。此时，可以采用向土仓内注泡沫或水、膨润土的方法进行强制性搅拌，让沙质土软化。使用泡沫可以有效控制土体塑流性，还可以润滑盾构刀盘、刀具、螺旋输送机等，保持盾构机的流畅运行，提高其性能和作用。所以，泡沫管可以有效防止刀盘运转过程中，泥土形成泥饼，通常情况下，泡沫管注入口设置在刀盘的中心部位或者刀盘的背面，通过旋转接头将泡沫引入，刀盘上布置的泡沫管有两种，一种是外置式，一种是内置式，外置式清理相对容易，但是与土壤直接摩擦，比较容易损坏，内置式清理比较麻烦，但是不宜损坏，目前盾构机多使用的是内置式。从盾构刀盘多目标设计的角度来说，做好泡沫管布置同样具有重要作用。

2.3刀盘倒角和变滚刀设计

盾构机刀盘的切削直径最终是由安装在刀盘外周的刀具实现的。所以，在盾构机进入土层的时候，其运行时通过周边的刮刀实现的。在土质坚硬或者岩石地质进行盾构的时候，主要由边滚刀实现，在土质较软的区域进行盾构的时候，主要由周边的刮刀实现。边滚刀的径向和刀盘的面板必须形成一定的角度，刀盘的形状在边缘处要流出一定的倾斜角。刀盘在运转的过程中，滚刀靠近刀盘的边缘，其旋转速度要比中心部位滚到旋转速度快，而且切削岩层的直线距离很长。所以，边滚刀的磨损要远远大于中心滚刀，因此在进行设计的时候，要增加边滚刀数量。

3.刀盘多目标的优化设计

刀盘设计之前，要预先建立相应的数学模型，将选取钢材的厚度作为设计中的主要变量，选择刀盘最大变形和质量作为函数，进行整体优化，其目标就是使刀盘最大变形量和质量实现最小。当然，进行多目标优化分析的时候，目标函数的级别会影响到设计方案的优化，并以此来确定最佳的设计方案。最优的设计方案选择原则在尽量满足优化目标的前提下进行，优化效果最明显的方案就是盾构刀盘需要选择的方案。

盾构刀盘优化设计流程，先将盾构机刀盘模型参数化，并按照典型的工况条件对刀盘进行静力分析，并将静力分析的结果和设计参数作为边界条件，对参数化的模型进行不断优化直至求出最佳解，将优化结果返回模型，变更并确定最终设计方案。通过这个方式进行盾构机刀盘校核，即使失败也可以通过改变设计参数改变刀盘模型的结构尺寸，减少重复建模的工作量。

4.总结

盾构刀盘进行设计的时候，要考虑到刀盘的使用范围和现实的土质情况，全面考虑各种问题之后，全面优化盾构刀盘优化设计。进行设计的时候可以根据相关参数选择获取设计方案，提高设计分析思路，为盾构刀盘设计提供新的方法和思路。

参考文献：

[1]黄德中.超大直径土压平衡盾构施工土体改良试验研究[J].现代隧道技术.2011（04）

[2]蒲毅，刘建琴，郭伟，裴瑞英.土压平衡盾构机刀盘刀具布置方法研究[J].机械工程学报. 2011（15）

[3]王锡军.无水砂卵石地层盾构施工[J].建筑技术.2011（03）

[4]李建峰，王旭，王凯，周喜.盾构刀盘中心区域磨损研究[J].现代隧道技术.2011（01）

[5]何峰，李小岗，孙善辉.北京铁路地下直径线泥水盾构刀盘、刀具适应性分析[J].中国工程科学. 2010（12）

负荷建模的多目标优化篇4

负荷建模是电力系统中公认的一个难题[1,2,3]。当模型结构确定以后,参数辨识就成为负荷建模的核心,其实质是个数值优化的过程。传统的优化方法很多,但都存在一些缺点:需要给定搜索的初始值,并且对目标函数要求苛刻,不仅有单峰要求,有的还要求存在一阶导数甚至二阶导数。而高阶非线性电力系统负荷模型的目标函数往往很难写出其解析关系,解空间也相当复杂,不仅有多个极值点,且极值点之间差异细微。所以使用传统优化方法对负荷模型进行参数辨识时,辨识结果常呈现出很大的分散性,这在很大程度上降低了辨识结果的可靠性,严重阻碍了其在工程实践中的应用。

近年来,随着优化理论和智能控制理论的进展,许多新算法在负荷参数辨识领域获得广泛应用,例如遗传算法(GA)、粒子群(PSO)算法等[4,5]。但现有用于负荷参数辨识的算法都存在一个共同缺陷,即只能辨识出一组参数,而负荷模型参数是不唯一的,这样辨识出的参数可能与实际情况不相符。

本文对传统负荷参数辨识的目标函数进行改进,将现有负荷模型参数辨识的单目标优化问题转化成多目标优化问题,并应用伪并行改进强度Pareto进化算法(SPEA2)的多目标优化算法实现负荷模型参数辨识,可以同时辨识出负荷模型的多组参数,解决了以前算法只能辨识出一组参数的问题,决策者可根据实际侧重目标的不同在Pareto最优解集中进行选择,力求克服目前困扰负荷建模及其参数辨识中收敛速度慢、易发散等问题。最后,利用本文提出的负荷建模理论和方法对上海地区的负荷进行实测建模,结果表明了本文建模策略的可行性。

1 负荷模型结构和参数辨识

1.1 模型结构分析

考虑配电网和无功补偿的负荷模型结构如图1所示[6],模型中设置了一个虚拟母线,虚拟母线(电压为 $\dot{V}_{S})$ 与实际负荷母线(电压为 $\dot{V}_{L})$ 之间是输配电网络的等值阻抗。该模型的参数如下:①感应电动机参数:Rs,Xs,Xm,Rr,Xr,A,B,H;②静态负荷参数:Zp,Ip,Pp,Zq,Iq,Pq;③无功补偿系统参数C;④等值电动机的初始有功在总有功中所占比例Kp;⑤感应电动机的额定初始负载率Kf。

1.2 辨识策略和参数初始范围的选取

参数辨识可采取辨识全部参数和辨识部分参数2种策略。研究表明,对电动机特性影响较大的参数主要有电动机定子电抗、电动机比例、电动机负载率和惯性时间常数[7]。由此,确定需重点辨识的参数为Xs,Kf,Kp,H,而其他参数则可以取典型值。

参数搜索范围的选取对辨识结果具有较大影响。本文在参数的初始空间选取上,当事先知道参数典型值时,将参数典型值放大和缩小相同比例得到参数的搜索范围,此范围必须尽量把参数实际可能取得的最大值和最小值包括在内,而对于参数无典型值时,比如感应电动机比例Kp,则可以结合参数的历史数据,按照参数可能出现的实际最大值和最小值作为参数的上下限。

1.3 目标函数的选取

参数辨识过程实质上是个数值优化的过程,进行参数优化需要选取一定的目标函数。目前,负荷建模参数辨识的目标函数主要有以下3种。

1)以有功和无功的绝对偏差平方和的均方根作为优化目标:

$\begin{array}{l} J = \\ \sqrt{\frac{1}{n} \sum_{k = 1}^{n} [(Ρ_{Μ} (k) - Ρ (k))^{2} + (Q_{Μ} (k) - Q (k))^{2}]} (1) \end{array}$

式中:n为数据长度;P(k),Q(k)为模型响应;PM(k),QM(k)为实测响应。

对于该目标函数,当有功和无功在数值上相差较大时,该目标会导致参数辨识的不合理。如果有功在数值上远大于无功,那么目标函数J的最小化主要取决于有功的拟合程度,此时可能出现目标函数J达到最小值、但无功拟合的效果较差;反之,如果无功在数值上远大于有功,则可能出现目标函数J达到最小值,但有功拟合的效果较差。

2)以有功和无功的相对偏差平方和的均方根作为优化目标:

$\begin{array}{l} J = \\ \sqrt{\frac{1}{n} \sum_{k = 1}^{n} [(\frac{Ρ_{Μ} (k) - Ρ (k)}{Ρ (k)})^{2} + (\frac{Q_{Μ} (k) - Q (k)}{Q (k)})^{2} 2 〗} (2) \end{array}$

该目标函数克服了目标函数1存在的缺陷,但如果以此作为目标函数,应用现有的算法进行参数优化时只能得到一组最优解,无法解决辨识参数不唯一性的问题。

3)以有功和无功绝对偏差平方和的加权均方根作为优化目标:

$\begin{array}{l} J = \\ \sqrt{\frac{1}{n} \sum_{k = 1}^{n} ω (k) [(Ρ_{Μ} (k) - Ρ (k))^{2} + (Q_{Μ} (k) - Q (k))^{2}]} (3) \end{array}$

该目标函数中ω(k)的选择比较困难且较盲目,应用现有算法对该目标函数进行参数优化时只能得到一组最优解,也无法解决辨识参数不唯一性的问题。

为克服以上3个目标函数存在的缺陷,本文提出一种多目标优化的模型,同时最小化有功和无功的相对偏差,模型如下:

${\begin{cases} \min (J_{1} ‚ J_{2}) \\ J_{1} = \frac{1}{n} \sum_{k = 1}^{n} (\frac{Ρ_{Μ} (k) - Ρ (k)}{Ρ (k)})^{2} \\ J_{2} = \frac{1}{n} \sum_{k = 1}^{n} (\frac{Q_{Μ} (k) - Q (k)}{Q (k)})^{2} \end{cases} (4)$

该模型既可以避免目标函数3中ω(k)选择的困难和盲目性,又可解决参数不唯一的问题,通过后面的算法可以辨识出负荷模型的多组参数,解决了以前算法只能辨识出一组参数的问题。该模型是一个多目标优化问题,现有单目标优化算法不再适用,因此,针对该多目标优化问题需要采用一种多目标优化算法。

2 参数辨识算法

当前电力系统研究中所要考虑的因素越来越多,多目标优化算法越来越受到重视。文献[5]将多目标算法应用于无功补偿的最优配置问题。文献[8]将多目标优化算法应用于配电系统的多目标设计,取得了很好的效果。多目标GA是用来解决多目标优化问题的一种进化算法,其核心就是协调各目标函数之间的关系,找出使各目标函数能尽量达到比较大(或比较小)的最优解集。

2.1 Pareto最优解

多目标优化问题可以用函数f来定义,该函数把决策向量X映射到目标向量Y,其数学描述为:

${\begin{cases} \min Y = f (X) = [f_{1} (X), f_{2} (X), \dots, f_{n} (X)]^{Τ} \\ s . t . g (X) = [g_{1} (X), g_{2} (X), \dots, g_{n} (X)]^{Τ} \leq 0 \end{cases} (5)$

式中:X=,由m个决策变量xi构成;Y由n个需同时优化的目标fi(X)构成;约束g(X)由n个等式、不等式gi(X)≤0构成。

上述多目标优化问题的各目标往往处于冲突状态,因而不存在使所有目标同时达到最优的绝对最优解,只能获得满意解即Pareto解。Pareto前沿是指多目标优化问题中一组Pareto最优解的集合分布情况,其构成完全依赖于解与解之间存在的Pareto支配关系。对于上述最小化问题,如果决策向量空间X中的任意2个解Xi和Xj满足下式:

${\begin{cases} f_{a} (X_{i}) \leq f_{a} (X_{j}) \forall a \in {1, 2, \dots, n} \\ f_{b} (X_{i}) < f_{b} (X_{j}) \exists b \in {1, 2, \dots, n} \end{cases} (6)$

则称Xi支配Xj,记为Xi>Xj。对解Xi∈X而言,若不存在解Xj∈X-{Xi},使得Xj支配Xi,则称Xi为一个非支配解或Pareto最优解,所有Pareto最优解构成Pareto前沿或Pareto最优解集合。

2.2SPEA2

强度Pareto进化算法(SPEA)[9]是一种相对较新的技术,采用协同进化规则的适应度分配策略和基于Pareto支配关系的小生境机制,与其他多目标进化算法相比有更强的优化能力,而且需要设置的参数较少,是目前公认比较好的多目标问题优化方法,但存在适应度分配不精确以及多样性差等缺点。针对上述缺点,SPEA2[10]对SPEA进行了改进,成功地把精确的适应度分配策略、密度估计技术、增强截断方法结合在一起,收敛速度加快,Pareto最优解分布均匀,在性能上比SPEA有较大程度提高,因而已成为一种较有代表性的多目标进化算法[10]。

2.3 并行GA

并行GA[11]与常规GA的主要差别在于:它存在同时进化的多个种群,对多个种群轮流进行遗传操作,这样能够提高算法的性能和效率,有效克服单种群算法的早熟现象。迁移策略是并行GA引入了一个新算子,它可加快较好个体在群体中的传播,提高收敛速度和解的精度,与单种群相比可用较小的计算量达到同等性能。

本文将SPEA2与并行GA结合,在单一处理器上以串行(伪并行)的方式进行并行计算。该算法可以在多台计算机上并行计算,为网格平台下的负荷建模做了前期准备。

2.4基于伪并行SPEA2的参数辨识

负荷的模型结构有多种,具体采用哪种结构可以根据实际情况选择,模型选定之后,采用前面介绍的算法进行参数辨识。基于伪并行SPEA2算法的动态负荷模型结构选择与参数估计步骤如下:

1)编码。视具体工程应用背景确定,对于负荷建模中的参数辨识应采用实数编码的方式。

2)初始种群的产生。取5个子种群,子种群的规模依次为50,40,30,50,30,随机产生各子种群的个体。

3)遗传操作。每个子种群采用SPEA2进行遗传操作,SPEA2的参数设置为:①选择:联赛选择,选择规模为2;②重组:实值重组,重组率为0.9,为了提高算法的搜索能力,5个子种群采用不同的方式,依次为离散重组、中间重组、线性重组、离散重组、中间重组;③变异:均匀变异,变异率为0.1。各子种群的变异步长依次为:0.100,0.030,0.010,0.003,0.001。

4)迁移策略。子群体间采用网络拓扑,按照排列比例来选择迁移个体,每运行8代迁移1次,迁移率为0.1。

5)迭代次数加1,返回步骤3,直至达到最大迭代次数为止,大种群中的所有非支配解即构成Pareto最优解集。

3 算例分析

上海地区4个典型站点的电压扰动试验在低压侧进行,负荷模型的参数是根据低压侧量测结果辨识出来的,因此在仿真分析中需考虑配电网阻抗的影响,配电网的阻抗RD+jXD取中国电力科学研究院推荐的参数0.026 5+j0.175 1。下面以西郊站为例分别介绍2种参数辨识策略下负荷模型的参数辨识结果。

3.1 辨识部分参数时的结果分析

根据上面的分析,辨识的部分参数为Xs,Kp,Kf,H。待辨识参数的搜索范围为:Xs为0.072～0.200;Kp为0.1～0.8;Kf为0.25～0.80;H为0.05～3.00;Zp为0～1.0;Ip为-5.0～5.0;Zq为-5.0～5.0;Iq为0～1.0。其他参数采用BPA中的典型值。静态负荷采用40%恒阻抗+60%恒功率的多项式模型。利用上海地区西郊站的电压扰动数据进行负荷参数辨识,运行得到的Pareto前沿如图2所示。

从图2可以看出,伪并行SPEA2求得的Pareto最优解集具有良好的多样性,并且分布均匀。由多目标问题的定义可知,一个非支配解至少存在一个目标函数值优于所有其他解的该目标函数值。因此,在2个目标的多目标优化问题中,可行解框图中所有非支配解形成一条凸向原点的曲线,即所有非支配解的有功相对偏差与无功相对偏差成反比。伪并行SPEA2一次运行可以得到多个Pareto最优解,解决了参数不唯一的问题,便于决策者根据实际情况进行选择。表1列出了图2中部分具有代表性的Pareto最优解。

实际负荷模型参数只有一个,工程中也只需要一个,所以如何从多目标优化获得的多个负荷模型参数中选取应用参数是一个重要问题。实际决策中,当侧重于拟合有功时,决策者可以在有功偏差较小的Pareto解集中进行选择;当侧重于拟合无功时,可以在无功偏差较小的Pareto解集中进行选择;若没有特别的侧重目标时,图2所示的无偏最优解(对应表1中解2)很好地协调了有功偏差与无功偏差的关系,2种偏差都比较小,可以选为最优解。

解2对应的拟合曲线与传统单目标算法(采用有功、无功相对偏差平方和的均方根作为优化目标)所得拟合曲线的对比如图3所示。可以看出,本文算法所得的结果更优,辨识效果更好。

此外,从表1可以看出:

1)各解对应感应电动机的定子电抗比中国电力科学研究院新推荐的典型值0.18稍小,比以前使用的0.295更是小得多。等效定子电抗下降的可能原因是目前各电网不断采用定子电抗较小的新型电动机。

2)各解对应的初始负载率辨识结果比典型值0.468大,但都在正常范围之内。国内大型感应电动机初始负载率的典型值为0.55,但随着感应电动机制造工艺以及效率的提高,初始负载率也有增大的趋势,逐渐向国外靠拢,如IEEE负荷建模工作组推荐的参数一般为0.6～0.8,所以辨识出的感应电动机的初始负载率是合理的。

3.2 辨识全部参数时的结果分析

仍然用西郊站的电压扰动数据,进行全部负荷参数辨识,表2列出了几组典型的Pareto最优解。对比表1与表2可知,辨识全部参数时,有功与无功的偏差会有所减小,但所需时间会大大增加,因此,如果在单机上以伪并行的方式运行本文算法,建议采用辨识部分参数的策略,这样可降低程序运行时间,精度也可满足要求,如果在网格平台上运行本文算法,建议采用辨识全部参数的策略,这样可提高辨识的准确度。观察表2可知,虽然各解对J1和J2的偏好不同,但总体而言,各解有功和无功偏差均较小,说明了本文建模方法的准确性和可行性。

4 结语

本文提出了多目标的负荷建模目标函数,将现有负荷模型参数辨识的单目标优化问题转化成多目标优化问题,并应用伪并行SPEA2进行多目标参数辨识,提出负荷模型参数Pareto最优解的概念,一次运行可以得到多个Pareto最优解,便于决策者根据不同的侧重目标选择最终的最优解,为负荷建模及其参数辨识提供了一条新思路。

参考文献

[1]冯士刚,艾芊.一种谐波负荷建模的新方法.电力系统自动化,2007,31(17):26-31.FENG Shigang,AI Qian.A new approach for harmonicmodeling of electric loads.Automation of Electric PowerSystems,2007,31(17):26-31.

[2]鞠平,谢会玲,陈谦.电力负荷建模研究的发展趋势.电力系统自动化,2007,31(2):1-4,64.JUPing,XIE Huiling,CHEN Qian.The researchtendencies ofelectric load modeling.Automation of Electric Power Systems,2007,31(2):1-4,64.

[3]AI Qian,GU Danzhen,CHEN Chen.New load modelingapproaches based on field tests for fast transient stabilitycalculations.IEEE Trans on Power Systems,2006,21(4):1864-1873.

[4]程颖,鞠平,吴峰.负荷模型参数辨识的粒子群优化法及其与基因算法比较.电力系统自动化,2003,27(11):25-29.CHENG Ying,JU Ping,WU Feng.PS algorithm in loadparameter identification and its comparison with geneticalgorithm.Automation of Electric Power Systems,2003,27(11):25-29.

[5]GARDEL P,BARAN B,ESTIGARRIBI A H,et al.Multiobjective reactive power compensation with an ant colonyopti mization algorithm//Proceedings of the 8th IEEInternational Conference on AC and DC Power Transmission,March 28-31,2006,London,UK:276-280.

[6]鞠平,何孝军,黄丽,等.广义电力负荷的模型结构与参数确定.电力系统自动化,2006,30(23):11-13.JU Ping,HE Xiaojun,HUANG Li,et al.Model structures andparameter esti mation of generalized loads.Automation ofElectric Power Systems,2006,30(23):11-13.

[7]石景海,贺仁睦.动态负荷模型多曲线拟合参数辨识.电力系统自动化,2003,27(24):18-22.SHI Jinghai,HE Renmu.Parameter identification of dynamicload model using multi-curve fitting method.Automation ofElectric Power Systems,2003,27(24):18-22.

[8]MENDOZA F,BERNAL-AGUSTI N J L,DOMI NGUEZ-NAVARRO J A.NSGA and SPEA applied to multiobjectivedesign of power distribution systems.IEEE Trans on PowerSystems,2006,21(4):1938-1945.

[9]ZITZLER E,THIELE L.Multi-objective evolutionaryalgorithm comparative case study and the strength Paretoapproach.IEEE Trans on Evolutionary Computation,1999,3(4):257-271.

[10]ZITZLER E,LAUMANNS M,THIELE L.SPEA2:i mproving the strength Pareto evolutionary algorithmfor multi-objective opti mization//Proceedings of the EvolutionaryMethods for Design,Opti mization and Control withApplication to Industrial Problems,September 19-21,2002,Athens,Greece:19-26.

多目标中长期优化篇5

基于多目标模糊优化方法的无人机航迹规划

针对以雷达威胁和燃油消耗为多目标的无人机航迹规划问题,采用多目标模糊优化方法建立航迹性能指标,并利用启发式A*搜索算法,提出基于动态权值的启发函数方法.最后结合实际算例,在基于Voronoi图的.状态空间内搜索航迹,验证了采用多目标模糊优化和启发式搜索方法进行航迹规划具有合理性和有效性.

作者：冯慧屈香菊 FENG Hui QU Xiang-ju 作者单位：北京航空航天大学,航空科学与工程学院,北京,100083刊名：飞行力学 ISTIC PKU英文刊名：FLIGHT DYNAMICS年，卷(期)：25(2)分类号：V249.1关键词：无人机航迹规划多目标模糊优化 A*搜索算法 Voronoi图

暖通空调系统的多目标优化模型篇6

关键词：暖通空调系统；节能；优化；模型

引言：在现代社会，人们一天中几乎有半天甚至更多时间是待在室内的，因此，利用空调维持室内环境的健康是非常重要的。据统计，空调系统在公用建筑中的能耗超过了60%。因此，暖通空调系统的能效问题为学者们关注的重点问题。暖通空调系统的运行是一个多角度的问题，因此脱离室内空气品质的控制，仅仅将能耗减到最小是不可取的。最佳的控制方法策略是将室内热舒适性维持在一个可以接受的范围内的情况下去考虑系统的能耗。本文将在综合考虑经济性和热舒适性的基础上来提出暖通空调系统的性能最优化模型，能够使暖通空调系统在运行上减少能耗、提高效率以及保持居住环境的舒适性，从而暖通空调系统的性能可以大大提高。

一、数据类型

公用建筑中暖通空调系统的总能耗主要由四个部分组成：空气处理系统的能耗，水泵的能耗，供回风系统的能耗，以及末端设备的再热。在这里，由于热水、照明以及家电能耗在优化过程中的变化并不明显，因此不考虑这部分的能耗。暖通空调系统的所有能耗可以由下式1得出：ETotal=EHeat+EFan+EPump+QReheat （1）

空气处理系统、风机和水泵的能耗可以由开始装在系统中的设备进行校准，因此末端设备的再热负荷导致了所有的能耗。通过调节阀门使热水流与舒适区的实际要求相匹配。热负荷可以由下式2计算得出：QReheat=cm（TVAV_EAT-TVAV_BAT）

QReheat=cm（TVAV_EAT-TVAV_BAT）（2）

在此实验中，用于热舒适性的标准估值由室内温度和湿度来确定，基于管理要求，室温应该维持在21℃～22℃之间室内，湿度范围要在30%～60%。而实际上系统有时会运行在这个范围之外，并且会使人不舒适。因此，如果要使室内这种不舒适性不会发生，则要将室内温度和湿度作为限定条件。从而，在本研究中，优化算法中的补偿函数由限制条件来进行确定。

二、优化方法

本研究优化框架如图1所示。

三、暖通空调系统模型

根据以上讨论，建立最优化问题的双向模型，最终的优化可由下式3得出：min（yEnergy （t）） xSAT_Spt，xSASP_Spt

边界条件为：yEnergy （t）=f（XSAT-SPt，XSASP-SPt，XLoad（t），）XLoad（t-1），XCHWC-vlv，XSA-Hund，XSOL-Horz，XOA-Humd，XOA-TEMP

四、结论

本文讨论了一种基于数据处理的暖通空调系统优化方法。首先，研究实验数据并选择一些重要的参数作为输入。然后讨论若干数据挖掘算法，选择适当的算法建立优化模型，将其作为输出。从边界条件入手，建立最优化问题的双向模型，从而在暖通空调系统上得到大量的节能。

参考文献：

[1] W. Huang， M. Zaheeruddin and S. H. Cho。Dynamic simulation of energy management control functions for HVAC systems in buildings[J]，Energy Conversion and Management，2006， 47 （7-8）： 926-943。

多目标中长期优化篇7

结构拓扑优化设计是优化设计领域最富有生命力、最具有发展前景的一个研究方向[1,2]。人们需要在结构优化设计领域中,寻找优化设计的最优方案或较优方案来解决单目标优化设计问题。然而在实际工程设计问题中,设计方案存在多项设计指标,期望其各指标达到最优,而这些指标往往难以协调,需要权衡多个目标来解决多目标问题,因此研究寻求合理解决多目标的拓扑优化优化问题的方法具有更重要的意义。

结构拓扑优化中以多工况静态柔度最小化及多阶动态频率最大化为目标函数构造问题是典型的多目标优化问题[3]。人们多引入数学规划来对多个目标进行综合权衡进而将多目标转化为单个目标来构造目标函数,最终建立优化数学模型。孙晓辉等[4]引入数学规划法相关理论建立了5种不同的目标函数,并得到既能提高动态振动固有频率又能提高结构刚度的拓扑构型。范文杰等[5]建立以折衷规划法定义柔度并结合平均频率特征值公式构建的多目标优化目标函数,并将函数应用于汽车车架结构的设计中,既提高了动态振动频率,又提高了结构刚度。占金青等[3]分别定义静态多工况刚度和动态特征值为两个分目标的目标函数,并以综合柔度最小化和平均频率特征值最大化为目标对算例进行多目标优化,验证其提出该数学模型的可行性。刘林华等[6]将折衷规划法与理想点法结合起来,分别以综合柔度、频率特征值最优化构造了目标函数,并以某越野车车架为例验证了多目标拓扑优化目标函数构建方法的正确性。显然,如何建立合理的目标函数是实现结构多目标优化的关键。本文将平均距离理论引入结构多目标优化,归纳了将多种多目标转化为单目标的方法,并运用于拓扑优化来构建目标函数,对车架控制臂进行拓扑优化;针对拓扑优化结果,验证该优化方法的可行性,为多目标结构优化设计提供了新的设计思路。

1 广义平均距离公式

Ma等[7]在1995年提出的平均特征值公式很好地解决结构固有频率振荡问题,根据其平均特征值理念,提出广义平均距离公式概念:

其中,(i=1,2,…,m)是各个单目标数值,ni(i=1,2,…,m)为指定的单目标,wi(i=1,2,…,M)为加权系数(各目标对目标函数的贡献度),(i=1,2,…,m)为给定的参数,p为给定的权力值,y0和α为任意常数(仅用于一些目标函数的物理意义和目标函数尺寸的调整)。

所构建目标函数的意义在于,将多个单一目标与给定参数的距离之和转化为平均值y来定义评价函数,用来表征各目标加权距离的平均值,可以用取得平均值最大或最小的方法来实现各目标离指定点加权距离的最大化或最小化。

当p=1,2,… 时,以目标函数最小化为例展开研究:

(1)当y0=0、α=1、p=2、wi=1时,目标函数的意义为所有单一目标函数的相对距离之和,表达式变为。使其最小化就意味着单目标的值尽可能接近指定值,也就是最短距离法;反之使y最大化就是使单目标值尽可能远离指定值。

(2)当

时,目标函数的意义是每个单一目标函数值与0的加权距离之和,表达式变为。使其最小化是使单目标值尽可能趋于0,也就是采用线性加权法;反之,使其最大化就是使单目标值尽可能趋于无穷大。

(3)当

时,采用折中规划法,目标函数变为。 ① 当时,目标函数的意义为所有单一目标的相对加权距离之和,即Manhattan距离,目标函数为。使其最小化就是使得单一目标值趋近各自的,反之,则远离。②当

时,目标函数的意义在于加权几何距离,即Euclidean距离,目标函数为

。使其最小化,就是使得单一目标值更快地趋近各自的期望值;反之,则远离。

当p=-1,-2,…时,以实现目标函数最大化为例展开研究:

(1)当

时,此公式变为平均频率特征值公式,即,其中λ为频率特征值。使其最大化就是让各目标特征值尽量趋近给定特征值λ0;反之则远离。

(2)当p=-2时,目标函数为

。使其最大化就是让各目标值更快地趋近于;反之,则远离。

2 平均距离公式在结构多目标拓扑优化中的应用

在目前的结构多目标拓扑优化问题中,多工况柔度与多阶动态频率都属于多目标问题,因此两个多目标问题都应用平均距离公式来解决。

2.1 静态多工况刚度拓扑优化数学模型

不同工况对应的最优拓扑结构不同,各工况对应的多刚度难以同时达到最优,因此,结合平均距离公式,以多工况下刚度最大化问题转化为柔度最小化的结构优化数学模型如下:

式中,C(ρ)为结构平均柔度值;m为工况总数;wi为第i个工况柔度距离p次方的权重系数;ρ1,ρ2,…,ρn为拓扑优化设计变量,即通过变密度法得到的结构材料密度;L为单元总数;C为结构的柔度,F为受力;K为结构的刚度矩阵;U为位移向量;V0为设计区域原体积;V为优化后的体积;Δ为体积分数。

为了使各目标值越来越小,本文用两种方法表示: 一种方法是使该目标函数最小, 即min C(ρ),当p=1,2,… 时Ci0取Cimin,即单工况得到的柔度最小值,使其越接近最小值;另一种方法是使目标函数最大,即max C(ρ),当p=-1,-2,… 时,Ci0取Cimin,即单工况柔度最小,使其尽量靠近最小值。因此产生两类平均柔度数学模型。

令C0=0、α=1,以p=2、p=-1为例,将目标函数变换为

2.2 动态频率拓扑优化数学模型

若简单地让其中某一阶频率达到最大,会使其他阶频率值降到比较低的值,从而导致几阶频率次序相互调换,这样会使目标函数发生频率振荡现象[7],因此为避免此现象并实现动态振动固有频率的最大化,结合平均距离公式得到

式中,f(ρ)为结构的平均固有频率值;l为固有频率总阶数;fj为结构的固有频率;M为系统的质量矩阵;фj为结构第j阶的正交特征向量;τj为结构第j阶的频率特征值;a=0.95。

为了使各阶频率达到最大,本文采用两种表示方法: 一种方法是使目标函数最小, 即min f(ρ),采用p=1,2,… 时的模型,fj0取fjmax,目的是使各阶频率更接近每阶频率最大值;另一种方法是使目标函数最大化,即max f(ρ),采用p= -1,-2,… 时的模型,可将单目标频率与最大目标值fjmax的距离最小化转化为与fjmin的距离最大化,此时f0min可选最小值0。因此产生两类平均频率数学模型,本文以p=2、p= -1为例,令f0=0,α=1,得

2.3 多目标拓扑优化的综合模型

由于柔度和频率的相互制约,而结构多目标优化的最终目的是实现各工况柔度最小化和各阶频率最大化,因此本文以权力值p=2为例,来实现两个定义的分目标最优。统一数量级,消除各自的量纲,可以得到最终的优化模型:

式中,C(ρ)max为平均柔度的最大值;C(ρ)min为平均柔度的最小值;f(ρ)max为平均频率的最大值;f(ρ)min为平均频率的最小值;C(ρ)0、f(ρ)0给定的值。

以列举的平均柔度和平均频率定义的两种目标函数为例,两两结合形成4种新的函数模型。

模型一:

模型二:

模型三:

模型四:

3 优化实例

本文以汽车悬架系统的控制臂为研究对象,以有限元软件Hyperworks为分析平台,参照文献[8]和文献[9],选择最为典型的制动、转向、过路面凹坑工况,建立了汽车控制臂的有限元模型;由于控制臂在有限元载荷计算中有累积误差,使得寻求一个完全平衡的外载荷力系的工作较困难[9],而且边界条件对计算结果有很大影响,因此本文采用惯性释放原理来减小该影响,从而使计算结果更合理,更接近实际情况。

材料弹性模量为210GPa,泊松比为0.3,密度7.9×103kg/m3,体积分数约束为上限40%,拔模方向指定为z方向,载荷与约束如图1所示,其中A为载荷施加点,B为z方向的约束点,Fx、Fy、Fz均为1000N。

3.1 优化过程

为了消除权重对各目标优化结果的影响,在本实例中把所有权重系数都设为1,在3 个工况下以结构柔度最小化为目标做拓扑优化的得到各工况的柔度最小值Cimin,初始值作为最大值Cimax;以固有频率最大化为目标拓扑优化得到各阶结构固有频率的最大值fjmax,初始值作为最小值fjmin。结果如表1、表2所示。

N·mm

再以平均柔度和平均频率最优化分别得到C(ρ)min、C(ρ)max、f(ρ)min、f(ρ)max,结果如表3所示。

最后将表1~表3的数值,分别代入4个总目标函数模型进行优化,得出最终优化结果。

3.2 优化结果

(1)经过Optistruct迭代得到的拓扑构型都保留相对密度0.505的材料,以z轴正方向观察,如图2所示,其中空白区域为删除材料的区域。

通过图2~图5中各分目标和总目标拓扑构型的对比,4种多目标构型结合了两分目标构型,拥有比较多的三角形和X形结构,其性能优于单目标构型。

(2)控制臂的各工况柔度和各阶频率经过这4种模型优化的最终结果如表4、表5所示。

由表4和表5可知:4种多目标优化模型优化后使各工况柔度有很大程度的减小,也就是各工况刚度得到较大程度的提高;优化后结构各阶频率也都得到相应的提高;该4种模型都很好地实现了多工况柔度最小化和多阶频率最大化的目的;模型三优化结果要比其他3种好。

N·mm

(3)4种模型目标函数的迭代过程如图6所示。通过观察4种多目标函数的迭代历程可知:由于4种目标函数构造的不同,迭代次数及迭代结果不同,但迭代趋势都趋于稳定,最终趋于0;说明在迭代过程中,各工况柔度及各阶频率都在向各自的目标值发展,使得柔度越接近最小值,频率越接近最大值,平均距离越趋于最小值。

4 结论

(1)本文将平均距离公式的基本理论与多目标结构优化相结合,基于4种构造的目标函数的拓扑优化结果可寻找较优的目标函数构建方法,从而使平均距离理念更好地应用于结构多目标拓扑优化。

(2)在多目标优化中,运用平均距离思想灵活地将距离的最大化转化为最小化来处理,通过优化结果的相互比较来有效的确定理想的结构拓扑构型,为设计者提供新思路,对于今后的实际工程优化问题有一定的指导意义。

(3)文中的平均距离公式可选择不同的参数,会演变不同的寻优方法,然而这种多样性同样增大优化过程的工作量,因此需对结构优化过程程序化,为拓扑优化模块及软件的开发提供了探索的空间。

摘要：为实现结构材料的多目标拓扑优化设计,基于数学规划法提出一种广义的平均距离法,用以研究多目标拓扑优化目标函数的构建方法。介绍了运用平均距离法演变的将多目标转化为单目标的多种方法,并以汽车悬架控制臂为实例,应用演变的多种方法进行拓扑优化仿真研究。研究表明:运用平均距离法演变的多种方法可以灵活地构建多目标优化目标函数,基于所构建的目标函数可以寻找较优的构建方法,更好地将平均距离理念应用于多目标结构优化设计。

关键词：平均距离法,目标函数,多目标,拓扑优化

参考文献

[1]Bendsoe M P,Sigmund O.Material Inter-polation Schemes in Topology Optimization[J].Arch.Appl.Mech.,1999,69:635-654.

[2]Bendsoe M P,Sigmund O.Topology Optimization:Theory,Methodsand Applications[M].New York:Springer,2003.

[3]占金青,张宪民.连续体结构的静动态多目标拓扑优化方法研究[J].机械强度,2010,32(6):933-937.Zhan Jinqing,Zhang Xianmin.Research on Static and Dynamic Multiobjective Topology Optimization of Continuum Struc-tures[J].Journal of Mechanical Strength,2010,32(6):933-937.

[4]孙晓辉,丁晓红.结构多目标拓扑优化设计[J].机械设计与研究,2012,28(4):1-4.Sun Xiaohui,Ding Xiaohong.The Topology Optimization Design of Multi-objective[J].Machine Design and Research,2012,28(4):1-4.

[5]范文杰,范子杰,苏瑞意.汽车车架结构多目标拓扑优化方法研究[J].中国机械工程,2008,19(12):1505-1508.Fan Wenjie,Fan Zijie,Su Ruiyi.Rsearchon Multiobjective Topology Optimizationon Bus Chassis Frame[J].China Mechanical Engineering,2008,19(12):1505-1508.

[6]刘林华,辛勇,汪伟.基于折衷规划的车架结构多目标拓扑优化设计[J].机械科学与技术,2011,30(3):382-385.Liu Linhua,Xin Yong,Wang Wei.Based on Compromise Programming Frame Structure of Multi Objective Topology Optimization Design[J].Mechanical Science and Technology Settings,2011,30(3):382-385.

[7]Ma Z D,Kikuchi N,Cheng H C.Topological Design for Vibrating Structures[J].Computer Methods in Appfied Mechanics and Engineering,1995,12(1):259-280.

[8]刘庆,侯献军.基于HyperMesh/OptiStruct的汽车零部件结构拓扑优化设计[J].装备制造技术,2008(10):42-44.Liu Qing,Hou Xianjun.Topology Optimization Design of Vehicle Components Based on HyperMesh/OptiStruct[J].Equipment Manufacturing Technology,2008(10):42-44.

具有约束多目标优化的进化算法篇8

二十世纪90年代以来,大量基于进化算法的多目标优化方法逐渐被重视[3,4]。但目前求解多目标优化的进化算法主要考虑相互冲突的多目标间的优化,而很少考虑约束条件[5]。而约束处理是工程优化问题中一个关键部分,因此有必要建立一个有效的方法求解一般的约束多目标优化问题。解决约束多目标优化问题关键是处理约束问题,也就是协调可行域和不可行域之间的搜索。

传统的解决约束多目标优化问题常用的方法是罚函数法,将约束多目标优化问题转化为无约束多目标优化问题。但一般罚函数方法处理约束条件的性能很大程度上依赖罚系数的设置。于是,我们提出了一种新的解决约束多目标优化的进化算法。在选择过程中,我们采用约束的Pareto支配和聚集距离[1],依据文献[2]中定义适应值的方法挑选出有代表性的个体。在变异过程中,沿着权重梯度方向搜索来寻找可行的Pareto最优解。权重选取基于下面这种思想:对目标函数的权重来说,若目标函数越不好,它对应的权重越大。对约束函数来说,若个体可行,则它对应权重为0;若个体不可行,则约束函数越偏离可行域,它对应权重越大。最后,采用两个数值算例对算法的求解性能进行测试,结果表明该算法能获得可行的Pareto最优解且具有较好的分散性。

1 约束多目标优化问题

本文主要考虑下面的约束多目标优化问题。

其中x=(x1,x2,…,xn)∈Rn是决策向量,f(x):Rn→Rm实向量函数;gi:Rn→R实函数。

定义约束违背函数如下:

其中,β通常取值为1或2,并且权重ωi>0(i=1,2,…,p)在搜索过程中可以调整。则约束条件gi(x)≤0等价于φ(g(x))=0。本文中,令:

定义1(Pareto支配″″)对于任两个决策向量a和b:

2 解决约束多目标优化的进化算法

2.1 初始种群

初始种群P中,第i个个体xi=(x1i,x2i,…,xni)依下面方式随机产生:

其中aj和bj是向量a和b的第j个元素,rj是符合均匀分布的0,1之间的随机数,N表示种群数。

2.2 计算个体的适应值

(2)计算中的聚集距离I,可行个体的聚集距离依据文献[1]进行计算,不可行个体的聚集距离设为0。

(3)计算P中个体的适应值:

2.3 选择

将计算出的个体的适应值按从小到大进行排序,并且选出排在前面的M个个体。

2.4 变异

(1)定义两种权重属性

为了保证fi(x)(i=1,2,…,m)是正数,我们引进一个大的正数c,则求目标函数fi(x)的最小化问题,等价于求函数c-fi(x)的最大化问题。

首先,在表1中列出函数c-f(x)的值。

其次,将表1中的数据规范化,得到表2。

定义目标函数的梯度方向权重ωi:

umin是表2中每行的最小值,ui是其相应行的第i个值i=(1,2,…,m),e是一个足够小的正数。

定义约束函数的梯度方向权重ω′i:

其中δ是用于调整的很小的正数。

构造权重梯度方向:

xki沿权重梯度方向d(xki)经变异产生子个体xkM+i可以描述为:

βk是均值衰减的Erlang分布随机数步长。

解决式(1)的算法流程如下:

Step1依照2.1节产生初始种群P,设置最大迭代次数(即最大进化次数)NG,初始迭代次数k=1;

Step2在种群P中,对于个体xki(i=1,2,…,N)依据2.1~2.2节选择M个体,产生种群P(k);

Step3产生新的个体xkM+i,根据式(5)~式(9);

Step4将新个体xkM+i添加到种群P(k)中,令P=P(k);

Step5令k=k+1,如果k≤NG,转Step2,否则输出非支配解集。

3 数值测试例子

我们引入两个测试函数[6]来检测算法的性能,对于每个测试函数:

例1的无约束情况已由很多研究者进行了求解[4],这里增加了约束条件用以测试算法在整个解空间搜索可行区域的性能。取群体规模为M=100,最大进化次数为300,计算结果见图1。图1给出了两个目标函数的Pareto前沿。计算结果说明可行的最优目标函数值范围是0≤f1≤1和1≤f2≤4,以及2.25≤f1≤4和0≤f2≤0.25,所得到的可行Pareto最优解在Pareto前沿形成均匀分布。

测试函数2是由Tanaka[7]引进的。该测试函数的Pareto前沿共分为三段曲线,其中中间段的水平和垂直部分由于解之间的差异甚微,往往是最难搜索的部分。取群体规模为M=100,最大进化次数为300,计算结果如图2所示,从图2可以看到,我们的算法可以成功地搜索到问题的Pareto前沿。

4 结论

本文提出了解决约束多目标优化的进化算法,我们采用约束的Pareto支配和聚集距离[1]依据文献[2]中定义适应值的方法挑选出有代表性的个体。我们改进了变异算子,并且定义了两种新的权重属性,在变异过程中使用权重梯度方向搜索来寻找可行的Pareto最优解。通过两个典型的带约束多目标优化问题的成功求解,证明我们的算法能很好地求得所有可行的Pareto最优解,并使得其在可行Pareto前沿形成均匀分布。

参考文献

[1]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective ge-netic algorithm:NSGA-II.IEEE Trans.Evol.Comput.2002,6(2):182197.

[2]Min Zhang,Huantong Geng,Wenjian Luo,et al.A Hybrid of Differen-tial Evolution and Genetic Algorithm for Constrained Multiobjective Op-timization Problems.University of Science and Technology of China.

[3]Shengjing MU,Hongye SU,Wang Yuexuan,et al.An efficient evolu-tionary multi-objective optimization algorithm[C]//Proceedings of the IEEE Congress on Evolutionary Computation(CEC2003).Canberra:IEEE Press,2003:914920.

[4]Zitzler E,Deb K,Thiele L.Comparison of multiobjective evolutionary algorithms:Empirical results[J].Evolutionary Computation,2000,8(2):173195.

[5]Deb K,Pratap A,Meyarivan T.Constrained Test Problems for Multiob-jective Evolutionary Optimization[R].KanGAL report,200002,Kan-pur:Indian Institute Technology,2002.

[6]王跃宣,刘连臣,牟盛静,等.处理带约束的多目标优化进化算法.清华大学学报:自然科学版,2005,45(1).

QoSR多目标优化的灰色模糊解篇9

关键词：灰色模糊多目标优化QoS路由,启发式算法,灰色模糊理论,灰色模糊关系

0 引言

面对Internet中实时业务的快速增长, 传统的单目标QoS优化已经不能满足现实的要求, 于是很多多目标优化算法被提出来, 这些算法大部分使用随机寻优的策略寻找最优路径, 比如蚂蚁算法、Hopfield神经网络方法、遗传算法[2,3,4]等, 但是这些算法或者时间复杂度太高, 需要离线计算;或者基于太多的假设, 在实际环境的性能往往比理论上有很大的降低, 甚至变得不可用, 导致实时环境中实用性并不高。针对这些问题, 本文提出的基于灰色模糊关系的QoS多目标优化方法, 通过将灰色系统理论与模糊数学两种理论加以融合, 使两种理论优势互补, 达到了较好的效果, 可以综合考虑各种QoS参数, 不仅能够找到最佳路径问题在灰色模糊意义下的最优解或者说至少能找到非劣解, 而且算法的时间复杂度得到了有效控制, 使算法在多项式时间内结束。最后的算例说明该算法是可行的。

1 问题描述

1.1 QoS路由多目标优化

QoS问题是一个很难完全解决问题[11], 针对QoS路由多目标路由优化中存在的这些问题, 结合网络实际, 本文提出了基于灰色模糊关系的QoS路由多目标路由优化算法, 并期望能够实现下列目标:

(1) 算法在多项式时间内可解, 这是算法须首先解决的问题, 本文通过将多个路径约束整合成一个综合指标, 从而实现了一种启发式算法, 使算法在多项式时间内至少能够找到一个非劣解甚至是最优解。

(2) 算法具有可扩展性, 除了考虑多QoS路径约束, 还可以考虑访问公平性等其它因素, 也就是参数的增加不会引起计算量的大幅增加。由于很多约束之间经常会存在相互干扰, 甚至是相互矛盾的优化要求, 目标之间的这种矛盾性使得算法在改善某方面性能的同时, 却使目标集中的另一性能变坏。本文通过使用模糊数学中的隶属度以及灰色理论中的灰度概念, 较好地解决了这个问题, 使算法具有较强的抗干扰性。

(3) 基于区分服务体系结构 (DiffServ) , 对不同的业务采取不同的优化策略, 并能够针对不同的业务类型区分不同的关键QoS约束和非关键QoS约束。结合文献[5], 本文主要考虑了四种业务类型, 如表1所示。

(4) 由于网络环境的复杂性、信息的陈旧性[6]等因素的影响, 使网络节点得到的链路状态信息往往是不可靠、不准确的, 算法通过考虑隶属度函数的灰色内涵性质, 使用灰度这一指标来量化隶属度函数的准确程度, 从而使算法的优化结果更加可信。

1.2 理论基础和问题描述

模糊数学能够考虑问题中的模糊因素, 而灰色理论适用于信息不完全或不充分的问题。但在工程实际中, 往往在一个信息不完全的问题中存在许多模糊的因素, 或是具有模糊因素的一个问题不具备完全充分的资料, 即在一个问题中既存在模糊性, 又具有灰色性, 这就要在处理时同时考虑模糊性和灰色性两方面的影响。灰色模糊集合以灰色模糊数学理论为基础, 将隶属度和灰度综合在一起, 可以处理同时具有灰色性和模糊性的问题, 因此有着比单一理论更为广泛的适用范围。所以可以将这两个理论有机地融合在一起, 使他们取长补短, 达到优势互补的目的。

1.2.1 基本概念

定义1 灰色模糊集合[9] 设 $\tilde{A}$ 是空间X = {x}上的模糊子集, 若对于 $\tilde{A}$ 的隶属度μA (x) 是[0, 1]上的一个灰数, 其点灰度为νA (x) , A为 $\tilde{A}$ 的支集, 则称 $\tilde{A}$ 为X 上的灰色模糊子集或灰色模糊集合, 记作 $\underset{⨂}{\tilde{A}}$ , 即:

$\underset{⨂}{\tilde{A}} ≜ {(x, μ_{A} (x), ν_{A} (x)) | x \in X}$

用集偶的形式可以表示为 $\underset{⨂}{\tilde{A}} ≜ (\tilde{A}, \underset{⨂}{A})$ , 其中 $\tilde{A} ≜ {(x, μ_{A} (x) | x \in X}$ 称为的模糊部分 (简称模部) , $\underset{⨂}{A} ≜ {(x, ν_{A} (x)) | x \in X}$ 称为的灰色部分 (简称灰部) 。若灰色模糊集 $\underset{⨂}{\tilde{A}}$ 的模部是一个模糊数, $\underset{⨂}{\tilde{A}}$ 的灰部是一个灰数, 则称 $\underset{⨂}{\tilde{A}}$ 为灰色模糊数, 记作 $⨂ (\tilde{a})$ 。

定义2 路径灰色模糊QoS参数设路径p的某个QoS参数 $⨂ (\tilde{x})$ 是空间X = {x}上的灰色模糊数, 若对于 $⨂ (\tilde{x})$ 的隶属度μ⨂ (x) 是[0, 1]上的一个灰数, 其点灰度为ν⨂ (x) , 则称 $⨂ (\tilde{x})$ 为路径p的灰色模糊QoS参数。记作 $⨂ (\tilde{x}) ≜ (μ_{⨂} (x), ν_{⨂} (x))$ 。

QoS参数可以是时延、分组丢失率、分组差错率、网络的连接阻塞率以及时延抖动等, 还可以考虑访问公平性中的某些参数, 从而使算法具有可扩展性。

定义3 路径灰色模糊指标向量对于给定的有向图G (V, E) , 设P为两节点v1、v2之间的路径集, $| Ρ | = m$ , pk∈P ( k=1, 2, …, m) , 用 $⨂^{k} (\tilde{x}_{i})$ 表示路径pk的第i个灰色模糊QoS参数, 则称由n个灰色模糊QoS参数组成的向量:

$⨂^{k} (\tilde{X}_{i}) ≜ (⨂^{k} (\tilde{x}_{1}), ⨂^{k} (\tilde{x}_{2}), \dots, ⨂^{k} (\tilde{x}_{n}))$

为路径pk的n维QoS灰色模糊指标向量。

定义4 路径参数灰色模糊关系对路径集空间P={p}, QoS灰色模糊指标向量集空间 $⨂ ≜ {⨂ (\tilde{x})}$ , 若p与 $⨂ (\tilde{x})$ 对于模糊关系 $\tilde{R}$ 的隶属度 $μ_{R} (p, ⨂ (\tilde{x}))$ 有点灰度 $ν_{R} (p, ⨂ (\tilde{x}))$ , 则称直积空间P×⨂中的灰色模糊集合之间的关系:

$\underset{⨂}{\tilde{R}} ≜ {((p, ⨂ (\tilde{x})), μ_{R} ((p, ⨂ (\tilde{x})), ν_{R} (p, ⨂ (\tilde{x})))$

$| p \in Ρ, ⨂ (\tilde{x}) \in ⨂ (\tilde{X})}$

为P×⨂上的路径参数灰色模糊关系。用灰色模糊矩阵可以表示为:

$\underset{⨂}{\tilde{R}} ≜ ((μ_{i j}, ν_{i j}))_{m \times n}$ (1)

1.2.2 问题描述

设P={p1, p2, …, pm}, $⨂ = {⨂^{1} (\tilde{X}), ⨂^{2} (\tilde{X}), \dots, ⨂^{n} (\tilde{X})}$ 分别为有向图G (V, E) 中的源节点vs、目标节点vt之间的路径集和相应的QoS灰色模糊指标向量集, 则在直积空间P×⨂上由网络链路状态决定的路径参数灰色模糊关系可以表示为:

其中μij表示元素 $(p_{i}, ⨂^{j} (\tilde{x}))$ 对模糊关系 $\tilde{R}$ 的隶属度 $μ_{R} (p_{i}, ⨂^{j} (\tilde{x}))$ , νij表示隶属度μij的灰度。

接下来确定μij、νij。对隶属度μij, 本模型的要求是越大越好, 但考虑到有些QoS参数对优化的影响是越小越好 (如时延、抖动等) , 本文称之为负影响参数;而其它的参数对结果的影响却是越大越好 (如资源利用率) , 本文称之为正影响参数。这两类参数显然要分别计算。对负影响参数和正影响参数本文分别定义其归一化隶属度函数为:

$μ_{i j}^{-} = 1 - \frac{⨂^{i} (x_{j})}{\sum_{i = 1}^{m} (⨂^{i} (x_{j}))} μ_{i j}^{+} = \frac{⨂^{i} (x_{j})}{\sum_{i = 1}^{m} ⨂^{i} (x_{j})}$ (3)

其中⨂i (xj) 是第i条路径的第j个QoS参数。

对灰度νij的计算, 通常是由专家根据经验进行打分的方法, 显然这种方法在本文的这种实时环境中是无效的。所以本文采用灰度公式来计算μij的灰度。一般来说, 影响网络状态信息可靠性的因素很多也很复杂, 许多文献都对此问题进行了探讨[6], 但影响信息不准确的主要因素是信息的陈旧性和网络负荷对链路信息交换的影响, 设链路状态信息的更新间隔时间ΔT, 参数⨂i (xj) 服从其值域上的均匀分布, 则我们确定归一化灰度νij近似为:

$ν_{i j} = \frac{ρ_{i} t_{i} - \min_{i} (ρ_{i} t_{i})}{\max_{i} (ρ_{i} t_{i}) - \min_{i} (ρ_{i} t_{i})} = \frac{ρ_{i} t_{i}}{Δ Τ}$ (4)

其中i=1, 2, …, m;j=1, 2, …, n;ρi为路径i的带宽利用率;ti是距离最近一次信息更新时间的时间。显然该定义满足灰度五公理。

本文的算法基于区分服务体系结构, 不同的服务类型对QoS参数的要求有不同的偏重。现假设路径灰色模糊指标向量中各灰色模糊QoS参数的权重及相应的点灰度构成的权重向量为:

$\tilde{w} ≜ ((α_{1}, ν_{1}), (α_{2}, ν_{2}), \dots, (α_{n}, ν_{n}))$ (5)

其中 $α_{j} > 0, \sum_{j = 1}^{n} α_{j} = 1$ , 0≤νj≤1 (j=1, 2, …, n) 。

集结路径集中各路径的灰色模糊综合属性值, 为了保留原始数据中更多的信息, 对模部采用 (≜, +) 算子, 对灰部采用 (≜, +) 算子, 即:

$\tilde{B} ≜ \underset{⨂}{\tilde{R}} \tilde{w}^{Τ} ≜ ((b_{i}, ν_{b_{i}}))_{m \times 1}$ (6)

其中 $b_{i} = \sum_{j = 1}^{n} α_{j} μ_{i j}, ν_{b_{i}} = [\frac{1}{n} \sum_{j = 1}^{n} (ν_{j} + ν_{i j})] \land 1 (i = 1, 2, \dots, m)$ 。

现在对灰色模糊综合属性值向量 $\tilde{B}$ 进行排序, 其排序向量β= (β1, β2, …, βm) 定义为[8]:

βi=P ( (bi, νbi) ) =αbi+ (1-α) (1-νbi) i=1, 2, …, m (7)

其中α为平衡系数 (0<α<1) 。式 (7) 的意义是βi的取值体现了第i条路径的综合隶属度越大越好, 而其综合点灰度越小越好。平衡系数α可以求下列优化问题的解:

考虑到多目标优化的时间复杂度以及算法的实时化特点, 本文直接选取α=0.5。

定义5 路径灰色模糊优化排序关系“≻” 若对两路径pi、pj的灰色模糊综合属性值βi、βj存在关系βi>βj, 则说明路径pi优于pj, 表示为pi≻pj。

类似地, 可以定义优化排序关系“≻”和“=”。与一般的路径排序关系不同, 本文定义的排序关系使任意两条路径总可以比较优劣关系, 即总存在≻、≺、=三种关系中的一种, 使路径在灰色模糊意义下具有“有序性”。

2 灰色模糊QoS多目标优化

2.1 灰色模糊QoS多目标优化算法

基于以上的分析, 现在给出灰色模糊QoS多目标优化算法的过程。该算法属源路由或者是MPLS的直接选路算法, 路由计算在源点或边界路由器进行, 源节点要维持整个网络的状态信息。对于给定的有向图G (V, E) , 源节点vs、目标节点vt之间所有路径形成的集合P。

第一步:首先读取链路状态信息, 根据不同业务类型的关键QoS约束删除不满足关键约束的路径得到P′。如果不存在这样的路径, 则连接被拒绝;

第二步:根据链路状态信息构建路径集P与灰色模糊QoS指标向量集⨂之间的路径参数灰色模糊关系 $\underset{⨂}{\tilde{R}}$ ;

第三步:根据事先规定的不同业务种类的QoS参数的权重向量 $\tilde{w}$ , 集结各路径的灰色模糊综合属性值, 即计算 $\tilde{B}$ ;

第四步:计算灰色模糊综合属性值向量 $\tilde{B}$ 的排序向量β= (β1, β2, …, βm) ;

第五步:按分量β1, β2, …, βm的大小筛选出最大分量, 该最大分量对应的路径即为灰色模糊最优路径。

2.2 算法计算复杂度分析

灰色模糊QoS多目标优化的核心运算是一次矩阵与列向量的乘法, 所以算法的时间复杂度跟矩阵乘法的时间复杂度是一样的, 在不对矩阵乘法作任何优化的情况下算法的时间复杂度为O (mn) , 其中m、n分别为路径条数和考虑的QoS参数的个数。显然, 这与复杂度动辄指数规模的随机寻优策略[2,3,4]相比, 在运算规模上具有一定的优越性。并且在大型网络中路径数m一般远远高于所考虑的QoS参数数目n, 这时n的值接近于log m, 所以在大型网络中该算法的时间复杂度接近于传统的单目标Dijkstra算法的时间复杂度O (mlog m) 。

2.3 算法性能分析

由于算法是在全路由的基础上进行的, 对于全路由的计算可以使用传统的有效算法, 从而该算法继承了这些算法的有效性, 不会产生回路问题;由于算法可以考虑不同数目的参数, 所以具有一定的可扩展性;算法基于DiffServ体系结构, 能够根据不同的业务类型采取不同的路由策略, 具有较强的适应性;由于算法基于模糊数学的隶属度和灰色理论中的灰度, 使算法对信息的不可靠性及不准确性有了一定的耐受能力, 具有健壮性的特点。

3 算例

本文选择了一个只有两个节点的比较简单的网络如图1所示。

对复杂网络的计算方法是相同的。考虑两个节点vs、vd之间共有五条路径p1, p2, …, p5, QoS参数考虑传输时延、时延抖动和差错率, 路径上的向量为 (传输延迟, 时延抖动, 差错率, ti, ρi) , 假设某一请求为实时业务, 则时延抖动为关键约束, 设要求时延抖动小于3, 该业务对各QoS参数的权重分配及其他数据假设为表2。

网络状态信息的更新间隔为100ms, 即ΔT=100ms。则计算灰色模糊QoS多目标优化路由的过程为:

首先由关键约束条件, 从路径集P中删除不满足关键约束的路径p2, 得到路径集P′;

接着根据链路状态信息及公式 (3) 、 (4) 确定路径参数灰色模糊关系矩阵 $\underset{⨂}{\tilde{R}}$ :

$\underset{⨂}{\tilde{R}} ≜ ((μ_{i j}, ν_{i j}))_{m \times n} ≜ (\begin{matrix} (0.77, 0.16) & (0.8, 0.16) & (0.8, 0.16) \\ (0.81, 0.27) & (0.8, 0.27) & (0.9, 0.27) \\ (0.62, 0.02) & (0.8, 0.02) & (0.6, 0.02) \\ (0.8, 0.26) & (0.6, 0.26) & (0.7, 0.26) \end{matrix})$

然后根据表2中的权重数据及公式 (6) 计算各路经的灰色模糊综合属性值 $\tilde{B}$ :

$\tilde{B} = ((0.793, 0.362), (0.828, 0.473), (0.705, 0.223), (0.675, 0.464))$

最后由公式 (7) 计算各路径的排序向量β= (0.577, 0.651, 0.464, 0.569) 。则根据各分量与路径的对应关系有p3≻p1≻p5≻p4, 即路径p3是最优的, 从而找到多约束问题在灰色模糊意义下的最优解。

4 小结

通过使用灰色模糊理论, 将所有的QoS参数集结成一个灰色模糊综合属性, 从而在O (mn) 时间内实现了QoS路由多目标优化, 找到了路由计算中的最优解, 并且使算法具有可扩展性、健壮性、对陈旧信息的抗干扰性等性能。算法的效果基本达到了本文开始提出的目标。

未来的工作希望可以从以下两个方面优化这个算法:①本文在确定各参数的灰色模糊权值时采用的是固定的经验权值, 这导致算法对权值比较敏感, 今后可以考虑根据不同的业务及网络状态动态计算权值;②在确定隶属度的点灰度时, 对信息不准确性的影响仅仅考虑了信息陈旧性及路径剩余带宽两个因素, 并且还假设QoS参数服从均匀分布, 今后还可以在影响网络信息不确定的因素及参数服从的分布方面进行优化。

参考文献

[1]Wang Z, Crowcroft J.Quality-of-Service Routing for Supporting Multi-media Application[J].IEEE Journal of Selected Areas in Communica-tion, 1996, 14 (7) :1229-1234.

[2]Feng X, Li J Z, Wang J V, et al.QoS routing based on genetic algorithm[J].Computer Communications, 1999, 22 (15/16) :1392-1399.

[3]Chotipat P, Goutam C, Norio S.Neural network approach to multicastrouting in real-time communication networks[C].Proc InternationalConference on Network Protocols, 1995:332-339.

[4]Zhang S B, Lv G Y, Liu Z M, et al.QoS routing based on ant-algorithm[J].J of Circuits and Systems, 2000, 5 (1) :1-5.

[5]Le F Facheur, et al.Requirements for support of Diff-Serv-aware MPLStraffic engineering, RFC3270, May 2002.

[6]Shaikh A, Rexford J, Shin KG.Evaluating the impact of stale link stateon quality-of-service routing[J].IEEE/ACM Transactions on Networ-king, 2001, 9 (2) :162-176.

[7]Nibin Chang C G, Wen Y L Chen, et al.A Grey Fuzzy MultiobjectiveProgramming Approach for the Optimal Planning of a Reservoir Water-shed.Part A:Theoretical development[J].Wat.Res, 1996, 30 (10) :2329-2334.

[8]Ishihuchi H, TanakaM.Multi-objective programming in optimization ofthe interval objective function[J].European Journal of Operation Re-search, 1990, 48:219-225.

[9]陈大为.灰色模糊集合引论[M].哈尔滨:黑龙江科学技术出版社, 1994.

[10]卜广志, 张宇文.基于灰色模糊关系的灰色模糊综合评判[J].系统工程理论与实践, 2002, 22 (4) :141-144.

航班着陆调度的多目标优化研究篇10

随着民航事业的发展,航空运输量迅猛增长,空中交通拥堵问题越来越严重,最终也就导致了航班延误数量大幅增加。造成这一结果的一个瓶颈就是终端区航班着陆调度问题。

航班着陆调度问题是一个组合优化问题,属于NP-hard问题。用简单的FCFS方法求解这类问题,虽然求解速度很快,但求解结果往往会造成时间、机场容量、飞行成本等多方面的浪费。而使用求最优解的算法,如动态规划、分支定界、回溯等,又需要太多的执行时间,达不到实时动态对航班进行调度的需求。所以,能够做到求解效率和求解质量上双重保证的启发式方法,是现阶段对航班进行实时动态调度的较好方法。近年来,国内外对终端区航班着陆调度进行了很多研究,提出了多种启发式方法。如Farah[1]提出了带有时间窗的蚁群算法。张伟[2]研究了基于遗传算法的优化算法。冯兴杰[3]提出了基于免疫粒子群优化算法的航班着陆调度。Balakrishnan[4]提出了基于约束位置偏移CPS的航班调度。但他们只考虑了一个求解目标的情况。张启钱[5]提出了基于RHC的航班着陆调度多目标优化算法,取得了不错的结果,但是由于只使用了GA进行求解,为了让GA较快得到一个收敛的解,也就无法充分发挥GA对更大搜索空间进行搜索的潜力,很容易陷入局部最优。

SWO[6]在航班调度上应用较少,但却被证明适用于多种组合优化问题,比如二维装箱问题[7],人工时间安排问题[8],多卫星数传调度问题[9]等。在这些问题中SWO在短时间内取得了不错的效果。这是因为SWO是一种大邻域导向式搜索性质的启发式算法,所以在一定的解空间中会很快找到一个比较优的解,但是搜索的解空间必然会有所减少。另外Tang[10]、Maqsood[11]等人将一些启发式算法和GA进行合理整合,最终提高了原算法的求解性能。尤其在Terada[12]的研究中进行了SWO与GA的整合尝试,并最终发现求解效果优于单纯的SWO或者GA的求解效果。但是他只是进行了简单的叠加整合,所以如果将SWO与GA合理整合,将会有更好的效果。因此本文对SWO与GA进行整合研究,记为SWOGA,以航班着陆多目标优化为目标,让GA充分增大搜索空间,使用SWO在搜索空间中快速找到当前局部最优,循环执行得到全局近似最优解。这样GA与SWO都能发挥所长,从而达到对求解质量与求解效率的优化效果。

1 问题描述及模型建立

航班着陆调度问题就是在获取待降落航班序列的到达时间后,在满足空域和机场容量以及安全间隔约束( 即尾流间距,如表1所示) 的前提下,以减少航班延迟、增加机场吞吐容量、能源节约等目标,对航班序列进行重新调度降落排序,给出满足合理目标结果的调度方案。

本文以如下符号描述航班着陆问题中的参数:

N: 预到达飞机数

A: 预到达飞机集合

ai: 飞机i的机型

Ei: 飞机i预到达时间

Sij: 飞机i与飞机j之间的尾流间距

ti: 飞机i降落时间

di: 飞机i的降落时间延迟

ci: 飞机i的降落延误成本

qi: 飞机i的实际降落顺序

为与文献[5]结果进行平等对比,计算时不考虑飞机提前降落的情况,飞机只能在预到达时间之后降落,所以有Ei≤ti。飞机在飞行时会产生尾流,对后面的飞机造成影响,所以相邻飞机之间的间距至少是最小尾流间距Sij,它由相邻两架飞机的机型ai和aj决定,取值如表1所示。另外,在终端区的飞机调度与预到达顺序相比不能有太大的位置移动,所以要满足MPS约束。

所以航班着陆问题可以表述为下面形式:

约束条件:

2 算法设计与实现

2. 1 SWO 算法介绍

SWO是一个以“构造 - 分析 - 优先级调整”为核心的迭代算法。对于一个调度问题,先构造一个调度的初始解。然后如图1所示,进入SWO的迭代,分析器对构造器生成的任务序列( 第一次是初始解) 进行分析,通过评价函数计算各任务当前责罚值。优先级排序器则根据分析器得出的责罚值,改变任务在下次迭代中的优先级。构造器在下次构造调度结果时对优先级高的任务进行优先安排,改变原来的调度顺序,从而生成新的调度结果。上述过程循环执行,直到满足算法退出条件。

为了描述SWO迭代过程,我们分析文献[6]中一个简单的调度问题。有一个生产线,有三个任务( A,B,C) 需要调度,并且在每个时间点只能执行一个任务。图2给出了每个任务的执行时间长度和计划完成时间,调度目标是最小化发生延迟的任务个数。

第一次迭代,假设初始调度解为 < C,A,B > ,我们以任务的延迟时间作为责罚值,通过分析器分析,A、B和C分别获得的责罚值为: 20,30,0。

第二次迭代,优先级排序器根据责罚值进行降序排序,从而得到新的优先级顺序: B,A,C。构造器根据新的优先级顺序得到新的调度解 < B,A,C > 。按照这样的调度顺序,A、B、C分别获得的责罚值为: 20,0,10。

第三次迭代,和上面迭代过程一样,我们可以得到新的调度解为 < A,C,B > 。这时只有一个任务B发生延迟,获得了最优解。所以SWO可以很快找到一个局部最优,但如果继续执行会陷入二三次迭代的循环。所以如果我们能够适时改变SWO搜索的区域,将会大大提升搜索质量。我们将用改进的GA来扩大SWO的搜索区域。

2. 2 算法整合

通过分析GA和SWO单兵作战的优缺点,我们发现,他们两个可以有效互补。首先由SWO快速获取一部分比较优的初始解集合store,然后GA将调度解序列作为染色体( 无需编码和解码操作) ,对store中的解集进行选择,杂交,变异操作,若发现一些更优的解,则更新store,并让SWO对这些更优的解进行迭代优化,并随时用SWO获得更优的解更新store; 否则,继续SWO的优化迭代。上面过程循环执行,便能充分发挥GA对解空间的扩展特点,以及SWO对局部最优解的快速搜索特点。从而使求解质量和效率得到双重提升。为了进一步提升整体性能,我们进行了一些算法调整,并加入一些启发式规则,最终达到了不错的效果:

( 1) 通过对比随机选择策略、轮盘赌策略、精英选择策略,对本文的多目标函数优化程度,发现采用随机选择策略结果会更好。我们将一些比较优的解( 种群) 存入store,作为GA中选择、交叉、变异操作的对象。

( 2) 在整个迭代操作过程中,SWO每次都执行,而GA只需要每隔100次迭代才执行一次,但每次GA的执行要进行多次交叉、变异尝试操作,从结果中选出目标函数总权值最小的调度结果与store中的进行对比。这样GA不会干扰SWO对解的优化倾向,并在合适的时候使用GA扩展搜索空间,最终也节约了执行时间。

( 3) 采用模拟退火算法的思想处理GA交叉操作得出的最新调度结果,若结果比store中的优,则接受新调度结果,使用SWO迭代优化,并更新store; 否则以执行时间t的概率p = p( t) ,接受不好的调度结果进入SWO迭代,但不用更新store,其中p( t) 随执行时间t的增加越来越小。

( 4) 通过分析实验数据发现,比较优的调度序列之间往往会存在大部分相同的降落序列部分,而它们之间不同的降落子序列部分很有可能出现更优的排列情况,所以完成大规模迭代后,对最优、次优解的不同的降落子序列部分进行一次小规模的SWO迭代优化,有可能提升最终结果的求解质量。

2. 3 算法实现

分析器对当前降落顺序X进行责罚值penalty分析,因为本文是多目标优化,所以选取各航班对延迟时间和成本的权值加和作为责罚值,即:

优先级排序器根据责罚值分析器分析出来的penalty,对航班降落优先级priority进行修改,其中责罚值越大优先级越高,即:

构造器根据降落航班的优先级priority,在满足约束条件的基础上,对优先级比较高的航班进行优先降落( 在原来调度位置的基础上进行前移) ,重新生成调度结果,即: Xi= f4( priorityi) ,1≤i≤N。

选择所以从记忆序列store里面随机选出两个调度序列作为交叉操作对象,即:

交叉将选择出来的两个序列分别作为父体和母体进行交叉,即:

变异对选择出来的序列进行变异操作,即:

算法实现流程如下:

1) 设置参数: SWO + GA迭代次数M0,子序列SWO优化次数M1。每个航班的责罚值初始化为0。

2) 利用FCFS算法构造初始解X,存入store。

3) 对X中各个航班进行责罚值分析。

4) 对步骤3) 中责罚值进行降序排序。

5) 在X的调度序列中,对步骤4) 中责罚值排名处在前N /2的航班均前移一位。作为新的调度解X。

6) 若当前迭代次数为100的整数倍,则使用GA随机选择store中两个解,进行多次交叉和变异。

7) 选出交叉和变异所得结果中最优的解与store进行对比,若比store中的优,则接受新调度结果,并更新store; 否则以概率p = p( t) ,接受不好的调度结果,但不更新store,其中p( t)随执行时间t的增加越来越小。

8) 若达到最大迭代次数M0,则终止迭代,否则转入步骤3) 。

9 ) 从store中选出最优、次优的两个不同解X1,X2,选取两个解中不同的连续子序列部分X3进行步骤3) 至步骤5) 的优化,迭代次数为M1。若X3得到优化,则整合X3与X1为新X1。X1记为当前算法所求最优解。

3 仿真结果及分析

3. 1 实验数据与仿真

本文采用文献[5]中的40架连续进场航班进行仿真验证。并与文献[5]中提供的RHC优化方法进行对比。参数设置如下: SWOGA整体迭代执行5000次,其中SWO每次均执行,而GA每隔100次执行一次。最后子序列优化200次。其他测试参数与文献[5]相同,计算时不考虑航班提前降落,尾流间隔如表1所示,决策偏好cd = 0. 5,cd1= 0. 5,最大位置偏移MPS = 3。重中轻3种机型单位时间延误成本比为5∶3∶1( 延误成本 = 延误时间×单位时间延误成本) 。

表2给出了航班预到达基本信息以及FCFS调度策略对应的降落时间。表3中各列分别为RHC、SWOGA单目标优化,多目标优化的降落时间。表4给出了三种优化策略的延迟结果分析。

3. 2 结果分析

通过对比表4的延误结果分析可以看出,虽然以延迟最小为目标进行研究时,SWOGA的总延迟时间只比RHC的结果稍优一点。但在以成本最小为目标和多目标优化时,SWOGA均比RHC策略取得了明显更好的结果。

除此之外,我们在图3中给出了SWOGA对多目标优化的求解结果分布。图中横纵坐标分别为延迟总时间和延迟总成本。其中RHC的优化结果为图中三角形的位置,SWOGA的优化结果为图中所有正方形所示,也就是说由SWOGA所求,处在三角形左上方的结果,延迟总时间比RHC少,但延迟总成本却高于RHC; 处在三角形右下方的结果( 只有一个) ,延迟总成本比RHC少,但延迟总时间高于RHC; 而处在三角形左下方的结果,无论延迟总时间还是延迟总成本都比RHC少。总体来看,SWOGA的求解结果要明显优于RHC的求解结果。可以提供总延迟以及总成本更少的航班降落调度优化方案。

4 结语

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处

【多目标中长期优化】相关文章：

山东省第十一次党代会报告深度解读：长期坚持的目标定位和根本要求06-22

基于多目标规划的唐山市土地资源优化配置研究11-18

多目标最优化问题在区域经济规划中的应用探讨04-20

打坐有什么好处长期坚持打坐好处多04-12

多目标分辨06-17