The knapsack problem is a classical combinatorial optimization problem widely encountered in areas such as logistics,resource allocation,and portfolio optimization.Traditional methods,including dynamic program-ming(DP...The knapsack problem is a classical combinatorial optimization problem widely encountered in areas such as logistics,resource allocation,and portfolio optimization.Traditional methods,including dynamic program-ming(DP)and greedy algorithms,have been effective in solving small problem instances but often struggle with scalability and efficiency as the problem size increases.DP,for instance,has exponential time complexity and can become computationally prohibitive for large problem instances.On the other hand,greedy algorithms offer faster solutions but may not always yield the optimal results,especially when the problem involves complex constraints or large numbers of items.This paper introduces a novel reinforcement learning(RL)approach to solve the knapsack problem by enhancing the state representation within the learning environment.We propose a representation where item weights and volumes are expressed as ratios relative to the knapsack’s capacity,and item values are normalized to represent their percentage of the total value across all items.This novel state modification leads to a 5%improvement in accuracy compared to the state-of-the-art RL-based algorithms,while significantly reducing execution time.Our RL-based method outperforms DP by over 9000 times in terms of speed,making it highly scalable for larger problem instances.Furthermore,we improve the performance of the RL model by incorporating Noisy layers into the neural network architecture.The addition of Noisy layers enhances the exploration capabilities of the agent,resulting in an additional accuracy boost of 0.2%–0.5%.The results demonstrate that our approach not only outperforms existing RL techniques,such as the Transformer model in terms of accuracy,but also provides a substantial improvement than DP in computational efficiency.This combination of enhanced accuracy and speed presents a promising solution for tackling large-scale optimization problems in real-world applications,where both precision and time are critical factors.展开更多
We propose an unbounded fully homomorphic encryption scheme, i.e. a scheme that allows one to compute on encrypted data for any desired functions without needing to decrypt the data or knowing the decryption keys. Thi...We propose an unbounded fully homomorphic encryption scheme, i.e. a scheme that allows one to compute on encrypted data for any desired functions without needing to decrypt the data or knowing the decryption keys. This is a rational solution to an old problem proposed by Rivest, Adleman, and Dertouzos [1] in 1978, and to some new problems that appeared in Peikert [2] as open questions 10 and open questions 11 a few years ago. Our scheme is completely different from the breakthrough work [3] of Gentry in 2009. Gentry’s bootstrapping technique constructs a fully homomorphic encryption (FHE) scheme from a somewhat homomorphic one that is powerful enough to evaluate its own decryption function. To date, it remains the only known way of obtaining unbounded FHE. Our construction of an unbounded FHE scheme is straightforward and can handle unbounded homomorphic computation on any refreshed ciphertexts without bootstrapping transformation technique.展开更多
This paper focuses on the 2-median location improvement problem on tree networks and the problem is to modify the weights of edges at the minimum cost such that the overall sum of the weighted distance of the vertices...This paper focuses on the 2-median location improvement problem on tree networks and the problem is to modify the weights of edges at the minimum cost such that the overall sum of the weighted distance of the vertices to the respective closest one of two prescribed vertices in the modified network is upper bounded by a given value.l1 norm and l∞norm are used to measure the total modification cost. These two problems have a strong practical application background and important theoretical research value. It is shown that such problems can be transformed into a series of sum-type and bottleneck-type continuous knapsack problems respectively.Based on the property of the optimal solution two O n2 algorithms for solving the two problems are proposed where n is the number of vertices on the tree.展开更多
Aiming at the problems of convergence-slow and convergence-free of Discrete Particle Swarm Optimization Algorithm(DPSO) in solving large scale or complicated discrete problem, this article proposes Intuitionistic Fuzz...Aiming at the problems of convergence-slow and convergence-free of Discrete Particle Swarm Optimization Algorithm(DPSO) in solving large scale or complicated discrete problem, this article proposes Intuitionistic Fuzzy Entropy of Discrete Particle Swarm Optimization(IFDPSO) and makes it applied to Dynamic Weapon Target Assignment(WTA). First, the strategy of choosing intuitionistic fuzzy parameters of particle swarm is defined, making intuitionistic fuzzy entropy as a basic parameter for measure and velocity mutation. Second, through analyzing the defects of DPSO, an adjusting parameter for balancing two cognition, velocity mutation mechanism and position mutation strategy are designed, and then two sets of improved and derivative algorithms for IFDPSO are put forward, which ensures the IFDPSO possibly search as much as possible sub-optimal positions and its neighborhood and the algorithm ability of searching global optimal value in solving large scale 0-1 knapsack problem is intensified. Third, focusing on the problem of WTA, some parameters including dynamic parameter for shifting firepower and constraints are designed to solve the problems of weapon target assignment. In addition, WTA Optimization Model with time and resource constraints is finally set up, which also intensifies the algorithm ability of searching global and local best value in the solution of WTA problem. Finally, the superiority of IFDPSO is proved by several simulation experiments. Particularly, IFDPSO, IFDPSO1~IFDPSO3 are respectively effective in solving large scale, medium scale or strict constraint problems such as 0-1 knapsack problem and WTA problem.展开更多
Some novel applications and pragmatic variations of knapsack problem （KP） are presented and constructed, which are formulated and developed from a model initiated in this paper on profit allocation from partition of...Some novel applications and pragmatic variations of knapsack problem （KP） are presented and constructed, which are formulated and developed from a model initiated in this paper on profit allocation from partition of jobs in terms of two-person discrete cooperation game.展开更多
In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding ...In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding feasible solutions. The Lagrangian relaxations were solved with the maximum-flow algorithm and the Lagrangian bounds was determined with the outer approximation method. Computational results show the efficiency of the proposed method for multi-dimensional quadratic 0-1 knapsack problems.展开更多
Similar to the classical meet-in-the-middle algorithm,the storage and computation complexity are the key factors that decide the efficiency of the quantum meet-in-the-middle algorithm.Aiming at the target vector of fi...Similar to the classical meet-in-the-middle algorithm,the storage and computation complexity are the key factors that decide the efficiency of the quantum meet-in-the-middle algorithm.Aiming at the target vector of fixed weight,based on the quantum meet-in-the-middle algorithm,the algorithm for searching all n-product vectors with the same weight is presented,whose complexity is better than the exhaustive search algorithm.And the algorithm can reduce the storage complexity of the quantum meet-in-the-middle search algorithm.Then based on the algorithm and the knapsack vector of the Chor-Rivest public-key crypto of fixed weight d,we present a general quantum meet-in-th√e-middle search algorithm based on the target solution of fixed weight,whose computational complexity is∑(d to j=0)(O((1/2)(C^(d-j)_(n-k+1))+O(C^j_klog C^j_k))with∑(d to i=0)C^i_k memory cost.And the optimal value of k is given.Compared to thequantum meet-in-the-middle search algorithm for knapsack problem and the quantum algorithm for searching a target solution of fixed weight,the computational complexity of the algorithm is lower.And its storage complexity is smaller than the quantum meet-in-the-middle-algorithm.展开更多
Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem i...Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem is often encountered in resource allocation, industrial planning and computer network. In this paper, a new convergent Lagrangian dual method was proposed for solving this problem. Cutting plane method was used to solve the dual problem and to compute the Lagrangian bounds of the primal problem. In order to eliminate the duality gap and thus to guarantee the convergence of the algorithm, domain cut technique was employed to remove certain integer boxes and partition the revised domain to a union of integer boxes. Extensive computational results show that the proposed method is efficient for solving large-scale multi-dimensional nonlinear knapsack problems. Our numerical results also indicate that the cutting plane method significantly outperforms the subgradient method as a dual search procedure.展开更多
This article introduces a fleet composition algorithm for a fleet of intermediate carriers, which should deliver a swarm of miniature unmanned aerial vehicles （mini-UAVs） to a mission area. The algorithm is based on...This article introduces a fleet composition algorithm for a fleet of intermediate carriers, which should deliver a swarm of miniature unmanned aerial vehicles （mini-UAVs） to a mission area. The algorithm is based on the sequential solution of several knapsack problems with various constraints. The algorithm allows both to form an initial set of required types of intermediate carriers, and to generate a fleet of intermediate carriers. The formation of a fleet of intermediate carriers to solve a suppression of enemy air defense （SEAD） problem is presented to illustrate the proposed algorithm.展开更多
In this paper a hybrid parallel multi-objective genetic algorithm is proposed for solving 0/1 knapsack problem. Multi-objective problems with non-convex and discrete Pareto front can take enormous computation time to ...In this paper a hybrid parallel multi-objective genetic algorithm is proposed for solving 0/1 knapsack problem. Multi-objective problems with non-convex and discrete Pareto front can take enormous computation time to converge to the true Pareto front. Hence, the classical multi-objective genetic algorithms (MOGAs) (i.e., non- Parallel MOGAs) may fail to solve such intractable problem in a reasonable amount of time. The proposed hybrid model will combine the best attribute of island and Jakobovic master slave models. We conduct an extensive experimental study in a multi-core system by varying the different size of processors and the result is compared with basic parallel model i.e., master-slave model which is used to parallelize NSGA-II. The experimental results confirm that the hybrid model is showing a clear edge over master-slave model in terms of processing time and approximation to the true Pareto front.展开更多
A revised weight-coded evolutionary algorithm (RWCEA) is proposed for solving multidimensional knapsack problems. This RWCEA uses a new decoding method and incorporates a heuristic method in initialization. Computatio...A revised weight-coded evolutionary algorithm (RWCEA) is proposed for solving multidimensional knapsack problems. This RWCEA uses a new decoding method and incorporates a heuristic method in initialization. Computational results show that the RWCEA performs better than a weight-coded evolutionary algorithm pro-posed by Raidl (1999) and to some existing benchmarks, it can yield better results than the ones reported in the OR-library.展开更多
The 0/1 Multidimensional Knapsack Problem (0/1 MKP) is an interesting NP-hard combinatorial optimization problem that can model a number of challenging applications in logistics, finance, telecommunications and other ...The 0/1 Multidimensional Knapsack Problem (0/1 MKP) is an interesting NP-hard combinatorial optimization problem that can model a number of challenging applications in logistics, finance, telecommunications and other fields. In the 0/1 MKP, a set of items is given, each with a size and value, which has to be placed into a knapsack that has a certain number of dimensions having each a limited capacity. The goal is to find a subset of items leading to the maximum total profit while respecting the capacity constraints. Even though the 0/1 MKP is well studied in the literature, we can just find a little number of recent review papers on this problem. Furthermore, the existing reviews focus particularly on some specific issues. This paper aims to give a general and comprehensive survey of the considered problem so that it can be useful for both researchers and practitioners. Indeed, we first describe the 0/1 MKP and its relevant variants. Then, we present the detailed models of some important real-world applications of this problem. Moreover, an important collection of recently published heuristics and metaheuristics is categorized and briefly reviewed. These approaches are then quantitatively compared through some indicative statistics. Finally, some synthetic remarks and research directions are highlighted in the conclusion.展开更多
Particle Swarm Optimization,a potential swarm intelligence heuristic,has been recognized as a global optimizer for solving various continuous as well as discrete optimization problems.Encourged by the performance of G...Particle Swarm Optimization,a potential swarm intelligence heuristic,has been recognized as a global optimizer for solving various continuous as well as discrete optimization problems.Encourged by the performance of Gompertz PSO on a set of continuous problems,this works extends the application of Gompertz PSO for solving binary optimization problems.Moreover,a new chaotic variant of Gompertz PSO namely Chaotic Gompertz Binary Particle Swarm Optimization(CGBPSO)has also been proposed.The new variant is further analysed for solving binary optimization problems.The new chaotic variant embeds the notion of chaos into GBPSO in later stages of searching process to avoid stagnation phenomena.The efficiency of both the Binary PSO variants has been tested on different sets of Knapsack Problems(KPs):0-1 Knapsack Problem(0-1 KP)and Multidimensional Knapsack Problems(MKP).The concluding remarks have made on the basis of detailed analysis of results,which comprises the comparison of results for Knapsack and Multidimensional Knapsack problems obtained using BPSO,GBPSO and CGBPSO.展开更多
The paper proposes a new sequential digital multi-signature scheme based on Knapsack public-key cryptosystem,which is different from the existing scheme.The advantages of this scheme over the existing schemes are that...The paper proposes a new sequential digital multi-signature scheme based on Knapsack public-key cryptosystem,which is different from the existing scheme.The advantages of this scheme over the existing schemes are that it simplifies the signature generation process and speeds up the signature verification process.What’s more,the scheme reduces the cost of communication and redundancy operation, and improves efficiency,and can avoid cheating by signer efficiently,so the scheme has very broad application prospects.展开更多
The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a ca...The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a capacity Ci.The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks.MKP(B,S,m,n) is strongly NP- Complete and no polynomial- time approximation algorithm can have an approxima- tion ratio better than0 .5 .In the last ten years,semi- definite programming has been empolyed to solve some combinatorial problems successfully.This paper firstly presents a semi- definite re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .展开更多
The set-union knapsack problem(SUKP)is proved to be a strongly NP-hard problem,and it is an extension of the classic NP-hard problem:the 0-1 knapsack problem(KP).Solving the SUKP through exact approaches is computatio...The set-union knapsack problem(SUKP)is proved to be a strongly NP-hard problem,and it is an extension of the classic NP-hard problem:the 0-1 knapsack problem(KP).Solving the SUKP through exact approaches is computationally expensive.Therefore,several swarm intelligent algorithms have been proposed in order to solve the SUKP.Hyper-heuristics have received notable attention by researchers in recent years,and they are successfully applied to solve the combinatorial optimization problems.In this article,we propose a binary particle swarm optimization(BPSO)based hyper-heuristic for solving the SUKP,in which the BPSO is employed as a search methodology.The proposed approach has been evaluated on three sets of SUKP instances.The results are compared with 6 approaches:BABC,EMS,gPSO,DHJaya,b WSA,and HBPSO/TS,and demonstrate that the proposed approach for the SUKP outperforms other approaches.展开更多
基金supported in part by the Research Start-Up Funds of South-Central Minzu University under Grants YZZ23002,YZY23001,and YZZ18006in part by the Hubei Provincial Natural Science Foundation of China under Grants 2024AFB842 and 2023AFB202+3 种基金in part by the Knowledge Innovation Program of Wuhan Basic Research underGrant 2023010201010151in part by the Spring Sunshine Program of Ministry of Education of the People’s Republic of China under Grant HZKY20220331in part by the Funds for Academic Innovation Teams and Research Platformof South-CentralMinzu University Grant Number:XT224003,PTZ24001in part by the Career Development Fund(CDF)of the Agency for Science,Technology and Research(A*STAR)(Grant Number:C233312007).
文摘The knapsack problem is a classical combinatorial optimization problem widely encountered in areas such as logistics,resource allocation,and portfolio optimization.Traditional methods,including dynamic program-ming(DP)and greedy algorithms,have been effective in solving small problem instances but often struggle with scalability and efficiency as the problem size increases.DP,for instance,has exponential time complexity and can become computationally prohibitive for large problem instances.On the other hand,greedy algorithms offer faster solutions but may not always yield the optimal results,especially when the problem involves complex constraints or large numbers of items.This paper introduces a novel reinforcement learning(RL)approach to solve the knapsack problem by enhancing the state representation within the learning environment.We propose a representation where item weights and volumes are expressed as ratios relative to the knapsack’s capacity,and item values are normalized to represent their percentage of the total value across all items.This novel state modification leads to a 5%improvement in accuracy compared to the state-of-the-art RL-based algorithms,while significantly reducing execution time.Our RL-based method outperforms DP by over 9000 times in terms of speed,making it highly scalable for larger problem instances.Furthermore,we improve the performance of the RL model by incorporating Noisy layers into the neural network architecture.The addition of Noisy layers enhances the exploration capabilities of the agent,resulting in an additional accuracy boost of 0.2%–0.5%.The results demonstrate that our approach not only outperforms existing RL techniques,such as the Transformer model in terms of accuracy,but also provides a substantial improvement than DP in computational efficiency.This combination of enhanced accuracy and speed presents a promising solution for tackling large-scale optimization problems in real-world applications,where both precision and time are critical factors.
文摘We propose an unbounded fully homomorphic encryption scheme, i.e. a scheme that allows one to compute on encrypted data for any desired functions without needing to decrypt the data or knowing the decryption keys. This is a rational solution to an old problem proposed by Rivest, Adleman, and Dertouzos [1] in 1978, and to some new problems that appeared in Peikert [2] as open questions 10 and open questions 11 a few years ago. Our scheme is completely different from the breakthrough work [3] of Gentry in 2009. Gentry’s bootstrapping technique constructs a fully homomorphic encryption (FHE) scheme from a somewhat homomorphic one that is powerful enough to evaluate its own decryption function. To date, it remains the only known way of obtaining unbounded FHE. Our construction of an unbounded FHE scheme is straightforward and can handle unbounded homomorphic computation on any refreshed ciphertexts without bootstrapping transformation technique.
基金The National Natural Science Foundation of China(No.10801031)
文摘This paper focuses on the 2-median location improvement problem on tree networks and the problem is to modify the weights of edges at the minimum cost such that the overall sum of the weighted distance of the vertices to the respective closest one of two prescribed vertices in the modified network is upper bounded by a given value.l1 norm and l∞norm are used to measure the total modification cost. These two problems have a strong practical application background and important theoretical research value. It is shown that such problems can be transformed into a series of sum-type and bottleneck-type continuous knapsack problems respectively.Based on the property of the optimal solution two O n2 algorithms for solving the two problems are proposed where n is the number of vertices on the tree.
基金supported by The National Natural Science Foundation of China under Grant Nos.61402517, 61573375The Foundation of State Key Laboratory of Astronautic Dynamics of China under Grant No. 2016ADL-DW0302+2 种基金The Postdoctoral Science Foundation of China under Grant Nos. 2013M542331, 2015M572778The Natural Science Foundation of Shaanxi Province of China under Grant No. 2013JQ8035The Aviation Science Foundation of China under Grant No. 20151996015
文摘Aiming at the problems of convergence-slow and convergence-free of Discrete Particle Swarm Optimization Algorithm(DPSO) in solving large scale or complicated discrete problem, this article proposes Intuitionistic Fuzzy Entropy of Discrete Particle Swarm Optimization(IFDPSO) and makes it applied to Dynamic Weapon Target Assignment(WTA). First, the strategy of choosing intuitionistic fuzzy parameters of particle swarm is defined, making intuitionistic fuzzy entropy as a basic parameter for measure and velocity mutation. Second, through analyzing the defects of DPSO, an adjusting parameter for balancing two cognition, velocity mutation mechanism and position mutation strategy are designed, and then two sets of improved and derivative algorithms for IFDPSO are put forward, which ensures the IFDPSO possibly search as much as possible sub-optimal positions and its neighborhood and the algorithm ability of searching global optimal value in solving large scale 0-1 knapsack problem is intensified. Third, focusing on the problem of WTA, some parameters including dynamic parameter for shifting firepower and constraints are designed to solve the problems of weapon target assignment. In addition, WTA Optimization Model with time and resource constraints is finally set up, which also intensifies the algorithm ability of searching global and local best value in the solution of WTA problem. Finally, the superiority of IFDPSO is proved by several simulation experiments. Particularly, IFDPSO, IFDPSO1~IFDPSO3 are respectively effective in solving large scale, medium scale or strict constraint problems such as 0-1 knapsack problem and WTA problem.
基金Supported by the Research Fund of Shenzhen University(200552).
文摘Some novel applications and pragmatic variations of knapsack problem （KP） are presented and constructed, which are formulated and developed from a model initiated in this paper on profit allocation from partition of jobs in terms of two-person discrete cooperation game.
基金Project supported by the National Natural Science Foundation of China （Grant No.10571116）
文摘In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding feasible solutions. The Lagrangian relaxations were solved with the maximum-flow algorithm and the Lagrangian bounds was determined with the outer approximation method. Computational results show the efficiency of the proposed method for multi-dimensional quadratic 0-1 knapsack problems.
基金Supported by the National Basic Research Program of China under Grant No.2013CB338002the National Natural Science Foundation of China under Grant No.61502526
文摘Similar to the classical meet-in-the-middle algorithm,the storage and computation complexity are the key factors that decide the efficiency of the quantum meet-in-the-middle algorithm.Aiming at the target vector of fixed weight,based on the quantum meet-in-the-middle algorithm,the algorithm for searching all n-product vectors with the same weight is presented,whose complexity is better than the exhaustive search algorithm.And the algorithm can reduce the storage complexity of the quantum meet-in-the-middle search algorithm.Then based on the algorithm and the knapsack vector of the Chor-Rivest public-key crypto of fixed weight d,we present a general quantum meet-in-th√e-middle search algorithm based on the target solution of fixed weight,whose computational complexity is∑(d to j=0)(O((1/2)(C^(d-j)_(n-k+1))+O(C^j_klog C^j_k))with∑(d to i=0)C^i_k memory cost.And the optimal value of k is given.Compared to thequantum meet-in-the-middle search algorithm for knapsack problem and the quantum algorithm for searching a target solution of fixed weight,the computational complexity of the algorithm is lower.And its storage complexity is smaller than the quantum meet-in-the-middle-algorithm.
文摘Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem is often encountered in resource allocation, industrial planning and computer network. In this paper, a new convergent Lagrangian dual method was proposed for solving this problem. Cutting plane method was used to solve the dual problem and to compute the Lagrangian bounds of the primal problem. In order to eliminate the duality gap and thus to guarantee the convergence of the algorithm, domain cut technique was employed to remove certain integer boxes and partition the revised domain to a union of integer boxes. Extensive computational results show that the proposed method is efficient for solving large-scale multi-dimensional nonlinear knapsack problems. Our numerical results also indicate that the cutting plane method significantly outperforms the subgradient method as a dual search procedure.
基金supported by the National Natural Science Foundation of China(60774064)the Aerospace Science Foundation (20085153015)
文摘This article introduces a fleet composition algorithm for a fleet of intermediate carriers, which should deliver a swarm of miniature unmanned aerial vehicles （mini-UAVs） to a mission area. The algorithm is based on the sequential solution of several knapsack problems with various constraints. The algorithm allows both to form an initial set of required types of intermediate carriers, and to generate a fleet of intermediate carriers. The formation of a fleet of intermediate carriers to solve a suppression of enemy air defense （SEAD） problem is presented to illustrate the proposed algorithm.
文摘In this paper a hybrid parallel multi-objective genetic algorithm is proposed for solving 0/1 knapsack problem. Multi-objective problems with non-convex and discrete Pareto front can take enormous computation time to converge to the true Pareto front. Hence, the classical multi-objective genetic algorithms (MOGAs) (i.e., non- Parallel MOGAs) may fail to solve such intractable problem in a reasonable amount of time. The proposed hybrid model will combine the best attribute of island and Jakobovic master slave models. We conduct an extensive experimental study in a multi-core system by varying the different size of processors and the result is compared with basic parallel model i.e., master-slave model which is used to parallelize NSGA-II. The experimental results confirm that the hybrid model is showing a clear edge over master-slave model in terms of processing time and approximation to the true Pareto front.
文摘A revised weight-coded evolutionary algorithm (RWCEA) is proposed for solving multidimensional knapsack problems. This RWCEA uses a new decoding method and incorporates a heuristic method in initialization. Computational results show that the RWCEA performs better than a weight-coded evolutionary algorithm pro-posed by Raidl (1999) and to some existing benchmarks, it can yield better results than the ones reported in the OR-library.
文摘The 0/1 Multidimensional Knapsack Problem (0/1 MKP) is an interesting NP-hard combinatorial optimization problem that can model a number of challenging applications in logistics, finance, telecommunications and other fields. In the 0/1 MKP, a set of items is given, each with a size and value, which has to be placed into a knapsack that has a certain number of dimensions having each a limited capacity. The goal is to find a subset of items leading to the maximum total profit while respecting the capacity constraints. Even though the 0/1 MKP is well studied in the literature, we can just find a little number of recent review papers on this problem. Furthermore, the existing reviews focus particularly on some specific issues. This paper aims to give a general and comprehensive survey of the considered problem so that it can be useful for both researchers and practitioners. Indeed, we first describe the 0/1 MKP and its relevant variants. Then, we present the detailed models of some important real-world applications of this problem. Moreover, an important collection of recently published heuristics and metaheuristics is categorized and briefly reviewed. These approaches are then quantitatively compared through some indicative statistics. Finally, some synthetic remarks and research directions are highlighted in the conclusion.
文摘Particle Swarm Optimization,a potential swarm intelligence heuristic,has been recognized as a global optimizer for solving various continuous as well as discrete optimization problems.Encourged by the performance of Gompertz PSO on a set of continuous problems,this works extends the application of Gompertz PSO for solving binary optimization problems.Moreover,a new chaotic variant of Gompertz PSO namely Chaotic Gompertz Binary Particle Swarm Optimization(CGBPSO)has also been proposed.The new variant is further analysed for solving binary optimization problems.The new chaotic variant embeds the notion of chaos into GBPSO in later stages of searching process to avoid stagnation phenomena.The efficiency of both the Binary PSO variants has been tested on different sets of Knapsack Problems(KPs):0-1 Knapsack Problem(0-1 KP)and Multidimensional Knapsack Problems(MKP).The concluding remarks have made on the basis of detailed analysis of results,which comprises the comparison of results for Knapsack and Multidimensional Knapsack problems obtained using BPSO,GBPSO and CGBPSO.
基金supported by the National Key Lab.of Integrated Service Networks of Xidian University(No.ISN7-01)National Natural Science Foundation of China(No.60642008)
文摘The paper proposes a new sequential digital multi-signature scheme based on Knapsack public-key cryptosystem,which is different from the existing scheme.The advantages of this scheme over the existing schemes are that it simplifies the signature generation process and speeds up the signature verification process.What’s more,the scheme reduces the cost of communication and redundancy operation, and improves efficiency,and can avoid cheating by signer efficiently,so the scheme has very broad application prospects.
基金Supported by the National Natural Science Foundation of China(1 9971 0 78)
文摘The multiple knapsack problem denoted by MKP (B,S,m,n) can be defined as fol- lows.A set B of n items and a set Sof m knapsacks are given such thateach item j has a profit pjand weightwj,and each knapsack i has a capacity Ci.The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks.MKP(B,S,m,n) is strongly NP- Complete and no polynomial- time approximation algorithm can have an approxima- tion ratio better than0 .5 .In the last ten years,semi- definite programming has been empolyed to solve some combinatorial problems successfully.This paper firstly presents a semi- definite re- laxation algorithm (MKPS) for MKP (B,S,m,n) .It is proved that MKPS have a approxima- tion ratio better than 0 .5 for a subclass of MKP (B,S,m,n) with n≤ 1 0 0 ,m≤ 5 and maxnj=1{ wj} minmi=1{ Ci} ≤ 2 3 .
基金Supported partly by the Natural Science Foundation of Fujian Province(2020J01843)the Science and Technology Project of the Education Bureau of Fujian(JAT200403)
文摘The set-union knapsack problem(SUKP)is proved to be a strongly NP-hard problem,and it is an extension of the classic NP-hard problem:the 0-1 knapsack problem(KP).Solving the SUKP through exact approaches is computationally expensive.Therefore,several swarm intelligent algorithms have been proposed in order to solve the SUKP.Hyper-heuristics have received notable attention by researchers in recent years,and they are successfully applied to solve the combinatorial optimization problems.In this article,we propose a binary particle swarm optimization(BPSO)based hyper-heuristic for solving the SUKP,in which the BPSO is employed as a search methodology.The proposed approach has been evaluated on three sets of SUKP instances.The results are compared with 6 approaches:BABC,EMS,gPSO,DHJaya,b WSA,and HBPSO/TS,and demonstrate that the proposed approach for the SUKP outperforms other approaches.
