(3.236.222.124) 您好!臺灣時間:2021/05/10 15:55
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:余秉璜
研究生(外文):Yu, Ping Huang
論文名稱:利用結合布隆過濾器的搜尋法處理複雜最佳化問題
論文名稱(外文):An Efficient Search Method Based on Bloom Filter for Expensive Optimization Problems
指導教授:丁川康丁川康引用關係
指導教授(外文):Ting, Chuan-Kang
口試委員:丁川康陳穎平蔣宗哲
口試委員(外文):Ting, Chuan-KangChen, Ying-pingChiang, Tsung-Che
口試日期:2011-07-05
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:中文
論文頁數:179
中文關鍵詞:布隆過濾器區域搜尋
外文關鍵詞:Bloom filterLocal search
相關次數:
  • 被引用被引用:0
  • 點閱點閱:202
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:20
  • 收藏至我的研究室書目清單書目收藏:0
摘要 啟發式演算法可分為兩種搜尋方式,區域搜尋和全域搜尋。前者搜尋快速且易於實作,後者不容易陷入區域最佳解。但無論是區域搜尋還是全域搜尋,它們都無法保證自己找到的解是否重覆。因此,兩種搜尋方式雖然各具特色且搜尋效率卓越,它們還是會重覆處理先前捨棄的解,增加演算法的搜尋時間。因此,很多研究致力於減少重覆計算的次數,藉以節省演算法的搜尋時間。最普遍的做法,就是利用額外的記憶體儲存搜尋的內容,當演算法又搜尋到相同的位置時,便可利用儲存的資訊,避免重複計算相同的解。近年來,有些研究甚至不限制記憶體的容量,試圖儲存所有演算法處理過的解,使演算法在容許的時間與記憶體空間下,能夠有更好的搜尋效率。

摘要 布隆過濾器自1970年由Burton Howard Bloom提出,它是一個兼具空間效率與時間效率的過濾器,可以用來判斷一個元素是否在過濾器所監測的集合中。網路技術起步之後,布隆過濾器便已深入網路通訊、資料庫管理的領域,被用來避免短時間內收取相同的封包,或者是輔助快取或緩衝記憶體的運作。在2000年之後,布隆過濾器也發展出多種改良版本,不但改進自身缺點,功能性顯著提升,適用的範圍也越來越廣。

摘要 本研究試圖使用布隆過濾器取代無限容量的記憶體,大幅降低記錄全部的解所需的時間與空間。演算法可以選擇更快完成任務,或者是利用布隆過濾器,確保自己找到的解不重覆,進而加強演算法的搜尋效率。在實驗的部分,我們試著改變布隆過濾器的失誤率、雜湊函式數量和雜湊函式本身,並且觀察這對演算法的搜尋效率有什麼影響。實驗的最後,我們證明了一個運作良好的布隆過濾器能夠有效的加快演算法的搜尋。
Contents 2
List of Figures 6
List of Tables 7
1 緒論 13
2 相關研究 15
2.1 演算法的重覆計算與緩存概念 . . . . . . . . . . . . . . 15
2.2 布隆過濾器 . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 計數型布隆過濾器 . . . . . . . . . . . . . . . . . 17
2.2.2 改善誤判 . . . . . . . . . . . . . . . . . . . . . 19
2.2.3 可擴展式布隆過濾器 . . . . . . . . . . . . . . . . . 20
2.2.4 其他改良方式 . . . . . . . . . . . . . . . . . . . 20
3 研究方法
3.1 方法架構 . . . . . . . . . . . . . . . . . . . . . . 22
3.2 研究方法 . . . . . . . . . . . . . . . . . . . . . . 23
3.2.1 解的表示方式 . . . . . . . . . . . . . . . . . . . 23
3.2.2 評估函式 . . . . . . . . . . . . . . . . . . . . . 24
3.2.3 鄰近區域 . . . . . . . . . . . . . . . . . . . . . 25
3.2.4 搜尋鄰居的策略 . . . . . . . . . . . . . . . . . . 25
3.2.5 接受解的方法 . . . . . . . . . . . . . . . . . . . 25
3.3 布隆過濾器 . . . . . . . . . . . . . . . . . . . . . 26
3.3.1 雜湊函式 . . . . . . . . . . . . . . . . . . . . . 27
3.3.2 位元圖 . . . . . . . . . . . . . . . . . . . . . . 31
3.3.3 失誤率 . . . . . . . . . . . . . . . . . . . . . . 32
4 實驗結果 34
4.1 實驗設定 . . . . . . . . . . . . . . . . . . . . . . 34
4.2 選取雜湊函式與布隆過濾器的輔助效果 . . . . . . . . . . 35
4.2.1 選取雜湊函式 . . . . . . . . . . . . . . . . . . . 36
4.2.2 布隆過濾器的輔助效果 . . . . . . . . . . . . . . . 38
4.3 與禁忌搜尋法比較 . . . . . . . . . . . . . . . . . . 42
4.4 探究BF-WOR與BF-WR所需的記憶體大小 . . . . . . . . . . 45
4.5 已快取形式實作布隆過濾器 . . . . . . . . . . . . . . 48
4.6 將BF-WOR實作於禁忌演算法 . . . . . . . . . . . . . . 53
5 結論與未來展望 57
附錄 A 雜湊函式詳細數據: Rastrigin function 59
附錄 B 雜湊函式詳細數據: Rosenbrock function 96
附錄 C 雜湊函式詳細數據: TSP 133
附錄 D 不同記憶體大小下: BF-WOR、BF-WR 164
附錄 E 不同記憶體大小: 快取形式 - Clear 171
[1] P. S. Almeida, C. Baquero, and N. Preguica. Scalable bloom filters. IPL: Information Processing Letters, 101:255–261, 2007.

