检索结果-内蒙古大学图书馆

The Collaborative Local Search Based on Dynamic-Constrained Decomposition With Grids for combinatorial multiobjective optimization

引用

IEEE TRANSACTIONS ON CYBERNETICS 2021年第5期51卷 2639-2650页

作者： Cai, Xinye Xia, Chao Zhang, Qingfu Mei, Zhiwei Hu, Han Wang, Lisong Hu, Jun Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 210016 Peoples R China Collaborat Innovat Ctr Novel Software Technol & I Nanjing 210023 Peoples R China Civil Aviat Univ China Informat Technol Res Base Civil Aviat Adm China Tianjin 300300 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

The decomposition-based algorithms [e.g., multiobjective evolutionary algorithm based on decomposition (MOEA/D)] transform a multiobjective optimization problem (MOP) into a number of single-objective optimization subproblems and solve them in a collaborative manner. It is a natural framework for using single-objective local search (LS) to solve combinatorial MOPs. However, commonly used decomposition methods, such as weighted sum (WS), Tchebycheff (TCH), and penalty-based boundary intersection (PBI) may not be good at maintaining the population diversity while providing diverse initial solutions for different LS procedures in a collaborative way. Based on our previous work on the constrained decomposition with grids (CDG), this article proposes a dynamic CDG (DCDG) framework used to design a multiobjective memetic algorithm (DCDG-MOMA). DCDG uses grids for maintaining diversity, supporting the collaborative LS. In addition, DCDG dynamically increases the number of grids for obtaining more nondominated solutions as well as the better collaborative search among them. DCDG-MOMA has been compared with several classical and state-of-the-art algorithms on multiobjective traveling salesman problem (MOTSP), multiobjective quadratic assignment problem (MOQAP), and multiobjective capacitated arc routing problem (MOCARP).

关键词： Collaboration optimization Sociology Statistics Heuristic algorithms Memetics Cybernetics combinatorial multiobjective optimization constrained decomposition with grids (CDG) decomposition Pareto local search (LS)

来源：评论

学校读者我要写书评

暂无评论

A decomposition-based coevolutionary multiobjective local search for combinatorial multiobjective optimization

引用

SWARM AND EVOLUTIONARY COMPUTATION 2019年 49卷 178-193页

作者： Cai, Xinye Hu, Mi Gong, Dunwei Guo, Yi-nan Zhang, Yong Fan, Zhun Huang, Yuhua Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 210016 Jiangsu Peoples R China Collaborat Innovat Ctr Novel Software Technol & I Nanjing 210016 Jiangsu Peoples R China Civil Aviat Univ China Informat Technol Res Base Civil Aviat Adm China Tianjin 300300 Peoples R China China Univ Min & Technol Sch Informat & Elect Engn Xuzhou 221116 Jiangsu Peoples R China Shantou Univ Sch Engn Dept Elect Engn Shantou 515063 Guangdong Peoples R China

multiobjective evolutionary algorithm based on decomposition (MOEA/D) divides a multiobjective optimization problem into a number of single-objective subproblems and solves them in a collaborative way. MOEA/D can be naturally extended by the common, intensification oriented method of local search for solving combinatorial multiobjective optimization problems (CMOPs). However, the performance of MOEA/D strongly depends on the distribution of direction vectors and the decomposition method it adopts. In this paper, an efficient coevolutionary multiobjective local search based on decomposition (CoMOLS/D) is proposed. In CoMOLS/D, two sets of direction vectors and two populations with different decomposition methods are adopted to coevolve with each other. Among them, one population aims to achieve fast convergence while the other one puts more effort for maintaining the complementarily diverse solutions based on the convergence population. In the experimental studies, CoMOLS/D is compared with four decomposition-based local search heuristics, i.e., MOEA/D-LS (WS, TCH, PBI and iPBI);a dominance-based local search, i.e., epsilon-MOEA-LS;an indicator-based local search, i.e., IBEALS;and a state-of-the-art local search with dual populations, i.e., ND/DPP-LS;on two well-known CMOPs. The experimental results show that CoMOLS/D significantly outperforms the compared algorithms on most of the test instances.

