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

PPLS/D: Parallel Pareto Local Search Based on Decomposition

IEEE TRANSACTIONS ON CYBERNETICS 2020年第3期50卷 1060-1071页

作者： Shi, Jialong Zhang, Qingfu Sun, Jianyong Xi An Jiao Tong Univ Sch Math & Stat Xian 710049 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

Pareto local search (PLS) is a basic building block in many metaheuristics for a multiobjective combinatorial optimization problem. In this paper, an enhanced PLS variant called parallel PLS based on decomposition (PPLS/D) is proposed. PPLS/D improves the efficiency of PLS using the techniques of parallel computation and problem decomposition. It decomposes the original search space into L subregions and executes L parallel processes searching in these subregions simultaneously. Inside each subregion, the PPLS/D process is guided by a unique scalar objective function. PPLS/D differs from the well-known two phase PLS in that it uses the scalar objective function to guide every move of the PLS procedure in a fine-grained manner. In the experimental studies, PPLS/D is compared against the basic PLS and a recently proposed PLS variant on the multiobjective unconstrained binary quadratic programming problems and the multiobjective traveling salesman problems with, at most, four objectives. The experimental results show that regardless of whether the initial solutions are randomly generated or generated by heuristic methods, PPLS/D always performs significantly better than the other two PLS variants.

关键词： multiobjective combinatorial optimization parallel metaheuristic Pareto local search unconstrained binary quadratic programming traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2020年第1期92卷 107-132页

作者： Schulze, Britta Stiglmayr, Michael Paquete, Luis Fonseca, Carlos M. Willems, David Ruzika, Stefan Univ Wuppertal Dept Math & Nat Sci Gaussstr 20 D-42119 Wuppertal Germany Univ Coimbra Dept Informat Engn CISUC Coimbra Portugal Univ Koblenz Landau Math Inst Koblenz Germany Univ Kaiserslautern Dept Math Kaiserslautern Germany

In this article, we introduce the rectangular knapsack problem as a special case of the quadratic knapsack problem consisting in the maximization of the product of two separate knapsack profits subject to a cardinality constraint. We propose a polynomial time algorithm for this problem that provides a constant approximation ratio of 4.5. Our experimental results on a large number of artificially generated problem instances show that the average ratio is far from theoretical guarantee. In addition, we suggest refined versions of this approximation algorithm with the same time complexity and approximation ratio that lead to even better experimental results.

关键词： Quadratic knapsack problem Approximation algorithm multiobjective combinatorial optimization Hypervolume

来源：评论

学校读者我要写书评

暂无评论

A greedy memetic algorithm for a multiobjective dynamic bin packing problem for storing cooling objects

引用

JOURNAL OF HEURISTICS 2019年第1期25卷 1-45页

作者： Spencer, Kristina Yancey Tsvetkov, Pavel V. Jarrell, Joshua J. Texas A&M Univ 3133 TAMU College Stn TX 77843 USA Oak Ridge Natl Lab Oak Ridge TN USA Idaho Natl Lab Idaho Falls ID USA

In this paper, a multiobjective dynamic bin packing problem for storing cooling objects is introduced along with a metaheuristic designed to work well in mixed-variable environments. The dynamic bin packing problem is based on cookie production at a bakery, where cookies arrive in batches at a cooling rack with limited capacity and are packed into boxes with three competing goals. The first is to minimize the number of boxes used. The second objective is to minimize the average initial heat of each box, and the third is to minimize the maximum time until the boxes can be moved to the storefront. The metaheuristic developed here incorporated greedy heuristics into an adaptive evolutionary framework with partial decomposition into clusters of solutions for the crossover operator. The new metaheuristic was applied to a variety benchmark bin packing problems and to a small and large version of the dynamic bin packing problem. It performed as well as other metaheuristics in the benchmark problems and produced more diverse solutions in the dynamic problems. It performed better overall in the small dynamic problem, but its performance could not be proven to be better or worse in the large dynamic problem.

关键词： Dynamic bin packing problem multiobjective combinatorial optimization Metaheuristics Memetic algorithms

来源：评论

学校读者我要写书评

暂无评论

Finding representations for an unconstrained bi-objective combinatorial optimization problem

引用

optimization LETTERS 2018年第2期12卷 321-334页

