大數(shù)據(jù)分析方法與應(yīng)用 課件 第7章 啟發(fā)式算法

大數(shù)據(jù)分析方法與應(yīng)用上海理工大學(xué)主講人：耿秀麗

教授第七章啟發(fā)式算法7.1

啟發(fā)式算法的基本原理目錄CONTENTS7.2

啟發(fā)式算法的類型7.3

遺傳算法及其實(shí)現(xiàn)7.4

粒子群算法及其實(shí)現(xiàn)7.5物流配送中心選址案例分析第七章學(xué)習(xí)結(jié)構(gòu)框架啟發(fā)式算法

什么是啟發(fā)式算法？啟發(fā)式算法是一種通過(guò)模擬自然現(xiàn)象或人類的經(jīng)驗(yàn)、知識(shí)和智慧，來(lái)尋求解決方案較優(yōu)或近似最優(yōu)的問(wèn)題求解方法。它能夠在有限時(shí)間內(nèi)找到接近最優(yōu)解的可行解，具有計(jì)算效率高、適應(yīng)性強(qiáng)、魯棒性強(qiáng)、可并行化等特點(diǎn)，并被廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、圖論等實(shí)際問(wèn)題中。7.1

啟發(fā)式算法的基本原理

組合優(yōu)化問(wèn)題人工智能領(lǐng)域數(shù)學(xué)優(yōu)化領(lǐng)域數(shù)據(jù)挖掘和模式識(shí)別領(lǐng)域最小生成樹(shù)調(diào)度和資源分配問(wèn)題多目標(biāo)優(yōu)化問(wèn)題通過(guò)引入啟發(fā)式準(zhǔn)則和尋找合適的搜索策略，可以在多個(gè)領(lǐng)域獲得較好的解決方法。在實(shí)際問(wèn)題中有著廣泛的應(yīng)用前景。啟發(fā)式算法的原理主要分為兩個(gè)方面：?jiǎn)l(fā)式函數(shù)和搜索策略。7.1

啟發(fā)式算法基本原理

7.1.1

啟發(fā)式函數(shù)啟發(fā)式函數(shù)是一種評(píng)估函數(shù)，它根據(jù)特定問(wèn)題的信息來(lái)評(píng)估解的質(zhì)量，并指導(dǎo)算法搜索解空間。在搜索空間中，每個(gè)狀態(tài)都有一個(gè)相應(yīng)的評(píng)估值，而啟發(fā)式函數(shù)本身可以根據(jù)搜索問(wèn)題的特點(diǎn)來(lái)設(shè)計(jì)和選擇。實(shí)踐中，設(shè)計(jì)好的啟發(fā)式函數(shù)可以在找到最優(yōu)解或接近最優(yōu)值的同時(shí)，有效降低搜索空間的大小，從而使算法具有更快的搜索速度。一個(gè)好的啟發(fā)式函數(shù)應(yīng)該滿足以下條件：1）啟發(fā)式函數(shù)應(yīng)該準(zhǔn)確地評(píng)估每個(gè)狀態(tài)，以便在搜索空間中找到最優(yōu)解或接近最優(yōu)值；2）啟發(fā)式函數(shù)應(yīng)該能夠快速計(jì)算，以便算法具有較快的搜索速度；3）啟發(fā)式函數(shù)應(yīng)該合理有效地指導(dǎo)算法搜索，以便算法能夠充分利用先前找到的最優(yōu)解。常用的啟發(fā)式函數(shù)包括曼哈頓距離（ManhattanDistance）、歐幾里得距離（EuclideanDistance）、切比雪夫距離（ChebyshevDistance）等。這些啟發(fā)式函數(shù)可以用于許多優(yōu)化問(wèn)題，如旅行商問(wèn)題、路徑規(guī)劃等。7.1啟發(fā)式算法基本原理

7.1.2

搜索策略一、定義搜索策略作為一種指導(dǎo)搜索過(guò)程的規(guī)則集合，也扮演著啟發(fā)式算法的重要組成部分。搜索策略是指在解空間中進(jìn)行搜索，并從中選擇有可能是最佳解的解。二、分類實(shí)現(xiàn)方式搜索順序隨機(jī)搜索深度優(yōu)先搜索局部搜索廣度優(yōu)先搜索全局搜索遺傳算法7.2