[2] B. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422–426, July 1970.

[3] F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese. An improved construction for counting bloom filters. In Yossi Azar and Thomas Erlebach, editors, ESA, volume 4168 of Lecture Notes in Computer Science, pages 684–695. Springer, 2006.

[4] B. Chazelle, J. Kilian, R. Rubinfeld, and A. Tal. The bloomier filter: An efficient data structure for static support lookup tables. In SODA: ACM-SIAM Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms), 2004.

[5] C. K. Chow, H. T. Tsui, and T. Lee. Surface registration using a dynamic genetic algorithm. Pattern Recognition, 37(1):105–117, January 2004.

[6] C. K. Chow and S. Y. Yuen. Continuous non-revisiting genetic algorithm with random search space re-partitioning and one-gene-flip mutation. In IEEE Congress on Evolutionary Computation, pages 1–8. IEEE, 2010.

[7] S. Cohen and Y. Matias. Spectral bloom filters. In ACM, editor, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data 2003, San Diego, California, June 09–12, 2003, pages 241–252, pub-ACM:adr, 2003. ACM Press.

[8] L. Fan, P. Cao, J. Almeida, and A. Broder. Summary cache: A scalable widearea Web cache sharing protocol. In Proceedings of the ACM SIGCOMM’98 conference, pages 254–265, September 1998.

[9] K. F. Fong, V. I. Hanby, and T. T. Chow. Hvac system optimization energy management evolutionary programming. Energy and Buildings, 38(3):220–231, 2006.

[10] K.F. Fong, S.Y. Yuen, C.K. Chow, and S.W. Leung. Energy management and design of centralized air-conditioning systems through the non-revisiting strategy for heuristic optimization methods. Applied Energy, 87:3494–3506, Nov 2010.

[11] D. Guo, Y. Liu, X. Y. Li, and P. Yang. False negative problem of counting bloom filter. Knowledge and Data Engineering, 22:651–664, January 2010.

[12] D. Guo, J. Wu, H. Chen, Y. Yuan, and X. Luo. The dynamic bloom filters.
Knowledge and Data Engineering, 22(1):120–133, Jan 2010.

[13] J. Kratica. Improving performances of the genetic algorithm by caching. Computers and Artificial Intelligence, 18(3):271–283, 1999.

[14] L. Li, B. Wang, and J. Lan. A variable length counting bloom filter. In Proceedings of ICCET 2010 2nd International Conference, volume 3, pages 504–508, April 2010.

[15] M. Mitzenmacher. Compressed bloom filters. In PODC, pages 144–150, 2001.

[16] C. W. Mortensen, R. Pagh, and M. Patrascu. On dynamic range reporting in one dimension. In STOC: ACM Symposium on Theory of Computing (STOC), 2005.

[17] C. E. Rothenberg, C. A. B. Macapuna, F. L. Verdi, and M. F. Magalhães. The deletable bloom filter: A new member of the bloom family. CoRR, 14(6):557–559, June 2010. informal publication.

[18] Z. Stanimirovic, J. Kratica, and D. Dugosija. Genetic algorithms for solving the discrete ordered median problem. European Journal of Operational Research, 182(3):983–1001, 2007.

[19] M. Z. Xiao, Y. F. Dai, and X. M. Li. Split bloom filter. Acta Electronica Sinica, 32(2):241–245, 2004.

[20] MyungKeun Yoon. Aging bloom filter with two active buffers for dynamic sets. IEEE Trans. Knowl. Data Eng, 22(1):134–138, 2010.

[21] S. Y. Yuen and C. K. Chow. A non-revisiting genetic algorithm. In IEEE Congress on Evolutionary Computation, pages 4583–4590. IEEE, 2007.

[22] S. Y. Yuen and C. K. Chow. Continuous non-revisiting genetic algorithm. In IEEE Congress on Evolutionary Computation, pages 1896–1903. IEEE, 2009.

[23] S. Y. Yuen and C. K. Chow. A genetic algorithm that adaptively mutates and never revisits. IEEE Trans. Evolutionary Computation, 13(2):454–472, 2009.

[24] S. Y. Yuen and C. K. Chow. A study of operator and parameter choices in nonrevisiting genetic algorithm. In IEEE Congress on Evolutionary Computation, pages 2977–2984. IEEE, 2009.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