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

multidimensional knapsack problem optimization using a binary particle swarm model with genetic operations

SOFT COMPUTING 2018年第8期22卷 2567-2582页

作者： Mingo Lopez, Luis Fernando Gomez Blas, Nuria Albert, Alberto Arteta Univ Politecn Madrid Dept Sistemas Informat Escuela Tecn Super Ingn Sistemas Informat Crta Valencia Km 7 Madrid 28031 Spain Troy Univ Dept Comp Sci Univ Ave Troy AL 36081 USA

Particle swarm optimization is a heuristic and stochastic technique inspired by the flock of birds when looking for food. It is currently being used to solve continuous and discrete optimization problems. This paper proposes a hybrid, genetic inspired algorithm that uses random mutation/crossover operations and adds penalty functions to solve a particular case: the multidimensional knapsack problem. The algorithm implementation uses particle swarm for binary variables with a genetic operator. The particles update is performed in the following way: first using the iterative process (standard algorithm) described in the PSO algorithm and then using the best particle position (local) and the best global position to perform a random crossover/mutation with the original particle. The mutation and crossover operations specifically apply to personal and global best individuals. The obtained results are promising compared to those obtained by using the probability binary particle swarm optimization algorithm.

关键词： Binary particle swarm optimization Combinatory optimization multidimensional knapsack problem Genetic operations

来源：评论

学校读者我要写书评

暂无评论

A discrete binary version of bat algorithm for multidimensional knapsack problem

引用

INTERNATIONAL JOURNAL OF BIO-INSPIRED COMPUTATION 2014年第2期6卷 140-152页

作者： Sabba, Sara Chikhi, Salim Constantine Univ 2 Fac Engn Sci Dept Comp Sci Constantine 25017 Algeria

The nature has become a main inspiration source of scientists for developing new intelligent systems and techniques. Nature-inspired meta-heuristics is a kind of algorithms that imitate the social behaviour of some biological species. The bat algorithm (BA) is a new bio-inspired algorithm recently introduced by Yang (2010a). It is an optimisation method that is based on the echolocation behaviour of microbats. Firstly, the BA has been proposed for continuous problems. In this paper, we propose a discrete binary bat algorithm (BinBA) for solving the optimisation problems in binary space. The proposed algorithm is based on the sigmoid function used by Kennedy and Eberhart in 1997 for their binary particle swarm optimisation algorithm. The BinBA was tested on hard instances of the multidimensional knapsack problem. The obtained results are very promising compared to other bio-inspired algorithms.

关键词： discrete optimisation problem bio-inspired algorithm bat algorithm binary bat algorithm multidimensional knapsack problem MKP

来源：评论

学校读者我要写书评

暂无评论

Application of Supervised Machine Learning Methods on the multidimensional knapsack problem

引用

NEURAL PROCESSING LETTERS 2022年第2期54卷 871-890页

作者： Rezoug, Abdellah Bader-el-den, Mohamed Boughaci, Dalila Univ Mhamed Bougara Dept Comp Sci Boumerdes Algeria Univ Portsmouth Sch Comp Portsmouth Hants England Univ Sci & Technol Houari Boumedienne Dept Comp Sci Algiers Algeria

Machine Learning (ML) has gained much importance in recent years as many of its effective applications are involved in different fields, healthcare, banking, trading, gaming, etc. Similarly, Combinatorial Optimisation (CO) keeps challenging researchers by new problems with more complex constraints. Merging both fields opens new horizons for development in many areas. This study investigates how effective is to solve CO problems by ML methods. The work considers the multidimensional knapsack problem (MKP) as a study case, which is an np-hard CO problem well-known for its multiple applications. The proposed approach suggests to use solutions of small-size MKP to build models with different ML methods;then, to apply the obtained models on large-size MKP to predict their solutions. The features consist of scores calculated based on information about items while the labels consist of decision variables of optimal solutions calculated from applying CPLEX Solver on small-size MKP. Supervised ML methods build models that help to predict structures of large-size MKP solutions and build them accordingly. A comparison of five ML methods is conducted on standard data set. The experiments showed that the tested methods were able to reach encouraging results. In addition, the study proposes a Genetic Algorithm (GA) that exploits ML outputs essentially in initialisation operator and to repair unfeasible solutions. The algorithm denoted GaPR explores the ML solution neighbourhood as a way of intensification to approach optimal solutions. The carried out experiments indicated that the approach was effective and competitive.

关键词： Machine learning multidimensional knapsack problem Genetic algorithm Combinatorial optimisation Evolutionary computation

来源：评论

