人工智能第12章群智能課件

1、人工智能第十二章 群智能第1頁，共73頁。12.1 群智能概述12.2 蟻群算法12.3 粒子群優(yōu)化算法12.4 其他群智能優(yōu)化算法第2頁，共73頁。群智能（Swarm Intelligence，SI）優(yōu)化算法通過模擬自然界中的昆蟲、鳥群、魚群等“社會(huì)性”生物群體的行為特征，利用群體性生物能夠不斷學(xué)習(xí)自身經(jīng)驗(yàn)與其他個(gè)體經(jīng)驗(yàn)的特性，在尋優(yōu)過程中不斷獲取和積累尋優(yōu)空間的知識(shí)，自適應(yīng)地進(jìn)行搜索尋優(yōu)，從而得到最優(yōu)解或準(zhǔn)有解。群智能優(yōu)化算法作為一種新興的演化計(jì)算技術(shù)，具有較強(qiáng)的自學(xué)習(xí)性、自適應(yīng)性、自組織性等智能特征，算法結(jié)構(gòu)簡單、收斂速度快、全局收斂性好，在旅行商問題、圖著色問題、車間調(diào)度問題、數(shù)據(jù)聚類

2、問題等領(lǐng)域得到廣泛的應(yīng)用，與進(jìn)化算法和人工神經(jīng)網(wǎng)絡(luò)并稱為人工智能領(lǐng)域的三駕馬車。12.1 群智能概述第3頁，共73頁。自然界中的群體生物，具有驚人的完成復(fù)雜行為的能力，群智能優(yōu)化算法則是國內(nèi)外研究學(xué)者受到群體生物的社會(huì)行為啟發(fā)而提出。其中提出時(shí)間最早、應(yīng)用最為廣泛的群智能優(yōu)化算法主要是模擬螞蟻覓食行為的蟻群算法（Ant Colony Optimization，ACO）和模擬鳥類覓食行為的粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）。 12.1.1 群智能優(yōu)化算法定義鳥群通過協(xié)作進(jìn)行捕食房間偏僻角落里的蛋糕總會(huì)先被螞蟻發(fā)現(xiàn)魚聚集成群可以有效的逃避捕食者第4頁，

3、共73頁。群智能優(yōu)化算法主要源于對(duì)自然界中群體生物覓食等行為的模擬，每個(gè)具有經(jīng)驗(yàn)和智慧的個(gè)體通過相互作用機(jī)制形成強(qiáng)大的群體智慧來解決復(fù)雜問題。其主要算法流程如下。將尋優(yōu)過程模擬成生物個(gè)體的覓食等行為過程，用搜索空間中的點(diǎn)模擬自然界中的生物個(gè)體；將求解問題的目標(biāo)函數(shù)量化為生物個(gè)體對(duì)環(huán)境的適應(yīng)能力；將生物個(gè)體覓食等行為過程類比為傳統(tǒng)尋優(yōu)方法用較優(yōu)的可行解取代較差可行解的迭代過程，從而演化成為一種具有“生成+檢驗(yàn)”特征的迭代搜索算法，是一種求解極值問題的自適應(yīng)人工智能技術(shù)。群智能主要算法流程第5頁，共73頁。12.1.2 群智能優(yōu)化算法原理自然界中的昆蟲、鳥群、魚群等一些生物具有群體性的行為特征，計(jì)

4、算機(jī)圖形學(xué)家雷諾茲（C. Reynolds）認(rèn)為以群落形式生存的生物在覓食時(shí)一般遵循以下三個(gè)規(guī)則。1）分隔規(guī)則：盡可能避免與周邊生物個(gè)體距離太近，造成擁擠；2）對(duì)準(zhǔn)規(guī)則：盡可能與周邊生物個(gè)體的平均移動(dòng)方向保持一致，向目標(biāo)方向移動(dòng)；3）內(nèi)聚規(guī)則：盡可能向周邊生物個(gè)體的中心移動(dòng)。第6頁，共73頁。上述規(guī)則中，分隔規(guī)則體現(xiàn)出生物的個(gè)體信息特征，即個(gè)體根據(jù)自身當(dāng)前狀態(tài)進(jìn)行決策；對(duì)準(zhǔn)規(guī)則和內(nèi)聚規(guī)則體現(xiàn)生物的群體信息特征，即個(gè)體根據(jù)群體狀態(tài)進(jìn)行決策。除個(gè)體信息與群體信息特征，生物行為還具有適應(yīng)性、盲目性、自治性、突現(xiàn)性、并行性等特征。群智能優(yōu)化算法就是利用雷諾茲模型模擬整個(gè)生物群體的行為，算法在迭代過程中