作者： Jesus, Alexandre D. Paquete, Luis Figueira, Jose Rui Univ Coimbra Dept Informat Engn CISUC Polo 2 P-3030290 Coimbra Portugal Univ Lisbon Inst Super Tecn CEG IST Ave Rovisco Pais 1 P-1049001 Lisbon Portugal

Typically, multi-objective optimization problems give rise to a large number of optimal solutions. However, this information can be overwhelming to a decision maker. This article introduces a technique to find a representative subset of optimal solutions, of a given bounded cardinality for an unconstrained bi-objective combinatorial optimization problem in terms of -indicator. This technique extends the Nemhauser-Ullman algorithm for the knapsack problem and allows to find a representative subset in a single run. We present a discussion on the representation quality achieved by this technique, both from a theoretical and numerical perspective, with respect to an optimal representation.

关键词： multiobjective combinatorial optimization Representation problem Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Using multiobjective optimization for biclustering microarray data

引用

APPLIED SOFT COMPUTING 2015年 33卷 239-249页

作者： Seridi, Khedidja Jourdan, Laetitia Talbi, El-Ghazali Univ Lille 1 CNRS Lab Informat Fondamentale Lille UMR Cite Sci 8022 F-59655 Villeneuve Dascq France INRIA Lille Nord Europe F-59650 Villeneuve Dascq France

Microarray data analysis is a challenging problem in the data mining field. Actually, it represents the expression levels of thousands of genes under several conditions. The analysis of this data consists on discovering genes that share similar expression patterns across a sub-set of conditions. In fact, the extracted informations are submatrices of the microarray data that satisfy a coherence constraint. These submatrices are called biclusters, while the process of extracting them is called biclustering. Since its first application to the analysis of microarray [1], many modeling and algorithms have been proposed to solve it. In this work, we propose a new multiobjective model and a new metaheuristic HMOBIibea for the biclustering problem. Results of the proposed method are compared to those of other existing algorithms and the biological relevance of the extracted information is validated. The experimental results show that our method extracts very relevant biclusters, with large sizes with respect to existing methods. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Biclustering problem Gene expression data Evolutionary algorithm multiobjective combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Exact Methods for Computing All Lorenz Optimal Solutions to Biobjective Problems 4th

引用

4th International Conference on Algorithmic Decision Theory (ADT)

作者： Galand, Lucie Lust, Thibaut Univ Paris 09 PSL LAMSADE CNRSUMR 7243 F-75775 Paris 16 France Univ Paris 06 Sorbonne Univ CNRS LIP6UMR 7606 F-75005 Paris France

ISBN: (纸本)9783319231143;9783319231136

This paper deals with biobjective combinatorial optimization problems where both objectives are required to be well-balanced. Lorenz dominance is a refinement of the Pareto dominance that has been proposed in economics to measure the inequalities in income distributions. We consider in this work the problem of computing the Lorenz optimal solutions to combinatorial optimization problems where solutions are evaluated by a two-component vector. This setting can encompass fair optimization or robust optimization. The computation of Lorenz optimal solutions in biobjective combinatorial optimization is however challenging (it has been shown intractable and NP-hard on certain problems). Nevertheless, to our knowledge, very few works address this problem. We propose thus in this work new methods to generate Lorenz optimal solutions. More precisely, we consider the adaptation of the well-known two-phase method proposed in biobjective optimization for computing Pareto optimal solutions to the direct computing of Lorenz optimal solutions. We show that some properties of the Lorenz dominance can provide a more efficient variant of the two-phase method. The results of the new method are compared to state-of-the-art methods on various biobjective combinatorial optimization problems and we show that the new method is more efficient in a majority of cases.

关键词： multiobjective combinatorial optimization Fairness Lorenz dominance Two-phase method

来源：评论

学校读者我要写书评

暂无评论

A hybrid metaheuristic for multiobjective unconstrained binary quadratic programming

引用

APPLIED SOFT COMPUTING 2014年第0期16卷 10-19页

作者： Liefooghe, Arnaud Verel, Sebastien Hao, Jin-Kao Univ Lille 1 LIFL UMR CNRS 8022 F-59655 Villeneuve Dascq France Inria Lille Nord Europe F-59650 Villeneuve Dascq France Univ Littoral Cote dOpale LISIC F-62228 Calais France Univ Angers LERIA F-49045 Angers France