啟發(fā)式算法的類型

啟發(fā)式算法仿植物類算法：模擬植物的生長(zhǎng)、繁殖和適應(yīng)環(huán)境的過(guò)程仿動(dòng)物類算法：模擬動(dòng)物的行為、交流和適應(yīng)環(huán)境的過(guò)程。0102蟻群算法鳥(niǎo)群算法粒子群算法蜂群算法魚(yú)群算法蝙蝠算法向光性算法雜草優(yōu)化算法模擬植物生長(zhǎng)算法特點(diǎn)：具有較強(qiáng)的自適應(yīng)性和魯棒性。（魯棒性：系統(tǒng)或算法在面對(duì)異常情況或輸入變化時(shí)能夠保持良好性能的能力）7.2

啟發(fā)式算法的類型

7.2.1

仿動(dòng)物類啟發(fā)式算法——蟻群算法（AntColonyOptimization,ACO）仿動(dòng)物類啟發(fā)式算法利用生物進(jìn)化、個(gè)體行為、群體行為等動(dòng)物的特征來(lái)進(jìn)行優(yōu)化求解，其最主要的特點(diǎn)是能夠考慮群體的可行性，解決發(fā)現(xiàn)局部最優(yōu)的問(wèn)題，提高搜索算法的效率。蟻群算法是基于螞蟻的運(yùn)動(dòng)規(guī)律，通過(guò)模擬螞蟻在搜索過(guò)程中沿路徑釋放信息素、揮發(fā)信息素等行為模式，來(lái)搜索全局最優(yōu)或局部最優(yōu)解。螞蟻在移動(dòng)過(guò)程中會(huì)釋放信息素，信息素越高表示該路徑被螞蟻選擇的概率越大，所以螞蟻更傾向于選擇信息素濃度高且長(zhǎng)度短的路徑。應(yīng)用：組合優(yōu)化問(wèn)題、路徑規(guī)劃問(wèn)題、調(diào)度問(wèn)題，易陷入局部最優(yōu)7.2

啟發(fā)式算法的類型

7.2.1

仿動(dòng)物類啟發(fā)式算法——粒子群算法（ParticleSwarmOptimization,PSO）粒子群算法是基于鳥(niǎo)類在尋找食物等過(guò)程中的覓食行為而設(shè)計(jì)的，這種算法通過(guò)模擬鳥(niǎo)類協(xié)作尋找最優(yōu)優(yōu)化結(jié)果；粒子群算法的基本思想是將待優(yōu)化問(wèn)題轉(zhuǎn)化為一個(gè)多維搜索空間中的優(yōu)化問(wèn)題，每個(gè)粒子代表一個(gè)可能的解，并根據(jù)自身的經(jīng)驗(yàn)和群體的經(jīng)驗(yàn)來(lái)更新自己的位置和速度。粒子的位置表示解的值，速度表示解的搜索方向和步長(zhǎng)。更新速度過(guò)程包括粒子向自己歷史最優(yōu)位置靠近和向群體歷史最優(yōu)位置靠近。應(yīng)用：函數(shù)優(yōu)化、組合優(yōu)化、參數(shù)優(yōu)化、非線性優(yōu)化問(wèn)題7.2啟發(fā)式算法的類型

7.2.1

仿動(dòng)物類啟發(fā)式算法——蜂群算法（BeeAlgorithm）蜂群算法是由國(guó)外學(xué)者于2005年首次提出，是一種基于蜜蜂覓食行為的啟發(fā)式優(yōu)化算法。蜜蜂覓食行為中包含了一系列的搜索、選擇和通信過(guò)程，這些行為被模擬為算法的操作。基本思想：通過(guò)模擬蜜蜂在搜索食物源時(shí)的行為尋找問(wèn)題的最優(yōu)解。蜂群算法的搜索過(guò)程是一個(gè)迭代的過(guò)程，每一次迭代中，蜜蜂們根據(jù)一定的規(guī)則進(jìn)行搜索，并根據(jù)搜索結(jié)果更新自己的位置和狀態(tài)。具有較好的全局搜索能力和收斂性能。它可以應(yīng)用于多種優(yōu)化問(wèn)題，如函數(shù)優(yōu)化、組合優(yōu)化、路徑規(guī)劃等。（引領(lǐng)蜂）7.2