5、不斷利用個(gè)體最優(yōu)值與群體最優(yōu)值進(jìn)行尋優(yōu)搜索，完成個(gè)體信息與群體信息的交互。在群智能優(yōu)化算法中，個(gè)體最優(yōu)值的隨機(jī)性使得算法搜索方向具有多樣性，能夠避免算法收斂過早陷入局部最優(yōu)；群體最優(yōu)值能夠把握全局尋優(yōu)方向，提高算法的全局尋優(yōu)能力，及時(shí)收斂。第7頁，共73頁。12.1.3 群智能優(yōu)化算法特點(diǎn)群智能優(yōu)化算法主要用來求解一些復(fù)雜的、難以用傳統(tǒng)算法解決的問題。與傳統(tǒng)優(yōu)化算法不同，群智能優(yōu)化算法是一種概率搜索算法，具有以下幾個(gè)特點(diǎn)。具有較強(qiáng)的魯棒性，群體中相互作用的個(gè)體是分布式的，沒有直接的控制中心，不會(huì)因少數(shù)個(gè)體出現(xiàn)故障而影響對(duì)問題的求解。結(jié)構(gòu)簡單，易于實(shí)現(xiàn)，每個(gè)個(gè)體只能感知局部信息，個(gè)體遵循的規(guī)則簡

6、單。易于擴(kuò)充，開銷較少。具有自組織性，群體表現(xiàn)出的智能復(fù)雜行為由簡單個(gè)體交互而來。第8頁，共73頁。12.2 蟻群算法蟻群算法，又稱為螞蟻算法，1992年多里戈（M. Dorigo）受自然界中真實(shí)蟻群的群體覓食行為啟發(fā)提出，是最早的群智能優(yōu)化算法，起初被用來求解旅行商（Total Suspended Particulate，TSP）問題。第9頁，共73頁。12.2.1 蟻群算法概述螞蟻是一種社會(huì)性生物，在尋找食物時(shí)，會(huì)在經(jīng)過的路徑上釋放一種信息素，一定范圍內(nèi)的螞蟻能夠感覺到這種信息素，并移動(dòng)到信息素濃度高的方向，因此蟻群通過螞蟻個(gè)體的交互能夠表現(xiàn)出復(fù)雜的行為特征。蟻群的群體性行為能夠看作是一種

7、正反饋現(xiàn)象，因此蟻群行為又可以被理解成增強(qiáng)型學(xué)習(xí)系統(tǒng)（Reinforcement Learning System）。第10頁，共73頁。12.2.2 蟻群算法的數(shù)學(xué)模型蟻群優(yōu)化算法的第一個(gè)應(yīng)用是著名的旅行商問題。旅行商問題闡明 蟻群系統(tǒng)模型旅行商問題（Traveling Salesman Problem，TSP）：在尋求單一旅行者由起點(diǎn)出發(fā)，通過所有給定的需求點(diǎn)之后，最后再回到原點(diǎn)的最小路徑成本。螞蟻搜索食物的過程 ：通過個(gè)體之間的信息交流與相互協(xié)作最終找到從蟻穴到食物源的最短路徑。第11頁，共73頁。符號(hào)表示 m 是蟻群中螞蟻的數(shù)量； 表示結(jié)點(diǎn)i（城市）和結(jié)點(diǎn)j（城市）之間的距離； 表示t時(shí)

8、刻在ij連線上殘留的信息素，初始時(shí)刻，各條路徑上 的信息素相等，螞蟻k在運(yùn)動(dòng)過程中，根據(jù)各條路徑上的信息 素決定轉(zhuǎn)移方向。 稱為啟發(fā)信息函數(shù)，等于距離的倒數(shù)； 表示在t時(shí)刻螞蟻 k 選擇從結(jié)點(diǎn) （城市）i 轉(zhuǎn)移到結(jié)點(diǎn)（城 市） j的概率，也稱為隨機(jī)比例規(guī)則。第12頁，共73頁。信息素 共同決定局部啟發(fā)信息 表示螞蟻k下一步允許選擇的城市 記錄螞蟻k當(dāng)前所走過的城市 是信息素啟發(fā)式因子，表示軌跡的相對(duì)重要性 表示期望啟發(fā)式因子，表示能見度的相對(duì)重要程度第13頁，共73頁。 值越大該螞蟻越傾向于選擇其它螞蟻經(jīng)過的路徑，該狀態(tài)轉(zhuǎn)移概率越接近于貪婪規(guī)則。當(dāng) = 0時(shí)不再考慮信息素水平，算法就成為有多重

