فهرست مقالات Knapsack problem

• دسترسی آزاد مقاله
  • صفحه چکیده
  • متن کامل
  
  1 - EMCSO: An Elitist Multi-Objective Cat Swarm Optimization
  Maysam Orouskhani Mohammad Teshnehlab Mohammad Ali Nekoui
  10.22094/joie.2017.500.12
  This paper introduces a novel multi-objective evolutionary algorithm based on cat swarm optimizationalgorithm (EMCSO) and its application to solve a multi-objective knapsack problem. The multi-objective optimizers try to find the closest solutions to true Pareto front ( چکیده کامل

  This paper introduces a novel multi-objective evolutionary algorithm based on cat swarm optimizationalgorithm (EMCSO) and its application to solve a multi-objective knapsack problem. The multi-objective optimizers try to find the closest solutions to true Pareto front (POF) where it will be achieved by finding the less-crowded non-dominated solutions. The proposed method applies cat swarm optimization (CSO), a swarm-based algorithm with ability of exploration and exploitation, to produce offspring solutions and uses thenon-dominated sorting method to findthe solutionsas close as to POFand crowding distance technique toobtain a uniform distribution among thenon-dominated solutions. Also, the algorithm is allowedto keep the elites of population in reproduction processand use an opposition-based learning method for population initialization to enhance the convergence speed.The proposed algorithm is tested on standard test functions (zitzler’ functions: ZDT) and its performance is compared with traditional algorithms and is analyzed based onperformance measures of generational distance (GD), inverted GD, spread,and spacing. The simulation results indicate that the proposed method gets the quite satisfactory results in comparison with other optimization algorithms for functions of ZDT1 and ZDT2. Moreover, the proposed algorithm is applied to solve multi-objective knapsack problem. پرونده مقاله
• دسترسی آزاد مقاله
  • صفحه چکیده
  • متن کامل
  
  2 - Speeding up the 0-1 Knapsack Problem Using Shuffled Frog Leaping Algorithm
  Farnaz Hoseini
  The knapsack problem is known as a NP-hard problem. The knapsack or rucksack problem consists of determining, given a set of items, each of which has a cost and a value, the number of items included in a collection such that the total cost is less than a given cost and چکیده کامل

  The knapsack problem is known as a NP-hard problem. The knapsack or rucksack problem consists of determining, given a set of items, each of which has a cost and a value, the number of items included in a collection such that the total cost is less than a given cost and the total value is as large as possible. There is a dynamic programming solution for this problem called the 0-1 knapsack. The 0-1 knapsack problem restricts the number of individual items to zero or one. The shuffled frog-leaping algorithm (SFLA) has long been considered a meta-heuristic algorithm that derives from how frog groups search for food. SFLA can improve computing performance by letting all frogs participate in memetic evolution and access an excellent ability for global search by adding the self-variation behavior to the frog. This study represents an efficient solution for the 0-1 knapsack problem using SFLA. Regarding the parallel nature of most meta-heuristic algorithms, they can be successfully used for speedup. Since it is time-consuming to test all the cases when the problems become larger, Compute Unified Device Architecture (CUDA) is used to implement the solution in parallel. The results of simulating the 0-1 knapsack problem using SFLA on the CUDA platform show that the execution time for a parallel solution decreases as the population of frogs increases. For the 0-1 Knapsack problem, it is 252 times faster than the sequential solution. پرونده مقاله
• دسترسی آزاد مقاله
  • صفحه چکیده
  • متن کامل
  
  3 - An employee transporting problem
  Ümit Yüceer
  An employee transporting problem is described and a set partitioning model is developed. An investigation of the model leads to a knapsack problem as a surrogate problem. Finding a partition corresponding to the knapsack problem provides a solution to the problem. An ex چکیده کامل

  An employee transporting problem is described and a set partitioning model is developed. An investigation of the model leads to a knapsack problem as a surrogate problem. Finding a partition corresponding to the knapsack problem provides a solution to the problem. An exact algorithm is proposed to obtain a partition (subset-vehicle combination) corresponding to the knapsack solution. It requires testing and matching too many alternatives to obtain a partition. The sweep algorithm is implemented in obtaining a partition (subset-vehicle combination) in an efficient manner. Illustrations are provided to show how the algorithms obtain solutions. پرونده مقاله
• دسترسی آزاد مقاله
  • صفحه چکیده
  • متن کامل
  
  4 - APPROXIMATE ALGORITHM FOR THE MULTI-DIMENSIONAL KNAPSACK PROBLEM BY USING MULTIPLE CRITERIA DECISION MAKING
  Majid Darehmiraki
  In this paper, an interesting and easy method to solve the multi-dimensional knapsack problem is presented. Although it belongs to the combinatorial optimization, but the proposed method belongs to the decision making field in mathematics. In order to, initially efficie چکیده کامل

  In this paper, an interesting and easy method to solve the multi-dimensional knapsack problem is presented. Although it belongs to the combinatorial optimization, but the proposed method belongs to the decision making field in mathematics. In order to, initially efficiency values for every item is calculated then items are ranked by using Multiple Criteria Decision Making (MCDA). Finally, items are selected in according to their rank. پرونده مقاله