学校读者我要写书评

暂无评论

A genetic programming hyper-heuristic for the multidimensional knapsack problem

引用

KYBERNETES 2014年第9-10期43卷 1500-1511页

作者： Drake, John H. Hyde, Matthew Ibrahim, Khaled Ozcan, Ender Univ Nottingham Sch Comp Sci Nottingham NG7 2RD England

Purpose - Hyper-heuristics are a class of high-level search techniques which operate on a search space of heuristics rather than directly on a search space of solutions. The purpose of this paper is to investigate the suitability of using genetic programming as a hyper-heuristic methodology to generate constructive heuristics to solve the multidimensional 0-1 knapsack problem Design/methodology/approach - Early hyper-heuristics focused on selecting and applying a low-level heuristic at each stage of a search. Recent trends in hyper-heuristic research have led to a number of approaches being developed to automatically generate new heuristics from a set of heuristic components. A population of heuristics to rank knapsack items are trained on a subset of test problems and then applied to unseen instances. Findings - The results over a set of standard benchmarks show that genetic programming can be used to generate constructive heuristics which yield human-competitive results. Originality/value - In this work the authors show that genetic programming is suitable as a method to generate reusable constructive heuristics for the multidimensional 0-1 knapsack problem. This is classified as a hyper-heuristic approach as it operates on a search space of heuristics rather than a search space of solutions. To our knowledge, this is the first time in the literature a GP hyper-heuristic has been used to solve the multidimensional 0-1 knapsack problem. The results suggest that using GP to evolve ranking mechanisms merits further future research effort.

关键词： Artificial intelligence Genetic programming Heuristic generation Hyper-heuristics multidimensional knapsack problem

来源：评论

学校读者我要写书评

暂无评论

Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2008年第2期15卷 165-178页

作者： Vimont, Yannick Boussier, Sylvain Vasquez, Michel LGI2P F-30035 Nimes 1 France

In a previous work we proposed a variable fixing heuristics for the 0-1 multidimensional knapsack problem (01MDK). This approach uses fractional optima calculated in hyperplanes which contain the binary optimum. This algorithm obtained best lower bounds on the OR-LIBRARY benchmarks. Although it is very attractive in terms of results, this method does not prove the optimality of the solutions found and may fix variables to a non-optimal value. In this paper, we propose an implicit enumeration based on a reduced costs analysis which tends to fix non-basic variables to their exact values. The combination of two specific constraint propagations based on reduced costs and an efficient enumeration framework enable us to fix variables on the one hand and to prune significantly the search tree on the other hand. Experimentally, our work provides two main contributions: (1) we obtain several new optimal solutions on hard instances of the OR-LIBRARY and (2) we reduce the bounds of the number of items at the optimum on several harder instances.

关键词： multidimensional knapsack problem implicit enumeration variable fixing reduced costs constraint propagation

来源：评论

学校读者我要写书评

暂无评论

Set-based particle swarm optimization applied to the multidimensional knapsack problem

引用

SWARM INTELLIGENCE 2012年第4期6卷 297-342页

作者： Langeveld, Joost Engelbrecht, Andries P. Univ Pretoria Dept Comp Sci ZA-0002 Pretoria South Africa

Particle swarm optimization algorithms have been successfully applied to discrete/valued optimization problems. However, in many cases the algorithms have been tailored specifically for the problem at hand. This paper proposes a generic set-based particle swarm optimization algorithm for use in discrete-valued optimization problems that can be formulated as set-based problems. A detailed sensitivity analysis of the parameters of the algorithm is conducted. The performance of the proposed algorithm is then compared against three other discrete particle swarm optimization algorithms from literature using the multidimensional knapsack problem and is shown to statistically outperform the existing algorithms.

关键词： Discrete optimization multidimensional knapsack problem Particle swarm optimization Set-based optimization problem

来源：评论

学校读者我要写书评

暂无评论

Heuristics for the 0-1 multidimensional knapsack problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2009年第3期199卷 658-664页

作者： Boyer, V. Elkihel, M. El Baz, D. Univ Toulouse CNRS LAAS F-31077 Toulouse 4 France

Two heuristics for the 0-1 multidimensional knapsack problem (MKP) are presented. The first one uses Surrogate relaxation, and the relaxed problem is solved via a modified dynamic-programming algorithm. The heuristics provides a feasible solution for (MKP). The second one combines a limited-branch-and-cut-procedure with the previous approach, and tries to improve the bound obtained by exploring some nodes that have been rejected by the modified dynamic-programming algorithm. Computational experiences show that our approaches give better results than the existing heuristics. and thus permit one to obtain a smaller gap between the solution provided and an optimal solution. (C) 2008 Elsevier B.V. All rights reserved.

