用伪二叉树法则构造多目标Pareto最优解集的方法

胡焕耀; 董渭清

您当前的位置：

首页 >

文章列表页 >

用伪二叉树法则构造多目标Pareto最优解集的方法

更新时间：2025-12-08

- 用伪二叉树法则构造多目标Pareto最优解集的方法
- An Approach to Constructing Multi-Objective Pareto Optimal Solutions Using Pseudo Binary Tree's Rule
- 西安交通大学学报 2009年43卷第2期页码：29-32
- 作者机构：
  
  西安交通大学电子与信息工程学院,西安,710049
- 作者简介：
- 基金信息：
  
  : 2008-05-15. 作者简介: 胡焕耀(1983-),男,硕士生;董渭清(联系人),男,教授. 基金项目:国家自然科学基金资助项目(60773118)
- DOI：
  中图分类号： TP301
- 网络首发：2009-02-10，
  
  纸质出版：2009
- 稿件说明：
移动端阅览
胡焕耀, 董渭清. 用伪二叉树法则构造多目标Pareto最优解集的方法[J]. 西安交通大学学报, 2009,43(2):29-32.

胡焕耀, 董渭清. An Approach to Constructing Multi-Objective Pareto Optimal Solutions Using Pseudo Binary Tree's Rule[J]. 2009, 43(2): 29-32.
胡焕耀, 董渭清. 用伪二叉树法则构造多目标Pareto最优解集的方法[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.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

冷库水平空气幕热湿阻隔性能数值模拟研究

张角凹坑气膜孔对双层壁气膜冷却特性的影响

结构-语义-残差协同的图像压缩框架：面向隐私保护与高保真重建

离子液体改性燃料的电流体动力学效应研究

三塔合一间接空冷系统结构参数对夏季运行特性的影响研究