啟發(fā)式算法的類型

7.2.1仿動(dòng)物類啟發(fā)式算法——魚(yú)群算法（FishSchoolSearch,FSS）魚(yú)群算法是由李曉磊博士于2003年提出的，是一種基于模擬自然界魚(yú)群食物搜索行為的啟發(fā)式優(yōu)化算法。該算法受到魚(yú)群行為的啟發(fā)，模擬了魚(yú)群中魚(yú)的個(gè)體行為和群體行為，用于解決優(yōu)化問(wèn)題?；舅枷耄和ㄟ^(guò)個(gè)體之間的相互作用和信息交流，以及對(duì)環(huán)境的感知和適應(yīng)，實(shí)現(xiàn)問(wèn)題的求解。具有較強(qiáng)的全局搜索能力和較快的收斂速度。（一片水域，如果某個(gè)地方的魚(yú)類數(shù)目最多，那么這個(gè)地方一般來(lái)說(shuō)就是水域內(nèi)富含營(yíng)養(yǎng)物質(zhì)最多的地方，依據(jù)這一特點(diǎn)來(lái)模仿魚(yú)群的覓食、聚群、追尾、隨機(jī)行為，以實(shí)現(xiàn)全局尋優(yōu)的目的。）應(yīng)用：各種需要尋找最優(yōu)解的問(wèn)題，尤其是那些復(fù)雜、高維、非線性的優(yōu)化問(wèn)題。優(yōu)點(diǎn)：并行性強(qiáng)、全局搜索能力強(qiáng)、適應(yīng)性強(qiáng)、算法簡(jiǎn)單易實(shí)現(xiàn)。7.2

啟發(fā)式算法的類型

7.2.1

仿動(dòng)物類啟發(fā)式算法——蝙蝠算法（BatAlgorithm）蝙蝠算法是由英國(guó)科學(xué)家Yang教授于2010年提出的一種模擬蝙蝠群體行為的啟發(fā)式優(yōu)化算法?；舅枷耄耗M蝙蝠在尋找食物和繁殖過(guò)程中的行為。蝙蝠在夜間通過(guò)發(fā)出超聲波信號(hào)來(lái)探測(cè)周圍環(huán)境，并根據(jù)接收到的回聲來(lái)判斷目標(biāo)的位置。發(fā)現(xiàn)目標(biāo)后，它會(huì)朝著目標(biāo)飛去，并通過(guò)調(diào)整頻率和聲音的強(qiáng)度來(lái)調(diào)整自己的飛行方向和速度。應(yīng)用：各種優(yōu)化問(wèn)題，特別是連續(xù)優(yōu)化問(wèn)題優(yōu)點(diǎn)：算法基本思想簡(jiǎn)單，易于理解和實(shí)現(xiàn)缺點(diǎn)：存在多個(gè)參數(shù)需要去設(shè)置，如蝙蝠個(gè)體的速度、頻率等，對(duì)初始解敏感，不同的初始解可能導(dǎo)致不同的搜索結(jié)果7.2

啟發(fā)式算法的類型

7.2.1

