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

Implementing an efficient fptas for the 0-1 multi-objective knapsack problem

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2009年第1期198卷 47-56页

作者： Bazgan, Cristina Hugot, Hadrien Vanderpooten, Daniel Univ Paris 09 LAMSADE F-75775 Paris 16 France

In the present work, we are interested in the practical behavior of a new fully polynomial time approximation schemes (fptas) to solve the approximation version of the 0-1 multi-objective knapsack problem. The proposed methodology makes use of very general techniques (such as dominance relations in dynamic programming) and thus may be applicable in the implementation of fptas for other problems as well. Extensive numerical experiments on various types of instances in the bi and tri-objective cases establish that our method performs very well both in terms of CPU time and size of solved instances. We point out some reasons for the good practical performance of our algorithm. A comparison with an exact method and the fptas proposed in [Erlebach, T., Kellerer, H., Pferschy, U., 2002. Approximating multi-objective knapsack problems. Management Science 48 (12), 1603-1612] is also performed. (C) 2008 Elsevier B.V. All rights reserved,

关键词： multi-objective knapsack problem Approximation Dynamic programming Dominance relations Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Solving efficiently the 0-1 multi-objective knapsack problem

引用

COMPUTERS & OPERATIONS RESEARCH 2009年第1期36卷 260-279页

作者： Bazgan, Cristina Hugot, Hadrien Vanderpooten, Daniel Univ Paris 09 LAMSADE F-75775 Paris 16 France

In this paper, we present an approach, based on dynamic programming, for solving the 0-1 multi-objective knapsack problem. The main idea of the approach relies on the use of several complementary dominance relations to discard partial solutions that cannot lead to new non-dominated criterion vectors. This way, we obtain an efficient method that outperforms the existing methods both in terms of CPU time and size of solved instances. Extensive numerical experiments on various types of instances are reported. A comparison with other exact methods is also performed. In addition, for the first time to our knowledge, we present experiments in the three-objective case. (C) 2007 Elsevier Ltd. All rights reserved.

关键词： multi-objective knapsack problem Non-dominated criterion vectors Efficient solutions Dynamic programming Dominance relations Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Indicator Based Ant Colony Optimization for multi-objective knapsack problem 19th

Indicator Based Ant Colony Optimization for Multi-Objective ...

引用

19th International Conference on Knowledge Based and Intelligent Information and Engineering Systems (KES)

作者： Ben Mansour, Imen Alaya, Ines Univ Manouba Cosmos ENSI Manouba 2010 Tunisia

The use of metaheuristics to solve multi-objective optimization problems (MOP) is a very active research topic. Ant Colony Optimization (ACO) has received a growing interest in the last years for such problems. Many algorithms have been proposed in the literature to solve different MOP. This paper presents an indicator-based ant colony optimization algorithm called IBACO for the multi-objective knapsack problem (MOKP). The IBACO algorithm proposes a new idea that uses binary quality indicators to guide the search of artificial ants. These indicators were initially used by Zitzler and Kunzli in in the selection process of their evolutionary algorithm IBEA. In this paper, we use the indicator optimization principle to reinforce the best solutions by rewarding pheromone trails. We carry out a set of experiments on MOKP benchmark instances by applying the two binary indicators: epsilon indicator and hypervolume indicator. The comparison of the proposed algorithm with IBEA, ACO and other state-of-the-art evolutionary algorithms shows that IBACO is significantly better on most instances. (C) 2015 The Authors. Published by Elsevier B.V.

关键词： multi-objective Ant colony optimization binary-indicator optimization multi-objective knapsack problem

来源：评论

学校读者我要写书评

暂无评论

An efficient implementation for the 0-1 multi-objective knapsack problem

An efficient implementation for the 0-1 multi-objective knap...

引用

6th International Workshop on Experimental Algorithms

作者： Bazgan, Cristina Hugot, Hadrien Vanderpooten, Daniel Univ Paris 09 LAMSADE Pl Marechal Lattre Tassigny F-75775 Paris 16 France

ISBN: (纸本)9783540728443

