基于混合進化算法的子結(jié)構(gòu)發(fā)現(xiàn)研究.pdf

1、關(guān)系無處不在。近年來，學習數(shù)據(jù)中各種關(guān)系的結(jié)構(gòu)數(shù)據(jù)挖掘得到了廣泛的關(guān)注并成為了數(shù)據(jù)挖掘與機器學習領(lǐng)域的一個重要分支。結(jié)構(gòu)數(shù)據(jù)含有更為豐富的信息，更能反映問題的本質(zhì)，同時也會導致更大、更復雜的假設(shè)空間，從而向數(shù)據(jù)挖掘與機器學習領(lǐng)域提出了新的挑戰(zhàn)。本文將在眾多的復雜問題求解過程中表現(xiàn)突出的進化算法引入到結(jié)構(gòu)數(shù)據(jù)挖掘的子結(jié)構(gòu)發(fā)現(xiàn)之中，取得了較同類算法更好的實驗結(jié)果。本文的主要工作包括如下內(nèi)容： 1、依據(jù)混合進化算法理論提出了混合進化子

2、結(jié)構(gòu)發(fā)現(xiàn)算法HEASD。在HEASD中，給出了基于圖的染色體表示和遺傳算子，并將爬山算法的思想融于交叉和變異算子的設(shè)計之中，實驗結(jié)果表明了該算法的有效性。同時我們還提出了一種新的子結(jié)構(gòu)擴展方法--單標簽擴展，并對其正確性和有效性進行了理論證明和實驗驗證。 2、子圖同構(gòu)問題是圖數(shù)據(jù)挖掘的瓶頸問題，是造成問題復雜的根源所在。其表現(xiàn)之一就是它造成了進化的單向性，從而導致了查找的不完全性。為此我們提出了基于帶回溯個體的混合進化子結(jié)構(gòu)發(fā)現(xiàn)

3、算法HEASDBT，將回溯機制融入到了進化過程之中，可以對假設(shè)空間中的某些關(guān)鍵區(qū)域進行密集搜索，實驗結(jié)果表明了該算法的有效性。 3、實例丟失現(xiàn)象是結(jié)構(gòu)數(shù)據(jù)挖掘中廣泛存在的造成解質(zhì)量降低的一個重要原因。為此我們提出了兩個算法HEASDFI和HEASDCI，前者采取“預防”的策略，盡量避免實例的丟失；后者則采取“治療”的辦法，重新找回丟失的實例。實驗結(jié)果表明了以上兩種算法的有效性。在HEASDCI中，我們還提出了一個新的遺傳算子一個

4、體協(xié)同算子，使多個代表同一子結(jié)構(gòu)的不同個體可以對同一目標進行協(xié)同查找，以提高解的質(zhì)量。由于個體協(xié)同算子需要進行頻繁的圖同構(gòu)操作，而圖同構(gòu)操作雖然不像子圖同構(gòu)那樣已被證明是NP完全問題，但目前還沒有多項式級的算法存在，為此本文提出了一個時間復雜度為多項式級的近似圖同構(gòu)算法以提高個體協(xié)同算子的執(zhí)行效率。 4、將本文提出的算法應(yīng)用于學科建設(shè)和區(qū)域經(jīng)濟研究。前者將各院校信息與計算科學學科的培養(yǎng)目標、課程設(shè)置等信息組織成為圖數(shù)據(jù)，然后用本