[發(fā)明專利]基于動態(tài)遺傳算法串行融合的直升機調(diào)度航線規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202110690807.2
• 申請日: 2021-06-22
• 公開（公告）號: CN113326990B
• 公開（公告）日: 2022-11-15
• 發(fā)明（設(shè)計）人: 劉洋洋;王夢;伍德林;張春嶺;房浩;尹牛牛
• 申請（專利權(quán)）人: 安徽農(nóng)業(yè)大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12;G06Q50/02
• 代理公司: 蕪湖市昌強專利代理事務(wù)所(特殊普通合伙) 34203
• 代理人: 周渭銘

1.一種基于動態(tài)遺傳算法串行融合的直升機調(diào)度航線規(guī)劃方法，其特征在于：包括如下步驟：

S1、根據(jù)各作業(yè)施藥區(qū)域的地形特點，在二維地圖上作各作業(yè)施藥區(qū)域的外切圓，并確定外切圓圓心的經(jīng)緯度信息；

S2、采用整數(shù)編碼的方式，對各個作業(yè)施藥區(qū)域外切圓圓心進行十進制編碼，確定作業(yè)施藥區(qū)域數(shù)量；

S3、根據(jù)需要的作業(yè)施藥區(qū)域數(shù)量，設(shè)置第一階動態(tài)遺傳算法的航線解集中的參數(shù)，航線條數(shù)M、變異概率Pm、最小進化率U、最大迭代次數(shù)GENMAX1、最小進化率連續(xù)迭代次數(shù)a₁、迭代次數(shù)初值置gen1＝1；

S4、通過各作業(yè)施藥區(qū)域外切圓圓心的編碼信息，采用隨機產(chǎn)生種群的方式得到第一階初始調(diào)度航線解集Gather1；

S5、計算第一階初始調(diào)度航線解集Gather1中每一條作業(yè)航線的適應(yīng)度，適應(yīng)度值為每條作業(yè)航線長度的倒數(shù)；

S6、將第一階初始調(diào)度航線解集Gather1中的所有作業(yè)航線根據(jù)適應(yīng)度大小進行排序，以中位數(shù)為節(jié)點，將第一階初始調(diào)度航線解集Gather1劃分為相等的上下兩部分，挑選出第一階初始調(diào)度航線解集Gather1中適應(yīng)度較大的那部分航線，進行下一步操作；

S7、對挑選出作業(yè)航線進行動態(tài)交叉概率計算，并根據(jù)動態(tài)交叉概率進行交叉操作和變異操作，得到第一階新航線解集Gather0，并將第一階新航線解集Gather0的數(shù)據(jù)賦予第一階初始調(diào)度航線解集Gather1，并且迭代次數(shù)加1，即gen1←gen1+1；

動態(tài)交叉概率的計算公式為：

式中，f_n為適應(yīng)度；f_min為最小適應(yīng)度值；f_max為最大適應(yīng)度值；

S8、檢查迭代次數(shù)gen1是否達到最大值GENMAX1，達到以后則輸出第一階新航線解集中航線最短的調(diào)度航線為最優(yōu)航線，否則執(zhí)行S9；

S9、判斷新航線解集迭代的進化率是否連續(xù)a₁次都小于預(yù)設(shè)的最小進化率，如果都小于，則輸出第一階航線解集Gather1，否則執(zhí)行步驟S5；

S10、把第一階動態(tài)遺傳算法輸出航線解集Gather1作為第二階動態(tài)遺傳算法的初始調(diào)度航線解集Gather2；

S11、設(shè)置第二階動態(tài)遺傳算法種群大小、迭代次數(shù)、變異概率、最小進化率、最小進化率連續(xù)迭代次數(shù)a₂，第二階算法最大迭代次數(shù)GENMAX2，并將迭代次數(shù)初值置1，即gen2＝1；

S12、采用二進制編碼的方式，初始化航線解集Gather2；

S13、結(jié)合每一作業(yè)施藥區(qū)域的作業(yè)起點和終點，計算第二階算法的適應(yīng)度值；

S14、將航線解集Gather2中的所有航線根據(jù)適應(yīng)度大小進行排序，并以中位數(shù)為節(jié)點，將數(shù)值集合Gather2劃分為相等的上下兩部分，挑選出航線解集Gather2中適應(yīng)度較大的那部分航線進行下一步操作；

S15、對挑選出航線的動態(tài)交叉概率進行計算，并根據(jù)動態(tài)交叉概率進行交叉操作和變異操作，得到新航線集Gather3，并將新航線集Gather3的數(shù)據(jù)賦予解集Gather2，并且迭代次數(shù)加1，即gen2←gen2+1；

S16、檢查迭代次數(shù)gen2是否達到最大值GENMAX2，達到以后則輸出航線解集Gather2中航線最短的調(diào)度航線，該航線為規(guī)劃的最優(yōu)航線，即多施藥區(qū)域航線調(diào)度規(guī)劃的最佳調(diào)度方案，否則執(zhí)行S17；

S17、判斷新航線解集迭代的進化率是否連續(xù)a₂次都小于預(yù)設(shè)的最小進化率，如果都小于，則輸出新航線解集中航線最短的調(diào)度航線為最優(yōu)航線，否則執(zhí)行步驟S13。

2.如權(quán)利要求1所述的基于動態(tài)遺傳算法串行融合的直升機調(diào)度航線規(guī)劃方法，其特征在于：所述步驟S5中，適應(yīng)度值計算公式為

設(shè)|k₁|k₂|…|k_i|…|k_n|為一個編碼的航線，

則

式中，為施藥區(qū)域i到施藥區(qū)域j的距離；f_n為適應(yīng)度。

3.如權(quán)利要求1所述的基于動態(tài)遺傳算法串行融合的直升機調(diào)度航線規(guī)劃方法，其特征在于：所述步驟S7中根據(jù)變異概率對新航線集中的航線采取變異操作，變異概率的取值為0.1。