9、起點(diǎn)的隨機(jī)貪婪算法。當(dāng) = 0時(shí)算法就成為純粹的正反饋的啟發(fā)式算法。第14頁，共73頁。1-表示信息素殘留因子，常數(shù) 為信息素?fù)]發(fā)因子， 表示路徑上信息素的損耗程度； 的大小關(guān)系到算法的全局搜索能力和收斂速度。螞蟻完成一次循環(huán)，各路徑上信息素濃度揮發(fā)規(guī)則為： 蟻群的信息素濃度更新規(guī)則為： 根據(jù)信息素更新策略不同，多里戈提出了3種基本蟻群算法模型。第15頁，共73頁。1、蟻周系統(tǒng)（Ant-cycle System）單只螞蟻所訪問路徑上的信息素濃度更新規(guī)則為： Q 為常數(shù)Lk 為優(yōu)化問題的目標(biāo)函數(shù)值，表示第k只螞蟻在本次循環(huán)中所走路徑的長度。第16頁，共73頁。2、蟻量系統(tǒng)（Ant-quantit

10、y System） 3、 蟻密系統(tǒng)（Ant-density System） 第17頁，共73頁。蟻圈系統(tǒng)利用的是全局信息 ，即螞蟻完成一個(gè)循環(huán)后，更新所有路徑上的信息。蟻量系統(tǒng)利用的是局部信息 ，即螞蟻每走一步都要更新殘留信息素的濃度。蟻密系統(tǒng)利用的是局部信息 ，即螞蟻每走一步都要更新殘留信息素的濃度。三種模型比較效果最好，通常作為蟻群優(yōu)化算法的基本模型。第18頁，共73頁。設(shè)置參數(shù),初始化信息素濃度While（不滿足條件時(shí)）dofor蟻群中的每只螞蟻for每個(gè)解構(gòu)造步驟(直到構(gòu)造出完整的可行解)1）螞蟻按照信息素及啟發(fā)因子構(gòu)造下一步問題的解；2）進(jìn)行信息素局部更新。(可選)end foren

11、d for1）以已獲得的解為起點(diǎn)進(jìn)行局部搜索；(可選)2）根據(jù)已獲得的解的質(zhì)量進(jìn)行全局信息素更新。end Whileend 蟻群算法流程第19頁，共73頁。12.2.3 蟻群算法的改進(jìn)為提高蟻群算法性能，諸多研究學(xué)者對(duì)蟻群算法進(jìn)行了改進(jìn)，其中主要包括螞蟻-Q系統(tǒng)（Ant-Q System）、蟻群系統(tǒng)（Ant Colony System, ACS）、最大-最小螞蟻系統(tǒng)（Max-Min Ant System，MMAS）、自適應(yīng)蟻群算法。第20頁，共73頁。螞蟻-Q系統(tǒng)1995年，意大利學(xué)者盧卡（M. Luca）、甘巴德拉（L. M. Gambardella）、多里戈在ACO算法的基礎(chǔ)上，進(jìn)行了創(chuàng)新

12、，提出了螞蟻-Q系統(tǒng)。在解構(gòu)造過程中提出了偽隨機(jī)比例狀態(tài)遷移規(guī)則；信息素局部更新規(guī)則引入強(qiáng)化學(xué)習(xí)中的Q學(xué)習(xí)機(jī)制；在信息素的全局更新中采用了精英策略。第21頁，共73頁。其概率分布計(jì)算、AQ值更新規(guī)則分別為：其中：第22頁，共73頁。1996年，甘巴德拉和多里戈又在Ant-Q算法的基礎(chǔ)上提出了蟻群系統(tǒng)，蟻群系統(tǒng)是Ant-Q算法的一種特例。其主要?jiǎng)?chuàng)新如下：蟻群系統(tǒng)相比ACO算法，蟻群系統(tǒng)中的螞蟻在下一步移動(dòng)之前，增加一次隨機(jī)實(shí)驗(yàn)，將選擇情況分成“利用已知信息”和“探索”兩類。提出了精英策略（Elitist Strategy）。設(shè)置精英螞蟻數(shù)目的最優(yōu)范圍：若低于該范圍，增加精英螞蟻數(shù)目，以便能夠較快

