碩士學位**
學科專業名稱：計算機軟體與理論
申請人姓名： 王偉偉
指導教師： 劉希玉教授
**提交時間：2023年 04月19日
本章首先介紹了群體智慧型的研究背景及前沿，其次闡述微粒群演算法的發展現狀，最後介紹了本文的主要工作和組織結構。
人們在很早的時候就對自然界中存在的群集行為感興趣,如大雁在飛行時自動排**字形,蝙蝠在洞穴中快速飛行卻可以互不碰撞等。同時受螞蟻、飛鳥等社會性昆蟲行為的啟發, 單個的個體智慧型並不高, 但依靠群體的能力, 卻發揮出超出個體的智慧型。這種現象揭示了簡單智慧型的主體通過合作可以表現出複雜智慧型行為的特性。
通過對其行為的模擬,產生了一系列解決複雜優化問題的新思路和方法, 用於解決組合優化問題和其它一些實際應用問題的新方法相繼產生。 一些啟發於群居性生物的尋食、打掃巢穴等行為而設計的演算法成功地解決了組合優化、通訊網路和機械人等領域的實際問題，這些研究被稱為對群體智慧型(swarmintelligence) 的研究。對於這些現象的一種解釋是,群體中的每個個體都遵守一定的行為準則,當它們按照這些準則相互作用時就會表現出上述的複雜行為。
作為乙個新興領域，自從20世紀80年代出現以來，引起了多個學科領域研究人員的關注，已經成為人工智慧以及經濟、社會、生物等交叉學科的熱點和前沿領域。基於這一思想,craig reynolds在2023年提出乙個**生物群體行為的模型boid。這是乙個人工鳥系統,其中每只人工鳥被稱為乙個boid,它有三種行為:
分離、列隊及聚集,並且能夠感知周圍一定範圍內其它boid的飛行資訊。boid 根據該資訊,結合其自身當前的飛行狀態,並在那三條簡單行為規則的指導下做出下一步的飛行決策。reynolds 用計算機動畫的形式展現了該系統的行為,每個boid能夠在快相撞時自動分開,遇到障礙物分開後又重新合攏。
這實際上就是一種群體智慧型模型。儘管這一模型出現在1986 年,但是群體智慧型(swarm intelligence) 概念被正式提出的時間並不長。乙個顯著的標誌是1999 年由牛津大學出版社出版的e bonabeau 和m dorigo 等人編寫的一本專著《群體智慧型:
從自然到人工系統》(「swarmintelligence : from natural to artificial system」)，群體智慧型由單個複雜個體完成的任務可由大量簡單的個體組成的群體合作完成，而後者往往更具有健壯性、靈活性和經濟上的優勢。bonabeau, do rigo 等人於1999 年給出群體智慧型的定義:
群體智慧型是指任何受到社會昆蟲群體和其它動物群體的集體行為的啟發而設計的演算法和分布式問題解決裝置，對這些新方法的研究可將其稱之為群體智慧型( swarm intelligence ) 的研究。
目前,對群體智慧型的研究尚處於初級階段,但是它越來越受到國際智慧型計算研究領域學者的關注,逐漸成為乙個新的重要的研究方向，並且已初見成果。2023年，在印第安那州召開的ieee國際會議上，首次發起了對群體智慧型的系列研究。2023年，進行了第二次關於群體智慧型的ieee國際會議，物理學家、工程師、計算機科學家、生物學家、經濟學家、生態學者等在廣義群體智慧型的定義下，展示和討論了他們在各自領域中使用群體智慧型得到的成果，以及群體智慧型在這個新興領域中的發展潛力和趨勢。
群體智慧型的特點是最小智慧型但自治的個體利用個體與個體和個體與環境的互動作用實現完全分布式控制,並具有自組織、可擴充套件性、健壯性等特性。利用群體優勢，在沒有集中控制，不提供全域性模型的前提下，為尋找複雜問題解決方案提供了新的思路。對群體智慧型的定義進行擴充套件，普遍意義上有以下幾種理解。
一是由一組簡單智慧型體(agent)湧現出來的集體的智慧型(collective intelligence)，以蟻群優化演算法(antcolony optimization，aco)和螞蟻聚類演算法等為代表；二是把群體中的成員看作粒子，而不是智慧型體，以粒子群優化演算法(particle swarm optimization，pso)為代表。群體智慧型是對生物群體的一種軟仿生，即有別於傳統的對生物個體結構的仿生。可以將個體看成是非常簡單和單一的，也可以讓它們擁有學習的能力，來解決具體的問題。
現有的對群體智慧型的研究，大都是從某一種由大量個體表現出來的群體行為出發，從它們的群體行為中提取模型，為這些行為建立一些規則，從而提出演算法，應用於解決實際中的問題。
目前,群體智慧型主要有兩種演算法,分別是微粒群優化演算法(particle swarm optimization,簡稱pso)和蟻群演算法(ant colony system,簡稱acs)。
微粒群優化演算法最早是由kennedy和eberhart於2023年提出的,是一種基於種群尋優的啟發式搜尋演算法。它的基本概念源於對鳥群群體行為的研究。在自然界中,儘管每只鳥的行為看起來似乎是簡單和隨機的,但是它們之間卻有著驚人的同步性,使得整個鳥群在空中的形態非常流暢優美。
鳥群具有這樣複雜的行為特徵,可能是因為每只鳥在飛行時都遵循一定的行為準則,並且能夠了解其相鄰區域內其它鳥的飛行資訊，從而調節自身的飛行位置和速度，實現鳥群的整體的和諧。微粒群優化演算法的提出就是借鑑了這樣的思想。在微粒群優化演算法中,每個微粒代表待求解問題的乙個潛在解。
每個微粒都可獲得其鄰域內其它微粒個體的資訊,並可根據該資訊以及簡單的位置和速度更新規則,改變自身的狀態量,以便更好地適應環境。隨著這一過程的反覆進行,微粒群最終能夠找到問題的近似最優解。由於微粒群優化演算法概念簡單, 易於實現,並且具有較好的尋優特性,因此它在短期內得到迅速發展,目前已在許多領域中得到應用,如電力系統優化、tsp問題求解、神經網路訓練、交通事故探測、引數辨識、模型優化等。
蟻群演算法是由m dorigo等人於2023年首先提出的,是受到自然界中螞蟻群的社會性行為啟發產生的,模擬了實際蟻群尋找食物的過程。在自然界中,螞蟻群總是能夠找到從巢穴到食物源之間的一條最短路徑。因為螞蟻在運食過程中,能在其經過的道路上留下一種被稱之為「外激素(pheromone)」的化學氣味。
該氣味能夠被後來的螞蟻感知到,並且會隨時間逐漸揮發。每個螞蟻根據道路上資訊素的強弱來指導自己的運動方向。隨著時間的推移，在某一道路上走過的螞蟻越多,因為重複注入資訊素，積累的資訊素就越多,該道路在下一時間內被其它螞蟻選中的概率就越大。
根據這樣的簡單邏輯規則，螞蟻最終會找到通往食物源的最短路徑。蟻群演算法正是利用了蟻群的這一特性來對問題進行求解。目前,蟻群演算法已在組合優化問題求解,以及電力、通訊、化工、交通、機械人、冶金等多個領域中得到應用,都表現出了令人滿意的效能。
例如多**程式系統，通過增加「外激素」強化好路由，使數字資訊素「蒸發」抑制差路由，從而解決路由選擇問題。
1.1.2關聯規則挖掘的研究背景及現狀
隨著資料庫技術的迅速發展以及資料庫管理系統的廣泛應用,人們積累的資料越來越多,面對海量的儲存資料,如何從中發現有價值的資訊或知識是一項非常艱鉅的任務。資料探勘就是為了滿足這種要求而迅速發展起來的。資料探勘是指從大型資料庫或資料倉儲中提取隱含的、先前未知的、對決策有潛在價值的知識和規則。
資料探勘是人工智慧和資料庫發展相結合的產物，是資料庫和資訊決策系統目前最前沿的研究方向之一，已引起了學術界和工業界的廣泛關注。關聯規則的發現是資料探勘中最成功和最重要的一項任務，它的目標是發現資料集中所有的頻繁模式。資料探勘(data mining)又稱資料庫中的知識發現(knowledge discovery in database , kdd),是乙個從大量資料中挖掘出隱含的、未知的、可理解的、對決策有潛在價值的知識發現過程.
資料探勘出現於20世紀80年代末,最早是在資料庫領域發展起來的,稱為資料庫中的知識發現(kdd，knowledge discovery in database),kdd一詞首先出現在2023年人工智慧國際會議上,以後這一研究逐漸成為熱點,kdd研究的內容是,能自動處理資料庫中大量的原始資料,從中挖掘出潛在的可能關係模式以發現新的知識為目標,隨著研究物件的擴充套件,人們開始稱之為資料探勘, 2023年，在加拿大蒙特婁召開了第一屆國際知識發現和資料探勘學術會議，之後每年召開一次，至2023年已經召開了9次。當今，知識發現和資料庫挖掘已經成為乙個活躍的it領域。我國從事資料探勘的研究起步較晚,大約在90年代中期開始,國內許多高校和科研院所在這一領域內開展研究,並取得了許多成就。
目前資料探勘技術已能夠立即投入使用,這是因為作為支撐的三個基礎技術已日趨完善。具體表現為:(1)資料庫現在正在以乙個空前的速度增長,並且資料庫正在廣泛地應用於各行各業,解決了海量資料收集。
(2)現在已經成熟的並行多處理機的技術形成了強大的多處理器計算機。對資料能做到快速訪問。(3)資料探勘演算法經過了最近10多年發展逐漸形成了一種成熟、穩定且易於理解和操作的應用技術。
在事物資料庫中挖掘關聯規則,關聯規則(association rules)的挖掘是研究的乙個重要方向也是資料探勘領域中的乙個非常重要的研究課題,它是由r.agrawal等人首先提出的。目前已有許多研究成果,最經典的挖掘關聯規則的演算法是apriori。
在資料探勘的研究領域, ,它由美國ibmalmaden research center的r.akeshagrawal等人於2023年首先提出,是描述資料庫中資料項之間存在的一些潛在關係的規則.典型的關聯規則演算法有r.
agrawal等人提出的apriori演算法和dhp演算法,它們屬於資料庫遍歷類演算法. r.agrawal提出的apriori-hybrid演算法,park等人提出的dhp演算法(direct hashing and pruning)使用的是hashing技術,這種演算法有效地改進了候選集的產生過程.
r,srikant和r.agrawal基於分類結構(is-a層次關係),提出了挖掘廣義關聯規則的問題,它用在高層抽象概念層上挖掘關聯規則不僅有助於獲得大的支援度、表達普遍的資料關係,而且能減少無興趣或冗餘的規則.h.
toiconen提出的抽樣(samping)方法,用較小的代價從大型資料庫中找出關聯規則.上述種種演算法的提出,均不同程度地改進了關聯規則發現的過程. 先前的研究表明隨著資料庫專案的增多,尤其是當降低支援度和可信度時, apriori演算法所生成的關聯規則的數目會以最大頻繁項集長度的指數增長,其中包含了大量的冗餘規則,不利於企業進行決策,同時也影響了演算法的效率。
關聯規則挖掘中有關apriori演算法的討論
r.agrawal 等在2023年設計了一種基於寬度優先演算法，通過對資料庫d的多趟掃瞄來發現所有的頻繁專案集。在每一趟掃瞄中只考慮具有同一長度k（即專案集中所含專案的個數）的所有k項集。
apriori演算法提出了挖掘關聯規則的乙個重要方法，是乙個基於兩階段頻集思想的方法，將關聯規則挖掘的設計分解為兩個子問題：
（1）找到所有支援度大於最小支援度的項集。這些項集稱為頻集。
（2）使用第1步找到的頻集產生期望的規則。
在關聯規則挖掘頻繁項集的諸多演算法中，apriori演算法是乙個最基本的，近年來，研究人員不斷努力對這一演算法進行改進，提出了基於雜湊表、劃分資料、取樣、動態資料等技術的改進演算法，還有人利用樹、堆疊和圖等資料結構來提高資料探勘得效率。
很多文獻針對演算法在執行中存在的上述搜尋空間問題提出了改進，例如在每一次生成lk的同時按照一定的規則縮減資料集的規模，從而大大減少了資料集的個數，有效地提高了演算法效率。或者利用hash表來存放事務資料。:對給定資料庫的事務和項資料用若干hash表來記錄,每個項構造乙個hash表,而hash表中的元素為各事務在該項中出現的事務編號,然後通過掃瞄各hash表,實現挖掘頻繁項集的目的。
如果對於長度大於k的候選專案集，可以採用雜湊技術，。借助於鄰接矩陣研究頻繁集的計數,在減少資料庫的掃瞄次數方面也有很大改進。
1. 關聯規則挖掘演算法自提出以來已經取得了一定的研究成果，但由於其研究才剛剛開始，研究領域也不全面，因此從群體智慧型理論出發，多層次多角度研究關聯規則挖掘演算法尤為必要。
2. 由頻繁k-1項集進行自連線生成候選頻繁k項集數量巨大，特別是在初期的候選集非常龐大，而在後期候選集將會急劇縮小，尤其在生成二維候選集時問題比較突出，因此需要縮小二維候選集的規模很具有研究意義；
基於關聯規則挖掘的高校成績分析研究
摘要 本文通過對本校某年級學生成績進行分析，主要應用資料探勘中的關聯規則和apriori演算法，挖掘出一些合理的課程關聯規則，將這些規則運用到教學管理中，可以指導學生選課和合理的設定課程，為高校的教學管理提供參考。關鍵詞 資料探勘 關聯規則 成績管理 中圖分類號 tp311.13 努力提高學生的成績...
基於關聯規則的教學質量評價
福建電腦 年第 期 桑莉君 蘭方鵬 太原理工大學輕紡工程與美術學院山西晉中 摘要 利用關聯規則的 演算法對我院藝術專業教師基本資料和歷年教學檢查資料進行資料 挖掘和分析，發掘出影響教學質量的關鍵因素，為我院教師隊伍建設和優秀人才的引進提供科學 可靠的 指導。關鍵詞 教學評價 資料探勘 關聯規則 演算...
基於關聯規則模型的商品分類問題研究
作者 伏蘭蘭黃秋萍盧葉園廖靜甘宇健 軟體導刊 2017年第11期 摘要 關聯規則是資料探勘的重要方法之一，apriori是傳統關聯規則中的經典演算法。提出基於大量商品 的資料集，分別建立單維和二維商品 關聯規則模型，挖掘單維和二維商品 的強關聯規則。通過對比分析單維和二維商品 強關聯規則，以發現同類...