- 相關(guān)推薦
開題報告文獻(xiàn)綜述 北理工
不會寫開題報告、文獻(xiàn)綜述,論文的過來看!下面是小編整理的開題報告文獻(xiàn)綜述 北理工范文。
【一】北京理工大學(xué)碩士學(xué)位論文開題文獻(xiàn)綜述報告
學(xué)位論文題目為《基于聚類分析的啟發(fā)式優(yōu)化算法》 ，論文內(nèi)容涉及了優(yōu)化算法(主要是經(jīng)典優(yōu)化算法，啟發(fā)式優(yōu)化算法) ，算復(fù)雜性理論和聚類分析等相關(guān)領(lǐng)域。
根據(jù)這些領(lǐng)域與論文的相關(guān)程度，比較詳細(xì)的歸納總結(jié)啟發(fā)式優(yōu)化算法，對計算復(fù)雜性理論和聚類分析只做了一般性的總結(jié)。
最后對這些相關(guān)領(lǐng)域未來的發(fā)展和研究提出自己的觀點。
在現(xiàn)實生活中許多重要的問題，都涉及到選區(qū)一個最好的目標(biāo)，或者為達(dá)到這個目標(biāo)而選擇某些參數(shù)、確定某些值，這些問題都可以歸結(jié)為最優(yōu)化問題。
對于一個最小值問題，其形式的描述為 min ( )f XXS∈(1) 這里的 S 為解的可行域，也稱為解空間或搜索空間，條件 XS∈概括了對向量 X 的約束。
這些約束可以包括線性或非線性函數(shù)， 以及離散變量， 都可以根據(jù)實際要求設(shè)置。
最優(yōu)化問題的目標(biāo)是找到(1)的最優(yōu)解(全局最優(yōu)解或局部最優(yōu)解) 。
顯然，只要改變目標(biāo)函數(shù)的符號，最大值問題就可以轉(zhuǎn)變成最小值問題，因此，本文在說明都是以最小值問題問標(biāo)準(zhǔn)。
解決最優(yōu)化問題的算法稱為最優(yōu)化算法，可以分為經(jīng)典優(yōu)化算法和啟發(fā)式優(yōu)化算法。
而經(jīng)典優(yōu)化算法又分為線形與非線性最優(yōu)化算法，下面分別對兩類算法的發(fā)展及常用的軟件包做了介紹。
1. 線性最優(yōu)化[1][10]： 線性最優(yōu)化, 又稱線性規(guī)劃, 是運籌學(xué)中應(yīng)用最廣泛的一個分支.這是因為自然科學(xué)和社會科學(xué)中許多問題都可以近似地化成線性規(guī)劃問題. 線性規(guī)劃理論和算法的研究及發(fā)展共經(jīng)歷了三個高潮, 每個高潮都引起了社會的極大關(guān)注.
線性規(guī)劃研究的第一高潮是著名的單純形法的研究.
這一方法是 Dantzig 在 1947 年提出的,它以-15- -15- 成熟的算法理論和完善的算法及軟件統(tǒng)治線性規(guī)劃達(dá)三十多年. 隨著 60 年代發(fā)展起來的計算復(fù)雜性理論的研究, 單純形法在七十年代末受到了挑戰(zhàn).
前蘇聯(lián)數(shù)學(xué)家 Khachiyan 提出了第一個理論上優(yōu)于單純形法的所謂多項式時間算法--橢球法, 曾成為轟動一時的新聞, 并掀起了研究線性規(guī)劃的第二個高潮.
但遺憾的是廣泛的數(shù)值試驗表明, 橢球算法的計算比單純形方法差. 1984 年 Karmarkar 提出了求解線性規(guī)劃的另一個多項式時間算法.
這個算法從理論和數(shù)值上都優(yōu)于橢球法, 因而引起學(xué)術(shù)界的極大關(guān)注, 并由此掀起了研究線性規(guī)劃的第三個高潮. 從那以后, 許多學(xué)者致力于改進(jìn)和完善這一算法,得到了許多改進(jìn)算法.這些算法運用不同的思想方法均獲得通過可行區(qū)域內(nèi)部的迭代點列, 因此統(tǒng)稱為解線性規(guī)劃問題的內(nèi)點算法.
目前內(nèi)點算法正以不可抗拒的趨勢將超越和替代單純形法. 在互聯(lián)網(wǎng)上能訪問到的解線性和整數(shù)規(guī)劃問題的軟件還有:EQPS(線性，整數(shù)和非線性規(guī)劃),FMP(線性和混合整數(shù)規(guī)劃) ，HS/LPLO(線性規(guī)劃) ，KORBX(線性規(guī)劃) ，LAMPS(線性和整數(shù)規(guī)劃) ，LPBLP(線性規(guī)劃) ，
MILP(混合整數(shù)規(guī)劃) ，MINTO(混合整數(shù)規(guī)劃) ， MPSIII(線性和混合整數(shù)規(guī)劃) ，OML(線性和混合整數(shù)規(guī)劃) ， OSL(線性，二次和混合整數(shù)規(guī)劃) ，PROCLP(線性和整數(shù)規(guī)劃) ，WB(線性和混合整數(shù)規(guī)劃) ，WHIZARD(線性和混合整數(shù)規(guī)劃) ，XPRESSMP(線性和混合整數(shù)規(guī)劃)等[41]。
2.非線性最優(yōu)化[1][2][3][10]： 非線性規(guī)劃的一個重要理論是 1951 年 Kuhn-Tucker 最優(yōu)條件(簡稱 KT 條件)的建立[2].此后的 50 年代主要是對梯度法和牛頓法的研究.以 Davidon(1959), Fletcher 和 Powell(1963)提出的 DFP 方法為起點, 60 年代是研究擬牛頓方法活躍時期, 同時對共軛梯度法也有較好的研究.
在 1970 年由 Broyden,Fletcher,Goldfarb 和 Shanno 從不同的角度共同提出的 BFGS 方法是目前為止最有效的擬牛頓方法.
由于Broyden, Dennis 和 More 的工作使得擬牛頓方法的理論變得很完善. 70 年代是非線性規(guī)劃飛速發(fā)展時期, 約束變尺度(SQP)方法(Han和Powell為代表)和Lagrange乘子法(代表人物是 Powell 和 Hestenes)是這一時期主要研究成果.計算機(jī)的飛速發(fā)展使 -15- 非線性規(guī)劃的研究如虎添翼.
80 年代開始研究信賴域法、稀疏 擬牛頓法、大規(guī)模問題的方法和并行計算, 90 年代研究解非線性規(guī)劃問題的內(nèi)點法和有限儲存法.
可以毫不夸張的說, 這半個世紀(jì)是最優(yōu)化發(fā)展的黃金時期. 與線性規(guī)劃相比，非線性規(guī)劃軟件還不夠完善. 但是已有大量解非線性規(guī)劃問題的軟件, 其中有相當(dāng)一部分可從互聯(lián)網(wǎng)上免費下載.LANCELOT 是由 Conn,Gould 和Toint 研制的解大規(guī)模最優(yōu)化問題的軟件包,適合解無約束最優(yōu)化、非線性最小二乘、邊界約束最優(yōu)化和一般約束最優(yōu)化問題.
這個軟件的基本思想是利用增廣Lagrange函數(shù)來處理約束條件, 在每步迭代中解一個邊界約束優(yōu)化子問題, 其所用的方法結(jié)合信賴域和投影梯度等技術(shù).MINPACK 是美國 Argonne 國家實驗室研制的軟件包， 適合求解非線性方程組和非線性最小二乘問題, 所用的基本方法是阻尼最小二乘法,
此軟件可以從網(wǎng)上圖書館獲得. PROC NLP 是 SAS 軟件公司研制的 SAS 商業(yè)軟件中 OR 模塊的一個程序，這個程序適合解無約束最優(yōu)化、非線性最小二乘、線性約束最優(yōu)化、二次規(guī)劃和一般約束最優(yōu)化問題.TENMIN 是 Schnabel 等研制的解中小規(guī)模問題的張量方法軟件。
在互聯(lián)網(wǎng)上能訪問到的解非線性最優(yōu)化問題的軟件還有:CONOPT(非線性規(guī)劃) ，DOT(優(yōu)化設(shè)計工具箱) ，Excel and Quattro Pro Solvers(線性，整數(shù)和非線性規(guī)劃) ，F(xiàn)SQP(非線性規(guī)劃和極小極大問題) ，GRG2(非線性規(guī)劃)， LBFGS(有限儲存法) ，
LINDO(線性、二次和混合整數(shù)規(guī)劃) ，LSSOL(最小二乘和二次規(guī)劃) ，MINOS(線性和非線性規(guī)劃) ，NLPJOB(非線性多目標(biāo)規(guī)劃) ， OPTPACK(約束和無約束最優(yōu)化),PETS(解非線性方程組和無約束問題的并行算法) ，
QPOPT(線性和二次規(guī)劃) ,SQOPT (大規(guī)模線性和凸二次規(guī)劃) ， SNOPT (大規(guī)模線性、 二次和非線性規(guī)劃) ，SPRNLP (稀疏最小二乘,稀疏和稠密非線性規(guī)劃) ， SYSFIT (非線性方程組的參數(shù)估計) ，TENSOLVE (非線性方程組和最小二乘) ， VE10(非線性最小二乘)等[38][39][40][41].
大自然是神奇的，它造就了很多巧妙的手段和運行機(jī)制。
受大自然的啟發(fā)，人們從大自然的運行規(guī)律中找到了許多解決實際問題的方法。
對于那些受大自然的運行規(guī)律或者面向具體問題的經(jīng)驗、規(guī)則啟發(fā)出來的方法，人們常常稱之為啟發(fā)式算法 -15- (Heuristic Algorithm) 。
現(xiàn)在的啟發(fā)式算法也不是全部來自然的規(guī)律，也有來自人類積累的工作經(jīng)驗。
啟發(fā)式算法有不同的定義：一種定義為，一個基于直觀或經(jīng)驗的構(gòu)造的算法，對優(yōu)化問題的實例能給出可接受的計算成本(計算時間、占用空間等)內(nèi)，給出一個近似最優(yōu)解，該近似解于真實最優(yōu)解的偏離程度不一定可以事先預(yù)計;
另一種是，啟發(fā)式算法是一種技術(shù)，這種技術(shù)使得在可接受的計算成本內(nèi)去搜尋最好的解，但不一定能保證所得的可行解和最優(yōu)解，甚至在多數(shù)情況下，無法闡述所得解同最優(yōu)解的近似程度[11]。
我比較贊同第二種定義，因為啟發(fā)式算法現(xiàn)在還沒有完備的理論體系，只能視作一種技術(shù)。
啟發(fā)式算法的計算量都比較大，所以啟發(fā)式算法伴隨著計算機(jī)技術(shù)的發(fā)展，取得了巨大的成就[11][23]。
40 年代：由于實際需要，人們已經(jīng)提出了一些解決實際問題快速有效的啟發(fā)式算法。
50 年代：啟發(fā)式算法的研究逐步繁榮起來。
隨后，人們將啟發(fā)式算法的思想和人工智能領(lǐng)域中的各種有關(guān)問題的求解的收縮方法相結(jié)合，提出了許多啟發(fā)式的搜索算法。
其中貪婪算法和局部搜索等到人們的關(guān)注。
60 年代: 隨著人們對數(shù)學(xué)模型和優(yōu)化算法的研究越來越重視，發(fā)現(xiàn)以前提出的啟發(fā)式算法速度很快，但是解得質(zhì)量不能保證。
雖然對優(yōu)化算法的研究取得了很大的進(jìn)展，但是較大規(guī)模的問題仍然無能為力(計算量還是太大) 。
70 年代：計算復(fù)雜性理論的提出。
NP 完全理論告訴我們，許多實際問題不可能在合理的時間范圍內(nèi)找到全局最優(yōu)解。
發(fā)現(xiàn)貪婪算法和局部搜索算法速度快，但解不好的原因主要是他們只是在局部的區(qū)域內(nèi)找解，得到的解不能保證全局最優(yōu)性。
由此必須引入新的搜索機(jī)制和策略， 才能有效地解決這些困難問題，這就導(dǎo)致了超啟發(fā)式算法(meta-heuristic algorithms)的產(chǎn)生。
Holland 模擬地球上生物進(jìn)化規(guī)律提出了遺傳算法(Genetic Algorithm) ，它的與眾不同的搜索機(jī)制引起了人們再次引發(fā)了人們研究啟發(fā)式算法的興趣，從而掀起了研究啟發(fā)式算法的熱潮。
-15- 80 年代以后： 模擬退火算法 (Simulated Annealing Algorithm) ， 人工神經(jīng)網(wǎng)絡(luò) (Artificial Neural Network) ，禁忌搜索(Tabu Search)相繼出現(xiàn)。
最近，演化算法(Evolutionary Algorithm), 蟻群算法(Ant Algorithms) ， 擬人擬物算法，量子算法等油相繼興起，掀起了研究啟發(fā)式算法的高潮。
由于這些算法簡單和有效，而且具有某種智能，因而成為科學(xué)計算和人類之間的橋梁。
優(yōu)勝劣汰是大自然的普遍規(guī)律，它主要通過選擇和變異來實現(xiàn)。
選擇是優(yōu)化的基本思想，變異(多樣化)是隨機(jī)搜索或非確定搜索的基本思想。
“優(yōu)勝劣汰”是算法搜索的核心，根據(jù)“優(yōu)勝劣汰”策略的不同，可以獲得不同的超啟發(fā)式算法。
超啟發(fā)式算法的主要思想來自于人類經(jīng)過長期對物理、生物、社會的自然現(xiàn)象仔細(xì)的觀察和實踐，以及對這些自然現(xiàn)象的深刻理解，逐步向大自然學(xué)習(xí)，模仿其中的自然現(xiàn)象的運行機(jī)制而得到的。
遺傳算法：是根據(jù)生物演化，模擬演化過程中基因染色體的選擇、交叉和變異得到的算法。
在進(jìn)化過程中，較好的個體有較大的生存幾率[5]。
模擬退火：是模擬統(tǒng)計物理中固體物質(zhì)的結(jié)晶過程。
在退火的過程中，如果搜索到好的解接受;否則，以一定的概率接受不好的解(即實現(xiàn)多樣化或變異的思想) ，達(dá)到跳出局部最優(yōu)解得目的[10]。
神經(jīng)網(wǎng)絡(luò)：模擬大腦神經(jīng)處理的過程，通過各個神經(jīng)元的競爭和協(xié)作，實現(xiàn)選擇和變異的過程[22]。
禁忌搜索： 模擬人的經(jīng)驗， 通過禁忌表記憶最近搜索過程中的歷史信息， 禁忌某些解，以避免走回頭路，達(dá)到跳出局部最優(yōu)解的目的[32]。
螞蟻算法：模擬螞蟻的行為，擬人擬物，向螞蟻的協(xié)作方式學(xué)習(xí)。
這幾種超啟發(fā)式算法都有一個共同的特點：從隨機(jī)的可行初始解出發(fā)，才用迭代改進(jìn)的策略，去逼近問題的最優(yōu)解[23]。
他們的基本要素： (1)隨機(jī)初始可行解; (2)給定一個評價函數(shù)(常常與目標(biāo)函數(shù)值有關(guān)) ; -15- (3)鄰域，產(chǎn)生新的可行解; (4)選擇和接受解得準(zhǔn)則; (5)終止準(zhǔn)則。
其中(4)集中反映了超啟發(fā)式算法的克服局部最優(yōu)的能力。
雖然人們研究對啟發(fā)式算法的研究將近50年，但它還有很多不足[5][23]： 1.啟發(fā)式算法目前缺乏統(tǒng)一、完整的理論體系。
2.由于 NP 理論，各種啟發(fā)式算法都不可避免的遭遇到局部最優(yōu)的問題，如何判斷 3.各種啟發(fā)式算法都有個自優(yōu)點如何，完美結(jié)合。
4.啟發(fā)式算法中的參數(shù)對算法的效果起著至關(guān)重要的作用，如何有效設(shè)置參數(shù)。
5.啟發(fā)算法缺乏有效的迭代停止條件。
6.啟發(fā)式算法收斂速度的研究等。
由于各種算法對同一個問題都有可能給出最優(yōu)解，為了判定各種算法的效率，人們給出了算法復(fù)雜性的度量。
計算復(fù)雜性理論是研究算法有效性和問題難度的一種工具。
它是最優(yōu)化問題的基礎(chǔ)，涉及如何判斷一個問題的難易程度。
只有了解了所研究問題的復(fù)雜性，才能更有針對性地設(shè)計有關(guān)算法，提高算法效率。
所謂 P 問題，就是可以被關(guān)于問題本身的參數(shù)，如維數(shù)，約束個數(shù)等的多項式時間內(nèi)求解的問題。
幾個多項式和指數(shù)的時間復(fù)雜性函數(shù)的對比[9] 規(guī)模 n 時間復(fù)雜性 函 數(shù) 10 20 30 40 50 60 N 20.00001s 0.00002s 0.00003s 0.00004s 0.00005s 0.00006s N0.0001s 0.0004s 0.0009s 0.0016s 0.0025s 0.0036s N30.001s 0.008s 0.027s 0.064s 0.125s 0.216s N50.1s 3.2s 24.3s 1.7m 5.2m 13.0m 2n0.001s 1.0s 17.9m 12.7d 35.7y 366c 3n0.059s 58m 6.5y 3855c 2x108c 1.3x1013c 圖(1) (S:秒 M:分 D:天 Y:年 C:世紀(jì)) NP 問題就是對于一個給定的點， 能多項式時間內(nèi)判定它是否給定問題的解的問題 -15- [9][14]。
NP 包含 P 是以顯然的事實。
但是 P 是否也包含 NP，就是一個非常困難的問題。
目前這個問題被列為全世界 7 大數(shù)學(xué)難題之首。
有一類 NP 問題，它們之間相互等價，求解其中一個問題就求解了全部問題。
大部分組合組優(yōu)化問題屬于此類。
這類問題稱為 NP 完全問題類。
單個問題就稱為 NP 完全問題。
一般相信，這類問題不存在多項式時間算法。
全局最優(yōu)化的問題很早就有很提出來個,Markowzi&Manne(1957)和Dantzig(1958)討論了線性混合整數(shù)規(guī)劃問題的全局最優(yōu)解.(線性優(yōu)化問題沒有全局最優(yōu)和局部最優(yōu)的區(qū)別,因為線性規(guī)劃是凸規(guī)劃,它的可行域上的局部最優(yōu)就是全局最優(yōu)).之后又有LAND&DOIG等研究了全局最優(yōu)化.
全局最優(yōu)化成為數(shù)學(xué)規(guī)劃的一個分支的時間是<>(dixon&Szego 1975).為了解決這個問題,大量的學(xué)者開始研究它,并提出了很多理論和算法,但是人們發(fā)現(xiàn)似乎是沒有好的算法能有效的解決全局最優(yōu)化問題.
起初人們用經(jīng)典算法(如最速下降法,牛頓法,SQP 等)進(jìn)行多初試點的計算不能有效地解決,在那時(1970年代)計算復(fù)雜理論創(chuàng)立了. 自從Cook1972年提出NP理論，衡量計算復(fù)雜性就有了標(biāo)準(zhǔn)。
已經(jīng)證明了全局最優(yōu)化問題是 NP 問題[11].經(jīng)典算法對它效果不是很好，隨后有的人開始根據(jù)全局優(yōu)化問題的特點對經(jīng)典算法進(jìn)行改進(jìn)，有的則引入了啟發(fā)式算法(如遺傳算法，神經(jīng)網(wǎng)絡(luò)，模擬退活)[35][36]。
大都采用隨機(jī)搜索的策略[25][26]。
似乎完美的東西是不存在的，如果得到精確的解，計算時間總是難以承受的.計算時間和結(jié)果的質(zhì)量是不能同時提高的，如果想提高計算結(jié)果的質(zhì)量就要多花時間，如果想要快速計算計算的結(jié)果就無法保證。
聚類分析是一種重要的人類行為。
早在文明歷史前，一個人就能通過不斷地改進(jìn)下意識中的 聚類模式來學(xué)會如何區(qū)分動植物。
聚類分析已經(jīng)廣泛地用在許多應(yīng)用中，包括模式識別，數(shù)據(jù)分析，圖像處理，以及市場研究。
通過聚類，人能夠識別密集的 -15- 和稀疏的區(qū)域，因而發(fā)現(xiàn)全局的分布模式，以及數(shù)據(jù)屬性之間的有趣相互關(guān)系。
聚類(clustering)就是將數(shù)據(jù)對象分組成為多個類或簇(cluster) ，在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大[17]。
相異度是根據(jù)描述對象的屬性值來計算的。
距離是經(jīng)常采用的度量方式。
常用的距離和相似度有明考斯基距離(Minkowski distance) 、歐氏距離(Euclidean distance) 、絕對值距離(City-block distance) 、切比雪夫距離(Sup distance ) 、 馬 氏 距 離 ( Mahalanobis distance ) 、 帕 松 相 關(guān) 系 數(shù) ( Pearson correlation) 、夾角余旋(Cosine similarity)等[15][18][20]。
距離和相關(guān)系數(shù)的選取對整個聚類過程起著至關(guān)重要的作用，當(dāng)然也可以根據(jù)具體問題，定義具體的距離和相關(guān)系數(shù)的計算方法。
聚類分析的方法可分為：劃分的方法(partitioning method) 、層次方法(hierarchical method) 、基于密度的方法(density-based method) 、基于網(wǎng)格的方法 (grid-based method) 、 和基于模型的方法 (model-based method) [17][19][37]。
1.劃分的方法(partitioning method) 給定一個對 n 個對象或元素的數(shù)據(jù)，一個劃分方法構(gòu)建數(shù)據(jù)的 k 個劃分，每個劃分表示一個聚簇，并且 n>k。
它將數(shù)據(jù)劃分為 k 個組，同時滿足 a.每組至少包含一個對象;b.每個對象必須屬于且只屬于一個組(模糊聚類除外) 。
思想：給定要構(gòu)建的劃分?jǐn)?shù)目 k，劃分方法首先創(chuàng)建一個初始劃分。
然后采用一種迭代的重定位技術(shù)，嘗試通過對象在劃分間移動來改進(jìn)劃分。
具 體 方 法 ： k-means, k-median, EM(Expectation Maximization), CLARA(Clustering LAge Applications)等[17][20]。
2.層次方法(hierarchical method) 層次的方法對給定數(shù)據(jù)對象集合進(jìn)行層次的分解，根據(jù)層次的方法可以分為凝聚的和分裂的。
凝聚的方法，一開始將每個對象作為單獨得一組，然后相繼地和合并相近的對象或組，直到所有的組合并稱為一類。
具體方法：系統(tǒng)聚類法[15]，CURE(Clustering Using Representatives)，變色 -15- 龍(Chameleon)等[17]. 3.基于密度的方法(density-based method) 大部分劃分方法基于對象之間的距離進(jìn)行聚類，這樣的方法只能發(fā)現(xiàn)球狀的簇，而不能發(fā)現(xiàn)任意形狀的簇。
隨之提出了基于密度的聚類方法，其主要思想是，只要鄰近區(qū)域的密度(對象或數(shù)據(jù)點的數(shù)目)超過某個閥值就繼續(xù)距類。
或者說只要兩點之間是密度可達(dá)的就把這兩點歸為一類。
(密度可達(dá)： 給定一個對象集合 D，如果 p 是在 q 的 e 鄰域內(nèi)，q 屬于 D，則稱 p 和 q 是密度可達(dá)的[17]) 。
具體方法：DBSCAN(Density-Based Spatial Clustering of Applications with Noise),OPTICS(Ordering Points to Identify the Clustering Structure), DENCLUE (DENsity-based CLUstERing)等[17][20]。
4.基于網(wǎng)格的方法(grid-based method) 基于網(wǎng)格的方法把對象空間量化為有限數(shù)目的單元，形成了一個網(wǎng)格的結(jié)構(gòu)。
所有的聚類操作都在這個網(wǎng)格結(jié)構(gòu)上進(jìn)行。
這種方法的主要有點就是他的處理速度很快，其處理時間獨立于數(shù)據(jù)對象的數(shù)目，只與量化空間中的每一維的單元數(shù)目有關(guān)。
也就是說， 網(wǎng)格劃分的越細(xì)計算量越大， 網(wǎng)格劃分的越粗聚類的誤差越大。
具 體 方 法 ： STING ( Statistical Information Grid )， WaveCluster, CLIQUE(Clustering In QUEst)等[17]。
5.基于模型的方法(model-based method) 基于模型的方法為每個簇假定了一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合。
一個基于模型的算法可能通過構(gòu)建反映數(shù)據(jù)點空間分布的密度函數(shù)來定位聚類。
具體方法:基于模型的方法主要有兩種，統(tǒng)計學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法[17]。
現(xiàn)在有的許多聚類算法對中小規(guī)模(200 個數(shù)據(jù)以下)的數(shù)據(jù)集合效果比較好，但是一個數(shù)據(jù)集合可能包含幾百萬個數(shù)據(jù)對象，在對這樣的大數(shù)據(jù)集合上進(jìn)行距類可能會導(dǎo)致偏差的結(jié)果， 或者計算復(fù)雜性太高， 以致無法在接受的時間內(nèi)等到聚類結(jié)果。
所以現(xiàn)在，研究工作都集中在為大型數(shù)據(jù)集合的有效和實際聚類分析尋找適當(dāng)?shù)姆?-15- 法。
活躍的研究主題集中在聚類方法的可伸縮性，方法對聚類復(fù)雜形狀和類型的數(shù)據(jù)的有效性，高維聚類分析技術(shù)，以及針對大型數(shù)據(jù)集合的混合數(shù)值和分類數(shù)據(jù)的聚類方法[20]。
聚類是一個富有挑戰(zhàn)性的研究領(lǐng)域，尤其是大規(guī)模高維數(shù)據(jù)集合的聚類。
數(shù)據(jù)挖掘?qū)垲惖囊笕缦拢篬17] 1. 可伸縮性：對任意規(guī)模的數(shù)據(jù)集合都可處理。
2. 處理不同類型屬性的能力：對不同類型屬性(如，數(shù)值型，正性，標(biāo)類型等)都可以處理。
3. 發(fā)現(xiàn)任意形狀的聚類：前面所說基于歐氏距離的聚類方法只能對球型數(shù)據(jù)聚類，如果數(shù)據(jù)類是條型，線形等其他形狀如何聚類。
4. 用于決定輸入?yún)?shù)的領(lǐng)域知識的最小化： 一些聚類方法聚類前需要確定一些參數(shù)，如 k-means，必須知道 k 才能開始聚類，往往這些參數(shù)對聚類結(jié)果有這至關(guān)重要的影響。
5. 處理噪聲的能力： 數(shù)據(jù)中的噪聲會影響到聚類的效果，如何把這種影響降到最低，做沒有影響。
6. 對輸入順序不敏感。
7. 高維性(high dimensionality) ：維數(shù)越大，計算越大，這種增長可能是指數(shù)增長的，如何有效地處理高維數(shù)據(jù)[16]。
8. 基于約束的聚類：聚類過程中有約束的影響，聚類的可行區(qū)域要符合約束。
9. 可解釋性和可用性：用戶希望聚類的結(jié)果是可解釋的，可理解的，可用的。
經(jīng)典優(yōu)化算法和啟發(fā)式優(yōu)化算法都是迭代算法，但是，它們又有很大區(qū)別：1.經(jīng)典算法是以一個可行解為迭代的初始值，而啟發(fā)式算法是以一組可行解為初始值;2.經(jīng)典算法的搜索策略為確定性的，而啟發(fā)式算法的搜索策略是結(jié)構(gòu)化和隨機(jī)化;
3.經(jīng)典算法大多都需要導(dǎo)數(shù)信息，而啟發(fā)式算法僅用到目標(biāo)函數(shù)值的信息;4.經(jīng)典算法對 -15- 函數(shù)性質(zhì)有著嚴(yán)格要求，而啟發(fā)式算對函數(shù)性質(zhì)沒有太大要求;5.經(jīng)典算法的計算量要比啟發(fā)式算法小很多。
比如，對于規(guī)模較大且函數(shù)性質(zhì)比較差的優(yōu)化問題，經(jīng)典算法的效果不好，但一般的啟發(fā)式算法的計算量太大[6]。
優(yōu)化算法的主要由搜索方向和搜索步長組成。
搜索方向和搜索步長的選區(qū)決定了優(yōu)化算法的搜索廣度和搜索深度。
經(jīng)典優(yōu)化算法和啟發(fā)式優(yōu)化算法的區(qū)別主要是由其搜索機(jī)制不同造成的。
經(jīng)典算法的搜索方向和搜索步長是由局部信息(如導(dǎo)數(shù))決定的所以只能對局部進(jìn)行有效的深度搜索，而不能進(jìn)行有效廣度搜索，所以經(jīng)典的優(yōu)化算法很難跳出局部最優(yōu)。
啟發(fā)式優(yōu)化算法，為了避免像經(jīng)典優(yōu)化算法那樣陷入局部最優(yōu)，采用了相對有效的廣度搜索，不過這樣做使得在問題規(guī)模較大的時候計算量難以承受。
縱觀優(yōu)化算法的發(fā)展，完美的算法是不存在的。
我們評價算法好壞的標(biāo)準(zhǔn)： (1)算法收斂速度; (2)算法使用范圍(普適性) ; (3)算法的時間復(fù)雜度; (4)算法得到解得質(zhì)量(局部性或全局性，對絕對最優(yōu)解的近似程度) ; (5)算法的可實現(xiàn)性; 可以說這些標(biāo)準(zhǔn)是不可公度的(不可能同時都好) 。
以全局最優(yōu)問題為例，要求計算時間少，搜索廣度無法保證，解得質(zhì)量就差;要求收斂速度快，就需要有效的搜索方向，有了搜索方向就降低了搜索廣度，這樣解得全局最優(yōu)性無法保證。
計算復(fù)雜性理論，全局優(yōu)化問題是NP-complete 問題。
我們只有根據(jù)實際問題采用不同的啟發(fā)式算法。
雖然算法的評價標(biāo)準(zhǔn)是不可公度的， 但是在具體實際問題中，這些標(biāo)準(zhǔn)不是等重要性的。
比如對于某些問題對解得要求降低 10%，它的計算是時間就可以減少50%。
這樣做是否值得，要根據(jù)實際情況而定。
在不明顯影響解質(zhì)量的前提下，如何提高啟發(fā)式算法計算速度。
一般的啟發(fā)式算法大部分都采用隨機(jī)搜索策略進(jìn)行廣度搜索，每次搜索的規(guī)模比較大(可行解數(shù)目) ，可以引入數(shù)據(jù)發(fā)掘的思想，對這些可行解及其所對應(yīng)函數(shù)值進(jìn)行數(shù)據(jù)挖掘。
數(shù)據(jù)挖掘 -15- 對大量數(shù)據(jù)進(jìn)行分析(這里主要用到的是其中的聚類分析)從中提取有價值的信息，尋找其找的規(guī)律，近似計算出最大可能下降方向，提高搜索效率。
這是《基于聚類分析的啟發(fā)式優(yōu)化算法》研究目的。
參考文獻(xiàn)：
【二】北京理工大學(xué)碩士開題報告模板
碩士學(xué)位論文 開題報告 選題名稱 ____________________________ 學(xué) 姓 導(dǎo) 號 ___________ 名 ___________ 師 ___________ 研究方向 ___________ 二級學(xué)科 ___________ 一級學(xué)科 ___________ 學(xué) 院 ___________ 年 月 日 填 表 說 明 1.只有學(xué)籍狀態(tài)為注冊或懸置的研究生才允許開題。
但學(xué)籍狀態(tài)為懸置 的研究生只有在完成注冊手續(xù)之后，開題報告及其評審結(jié)果才能被認(rèn)可。
2.碩士學(xué)位論文開題報告封面及一至八項必須用計算機(jī)輸入、打印。
3.開題報告為 A4 大小，于左側(cè)裝訂成冊。
碩士研究生應(yīng)逐項認(rèn)真填 寫，各欄空格不夠時請自行加頁。
4.開題報告經(jīng)指導(dǎo)教師審閱通過后，由碩士研究生在學(xué)科組或更大范圍 內(nèi)宣讀，并接受專家組質(zhì)疑、評議。
專家組由三名以上高級職稱專家組成。
開題報告應(yīng)由碩士生導(dǎo)師為主體組成的評審小組評審。
評審合格后，裝訂， 。
評審合格后，裝訂， 學(xué)院歸檔留存?zhèn)洳椤?/p>
學(xué)院歸檔留存?zhèn)洳椤?/p>
歸檔留存?zhèn)洳?5.碩士研究生應(yīng)在選題前閱讀相關(guān)領(lǐng)域的中外文資料，并寫出不少于 4000 字的文獻(xiàn)綜述報告，引用參考文獻(xiàn)的篇數(shù)不得低于本學(xué)科專業(yè)培養(yǎng)方案 的規(guī)定。
文獻(xiàn)綜述報告應(yīng)反映國際和國內(nèi)本領(lǐng)域的研究歷史、現(xiàn)狀和發(fā)展趨 勢。
文獻(xiàn)綜述報告是開題報告的必要附件，開題報告通過后，由學(xué)院留存。
6.“參考文獻(xiàn)”著錄按照 GB7714-87 文參考文獻(xiàn)著錄規(guī)則執(zhí)行。
書寫順 序為：序號·作者·論文名或著作名·雜志或會議名·卷號、期號或會議地 點·出版社·頁號·年。
一 簡表 研 究 生 簡 況 姓名 學(xué)號 學(xué)科、專業(yè) 本科畢業(yè)時間 姓名 職稱 本科畢業(yè)學(xué)校 工作單位 簽字 性別 入學(xué)時間 出生年月 身份證號 指導(dǎo)小組 導(dǎo)師 小組成員 名稱 中文 英文 國家項目( 自擬項目( 基礎(chǔ)研究( )： 部(省)項目( ); 是否兵器類項目( ); 應(yīng)用基礎(chǔ)研究( ) ) 摘 要 );
企業(yè)項目( ); ) 類別 性質(zhì) ); 是否涉密(是/否，密級： ); 應(yīng)用技術(shù)研究( ) 與導(dǎo)師課題研 究課題的關(guān)系 是導(dǎo)師研究課題的一部分( 與導(dǎo)師研究課題無關(guān)( 研 究 課 題 1.關(guān)鍵詞限 3~5 個;2.關(guān)鍵詞之間用“;”分隔。
關(guān) 鍵 詞 英文 中文 二 選題依據(jù) 簡述該選題的研究意義、國內(nèi)外研究概況和發(fā)展趨勢。
三 研究內(nèi)容 四 研究方案 擬采用的研究方法、技術(shù)路線、實驗方案及可行性分析。
五 研究工作進(jìn)度安排 理論研究：應(yīng)包括文獻(xiàn)調(diào)研，理論推導(dǎo)，數(shù)值計算，理論分析，撰寫論文等; 實驗研究和工程技術(shù)研究：應(yīng)包括文獻(xiàn)調(diào)研，理論分析，實驗設(shè)計，儀器設(shè)備的研制和調(diào)試，實驗操 作，實驗數(shù)據(jù)的分析處理，撰寫論文等。
六 預(yù)期研究成果 本課題創(chuàng)新之處 七 本課題創(chuàng)新之處 說明研究內(nèi)容、擬采用的研究方法、技術(shù)路線或預(yù)期成果中有哪些創(chuàng)新之處。
八 研究基礎(chǔ) 1.與本項目有關(guān)的研究工作積累和已取得的研究工作成績。
2.已具備的實驗條件，尚缺少的實驗條件和解決的途徑(包括利用國家重點實驗室和部門開放實驗室 的計劃與落實情況)。
3. 研究經(jīng)費預(yù)算計劃和落實情況。
碩士學(xué)位論文開題報告——導(dǎo)師意見 士學(xué)位論文開題報告——導(dǎo)師意見 開題報告—— 學(xué)籍狀態(tài) 學(xué)位論文是否已被批準(zhǔn)為涉密論文 導(dǎo)師對開題報告的審閱意見： □ □ 注冊 是 □ □ 懸置 否 導(dǎo)師 簽字： 年 說明： 本頁全部由指導(dǎo)教師填寫。
月 日 碩士學(xué)位論文開題報告評審表 士學(xué)位論文開題報告評審表 學(xué)號 所在學(xué)院 課程學(xué)習(xí)情況 選題名稱 課題經(jīng)費來源 開題報告時間 姓 評 審 組 成 員 組長 名 職 稱 工作單位 簽 字 已修課程學(xué)分 姓名 學(xué)科、專業(yè) 待修課程學(xué)分 導(dǎo)師姓名 組員
評審組意見： 組長簽字： 年 月 日 碩士學(xué)位論文開題 文 獻(xiàn) 綜 述 報 告 報告題目 ____________________________
學(xué) 姓 導(dǎo) 號 ___________ 名 ___________ 師 ___________ 研究方向 ___________ 二級學(xué)科 ___________ ___________ 一級學(xué)科 ___________ 學(xué) 院 ___________ 年 月 日 文獻(xiàn)綜述報告要求與打印格式說明 文獻(xiàn)綜述報告要求與打印格式說明 綜述報告要求與
1. 文獻(xiàn)綜述報告應(yīng)符合碩士研究生所在學(xué)科培養(yǎng)方案的要求。
2. 文獻(xiàn)綜述報告的內(nèi)容不再在開題報告中重復(fù)，需單獨在必修環(huán)節(jié) 中上傳。
3. 文獻(xiàn)綜述報告必須對相關(guān)領(lǐng)域已取得之成果進(jìn)行歸納總結(jié)，結(jié)合 學(xué)位論文選題對相關(guān)領(lǐng)域未來的發(fā)展和研究提出自己的觀點。
4. 打印用紙：A4;裝訂后，學(xué)院歸檔留存?zhèn)洳椤?/p>
裝訂后 學(xué)院歸檔留存?zhèn)洳?歸檔留存?zhèn)洳椤?/p>
5. 頁眉為“北京理工大學(xué)碩士學(xué)位論文開題文獻(xiàn)綜述報告”; 加 黑宋體，小 3 號，居中。
頁碼居右排版; 6. 頁 面 設(shè) 計 ： 頁 眉 2.5cm ， 頁 腳 1.5cm ， 左 邊 距 3cm ， 右 邊 距 2.4cm，正文用宋體，小 4 號，行間距 26 磅。
碩士研究生文獻(xiàn)綜述報告評閱表 研 究 生 簡 況 本科畢業(yè)時間 指導(dǎo)小組 導(dǎo)師 姓名 職稱 本科畢業(yè)學(xué)校 工作單位 簽字 學(xué)科、專業(yè) 姓名 學(xué)號 性別 入學(xué)時間 出生年月 身份證號 小組成員 文獻(xiàn)綜述報告成績 □ 優(yōu) □ 良 □ 通過 □ 未通過 導(dǎo)師評閱意見 簽字： 年 月 日
【開題報告文獻(xiàn)綜述 北理工】相關(guān)文章：
開題報告文獻(xiàn)綜述10-06
開題報告的文獻(xiàn)綜述09-30
文獻(xiàn)綜述開題報告09-30
開題報告 文獻(xiàn)綜述09-30
開題報告,文獻(xiàn)綜述,09-30
開題報告文獻(xiàn)綜述范文09-30
論文開題報告文獻(xiàn)綜述09-30
開題報告文獻(xiàn)綜述范例09-30
本科開題報告文獻(xiàn)綜述09-30