13、的發(fā)現(xiàn)最優(yōu)路徑；若高于該范圍，精英螞蟻會(huì)在搜索初期迫使尋優(yōu)過程停留在次優(yōu)解附近，降低算法性能。第23頁，共73頁。其中狀態(tài)轉(zhuǎn)移規(guī)則為： 其中，Sk表示螞蟻k所選中的下一個(gè)結(jié)點(diǎn)；q是一個(gè)隨機(jī)變量，為設(shè)定閾值。第24頁，共73頁。1997年，德國學(xué)者施蒂茨勒（T. Stutzle）提出了最大-最小螞蟻系統(tǒng)。其主要?jiǎng)?chuàng)新如下：最大-最小螞蟻系統(tǒng)為了避免算法收斂過早，陷入局部最優(yōu)，將各條路徑的信息素濃度限制到min,max區(qū)間范圍內(nèi)。采用了平滑機(jī)制，路徑上信息素濃度的增加與max和當(dāng)前濃度(i, j)之差成正比，即其中，0 1。第25頁，共73頁。自適應(yīng)蟻群算法自適應(yīng)蟻群算法能夠根據(jù)搜索結(jié)果進(jìn)行信息素濃

14、度更新，如果算法陷入局部最優(yōu)，自適應(yīng)調(diào)整陷入局部最優(yōu)的螞蟻所經(jīng)過路徑中的信息素和信息素強(qiáng)度Q，使得算法能夠較快的跳出局部最優(yōu)，避免算法“早熟”，同時(shí)自適應(yīng)蟻群算法限定所有路徑上的信息素范圍，有利于提高算法全局搜索能力。第26頁，共73頁。蟻群算法最早被用來解決旅行商問題，隨后陸續(xù)被用于解決圖著色問題、二次分配問題、大規(guī)模集成電路設(shè)計(jì)、通訊網(wǎng)絡(luò)中的路由問題以及負(fù)載平衡問題、車輛調(diào)度問題、數(shù)據(jù)聚類問題、武器攻擊目標(biāo)分配和優(yōu)化問題、區(qū)域性無線電頻率自動(dòng)分配問題等。12.2.3 蟻群算法的應(yīng)用示例旅行商問題描述如下：假設(shè)為一個(gè)加權(quán)圖，為頂點(diǎn)集，為邊集。為頂點(diǎn)i到頂點(diǎn)j的距離，其中且，同時(shí)。 第27頁，

15、共73頁。經(jīng)典TSP的數(shù)學(xué)模型為： 是圖s的頂點(diǎn)數(shù)。第28頁，共73頁。實(shí)際問題可以描述為：一行人要去27個(gè)城市旅行，其中城市坐標(biāo)如表所示，該人從一城市出發(fā)，使用蟻群算法計(jì)算，應(yīng)如何選擇行進(jìn)路線，以使總的行程最短。城市123456789行值304639177 712 488326238196312列值312315244399535556229104790城市101112131415161718行值386107562788381332715918161列值570970756491676695678179370城市192021222324252627行值7806763292634295073944

16、39935列值212578838931908367643201240第29頁，共73頁。應(yīng)用基本蟻群算法進(jìn)行建模，可計(jì)算得出行程最短路徑為：城市19城市4城市2城市24城市26城市8城市7城市3城市18城市1城市5城市10城市6城市25城市14城市15城市9城市21城市22城市11城市23城市12城市16城市20城市13城市27城市17。第30頁，共73頁。12.3 粒子群優(yōu)化算法粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）源于對(duì)鳥群社會(huì)系統(tǒng)的研究，由美國普渡大學(xué)的埃伯哈特（J. Eberhart）和肯尼迪（R. Kennedy）于1995年提出。其核心思想

17、是利用個(gè)體的信息共享促使群體在問題解空間從無序進(jìn)行有序演化，最終得到問題的最優(yōu)解。第31頁，共73頁?？捎萌缦陆?jīng)典描述直觀理解粒子群優(yōu)化算法：設(shè)想這么一個(gè)場景：一群鳥在尋找食物，在遠(yuǎn)處有一片玉米地，所有的鳥都不知道玉米地到底在哪里，但是它們知道自己當(dāng)前的位置距離玉米地有多遠(yuǎn)。那么找到玉米地的最優(yōu)策略就是搜尋目前距離玉米地最近的鳥群的所在區(qū)域。粒子群優(yōu)化算法就是從鳥群食物的覓食行為中得到啟示，從而構(gòu)建形成的一種優(yōu)化方法。12.3.1 粒子群優(yōu)化算法基本思想第32頁，共73頁。粒子群優(yōu)化算法將每個(gè)問題的解類比為搜索空間中的一只鳥，稱之為“粒子”，問題的最優(yōu)解對(duì)應(yīng)為鳥群要尋找的“玉米地”。每個(gè)粒子設(shè)

