时间：2023-09-12 17:09:34
导语：在多目标优化概念的撰写旅程中，学习并吸收他人佳作的精髓是一条宝贵的路径，好期刊汇集了九篇优秀范文，愿这些内容能够启发您的创作灵感，引领您探索更多的创作可能。
关键词:
多目标优化; Pareto优胜; Pareto前沿; 演化算法; 自适应
中图分类号: TP18
文献标志码:A
Quick multi-objective evolutionary algorithm based on adaptive Pareto-ε dominance
WANG Jiang-qing1, YANG Xun2
(
1. College of Computer Science, South-Central University for Nationalities, Wuhan Hubei 430074, China;
2. Yan’an General Office, China Executive Leadership Academy,Yan’an Shaanxi 716000, China
)
Abstract:
For multi-objective optimization problems (MOP), it is very important to provide proper and feasible solutions rapidly for the decision makers. A method for MOP was given. First, a conception of Pareto-ε dominance was defined. Then, based on this conception, a new adaptive multi-objective evolutionary algorithm was proposed. The numerical results demonstrate that the new algorithm can improve the process of MOP optimization, and can meet the requirement of the high-speed, effectiveness in application.
For Multi-objective Optimization Problems (MOP), it is very important to provide proper and feasible solutions rapidly for the decision makers. A method for MOP was given. First, a concept of Pareto-ε dominance was defined. Then, based on this concept, a new adaptive multi-objective evolutionary algorithm was proposed. The simulation results demonstrate that the new algorithm can improve the process of MOP optimization, and can meet the requirements of high-speed and effectiveness in application.
Key words:
multi-objective optimization; Pareto dominance; Pareto front; evolutionary algorithm; adaptive
0 引言
科学研究和工程应用中的优化问题大多是多目标优化问题(Multi-objective Optimization Problem,MOP),如车辆路径路径问题、QoS路由等。这类问题通常包含若干个相互矛盾且没有共同量纲的目标 [1-3]。如何在优化过程中既兼顾各目标利益又体现各目标的地位,是求解此类问题的关键[4-5]。
多目标优化的目的是使决策者最终能够找到一个满意的决策方案。目前在多目标优化算法中,基于Pareto优胜的算法非常流行[6-8]。这些算法主要集中于利用算法找到最大的Pareto最优解集,找到Pareto 前沿与已知全局前沿的最小距离,及找到解的最大宽度等[9-10]。然而,在实际的应用系统中,决策者通常期望算法能够在较短的时间内提供一个或几个可采纳的解决方案。在算法的效率和解的质量不能同时满足的情况下,如何快速地给决策者提供合理、易决策、可接受的解决方案,是算法走向实际应用的一个关键问题。
本文定义了一种Pareto-ε优胜的概念,并基于此概念提出了一种新的基于ε-优胜的多目标演化算法(Pareto-ε Multi-Objective Evolutionary Algorithm,PEMOEA)。该算法采用一种新的带调节度的搜索策略以调节搜索的步长,加快算法的收敛,并采用ε的自适应调整策略改进解的质量。实验结果显示,新策略可以使搜索更加快速有效地到达Pareto前沿,为决策者提供可行的解决方案。
1 Pareto-ε的相关定义
图1为Pareto比较搜索示意图。图中f1 和f2为两个子目标,表示搜索空间中的随机点,所组成的曲线表示最终的Pareto前沿。
图片
图1 Pareto比较搜索示意图
如果从随机点A出发进行搜索,那么A的附近有B、C、D优于它(极小化)。逐步推进搜索到E、F、G、H,然后搜索到N、O、…、S,最后才能搜索到Pareto前沿…。通过分析发现,从A搜索到最优解,做了许多无用功。如果采取一定的策略,适当调整搜索的步长,搜索速度将会大幅度提高。
定义1 Pareto-ε优胜。向量u=(u1,…,un)ε-优胜于向量v=(v1,…,vn)(表示为u┆华εv)当且仅当i∈{1,…,n},满足ui≤vi±ε,ε≥0。
与以往文献的区别在于,本文定义的ε-优胜可以加上ε也可以减去ε:如果加上ε,称该调节度为带宽容度的;如果减去ε,称该调节度为带苛刻度的。
定义2 Pareto-ε无差别。向量u=(u1,…,un)无差别于向量v=(u1,…,un)当且仅当i∈{1,…,n} 满足|ui-vi|≤ε,ε≥0。
定义3 Pareto-ε最优解。对于给定的MOP F(x),解x∈X称为X上的Pareto-ε最优解,当且仅当不存在x′∈X,使得F(x′)沪F(x)。
定义4 Pareto-ε最优解集。对于给定的MOP,其Pareto-ε最优解集P*-ε定义为:
P*-ε={x∈X|开霆x′∈X,使得F(x′)沪F(x)}
由以上定义可以看出,Pareto-ε最优解集是在Pareto最优解集基础上的推广,是一个比Pareto最优解集更大的区域(宽容度下)或者更狭窄的区域(苛刻度下)。
定义5 Pareto-ε前沿。Pareto-ε前沿Pf-ε*定义为:
Pf-ε*={u=F(x)|x∈P-ε*}
Pareto优胜关系与Pareto-ε优胜关系的区别如图2所示。
图片
图2 Pareto与Pareto-ε比较
图中,f1和f2Х直鸨硎MOP的两个子目标,a、b、c、d、e、f、g、h、i分别代表目标空间中的一个区域。显然,优胜于a的是b、e、d区域。而根据本文的定义1、2可知,ε-优胜于a的是c、f、i、h、g区域,b、e、d区域与a是ε-无差别的。a的非劣域正好由L曲线(Pareto优胜下的)所标识的区域向前推进到达U曲线(Pareto-ε优胜下)所标识的区域。
Pareto优胜与Pareto-ε优胜相比,每次找到的Pareto最优解的范围是一条曲线或者曲面,而找到的Pareto-ε最优解的范围是带一定宽度的区域带;基于Pareto-ε优胜比较的搜索步伐要明显快于Pareto优胜比较的。
┑4期 ┩踅晴等:基于Pareto-ε优胜的自适应快速多目标演化算法
┆扑慊应用 ┑30卷
2 PEMOEA算法
2.1 算法设计
由于当前研究MOP大多数是基于演化算法的,为验证Pareto-ε优胜的新定义及其相关策略,本节基于演化算法,给出一类新的基于Pareto-ε优胜的多目标优化算法。算法框架如下:
程序前
begin
t=0;
随机产生初始群体Pt={x1,x2,…,xM};
计算群体中所有个体的Rank函数值;
while (不满足终止条件) do
从Ptе腥〕Rank值最大的前N个个体x1,x2,…,xN进行遗传操作,产生KЦ鲂赂鎏;
Pt′=Pt∪K;
计算Pt′е兴有个体的Rank值并从大到小排列;
取前M个个体形成新一代群体Pt+1;
t=t+1;
endwhile;
输出Ptё魑求出的Pareto-ε最优解集,计算出与PtФ杂Φ哪勘晗蛄考;
end
程序后
2.2 自适应Е诺髡策略
算法采用动态调整策略,通过动态调整ε的值,使算法开始时快速向Pareto真实前沿逼近,但最终又不受ε的影响,也就是让εг谒惴ㄔ诵泄程中逐步回归为0,从而更好地逼近真实的Pareto前沿。本文设计了一个公式,该公式的值可以随着算法执行代数的增加而减少,逐步趋近为0,从而减弱Е弄Ф宰詈蠼獾挠跋,如式(1)所示。
ε=-(gig┆max+l)h+d (1)
其中:gi为算法当前的运行代数;g┆max是最大运行代数;l、r、s分别为调节参数。
3 实验结果和讨论
3.1 实验仿真
实验所使用的物理平台为Pentium 4 CPU 3.0@GHz、512@MB内存,软件平台为VC++6.0和Matalab 7.0。算法分别采用三种搜索策略进行测试:带苛刻度的、带宽容度的、动态调整Е诺摹T谒惴ㄔ诵泄程中只是εУ娜≈挡煌,实施动态调整策略后,也只是增加了对式(1)的计算,并未增加时间复杂度和较大的计算量。因此,本文采用算法终止时所花费的计算代数来衡量算法的性能。从仿真实验中随机选择一组测试数据,测试函数为:
F=(f1(x,y), f2(x,y))(2)
其中:
f1(x,y)=(x-2)2+(y-1)2+2;
f2(x,y)=9x+(y-1)2。
函数的Pareto前沿最终效果如图3所示。
图片
图3 函数Pareto前沿效果
Е湃「髦植煌值时算法的终止代数如表1所示。表2为对ε实行动态调整后的计算结果。图4则给出了g┆max=5B000, l=1,r=-3,s=0.3下的Pf-ε*效果图,其中M为群体大小。
3.2 性能分析
1)Pareto-ε优胜比较策略。实验证明该策略可以增加搜索步长,加快算法的收敛速度,无论是带宽容度的还是带苛刻度的比较策略都可以显著改善收敛性质。在带宽容度的情况下,Е旁酱蟊冉咸跫就越弱,搜索速度就越快,随着ε值的增大算法的收敛性能逐步减弱。在带苛刻度的情况下,虽然比较条件加强了,但是每次成功的移动步长增大了,从而收敛速度也加快了。但两种情况均有不足,在带宽容度的情况下,ε的值增大到一定程度后,解的质量会下降;在带苛刻度的情况下,若ε过大会导致收敛速度过快而早熟,甚至出现比较条件过强而算法无法启动的情况。
2)自适应的ε调整策略。针对以上不足,本文通过动态调整εУ闹,使算法开始时快速向Pareto前沿逼近,最终让Е弄г谒惴ㄔ诵泄程中逐步回归为0,从而更好地逼近真实的Pareto前沿。该策略既可以提高算法的搜索和收敛速度,又可以消除Е弄е刀宰钪战獾闹柿康挠跋臁S氤S玫亩嗄勘晁惴ㄏ啾,这种包括自适应的Е弄У髡策略的PEMOEA算法在处理MOP上具有显著的优越性。
表格(有表名)
表1 不同Е弄取值下的算法终止代数
运算次数ε
00.1-0.1-0.2-0.5-1-1.1-1.2-1.2-1.5-2
1403430359393317377334370370358285
2450485394372392367352344344394305
3437396377382302322353339307329313
4450462394354392344338384377376297
5398389371447354349302316319322332
6438333403349404334337347299322390
7438338404387377341383319301292356
8403338421414348383370358346310320
9425390390434357368327372356363329
10377430435415337358336330348354328
11392366403454367345338350398324327
12421410454456352346318356350305319
13393454442378346340291359342312293
平均运算代数417.3401.6403.6402.6357.3351.8336.8349.5342.8335.4322.6
图片
图4 不同群体规模下的Pf-ε*效果
表格(有表名)
表2 动态调整Е弄У乃惴ㄖ罩勾数
运算ご问ε
-1/(i/m+1)-0.2-1/(i/m+1)-1/(i/m+1)+0.2
1389312333
2375351318
3381368354
4314338370
5411340303
6347337376
7347374319
8345369354
9362352350
10328313330
11336334355
12361336379
13334350362
14332397366
15318348402
16378355360
平均运に愦数353.625348.375351.938
4 结语
本文定义了一种Pareto-ε优胜关系的概念,提出了一种新的自适应ε调整策略,设计了一个新的基于ε-优胜的快速多目标演化算法,分析了ε取值对算法的影响。实验表明,Pareto-ε概念是合理、有效的,加快了算法寻优的速度,可以快速地为决策者提供合理、满意的决策方案。下一步的工作重点在于:进一步探讨ε的取值及其动态变化规律;探索在宽容度和苛刻度下,算法性能得以进一步改进的内在机制。
参考文献:
[1]ELMUSRATI M, EL-SALLABI H, KOIVO H. Applications of multi-objective optimization techniques in radio resource scheduling of cellular communication systems[J]. IEEE Transactions on Wireless Communications, 2008,7(1):343-353.
[2]DASHENG L, TAN K C, GOH C K. A particle swarm algorithm for multiobjective design optimization [J]. IEEE Transactions on Systems Man and Cybernetics, 2007,37(1):42-50.
[3]HO S L, YANG S Y, ZHANG G. A particle swarm optimization-based method for multi-objective design optimizations [J]. IEEE Transactions on Magnetics, 2005,41(5):1756-1759.
[4]刘淳安,王宇平.动态多目标优化的进化算法及其收敛性分析[J].电子学报,2007,35(6): 1118-1121.
[5]石川,李清勇,史忠植.一种快速的基于占优树的多目标进化算法[J].软件学报,2007,18(3): 505-516.
[6]郑向伟,刘弘.多目标进化算法研究进展[J].计算机科学,2007,34(17): 187-191.
[7]VALENZUELA C L.A simple evolutionary algorithm for multi-objective optimization (SEAMO)[C]// CEC’02:Proceedings of the 2002 Congress on Evolutionary Computation.Honolulu:IEEE, 2002: 717-722.
[8]DEB K, MOHAN M, MISHRA S. Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions[J]. Evolutionary Computation,2005,13(4):501-525.
关键词：多目标决策；优化决策方法
中图分类号：C93-0 文献标识码：A 文章编号：1001-828X（2013）08-00-01
一、引言
人们在对科学问题进行研究的过程中，仅考虑单一目标的做法已经不能满足实际需求，随着研究问题规模的不断扩大以及复杂程度的不断增加，必然涉及对多个目标进行分析、优化，并最终做出合理的决策。一般情况下，多目标决策问题的各个目标之间往往是矛盾的，改善其中的一个目标，有可能会是其他目标难以实现，或者说是效用降低，也就是说想要使多个目标一起达到最优值是不现实的，而只能通过的一定的方法进行处理，使各个子目标最大程度的实现最优化[1]。自 20世纪60年代早期以来，多目标优化决策问题吸引了越来越多研究人员的注意力。因此，解决多目标优化决策问题具有非常重要的科研价值和实际意义。
二、多目标优化决策方法
在对文献研究的基础上，得出Keen和Morton将决策问题分类为结构化决策问题、半结构化决策问题和非结构化决策问题[2]。在实际解决问题的过程中，一般情况下，多目标优化问题是不存在唯一全局最优解的，而求解得到的过多的非劣解是无法直接应用的，所以在求解时要需要通过一定的方法寻找到一个最终解。目前对于多目标优化决策方法还没有一个统一的分类标准，从国外的研究资料来看，本文将从以下三个方面进行分类介绍。
1.按照优化决策过程
根据优化过程和决策过程的先后顺序，可以将多目标优化决策方法分为以下3大类[3]。
（1）先验优先权方法，即先决策后搜索。这种方法是通过预先确定各目标的优先权值，再将所有目标按权值大小组合成一个标量效用函数，通过这种方法最终可以复杂的多目标优化决策问题转化成比较常规的单目标优化决策问题。这种方法可以说是一种化繁为简的方法。
（2）交互式方法，即决策与搜索交互进行。这里所说的交互是指优先权决策与非劣解集的搜索二者之间是交替进行的。首先按照优先权进行决策，逐渐产生非劣解，最后又从非劣解集搜索的过程中提出取能够对优先权设置进行改良的信息。可以说，交互式方法结合了概率的相关知识，是先验与后验优权设置方法的有机结合。
（3）后验优先权方法，即先搜索后决策。首先通过优化器进行非劣解集的搜索，然后再利用决策器从搜索到的非劣解集中进行选择。
2.按照适应度和选择方式
基于适应度和选择方式的不同，可以将多目标优化决策方法分为以下3类[4]。
（1）基于聚合选择的优化方法。这些算法的原理是首先将多目标优化决策问题转化为单目标优化问题，然后再利用一般的解决单目标优化决策问题的方法进行求解。不过，这类方法在将多目标问题转化为单目标问题的过程中，会具有一定的主观色彩，当决策人员对优化对象认识的经验不足时聚合得到的单目标问题将不再符合原有多目标问题的初衷以及特点。
（2）基于准则选择的优化方法。这种算法会依据不同的准则进行选择、交叉以及转变，并最终将所有目标融合起来，其实相当于把适应度函数进行线性求和，而目标的权重则取决于当前代的种群。
（3）基于Pareto选择的优化方法。这是基于Pareto概念的一种优化决策算法，它的基本原理是将多个目标的值直接映射到一个基于秩的适应度函数中。
3.偏好信息的表达方式
按照偏好信息的表达方式，可以将多目标优化决策方法分为了以下三类：
（1）事前偏好信息索取。这种方法在优化之前，决策者首先要把所有的偏好信息一次性都提供给分析人员，而分析人依据这些偏好，结合一定的方法优化计算出可行的“最优解”。
（2）事后偏好信息索取。这种方法是指在对问题进行了最大优化之后，由分析人求得了大部分的非劣解之后，再请决策者在这些非劣解中按照自己的偏好做出选择。
（3）逐步偏好信息索取。这种优化方式是在优化过程中，由分析人员通过不断交流的方式向决策者不停地、逐步地获取偏好信息，在过程中逐渐优化决策信息的一种方法。
三、结论
对以上的多目标优化决策方法进行分类了解之后，可以得出多目标优化问题的目标间具有矛盾性，当某一目标值得到改进时，可能造成其他目标值的变坏。在多目标优化决策方法发展之初，决策者的性格、偏好、经验、知识等几乎没有被考虑在决策问题的求解过程中，这样使得决策结果往往不太贴合实际情况，因此在后来产生的很多决策算法，都加入了决策者的意愿。可以得知，多目标优化问题求解是一个决策过程，决策者的主要任务就是在各个目标之间进行折衷，通过牺牲某个或某些目标的性能来改善其它目标，所以寻找令决策者满意的解。不同的优化问题具有不同的属性和特点，每种优化算法也都具有自身的特点，其适应性是相对的而不是绝对的。因此，在解决实际的问题时候，应该首先了解待求解问题的特点，从而选择出适合于优化问题自身特点的优化算法。所以说，多目标优化决策方法的研究，不仅仅要对单一算法进行深入的分析，更重要的是算法之间的结合运用，使其能够互相取长补短，共同解决好实际中满足决策人要求的问题。
参考文献：
[1]肖晓伟，肖迪，林锦国，肖玉峰.多目标优化问题的研究概述[J].计算机应用研究，2011，28（3）：805-808.
[2]陈雪龙.面向复杂决策问题的模型构造与管理方法研究[D].大连：大连理工大学，2008：3-5.
[3] Veldhuizen D A V， Lamont G B， evolutionary computation and convergence to a Pareto front[A]. 1998 Genetic Programming Conference [C]. Madison， Wisconsin， 1998. 144-150.
[4] Horn J， Handbook of evolutionary computation [M]. Bristol（UK）： Institute of Physics Publishing， 1997.
关键词：文化算法；多目标优化
中图分类号：TP301.6 文献标识码：A文章编号：1007-9599 (2012) 06-0000-02
研究表明，文化能使种群以一定的速度进化和适应环境，而这个速度是超越单纯依靠基因遗传生物进化速度的[1]。种群在进化过程中，个体知识的积累和群体内部知识的交流在另外一个层面促进群体的进化。受这些思想的启发，Reynolds[1]于1994年提出文化算法，近年来引起国内外众多学者关注。
与其他进化算法相比，文化算法提供了一种明确的机制来表示、存储和传递进化时的知识，因而在一些问题上取得了比传统进化算法更好的结果。但是对文化算法的研究才刚刚开始，还有许多问题需要进一步研究。因此有必要对文化算法进行深入研究，对其基本原理、特点、适用的问题、应用等方面展开全面研究，以引起国内更多学者的关注，为后续学者展开相关研究提供方便。
一、文化算法
（一）文化算法基本原理
文化算法框架由群体空间(Population Space)和信念空间(Belief Space)两部分组成，如图1所示。群体空间和信念空间是两个相对独立的进化过程，群体空间从微观层面模拟个体进化的过程，而信念空间从宏观层面模拟文化的形成、传递和比较。从计算模型的角度来看，任何一种符合文化算法要求的进化算法都可以嵌入文化算法框架中作为群体空间的一个进化过程[2]。
图1 文化算法框架
经典文化算法的伪代码如下所示：
其中：
Accept()：将从群体中所选择个体的经验传递到信念空间。
Influence()：信念空间形成群体经验后，利用此函数影响群体空间中个体的行为，以使群体空间中个体得到更高的进化效率。
（二）文化算法一般特点
1.双重继承（群体层和知识层）；2.知识是用来指导种群进化的“明灯”；3.支持分层结构；4.领域知识与个体分离；5.支持自适应；6.不同的层可以不同的速率进化（文化进化速度是生物进化速度的10倍）；7.支持混合方式(hybrid approaches)来解决问题；8.文化算法的各不同模型都可用一个统一的框架表示。
（三）文化算法适用的问题
1.含有大量领域知识的问题（如约束优化问题）；2.一些群体空间和信念空间中的适应过程可能在不同层次以不同速度发生的复杂环境；3.知识需要以不同的方式进行推理，并以不同的形式表达；4.需要多种群、多信念空间，并且这些空间进行交互的；5.一些可能出现分层结构的群体和知识因素的环境。
（四）文化算法的设计
1.信念空间的设计
A本体知识（某一领域中的公用概念）的描述；B约束知识的描述；C解决方案的描述；D确定哪些部分将会被修改？用Update()函数来更新每一个需要修改的部分；E知识维护；
2.群体空间的设计
A声明变量；B如何用这些变量来产生一个解决方案？C如何评价这个解决方案？设计时要注意：究竟该从信念空间开始还是从群体空间开始设计，取决于具体问题。如对于分类问题和约束问题，前者经常从信念空间开始，而后者经常从群体空间开始。
二、利用文化算法求解多目标优化问题[3]
（一）多目标优化问题
多目标优化问题的主要任务就是在满足一定约束条件的参数空间内搜索Pareto最优集。近年来兴起的进化算法，包括遗传算法、模拟退火算法由于能较好地解决传统算法的缺点，成为近年来解决多目标优化问题的研究热点。2003年，Ricardo Landa Becerra首次提出用文化算法来求解多目标优化问题[3]，并取得了不错的结果。
（二）求解MOP的文化算法
利用文化算法求解MOP问题时，种群空间采用进化规划，因此称为CAEP。信念空间包括两类知识：规范化知识和网格图。
信念空间：规范化知识记录每一个目标函数值区间的上下边界 和 ，如下图6所示。利用输入的 值可以将每个区间[ ， ]划分为 个子区间，并由此创建对应的网格图。
…
图2 规范化知识结构
如下图3所示是用于解决具有两个目标函数的MOP时的网格图，此时，网格在每一维上被分割为8个子区间，因此形成一个8*8的网格图。
图3 网格图
对于有k个目标函数的MOP，网格图有 个单元，每一个单元中记录位于该单元中非劣最优解的个数，其中，所有的非劣最优解都存储在一个外部文件中。算法结束时，存储在外部文件中的内容即为算法找到的Pareto最优解集，其中外部文件的大小为q。
信念空间初始化：初始化信念空间前，首先在种群空间生成一个初始种群。然后求得初始种群中所有非劣最优解对应的每一个目标函数的最小值和最大值，即为规范化知识的边界值 和 。利用此边界值，可以画出相应的网格图。并根据输入的 划分子区间。
信念空间的更新：网格图每一代都更新，规范化知识每 代更新一次。
更新规范化知识时，只需要利用Accept()函数从当前存储在外部文件中的所有非劣最优解中选出新产生的解，利用这些新产生的非劣最优解所对应的目标函数区间来更新网格图。
变异：种群空间中的个体采用下式进行变异，变异后种群中个体数为2p。
选择：采用锦标赛选择法从2p个个体中选择p个个体作为下一代。选择原则如下：
1.若一个个体优于（dominate）另一个个体，则优个体获胜；
2.若两个个体无法比较，或者两个个体的目标函数值相同，则：
a若两者均位于信念空间中的网格图中，则所在单元含个体较少的个体获胜；
b若其中一个个体不在网格图中，则此个体获胜。
（三）求解MOP的文化算法流程
Step1 生成大小为P的初始种群；
Step2 评价初始种群；
Step3 初始化信念空间；
Step4 执行变异操作以产生P个子个体（这时种群中有2P个个体）；
Step5 评价子个体；
Step6 利用锦标赛选择法选择出P个个体作为下一代；
Step7 将新产生的非劣最优解保存到外部文件中；
Step8 利用保存在外部文件中的个体更新信念空间；
Step9 转到Step4直到满足终止条件。
（四）结论
与其他算法相比，用文化算法求解多目标优化问题时，执行次数较少，求得的解更好，甚至能够找到其他算法没有发现的Pareto前沿区域。缺点是该方法在一些情况中会很快失去种群多样性。
三、总结与展望
与传统的进化算法不同，文化算法只提供了一个进化模型，任何基于种群的进化算法都可为文化算法的群体空间提供种群，如遗传算法、进化规划、进化策略等。
相比其他较成熟的进化算法，文化算法的研究才刚刚起步，应用的范围也比较少，因此有必要对文化算法进行深入研究，将其应用到更多的领域。
参考文献：
[1]Robert R G．An Introduction to Cultural Algorithms[J]. In: Proceeding of the third annual Conf. on Evolution Programming, Sebalk. A.V.Fogel L.J., River Edge, NJ. ⅥWorld Scientific Publishing. 1994, 131-136.
本文提出了一种用于解决约束多目标优化问题的方法。本算法在进化算法的基础上加入了邻里竞争与邻里合作算子，并通过引入agent-based模型的设计理念，更加注重个体变化对整个群体的影响。本算法首先使用约束偏离值的方法将约束多目标优化问题简化为多目标优化问题；然后使用自我更新算子，当新产生的个体优于原先的个体时予以替换；之后通过邻里竞争与邻里合作加快种群内部的信息交流；最后加入量子加速算子，通过使用量子旋转门来扩大计算搜寻范围提高程序计算速度。本文最后与两种已有算法进行对比，实验结果表明，本算法完成了设计目标。在运行时间和输出结果精度方面都有不错的表现。
【关键词】约束多目标优化 量子计算 约束偏离值 邻里竞争
1 引言
进化算法是以达尔文的进化论思想为基础，通过模拟生物进化过程与机制的求解问题的自组织、自适应的人工智能技术。与传统的优化算法相比，进化计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法，具有自组织、自适应、自学习的特性。尤其是在处理多目标优化问题时，进化算法表现出很好的效果。
近年来，出现了很多优秀的算法用于解决约束多目标优化问题，其中Deb提出的NSGA-II算法是最为经典的一个算法。NSGA-II成功的将进化算法应用在约束多目标优化问题上，在进化算法的基础上引入了约束偏离值。Hongguang Li提出了基于agent的进化算法用于求解约束多目标优化问题。算法利用agent概念认为每个个体与其种群内其他个体都有相互的作用和影响，虽然算法精度不是很高但是计算速度很快。本文受到基于agent概念的启发，希望设计出一个计算速度快，精度高的算法。
2 量子进化算法
2.1 邻里竞争与邻里合作
agent-based模型是一种从底层到高层的数学模型，模型更加注重的是每个个体对整个群体的影响，通过改变个体的某些特征和表现从而影响整个整体。本算法在此基础上，通过模仿自然界种群内部个体之间既有竞争又有合作的关系，设计出了邻里竞争与邻里合作算子。邻里竞争算子采用的是吞并算子，算子表示如下：
设对于一个种群共有k个个体X1，X2，…，Xi，每个个体的目标函数值分别为，则：
（1）
其中表示的是新产生的个体。公式表达的意义是：每个个体与其排名靠后一位的个体进行竞争，将两者目标函数值进行对比，目标函数值较小的个体成为这一位置上的新个体。
邻里合作算子如下：
（2）
（3）
其中，是个体i、j的第k个决策变量，且。r，u是分布在[0，1]之间的随机数。
2.2 量子计算
加入量子算子是为了加快计算速度，希望通过更少的进化代数进化出更加优秀的种群。本算法通过设计出一个对周围区域具有自适应调整搜索步长的量子旋转门，从而提升量子计算运行效率。量子计算首先需要将个体的基因编码从实数编码形式转换为量子编码形式，之后通过量子旋转门的计算快速搜索周围空间寻找更加优秀的个体进行输出。
个体在完成量子旋转门的计算后，个体的基因编码需要映射回实数域，完成其他计算过程。量子算子的本质也就是通过将个体基因编码转换为量子域，通过利用量子计算在量子域具有指数级加速和指数级存储的能力，快速的寻找最优解的过程。
2.3 算法的主要流程
图1为本算法流程图。算法采用顺序结构设计，结构简单， 在进化计算的基础上首先使用了约束偏离值的方法，将约束多目标问题进行简化。其次借鉴了基于agent模型里种群中个体之间又相互的影响和作用，设计了邻里竞争与邻里合作算子。又利用了量子计算的加速性能，提升了算法的运行速度。
若为第一代种群，本算法通过之前修正好的目标函数向量进行选择，首先在可行解里选取非支配解，形成种群FeaPop，并在全部种群中寻找非支配解，放入种群NonPop中；若不是第一代种群，则将上一代产生的父代FeaPop与当代的进化种群Pop合并形成NPop，在合并之后的种群里再去寻找可行非支配解形成当代的FeaPop种群，寻找非支配解形成当代的NonPop。变异算子对于防止种群陷入局部最优解起到了重要的作用，本算法采用文献中非一致性变异算子。
3 仿真实验与结果分析
本文的测试问题是Deb提出的六个经典的约束多目标最小化问题， 算法参数设计为：初始种群大小为100，合作概率为0.9， 合作指数为10，变异概率为0.5，非一致系数为2，自我更新指数为20。最大的可行非支配解集FeaPop大小为100，非支配解集NonPop大小为100。对比算法初始种群大小为100， 交叉概率为0.9， 交叉分布指数为15， 变异概率为0.1， 变异分布指数为20。
文中所有测试问题均独立运行30次，我们采用的度量指标分别为GD和算法运行时间。世代距离指标（GD），是度量算法所得Pareto前端与真实前端之间的距离。其数学表达式如下式所示：
（4）
其中，，n为个体数目，是中第个个体的目标函数向量与中最近个体间的欧氏距离。GD值越小，所求得的前端就越接近真实前端，解集的收敛性就越好。运行时间则是算法的跑完相同进化代数所需要的时间，时间越短说明算法运行速度越快，本文中涉及到的几种算法运行代数均为1000代。
表1给出本文算法与两种对比算法运行6测试问题的结果。
CTP2、CTP7是寻找离散的几个线段，CTP3、CTP4两个问题要寻找的Pareto前端都是离散的端点，CTP5是离散点和线段的组合，CTP6问题是寻找连续的直线。从表中我们可以看出几种算法对于处理CTP2问题都有不错的结果，都可以很好地找到几个离散端点。对于CTP3和CTP4问题由于测试函数难度的加大，算法[3]已不能很好地找出真实Pareto前端所在位置，而NSGA-II、本算法还能找到真实Pareto前端所在区域，不过已经无法做到很精准的定位Pareto前端的位置。对于CTP5，几种算法在找离散点的能力都很不错。对于CTP6问题几种算法都找到了Pareto前端，只是均匀性稍有差异。CTP7问题，除了算法[3]之外也都很好的找到了前端所在区域。
4 总结与展望
本文算法用于处理约束多目标优化问题，在设计上借鉴了agent-based模型，更加注意种群中个体对整个种群的影响，通过进行自我更新，邻里协作与邻里竞争等操作来改变个体的基因编码，从而改变了整个种群的进化方向进化速度，共同朝着真实的Pareto前端进行进化。并且本算法融入了量子计算，使得程序可以更高效更快捷更准确的去寻找最优解。在和现有的几种算法的对比上体现出了算法的优势，在保证精度值的基础上减少了大量的程序运行时间。不过提高算法的精度仍然是之后研究的重点。如何更好地处理种群中个体之间的关系是我们今后需要进一步做的工作。
参考文献
[1]王勇，蔡自兴，周育人.约束优化进化算法[J]软件学报，2009，20（1）：11-29.
[2]Venkatraman S and Yen GG.A Generic Framework for Constrained optimization Using Genetic Algorithms.IEEE Trans.on Evolutionary Computation，2005，9（4）：424-435.
[3]Woldesenbet YG，Yen GG，and Tessema BG.Constrained Handling in Multiobjective Evolutionary Optimization. IEEE Trans.on Evolutionary Computation，2009，13（3）：514-525.
[4]Vargas Denis E.C.，Lemonge Afonso C.C.，Barbosa Helio J.C.，Bernardino Heder S.Differential evolution with the Adaptive Penalty Method for constrained multiobjective optimization.2013.CEC 2013.（IEEE Congress on Digital Object Identifier），2013：1342-1349.
[5]Deb K，Pratap A，Agarwal S，and Meyarivan T.A Fast and Elitist Multiobjective Genetic Algorithm： NSGA-II.IEEE Trans.on Evolutionary Computatuion，2002，6（2）：182-197.
[6]Hongguang Li，Hui Ding，Agent-based evolutionary algorithms applied to constrained muliti-objective optimization problems，Applied Artificial Intelligence， 2012，26（10）：941-951.
[7]Ling，S.H.，Leung.F.H.F.； Lam，H.K.；Yim-Shu Lee；Tam，P.K.S A novel genetic-algorithm-based neural network for short-term load forecasting.IEEE Industrial Electronics Society，Aug.2003，793-799.
[8]Deb K，Pratap A，and Meyarivan T.Constrained Test Problems for Multi-objecitve Evolutionary Optimization. EMO 2001，LNCS 1993，2001：284-298.
作者简介
陈妍冰（1989-），女，陕西省西安市人。硕士研究生学历。现在供职于西安科技大学工程训练中心。主要研究方向为数字图像处理、模式识别、机器学习。
作者单位
在居住建筑天然光环境设计中，面对不同室外环境特点和室内空间功能，首先应该立足的是居住建筑天然光环境的多目标性，即充分认识到居住建筑天然光环境丰富多样的内容，以及这些内容落实到建筑设计中的内在结构关系，这种认识对于任何居住建筑空间来说都是适用的，并在此基础上展开对不同目标功能性要求的分析，也就是从设计之初，就应该建立“多目标系统与多目标控制”的设计思路，突破专业和学科的界限，从更大的环境范围整体性地思考设计内容。明确这一思路，可以有助于系统化设计过程，突破传统的专业和学科界限，使得设计过程更加立体，设计结果更加精确。为了使抽象的概念层级与具象的设计目的相联系，本文对一般情况下，城市居住建筑天然光环境的设计内容和任务进行了总结，主要包括以下几点:1)要满足现有规范中对于天然光环境各因素的基本要求，主要有:卧室、起居室(厅)等居住房间以及厨房均应直接采光，以满足居住者生理、心理和卫生方面的需要;要有良好的采光窗朝向，最好为南朝向，东南或西南朝向次之，东、西朝向再次，最次为东北或西北朝向以及北朝向，目的在于获得足够的天然光;要满足《建筑采光设计标准》(GB/T50033-2001)对窗地面积比和采光系数最低值的要求;对有日照要求的房间，要满足《城市居住区规划设计规范》(GB50180-93)(2002年版)的要求［2］;窗户和建筑形式的设计要满足《严寒和寒冷地区居住建筑节能设计标准》(JGJ26-2010)对建筑体形系数、围护结构传热系数、窗墙面积比、建筑耗热量指标的要求。2)窗户面积的设置满足采光能效值的要求。3)窗户形状、位置的设计满足采光和视觉舒适度的要求。4)兼顾室内的景观和视野感受。完成了上述“基于多目标的居住建筑天然光环境优化设计”方法实践应用的第一步，就明确了设计的总体目标和思路，明确、细化了设计任务，为具体的设计内容提供了实践起点。
2居住建筑天然光环境设计目标的整合
在明确思路和设计任务之后，需要将这一思路与具体的居住建筑空间相联系，以形成具体化的设计任务，按照“整合目标”的实践步骤，首先需要确定每1项设计任务所需要的数据或资源信息，以及达到这些信息的具体设计手法。比如，朝向是天然光环境设计的主要内容之一，首先应该确定居住建筑户型，明确不同功能空间的朝向。但是居住建筑的朝向会受到不同因素的制约，在对居民的问卷调查中，普遍认为的住宅最佳朝向中南向占73%，东南向占18%，东向占9%(见图1)，居住者可以接受的朝向中南向、东南向、西南向占的比例最大分别占到28%、24%和27%，其次为东向占到12%，北向、东北向和西向占的比例最小均为3%(见图2)。而针对与朝向有关的居室布置的问题，当仅有2个房间可以占据一户中的最佳朝向时，59%选择了起居室与卧室，而选择双卧占据最佳朝向所占的比例为11%，15%选择了卧室与书房，11%选择了起居室和书房，可见大部分居住者希望起居室能占据最好的朝向位置。居民在回答调查问卷的问题时按照问卷填写内容倾向于从采光和日照的角度选择最佳朝向，由图3可以看出，窗外景观的重要性程度仅次于直射阳光和空间照度分布，而在实际的项目设计中，环境景观也是决定居室朝向的重要因素，此时需要综合采光和景观的要求，协调两者矛盾，根据项目实际特点确定居室朝向。这其中，居住者对于采光、日照和景观的要求即是该项设计任务的资源信息，而“整合目标”的步骤提供了完成这一设计任务的手段。在确定了居室朝向后，需要决定居室窗户的面积和形式，本文针对建立的天然光环境多目标优化设计模型以及对模型的求解也是1种“整合目标”的过程，其过程可由图4表示。
首先，窗户面积是影响建筑耗热量指标和室内天然采光质量的最直观的形式特征，也是影响居住者视知觉感受的直接的空间表象。在天然光环境优化设计中首先要确定建筑的耗热量指标，进而根据耗热量指标确定计算房间的窗户面积。《建筑采光设计标准》(GB/T50033-2001)和《严寒和寒冷地区居住建筑节能设计标准》(JGJ26-2010)中都对窗户面积提出了相应的要求和规定。《建筑采光设计标准》(GB/T50033-2001)要求在建筑方案设计时，对于类光气候区的普通玻璃单层铝窗采光，起居室、卧室、书房、厨房的窗地面积比可按1/7进行估算，卫生间、过厅、楼梯间、餐厅的窗地面积比可按1/12进行估算。其次，窗户的形状和位置是影响天然光在室内空间分布和视知觉感受的功能性特征，优化设计的重要内容即是根据室内空间的具体使用情况和使用者的个体特征确定窗户的形状和位置，窗户形式对于室内空间天然光的分布和视知觉感受并不是直观可知，且并不存在最佳的窗户形式。通过研究表明窗户的上沿高度与室内采光系数的相关度最高，因此可以通过窗高临界点结合视知觉感受和采光能效的研究结果的思路确定合适的窗户形式和位置。由图4可以看出，在这一过程中综合考虑了包括光气候条件、不同功能空间的采光能效值、窗户形式对采光系数的影响作用、窗户形式对视知觉感受的影响各方面的设计参考信息，形成了“窗户面积———窗户高度———窗户位置、形式”的设计过程，并在这一设计过程中有效的整合了各种参考信息的设计要求。突出了窗户作为天然光环境设计的主体地位，强调了采光与建筑耗热和主观舒适度的等设计目标间的相互影响作用，和对窗户形式、位置设计结果的影响作用。由此可见，在“多目标控制”的设计思路下，需要随时整合不同目标的设计要求，并根据项目实际特点做出相应的选择，使对目标的追求落实于实际的设计中。
3居住建筑天然光环境目标的完成
在完成了前2步设计过程之后，基本的设计内容已经完成，这时需要从整体的角度针对各项目标和任务进行计算和检验，适时地做出设计调整，对于通过建筑形式设计无法达到或在某些项目中无法协调的目标，可以选择适当的采光技术和先进的窗体和墙体材料进行补充，完成相应的设计目标和任务。
4结语
粒子群算法作为当前进化算法中的最新模式，主要通过记忆与反馈机制来实现高效快速的搜索，以其全局最优性、迅捷性、收敛性等特点为解决大规模的数学问题提供了技术支持。输电网扩展规划作为一个非常庞大的函数问题，需要借助粒子群算法来实现输电网总体规划的优化。然而，粒子群算法在具体的应用实践中也存在着诸多不足之处，包括易在早期成熟收敛导致出现局部最优不足，并对输电网规划的优化产生偏差。本文正是基于此，探讨在粒子群算法改进视角下，输电网规划的优化方案。
【关键词】粒子群算法 改进 输电网规划 优化
1 粒子群算法改进对实现输电网规划优化的必要性
粒子群算法，是近年新发展起来的进化算法，其寻求最优解的来源是随机解，在通过迭代寻找最优解，并通过追随当前搜索到的最优解来实现全局在整体上的最优，其优点在于操作流程简单易懂、操作的相应参数简单、精度高、收敛快。粒子群算法的这些特点以及优势使粒子群成为了当下非常被认可的计算方法，并且在相应领域的学术界得到了高度重视。尽管如此，粒子群算法还是存在着易在早期成熟收敛导致出现局部最优不足的缺陷，以致于出现局部最优解，这对于输电网规划的优化将极为不利。
毋庸置疑，粒子群算法应用于输电网系统中，不但在电网规划方面提高了收敛速度，而且还使输电网系统的运行数据更加精准，运行方式更加快捷。能有效改善传统算法存在的局部搜索能力差、全局搜索能力弱、计算时间过长等方面的缺陷，正是基于此，粒子群算法近几年在电力系统中得到了广泛的应用。然不容忽视的是，粒子群算法也存在着局部最优解的不足，对此，必须对粒子群算法进行改进，以推进其在输电网规划优化中的应用。
2 粒子群算法的改进方案：Pareto最优概念的引入和数学模型的构建
要实现输电网规划的优化，必须克服粒子群算法存在的局部最优解问题，然要实现这一点，必须要使庞大的输电网规划系统的各项目标函数达到最优，各目标函数互相制约。那么采用Pareto最优概念对于输电网规划这样的多目标课题来说，无疑是实现粒子群算法改进的首选。
将Pareto最优概念引入粒子群算法改进之后，在输电网规划中，从最小化输电成本和运行成本出发，以线路投资和系统网损坏值作为目标函数。可以构建基于粒子群算法改进的多目标输电网规划模型。
f1：min
f1：min
其中，f1为路线成本，f2为网络受损率， N1为系统可增线路Ci为之路i的线路单位长度，Z0i为之路i的原有路线，i扩建线路数， r1为支路i的原有线路数。
3 基于粒子群算法改进视角下输电网系统的规划
输电网系统规划的最终目标有两个，一为输电网系统要在系统运行良好的基础上实现费用的最低化，二为输电网系统要在考虑经济效益的同时更注重安全性能。这两个目标要求输电网系统做如下的具体规划：
3.1 坚持输电网供电系统的可持续发展战略
供电系统的可持续发展战略具体说来就是要求供电企业在供电的过程中将供电产值与经济效益相结合，使供电系统形成一个良好运行有序发展的态势。这就要求供电企业能够对供电的前景以及要求进行科学的预测和分析，明确每一个步骤的系统要求，科学规划供电系统。为此，将基于粒子群算法改进的背景下，根基数据模型可以实现线路成本（f1）和网络受损率（f2）的求解，从而为输电网方案的优化提供数据支持。总之，供电系统的优化需要从多方面进行考虑、详细计算并且明确方案，最终实现输电网系统的供电能够在规划的背景下持续不断的可持续发展。
3.2 输电网供电系统的规划要从多个角度考虑
输电网工段系统是供电公司的具体工作，随着新形势下的新要求，供电系统要求被优化。这就要求供电企业能够肩负起相应的责任，在对输电网供电系统优化的过程中结合多方面因素。具体说来输电网供电系统优化需考虑的因素有：公司自身的财务状况、公司在现阶段能够进到最大的供电能力、公司进行供电时的供电质量、供电时的安全性能以及可靠性能。另外输电网的工单系统需考虑的因素还有：输电网供电系统的服务对象是社会上的所有群体，这些群体对用电的最基本要求是供电的质量、供电的安性与供电的可靠性还有最重要的就是电力的价格。这些多方面的因素使得整个输电网系统的规划有一定的实施难度。然对于这一点，粒子群算法改进以其目标多样化的性能完善，可以有效解决这一问题，以实现输电网规划中的多目标最优。
参考文献
[1]程浩忠，张焰.电力网络规划的方法和应用[M].上海：上海科学技术出版社，2002.
[2]许磊，张兰.电网规划算法综述[J].大众科技，2009（09）.
[3]李红升.基于粒子群算法改进电力信息系统的安全研究[J].科技学报，2013，（4）.
作者简介
陈达波（1983-），男，汉，重庆水利电力职业技术学院，讲师，毕业院校及专业：华南热带农业大学电气工程及其自动化。
关键词：市政规划；天然气管网；设计分析
引言
随着我国天然气资源的不断开发和利用，天然气逐步取代了传统的一些常规具有污染性的能源，成为越来越多的城市的主要能源之一，最为显著的是一些利用煤气资源的大中城市也不断尝试着向天然气方向转换。在进行城市利用天然气的工程总体规划中，天然气管网的规划和设计关系到城市市政建设的质量好坏，是市政规划中极为重要的内容。城市的总体规划设计进行的燃气专项总体规划在燃气工程建筑中具有十分重要的指导作用，在这项重要的总体规划中，天然气管网的建设无疑十分重要。城市天然气系统工程的投资相对较大，尤其是在工程建成之后，其扩建和改建的难度较大，对于城市的建设、居民生活等方面有着较大的影响，此外也可能会造成一定的人力、物力和财力的巨大浪费。由此来看，有效保障城市燃气事业的健康发展，以及天然气管网的规范和科学化设计无疑有着极为重要的意义和作用。
1 市政规划中天然气管网规划原则
1.1 管网规划工作的先进性
对于一般情况下的输气管网来说，单单依靠手工计算以及运营经验来进性天然气管网的规划设计是无法有效满足设计需求的，因此这就需要依靠精确的管网模拟软件来进行综合的分析和运算，进而进行对比和分析，选择最佳的改造和扩建的方案。在进行管网的调度时，通过借助相关软件进行在线模拟分析，可以最大程度的有效提高管网的运行效率，进而可以降低所需要的输气成本。
1.2 管网规划工作的整体性
在天然气地面建设工程中可以借助和引进较为成熟的数模软件，也就是可以将地层中的水力动态与地面管网中的水力动态结合成为一个整体，进而对其天然气管网的整体进行有效的把握和了解，综合其中所有的方案，最终确定最优方案。
2 市政规划中天然气管网的规划设计
城市天然气系统工程规划设计的主要目标是，在有效满足用户和工艺设计的基础之上，将天然气系统工程所需要的投资费用降到最低，进而有效保障天然气管网的正常运行，以及天然气管网运行的经济性、安全性以及可靠性。但是由于我国的地形等方面的因素较为复杂，再者由于天然气工程自身的庞大性和复杂性，因此，单纯依靠传统的手工进行设计，很难满足当今日趋复杂的天然气管网设计需求，这就需要借助于先进的计算机技术，来克服传统方法的计算精度较低、效率较低以及规划设计的进一步优化等。
市政规划中天然气管网的系统规划一般主要包括两个主要的问题：第一是管网系统布局的优化问题；第二个则是对管网结构进行确定之后，对管网的工艺参数进行进一步的优化。这两个主要问题相互关联，尤其是在进行天然气管网的规划和设计时，由此来看，必须在规划和设计时主要考虑两者之间的相关性，进而获得最理想的优化效果。市政规划中天然气管道优化一般情况下指的是天然气输配管网的优化情况，这种管网优化一般会针对某一级管网逐级进行，但前提条件是气源条件一定。
3 天然气管网规划发展趋势
3.1 天然气管网规划发展趋势
在天然气管网的规划中，多目标规划相对较为复杂，尤其是关于解的概念问题。在针对多目标优化的问题中，一般情况下各目标函数，其矛盾一般情况下无法进行有效的调和。在管网多目标的优化过程中，假设考虑降低管网投资与降低管网的动力能耗两个目标函数，倘若其所选用的管径相对较小，尽管一定程度上降低了在管道方面的投资，但是这势必一定会增加液体输送的阻力，间接的是管网的动力的能耗增加；相反，如果管径选用的相对较大，尽管这一定程度可以有效的降低动力能耗，但是却不可避免的增加了管道方面的投资。综合以上来看，目标函数自身的冲突性，使得设计方案的优化不能选用这唯一的评价方法，就目前来说，解决多目标规划的方法常见的有三种，分别为价函数法、分层序列法和增量系数法。多目标规划的一个较为显著的优势是，可以从诸多方案中选择最佳方案，此外，还可以通过对替换模型问题的解决方面，为方案的最终选定提供依据。
3.2 天然气规划建议
综合来看，我国的输气管网的规划正处于探索和初级阶段，尤其是市政规划中天然气管网的特殊性，从数学的角度分析，可以将输气管网、供水管网的布局规划划分为网络规划问题，因此，在进行相关的输气管网网络的布局研究时，可以选择性的借鉴供水管网布局规划的一些技巧和成功之处。输气管道在进行输气运转中，其输送具有距离较长、输送压力较高以及口径较大的特点，因此在市政规划中要注意输气管道输送过程中的这些特点，并有效的针对这些特点提出相应的针对性措施，此外，供水管网的布局规划的一些技术和相关的成功之处可以为天然气管网的规划和设计提供一定的参考和指导，但是还是要立足于具体的天然气管网输气的实际情况进行规划，注意天然气管网的规划设计与实际施工的区别和差异。综合现有的诸多研究文献来看，神经网络在管网规划的中具有十分广阔的发展前景和发展潜力，应该逐步深入对其的研究和思考，并在相关研究的基础之上，开发出以神经网络为基础的规划软件。在日后的管网规划和设计规划中，要注重充分利用先进的高科技技术，用科技和知识力量为市政规划中天然气管网的规划和设计提供较为规范和科学的指导，进而有效提高管网的综合利用效率，并在此基础之上，注重与城市的整体环境相适应，提高其整体的美观度，有效对规划设计和生产管理的水平加以有效的提高。
4 结束语
天然气管网的规划与设计是市政规划中较为重要的一项内容，因此必须高度重视天然气管网的规划和设计，进而有效提高其规划和设计的水平。以上关于对市政规划中天然气管网的相关探索，进而更好的指导市政规划中天然气管网的相关设计和规划工作的开展。
参考文献
[1]余伟斌.论市政规划中给排水管网设计的原则[J].中华民居（下旬刊），2013.
[2]陈进殿，汪玉春，黄泽俊.天然气管网系统最优化研究[J].油气储运，2006.
[3]苏欣，袁宗明，张琳，等.城市天然气管网规划现状[J].管道技术与设备，2006.
[4]李余斌，黄坤，苏欣，等.城市天然气管网规划现状[J].油气储运，2006.
[关键词] 配送 车辆路径问题 时间窗 遗传算法
随着经济全球化趋势的加强，科学技术尤其是信息技术的发展突飞猛进，产品营销范围日趋扩大，社会生产、物资流通、商品交易及其管理方式正在发生着深刻的变革，与此相适应，被普遍认为企业在降低物资消耗、提高劳动生产率以外的“第三利润源”的现代物流在世界范围内广泛兴起，目前正在成为全球经济发展的一个重要热点和新的经济增长点。随着传统批发、交通运输、仓储业向现代物流转化，尤其是配送方式的采用，对运输成本和时间的有效控制日渐成为城市配送车辆路径问题的一项重要目标。VRP一直以来都是车辆调度所重点研究的方向。而在城市内采取的配送方式恰恰具备了VRP问题的一般特征和优化调度条件。
一、VRP模型的条件及假设
VRP问题是指按要求用多个车辆从配送中心对顾客进行配给货物。各顾客点的位置和需求量为己知，各车辆的装载质量己知，力求寻找一个好的配送方案，使得总代价最小(车辆尽量少，行车总距离尽量短，总费用尽量低等)，由VRP的定义不难看出，必须满足以下条件及假设：
1.仅考虑位置已知的单一配送中心，所有的配送车辆以配送中心为起点，并最终回到配送中心。
2.每条配送路径上各需求点的需求量之和不超过车辆的装载质量，被配送货物是可混装的货物。
3.每条配送路径的长度不超过车辆一次允许行驶的最大距离，配送中心有足够的资源以供配送，并且有足够的运输能力。
4.各个客户需求和所在地均已知，每个需求点的需求由且仅由一辆车一次送货满足。
5.满足总时间约束与时间窗口。必须在时间区间[ei,lj]访问点i客户，并允许在i处等待，车辆服务的总时间不能超过物流中心的时间约束。
6.多个客户之间存在优先关系，必须在访问客户j之前访问客户i。
二、带时间窗VRP模型的建立
基于文献一文中的模型，并考虑配送系统是一个服务系统，所提供的服务必须能够让客户方便、满意。配送系统的运作成本必须和配送系统其他性能参数综合进行考评，单纯对成本进行评价是没有任何实际意义的。需要关注和努力的是：要在保证配送满足客户要求、提升客户满意度的同时，通过各种技术和管理手段，降低运作成本。因此，本文将建立改进的运输路径模型，在传统的车辆配送成本最小化目标的基础上，兼顾客户对配送时间的要求，使车辆等待和延误时间之和最小化。
（1）
（2）
式中K――车队规模，即总的车辆数目；
k――车辆数目(k=1,2,……,K)；
N――有待访问的总的客户的数目；
O――配送中心；
Q――每辆车辆的容量，这里假设所有车辆同质，容量均为Q;
i,j――顾客数(i=1,2,……,N；j=1,2,……,N)；
T――个很大的数字；
C――每辆车单位运距的运费；
t0――车辆从配送中心出发的时间；
e0――车辆可离开配送中心的最早时间；
ei――到达客户i处规定最早到达时间；
l0――车辆返回配送中心的最晚时间；
li――到达客户i处规定最晚到达时间；
dij――从客户i到客户j的距离；
pj――每个客户单位卸货量的卸载费用；
mi――客户i的货运需求量；
tki、tkj――第k辆车到达客户i、j处的时间；
tij――连接客户i和客户j的行驶时间；
si――客户i处的服务时间；
wi――在客户i的等待时间，wi≥0。
两个决策变量如下：
这个模型通用性很强，经过参数的不同设定，可以转换为其它组合优化问题的数学模型。
三、带时间窗VRP模型的遗传算法求解
在模型的处理上，根据本文提出的模型单位标量不统一的特殊性来选择权重系数变化法，将变化后的多目标函数经分析和试验得出各个子目标函数的数量级大小并确定权重，最后加权化为单目标函数用遗传算法求解。
1.惩罚函数的引入。在以往的对含有时间窗约束的车辆配送系统的研究中，所研究的成本大多仅包含行驶成本，但事实上，还包括其它成本(如装卸搬运成本)，将时间窗约束转化为惩罚函数而体现在模型中。
式中c1――车辆在任务点处等待单位时间的机会成本。
c2――车辆在要求时间之后到达单位时间所处以的惩罚值(c1和c2的大小，要根据实际情况来定)。
2.建立适度度函数。根据遗传算法中适应度函数的特点，需要将原目标函数式变化为：
(4)
(5)
式中A*，B* ――变化后的目标函数值，取值范围为[0，1)；
Amax,Bmax――分别是原始目标函数。
适应度函数因此变化为：f(A,B)=α×A*+β×B*(6)
经过分析和实验发现，A*，B*经过处理后，A*的数量级一般是10-2，B＊的数量级一般是10-1。
3.用遗传算法求解带时间窗VRP模型。本文取α＝0.8,β＝0.2，用遗传算法进行求解。在运用遗传算法求解后，验证了该算法易于理解，对问题的依赖性较小，对其求解的函数要求简单，实现起来简单高效，若参数选择的合理，收敛速度很快，但是遗传参数的控制对于算法的收敛速度影响很大，在参数选择方面有一定难度。虽然文中使用的是根据以往学者经验选定的参数，但计算表明最优解所在“代”数的稳定性不是很好，这也是以后需要进一步研究的地方。
四、结论
在传统的车辆配送成本最小化为目标的基础上，兼顾客户对配送时间的要求，建立了带时间窗的车辆路径优化多目标模型。在对模型的处理上，将两个量纲不统一的子目标函数除以各子目标函数的最大值后使其变成无量纲的函数，并通过权重系数变化法将各个子目标函数线性加权和作为多目标优化问题的适应度函数，使得多目标优化问题转化为单目标优化问题后再用遗传算法求解。
参考文献:
[1]王 惠:引入顾客满意度求解车辆优化调度问题.大连海事大学硕士论文,2006:1～13
[2]盛丽俊:带有时间窗的车辆路径问题的优化研究.大连海事大学硕士论文,2002:13～57
[3]牟燕妮:物流配送中路径优化的选择研究.沈阳工业大学硕士论文,2006:28～41
关键词：电网；规划；启发式；数学式
Abstract: the city is the main center of power system load, the city grid operation is good or not depends on the city grid planning and construction is scientific, reasonable economy or not, for fixed assets under huge power supply enterprise is concerned, the city network planning of power supply enterprises in work in the survival and development of always play a decisive role. This paper introduces the heuristic programming, mathematics type planning two methods, meet and appropriate leading power supply area economic development electricity demand.
Keywords: grid; Planning; Heuristic; Mathematics type
中图分类号：U665.12 文献标识码：A 文章编号：
1电网规划的概念
电网规划就是指电力企业为了顺应社会及经济的发展，努力提高为用户服务的质量，保证电力供应的安全性和连续性而进行的电力系统供应规划。其目标是满足并适度超前供电区域内的经济发展用电需求。保障电网的顺利运行，实现电力企业快速、稳定、持续发展。科学、长远的电网规划，其对地区经济的发展影响重大，而且也关系到电力企业本身的可持续发展。电网规划是电力供应可靠性、经济性的保障。
2电网规划的重要性
随着经济的发展，对电力的依靠程度越来越高，实现电力运营的安全可靠及经济合理，是电力企业面临的永恒课题，而且是企业发展的重要前提和保障。因此，保证电网的正常运行、保证电力供应的连续性和安全I生，保证线路损耗最低，运营成本最低，是电网规划中不容忽视的问题。电力工业的发展比任何一个行业的发展都重要，因为电力行业是其它行业发展的基础，是经济发展的能源保证。
3电网规划的内容和特点
电网规划的内容涉及网络正常运行，也就是在设备完好的前提下，应保证电力供应的正常进行；保证电力供应的安全性，也就是要在进行一些设备故障、检修的情况下，保证供电的可靠性。电网规划包括短期电网规划、中长期电网规划、远景电网规划三种规划形式。
电网的规划和建设具有以下特点：
(a)多目标性。一个规划合理的电网，首先应该满足技术上的先进性，进而达到可靠性和灵活性，同时还要实现经济效益上的增加，以及为社会带来的公共效益，还要保证环保，这是一个大系统、多目标的规划。
(b)不确定性。电网规划一般是以未来一个时期作为规划目标的。对网内电源及负荷的发展水平为固化内容。但是由于电力企业的国家管理的性质，直接受国家政策的影响，受经济发展的制约，人口增加及环境影响，发展的不可预见性极大，经济的
发展，社会的进步，用户对用电质量要求也是越来越高，都是电网规划部门应该给予考虑的问题。
(c)特别是城网由于是政治、经济、人口的相对集中，其电网设计标准较高，在安全与经济合理平衡下，电网运行的可靠性以及安全性要求都非常高。
(d)电网的运行悠长和复杂导致接线的复杂，技术要求高。运行中要保证调度上的灵活性、供电连续性及经济性的特点。
(e)各地都在逐步引进计算机辅助管理，见于电网管理要求的提高，电网的自动化较为完善。
(f)城网的复杂化对配电设施要求较高。对线路、变电所的要求都较高，其占地面积小、容量大、安全可靠、维护量小及满足城市景观要求等多方面，都是城网规划要考虑的问题。见于城市的市容市貌要求，特别在城市中心区使用电力电缆线路，要保持城市上空的洁净及配电变压器的数量。
4电网规划的方法
以往电力规划人员对电网的规划都是依靠经验，然后再经过定性分析作出未来一定时期的用电预测，再根据这个预测的负荷值结合本地情况以及电源情况，设计几种规划方案，最后遴选出一种最佳方案。
4．1启发式规划法
启发式优化方法是一种以直观分析为依据的算法，通常是基于系统某一性能指标对可行路径上的一些参数作灵敏度分析，并根据一定的原则选择要架设的线路。启发式方法又分为逐步扩展法和逐步倒推法。逐步扩展法是根据灵敏度分析的结果，以最有效的线路加入系统逐步扩展网络。逐步倒推法是将所有待选线路全部加入系统，构成一个冗余的虚拟网络，然后根据灵敏度分析，逐步去掉有效性低的线路。启发式方法的优点是：a.简单、直观、灵活、计算量小、计算时间短；b.易于同规划人员的经验相结合；c.应用方便，相对数学方法能够较为准确地数学模拟电力行为。缺点是：a.无法严格保证解的最优性；b.不能很好地考虑各阶段各架线决策间的相互影响。因此，启发式方法不能保证得出的规划方案最优，特别是当规划期较长、待选线数量较多时，所得结果可能与真正的最优方案有很大偏差。 灵敏度方法是最早使用的启发式方法，基本思想是以某种有效性指标与决策变量的灵敏度关系作为启发式的准则，从待选线路中选出当前最有效的线路作为选中的架线。根据定义的有效性指标的不同，该方法可分为两类：一类是基于支路性能指标，根据系统运行时线路功率传输情况来完成线路的选择；另一类是基于系统性能指标，根据线路对整个系统的运行性能指标的影响程度来完成线路的筛选。该方法的优点是：a.原理简单，实现方便；b.易于同规划人员的经验相结合；c.不需要考虑收敛问题，简单易行。缺点是：a.只计算一条线路的指标，没有计及线路之间的相互影响；b.从全局的角度确定架线方案，无法得到全局最优；c.需要大量的灵敏度计算，d.需要对模型进行线性化，精度将受到一定的影响。 模拟退火算法是以马尔科夫链的遍历理论为基础的一种适用于大型组合优化问题的随机搜索技术，算法的核心在于模拟热力学中固体物质冷却和退火过程，采用Metropolis接受准则避免落入局部最优解，渐进地收敛于全局最优。
遗传算法是电网规划采用的一种新的优化方法，它根据优胜劣汰的原则进行搜索和优化，可以考虑多种目标函数和约束条件，特别适合于整数型变量的优化问题。遗传算法利用简单的编码技术和进化机制将规划问题抽象为纯数学问题，便于同时处理整数变量和连续变量，对于大型电网规划问题不需要分解处理，直接将网络的运行计算结果计入评价值，避免了由于分解或线性化造成的误差。此外，考虑到模拟退火算法可以有效防止陷入局部最优解这一特性，将模拟退火法和遗传算法结合的混合-模拟退火算法也取得了不错的效果。总体来说，遗传算法及其在电网规划的应用正处于蓬勃发展阶段，有着极好的应用前景。 4．2数学式规划法
数学优化方法显然是利用计算的方法，对电网规划方案及策略进行数学描述，然后再把这种数学方式转变成有约束的极值问题，通过采用最优化理论进行最后的求解。这种方法的最大优点是求得的解可以保证最优，但是不利的方面是计算量过大，给规划人员带来巨大的劳动量，实际应用中有许多困难。主要原因是：第一，电网规划中要考虑的因素很多，而且问题的阶数也很大，因此建立模型十分困难，即使建立了模型，也很难求解；第二，实际中的许多因素不能完全形式化，通常需要对原问题的数学模型作简化处理，因而可能丢失最优解。和启发式优化方法相比，数学优化方法在理论上更为优越，因此得以广泛研究和发展。数学优化的主要方法有：线性规划、整数规划、多目标规划、混合整数规划和动态规划等方法。
模糊规划是具有模糊参数的一类不确定性规划，它不仅涉及到非线性规划的复杂算法，还用到模糊数学的理论和方法。在模糊规划模型中，通过模糊化处理各种不确定性数据，并通过模糊规则来描述输入输出之间的关系，为模糊规划提供数据。模糊规划法之所以能用于电网规划的原因在于规划中有许多不确定性的因素存在。该方法的优点是：a.能够处理不具有随机性的不确定性问题；b.提供了对研究对象多种属性的选择方案；c.能够处理规划过程中现象和因原诸方面的表示模棱两可的问题；d.算法简单易行，易于在计算机上实现。缺点是：a.在线处理能力差；b.需用其它模糊算子进行模糊优化，当引入其它模糊算子时，势必又导致其模型变成非线性，从而影响计算效率。模糊规划法是目前电网规划中研究的最充分的一种方法。 动态规划的主要思想是将一个问题转化为几个子问题分阶段考虑。动态规划模型中，决策变量在各阶段的取值相互制约，当线路在某一阶段被选中后，就不能在其它阶段中被选中。对于目标函数，长期规划还必须考虑资金的时间价值。目前主要有分支定界法、混合整数规划法、分解协调法、临界可行结构匹配法等。动态规划法的优点是：a.能够避免连续变量法常常遇到的搜索方向错误，迭代不收敛，收敛到局部最优点等问题；b.避免了灵敏度系数的缺陷。缺点是：a.计算时间长；b.对于大规模系统，变量组合较多，易出现维数灾、不易计算等问题。 多目标规划法将电网规划的经济性和可靠性有机地结合起来，使优化方案的综合效益达到最佳，适应了目前电网规划部门的实际需要。同时，多目标电网规划以供应方的开发成本最小和需求方缺电成本最小为优化目标，兼顾供需双方的利益，提高了规划方案的综合社会效益。该方法的优点是：a.在目标函数中可以综合考虑经济性和可靠性要求，将可靠性指标转化成经济形式加入目标函数，求得综合成本最低的网架方案；b.在理论上验证了综合考虑经济性和可靠性的多目标电网规划方法的可行性，并提出了数学模型和求解方法。缺点是适用规模小，适用性差。 结论：掌握电网规划的研究方法及特点，科学地完成电网规划工作，提高供电质量、供电的安全和可靠水平，合理有效地利用资金和节能降损，取得最大的经济和社会效益，乃是各级决策者都十分关注的问题。合理地进行规划可以获得巨大的社会效益和经济效益。因此，对电网规划问题进行研究具有重大的现实意义。
参考文献：
[1]王一，程浩忠．计及输电阻塞的帕累托最优多目标电网规划
[J]．中国电机工程学报．2008(13)．
[2] 陈根军, 王磊, 唐国庆. 基于蚁群最优的输电网络扩展规划
[J]. 电网技术 2001.2.5(6):21～24. [3] 王志刚, 杨丽徙, 陈根永. 基于蚁群算法的配电网网加优化规划方法
购物车(0)