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

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

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

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

7.1.1

啟發(fā)式函數(shù)啟發(fā)式函數(shù)是一種評(píng)估函數(shù)，它根據(jù)特定問題的信息來評(píng)估解的質(zhì)量，并指導(dǎo)算法搜索解空間。在搜索空間中，每個(gè)狀態(tài)都有一個(gè)相應(yīng)的評(píng)估值，而啟發(fā)式函數(shù)本身可以根據(jù)搜索問題的特點(diǎn)來設(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)化問題，如旅行商問題、路徑規(guī)劃等。7.1啟發(fā)式算法基本原理

7.1.2

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

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

啟發(fā)式算法仿植物類算法：模擬植物的生長、繁殖和適應(yīng)環(huán)境的過程仿動(dòng)物類算法：模擬動(dòng)物的行為、交流和適應(yīng)環(huán)境的過程。0102蟻群算法鳥群算法粒子群算法蜂群算法魚群算法蝙蝠算法向光性算法雜草優(yōu)化算法模擬植物生長算法特點(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)物的特征來進(jìn)行優(yōu)化求解，其最主要的特點(diǎn)是能夠考慮群體的可行性，解決發(fā)現(xiàn)局部最優(yōu)的問題，提高搜索算法的效率。蟻群算法是基于螞蟻的運(yùn)動(dòng)規(guī)律，通過模擬螞蟻在搜索過程中沿路徑釋放信息素、揮發(fā)信息素等行為模式，來搜索全局最優(yōu)或局部最優(yōu)解。螞蟻在移動(dòng)過程中會(huì)釋放信息素，信息素越高表示該路徑被螞蟻選擇的概率越大，所以螞蟻更傾向于選擇信息素濃度高且長度短的路徑。應(yīng)用：組合優(yōu)化問題、路徑規(guī)劃問題、調(diào)度問題，易陷入局部最優(yōu)7.2

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

7.2.1

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

7.2.1

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

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

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

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

7.2.1

仿動(dòng)物類啟發(fā)式算法——蝙蝠算法（BatAlgorithm）蝙蝠算法是由英國科學(xué)家Yang教授于2010年提出的一種模擬蝙蝠群體行為的啟發(fā)式優(yōu)化算法。基本思想：模擬蝙蝠在尋找食物和繁殖過程中的行為。蝙蝠在夜間通過發(fā)出超聲波信號(hào)來探測(cè)周圍環(huán)境，并根據(jù)接收到的回聲來判斷目標(biāo)的位置。發(fā)現(xiàn)目標(biāo)后，它會(huì)朝著目標(biāo)飛去，并通過調(diào)整頻率和聲音的強(qiáng)度來調(diào)整自己的飛行方向和速度。應(yīng)用：各種優(yōu)化問題，特別是連續(xù)優(yōu)化問題優(yōu)點(diǎ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)化問題的算法，也稱為光子算法。該算法模擬了光在環(huán)境中的傳播和反射過程，通過光的傳播路徑來搜索最優(yōu)解通過模擬生物體對(duì)光的感知和移動(dòng)來解決優(yōu)化問題連續(xù)優(yōu)化問題和多模態(tài)優(yōu)化問題雜草優(yōu)化算法（WeedOptimizationAlgorithm,WOA）一種基于仿生學(xué)的優(yōu)化算法通過模擬雜草的生長過程來求解優(yōu)化問題機(jī)器學(xué)習(xí)、圖像處理、電力系統(tǒng)優(yōu)化模擬植物生長算法(PlantGrowthSimulationAlgorithm,PGSA)一種以植物向光性機(jī)理（形態(tài)素濃度理論）為啟發(fā)準(zhǔn)則的智能優(yōu)化算法。通過模擬植物的生理機(jī)制和生長規(guī)律來解決問題，可以應(yīng)用于多種問題的求解函數(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)化方法。二、原理遺傳算法通過模擬自然選擇和遺傳中發(fā)生的復(fù)制、交叉和變異等現(xiàn)象，從任一初始種群出發(fā)，通過隨機(jī)選擇、交叉和變異操作，產(chǎn)生一群更適合環(huán)境的個(gè)體，使群體進(jìn)化到搜索空間中越來越好的區(qū)域，這樣一代一代不斷繁衍進(jìn)化，最后收斂到一群最適應(yīng)環(huán)境的個(gè)體，從而求得問題的優(yōu)質(zhì)解。三、優(yōu)勢(shì)在求解較為復(fù)雜的組合優(yōu)化問題時(shí)，相對(duì)一些常規(guī)的優(yōu)化算法，遺傳算法通常能夠較快地獲得較好的優(yōu)化結(jié)果。四、應(yīng)用車間調(diào)度、機(jī)器仿真、信號(hào)處理

7.3

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

7.3.1

遺傳算法的原理四、常用術(shù)語算法名稱概念染色體（Chromosome）染色體又可稱為基因型個(gè)體（Individuals），一定數(shù)量的個(gè)體組成了群體（Population），群體中個(gè)體的數(shù)量叫作群體大小（Populationsize）。位串（BitString）個(gè)體的表示形式，對(duì)應(yīng)于遺傳學(xué)中的染色體?；颍℅ene）基因是染色體中的元素，用于表示個(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ì)問題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)。這個(gè)函數(shù)通常會(huì)被用來計(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ù)具體問題計(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是一種通用的編程語言，擁有豐富的科學(xué)計(jì)算庫，如NumPy、SciPy和DEAP等，可以用于實(shí)現(xiàn)遺傳算法。Java是一種廣泛使用的編程語言，它提供了強(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粒子群算法的原理一、粒子群算法的靈感來源

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

每只鳥兒就是一個(gè)粒子，食物的位置也就是問題的最優(yōu)解，鳥兒與食物的距離也即當(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è)迭代的過程，需要多次迭代才能獲取到理想的最優(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。迭代開始的時(shí)候以及迭代的過程中，均需要對(duì)粒子的位置進(jìn)行隨機(jī)分布，需要設(shè)置隨機(jī)分布的上下限，不然隨機(jī)分布偏離得太遠(yuǎn)，會(huì)嚴(yán)重影響優(yōu)化結(jié)果。速度的上下限：Vmin，Vmax。迭代過程中，速度也具有一定的隨機(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)，問題描述：求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

物流配送中心案例分析

一、問題：

一共有五個(gè)配送中心候選節(jié)點(diǎn)，其建設(shè)成本和坐標(biāo)如表7-1所示。供應(yīng)點(diǎn)有13個(gè)，其坐標(biāo)和運(yùn)輸量如表7-2所示，通過遺傳算法分析配送中心可覆蓋的供應(yīng)點(diǎn)。配送中心候選節(jié)點(diǎn)建設(shè)成本（萬元）坐標(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