时间：2023-06-20 18:03:17
序论：速发表网结合其深厚的文秘经验，特别为您筛选了11篇多目标优化概念范文。如果您需要更多原创资料，欢迎随时与我们的客服老师联系，希望您能从中汲取灵感和知识！
多目标规划最优的思想起初由法国经济学家V.帕雷托提出，他由政治经济学的角度将不可比较的多个目标转化为多个单目标的最优问题，涉及到了多目标规划的概念。上世纪40年代末，J?冯?诺伊曼和O?莫根施特恩又基于对策论又提出了在多个决策人相互矛盾的前提下引入多目标问题。50年代初，T?C?库普曼斯从生产和分配的活动中提出多目标最优化问题，引入有效解的概念，并得到一些基本结果。同时，H?W?库恩和A?W?塔克尔从研究数学规划的角度提出向量极值问题，引入库恩-塔克尔有效解概念，并研究了它的必要和充分条件。自70年代以来，多目标规划的研究越来越受到人们的重视。至今关于多目标最优解尚无一种完全令人满意的定义，所以在理论上多目标规划仍处于发展阶段。
2、多目标规划方法优化投资组合的应用分析
某生产车间计划在10天内安排生产甲类和乙类两种商品。已知生产甲类商品需要A号配件5组，B号配件3组；生产乙类商品需要A号配件2组，B号配件4组。在十天的计划期内该生产车间仅提高A号配件180组，B号配件135组。同时，我们还知道该生产车间没生产一个甲类商品可获取利润为20元，生产一个乙类商品可获取利润15元。那么，通过以上条件甲乙两类商品分别生产多少可实现利润最大呢？下面我们将各项数据列表如下表1所示：
表1
我们假设，X1和X2分别为甲乙两类商品的生产数量，Z为总利润，以此可以线性规划描述此问题，建立数学模型应该是：
（1）
（2）
其中，X1和X2均为整数。理想状态下，可以利用图解法即可得出公式（1）的最优解为Z=775，X1=32，X2=9。但是，站在车间生产计划人员的角度上将，问题往往比较复杂。
首先，这是一种单一目标优化问题。但通常来讲，一个规划问题需要满足多个条件。例如，例如财务部门的利润目标：利润尽可能大；物资部门的节约资金：消耗尽可能小；销售部门的适销对路：产品品种多样；计划部门的安排生产：产品批量尽可能大。规划问题其本质上是多目标决策类问题，只是因为利用线性规划模型处置，致使生产计划人员不得已从诸多目标中硬性选择其中的一种作为线性规划的数学模型。这样一来，由数学模型目标函数得到的结果可能会违背部分部门的根部意愿，从而导致生产过程受阻，又或者是从生产计划开始阶段就因为某些矛盾而不能从诸多目标中选取一个最优目标。
其次，线性规划问题存在最优解的必要条件是可行解集合非空，也就是说各个约束条件之间彼此相容。但在优化投资组合等实际应用问题中有时候也未必能完全满足这样的条件。如因设备维修养护、消耗能源或其他产品自身原因导致生产计划期内不能提供足够的工时而无法满足计划生产的进度和产量，又或者因投资资本有限的束缚生产原材料的供应不能满足计划产品的需求等等。
第三，线性规划问题的可行解和最优解具有非常明确的价值，这些可行解和最优解都依数学函数模型而定。在实际的投资组合应用当中，决策人发出决策后往往还需要对其决策进行某种修正，主要原因就在于数学函数模型与实际问题之间不尽相同，具有一种近似性，也就是建立数学模型时应对实际应用问题进行简化且不考虑新情况的发生。
计划人员为决策人提供的数学可行解并不是严格意义上的最优解，仅作为决策实现最优的一种参考性计划方案。上世界六十年代初期，由查恩斯（A?Charnes）和库柏（W?w?CooPer）提出的目标规划（Goalprogramming）直接已得到了重视和推广，该法在处置实际应用问题方面承认诸项决策条件存在的合理性，即便多个决策条件是相互冲突的、相互影响的都具有合理性，在做出最终决策中不会强调绝对的最优性。由此看来，多目标规划问题可以认为是一种较之于线性规划问题更切合于实际应用的决策手段。
3、多目标规划方法优化投资组合的常见途径
（1）加权法（或效用系数法）。
加权法（或效用系数法）将投资问题中所有的目标进行统一度量（例如以钱或效用系数度量）。本方法的的基本原理是将多目标模型转化为多个单目标模型。多个目标，有主次不同和轻重缓急不同等区别，最重要的一个目标我们将之赋予为优先因子P1，次重要的目标依次赋予优先因子P2，P3，P4，…，同时约定PK>>PK+1（PK比PK+1拥有更好的优先权）。如果非要将拥有相同优先因子的目标加以区别，我们可以将其分别赋予不同的权系数wj。它的优点在于适用于计算机运算求解可行解和最优解（如线性函数模型可用单纯形法求解），而缺点则在于难以找到合理的权系数（如某高速公路建设投资，在减少建设投资和保证施工质量降低交通伤亡事故率之间难以衡量人的生命价值）。
（2）序列法（或优先级法）。
序列法（或优先级法）并不是对每一个目标进行加权，它主要是按照目标的轻重缓急不同将其分为各个不同等级后再行求解。它的优点在于可规避权系数的困扰，适用范围比较广，各种决策活动几乎都可使用。例如，某公司在决定提拔人员，很多单位主要根据该人员的工作积极性、工作能力和对单位的贡献价值等几个方面予以考虑，这几个方面也会按照先后顺序依次评定，等级不同参考评定的比重也会有所不同。它的缺点在于难以区分各个目标的轻重等级，难以排定优先顺序无法保证最终的求解结果是最令人满意的。
（3）有效解法（或非劣解法）。
中图分类号：TP301.6文献标识码：A文章编号文章编号：1672-7800（2013）012-0067-04
作者简介：马春连（1988-），男，安徽理工大学理学院硕士研究生，研究方向为智能计算；许峰（1963-），男，安徽理工大学理学院教授，研究方向为波谱学和智能计算。
0引言
在科学研究和工程应用中，许多决策问题具有多目标的特点和性质，它们需要同时满足几个相互冲突的不同目标，即无法使各个目标同时达到最优，这类问题称之为多目标优化问题（Multi-objective Optimization Problem， MOP）。多目标优化问题存在一个最优解集合，其中的元素称为Pareto最优解。
由于多目标进化算法在优化控制、挖掘数据、设计机械、移动网络规划等领域的成功应用，使得学术界兴起研究进化算法的热潮。自上世纪80年代以来，人们已提出多种多目标进化算法，比如Srinivas的NSGA，Zitzler的SPEA，Knowles的PAES以及Deb的NSGA-Ⅱ等。
近年来，一些新的进化算法被用来求解多目标优化问题，如蚁群算法、粒子群算法、免疫算法、分布估计算法等。
上世纪90年代末，人工免疫算法开始兴起，其思想源于生物的免疫系统，它借鉴了免疫系统的功能、原理和模型并用于进行寻优搜索。由于现在还不能充分认识免疫机理，所以有关免疫算法的研究基本集中在其它算法。我们用免疫原理来改进并构成新的算法，比如免疫神经网络、免疫遗传算法等。人工免疫系统算法的自身研究成果并不多，主要有基于克隆选择原理的克隆选择算法和基于阴性选择原理的阴性选择算法等。
多目标优化; 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.
中图分类号：TM352 文献标识码：A 文章编号：2095-1302（2016）10-00-02
0 引 言
一直以来，人们都想实现模拟集成电路设计的自动化，但考虑到模拟集成电路性能指标多，各性能指标间互相影响等因素，使得模拟集成电路的自动化进程远远落后于数字集成电路，模拟集成电路已经成为制约集成电路发展的瓶颈。随着技术的发展，片上系统将模拟集成电路与数字集成电路整合到一块芯片上。但人们对模拟集成电路的自动化研究却从未中断过，同时也取得了一些成果，其中基于优化的设计方法因适用范围广而受到了人们的青睐。
基于优化的设计方法将模拟集成电路的设计看作是多目标优化问题，电路设计时的性能指标如增益、带宽、相位裕度等就是多目标优化的目标函数。通过多目标优化算法求解出电路目标空间的Pareto前沿，该前沿就是电路各种性能指标折衷后的最优前沿，允许电路设计者从一组相互冲突的设计指标中做出最佳选择。
基于优化的设计方法的核心是多目标优化算法，解决多目标优化问题的常用算法是加权和算法[1]，该算法容易理解、操作简单，但是该算法不能求出Pareto前沿上位于凹区间内的解，而当权值均匀分布时，Pareto前沿上凸区间内的解分布不均匀[2]。本文采用了自适应加权和算法，该算法在加权和算法的基础上改进而来，克服了加权和算法的上述缺点。
1 自适应加权和算法原理
自适应加权和算法[3]的权值系数没有预先确定，而是通过所要求解问题的Pareto前沿曲线获得。首先用传统加权和算法产生一组起始解，然后在目标空间确定需要细化的区域。将待细化区域看作可行域并且对该区域施加不等式约束条件，最后用传统加权和方法对这些需要细化的子区域进行优化。当Pareto前沿上的所有子区域长度达到预定值时，优化工作完成。
图1所示的自适应加权算法与传统加权和算法进行了对比，说明了自适应加权和算法的基本概念。真正的Pareto前沿用实线表示，通过多目标优化算法获得的解用黑圆点表示。在该例中，整个Pareto前沿由相对平坦的凸区域和明显凹的区域组成。解决这类问题的典型方法就是加权和算法，该算法可以描述成如下形式：
上式中描述的是两个优化目标的情形，J1（x）和J2（x）分别为两个目标函数，sf1，0（x）和sf2，0（x）分别为对应的归一化因子，h（x）和g（x）分别为等式约束条件和不等式约束条件。
图1（a）为采用加权和算法后解的分布，可以看出大部分解都分布在anchor points和inflection point，凹区间内没有求出解。该图反映了加权和算法的两个典型缺点：
（1）解在Pareto前沿曲线上分布不均匀；
（2）在Pareto前沿曲线为凹区间的部分不能求出解。
因此尽管加权和算法具有简单、易操作的优点，但上述缺点却限制了其应用，这些固有缺陷在实际多目标优化设计问题中频繁出现。图1描述了本文所提出的自适应加权和算法的总体流程以及基本概念。首先根据加权和算法得到一组起始解，如图1（a）所示，通过计算目标前沿空间上相邻解的距离来确定需要进行细化的区域，如图1（b）所示，该图中确定了两个需要进行细化的区域。在确定需要进行细化的区域分别在平行于两个目标方向上添加额外的约束，如图1（c）所示，在该图中向减小方向J1添加的约束为1，J2减小方向添加的约束为2。对细化后添加完约束的区域用加权和算法优化，得出新解，如图1（d）所示，其中加权和算法求解最优解时采用Matlab中的fmincon函数。从该图中可看出，细化区域内产生了新解，Pareto前沿上解的分布较之前更加均匀，且求出了凹区域内的解，继续细化能够找出更多的解，Pareto前沿上的解也将分布地更加均匀。自适应加权和算法的流程图如图2所示。
2 两级运放设计实例
以一个带米勒补偿的两级运放[4]为例，说明自适应加权和算法的多目标优化设计。两级运放电路图如图3所示。
电路的各项性能指标如表1所列。
电路优化过程中采用工作点驱动[5，6]的设计方法，电路的设计变量为电路直流工作点上一组独立的电压、电流。电路性能通过方程获得，但方程中的小信号参数通过对工艺库进行模糊逻辑建模[7，8]得到，使得计算速度提高的同时保证了计算精度。两级运放电路的优化结果如图4所示。
图为算法迭代五代后的优化结果，由图可以发现，经过五代的优化迭代，求出的最优解在Pareto前沿上分布均匀。在同一电路中，单位增益带宽的增加与摆率的增加都会使功耗增加，而电路功耗降低导致的结果是电路的面积增加，或通过牺牲面积来换取低功耗，牺牲面积换取电路的带宽增加。这些结果与电路理论相吻合，同时也再次说明了模拟电路设计过程中的折衷以及模拟集成电路设计的复杂性。
3 结 语
自适应加权和算法能求出位于凹区间内的最优解，并且最优解分布均匀。本文通过两级运放电路验证了算法的优化效果，最终得到了满意的优化结果。
参考文献
[1]阳明盛，罗长童.最优化原理、方法及求解软件[M].北京：科学出版社，2010：92-94.
[2]I.Das， J.E. Dennis. A closer look at drawbacks of minimizing weighte dsums of objectives for Pareto set generation in multicriteria optimization problems [J]. Structral Optimization， 1997（14）：63-69.
[3]I. Y. Kim， O. L. de Weck. Adaptive weighted-summethod forbi-objective optimization：Paretofrontgeneration [J]. Struct Multidisc Optim， 2005（29）：149-158.
[4]Razavi B. Design of analog CMOS integrated circuits [M]. New York： Mc Graw-Hill， 2001.
[5]陈晓，郭裕顺.工作点驱动的模拟集成电路优化设计[J].杭州电子科技大学学报，35（6）：18-22.
中图分类号：TM732 文献标识码：A 文章编号：1671－7597（2012）0220135－01
在发电权的交易上，很多文章主要以买卖双方报价为主，本文为体现发电调度的节能减排要求，将煤耗率和价格这两个参数结合起来，提出了基于能耗和效益综合最优的多目标交易模型，并使用Pareto最优的方法来对多目标进行求解。
1 发电权交易模式
发电权是一种商品，发电权市场是双边交易市场，撮合交易是组织发电权交易的常见模式。
2 发电权交易成本
本文将交易成本分为两部分，固定成本 和电力网损成本 。固定成本包括组织发电权的固定佣金，管理费用，行政费用等，电力网损成本是开展发电权交易前后整个网络潮流变化所带来的成本。
3 发电权交易模型设计
3.1 发电权交易模型
基于文献[3]提出的效益最优、文献[6]提出的能耗最优的发电权交易模型，本文提出了基于能耗和效益综合最优的发电权交易模型。
3.2 基于煤耗和效益综合最优的模型
基于煤耗和效益综合最优的发电权交易的目标函数为：
其中C表示Pareto前沿所组成的集合， 买方i和卖方j 的交易量，
为卖方j出售的电量， 为买方i购买的电量， 为第i个买家申报的报价， 为第j个卖家申报的报价， 为买家 和卖家 之间的交易成本，
和 是参与交易的机组 和机组 的煤耗率函数。 表示发电权交易产生的社会效益， 表示发电权交易所节约的煤耗量。
4 Pareto最优的概念及求解
在3.2所提到的煤耗和效益多目标综合最优模型，在数学上称为多目标优化问题，关于多目标最优有很多种求解方法，本文使用Pareto最优的方法来对多目标进行求解。
4.1 Pareto最优的概念
一般地，多目标优化问题有如下形式：
其中Ω表示所有可行解的集合， 表示k个目标函数。
4.2 Pareto最优解的求解方法
多目标优化Pareto最优解集的求取可分为两大类：传统算法和进化算法。PSO粒子群优化算法是最近兴起的一种进化计算方法。
PSO算法的标准形式如下所示：
其中 和 分别表示第 个粒子在第 次迭代中的位置和速度；
表示第 个粒子的个体最优解； 表示全局最优解； 是之间的随机数； 是学习因子，用于控制收敛的速度； 是惯性系数。
本文在PSO算法基础上，提出一种基于动态Pareto解集的PSO算法（Dynamic Pareto Warehouse-based PSO，DPW-PSO），利用这种算法可在较小的初始种群规模下，产生大量的Pareto最优解而并不显著增加计算量。
5 DPW-PSO算法求解多目标发电权交易问题
本文使用Pareto最优的方法、DPW-PSO算法对多目标进行求解，求解过程是先通过随机算法大致得到（U，F）这个二维函数的Pareto前沿，然后在Pareto前沿上选出一些解和它们对应的交易方案，这些交易方案在某种程度上来说都是最佳的。
6 发电权交易算例分析
下面是对某电网发电权交易的算例分析，选取电网典型运行方式下的数据，分别按效益最优、能耗最优、效益和能耗综合最优三种模型进行仿真计算。表1是某电网典型情况下各机组的发电出力和煤耗率。
A6电厂发电不足，A1-A5电厂代其发电，表2为发电权交易在效益最优模型、煤耗最优模型、煤耗和效益综合最优三种模型下所产生的社会效益、消耗的煤的总量以及电网网损的变化。
对计算结果分析可知，多目标最优有多个解，这些解得到的交易方案在某种程度上来说都是最佳的，电力公司可以根据交易结果对发电权进行安全校核，每次交易的完成都以电网通过安全约束为标志。
7 结论
基于煤耗和效益综合最优的发电权交易模型，其Pareto最优解为一个解集，这表明决策者有多组相对而言都比较理想的交易方案可做选择，这些交易方案效益和降低煤耗不一样，但总体是朝着煤耗减少和社会效益增大的方向变化。因此，研究与市场机制相协调的电网节能降耗发电权交易机制，实施“以大代小”、“以煤代气”发电权交易，对于充分发挥其节能减排的优势，满足发电调度的节能减排要求具有十分重要的意义和广阔的应用前景。
参考文献：
中图分类号：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.
中图分类号：TP311.13文献标识码：A 文章编号：1672-3791（2015）01（a）-0000-00
Curriculum Scheduling Algorithm based on Pareto Multi Object Genetic Algorithm
HE Yi-xuan
Class 12 Grade Three， Haizhou Senior High School of Jiangsu Province， Lianyungang 222023， China
Abstract： Curriculum scheduling for primary school and high school should not only to resolve the arrangement of time， room and personnel， but should also to optimize some other factors， and these factors need optimized simultaneously. For the weak point that traditional multi objective optimization algorithm should have priori knowledge before optimization， we propose a curriculum scheduling algorithm based on Pareto multi object genetic algorithm. Finally， an experiment is given to verify our algorithm.
KeyWord： genetic algorithm； multi object； Pareto； curriculum scheduling
课表编排系统的设计是整个教务管理信息系统的设计难点。除了要解决时间、空间、人员的安排问题，排课需要考虑的因素和指标还比较多，如课程安排的均匀程度、重要课程尽量安排在上午等。这些指标往往需要同时优化，即多目标优化问题[1-2]。由于往往多个目标不能同时最优，对各个目标的偏好不同，得到的优化解也不同。传统方法是将多目标优化问题的多个目标函数通过适当方法（如加权法等）转化为单目标优化问题进行处理。该方法的缺点需要对优化问题掌握一定的先验知识，否则难以确定加权系数。
针对上述问题，本文采用Pareto多目标遗传算法来进行优化计算。该方法无需对优化的各个目标掌握先验知识，并具有极强的鲁棒性、全局寻优能力和隐含的并行性等特点，使得该方法成为多目标优化方法中的一个研究热点。
1 排课系统设计
课表的安排除了要考虑教学计划、教师资源以及教室使用情况，同时还要以其他教学要求来评判课程安排的优劣，如：
（1）课程分布均匀，避免课程都集中在某一两天的情况；
（2）重要课程尽量安排在上午；
（3）对于一周多节的课程要尽量保证同一门课程两节之间时间间隔较长。
本文设定一个班级一天排6节课，上午排4节课，下午排2节课，即一周有30节课，因此每一节上课时间的变量在整数区间（1-30）上取值。量化排课优劣程度的方法如下描述：
（1）为了使重要课程尽量安排在上午，首先将每一节课的值进行修正：一周有n节课时，按先后顺序记课的值分别为1，2，…，n。其中，式中，若该节无课，则当前值设为0。假设排课结果为x1，x2，…，xn，评价函数f1（X）如式（1）所示：
（1）
由式（1）可以看出，当f1（X）的值越小时，课程就越集中在上午。
（2）对于使课程安排均匀，我们统计一周每天安排的课程数目，并求这5天课程数目的方差f2（X）。那么，方差f2（X）越小则排课越均匀。
（3）对于每周要安排多节的课程，要使同一门课程两节之间间隔的时间尽可能长，我们计算同一门课（每周需要安排多节的课程）两次值的相差绝对值。那么，一周内所有课的相差绝对值之和f3（X）越大，则课程安排越合理。
2 多目标遗传算法优化
传统多目标优化方法是将多目标优化问题转化为单目标优化问题。如线性加权法，将上述三个目标函数f1（X），f2（X），f3（X）按其重要程度给出一组权系数w1，w2，w3，则评价函数的最优解如式（2）所示：
（2）
但该方法要求对优化问题掌握先验知识时。而本文采用Pareto多目标遗传算法来进行优化计算。无需掌握先验知识，
Pareto占优定义如下：假设x1，x2∈某一可行域Ω，x1被x2占优是指对部分i，有fi（X）≥fj（X），而对其他的j≠i，fi（X）> fj（X）。Pareto最优解x0是指在Ω中不存在任何x占优于x0。
从定义中可知，Pareto最优解不是唯一的，而是由许多“非劣解”（非劣解，是指在不降低其它性能指标的前提下，再也不能提高该性能指标）组成的解集，因此群体搜索策略（如遗传算法）是非常合适的求解方法。
遗传算法是通过对一代群体按照寻优目标进行一系列的选种、交叉、变异而使下一代群体从整体上更接近最优解[3]。本文将选择算子中引入Pareto占优概念，即Pareto遗传算法。
本文Pareto遗传算法操作流程如下：
输入：函数h（X）；权系数w1，w2，w3；初始群体
Step 1：设小生境距离；
Step 2：在每类部分群体中选Pareto占优个体；
Step 3：交叉；
Step 4：变异；
Step 5：生成下一代群体；
Step 6：检查评价优化结果是否收敛。如没有，
返回步骤（2）；如已收敛，执行-结束。
输出：优化结果（即最后一代群体）
相比较以往传统遗传算法，本文算法改进措施如下：
（1）根据种群中占优的个数多少来赋予个体相应适应度。
（2）在每代中采用部分种群来决定占优的情况。而且，当两个个体之间彼此互不占优的时候，其结果通过适应度共享来决定。由于本文没有在整个种群中使用Pareto意义选种，而是在每代中只采用部分种群，因此其能快速并产生较好的Pareto意义占优解。
（3）相比较传统遗传算法，本文算法还引入小生境技术[4-5]。该技术可以防止基因漂移，使群体均匀分布在Pareto最优解集中。由于一周有5天课程，本文将个体划分为5类，即从这5个类当中选出适应度较大的个体作为该类的代表组群。
3 实验结果及分析
假设需为某班排课，共6门课程，英语、语文、数学等。其中英语、语文、数学每周需要安排6节，其他课程每周安排2节。
我们首先通过随机方法生成30次排课解作为初始群体，以上述f1（X），f2（X），f3（X）的极值作为优化目标。根据遗传算法进行优化计算，设突变率为1%，经过100代进化，结果如表1所示：
表1 Pareto多目标遗传算法优化结果
初始群体 100代群体
均值 标准差 均值 标准差
f1（X） 10.13 1.29 7.62 0.22
f2（X） 1.34 0.03 1.11 0.01
f3（X） 132.24 15.21 168.12 1.25
由表1可以看出，尽管实验没有提供对优化目标的先验知识，但通过Pareto遗传算法优化后，3个优化目标f1（X），f2（X），f3（X）都得到同时优化，并且优化结果比较理想。
4 结束语
该文针对传统多目标优化排课算法需要先验知识的缺点，将Pareto多目标遗传算法应用到排课系统中，并实验证明该方法的有效性。
参 考 文 献
[1] Tan K C， Lee T H， Khoo D， and et al. A multi-objective evolutionary algorithm toolbox for computer-aided multi-objective optimization[J]， IEEE Transactions on Systems， Man and Cybernetics： Part B （Cybernetics）， 2001， 31（4）：537-556.
[2] Vieira D A G， Adriano R， Vasconcelos J A， and et al. Treating constraints as objectives in multiobjective optimization problems using niched Pareto genetic algorithm[J]， IEEE Transactions on Magnetics， 2004， 40（2）： 1188-1191.
【关键词】协同进化 多目标算法 多目标优化
协同进化算法是基于协同进化理论出现的一类新的进化算法，其在传统进化算法强调个体与个体之间因环境原因所产生的竞争的基础之上，进一步考虑多个种群之间、种群与环境之间的在进化过程中的协同作用。目前通常使用的协同进化算法主要可以分为两类：以种群竞争的方式加速算法收敛和使用种群合作的方式保持种群多样性。但是这两种方式都只是强调了协同进化中的一部分，都存在其不足。在大自然生物们个体之间的协同进化过程中，竞争、合作这两种相互矛盾的关系往往都是同时存在的。只有强者才具优先的权利，以遗传下自身的基因，其他处于弱势的个体会团结起来与其对抗，达到留下自身基因的目的。刘静在她的博士论文《协同进化算法及其应用研究》中基于种群竞争和合作思想构建了MOCEA（Multi-objective Coevolutionary Algorithm），通过竞争特性算子――吞并算子来达到使得优秀的基因得到广泛的传播和保持种群基因的多样性，并得到很好的效果。但由于刘的思想仍然是主要依靠种群合作来达到加速收敛的目的，其所采用的竞争特性算子――吞并算子对其算法进化并没起到决定性作用。
1 算法设计
1.1 算子设定
1.3.1 测试函数一
该测试函数为一带约束条件两目标函数，其主要用于测试多目标优化算法在pareto前沿的收敛的能力。
从表3.1可以看出CCEA算法在Spreed这个指标上具有很大的优势，从图3-1也可以看出CCEA算法比NSGAII算法在这个测试函数的计算上具有更大的优势。
1.3.2 测试函数二
该函数为带约束的两目标测试函数，在其约束条件内含有两个可调变量a、b，本文选取a=0.1，b=16来对CCEA算法和NSGAII算法进行测试。该函数的PFtrue曲线为三段相互之间不连续的曲线，在对多目标优化算法测试时，通常对中间一段进行关注，其主要特点在于这个区段的部分点不易被搜索到，性能较差的算法在这部分通常表现为断开。该函数因此可以检测算法在pareto前沿的搜索能力。
由表3.2可以看出CCEA算法除了在GD这个指标上占优势以外，在其他两个指标上并不占优势，甚至在Spreed这个指标上略有不如。但从图3-2看出来在中间一段曲线上CCEA算法搜索出来的为一条连续曲线，而NSGAII算法在这部分是断开的，这可证明CCEA算法对pareto前沿解的搜索性能要强于NSGAII算法。
2 结论
中图分类号：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前沿区域。缺点是该方法在一些情况中会很快失去种群多样性。
三、总结与展望
与传统的进化算法不同，文化算法只提供了一个进化模型，任何基于种群的进化算法都可为文化算法的群体空间提供种群，如遗传算法、进化规划、进化策略等。
相比其他较成熟的进化算法，文化算法的研究才刚刚起步，应用的范围也比较少，因此有必要对文化算法进行深入研究，将其应用到更多的领域。
参考文献：
区域经济规划理论概述
（一）区域经济规划的概念
所谓区域经济，它是建立在对区域经济发展的研究之上的。研究区域经济发展的根本目的，就是为了解决区域经济如何实现增长的问题，也就是如何生产更多的财富、创造更多的GDP、如何提高区域人民生活水平和人均收入等问题。按照古典经济学理论分析，区域发展的三个最基本的要素就是：资本、劳动力和技术。而要想将要素转化为实际的财富，需要一定的条件和方式，而一个健全的政策、机制和环境，则进一步决定了各类要素如何在各区域发展中实现其作用以及作用的大小。
区域经济规划就是在时间上提前对区域经济发展的一个统筹规划。具体来讲，它是指一组生产要素现在和未来在特定区域的配置或部署问题，根据目前已有的要素组合，综合评估发展条件以及未来环境变化的可能性，合理的安排在未来时期要素应该如何组合、如何配置才能达到预期的发展目标。所以，区域经济规划主要是以当前已有的要素组合和发展环境条件等进行的一项决策活动，具体实施这种决策则是未来的活动。如果这种未来是将来很长一段时间，这就需要解决战略问题，对未来发展起到导向作用；相反如果是一个不长的时间，那就需要制定行动的具体方案，有效指导将来的发展行动。
另外，区域经济规划和区域产业布局是容易被混淆的两个概念，被混淆的原因是两者有许多共性。产业的空间布局是以致富最小的生产成本为目的进行的，例如以运费最小为标准来选择最佳区位，或企业如何选择分布地点导致利润最大化等。而区域经济规划的任务则主要为了解决以下三个问题：第一，在什么时间、投入多少、投入哪类要素？第二，各类要素在规定的时间内在什么样的地方组合？ 第三，以什么样的方式、什么样的机制和什么指导思想去组合？两者虽有诸多相同，但也有本质上的区别。
（二）区域经济规划的基本内容
顾名思义，区域经济规划的对象当然是区域。在很大程度上，它的基本职能就是从整体上进行综合性协调，所以它绝不同于部门规划、行业规划和专题规划等规划活动。区域经济规划涉及的范围不仅囊括了经济、人口、社会、环境、资源等方面，而且还需要对条块之间、块块之间以及区内区外之间进行协调规划。除此之外，它还需要对不同的产业部门之间、主导产业和配套产业之间进行协调规划。总而言之，区域经济规划是一项综合性的规划，综合性规划下又包含了许多不同层面形成的单向规划，综合规划还必须考虑到单项规划相互之间的协调关系。
所以，区域经济规划的内容是十分丰富和广泛的。目前从国家已作出的相关区域经济规划中可以看到，区域经济规划主要包含了以下内容：国土开发整治的目标和任务；自然条件和国土资源的综合评价；自然资源开发的规模、布局和步骤；社会、经济现状分析和远景预测；国土整治和环境保护；人口、城市化和城市布局；综合开发的重点区域；交通、通讯、动力和水电等基础设施的安排；宏观经济效益估价；实施对策和措施。改革开放以来，随着中央财权事权的逐步下放，地方自也日益扩大，区域经济规划的内容在实践中也不断地丰富，并且日益区域化。
（三）区域经济规划的目标
区域经济规划的目标不是单一的，而是形成了一个目标体系。这个目标体系主要包括三个目标，即经济增长方面的目标、社会进步方面的目标和生态环境改善方面的目标。这些目标可能是相辅相成、相互促进的关系，同时也可能存在着相互矛盾和制约的一面。比如经济增长目标和就业目标，为了取得高速的经济增长，就需要大力推进工业化的进程，优先发展重工业和高科技产业，推进技术创新与技术进步。而高科技产业是资金密集型产业，而且随着技术的飞速进步，生产效率和投资利用率也进一步提高，这样就限制了劳动就业的增加。反过来，如果增加了就业人口，劳动力数量增多，人均固定资产减少，劳动生产率自然相应下降，经济增长就受到了限制和影响。再比如经济增长和生态环境目标，如果可以提高对二者协调发展的关注度，那么经济增长则有利于生态环境的保护和改善，节能减排，经济增长也可以提供更多的资金改善生态环境；而如果忽视了生态环境，只将经济增长作为发展的唯一目标，就会造成对生态环境的严重破坏，环境质量也会不断下降。
（四）区域经济规划的影响因素
1.本国经济发展的历史背景。从很大程度上来说，区域经济发展的状况和规划是由国家的宏观经济发展规划所决定的。那么，各省区战略地位的确定，各地区之间的区域分工，以及各省区和区域未来的发展方向，国家在宏观布局时早已做好了规划和安排。所以，各地区在进行本区域的经济规划时，必须以国家的宏观经济规划为前提，在此基础上制定自身的区域经济规划。例如，国家相继提出的沿海各省对外开放政策、西部大开发战略、振兴东北老工业基地战略以及中部崛起战略等。
2.规划区域的自然状况。一个地区的发展很大程度上依赖于该地区的自然资源等物质基础。所以，在制定规划时，要充分考虑到地区的自然资源状况，充分发挥自身自然资源状况的优势，然后在此基础上选择主导产业以带动区域经济的发展。比如在新疆地区，石油资源和煤炭资源比较丰富，同时也是重要的棉花产地，这些都是国家的战略物质，所以在制定该地区的经济规划时，一定要围绕能源、棉花等这些优势资源做文章，以期通过这些优势来带动当地经济发展。
3.规划区域的经济资源状况。除了规划区域内的自然资源状况对区域经济规划有重要的影响，经济资源状况也起着十分重要的作用。
首先，人口数量和劳动力资源。劳动力作为生产要素之一，自然是经济发展不可或缺的，所以具有丰富的劳动力资源，不仅可以有效降低人均劳动力成本，也可能提供大量的高素质人才，这些都可以有效带动区域经济发展。
其次，市场对区域经济规划的影响。在制定区域经济规划时，一定要事先调查分析当地市场的需求和供给。如果供过于求，而区域居民有效需求不足，必然导致经济滞胀，产生大量失业人口，不利于当地经济的发展与稳定；如果供不应求，又必然导致地区通货膨胀，同样不利于经济发展。所以制定区域经济规划时，一定要在充分了解当地市场供给需求的基础上进行。另外，对于某些特殊产业，还需要注意其空间位置的布置，例如农产品的生产、第三产业的发展，这些都对市场有着比较强烈的依赖，所以应该大力发展这些企业，进而带动整个区域经济的发展。
最后，区域内以及周边的产业集群状况。通过产业在空间上的聚集，集群内部的企业之间交流增多，在区域内也比较容易形成一条完整的产业链，再加上政府对一些配套设施的建设，可以形成一整套的区域核心竞争力。同时，产业集群也有着比较明显的经济外部性，通过这种外部规模经济和外部范围经济，有效带动周边经济的发展，进而带动整个区域经济发展。另外，相关产业共同发展的同时，各产业之间会加强彼此技术和经验的交流，通过这种交流与扩散达到技术的创新，继而实现产品的创新、产业的升级。
多目标最优化方法简述
（一）一般多目标最优化模型
所谓一般多目标最优化模型，是对于一个需要决策的问题，存在多种决策选择，而所要达到的目标不分主次，这样就可以构建成一个数学函数模型，其中自变量就是各种决策的变量，因变量就是目标函数。除此之外，对于自变量，也就是决策的选择存在一些限制，这就形成对自变量的约束函数。
每种不同的决策变量的组合对应一个目标函数。对于一个决策变量组合，如果它能满足其所对应的目标函数不大于其他任何决策变量组合对应的目标函数，则称这个组合是该多目标最优化模型的一个有效解；而如果它能满足其所对应的目标函数严格小于其他组合对应的目标函数，则称这种决策组合是该多目标最优化模型的一个弱有效解。显然，若一个决策变量组合是有效解，则它一定是弱有效解。
一般来说，一个多目标最优化问题有无穷多个有效解，它们并不都是决策者满意的解，只有决策者满意的有效解才是问题的最终解。得到最优解一般有两种方法：一种是评价函数法，即先求出大量的有效解，然后根据决策者的意图找出最优解；另一种是交互法，即通过分析者与决策者的相互沟通，逐步地达成一个最终解。
（二）分层次多目标最优化模型
这类模型较一般多目标最优化模型的特点是：在约束条件下，各个目标函数不是同等地被最优化，而是按不同的优先层次先后地进行最优化。在构建数学函数模型时，也需要按照不同的优先层次来设定目标函数。对于分层多目标最优化问题的求解，就需要按照模型所要求的有限层次逐层地进行求解，最后一定就可以获得最优解，即使这种最优解不是统计意义上的绝对最优，但一定是可以满足决策者要求的最优解。
区域经济规划的多目标最优化实践
（一）建立数学模型的步骤
为了正确处理各局部之间的关系，加强局部的协调发展，注意各地区及部门之间的综合平衡，就必须运用科学的方法来建立经济数学模型，把抽象的规划问题具体化。最后利用严格的数学方法，求得最优解，以满足区域经济规划决策者的要求。
建立经济数学模型主要有以下几个步骤：第一，定义和识别。了解问题的真实背景，即规划区域的历史背景、自然资源、市场资源状况；明确建模的目标，确定决策者规划经济所需要达到的目标，如经济增长、就业和生态环境等；掌握必要的数据资料，建模前必须获得当地的相关数据，如人口数据、市场需求与供给等数据。第二，数据预处理。在已经了解问题背景，明确了建模目的和掌握了必要的数据资料后，就需要提出一些恰当的假设，对问题进行必要的简化。第三，估计。通过综合的分析所获得的资料，在已有的假设基础上，利用适当的数学工具合理刻画各变量之间的关系，形成目标函数和约束条件，初步建立数学模型。第四，验证。将所建立的模型与实际情况相比较，包括目标函数与决策者意图的比较、约束函数与实际条件的对比等，以此验证模型的正确性。
（二）实现最优化的建模原则
实现最优化建模需要遵守以下原则：
一是能充分有效地发挥区域优势。前面已有介绍，利用地区自然资源等优势可以加快地区经济发展。
二是从区域实际情况出发，建立适当的经济数学模型。模型中需要考虑的因素很多，要全面协调各种因素，保证模型与区域实际相符。
三是模型必须考虑到各部门均衡发展和区域间相互协调。只有各部门均衡发展、步调一致，才能实现最终的和谐发展。
四是要有利于环境保护，坚持可持续战略思想。虽然经济发展与生态环境有矛盾之处，但是也更要注意这二者之间的协调。
结论
多目标最优化理论在经济、管理、政治方面的运用，可以有效合理配置和最优化。在区域经济规划时，引入多目标最优化的方法，可以根据实现各种方案目标所需要的区域资源与条件来最终确定最优解，这样的方法既科学，也符合实际情况，还能有效促进区域经济快速增长，社会协调发展。本文简要介绍了区域经济规划的相关理论和多目标最优化方法，并将二者结合起来，以期能够将这种方法运用到实际的区域经济规划中去。
参考文献：
1.唐永才.90年代国内多目标规划研究述评[J].荆门职业技术学院学报，1999（3）
本文是在文献12的基础上，针对算法的种群初始化操作，引入了超启发方法；在算法的克隆操作中，设计了一种新的资源分配模型，是一种关于多目标考试时间表问题的NNIA改进算法，所以除种群初始化操作与克隆操作外，算法中的其他所有操作算子，以及算法流程与文献12完全相同，算法流程如图1所示。
1.1资源分配模型NNIA是一种经典的进化多目标优化算法，在此算法的运行过程中，只是采用少数的非支配个体进行操作，考虑到本文采用的多目标考试时间表的建模方式，在算法运行过程中，当出现非支配解数量不足的情况时，必然会对NNIA框架下的算法性能产生十分明显的影响。顾本文在采用NNIA算法框架的基础上，在个体克隆阶段，设计了一种基于博弈论的资源分配模型，通过动态控制优势个体的克隆数量手段，更加合理的分配计算资源。在资源分配模型中，根据非支配排序关系，待克隆的个体首先被划分为不同的等级（R1,…,Rn）。其中，Ri代表了第i等级的个体的数量。通常情况下，R1中的个体优于其他个体。根据R1个体在所有待克隆个体中所占的比例r，将资源分配模型分解为早期模型、中期模型和后期模型。算法在运行过程中，根据不同的模型，采用相应的克隆策略。早期模型(r≤1/3)：在此阶段只有很少的优秀个体（R1个体）。根据博弈论的相关概念，需要抑制R2中个体的克隆数量，以保证其无法影响到R1中的个体。如公式(5)所示，其中Si表示原始的克隆尺寸，Mi表示资源分配模型计算过后，克隆后第i级别的克隆规模。
1.2基于超启发方法的种群初始化许多学者的研究及仿真实验表明[1]，基于图着色的超启发方法十分适合处理单目标考试时间表问题。采用超启发方法拥有更大几率快速找到可行解或潜在的优势个体。针对本文所面对的多目标考试时间表问题，若能快速得到可行解或潜在的优势个体，在固定的算法迭代次数的条件下，则更加有利于得到更好的结果。因此，本文采用基于图着色的超启发方法生成初始种群。其中，初始种群是由一定数量的初始解(时间表)构成的。首先，随机产生由不同图启发算法构成的启发式链表，根据启发式链表，产生初始解（考试时间表）。在产生初始解的过程中，每当产生一个新的考试时间表示，通过这些不同的启发式算法，可以产生一个考试科目安排顺序，在不违反硬约束的条件下，根据考试安排顺序，每门考试随机安排在时间段中。具体的超启发方法请参看文献[1]。另外，本文采用二进制编码方式，其中每一列代表一个时间段，每一行代表一门考试，数字1表示在此时段安排某门考试，0表示在此时段未安排考试。
2仿真实验
本文选取Carter标准数据集[14]进行测试。近几十年来，几乎所有关于考试时间表算法的研究都采用此数据集进行性能测试，但此数据仍是开放数据，理论最优解仍然未知。本文选取了该数据集中的十个具有代表性的数据，对提出的算法进行仿真实验。以下仿真均为10次独立运行实验，运行环境为2.8GHzCorePersonalComputer。具体参数如表1所示：针对10个测试数据，算法经过10次独立运行，随机选取一组解集，其pareto前沿面如图2所示。少数几个测试集（car91,car92,ear83等）在个别区域没有找到非支配解。除上述测试集，大部分的测试集基本上能够完整勾勒出2目标优化的pareto前沿面，并且对于每一组数据的pareto解都可以较为均匀的分布在其前沿面上。表2记录了现今这些测试集的最好的运行结果，需要注意的是，此结果均为在单目标优化(固定时间表长度，只优化考试间冲突关系)的环境下产生的。我们选取的运行结果则是根据单目标环境下的时间表长度(P),在我们的多目标算法运行的结果中，选取的对应结果。从对比结果来看，除数据集york83，我们的算法均能找到与单目标模型中相同的时间段。从具体结果上来说，我们的结果的确与其他几种最优秀的单目标优化结果尚存一定差距，但差距并不明显。重要的是采用本文提出的多目标优化算法，经过一次运行就可提供不同时间段的多个解，运行效率是单目标优化的数十倍。上述结果表明，将考试时间表问题按照多目标优化问题建模有效且可以极大地提高计算效率。本文在NNIA框架下，在克隆阶段采用了资源分配模型，此模型对于整个算法的影响可由下列实验得出结论。图3为十组测试数据分别来自为采用资源分配模型的RA-NNIA和未采用此模型的原始NNIA进行十次独立运行后，非支配解个数的统计盒图。针对每一个测试数据，左边采用RA-NNIA，右边采用NNIA。我们可以明显看出，采用资源分配模型的RA-NNIA的非支配个体数量明显的好于未采用的NNIA。图4为十组测试数据，分别采用RA-NNIA和NNIA，经过十次独立实验后，spacing指标的统计盒图对比。由图可知，除少数几组数据(car92,ear83)，采用RA-NNIA算法的均匀性指标都要优于采用NNIA的运行结果。根据以上两组实验结果分析可知，对于如此建模的多目标考试时间表问题，非支配解的数量本身就十分的有限，传统的NNIA仅采用当前的非支配个体进行克隆，而后进行进化操作，导致种群的多样性难以保持，很有可能进一步导致最终的非支配解数目不足，而RA-NNIA克隆阶段，在非支配个体数量不足时，还会利用少部分较好的支配个体，共同进行克隆操作，并且，资源分配模型还会根据当前非支配个体所占的比例，动态控制每一部分个体的克隆比例，此种策略在一定的情况下可以很好地改善传统NNIA在这方面上的不足。所以，采用资源分配模型的NNIA是有利于非支配个体的产生与保留，有利于算法的多样性的保持，此策略十分适合用于求解多目标考试时间表问题的多目标进化算法。
