[發明專利]基于差分進化算法的大型公共場所人流引導路徑規劃方法

有效

• 申請號: 202110219913.2
• 申請日: 2021-02-26
• 公開（公告）號: CN112884229B
• 公開（公告）日: 2022-12-20
• 發明（設計）人: 鐘競輝;李東芮;蔡文桐
• 申請（專利權）人: 中新國際聯合研究院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06F30/27;G06N3/00;G06F111/06
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 李盛洪

本發明公開了一種基于差分進化算法的大型公共場所人流引導路徑規劃方法。本發明將路徑規劃問題表示為一個連續優化問題，利用差分進化算法結合多目標優化技術解決大型公共場所的人流引導路徑規劃問題，將路徑方案編碼為一組前后相關互聯的基因序列，在差分進化過程中，基于人群行為仿真的結果對路徑方案進行適應度評估，引導種群進行個體選擇，將安全性和效率作為多目標選擇操作的兩個目標，應用經典的NSGA?II算法進行種群個體選擇，得到的路徑方案既有著較好的安全性，又能引導人群高效通過場景，有效地克服了現有技術優化時評估準則過于單一的不足，減少了路徑交叉，兼顧了安全性和效率。

技術領域

本發明涉及路徑規劃和智能計算技術領域，具體涉及一種基于差分進化算法的大型公共場所人流引導路徑規劃方法。

背景技術

大型公共場所的人流引導問題是公共安全的重要問題。它要求在給定場景下提供路牌或路線指示，從而使得行人能快速、安全地到達各自的目的地，同時盡可能地避免不同路線之間的交叉導致的擁堵。

路徑規劃方法主要包括根據場景信息進行的全局路徑規劃和根據實時信息進行的局部路徑規劃。傳統的路徑規劃方法包括Dijkstra算法和A*算法等，近年來也有仿生學方法被應用于路徑規劃，如蟻群算法、遺傳算法等。這些方法往往針對給定的靜態場景提供一組最短或較短的路徑，但在像車站和商場這些人流密集、行人路線復雜的場景下，僅優化距離得到的路徑往往不夠安全，行走方向不同的人流之間的交叉可能會導致人群擁堵，而嚴重的擁堵則可能引發安全事故。在這類場景下，路徑的距離或人群通過場景的效率往往不是唯一應該考慮的的優化目標，而現有的路徑規劃方法大多僅適用于優化單一目標，故而，在路徑復雜的場景下，考慮路徑的距離提高效率的同時減少路徑交叉，從而提高路徑安全性成為一個需要解決的問題。

此外，對于多出入口的場景，還需要將出口的選擇作為規劃內容的一部分，如何為走向各目的地的行人合理分配出口，既提高出口利用率，也控制出口的負載，同樣是一個既關乎安全性也關乎效率的需要解決的問題。

發明內容

本發明的目的是為了解決現有技術中的上述缺陷，提供一種基于差分進化算法的大型公共場所人流引導路徑規劃方法。差分進化算法是一種基于種群的啟發式搜索算法，種群中的每個種群個體對應一個解向量，稱之為目標向量，其進化流程包括變異、雜交和選擇等操作，生成測試向量，通過對目標向量和測試向量進行適應度評估，更新種群個體，經過不斷地進化迭代，保留優良個體，淘汰劣質個體，引導搜索向最優解逼近。本發明提出的路徑規劃方法利用差分進化算法結合多目標優化技術解決路徑規劃問題，有效地克服了現有技術優化時評估準則過于單一的不足，減少了路徑交叉，兼顧了安全性和效率，提高了其實用性。

本發明的目的可以通過采取如下技術方案達到：

一種基于差分進化算法的大型公共場所人流引導路徑規劃方法，其路徑規劃方法包括以下步驟：

S1、執行初始化操作：根據場景中的可行區域，隨機生成大小為N的種群Q，所述種群包含N個種群個體；用前后基因互相關聯的編碼方式編碼路徑方案，為每個種群個體構建目標向量，路徑方案由多條路徑組成，對路徑方案進行編碼即對路徑用前后基因互相關聯的編碼方式進行編碼；基于人群行為的仿真結果計算所述目標向量的目標函數值，在仿真過程中，利用智能體模擬人群行為。

S2、執行個體交叉操作：為每個所述種群個體構建測試向量；基于人群行為仿真的結果計算測試向量的目標函數值；進行適應度評估，執行多目標選擇操作更新種群個體的目標向量。

S3、執行局部搜索操作：更新種群個體測試向量；基于人群行為仿真的結果計算測試向量的目標函數值；進行適應度評估，執行多目標選擇操作更新種群個體的目標向量。

S4、重復執行S2、S3步驟，直到達到預設迭代次數或路徑方案的安全性和效率都滿足預設需求。

S5、將最后一次迭代得到的路徑方案作為最終路徑方案，并對路徑規劃方案進行后期處理。