基于屬性論的0-1背包問題算法研究.pdf

1、背包問題是一個在運籌學領域里常見的典型NP-C難題。工廠里的下料問題，管理中的資源分配，資金預算，投資決策，裝載問題等均可建模為背包問題。對該問題的求解方法的研究無論是在理論上，還是在實踐中都具有重要意義。對于背包問題，己有的求解方法可分為精確算法(如動態(tài)規(guī)劃，分支定界等)和近似算法(如貪婪法，螞蟻算法，遺傳算法等)兩大類。因為精確算法的時間復雜性都是呈指數(shù)增長的，所以從六十年代逐漸提出了一些近似算法。 屬性論方法是馮嘉禮教授提

2、出的人工智能領域的一種新的理論。目前在組合優(yōu)化問題、模式識別、非線性分類、質(zhì)量評估模型、股票預測以及網(wǎng)絡攻擊探測等領域都已經(jīng)得到廣泛的應用。 在閱讀了大量中外文獻的基礎上，本文提出了背包問題的一種基于屬性論的啟發(fā)式算法。文章在開篇綜述背包問題的一些基本情況后，接著介紹了屬性論的一些基本觀點、方法和理論，包括定性映射模型，人工神經(jīng)元模型與定性映射模型的關系，量質(zhì)轉(zhuǎn)換程度函數(shù)等等。隨后結(jié)合貪婪算法和背包核問題的思想，我們給出了物件基

3、于核的一個定性映射。在根據(jù)背包的核問題的具體情況對屬性論中傳統(tǒng)的Gauss型轉(zhuǎn)換程度作了必要的改進之后，我們給出了背包問題基于屬性論的一個近似轉(zhuǎn)化優(yōu)化算法并且根據(jù)此算法用Java語言設計了背包問題軟件包。軟件包的設計充分結(jié)合了Java語言的特點，具有高性能和高的可擴展性，提供了可擴展的接口以方便其他應用程序擴展和調(diào)用。 作為軟件包開發(fā)的一部分，我們結(jié)合背包問題實例的四種類型，設計了測試實例生成器及背包問題優(yōu)化程序。本文在文章的后