Solving the 0/1 knapsack problem using rough sets and genetic algorithms

NCUTIR > College of Management > Development of Industrial Engineering and Management > 【工業工程與管理系所】期刊論文 > Item 987654321/6842

Please use this identifier to cite or link to this item: http://ir.lib.ncut.edu.tw/handle/987654321/6842

Title:	Solving the 0/1 knapsack problem using rough sets and genetic algorithms
Authors:	楊旭豪
Contributors:	工業工程與(工程)管理系
Date:	2011-07
Issue Date:	2017-12-17 11:04:33 (UTC+8)
Abstract:	This article proposes a methodology that introduces attribute reduction of rough sets into crossover of genetic algorithms (GAs), and then uses the methodology to develop two algorithms. The first algorithm selects the crossover points, either by attribute reduction or randomly; the second selects the crossover points solely by attribute reduction, with no crossover otherwise. We test the methodology on the solving of the 0/1 knapsack problem, due to the problem's NP-hard complexity, and we compare the experiment results to those of typical GAs. According to the results, the introduction of attribute reduction increases the mean and decreases the standard deviation of the final solutions, especially in the presence of tighter capacity, i.e. attribution reduction leads to better solution quality and more tightly clustered solutions. Moreover, the mean number of iterations required to terminate the algorithm and that required to reach maximal profits are significantly reduced.
Relation:	Journal of the Chinese Institute of Industrial Engineers
Appears in Collections:	[Development of Industrial Engineering and Management] 【工業工程與管理系所】期刊論文

Files in This Item:

There are no files associated with this item.

View Licence