[發明專利]基于最小生成樹聚類遺傳算法的交通信號配時優化方法

有效

• 申請號: 201310652912.2
• 申請日: 2013-12-05
• 公開（公告）號: CN103699933A
• 公開（公告）日: 2014-04-02
• 發明（設計）人: 楊新武;薛慧斌
• 申請（專利權）人: 北京工業大學
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 張慧

1.一種基于最小生成樹聚類遺傳算法的交通信號優化配時方法，包括以下步驟：

步驟一，進行個體編碼、初始化數據，并設定參數；

所述個體表示綠燈時間的組合；用t_i表示i相位的綠燈時間，為保持產生的后代個體的有效性，采用3個時間組合，個體編碼形式為：＜t₁?t₂?t₃＞，用二進制進行編碼；所述初始化數據將種群大小初始化為popszie，每次后代都產生popsize大小的種群；所述設定參數包括：設定交叉概率P_c為0.8，變異概率P_m為0.01，個體長度21位；

步驟二，進行種群初始化，隨機產生popsize個21位個體組成的種群；

步驟三，計算種群內個體的適應度值；

步驟四，對種群進行最小生成樹聚類；

步驟五，選擇種群內個體參加遺傳操作；

對種群內個體采用輪盤賭選擇兩個個體，如果兩個個體不屬于同一類，則兩個個體被選定，參與到遺傳操作中產生后代個體；如果兩個個體屬于同一類，判斷兩個個體的適應度值大小，將適應度值大的個體淘汰，重新選擇，直到選到的個體屬于不同類為止；

步驟六，對步驟五選擇的個體進行交叉和變異操作；

交叉操作，采用單點交叉，隨機產生交叉位，互組父代個體之間的基因位，形成兩個新的個體；

變異操作，對交叉后產生的兩個個體，以一定的概率進行變異，0變1，或1變0，變異后產生個體還需要解碼后判斷是否滿足t_i的條件，如果滿足，將其歸入下一代種群，直到產生大小為popsize的后代種群，作為下一代操作的父代種群；如果不滿足，則直接淘汰產生的新個體，同時計數器不進行累加，保證最后產生popsize個后代個體；

步驟七，重復執行步驟四～六，得到對應周期的最佳配時；

其特征在于，所述步驟四對種群進行最小生成樹聚類的方法如下：

（1）計算popsize個個體間的歐式距離作為兩個個體建立的邊的權重，構成一個有權無向圖；

（2）利用Prim算法求出這個無向圖的最小生成樹；

（3）確定最小生成樹的斷邊閾值；

（4）通過切斷生成樹中的邊進行分類：從最小生成樹起點開始遍歷，將權重大于閾值的邊去掉，形成一個森林，屬于同一個樹的邊就屬于同一類；

（5）對森林進行深度遍歷，對每一類進行記錄保存，同時對每類中的個體按照適應度值大小進行排序。