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

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

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

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