In this paper, we present an approach, based on dynamic programming, for solving 0-1 multi-objective knapsack problems. The main idea of the approach relies on the use of several complementary dominance relations to discard partial solutions that cannot lead to new non-dominated criterion vectors. This way, we obtain an efficient method that outperforms the existing methods both in terms of CPU time and size of solved instances. Extensive numerical experiments on various types of instances are reported. A comparison with other exact methods is also performed. In addition, for the first time to our knowledge, we present experiments in the three-objective case.

关键词： multi-objective knapsack problem efficient solutions dynamic programming dominance relations combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

A practical efficient fptas for the 0-1 multi-objective knapsack problem

A practical efficient fptas for the 0-1 multi-objective knap...

引用

15th Annual European Symposium on Algorithms (ESA 2007)

作者： Bazgan, Cristina Hugot, Hadrien Vanderpooten, Daniel Univ Paris 09 LAMSADE Pl Marechal Lattre Tassigny F-75775 Paris 16 France

ISBN: (纸本)9783540755197

In the present work, we are interested in the practical behavior of a new fptas to solve the approximation version of the 0-1 multiobjective knapsack problem. Nevertheless, our methodology focuses on very general techniques (such as dominance relations in dynamic programming) and thus may be applicable in the implementation of fptas for other problems as well. Extensive numerical experiments on various types of instances establish that our method performs very well both in terms of CPU time and size of solved instances. We point out some reasons for the good practical performance of our algorithm. A comparison with an exact method is also performed.

关键词： multi-objective knapsack problem approximation dynamic programming dominance relations combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

A Mixed-Factor Evolutionary Algorithm for multi-objective knapsack problem 18th

A Mixed-Factor Evolutionary Algorithm for Multi-objective Kn...

引用

18th International Conference on Intelligent Computing (ICIC)

作者： Du, Yanlian Feng, Zejing Shen, Yijun Hainan Univ Sch Informat & Commun Engn Haikou 570228 Hainan Peoples R China Hainan Univ State Key Lab Marine Resources Utilizat South Chi Haikou 570228 Hainan Peoples R China Hainan Univ Coll Appl Sci & Technol Danzhou 571737 Peoples R China

ISBN: (纸本)9783031138706;9783031138690

Nondominated-sorting plays an important role in multi-objective evolutionary algorithm in recent decades. However, it fails to work well when the target multi-objective problem has a complex Pareto front, brusque nondominated-sorting virtually steers by the conflicting nature of objectives, which leads to irrationality. In this paper, a novel mixed-factor evolutionary algorithm is proposed. A normalization procedure, i.e. mixed-factor, is introduced in the objective space, which links all the objectives for all the solutions of the problem to ease the conflicting nature. In the process of nondominated-sorting, the mixed factors of individual substitute the raw objectives. In order to ensure that the population are thoroughly steered through the normalized objective space, hybrid ageing operator and static hypermutation with first constructive mutation are used to guide the searching agents converge towards the true Pareto front. The algorithm proposed is operated on multi-objective knapsack problem. The effectiveness of MFEA is compared with five state-of-the-art algorithms, i.e., NSGA-II, NSGA-III, MOEA/D, SPEA2 and GrEA, in terms of five performance metrics. Simulation results demonstrate that MFEA achieves better performance.

关键词： multi-objective evolutionary algorithm Mixed-factor evolutionary algorithm multi-objective knapsack problem Normalization procedure

来源：评论

学校读者我要写书评

暂无评论

Indicator Based Ant Colony Optimization for multi-objective knapsack problem

引用

Procedia Computer Science 2015年 60卷 448-457页

作者： Imen Ben Mansour Ines Alaya Cosmos-ENSI University of Manouba Manouba 2010 Tunisia

The use of metaheuristics to solve multi-objective optimization problems (MOP) is a very active research topic. Ant Colony Optimization (ACO) has received a growing interest in the last years for such problems. Many algorithms have been proposed in the literature to solve different MOP. This paper presents an indicator-based ant colony optimization algorithm called IBACO for the multi-objective knapsack problem (MOKP). The IBACO algorithm proposes a new idea that uses binary quality indicators to guide the search of artificial ants. These indicators were initially used by Zitzler and Künzli in the selection process of their evolutionary algorithm IBEA. In this paper, we use the indicator optimization principle to reinforce the best solutions by rewarding pheromone trails. We carry out a set of experiments on MOKP benchmark instances by applying the two binary indicators: epsilon indicator and hypervolume indicator. The comparison of the proposed algorithm with IBEA, ACO and other state-of-the-art evolutionary algorithms shows that IBACO is significantly better on most instances.