18、定一個(gè)初始位置和速度向量，根據(jù)目標(biāo)函數(shù)計(jì)算當(dāng)前所在位置的適應(yīng)度值（Fitness Value），可以將其理解為距離“玉米地”的距離。粒子在迭代過程中，根據(jù)自身的“經(jīng)驗(yàn)”和群體中的最優(yōu)粒子的“經(jīng)驗(yàn)”進(jìn)行學(xué)習(xí)，從而確定下一次迭代時(shí)飛行的方向和速度。通過逐步迭代，整個(gè)群體逐步趨于最優(yōu)解。第33頁，共73頁。在n 維連續(xù)搜索空間中，對(duì)粒子群中的第i (i=1, 2, , m)個(gè)粒子進(jìn)行定義： ：表示搜索空間中粒子的當(dāng)前位置。 ：表示該粒子至今所獲得的具有最優(yōu)適應(yīng)度 的位置。 ：表示該粒子的搜索方向。12.3.2 粒子群優(yōu)化算法基本框架 ：表示每個(gè)粒子經(jīng)歷過的最優(yōu)位置（Pbest）。 ：群體經(jīng)歷過的最優(yōu)

19、位置（Gbest）。第34頁，共73頁。c1 ，c2 是速度因子，均為非負(fù)值；r1 和 r2 為0, 1 范圍內(nèi)的隨機(jī)數(shù)。早期的粒子群優(yōu)化算法速度和位置向量更新公式如下：；第35頁，共73頁。由于 的更新過于隨機(jī)，使得粒子群優(yōu)化算法具有較強(qiáng)的全局尋優(yōu)能力，但是局部尋優(yōu)能力較差。為保證算法具有全局尋優(yōu)能力的同時(shí)，提高其局部尋優(yōu)能力。1998年Shi Yuhui和埃伯哈特在算法中引入慣性權(quán)重（Inertia Weight）系數(shù)w，修正了速度向量更新公式：第36頁，共73頁。參數(shù)w取值范圍為0,1，與物理中的慣性相似，w反映了粒子歷史運(yùn)動(dòng)狀態(tài)對(duì)當(dāng)前運(yùn)動(dòng)的影響。如果w取值較小，歷史運(yùn)動(dòng)狀態(tài)對(duì)當(dāng)前運(yùn)動(dòng)影

20、響較小，粒子的速度能夠很快的改變；相反，如果w取值較大，雖然提高了搜索空間范圍，但是粒子運(yùn)動(dòng)方向不易改變，難于向較優(yōu)位置收斂。因此w設(shè)置較大時(shí)，能夠提高算法全局尋優(yōu)能力，w設(shè)置較小時(shí)，又能夠加快算法局部尋優(yōu)。實(shí)際工程應(yīng)用中w可采取自適應(yīng)取值方式。第37頁，共73頁。粒子群優(yōu)化算法流程procedure PSO for 每個(gè)粒子i 初始化每個(gè)粒子i，隨機(jī)設(shè)置每個(gè)粒子的初始位置和速度 計(jì)算每個(gè)粒子i的目標(biāo)函數(shù)，Gbest = end for Gbest = minPbesti while not stop for i=1 to m 更新粒子i的速度和位置 if fit() fit(Pbesti)

21、Pbesti = if fit(Pbesti) fit(Gbest) Gbest = Pbesti; end for end while print Gbestend procedure第38頁，共73頁。12.3.3 粒子群優(yōu)化算法參數(shù)分析與改進(jìn)粒子群優(yōu)化算法中主要參數(shù)如下：種群規(guī)模m種群規(guī)模通常設(shè)置為20-40，可根據(jù)不同問題進(jìn)行自定義。慣性權(quán)重w慣性權(quán)重能夠保持粒子運(yùn)動(dòng)慣性，擴(kuò)展搜索空間，搜索新的區(qū)域。最大速度Vmax最大速度Vmax決定當(dāng)前位置與最優(yōu)位置之間的區(qū)域的精度。若Vmax過大，粒子可能跨過最優(yōu)位置；若Vmax過小，粒子無法在局部最優(yōu)值之外進(jìn)行足夠的探索，易陷入局部最優(yōu)。限制最

