An Approach to Constructing Multi-Objective Pareto Optimal Solutions Using Pseudo Binary Tree's Rule

胡焕耀; 董渭清

您当前的位置：

首页 >

文章列表页 >

An Approach to Constructing Multi-Objective Pareto Optimal Solutions Using Pseudo Binary Tree's Rule

更新时间：2025-12-08

- An Approach to Constructing Multi-Objective Pareto Optimal Solutions Using Pseudo Binary Tree's Rule
- Vol. 43, Issue 2, Pages: 29-32(2009)
- 作者机构：
  
  西安交通大学电子与信息工程学院,西安,710049
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP301
- Online First：10 February 2009，
  
  Published：2009
- 稿件说明：
移动端阅览
胡焕耀, 董渭清. An Approach to Constructing Multi-Objective Pareto Optimal Solutions Using Pseudo Binary Tree's Rule[J]. 2009, 43(2): 29-32.
DOI：

胡焕耀, 董渭清. An Approach to Constructing Multi-Objective Pareto Optimal Solutions Using Pseudo Binary Tree's Rule[J]. 2009, 43(2): 29-32. DOI：

摘要

针对多目标进化算法中如何提高非支配集构造效率的问题

提出了一种用伪二叉树法则构造多目标Pareto最优解集的方法.根据多目标解的性质

将解的比较结果分为支配、被支配以及不相关3种类型

再根据解的比较结果生成排序伪二叉树.在每一轮比较中

从进化群体中选出一个个体

将该个体与当前非支配集中的个体进行比较

淘汰被支配的个体

而未被淘汰的个体将插入到非支配集中第一个被淘汰个体的位置.依次进行

直到进化群体中的个体比较完毕

从而生成排序的伪二叉树.同时

在理论上证明了采用该方法获取的非支配集为目标进化群体的最大非支配集

分析得知其在最差情况下的时间复杂度为O(rN

/2).实验结果表明

当目标数较大时(r≥5)

在构造非支配集的效率上伪二叉树法要明显优于Deb、Jensen算法及擂台赛法则.

Abstract

To improve the efficiency of building a non-dominated set in multi-objective evolution algorithm

an approach called Pseudo binary tree's rule is proposed to construct the Pareto optimal solutions. The multi-objective solutions are divided into three types: dominated

non-dominated and irrelevant

based on their natures and comparison results

and then the sorting pseudo binary tree is generated according to the comparison results. An individual in the evolution group is selected in every round of comparison. Then the selected individual is compared with the individuals in the non-dominated set

and those that are dominated are eliminated. If the selected one survives

it replaces the first eliminated individual in the non-dominated set. Repeat the process successively until there is no individual left in

the evolution group

and a sorting pseudo binary tree is generated. It is proved in theory that the non-dominated set obtained by the proposed method is the biggest non-dominated set in the objective evolution group

and the worst time complexity is O(rN

/2). Experimental results show that when the number of objects is comparatively large(r≥5)

the efficiency of building the non-dominated set using the pseudo binarytree's rule is obviously higher than that using Deb's algorithm

Jensen's algorithm or arena's principle.

关键词

Keywords

references

SAWARAGI Y, NAKAYAMA H, TANINO T. Theory of multiobjective optimization[M]. New York, USA: Academic Press, 1985.

PARETO V. Cours D' economie politique: I, II [M]. Lausanne,Switzerland: F. Rouge,1896.

CEOLLO C A, VAN VELDHUIZEN D A, LAMOUNT G B. Evolutionary algorithms for solving multi-objective problems [M]. Dordrecht, Netherlands: Kluwer Academic Publishers, 2002.

ATASHKARI K, NARIMAN-ZADEH N, PILECHI A, et al. Thermodynamic Pareto optimization of turbojet engines using multi-objective genetic algorithm [J]. International Journal of Thermal Sciences, 2005,44(11):1061-1071.

YEN G, LU H. Dynamic multiobjective evolutionary algorithm: adaptive cell-based rank and density estimation [J]. IEEE Trans on Evolutionary Computation, 2003,7(3):253-274.

DEB K, PRATAP A, AGRAWAL S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Trans on Evolutionary Computation, 2002,6(2):182-197.

DEB K, AGRAWAL S, PRATAB A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization NSGA-II, KanGAL Report, 200001[R]. Kanpur,India: Indian Institute of Technology, 2000.

JENSEN M T. Reducing the run-time complexity of multiobjective EAs: the NSGA-II and other algorithms[J]. IEEE Trans on Evolutionary Computation, 2003,7(5):503-515.

郑金华,蒋浩,邝达,等.用擂台赛法则构造多目标 Pareto 最优解集的方法[J]. 软件学报,2007, 18(6):1287-1297.

ZHENG Jinhua, JIANG Hao, KUANG Da, et al. An approach of constructing multi-objective pareto optimal solutions using arena's principle[J]. Journal of Software, 2007,18(6):1287-1297.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Diffusion Characteristics and Influencing Factors in Case of Hydrogen Leakage from Fuel Cell Vehicles Running in Tunnels

Numerical Simulation of the Energy Conversion Process in Thermoacoustic Engines with Different Stack Materials

Electrothermal Coupling Research on the Evolutionary Law of Anti-Corona Performance for High-Altitude Air-Cooled Generators

Study on the Thermodynamic Properties in the Anomalous Region of Supercritical Water

Research on the Electrohydrodynamic Effects of Ionic Liquid-Modified Fuels

Related Author

No data

Related Institution

No data

⁰