仿植物類啟發(fā)式算法算法名稱概念基本思想應(yīng)用向光性算法（PhototaxisAlgorithm）用于解決優(yōu)化問(wèn)題的算法，也稱為光子算法。該算法模擬了光在環(huán)境中的傳播和反射過(guò)程，通過(guò)光的傳播路徑來(lái)搜索最優(yōu)解通過(guò)模擬生物體對(duì)光的感知和移動(dòng)來(lái)解決優(yōu)化問(wèn)題連續(xù)優(yōu)化問(wèn)題和多模態(tài)優(yōu)化問(wèn)題雜草優(yōu)化算法（WeedOptimizationAlgorithm,WOA）一種基于仿生學(xué)的優(yōu)化算法通過(guò)模擬雜草的生長(zhǎng)過(guò)程來(lái)求解優(yōu)化問(wèn)題機(jī)器學(xué)習(xí)、圖像處理、電力系統(tǒng)優(yōu)化模擬植物生長(zhǎng)算法(PlantGrowthSimulationAlgorithm,PGSA)一種以植物向光性機(jī)理（形態(tài)素濃度理論）為啟發(fā)準(zhǔn)則的智能優(yōu)化算法。通過(guò)模擬植物的生理機(jī)制和生長(zhǎng)規(guī)律來(lái)解決問(wèn)題，可以應(yīng)用于多種問(wèn)題的求解函數(shù)優(yōu)化、組合優(yōu)化、圖像處理（全局搜索）7.3

遺傳算法及其實(shí)現(xiàn)

7.3.1

遺傳算法的原理一、概念遺傳算法（GeneticAlgorithm,GA）起源于對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究，是一種隨機(jī)全局搜索優(yōu)化方法。二、原理遺傳算法通過(guò)模擬自然選擇和遺傳中發(fā)生的復(fù)制、交叉和變異等現(xiàn)象，從任一初始種群出發(fā)，通過(guò)隨機(jī)選擇、交叉和變異操作，產(chǎn)生一群更適合環(huán)境的個(gè)體，使群體進(jìn)化到搜索空間中越來(lái)越好的區(qū)域，這樣一代一代不斷繁衍進(jìn)化，最后收斂到一群最適應(yīng)環(huán)境的個(gè)體，從而求得問(wèn)題的優(yōu)質(zhì)解。三、優(yōu)勢(shì)在求解較為復(fù)雜的組合優(yōu)化問(wèn)題時(shí)，相對(duì)一些常規(guī)的優(yōu)化算法，遺傳算法通常能夠較快地獲得較好的優(yōu)化結(jié)果。四、應(yīng)用車間調(diào)度、機(jī)器仿真、信號(hào)處理

7.3

遺傳算法及其實(shí)現(xiàn)

7.3.1

遺傳算法的原理四、常用術(shù)語(yǔ)算法名稱概念染色體（Chromosome）染色體又可稱為基因型個(gè)體（Individuals），一定數(shù)量的個(gè)體組成了群體（Population），群體中個(gè)體的數(shù)量叫作群體大?。≒opulationsize）。位串（BitString）個(gè)體的表示形式，對(duì)應(yīng)于遺傳學(xué)中的染色體。基因（Gene）基因是染色體中的元素，用于表示個(gè)體的特征。例如有一個(gè)位串（即染色體）S=1011，則其中的1，0，1，1這4個(gè)元素分別稱為基因。特征值（Feature）在用位串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致，例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8適應(yīng)度（Fitness）各個(gè)體對(duì)環(huán)境的適應(yīng)程度叫作適應(yīng)度。為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問(wèn)題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)。這個(gè)函數(shù)通常會(huì)被用來(lái)計(jì)算個(gè)體在群體中被使用的概率?；蛐停℅enotype）或稱遺傳型，是指基因組定義遺傳特征和表現(xiàn)，對(duì)應(yīng)于GA中的位串表現(xiàn)型（Phenotype）指的是生物體的基因型在特定環(huán)境下的表現(xiàn)特征，對(duì)應(yīng)于GA中的位串解碼后的參數(shù)。7.3

遺傳算法及其實(shí)現(xiàn)

7.3.2

遺傳算法的步驟初始化種群：隨機(jī)生成一組初始個(gè)體，形成初始種群。評(píng)估適應(yīng)度：適應(yīng)度函數(shù)表明個(gè)體或解的優(yōu)劣性。根據(jù)具體問(wèn)題計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。遺傳算子：選擇操作、交叉操作、變異操作、終止判斷條件7.3

遺傳算法及其實(shí)現(xiàn)

7.3.3