22、大速度可以有效防止計(jì)算溢出、決定問題空間搜索的粒度。迭代次數(shù)Gmax迭代次數(shù)Gmax根據(jù)工程應(yīng)用具體問題決定。第39頁，共73頁。學(xué)習(xí)因子c1、c2學(xué)習(xí)因子c1、c2分別控制個(gè)體認(rèn)知分量和群體社會(huì)分量相對(duì)貢獻(xiàn)的學(xué)習(xí)率。當(dāng)c1=0、c2=0時(shí)，只有第1部分，粒子保持當(dāng)前速度飛行，直到達(dá)邊界，只能搜索有限的區(qū)域，無法找到最優(yōu)解。w=0時(shí)，沒有第1部分，速度沒有記憶性，只取決于粒子當(dāng)前位置和其歷史最優(yōu)位置。當(dāng)c1=0時(shí)，沒有第2部分，粒子沒有認(rèn)知能力，只有“社會(huì)模型”。在粒子的相互作用下，有能力達(dá)到新的搜索空間。但是復(fù)雜問題容易陷入局部最優(yōu)。當(dāng)c2=0時(shí)，沒有第3部分，粒子間沒有社會(huì)共享信息，只有“

23、認(rèn)知模型”。個(gè)體間沒有交互，群體中所有個(gè)體獨(dú)立搜索，因此無法得到最優(yōu)解。第40頁，共73頁。粒子群優(yōu)化算法的改進(jìn)粒子群優(yōu)化算法具有收斂速度快的優(yōu)點(diǎn)，但是在算法運(yùn)行初期，算法存在精度較低、易發(fā)散等缺點(diǎn)。因此國內(nèi)外諸多研究人員致力于提高粒子群優(yōu)化算法的性能，現(xiàn)階段主要側(cè)重理論研究改進(jìn)、拓?fù)浣Y(jié)構(gòu)改進(jìn)、混合改進(jìn)算法、參數(shù)優(yōu)化等方面。第41頁，共73頁。粒子群優(yōu)化算法自提出至今，被廣泛的應(yīng)用于神經(jīng)網(wǎng)絡(luò)訓(xùn)練、機(jī)器人、經(jīng)濟(jì)、通信、醫(yī)學(xué)等多種領(lǐng)域。本節(jié)示例為粒子群優(yōu)化算法在車輛路徑問題（Vehicle Routing Problem，VRP）中的應(yīng)用。12.3.4 粒子群優(yōu)化算法的應(yīng)用示例第42頁，共73頁。

24、假定配送中心最多可以用 輛車對(duì) 個(gè)客戶進(jìn)行運(yùn)輸配送， 表示倉庫。每個(gè)車輛載重為 ，每個(gè)客戶的需求為 ，客戶i到客戶 j 的運(yùn)輸成本為 cij（可以是距離，時(shí)間，費(fèi)用等）。定義如下變量：第43頁，共73頁。1、建立車輛路徑問題的數(shù)學(xué)模型如下：每輛車的能力約束：保證每個(gè)客戶都被服務(wù)：保證客戶是僅被一輛車訪問：保證客戶是僅被一輛車訪問：消除子回路：表示變量的取值范圍：表示變量的取值范圍：第44頁，共73頁。2、編碼與初始種群 對(duì)這類組合優(yōu)化問題，編碼方式、初始解的設(shè)置對(duì)問題的求解都有很大的影響。 本問題采用常用的自然數(shù)編碼方式。 對(duì)于K輛車和L個(gè)客戶的問題，用從1到L的自然數(shù)隨機(jī)排列來產(chǎn)生一組解 。

25、然后分別用節(jié)約法或者最近插入法構(gòu)造初始解。第45頁，共73頁。粒子群優(yōu)化算法的各個(gè)參數(shù)設(shè)置如下：種群規(guī)模p=50 ，迭代次數(shù)Gmax=1000，w的初始值為1，隨著迭代的進(jìn)行，線性減小到0，c1=c2=1.4 ， 。優(yōu)化結(jié)果及其比較實(shí)例PSOGAbestdev(%)bestdev(%)A-n32-k58295.738184.34A-n33-k57056.656741.97A-n34-k58326.948215.52A-n39-k68726.088665.35A-n44-k610168.499915.76A-n46-k79776.899574.7A-n54-k712053.2612033.08A