关键词： combinatorial multiobjective optimization Local search Decomposition Coevolution

来源：评论

学校读者我要写书评

暂无评论

A Grid Weighted Sum Pareto Local Search for combinatorial Multi and Many-Objective optimization

引用

IEEE TRANSACTIONS ON CYBERNETICS 2019年第9期49卷 3586-3598页

作者： Cai, Xinye Sun, Haoran Zhang, Qingfu Huang, Yuhua Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 210016 Jiangsu Peoples R China Collaborat Innovat Ctr Novel Software Technol & I Nanjing 210023 Jiangsu Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

combinatorial multiobjective optimization problems (CMOPs) are very popular due to their widespread applications in the real world. One common method for CMOPs is Pareto local search (PLS), a natural extension of single-objective local search (LS). However, classical PLS tends to reserve all of the nondominated solutions for LS, which causes the inefficient LS, as well as unbearable computational and space cost. Due to the aforementioned reasons, most PLS approaches can only handle CMOPs with no more than two objectives. In this paper, by combining the Pareto dominance and weighted sum (WS) approach in a grid system, the grid weighted sum dominance (gws-dominance) is proposed and integrated into PLS for CMOPs with multiple objectives. In the grid system, at most one representative solution is maintained in each grid for more efficient LS, thus largely reducing the computational and space complexity. The grid-based WS approach can further guide the LS in different grids for maintaining more widely and uniformly distributed Pareto front approximations. In the experimental studies, the grid WS PLS is compared with the classical PLS, three decomposition-based LS approaches [multiobjective evolutionary algorithm based on decomposition-LS (WS, Tchebycheff, and penalty-based boundary intersection)], a grid-based algorithm (epsilon-MOEA), and a state-of-the-art hybrid approach (multiobjective memetic algorithm based on decomposition) on two sets of benchmark CMOPs. The experimental results show that the grid weighted sum Pareto local search significantly outperforms the compared algorithms and remains effective and efficient on combinatorial multiobjective and even many-objective optimization problems.

关键词： combinatorial many-objective optimization combinatorial multiobjective optimization grid weighted sum dominance (gws-dominance) Pareto local search (PLS)

来源：评论

学校读者我要写书评

暂无评论

An External Archive Guided multiobjective Evolutionary Algorithm Based on Decomposition for combinatorial optimization

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2015年第4期19卷 508-523页

作者： Cai, Xinye Li, Yexing Fan, Zhun Zhang, Qingfu Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 210016 Jiangsu Peoples R China Shantou Univ Sch Engn Guangdong Prov Key Lab Digital Signal & Image Pro Shantou 515063 Peoples R China Shantou Univ Sch Engn Dept Elect Engn Shantou 515063 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

Domination-based sorting and decomposition are two basic strategies used in multiobjective evolutionary optimization. This paper proposes a hybrid multiobjective evolutionary algorithm integrating these two different strategies for combinatorial optimization problems with two or three objectives. The proposed algorithm works with an internal (working) population and an external archive. It uses a decomposition-based strategy for evolving its working population and uses a domination-based sorting for maintaining the external archive. Information extracted from the external archive is used to decide which search regions should be searched at each generation. In such a way, the domination-based sorting and the decomposition strategy can complement each other. In our experimental studies, the proposed algorithm is compared with a domination-based approach, a decomposition-based one, and one of its enhanced variants on two well-known multiobjective combinatorial optimization problems. Experimental results show that our proposed algorithm outperforms other approaches. The effects of the external archive in the proposed algorithm are also investigated and discussed.

关键词： combinatorial multiobjective optimization decomposition Pareto optimality

来源：评论

学校读者我要写书评

暂无评论

Memots: A memetic algorithm integrating tabu search for combinatorial multiobjective optimization

引用

RAIRO-OPERATIONS RESEARCH 2008年第1期42卷 3-33页

作者： Lust, Thibaut Teghem, Jacques Fac Polytech Mons Lab Math & Operat Res B-7000 Mons Belgium