遺傳算法的計(jì)算機(jī)實(shí)現(xiàn)常用軟件MATLAB是一種高級(jí)的數(shù)學(xué)計(jì)算軟件，它提供了豐富的工具箱和函數(shù)，可以方便地實(shí)現(xiàn)遺傳算法。Python是一種通用的編程語(yǔ)言，擁有豐富的科學(xué)計(jì)算庫(kù)，如NumPy、SciPy和DEAP等，可以用于實(shí)現(xiàn)遺傳算法。Java是一種廣泛使用的編程語(yǔ)言，它提供了強(qiáng)大的面向?qū)ο蟮木幊棠芰Γ梢杂糜趯?shí)現(xiàn)遺傳算法。7.3

遺傳算法及其實(shí)現(xiàn)

7.3.3

遺傳算法的計(jì)算機(jī)實(shí)現(xiàn)——驗(yàn)證Python軟件的實(shí)現(xiàn)初始化種群優(yōu)勝劣汰7.3

遺傳算法及其實(shí)現(xiàn)

7.3.3

遺傳算法的計(jì)算機(jī)實(shí)現(xiàn)——驗(yàn)證Python軟件的實(shí)現(xiàn)交配生殖、變異7.3

遺傳算法及其實(shí)現(xiàn)

7.3.3

遺傳算法的計(jì)算機(jī)實(shí)現(xiàn)——驗(yàn)證Python軟件的實(shí)現(xiàn)生物遺傳進(jìn)化7.4

粒子群算法及其實(shí)現(xiàn)

7.4.1粒子群算法的原理一、粒子群算法的靈感來(lái)源

粒子群算法被提出的靈感來(lái)源于鳥(niǎo)群覓食，鳥(niǎo)群覓食過(guò)程中，每只鳥(niǎo)沿著各個(gè)方向飛行去尋找食物，每只鳥(niǎo)兒都能記住到目前為止自己在飛行過(guò)程中最接近食物的位置，同時(shí)每只鳥(niǎo)兒之間也有信息共享，它們會(huì)比較到目前為止各自與食物之間的最近距離，從各自的最近距離中，選擇并記憶整體的一個(gè)最近距離位置。二、數(shù)學(xué)模型

每只鳥(niǎo)兒就是一個(gè)粒子，食物的位置也就是問(wèn)題的最優(yōu)解，鳥(niǎo)兒與食物的距離也即當(dāng)前粒子的目標(biāo)函數(shù)值。7.4

粒子群算法及其實(shí)現(xiàn)

7.4.2

粒子群算法的步驟對(duì)于每個(gè)粒子，它包含的元素：當(dāng)前時(shí)刻位置：(x1,x2,...,xn)當(dāng)前時(shí)刻的目標(biāo)函數(shù)值（也稱為適應(yīng)度）：f(x1,x2,...,xn)該粒子的歷史最優(yōu)位置：(x1_pbest，x2_pbest，...，xn_pbest)該粒子的歷史最優(yōu)目標(biāo)函數(shù)值：f_pbest=f(x1_pbest，x2_pbest，...，xn_pbest)對(duì)于全部粒子，它們共有的元素：粒子總數(shù)：num迭代總次數(shù)：cnt。粒子群算法也是一個(gè)迭代的過(guò)程，需要多次迭代才能獲取到理想的最優(yōu)解。全局最優(yōu)位置：(x1_gbest，x2_gbest，...，xn_gbest)全局最優(yōu)目標(biāo)函數(shù)值：f_gbest=f(x1_gbest，x2_gbest，...，xn_gbest)位置隨機(jī)化的上下限：xmin，xmax。迭代開(kāi)始的時(shí)候以及迭代的過(guò)程中，均需要對(duì)粒子的位置進(jìn)行隨機(jī)分布，需要設(shè)置隨機(jī)分布的上下限，不然隨機(jī)分布偏離得太遠(yuǎn)，會(huì)嚴(yán)重影響優(yōu)化結(jié)果。速度的上下限：Vmin，Vmax。迭代過(guò)程中，速度也具有一定的隨機(jī)性，需要限制速度的大小在一定范圍內(nèi)，不然如果速度值太大也會(huì)嚴(yán)重影響優(yōu)化結(jié)果。速度計(jì)算參數(shù)：c1、c2。通常取1.0~1.8的值。速度更新：Vi=w*Vi+c1*rand()*(pbesti+Xi)+c2*rand()*(gbest-Xi)位置更新：Xi=Xi+Vi7.4粒子群算法及其實(shí)現(xiàn)

