[發明專利]一種基于改進遺傳算法的快速最短枝切搜索方法

有效

• 申請號: 201910124930.0
• 申請日: 2019-02-19
• 公開（公告）號: CN110059825B
• 公開（公告）日: 2023-04-07
• 發明（設計）人: 楊延西;王建華;張申華;鄧毅;高異
• 申請（專利權）人: 西安理工大學
• 主分類號: G06N3/126
• 分類號: G06N3/126;G01B11/25
• 代理公司: 北京國昊天誠知識產權代理有限公司 11315
• 代理人: 楊洲

1.一種基于改進遺傳算法的快速最短枝切搜索方法，其特征在于，包括以下步驟：

步驟1，殘差點識別、數量匹配與殘差點編碼，具體做法是：

1)掃描整幅包裹相位圖，識別出正、負殘差點，并將正、幅殘差點在包裹相位圖中的行列號分別記錄在兩個矩陣中，記為正殘差點行列號矩陣和負殘差點行列號矩陣；

2)殘差點編碼時，最大編碼為正、負殘差點數量的最大值，依據公式(2)，當正、負殘差點的數量不一致時，殘差點數量少的需要補充至兩者相等；補充的殘差點的行列號為(0,0)，行列號為(0,0)的殘差點既可以作為正殘差點，也可以作為負殘差點，即相當于圖像的四邊界，

N＝max{No_positive,No_negative}??????????????(2)

式中，No_positive為正殘差點的數量，No_negative為負殘差點的數量，N為最大編碼；

當一個普通殘差點與一個行列號為(0,0)的特殊殘差點匹配時，適應度函數采用公式(3)，公式(3)表示殘差點與四邊界之間的最近距離，

fitness＝min{xⁱ,yⁱ,(width-xⁱ),(length-yⁱ)}????????????(3)

式中，width為包裹相位圖的寬，length為包裹相位圖的長，(xⁱ,yⁱ)為普通殘差點的行列號；

步驟2，負殘差點初始種群的生成

正殘差點的染色體序列只有一個，且固定不變，

A、隨機產生m種具有不同排序的負殘差點的染色體序列；

B、采用最近鄰算法產生n種有不同排序的負殘差點的染色體序列，且為了實現種群多樣性，所有產生的染色體序列與步驟A中的染色體序列互不相同；

C、共生成m+n種染色體序列的初始種群，為了實現后面的交叉算子，m+n應為偶數，即染色體交叉算子配對的數目為[(m+n)/2]；

步驟3，選擇算子

采用適者生存的自然選擇法則，以適應度函數為評價標準，在當前的群體中，尋找適用度最佳的k(k[(m+n)/2])種染色體序列來替換適應度最差的k種染色體序列，因此，優良的父染色體序列具有更大的概率將染色體傳遞給子染色體序列；

步驟4，交叉算子

以交叉概率P_c實施交叉算子，如果有(m+n)種染色體序列的初始種群，相鄰的兩個染色體序列形成交叉對，則交叉對的數目為[(m+n)/2]；然后，將交叉對染色體序列的一串基因交換，并將重復的基因替換，生成兩個新的子染色體，

步驟5，變異算子

以變異概率P_m實施變異算子，其原理是在同一染色體序列上隨機選擇兩個基因并互換它們，變異后將產生一個新的染色體來改善種群多樣性，類似于交叉算子，如果新的子染色體更適合，則父染色體被子染色體取代；否則，父染色體被保留，子染色體丟失。

2.根據權利要求1所述的一種基于改進遺傳算法的快速最短枝切搜索方法，其特征在于，步驟4所述的交叉算子，其操作步驟如下：

a、在交叉對染色體序列上隨機選取兩個交叉點，交叉點分別記為crosspoint(1)和crosspoint(2)；

b、交叉點crosspoint(1)和crosspoint(2)之間的基因串互換，crosspoint(1)＝5，表示交叉點位置，不是基因編碼數據，crosspoint(2)＝8；染色體序列1的crosspoint(1)和crosspoint(2)之間的基因串為7-,6-,2-,8-,染色體序列2的crosspoint(1)和crosspoint(2)之間的基因串為3-,5-,4-,6-；交互之后，染色體序列1替換為5-,4-,1-,9-,3-,5-,4-,6-,3-，染色體序列2替換為7-,8-,2-,1-,7-,6-,2-,8-,9-；

c、基因串交叉完成后，當基因編碼存在重復時，參照現有遺傳算法的交叉算子解決；

d、如果生成的子染色體序列適應度更好，則父染色體序列會被子染色體序列替換，否則，父染色體序列被保留而子染色體序列被遺棄。