[發(fā)明專利]水下潛航器的雙重粒子群多監(jiān)測點(diǎn)訪問路徑規(guī)劃方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201810746145.4
• 申請(qǐng)日: 2018-07-09
• 公開（公告）號(hào): CN109190787B
• 公開（公告）日: 2022-02-18
• 發(fā)明（設(shè)計(jì)）人: 胡曉敏;王明豐;梁天毅;李敏
• 申請(qǐng)（專利權(quán)）人: 廣東工業(yè)大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06N3/00
• 代理公司: 廣州粵高專利商標(biāo)代理有限公司 44102
• 代理人: 林麗明

1.水下潛航器的雙重粒子群多監(jiān)測點(diǎn)訪問路徑規(guī)劃，其特征在于，監(jiān)測點(diǎn)之間的路線優(yōu)化與最優(yōu)訪問序列交替協(xié)同優(yōu)化，其包括以下步驟：

S1：距離矩陣的初始化：通過讀入三維地形數(shù)據(jù)和所有的監(jiān)測點(diǎn)的空間坐標(biāo)，對(duì)于這n個(gè)監(jiān)測點(diǎn)，計(jì)算任意兩點(diǎn)之間的歐幾里得距離，然后得到一個(gè)初始距離矩陣DistMatrix；

S2：最優(yōu)路徑序列的反復(fù)構(gòu)造，具體包括：

S2.1：構(gòu)造種群，種群中每個(gè)粒子個(gè)體代表一種監(jiān)測點(diǎn)訪問序列，i＝1,2,…,m，其中m是種群粒子數(shù)量，n代表訪問序列中待監(jiān)測點(diǎn)的數(shù)量，即粒子的維度數(shù)；然后隨機(jī)初始化粒子的速度集V_i為一些帶概率的邊組成的集合，即一些從全部監(jiān)測點(diǎn)中隨機(jī)選取的兩點(diǎn)構(gòu)成的二元組并附加一個(gè)(0,1)之間的概率值組成的集合，其中概率值表示一條邊被選中用來構(gòu)造新的訪問序列的可能性大小；

S2.2：根據(jù)距離矩陣DistMatrix計(jì)算每個(gè)個(gè)體的路線總長度，然后記錄每個(gè)個(gè)體的歷史最優(yōu)個(gè)體pbest；并選出使路線長度最短的全局最優(yōu)個(gè)體gbest；

S2.3：按照公式來更新每個(gè)粒子的速度集：對(duì)于維度節(jié)點(diǎn)j(j＝1,2,…,n)，首先生成一個(gè)隨機(jī)數(shù)ran∈[0,1]，若ran大于預(yù)先設(shè)定的分界值Pc，則f_i(j)＝i，即從自身歷史最優(yōu)個(gè)體學(xué)習(xí)并更新速度集，否則從種群中隨機(jī)選擇兩個(gè)個(gè)體，取它們歷史最優(yōu)個(gè)體中總路線長度最短的那個(gè)個(gè)體作為f_i(j)來學(xué)習(xí)；然后從監(jiān)測點(diǎn)訪問序列和里前后相連的節(jié)點(diǎn)組成的邊集中選擇屬于而不屬于的邊，再乘以cr^j當(dāng)做邊的概率值來構(gòu)造出一個(gè)啟發(fā)式速度集，其中c表示學(xué)習(xí)因子，是一個(gè)固定值；r^j為介于(0,1)之間的隨機(jī)數(shù)；最后將速度集中邊的概率值乘以一個(gè)固定慣性權(quán)重w構(gòu)成速度集再將其與剛才的啟發(fā)式速度集合并，構(gòu)造出新的速度集，為種群個(gè)數(shù)；

S2.4：結(jié)合更新后的速度子集更新粒子個(gè)體的訪問序列：首先構(gòu)造一個(gè)空集New_P_i，隨機(jī)選擇一個(gè)節(jié)點(diǎn)t作為訪問起點(diǎn)加入空集，剔除掉速度集V_i中概率較小的邊；然后從速度集v_i中查找與當(dāng)前節(jié)點(diǎn)t相連的所有邊中概率值最大的邊，并將這條邊另一個(gè)節(jié)點(diǎn)加入New_P_i中；如果速度集v_i不包含與節(jié)點(diǎn)t相連的邊，則查看原路徑序列P_i中與節(jié)點(diǎn)t相連的節(jié)點(diǎn)是否已全部加入New_P_i，若還有尚未加入的邊節(jié)點(diǎn)，則選擇與當(dāng)前節(jié)點(diǎn)相連且距離最近的邊節(jié)點(diǎn)加入New_P_i；否則從其他種群個(gè)體中選擇與當(dāng)前節(jié)點(diǎn)距離最近且未納入的節(jié)點(diǎn)加入New_P_i；最后為剛加入的節(jié)點(diǎn)構(gòu)造下一個(gè)訪問點(diǎn)；重復(fù)上述過程，直到所有的監(jiān)測點(diǎn)加入到新的路徑序列New_P_i為止；

S2.5：重復(fù)S2.3、S2.4兩個(gè)步驟，直到到達(dá)最大迭代次數(shù)或連續(xù)若干代無法得到更好的解時(shí)即停止迭代；最后得到一條最優(yōu)訪問序列，完成實(shí)現(xiàn)第一重粒子群優(yōu)化；

S3：路徑點(diǎn)之間的路線優(yōu)化：對(duì)上一步驟得到的最優(yōu)訪問序列中前后相連的路徑點(diǎn)之間的距離和路線進(jìn)行優(yōu)化，利用優(yōu)化后的距離值來更新之前的距離矩陣DistMatrix，并借此計(jì)算最優(yōu)訪問序列的路線總長度，更新并記錄最優(yōu)訪問序列及其總路線長度；

S4：如果達(dá)到結(jié)束條件就終止整個(gè)算法，否則返回步驟S2；

S5：輸出所有監(jiān)測點(diǎn)的最佳訪問序列、訪問路線及其長度；

以任意兩點(diǎn)之間的歐幾里得直線距離作為初始距離矩陣，是粒子群算法在尋找最優(yōu)訪問序列過程中評(píng)價(jià)種群粒子所代表的訪問序列的質(zhì)量并計(jì)算其總路線長度的前提條件；基于不同的距離矩陣，粒子群優(yōu)化算法尋找的最優(yōu)訪問序列也不同；在距離矩陣得到更新優(yōu)化后，優(yōu)化收斂尋找到的最優(yōu)訪問序列質(zhì)量也更好；

監(jiān)測點(diǎn)距離矩陣與最優(yōu)路徑訪問序列的兩重優(yōu)化是交替往復(fù)進(jìn)行的；構(gòu)造最優(yōu)訪問序列的過程依賴當(dāng)前的監(jiān)測點(diǎn)距離矩陣，為減少更新任意兩個(gè)監(jiān)測點(diǎn)之間的路線和距離所帶來的巨大時(shí)間開銷，距離矩陣的更新又依賴于當(dāng)前構(gòu)造出的最優(yōu)路徑序列中前后相連的監(jiān)測點(diǎn)信息，這兩個(gè)過程相互依賴，交互在線進(jìn)行優(yōu)化。