7.4.3粒子群算法的計(jì)算機(jī)實(shí)現(xiàn)——驗(yàn)證設(shè)定PSO初始參數(shù)本節(jié)用Python軟件對(duì)粒子群算法進(jìn)行實(shí)現(xiàn)，問(wèn)題描述：求y=x2-4x+3最小值。7.4粒子群算法及其實(shí)現(xiàn)

7.4.3粒子群算法的計(jì)算機(jī)實(shí)現(xiàn)——驗(yàn)證設(shè)定目標(biāo)函數(shù)及初始化種群7.4粒子群算法及其實(shí)現(xiàn)

7.4.3粒子群算法的計(jì)算機(jī)實(shí)現(xiàn)——驗(yàn)證更新粒子速度和位置7.4粒子群算法及其實(shí)現(xiàn)

7.4.3粒子群算法的計(jì)算機(jī)實(shí)現(xiàn)——驗(yàn)證圖形可視化7.5

物流配送中心案例分析

一、問(wèn)題：

一共有五個(gè)配送中心候選節(jié)點(diǎn)，其建設(shè)成本和坐標(biāo)如表7-1所示。供應(yīng)點(diǎn)有13個(gè)，其坐標(biāo)和運(yùn)輸量如表7-2所示，通過(guò)遺傳算法分析配送中心可覆蓋的供應(yīng)點(diǎn)。配送中心候選節(jié)點(diǎn)建設(shè)成本（萬(wàn)元）坐標(biāo)15495.7（58.9,45.2）23458.8（54.9,117）34226.7（114,135）47294.2（67.7,195）58560.2（176,149）供應(yīng)點(diǎn)坐標(biāo)運(yùn)輸量1(106,74.1)67.572(105,117)107.153(74.9,91.5)221.564(81.8,147)293.935(136,161)105.536(192,43.4)191.167(39.9,63.0)285.48續(xù)表：8(37.7,85.3)197.079(41.7,152)304.2410(12.4,100)217.8211(31.7,9.80)100.9612(32.9,189)61.4713(159,218)258.37.5

物流配送中心案例分析

二、解題思路——提出假設(shè)

1）在一定備選范圍內(nèi)進(jìn)行配送中心的選取。2）供應(yīng)點(diǎn)數(shù)目多于配送中心數(shù)目。3）一個(gè)供應(yīng)點(diǎn)僅由一個(gè)配送中心提供配送服務(wù)，但一個(gè)配送中心可覆蓋多個(gè)供應(yīng)點(diǎn)。4）配送中心容量可滿足各供應(yīng)網(wǎng)點(diǎn)的總需求量。5）各供應(yīng)點(diǎn)配送需求一次性運(yùn)輸完成，且假設(shè)勻速行駛。6）只考慮配送中心建設(shè)成本、運(yùn)輸成本。符號(hào)及定義：

I：表示供應(yīng)點(diǎn)集合；

J：表示配送中心集合；

Cij：從供應(yīng)點(diǎn)i到配送中心j的運(yùn)輸成本；

qij：供應(yīng)點(diǎn)i到配送中心j的運(yùn)輸量；

fj：配送中心j的建設(shè)成本；

Dj：配送中心j的需求量；

P：配送中心的最大建設(shè)數(shù)量；

Mj：配送中心j的最大容量。7.5物流配送中心案例分析

二、解題思路——確定目標(biāo)函數(shù)及約束條件

目標(biāo)函數(shù)：

，表示總費(fèi)用最小約束條件1：

，配送中心的數(shù)量為2個(gè)；約束條件2：

從供應(yīng)點(diǎn)到配送中心的數(shù)量大于等于配送中心的需求量；約束條件3：

，配送中心容納能力限制；約束條件4：

，

，

，變量取值。7.5

物流配送中心案例分析

二、解題思路——Python

運(yùn)行

由備選中心2