The conventional unconstrained binary quadratic programming (UBQP) problem is known to be a unified modeling and solution framework for many combinatorial optimization problems. This paper extends the single-objective UBQP to the multiobjective case (mUBQP) where multiple objectives are to be optimized simultaneously. We propose a hybrid metaheuristic which combines an elitist evolutionary multiobjective optimization algorithm and a state-of-the-art single-objective tabu search procedure by using an achievement scalarizing function. Finally, we define a formal model to generate mUBQP instances and validate the performance of the proposed approach in obtaining competitive results on large-size mUBQ Pinstances with two and three objectives. (C) 2013 Elsevier B. V. All rights reserved.

关键词： Unconstrained binary quadratic programming multiobjective combinatorial optimization Hybrid metaheuristic Evolutionary multiobjective optimization Tabu search Scalarizing functiona

来源：评论

学校读者我要写书评

暂无评论

2-additive Choquet Optimal Solutions in multiobjective optimization Problems

2-additive Choquet Optimal Solutions in Multiobjective Optim...

引用

15th International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems (IPMU)

作者： Lust, Thibaut Rolland, Antoine Univ Paris 06 CNRS LIP6 Sorbonne Univ Paris France Univ Lyon 1 ERIC Villeurbanne France

ISBN: (纸本)9783319087955;9783319087948

In this paper, we propose a suffcient condition for a solution to be optimal for a 2-additive Choquet integral in the context of multiobjective combinatorial optimization problems. A 2-additive Choquet optimal solution is a solution that optimizes at least one set of parameters of the 2-additive Choquet integral. We also present a method to generate 2-additive Choquet optimal solutions of multiobjective combinatorial optimization problems. The method is experimented on some Pareto fronts and the results are analyzed.

关键词： Choquet integral Multicriteria decision making Fuzzy measure multiobjective combinatorial optimization k-additivity

来源：评论

学校读者我要写书评

暂无评论

Balancing profits and costs on trees

引用

NETWORKS 2013年第3期61卷 200-211页

作者： Coene, Sofie Filippi, Carlo Spieksma, Frits C. R. Stevanato, Elisa Katholieke Univ Leuven Operat Res Grp B-3000 Louvain Belgium Univ Brescia Dept Quantitat Methods I-25122 Brescia Italy

We consider a rooted tree graph with costs associated with the edges and profits associated with the vertices. Every subtree containing the root incurs the sum of the costs of its edges, and collects the sum of the profits of its nodes;the goal is the simultaneous minimization of the total cost and maximization of the total profit. This problem is related to the TSP with profits on graphs with a tree metric. We analyze the problem from a biobjective point of view. We show that finding all extreme supported efficient points can be done in polynomial time. The problem of finding all efficient points, however, is harder;we propose a practical FPTAS for solving this problem. Some special cases are considered where the particular profit/cost structure or graph topology allows the efficient points to be found in polynomial time. Our results can be extended to more general graphs with distance matrices satisfying the Kalmanson conditions. (c) 2012 Wiley Periodicals, Inc. NETWORKS, 2013

关键词： multiobjective combinatorial optimization trees traveling salesman problem with profits Kalmanson conditions complexity

来源：评论

学校读者我要写书评

暂无评论

On a biobjective search problem in a line: Formulations and algorithms

引用

THEORETICAL COMPUTER SCIENCE 2013年 507卷 61-71页

作者： Paquete, Luis Jaschob, Mathias Klamroth, Kathrin Gorski, Jochen Univ Coimbra Dept Informat Engn CISUC P-3000 Coimbra Portugal Univ Wuppertal Dept Math & Nat Sci Wuppertal Germany

In this article we describe three formulations of a multiobjective combinatorial optimization problem, as well as several complexity results and structural properties of these formulations. A multiobjective dynamic programming algorithm is proposed for each of the three formulations. Based on our theoretical and computational results we argue that a clever definition of the recursion, allowing for strong dominance criteria, is crucial in the design of a multiobjective dynamic programming algorithm. (C) 2013 Elsevier B.V. All rights reserved.

关键词： multiobjective combinatorial optimization Dynamic programming Shortest path problems Knapsack problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：