人工智能通識基礎(chǔ)與應(yīng)用課件

人工智能通識基礎(chǔ)與應(yīng)用第2章機(jī)器學(xué)習(xí)目錄2.6進(jìn)化計(jì)算2.7群體智能2.8知識發(fā)現(xiàn)2.6進(jìn)化計(jì)算2.6進(jìn)化計(jì)算2.6.1進(jìn)化算法進(jìn)化算法也被稱作“演化算法”(EvolutionaryAlgorithms，EAs)，它屬于一個(gè)“算法簇”。雖然它存在諸多變化，比如有著不同的遺傳基因表達(dá)方式、不同的交叉和變異算子、會引用特殊算子，還有不同的再生和選擇方法等，但這些不同形式的進(jìn)化算法，其靈感統(tǒng)統(tǒng)都源自大自然中的生物進(jìn)化。相較于傳統(tǒng)的依靠微積分的方法以及窮舉法等優(yōu)化算法，進(jìn)化算法已然是一種發(fā)展較為成熟的全局優(yōu)化方法，它具備高魯棒性以及廣泛的適用性，同時(shí)還擁有自組織、自適應(yīng)、自學(xué)習(xí)這些特性，能夠突破問題性質(zhì)的限制，對那些傳統(tǒng)優(yōu)化算法難以解決的復(fù)雜問題進(jìn)行有效的處理。該算法的一般形式可以描述為(μ/ρ，λ)(μ/ρ＋λ)

進(jìn)化算法的重要部分不是突變的范圍不固定，而是繼承。進(jìn)化算法經(jīng)常被用到多目標(biāo)問題的優(yōu)化求解中。2.6進(jìn)化計(jì)算2.6.2遺傳算法遺傳算法(GeneticAlgorithms，CAs)是一類借鑒生物界的進(jìn)化規(guī)律(“優(yōu)勝劣汰”遺傳機(jī)制)演化而來的隨機(jī)化搜索方法。特點(diǎn)可以直接對結(jié)構(gòu)、對象展開操作，不會受到求導(dǎo)以及函數(shù)連續(xù)性方面的限制；運(yùn)用概率化的尋優(yōu)方法，能夠自動獲取并引導(dǎo)優(yōu)化的搜索空間，還能自適應(yīng)地調(diào)整搜索方向，無須依靠確定的規(guī)則。2.6.2遺傳算法運(yùn)用基本遺傳算法進(jìn)行問題求解的過程如下：1.編碼2.初始群體的生成。3.適應(yīng)性值評估檢測。4.選擇5.雜交6.變異基本遺傳算法可定義為一個(gè)八元組：SGA＝(C，E，P0，M，Φ，Γ，Ψ，Τ)遺傳算法的優(yōu)越性主要表現(xiàn)為以下兩點(diǎn)：在搜索的過程中，它不易陷入局部最優(yōu)的狀況，即便所定義的適應(yīng)函數(shù)呈現(xiàn)出不連續(xù)、非規(guī)則或者存在噪聲等情況，其依舊能夠以較高的概率尋找到整體最優(yōu)解。鑒于遺傳算法本身所固有的并行性特點(diǎn)，它十分適合在大規(guī)模并行計(jì)算機(jī)上應(yīng)用。與傳統(tǒng)的優(yōu)化算法相比，遺傳算法主要有以下幾個(gè)不同之處。遺傳算法不是直接作用在參變量集上的，而是利用參變量集的某種編碼。遺傳算法不是從單個(gè)點(diǎn)，而是從一個(gè)點(diǎn)的群體開始搜索的。遺傳算法利用適應(yīng)值信息，無須導(dǎo)數(shù)或其他輔助信息。遺傳算法利用概率轉(zhuǎn)移規(guī)則，而非確定性規(guī)則。2.6進(jìn)化計(jì)算2.6.3進(jìn)化策略進(jìn)化策略(EvolutionaryStrategies，ESs)模仿自然進(jìn)化原理作為一種求解參數(shù)優(yōu)化問題的方法。進(jìn)化策略強(qiáng)調(diào)在個(gè)體級上的行為變化。最簡單的實(shí)現(xiàn)方法如下。(1)定義的問題是尋找n維的實(shí)數(shù)向量x，它使函數(shù)F(x):