We present in this paper a new multiobjective memetic algorithm scheme called MEMOX. In current multiobjective memetic algorithms, the parents used for recombination are randomly selected. We improve this approach by using a dynamic hypergrid which allows to select a parent located in a region of minimal density. The second parent selected is a solution close, in the objective space, to the first parent. A local search is then applied to the of spring. We experiment this scheme with a new multiobjective tabu search called PRTS, which leads to the memetic algorithm MEMOTS. We show on the multidimensional multiobjective knapsack problem that if the number of objectives increase, it is preferable to have a diversified research rather using an advanced local search. We compare the memetic algorithm MEMOTS to other multiobjective memetic algorithms by using different quality indicators and show that the performances of the method are very interesting.

关键词： combinatorial multiobjective optimization hybrid meta-heuristic memetic algorithm Tabu Search Knapsack

来源：评论

学校读者我要写书评

暂无评论

Difficulty in Evolutionary multiobjective optimization of Discrete Objective Functions with Different Granularities

Difficulty in Evolutionary Multiobjective Optimization of Di...

引用

7th International Conference on Evolutionary Multi-Criterion optimization (EMO)

作者： Ishibuchi, Hisao Yamane, Masakazu Nojima, Yusuke Osaka Prefecture Univ Dept Comp Sci & Intelligent Syst Grad Sch Engn Naka Ku Sakai Osaka 5998531 Japan

ISBN: (纸本)9783642371400

Objective functions are discrete in combinatorial optimization. In general, the number of possible values of a discrete objective is totally different from problem to problem. That is, discrete objectives have totally different granularities in different problems (In this paper, "granularity" means the width of discretization intervals). In combinatorial multiobjective optimization, a single problem has multiple discrete objectives with different granularities. Some objectives may have fine granularities with many possible values while others may have very coarse granularities with only a few possible values. Handling of such a combinatorial multiobjective problem has not been actively discussed in the EMO community. In our former study, we showed that discrete objectives with coarse granularities slowed down the search by NSGA-II, SPEA2, MOEA/D and SMS-EMOA on two-objective problems. In this paper, we first discuss why such a discrete objective deteriorates the search ability of those EMO algorithms. Next we propose the use of strong Pareto dominance in NSGA-II to improve its search ability. Then we examine the effect of discrete objectives on the performance of the four EMO algorithms on many-objective problems. An interesting observation is that discrete objectives with coarse granularities improve the search ability of NSGA-II and SPEA2 on many-objective problems whereas they deteriorate their search ability on two-objective problems. The performance of MOEA/D and SMS-EMOA is always deteriorated by discrete objectives with coarse granularities. These observations are discussed from the following two viewpoints: One is the difficulty of many-objective problems for Pareto dominance-based EMO algorithms, and the other is the relation between discrete objectives and the concept of epsilon-dominance.

关键词： Evolutionary multiobjective optimization many-objective problems discrete objectives epsilon-dominance combinatorial multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

Two-phase Pareto local search for the biobjective traveling salesman problem

引用

JOURNAL OF HEURISTICS 2010年第3期16卷 475-510页

作者： Lust, Thibaut Teghem, Jacques Fac Polytech Mons Lab Math & Operat Res B-7000 Mons Belgium

In this work, we present a method, called Two-Phase Pareto Local Search, to find a good approximation of the efficient set of the biobjective traveling salesman problem. In the first phase of the method, an initial population composed of a good approximation of the extreme supported efficient solutions is generated. We use as second phase a Pareto Local Search method applied to each solution of the initial population. We show that using the combination of these two techniques: good initial population generation plus Pareto Local Search gives better results than state-of-the-art algorithms. Two other points are introduced: the notion of ideal set and a simple way to produce near-efficient solutions of multiobjective problems, by using an efficient single-objective solver with a data perturbation technique.

关键词： combinatorial multiobjective optimization Biobjective traveling salesman problem Two-phase method Supported efficient solutions Pareto local search Data perturbation technique Performance assessment of multiobjective metaheuristics

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：