26、-n60-k914769.0114104.13A-n69-k912751012437.24A-n80-k10199212.9818716.12第46頁，共73頁。12.4 其他群智能優(yōu)化算法隨著蟻群算法、粒子群優(yōu)化算法的廣泛應(yīng)用，各類群智能優(yōu)化算法蜂擁而至。其中較為典型的幾種包括人工魚群算法（Artificial Fish Swarm Algorithm，AFSA）、細(xì)菌覓食算法（Bacterial Foraging Optimization，BFO）、蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）、果蠅優(yōu)化算法（Fruit Fly Optimizatio

27、n Algorithm，F(xiàn)OA）等。群智能優(yōu)化1992年 1995年2002年2003年2005年2007年2011年2014年蟻群算法果蠅優(yōu)化算法狼群算法鴿群優(yōu)化算法人工魚群算法第47頁，共73頁。人工魚群算法（Artificial Fish Swarm Algorithm，AFSA），由李曉磊博士于2001年提出，是一種源于魚群自治行為的群智能優(yōu)化算法，通過構(gòu)造人工魚來模仿魚群的覓食、聚群、追尾和隨機(jī)行為，從而實(shí)現(xiàn)尋優(yōu)，具有較快的收斂速度，可以用于解決有實(shí)時(shí)性要求的問題。12.4.1 人工魚群算法人工魚的結(jié)構(gòu)圖第48頁，共73頁。假設(shè)人工魚當(dāng)前狀態(tài)為X，Visual代表其視野范圍，Xv表示

28、某時(shí)刻其視點(diǎn)所在位置。若該位置的狀態(tài)優(yōu)于當(dāng)前狀態(tài)，向當(dāng)前位置方向前進(jìn)一步到達(dá)狀態(tài)Xnext；若狀態(tài)Xv比當(dāng)前狀態(tài)差，繼續(xù)巡視視野內(nèi)的其他位置。巡視的次數(shù)越多，對(duì)視野范圍內(nèi)的信息了解越全面，從而能夠全方位立體感知周圍的環(huán)境，有助于對(duì)目標(biāo)問題做出相應(yīng)的判斷和決策。人工魚群算法基本概念人工魚視覺的概念第49頁，共73頁。其中，狀態(tài) ，狀態(tài) ，則該過程可以表示為：式中，rand函數(shù)用來產(chǎn)生0,1之間的隨機(jī)數(shù)；Step為移動(dòng)步長。第50頁，共73頁。人工魚群算法采用面向?qū)ο蟮募夹g(shù)重構(gòu)人工魚的模型，將人工魚封裝成變量和函數(shù)兩部分。其中變量部分包括人工魚的總數(shù)N，人工魚個(gè)體的狀態(tài)為待尋優(yōu)的變量），人工魚移動(dòng)

29、的最大步長Step，人工魚的視野Visual，嘗試次數(shù)Try_number，擁擠度因子，人工魚個(gè)體i,j之間的距離 。函數(shù)部分包括人工魚當(dāng)前所處位置的食物濃度 人工魚的各種行為函數(shù)（覓食行為Prey()、聚群行為Swarm()、追尾行為Follow()、隨機(jī)行為Move()以及行為評(píng)價(jià)函數(shù)Evaluate()）。通過封裝，人工魚的狀態(tài)能夠被其他同伴感知。（Y為目標(biāo)函數(shù)值）第51頁，共73頁。覓食行為聚群行為追尾行為隨機(jī)行為人工魚的四種基本行為算法描述由于魚類不具備復(fù)雜邏輯推理能力和綜合判斷能力，它們只能通過簡單行為達(dá)到目的。因此通過模擬魚類的四種行為覓食行為、聚群行為、追尾行為和隨機(jī)行為來使魚

30、類活動(dòng)在周圍的環(huán)境。第52頁，共73頁。覓食行為是人工魚趨向食物源的一種基本行為，一般通過視覺或味覺感知水中的食物數(shù)量或濃度，進(jìn)行趨向選擇。行為描述：設(shè)人工魚i的當(dāng)前狀態(tài)為Xi，在其感知范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj，則其中，rand是一個(gè)0,1之間的隨機(jī)數(shù)，在求解問題極大值時(shí)，若YiYj，則向Xj方向前進(jìn)一步：否則，再次隨機(jī)選擇狀態(tài)Xj，判斷是否滿足前進(jìn)條件，若反復(fù)嘗試Try_number次后仍不滿足前進(jìn)條件，則隨機(jī)移動(dòng)一步：覓食行為第53頁，共73頁。這是魚群生存和躲避危害的一種生活習(xí)性。在魚群算法中，一般規(guī)定兩條，一是盡量向鄰近伙伴的中心移動(dòng)，二是避免過分擁擠。行為描述：設(shè)人工魚當(dāng)前狀態(tài)為X