→R。(2)雙親向量的初始群體從每維可行范圍內(nèi)隨機(jī)選擇。(3)子孫向量的創(chuàng)建是從每個(gè)雙親向量加上零均方差高斯隨機(jī)變量。(4)根據(jù)最小誤差選擇向量為下一代新的雙親。(5)當(dāng)向量的標(biāo)準(zhǔn)偏差保持不變或沒有可用的計(jì)算方法時(shí)，處理結(jié)束。2.6進(jìn)化計(jì)算2.6.4進(jìn)化規(guī)劃進(jìn)化規(guī)劃(EvolutionaryProgramming，EP)的過程可理解為從所有可能的計(jì)算機(jī)程序形成的空間里搜索那些具備高適應(yīng)值的計(jì)算機(jī)程序個(gè)體，在進(jìn)化規(guī)劃當(dāng)中，會有成百甚至上千個(gè)計(jì)算機(jī)程序參與到遺傳進(jìn)化之中。(1)產(chǎn)生初始群體。(2)迭代完成下述子步驟，直至滿足選種標(biāo)準(zhǔn)。執(zhí)行群體中的每個(gè)程序，根據(jù)它解決問題的能力，給它指定一個(gè)適應(yīng)值。借助變異等操作來生成新的計(jì)算機(jī)程序群體。(3)在后代中適應(yīng)值最高的計(jì)算機(jī)程序個(gè)體被指定為進(jìn)化程序設(shè)計(jì)的結(jié)果。2.7群體智能Thoughtforcustomerservice"isthesacredmissionofhidesign。2.7群體智能2.7.1蟻群算法1蟻群算法模型蟻群算法起源蟻群算法(AntColonyAlgorithm)是由意大利學(xué)者多里科(M。Dorigo)等人在1991年的首屆歐洲人工生命會議上提出的，它主要是運(yùn)用群體智能解決組合優(yōu)化方面的問題。蟻群算法原理螞蟻在找尋食物的過程中，會在自己走過的路徑上釋放一種叫信息素（Pheromone）的物質(zhì)，而信息素具有容易揮發(fā)的特性，隨著時(shí)間不斷流逝，遺留在路徑上的信息素含量會變得越來越少。倘若螞蟻從巢穴出發(fā)時(shí)，路徑上已經(jīng)存在信息素了，那么螞蟻就會朝著信息素濃度比較高的路徑前行，如此一來，它所經(jīng)過的路徑上的信息素濃度便會進(jìn)一步升高，進(jìn)而形成一種正向的催化作用。經(jīng)過一定時(shí)長的搜索之后，螞蟻?zhàn)罱K能夠找到一條從巢穴通往食物源的最短路徑。2.7群體智能2.7.1蟻群算法食物BDCA1122巢穴螞蟻覓食示意圖蟻群算法的簡單流程如下:(1)初始化。(2)為每只螞蟻選擇下一個(gè)節(jié)點(diǎn)。(3)更新信息素矩陣。(4)檢查終止條件。(5)輸出最優(yōu)值。2.7群體智能基于群體智能的混合聚類算法主要思想：把待測對象隨機(jī)地分布于一個(gè)二維網(wǎng)格的環(huán)境之中。像螞蟻這類簡單個(gè)體，會去測量當(dāng)前對象在局部環(huán)境下的群體相似度，然后借助概率轉(zhuǎn)換函數(shù)算出拾起或者放下對象的概率，再按照這個(gè)概率來采取相應(yīng)的行動。經(jīng)過群體之間大量的相互作用后，便能夠得出若干個(gè)聚類中心。最終，運(yùn)用遞歸算法來收集相應(yīng)的聚類結(jié)果。群體相似度一個(gè)待聚類模式(對象)與其所在一定的局部環(huán)境中所有其他模式的綜合相似度。概率轉(zhuǎn)換函數(shù)概率轉(zhuǎn)換函數(shù)是將群體相似度轉(zhuǎn)換為簡單個(gè)體移動待聚類模式(對象)概率的函數(shù)，它是以群體相似度為自變量的函數(shù)，函數(shù)的值域是[0，1]2.7群體智能基于群體智能的混合聚類算法CSIM主要包括兩個(gè)階段：第一階段要完成的是基于群體智能的聚類過程；第二階段會以第一階段所獲取的聚類中心均值模板以及聚類中心的個(gè)數(shù)作為參數(shù)，進(jìn)而實(shí)現(xiàn)K均值聚類過程。需要注意的是，在收集第一階段聚類結(jié)果的時(shí)候，那些由單個(gè)模式所形成的聚類中心并不會被列為第二階段的初始聚類中心模板。2.7群體智能2.7.2粒子群優(yōu)化算法粒子群優(yōu)化(ParticleSwarmOptimization，PSO)算法屬于一種基于群體智能的全局隨機(jī)搜索算法，它因模擬鳥群在覓食過程中所展現(xiàn)出的遷徙以及群聚行為而被提出。粒子群優(yōu)化算法和其他進(jìn)化算法存在相同之處，它們同樣都是基于“種群”和“進(jìn)化”的概念，借助個(gè)體之間的協(xié)作與競爭，去實(shí)現(xiàn)對復(fù)雜空間中最優(yōu)解的搜索。不過，粒子群優(yōu)化算法也有其獨(dú)特的地方，它是把群體中的個(gè)體視作在D維搜索空間里沒有質(zhì)量和體積的粒子，在這個(gè)空間中，每個(gè)粒子會以特定的速度在解空間進(jìn)行運(yùn)動，并且朝著自身歷史最佳位置Pbest以及鄰域歷史最佳位置Nest聚集，進(jìn)而達(dá)成對候選解的進(jìn)化。2.7群體智能2.7.2粒子群優(yōu)化算法基本粒子群優(yōu)化算法的流程初始化個(gè)體極值與全局最優(yōu)解更新速度和位置2.7群體智能2.7.2粒子群優(yōu)化算法在全局最優(yōu)模式中，每個(gè)個(gè)體被吸引到由種群任何個(gè)體發(fā)現(xiàn)的最優(yōu)解。全局最優(yōu)模式有較快的收斂速度，但容易陷入局部極值。而在局部最優(yōu)模式中，粒子總是依據(jù)自身的信息和鄰域內(nèi)的最優(yōu)值相關(guān)信息來對自身的運(yùn)動軌跡進(jìn)行調(diào)整，并非依據(jù)群體粒子的最優(yōu)值信息。粒子群優(yōu)化算法全局最優(yōu)局部最優(yōu)2.7群體智能2.7.2粒子群優(yōu)化算法由兩個(gè)粒子空間位置決定“鄰居”，它們的遠(yuǎn)近用粒子間的距離來度量。編號方法，即粒子群中的粒子在搜索之前就被編以不同的號碼，形成環(huán)狀拓?fù)渖鐣Y(jié)構(gòu)。局部模式第一種方式，在每次迭代之后都需要計(jì)算每個(gè)粒子與其他粒子間的距離來確定鄰域中包括哪些粒子，這會導(dǎo)致算法的復(fù)雜程度增加，降低算法的運(yùn)行效率。第二種方式由于事先對粒子進(jìn)行了編號，因而在迭代中粒子的鄰域不會改變，這導(dǎo)致在搜索過程中，當(dāng)前粒子與指定的鄰域粒子迅速聚集，而整個(gè)粒子群就被分成幾個(gè)小塊，表面上看似增大了搜索范圍，實(shí)際上大大降低了收斂速度。雖然局部最優(yōu)模式收斂速度較慢，但具有較強(qiáng)的全局搜索能力。2.7群體智能2.7.2粒子群優(yōu)化算法

粒子群優(yōu)化算法有著諸多優(yōu)勢，其算法較為簡潔，易于操作實(shí)現(xiàn)，并且不需要對大量參數(shù)進(jìn)行調(diào)整，同時(shí)也無須依賴梯度信息。它是解決非線性連續(xù)優(yōu)化問題、組合優(yōu)化問題以及混合整數(shù)非線性優(yōu)化問題的有效優(yōu)化工具。2.8知識發(fā)現(xiàn)Thoughtforcustomerservice"isthesacredmissionofhidesign。2.8知識發(fā)現(xiàn)

知識發(fā)現(xiàn)是從數(shù)據(jù)集中識別出有效的、新穎的、潛在有用的，以及可理解模式的非平凡過程。這里數(shù)據(jù)集是一組事實(shí)F（如關(guān)系數(shù)據(jù)庫中的記錄）。模式是一個(gè)用語言L來表示的表達(dá)式E，它可用來描述數(shù)據(jù)集F的某個(gè)子集FE，E作為一個(gè)模式，要求本身比數(shù)據(jù)子集FE的枚舉要簡單。有效性是指發(fā)現(xiàn)的模式對于新的數(shù)據(jù)仍保持有一定的可信度。新穎