2012.9
No ve l Ada ptive Simula te d Anne a ling
Algo r ithm fo r C o ns tra ine d Multi-O bje ctive O ptim iz a tio n
Chuai Gang1, 2 , Zhao Dan1, 2 , Sun Li1, 3
- School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, Bei-jing 100876, P. R. China
- Key Laboratory of Universal Wireless Communication, Ministry of Education, Beijing University of Posts and Telecommunications, Beijing 100876, P. R. China
- Beijing Key Laboratory of Network System Architecture and Convergence, Beijing University of Posts and Telecommunications, Beijing 100876, P. R. China
|
Abstract: In recent years, simulated annealing algo- |
ters scenarios where more than one conflicting ob- |
|
|
rithms have been extensively developed and utilized |
jectives have to be optimized simultaneously , sub- |
|
|
to solve multi-objective optimization problems. In |
ject to a number of given constraints. In terms of |
|
|
order to obtain better optimization performance, |
handling multiple objectives, a number of strategies |
|
|
this paper proposes a Novel Adaptive Simulated |
have been proposed in recent years. They can be |
|
|
Annealing (NASA) algorithm for constrained multi- |
broadly classified into three categories: 1 ) scalar |
|
|
objective optimization based on Archived M ulti- |
function schemes; 2 ) composite energy difference |
|
|
objective Simulated Annealing (AM OSA). For han- |
schemes; 3 ) pareto dominance based schemes. In |
|
|
dling multi-objective, NASA makes improvements |
scalar function scheme, a scalar objective is formed |
|
|
in three aspects: sub-iteration search, sub-archive and |
by weighted aggregation of the multiple objectives, |
|
|
adaptive search, which effectively strengthen the sta- |
which is then used as an energy function in Simula- |
|
|
bility and efficiency of the algorithm. For handling |
ted Annealing (SA ) [1 ]. Although solutions on a |
|
|
constraints, NASA introduces corresponding solution |
pareto set can be found by using scalar function |
|
|
acceptance criterion. Furthermore, NASA has also |
method, each time SA renders only one solution, |
|
|
been applied to optimize TD-LTE network perform- |
and hence, a number of runs have to be made in or- |
|
|
ance by adjusting antenna parameters; it can achieve |
der to get a required number of solutions on the Pa- |
|
|
better extension and convergence than AMOSA, NS- |
reto front. As alternatives to scalar function |
|
|
GAII and MOPSO. Analytical studies and simula- |
scheme, methods based on composite energy differ- |
|
|
tions indicate that the proposed NASA algorithm can |
ence calculation have been suggested for SA, where |
|
|
play an important role in improving multi-objective |
the probability of acceptance of a trial solution is |
|
|
optimization performance. |
calculated as a function of the acceptance probabili- |
|
|
Key words: simulated annealing; constrained multi- |
ties for individual functions [2-4]. While using com- |
|
|
objective optimization; adaptive; sub-iteration search- |
posite energy techniques, it is necessary to scale |
|
|
ing; sub-archive; pareto-optimal |
the individual objectives such that the search does |
|
|
not become biased towards particular objective. To |
||
|
I． INTRODUCTION |
overcome the difficulties associated with scalar |
|
|
techniques and composite functions, attempts have |
||
|
While solving practical problems, one often encoun- |
been made by various researchers to incorporate |
68
DIGITAL COMMUNICATIONS
the concept of Pareto dominance in SA [5-9 ]. On the other hand, there have been recent efforts to en-hance SA for eliminating constraint handling [10-11]. Depending on whether the current solution is feasi-ble or not [11], the corresponding acceptance criteri-on is developed.
Although studies have been done on handling multiple objectives and constraints, limited studies have been focused on improving the searching methods of SA for constrained multi-objective op-timization problems. This paper proposes a Novel Adaptive Simulated Annealing (NASA ) algorithm for constrained multi-objective optimization based on Archived M ulti-Objective Simulated Annealing (AM OSA) [12].
As SA is a single-point search algorithm, the ran-dom searching process makes it easy to fall into lo-cal optimization area and run an extensive search in poor region. For multi-objective, NASA introduces improvements in three areas based on AM OSA: 1) sub-iteration search: sub-iteration search includes diversity search and accuracy search, the diversity search prevents the algorithm from falling into a lo-cal optimization area, and the accuracy search
剩余内容已隐藏，支付完成后下载完整资料
自适应的多目标模拟退火优化算法
摘要：近年来，算法已被广泛开发和利用解决多目标优化问题。在为了获得更好的优化性能,本文提出了一种新型自适应模拟退火（NASA）算法，基于存档的终端客观优化客观模拟退火（AM OSA）。为了处理多目标，NASA做出改进在三个方面：子迭代搜索，子归档和自适应搜索，有效加强了算法的灵活性和效率。处理约束，NASA引入相应的解决方案验收标准。此外，美国宇航局也已被应用于优化TD-LTE网络性能，调整天线参数;它可以实现更好的延伸和收敛比AMOSA，NS-GAII和MOPSO。分析研究和模拟表明提出的NASA算法可以在改善多目标方面发挥重要作用优化性能。
关键词：模拟退火; 约束多目标优化; 适应性 子迭代搜索 ; 子档案；帕累托最优。
一 简介
在解决实际问题的同时，经常遇到多个冲突目标必须同时优化的情景，受到一些给定的限制。 在处理多个目标方面，近年来已经提出一些策略。 它们可以广泛地分为三类：1）标量函数方案; 2）复合能量差异方案; 3）帕累托优势计划。 Inscalar函数方案，通过多个目标的加权聚合形成标量目标，然后将其用作模拟退火（SA）中的能量函数[1]。 虽然通过使用标量函数方法可以找到apareto集合的解，但每次SA只呈现一个解，因此，为了在帕累托前线获得所需数量的解决方案，必须进行一些运行。 作为标量函数的替代方法，已经提出了基于复合能量差计算的方法，其中接受试验解决方案的概率为作为个体功能接受概率的函数计算[2-4]。 在使用复合能量技术的同时，还需要进行规模化个人目标，使搜索不会偏向于特定的目标。 为了克服与标量技术和复合函数相关的困难，各种研究人员试图将帕累托优势的概念纳入到SA [5-9]中。 另一方面，最近有一些努力来加强SA消除约束处理[10-11]。 根据目前的解决方案是否可行[11]，制定了相应的验收标准。
虽然已经对处理多个目标和约束进行了研究，但是有限的研究一直侧重于改进SA对于约束多目标运算时间问题的搜索方法。本文提出了一种基于归档多目标模拟退火（AM OSA）的约束多目标优化的新型自适应模拟退火（NASA）算法[12]。由于SA是单点搜索算法，所以搜索过程可以很容易地落入偏僻的优化区域，并且在偏僻地区进行广泛的搜索。为了多目标，NASA基于AM OSA对三个方面进行了改进：1）子迭代搜索：子迭代搜索包括分集搜索和精确搜索，分集搜索防止算法落入一个优化区域，精确度搜索有助于在真正的帕累托最优边界附近实现更好的收敛; 2）子档案：最好的非主导的子迭代解决方案集称为子档案; 3）自适应搜索：搜索方法可以根据实时情况在优化过程中进行调整，包括改变分集搜索和搜索搜索的比例等，提高了优化效率。
此外，这个方法不仅涉及NASA，而且还通过调整天线参数来研究该算法的结果，以便对TD-LTE网络性能进行定时化。 同时，具有一些常见的多目标算法（包括NSGAII [13-16]，M OPSO [16-18]和AM OSA [12]）的实际编码版本的comp 发现NASA的管道和性能通常更好。
本文的其余部分安排如下。 第二部分介绍了NASA算法的细节。 在第三节中，我们应用NASA通过调整天线参数优化TD-LTE网络性能，并通过仿真比较NASA与其他多目标优化算法的性能。 最后，在第四部分中，我们将结束本文和电子实验，了解我们将来如何利用它。
二 一个新的自适应模拟退火算法
在本节中，由Bandyopadhyay等人提出了SA和AMOSA的简要介绍 [12]，因为NASA是一种基于AMOSA的改进算法。之后，详细讨论了所提出的NASA算法。
2.1 SA背景
作为流行的搜索算法，SA利用关于低温下大量原子的行为的统计力学原理，通过最小化相关能量来找到最大化优化问题的成本解决方案。在统计力学中，调查低能量物质状态至关重要。这些状态在非常低的温度下实现。在退火过程中，首先升温，然后逐渐降低到非常低的值，同时确保在每个温度值下花费足够的时间。该过程产生稳定的低能态。 S.双子座Geman [19]提供SA的证明。如果温度退火足够慢，则SA可以收敛到全局最优值。基于强大的理论，SA在不同领域有应用[20-22]。
2.2 AM OSA背景
AMOSA是一种基于优势的SA方法，基本流程图如图1所示。 AMOSA和大多数早期SA技术之间的突出差异是试用解决方案的验收标准，考虑到当前解决方案和存档（所有非主导解决方案都是如此）。AMOSA的另一个突出特点是它比较了基于优势度量的解决方案，而不是主导的解决方案的数量积分。给定解a和b，当a占主导地位时，统治量定义如下[12]。
|
doma, b |
= prod; (| |
fi (a) － fi (b) | ) |
(1) |
||
|
nobj |
|||||
|
i = 1, fi(a)ne;fi(b) |
Ri |
||||
其中nobj是目标的数量，Ri是第i个目标的范围。 Ri由归档中的解决方案（搜索中的非主导解决方案集），当前和拟议的试用解决方案。
图1 AM OSA流程图
AMOSA搜索通过一些解决方案进行初始化，这些解决方案通过使用简单的策略进行了几次迭代的改进，只有当它支配先前的解决方案时，才能接受该命令。 通过使用这种技术获得的非主导解决方案用于初始化非主导解决方案。 主要搜索从档案中的随机解决方案开始。 La-place扰动用于创建试用解决方案。此后，分析了当前解决方案，新解决方案和归档的统治状态。 基于统治地位，可以产生一些案例。 从详尽的案件清单中，验收是根据适用案例计算的。 在搜索期间维护和不断更新存档。
每当考虑接受不利的举动时，接受的概率计算为
prob = 1 /（1 exp（dom / T））（2）
其中T是温度，dom是基于当前解决方案，试用解决方案和存档的优势关系的值。
在搜索过程中，要将存档中的解决方案数量限制在所需的值，需要切割。允许档案长到规定的软限制（SL），一旦达到限制，就进行剪切归档，以减少规定硬限制（HL）的解决方案数量。
2.3建议的NASA算法
由于AMOSA也是像SA这样的单点搜索算法，因此随机搜索过程使其易于落入局部优化领域。对于多目标，NASA基于AMOSA在三个方面引入了改进：子迭代搜索，子归档和自适应搜索。对于受限制的干扰，NASA引入相应的解决方案标准。
1）子迭代搜索
AMOSA使用单点搜索方法，可以从当前解决方案中生成新的解决方案。在NASA中，搜索过程包括搜索和子迭代搜索。随温度变化更新的当前解决方案称为迭代解决方案，相应的搜索过程称为迭代搜索;在相同温度下从同一当前解决方案生成的新解决方案称为子迭代解决方案，相应的搜索过程称为子迭代搜索。在引入子迭代搜索之后，每当M（M是次迭代搜索的数量）时，从当前解决方案中生成新的解决方案，然后从M解决方案更新中选择最佳解决方案之一为目前的解决方案。
子迭代搜索包括分集搜索和精确搜索。 nd元素随机地从决策变量中选择并被分集搜索中的随机变量扰乱。在精确搜索中选择na元素，（ndgt; na）。因此，来自分集搜索的新解决方案比基于相同当前解决方案的精度搜索的新解决方案具有更大的突变。以这种方式，分集搜索防止NASA落入局部优化区域，精度搜索有助于在真实的帕累托最优边界附近实现更好的收敛。
2）子档案
NASA中存在归档和子存档，这两个应在搜索过程中进行更新。最优秀的非主导解决方案集合搜索被称为归档。在子分析搜索中，每次可以根据当前的解决方案生成一些新的解决方案，这些解决方案的非主导解决方案集是子归档。每次通过子归档更新存档。
3）自适应搜索
自适应搜索意味着可以在优化过程中根据实时情况调整搜索方法，包括改变分集搜索的比例和移动的元素的数量。当新解决方案尚未被接受为当前解决方案多次时，搜索可能已落入本地优化领域，并采取措施。这些措施包括增加二维搜索的比例，增加nd（分集搜索中的每个元素的数量）和减少na（精确搜索中移动的元素的数量）。跳出本地优化区后，所有更改的变量将被替换为默认值。在优化过程中，可以根据实时情况调整突变，因此NASA将在真实的帕累托最优边界附近实现更好的转换
AM OSA。
4）限制处理
对于约束处理，我们定义了一些新的概念，包括约束函数，可行解和不可行解。如果给定约束如下：g1（x）le;0，g2（x）le;0，...，gI（x）le;0，总计
一世
约束函数可以给出为g（x）=Sigma;gi（x）le;0。
i = 1
对于解x，如果g（x）le;0，则x是可行的解;否则，x是不可行的解决方案。美国宇航局为可行和不可行的解决方案制定了不同的验收标准。
NASA算法的流程图如图2所示，详细内容将在后面的章节中进行讨论。
图2 NASA流程图（算法1）
2.3.1参数说明
1）T max：最大（初始）温度，Tmin：最小（最终）温度;
2）N：迭代次数，N =logalpha;（T min / T max）;
3）alpha;：冷却速率，beta;：sigma;的下降率;
4）M：子迭代号，M 0 = M 1 M 2，M 1：分集搜索号，M2：精度搜索号;
5）HL：存档的硬限制大小，SL：档案的软限制大小。
2.3.2自适应子迭代搜索
子迭代搜索包括分集搜索和精确搜索。每次通过分集搜索从目前的解决方案生成M 1解，通过精确搜索得到M 2解（M = M 1 M 2）。 nd元素从分集搜索中的随机变量随机选择，并且在精度搜索中代替nd，而n（n）gt; na（n是决策向量的长度）。
自适应搜索意味着搜索方法可以在优化过程中根据实时情况进行调整。当新解决方案未被接受为当前解决方案一定次数时，会逐渐增加M 1并逐渐向本地优化区域跳出，逐渐减少M2和na搜索更准确的解决方案。之后，所有更改的变量将被替换为默认值。这样可以根据实时情况调整搜索方式。
2.3.3拉普拉斯
拉普拉斯突变如参考文献[5,12]。决定矢量的nd或na元素随机选取，并由拉普拉斯分布p（ε）alpha;e-sigma;ε绘制的随机变量ε扰动，其中sigma;表示扰动的扩展。为了有效地搜索变量空间，在整个搜索过程中缩放了sigma;。最初它被设置得足够大，使得算法可以遍历变量的整个范围。随着迭代的进行，sigma;被指数地减少到一个小的值。
这种更新方案的目的是通过以下方式辅助搜索：1）在初始阶段，这将有助于算法随机遍历搜索空间，从而识别潜在最优的区域; 2）在后期阶段，需要调整变数值以尽可能接近帕累托边界，在这个阶段，使用小的sigma;值，以增加改进的机会解决方案是最后的边界。
2.3.4解决方案验收标准
如图3所示，解决方案接受度取决于当前的解（xold）
新的解决方案（x）是否可行。何时可行的解决方案优先于不可行解;更新归档时，只有可行的解决方案才能被归档，因为归档是最终的解决方案。详细的解决方案验收标准如图3所示。当xold和xnew都可行时，验收标准（算法2）如图4所示是复杂的。
图3 NASA的验收标准
图4 xold和xnew可行时的验收标准（算法2）
2.3.5存档和子存档更新
档案和子档案应在NASA更新。在子迭代搜索中，每当它可以基于当前的解决方案生成一些新的解决方案时，这些解决方案的非主导解决方案集是子归档。每次通过子存档更新ar-chive，如Al-3算法所述。如果存档的大小超过预先限定的限制SL，则通过使用NSGAII中的拥挤比较程序将存档的大小减少为HL 13]。
算法3.存档更新
- for i = 1∶ m (the size of sub-archive)
- for j = 1∶ n (the size of archive)
- (ai is the ith of sub-archive, bj is the jth of archive)
- compare the domination relation of ai and bj
- end for
6: if ai dominate k( k ＞ 0) points of the archive
- delete the k points, add ai to archive
- else if ai is non-dominating with the points of archive
- add ai to archive
- end if
-
end
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[26447]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
