基于蟻群算法的博物館人流動線設(shè)計(jì)研究

賀嘉琦 高子期

摘? 要：為優(yōu)化博物館人流動線設(shè)計(jì)的合理性，提高游客在博物館中的參觀體驗(yàn)感，文章提出通過蟻群算法對博物館的人流動線設(shè)計(jì)進(jìn)行研究。以秦始皇兵馬俑博物館為例，用柵格圖法對秦始皇兵馬俑博物館的人流動線進(jìn)行相關(guān)實(shí)驗(yàn)研究。經(jīng)過三種仿真模擬實(shí)驗(yàn)，模擬五個(gè)展館在特殊情況下多種開館情況。通過更新信息素和增加迭代次數(shù)來判斷人流動線的長短，得出秦始皇兵馬俑博物館人流動線的最短路徑和參觀順序。仿真實(shí)驗(yàn)證明，蟻群算法可用于秦始皇兵馬俑博物館三種參觀需求的人流動線規(guī)劃設(shè)計(jì)。蟻群算法在博物館的人流動線設(shè)計(jì)中是有效的，可以得出一種最優(yōu)的參觀人流動線設(shè)計(jì)規(guī)劃。

關(guān)鍵詞：博物館;蟻群算法;人流動線設(shè)計(jì);參觀順序;最短路徑

中圖分類號：TP18;TU242.5? ? ? ? ?文獻(xiàn)標(biāo)識碼：A文章編號： 2096-4706（2021）22-0079-04

Abstract： In order to optimize the rationality of the design of people flow line in the museum to improve visitors’ visiting experience in the museum. This paper proposes to study the design of people flow line of museum through ant colony algorithm. Taking the Terracotta Warriors and Horses Museum of Qin Shihuang as an example， this paper makes an experimental study on the people flow line of the Terracotta Warriors and Horses Museum of Qin Shihuang by using the grid method. After three kinds of simulation experiments， simulate the opening of five pavilions under special circumstances. By updating the pheromone and increasing the number of iterations to judge the length of the people flow line， the shortest path and visiting order of the people flow line in the Terracotta Warriors and Horses Museum of Qin Shihuang are obtained. Simulation results show that the ant colony algorithm can be used for the planning and design of people flow lines for three visiting needs of the Terracotta Warriors and Horses Museum of Qin Shihuang. Ant colony algorithm is effective in the design of people flow line of Museum， and an optimal design plan of visitor flow line can be obtained.

Keywords： museum; ant colony algorithm; people flow line design; visiting order; shortest path

0? 引? 言

隨著中國經(jīng)濟(jì)生活水平的不斷提高，人們對博物館的需求越來越成為日常生活中不可或缺的一部分。博物館宣傳教化的功能日益凸顯，博物館不僅是城市文化的標(biāo)志和象征，也是人們了解歷史和復(fù)原歷史的基點(diǎn)。因此博物館人流動線設(shè)計(jì)對于參觀游客就顯得尤為重要。

通常將路徑規(guī)劃的算法分為以下幾種：傳統(tǒng)路徑規(guī)劃算法[1]、啟發(fā)式搜索算法[2]、離散優(yōu)化算法[3]、隨機(jī)采樣算法[4]和智能仿生算法[5]。其中蟻群算法是智能仿生算法中的一種，并已在路徑規(guī)劃具有較為成熟和廣泛的應(yīng)用。如Dorigo和gambardella[6]在隨機(jī)比例狀態(tài)轉(zhuǎn)移規(guī)則的基礎(chǔ)上，提出了偽隨機(jī)比例狀態(tài)轉(zhuǎn)移規(guī)則（pseudo random-proportional state transition rule）。它為解決新的路徑探索提供了一種直接的方法。郭保青等人提出了一種改進(jìn)的蟻群算法是在其中加入回退策略和啟發(fā)式信息，該算法解決了在智能停車庫中AGV的路徑規(guī)劃問題[7]。王雷、石鑫通過改進(jìn)蟻群算法在動態(tài)環(huán)境下移動機(jī)器人得到最優(yōu)路徑，在動態(tài)路徑規(guī)劃時(shí)找出相應(yīng)躲避障礙的方法，使移動機(jī)器人在躲避障礙時(shí)獲得最優(yōu)的或次優(yōu)路徑[8]。施建禮等人在蟻群算法的基礎(chǔ)上引進(jìn)遺傳算法的變異策略，結(jié)合作戰(zhàn)特點(diǎn)和作戰(zhàn)需求優(yōu)化了潛水艇的路徑規(guī)劃，為潛水艇找到最優(yōu)的路徑規(guī)劃方法[9]。

現(xiàn)如今博物館的人流動線設(shè)計(jì)經(jīng)常會造成人流擁堵，走斷頭路、重復(fù)路等缺點(diǎn)。蟻群算法在路徑規(guī)劃上優(yōu)勢明顯，具有全局尋優(yōu)的能力。所以通過蟻群算法來解決博物館的人流動線設(shè)計(jì)有非常重要的應(yīng)用研究價(jià)值。