关键词： multidimensional knapsack problem Dynamic-programming Branch-and-cut Surrogate relaxation Heuristics

来源：评论

学校读者我要写书评

暂无评论

Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem

引用

APPLIED SOFT COMPUTING 2015年 26卷 378-389页

作者： Chih, Mingchang Natl Chung Shan Inst Sci & Technol Syst Dev Ctr Taoyuan 32546 Taiwan

The multidimensional knapsack problem (MKP) is a combinatorial optimization problem belonging to the class of NP-hard problems. This study proposes a novel self-adaptive check and repair operator (SACRO) combined with particle swarm optimization (PSO) to solve the MKP. The traditional check and repair operator (CRO) uses a unique pseudo-utility ratio, whereas SACRO dynamically and automatically changes the alternative pseudo-utility ratio as the PSO algorithm runs. Two existing PSO algorithms are used as the foundation to support the novel SACRO methods, the proposed SACRO-based algorithms were tested using 137 benchmark problems from the OR-Library to validate and demonstrate the efficiency of SACRO idea. The results were compared with those of other population-based algorithms. Simulation and evaluation results show that SACRO is more competitive and robust than the traditional CRO. The proposed SACRO-based algorithms rival other state-of-the-art PSO and other algorithms. Therefore, changing different types of pseudo-utility ratios produces solutions with better results in solving MKP. Moreover, SACRO can be combined with other population-based optimization algorithms to solve constrained optimization problems. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Self adaptive check and repair multidimensional knapsack problem Particle swarm optimization Pseudo-utility ratio OR-Library

来源：评论

学校读者我要写书评

暂无评论

An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem

引用

EXPERT SYSTEMS WITH APPLICATIONS 2012年第5期39卷 5593-5599页

作者： Wang, Ling Wang, Sheng-yao Xu, Ye Tsinghua Univ Dept Automat TNList Beijing 100084 Peoples R China

In this paper, an effective hybrid algorithm based on estimation of distribution algorithm (EDA) is proposed to solve the multidimensional knapsack problem (MKP). With the framework of EDA, the probability model is built with the superior population and the new individuals are generated based on probability model. In addition, an updating mechanism of the probability model is proposed and a mechanism for initializing the probability model based on the specific knowledge of the MKP is also proposed to improve the convergence speed. Meanwhile, an adaptive local search is proposed to enhance the exploitation ability. Furthermore, the influences of parameters are investigated based on Taguchi method of design of experiment and the importance of repair operator is also studied via simulation testing and comparisons. Finally, numerical simulation is carried out based on the benchmark instances, and the comparisons with some existing algorithms demonstrate the effectiveness of the proposed algorithm. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： multidimensional knapsack problem Estimation of distribution algorithm Probability model Hybrid algorithm Design of experiment

来源：评论

学校读者我要写书评

暂无评论

A Pareto evolutionary algorithm based on incremental learning for a kind of multi-objective multidimensional knapsack problem

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2019年 135卷 537-559页

作者： Luo, Rong-juan Ji, Shou-feng Zhu, Bao-lin Northeastern Univ Sch Business Adm Shenyang 110167 Liaoning Peoples R China

multidimensional knapsack problem (MKP) is a classic combinatorial optimization problem arising from many practical applications. To be closer to real-life applications, this paper focuses on a special kind of multi-objective MKP (MOMKP), where the optimization objectives are to maximize the total profit and minimize the maximum consumption of multidimensional resources. To solve it, a Pareto evolutionary algorithm based on Incremental Learning (PEAIL) is proposed, whose components mainly consist of two parts, i.e., the online Incremental Learning and the nondominated sorting. PEAIL is unique in that it can extract the historical information of the search behavior and then feed them back to the main evolutionary framework. Firstly, problem-dependent heuristics, including genetic operators and a repair mechanism for infeasible solutions, are proposed and discussed. Secondly, an online Incremental Learning approach is put forward to learn the probability model of excellent solutions during the iteration process. Thereby, we can predict promising individuals from this probability model, which are used for further strengthening PEAIL's search ability. Thirdly, a simple yet effective competition-based improvement mechanism is proposed to refine the offspring of PEAIL. Finally, results of experiments on 45 benchmark instances and a real-life case study demonstrate the effectiveness and practical values of the proposed PEAIL.

关键词： multidimensional knapsack problem Multi-objective optimization Repair mechanism Incremental Learning Nondominated sorting

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：