31、i，當(dāng)前搜索范圍內(nèi)dijVisual，伙伴數(shù)目為 ，中心位置為Xo。若 ，表明伙伴中心食物較多且不存在過分擁擠，則向伙伴中心位置方向前進(jìn)一步，即否則，執(zhí)行覓食行為。聚集行為第54頁，共73頁。魚群在游動(dòng)過程中，當(dāng)其中一條魚或幾條魚發(fā)現(xiàn)食物時(shí)，其鄰近的伙伴會(huì)尾隨其快速到達(dá)食物點(diǎn)。行為描述：設(shè)人工魚i當(dāng)前狀態(tài)為Xi，當(dāng)前搜索范圍內(nèi)dij0表示細(xì)菌的游動(dòng)步長單位； 表示細(xì)菌翻轉(zhuǎn)運(yùn)動(dòng)后隨機(jī)改變的角度。 第62頁，共73頁。細(xì)菌覓食算法具體步驟算法參數(shù)初始化，包括細(xì)菌個(gè)數(shù)S、趨化操作次數(shù)Nc、最大游動(dòng)步數(shù)Ns、繁殖操作次數(shù)Nre、驅(qū)散操作次數(shù)Ned以及細(xì)菌個(gè)體驅(qū)散概率P、隨機(jī)生成單個(gè)細(xì)菌的位置。種群位置

32、初始化，計(jì)算每個(gè)細(xì)菌初始適應(yīng)度值，j=0，k=0，l=0。驅(qū)散操作循環(huán)l=l+1。繁殖操作循環(huán)k=k+1。趨化操作循環(huán)i=i+1，每個(gè)細(xì)菌個(gè)體進(jìn)行趨化操作。若jNc，則回到。繁殖操作，適應(yīng)度值排在前S/2的個(gè)體進(jìn)行繁殖，替換適應(yīng)度值較小的另一半細(xì)菌。若kNre，則轉(zhuǎn)到。驅(qū)散操作。當(dāng)細(xì)菌i滿足驅(qū)散概率，隨機(jī)生成新的細(xì)菌替換細(xì)菌i。若lNed，則轉(zhuǎn)到；否則，算法結(jié)束，輸出問題最優(yōu)結(jié)果。第63頁，共73頁。12.4.3 混合蛙跳算法混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA），由尤瑟夫（M. M. Eusuff）和蘭西（K. E. Lansey）于2003

33、年提出，是一種全新的后啟發(fā)式群體智能算法，結(jié)合了模因演算MA（Memetic Algorithm）和粒子群優(yōu)化算法2種算法的優(yōu)點(diǎn)，具有高效的計(jì)算效率和良好的全局尋優(yōu)能力。第64頁，共73頁?；旌贤芴惴ɑ靖拍罨旌贤芴惴梢悦枋鰹椋涸谝黄臻g區(qū)域內(nèi)生活著一群青蛙，為了尋找食物較多的地方，蛙群首先按照一定的規(guī)則確定每只青蛙的初始位置。隨后，每只青蛙利用個(gè)體信息在初始位置附近搜索食物更多的區(qū)域，跳躍完成個(gè)體位置更新。主要搜索規(guī)則為，蛙群利用青蛙的自組織性行為，組成多個(gè)子種群，子種群中的青蛙個(gè)數(shù)基本相同，由子種群中的局部精英個(gè)體帶領(lǐng)其他個(gè)體進(jìn)行組團(tuán)搜索。子種群完成一次搜索后，蛙群中的所有個(gè)體進(jìn)行重新混合分組，繼續(xù)執(zhí)行組團(tuán)。組團(tuán)搜索與蛙群混合迭代進(jìn)行，直至到達(dá)食物最豐富的位置。第65頁，共73頁?；旌贤芴惴ɑ玖鞒袒旌贤芴惴ㄊ紫葟目尚杏蛑须S機(jī)產(chǎn)生一組初始解，每個(gè)解對(duì)應(yīng)一只青蛙，形成初始種群；根據(jù)目標(biāo)函數(shù)，計(jì)算每個(gè)青蛙的適應(yīng)度值，進(jìn)行由大到小排列；以一定的規(guī)則將蛙群劃分為一定數(shù)量的子種群，每個(gè)子種群進(jìn)行局部搜索，子種群內(nèi)最差的青蛙根據(jù)更新策略向局部最優(yōu)位置靠近；子種群完成一次局部搜索后，