适应性多目标组合优化：软件发布与旅行商问题的 memetic 框架

59 浏览量更新于2024-07-15 收藏 1.16MB PDF 举报

"本文提出了一种自适应的多目标迷宫算法（MOMAs），用于解决组合优化问题，如软件下一版本选择和旅行商问题。该框架结合了两种不同的自适应机制，并采用模拟退火作为局部搜索过程。" 在《An Adaptive Memetic Framework for Multi-objective Combinatorial Optimization Problems: Studies on Software Next Release and Travelling Salesman Problems》这篇研究论文中，作者Xinye Cai、Xin Cheng、Zhun Fan、Erik Goodman和Lisong Wang探讨了如何有效解决多目标优化问题。他们提出了一种创新的框架，该框架旨在处理那些具有多个相互冲突目标的组合优化问题，例如在软件开发中的下一个版本选择和经典的旅行商问题。多目标优化问题（MOOPs）的挑战在于寻找一组非支配解，这些解代表了问题的帕累托前沿，即无法在不损害一个目标的情况下改进另一个目标的解决方案集合。为了解决这些问题，论文提出了两种自适应机制： 1. 第一种自适应机制是基于解决方案对帕累托前沿的收敛性进行选择。这种机制动态地选择那些在进化过程中朝着帕累托前沿靠近的解决方案进行局部搜索，从而有助于发现更优的解集。 2. 第二种机制利用外部集（支配档案）的收敛性和多样性信息来指导局部搜索中有潜力解决方案的选择。这种方法可以保持种群的多样性和防止过早收敛，这对于维持解的全局探索能力至关重要。此外，论文还引入了模拟退火作为局部搜索策略。模拟退火是一种全局优化技术，它模拟了固体冷却的过程，通过接受可能恶化当前解决方案的步骤来跳出局部最优，从而增加找到全局最优解的可能性。论文的研究成果对解决实际问题具有重要价值，特别是在软件工程领域。在软件下一个版本选择问题中，需要在功能的添加、优先级排序和资源分配之间做出平衡，而多目标优化方法可以帮助开发者做出更加全面和均衡的决策。同样，旅行商问题（TSP）是运筹学中的经典问题，优化路径可以提高物流和配送效率。这篇论文提出的自适应迷宫算法框架为多目标组合优化问题提供了一个强大的工具，通过智能的自适应策略和有效的局部搜索机制，能够在解决复杂优化问题时达到更好的性能。这一工作不仅对理论研究有所贡献，也为实际应用提供了有价值的解决方案。

An adaptive memetic framework for multi -objective combinatorial optimization...

The external-set-guided adaptive mechanism is inspired

by EAG-MOEA/D (Cai et al. 2014). So this section dis-

cusses the similarities and differences between aMOMA-SA

and EAG-MOEA/D. Both aMOMA-SA and EAG-MOEA/D

adopt adaptive selection of solutions. However, these two

algorithms are different in the following aspects:

1. The frameworks of the aMOMA-SA and EAG-MOEA/D

are different.

(a) aMOMA-SA is essentially a multiobjective memetic

algorithm, which uses external-set-guided selection

for the local search (simulated annealing) while EAG-

MOEA/D does not have any local search. It only uses

external set to guide the global search.

(b) In EAG-MOEA/D, all the generated solutions have

been put in a temporary population L, which later

is used to update the external set A. However, in

aMOMA-SA, the update of population L is based

on Boltzmann criterion (see Sect. 4.2.4).

2. The adaptive mechanisms for choosing s ubproblems are

different. In EAG-MOEA/D, the probability for choosing

a subproblem is calculated based on the contributions of

each subproblem on the external set over the last certain

number of generations. However, in aMOMA-SA, the

probability is calculated based on the contributions of

each subproblem on the current external set.

4 The proposed multi-objective memetic

algorithms

Our multi-objective memetic algorithm with simulated

annealing as its local search method (MOMA-SA) decom-

poses a MOP into N single-objective optimization subprob-

lems by aggregating objective functions with different weight

vectors. In principle, we can adopt any aggregation method

for this purpose. For simplicity, we use the weighted sum

approach with N weight vectors:

= (λ

,...,λ

) j = 1,...,N. (2)

where λ

∈ R

and



i=1

= 1, m is the number of

objectives. Subproblem k is:

minimize g

(x) =



i=1

(x)

subject to x ∈  (3)

For each k = 1,...,N ,setB(k) stores the indices of the

T closest weight vectors to λ

in terms of the Euclidean dis-

tance. Subproblem i is deﬁned as a neighbour of subproblem

k, when i ∈ B(k).

The following solution are maintained during the evolu-

tionary process:

– Decomposition population set P ={x

,...,x

where x

is the best solution associated with subproblem

– External set (dominance archive) A, which contains

N solutions selected by fast-non-dominated-sorting and

crowding-distance-assignment in NSGA-II (Deb 2001;

Deb et al. 2002).

– L, which stores solutions after undergoing local search.

– Y , which stores solutions after undergoing global search.

The pseudocode of the framework is presented in Algo-

rithm 1. It works as follows:

Step 1 Initialization: Initialize P and A.

Step 2 Local Search: Use a mechanism to select solutions

from P (in Sect. 4.3) to undergo local search; the

generated new solution set are stored in L.

Step 3 Global Search: Perform global search on P to gen-

erate a new solution set Y .

Step 4 Update of Population and External Set: Use L and

Y to update P and A.

Step 5 Stopping Criterion: If preset criteria are satisﬁed,

output A.Otherwise,gotoStep2.

More detailed descriptions of Steps 1–4 of Algorithm 1

are given as follows:

4.1 Initialization

A MOP is originally decomposed into N subproblems based

on Eqs. 2 and 3. The decomposition population P is ran-

domly generated and assigned to the external set A.TheT

closest neighbours, in terms of Euclidean distance, to each

weight vector are determined. Therefore, subproblem i has

T neighbours, denoted as B(i) ={i

,...,i

}. The whole

process of initialization is shown in Step 1.

4.2 Local search

The procedures of local search are demonstrated in Step 2

as follows. In Step 2a, using one of the following mecha-

nisms, N solutions are chosen from P for local search. This

is actually to address the issue of the frequency of reﬁne-

ment and individual subset selection in Sudholt (2006). In

this work, one baseline and two adaptive mechanisms for

selecting individuals for local search are adopted as follows.

123

剩余21页未读，继续阅读

weixin_38550334

粉丝: 2
资源: 952

适应性多目标组合优化：软件发布与旅行商问题的 memetic 框架

H.264/MPEG-4 Part10 白皮书：新一代视频压缩标准

i-VISTA智能汽车指数：01自适应巡航控制试验规程详解

MATLAB在多对称Euler盒方案和参数敏感性分析中的应用

Integration of improved predictive model and adaptive differential evolution based dynamic multi-objective evolutionary optimization algorithm

Multi-objective differential evolution with performance-metric-based self-adaptive mutation operator for chemical and biochemical dynamic optimization problems

Fast Adaptive Coordinate Descent for Non-linear Optimization: Fast Adaptive Coordinate Descent for Large-scale (D>>100) Non-linear Optimization-matlab开发

An Adaptive Archive-Based Evolutionary Framework for Many-Task Optimization

matlab代码粒子群算法-Self-Adaptive-Particle-Swarm-Optimization-for-Large-Scale

最小均方差滤波器MATLAB代码-Adaptive-Filter-Minimum-Mean-Square-Error-:用Matlab编写的用

自适应k均值matlab代码-K-Means-in-BMS-to-generate-an-adaptive-curve:K-Means-in-

最新资源