:::

詳目顯示

回上一頁
題名:Solving the 0/1 Knapsack Problem Using Rough Sets and Genetic Algorithms
書刊名:工業工程學刊
作者:楊旭豪王世文
作者(外文):Yang, Hsu-haoWang, Shih-wen
出版日期:2011
卷期:28:5
頁次:頁360-369
主題關鍵詞:約略集基因演算法0/1背包問題最佳化Rough setsGenetic algorithms0/1 Knapsack problemOptimization
原始連結:連回原系統網址new window
相關次數:
  • 被引用次數被引用次數:期刊(0) 博士論文(0) 專書(0) 專書論文(0)
  • 排除自我引用排除自我引用:0
  • 共同引用共同引用:0
  • 點閱點閱:25
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.
期刊論文
1.Pawlak, Z.(1982)。Rough Set。International journal of information and computer sciences,11(1),341-356。  new window
圖書
1.Gen, M.、Cheng, R.(1997)。Genetic Algorithms and Engineering Design。New York:John Wiley & Sons。  new window
2.Garey, Michael R.、Johnson, David S.(1979)。Computers and Intractability: A Guide to the theory of NP-Completeness。W. H. Freeman and Company。  new window
3.Holland, J. H.(1975)。Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence。MI:University of Michigan Press。  new window
其他
1.Anagun, A.S. and T. Sarac(2006)。Optimization performance of genetic algorithm for 0-1 knapsack problems using Taguchi method。  new window
2.Bhatia, A.K. and S.K. Basu(2003)。Tackling 0/1 knapsack problem with gene induction。  new window
3.Caccetta, L. and A. Kulanoot(2001)。Computational aspects on hard knapsack problems。  new window
4.Calvin, J.M. and J.Y.T. Leung(2003)。Average-case analysis of a greedy algorithm for the 0/1 knapsack problem。  new window
5.Kumar, R. and P.K. Singh(2010)。Assessing solution quality of biobjective 0-1 knapsack problem using evolutionary and heuristic algorithms。  new window
6.Martello, S., D. Pisinger and P. Toth(2000)。New trend in exact algorithms for the 0-1 knapsack problem。  new window
7.Olsen, A.L.(1994)。Penalty functions and the knapsack problem。  new window
8.Taguch, G., S. Chowdhury and Y. Wu(2004)。Taguchi’s Quality Engineering Handbook。  new window
9.Xue, D. and Y. Chen(2004)。Solving Advanced Applied Mathematical Problems with MATLAB。  new window
10.Yang, H.H., S.W. Wang, H.T. Ko and J.C. Lin(2009)。A novel approach for crossover based on attribute reduction - a case of 0/1 knapsack problem。  new window
 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top
QR Code
QRCODE