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