為使游客在參觀博物館時(shí)擁有更加科學(xué)的參觀順序和最優(yōu)的人流動線設(shè)計(jì)。在此，提出一種基于蟻群算法的博物館人流動線設(shè)計(jì)研究。通過驗(yàn)證表明，蟻群算法具有較強(qiáng)的魯棒性、自適應(yīng)性和優(yōu)良的分布式計(jì)算機(jī)制等優(yōu)點(diǎn)?？梢詫⑵淅迷诓┪镳^人流動線設(shè)計(jì)當(dāng)中，為參觀游客提供更好地參觀體驗(yàn)。

1? 問題描述

圖1為秦始皇兵馬俑博物館。該館位于陜西省西安市臨潼區(qū)。1979年10月1日開館以來已接待數(shù)千萬中外游客。秦始皇兵馬俑博物館由眾多陪葬坑組成，其總占地面積約46萬平方米。秦始皇兵馬俑博物館目前為止，已經(jīng)建成并開放了秦兵馬俑一、二、三號坑展館、銅車馬展館以及環(huán)幕影院可供參觀。圖1中①為博物館東門入口，②～⑥為各展館入口，⑦為博物館西門出口。

本文根據(jù)具體要求，通過蟻群算法得出三種方案，來驗(yàn)證蟻群算法在博物館內(nèi)人流動線規(guī)劃的可施行性。首先驗(yàn)證蟻群算法可以規(guī)劃最短人流動線，通過在隨意兩個(gè)展館之間尋找最短人流動線的方法，來驗(yàn)證蟻群算法可以找到最短人流動線。

其次，根據(jù)博物館的參觀要求，在其中一些展館閉館維護(hù)時(shí)，僅開放銅車馬展館、秦兵馬俑一號坑展館、秦兵馬俑二號坑展館。通過蟻群算法得出開放展館中游客的參觀順序和最短人流動線。

如果博物館五個(gè)展館全部開放，并且規(guī)定銅車馬展館為游客第一個(gè)參觀的展館，秦兵馬俑三號展館為最后一個(gè)參觀的展館，通過蟻群算法來計(jì)算這五個(gè)展館的參觀順序和最短人流動線。

2? 蟻群算法

1992年Marco Dorigo提出了蟻群算法（ACO）這是一種模擬大自然中的螞蟻覓食的仿生優(yōu)化算法[10]。該算法采用了正反饋并行自催化機(jī)制，具有較強(qiáng)的魯棒性、自適應(yīng)性等優(yōu)點(diǎn)。是受到大自然中螞蟻覓食行為的啟發(fā)，想法來源于螞蟻在覓食的過程中會在經(jīng)過的路徑上釋放信息素。隨著信息素的增高，該路徑被其他螞蟻的選擇概率就會大大增加[11]。剩下的螞蟻也將傾向于選擇路徑較短和信息素強(qiáng)度高的方向移動[12]。隨著信息素積累螞蟻在信息素的作用下會不斷搜索路徑，從而得到一條由蟻穴到食物的最短路徑[13]。蟻群算法可用來尋找并得到最優(yōu)路徑。圖2為蟻群算法流程圖。

2.1? 構(gòu)造解空間

根據(jù)秦始皇兵馬俑博物館地圖，通過對地圖一一對應(yīng)，建造相應(yīng)的柵格地圖，將障礙物在柵格地圖中用深色來表示，游客可參觀的路線用淺色來表示。并用數(shù)字進(jìn)行標(biāo)號，模擬游客可以通過淺色柵格進(jìn)行博物館的參觀。將博物館的入口和出口輸入其中，使用概率公式得到下一節(jié)點(diǎn)，最終得到目標(biāo)點(diǎn)，通過這一方法進(jìn)程的淺色柵格即為最短路線。

2.2? 節(jié)點(diǎn)選擇

在模擬實(shí)驗(yàn)中，每次迭代派出X只螞蟻去搜索路徑，經(jīng)歷了N次迭代后。將參觀入口設(shè)置為E，將參觀出口設(shè)置為W?？梢酝ㄟ^先計(jì)算本節(jié)點(diǎn)j與附近范圍內(nèi)八個(gè)節(jié)點(diǎn)i之間的選擇概率Pi，j，然后利用選擇概率Pi，j去判斷下一節(jié)點(diǎn)。來得到每只螞蟻尋找下一節(jié)點(diǎn)的方法。Pi，j的計(jì)算方法為：

式中：i為現(xiàn)螞蟻當(dāng)前節(jié)點(diǎn)的附近八個(gè)節(jié)點(diǎn)的數(shù)字標(biāo)號集合;τi，j為邊（i，j）上的信息素;ηi，j是（i，j）上的啟發(fā)信息;β是影響因子;u表示所有未經(jīng)過點(diǎn)組成的集合。

2.3? 信息素更新策略

根據(jù)每個(gè)算法的不同信息素表達(dá)形式分為兩種，一種為局部信息素更新規(guī)則，另一種為全局信息素更新規(guī)則。兩者的區(qū)別：螞蟻在路徑搜尋中每經(jīng)過一點(diǎn)就會完成對該路徑的信息素進(jìn)行更新。如式（2）所示，本文中使用局部信息素更新。