关键词： multi-objective Ant colony optimization binary-indicator optimization multi-objective knapsack problem

来源：评论

学校读者我要写书评

暂无评论

Screening alternatives in multiple criteria subset selection

引用

INFOR 2004年第1期42卷 43-60页

作者： Kilgour, DM Rajabi, S Hipel, KW Chen, Y Wilfrid Laurier Univ Dept Math Waterloo ON N2L 3C5 Canada i2 Technol Dallas TX 75234 USA Univ Waterloo Dept Syst Design Engn Waterloo ON N2L 3G1 Canada

New techniques are presented to reduce the number of feasible alternatives in certain multiple criteria subset selection problems, thereby making it less difficult to find a good subset. The class of m-best alternatives problems is defined and the relation between dominance and potential optimality explored in the context of this class. A program is proposed to identify whether an individually dominated alternative can belong to an optimal subset satisfying certain pre-specified constraints. The extension of the proposed method to multi-objective knapsack problems is considered. Two examples illustrate the screening procedure for m-best alternatives problems and multi-objective knapsack problems.

关键词： multiple criteria decision aid screening efficient solutions potential optimality multi-objective knapsack problem

来源：评论

学校读者我要写书评

暂无评论

Solution approaches for equitable multiobjective integer programming problems

引用

ANNALS OF OPERATIONS RESEARCH 2022年第2期311卷 967-995页

作者： Bashir, Bashir Karsu, Ozlem Bilkent Univ Dept Ind Engn Ankara Turkey

We consider multi-objective optimization problems where the decision maker (DM) has equity concerns. We assume that the preference model of the DM satisfies properties related to inequity-aversion, hence we focus on finding nondominated solutions in line with the properties of inequity-averse preferences, namely the equitably nondominated solutions. We discuss two algorithms for finding good subsets of equitably nondominated solutions. The first approach is an extension of an interactive approach developed for finding the most preferred nondominated solution when the utility function is assumed to be quasiconcave. We find the most preferred equitably nondominated solution when the utility function is assumed to be symmetric quasiconcave. In the second approach we generate an evenly distributed subset of the set of equitably nondominated solutions to be considered further by the DM. We show the computational feasibility of the two algorithms on equitable multi-objective knapsack problem, in which projects in different categories are to be funded subject to a limited budget. We perform experiments to show and discuss the performances of the algorithms.

关键词： Equitable preferences Equitable efficiency Equitable dominance Generalized Lorenz dominance multi-objective knapsack problem Convex cones Fairness multiobjective integer programming Interactive algorithm

来源：评论

学校读者我要写书评

暂无评论

Hybrid Directional-Biased Evolutionary Algorithm for multi-objective Optimization

Hybrid Directional-Biased Evolutionary Algorithm for Multi-O...

引用

11th International Conference on Parallel problem Solving from Nature

作者： Shimada, Tomohiro Otani, Masayuki Matsushima, Hiroyasu Sato, Hiroyuki Hattori, Kiyohiko Takadama, Keiki Univ Electrocommun Tokyo 1828585 Japan

ISBN: (纸本)9783642158704

This paper proposes the hybrid Indicator-based Directional-biased Evolutionary Algorithm (hIDEA) and verifies its effectiveness through the simulations of the multi-objective 0/1 knapsack problem. Although the conventional multi-objective Optimization Evolutionary Algorithms (MOEA5) regard the weights of all objective functions as equally, hIDEA biases the weights of the objective functions in order to search not only the center of true Pareto optimal solutions but also near the edges of them. Intensive simulations have revealed that hIDEA is able to search the Pareto optimal solutions widely and accurately including the edge of true ones in comparison with the conventional methods.

关键词： multi-objective optimization evolutionary algorithm indicator multi-objective knapsack problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：