[發(fā)明專(zhuān)利]求解旅行商問(wèn)題的順序交叉多子代遺傳算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201410740661.8
• 申請(qǐng)日: 2014-12-09
• 公開(kāi)（公告）號(hào): CN104463328A
• 公開(kāi)（公告）日: 2015-03-25
• 發(fā)明（設(shè)計(jì)）人: 王吉權(quán);田占偉;王福林;何夢(mèng)瑩
• 申請(qǐng)（專(zhuān)利權(quán)）人: 東北農(nóng)業(yè)大學(xué)
• 主分類(lèi)號(hào): G06N3/12
• 分類(lèi)號(hào): G06N3/12;G06Q10/04
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.求解旅行商問(wèn)題的順序交叉多子代遺傳算法，其特征在于：

與現(xiàn)有求解旅行商問(wèn)題的遺傳算法的進(jìn)化策略不同，求解旅行商問(wèn)題的順序交叉多子代遺傳算法的進(jìn)化策略為：

首先，產(chǎn)生種群規(guī)模為n的初始種群，以初始種群作為父代，并將種群中的所有個(gè)體按路線長(zhǎng)度從小到大進(jìn)行排序，根據(jù)排序的結(jié)果計(jì)算種群中每一個(gè)個(gè)體的適應(yīng)度，然后進(jìn)行選擇、交叉，并從交叉產(chǎn)生的2n個(gè)子代個(gè)體和n個(gè)父代個(gè)體中保留q個(gè)精英個(gè)體，然后將交叉產(chǎn)生的2n個(gè)子代個(gè)體按變異概率p_m進(jìn)行變異，變異后得到的個(gè)體數(shù)為2np_m，再加上交叉后沒(méi)有變異的那一部分個(gè)體與從父代和交叉產(chǎn)生的個(gè)體中選出的q個(gè)精英個(gè)體，此時(shí)種群中共有2n?+q個(gè)子代個(gè)體，可在2n?+q個(gè)個(gè)體中選取最優(yōu)的q個(gè)作為精英個(gè)體，選取最優(yōu)的n個(gè)個(gè)體作為子代；判斷是否滿足給定的迭代終止條件，若滿足迭代終止條件，則停止計(jì)算；若不滿足迭代終止條件，則把子代當(dāng)成父代；重復(fù)上述步驟，直至滿足迭代終止條件為止。

2.根據(jù)權(quán)利要求1所述的求解旅行商問(wèn)題的順序交叉多子代遺傳算法，其特征在于給出了一種基于順序交叉的多子代產(chǎn)生方法；這種多子代的產(chǎn)生方法為：

設(shè)被選擇配對(duì)的父代個(gè)體為A和B

A=3?4?6?8?1?2?9?7?5

B=2?7?1?9?5?3?6?4?8

根據(jù)均勻隨機(jī)分布產(chǎn)生兩個(gè)交叉點(diǎn)，用“|”表示交叉點(diǎn)所在的位置，具體情況如下：

A=3?4?6?｜?8?1?2?9｜7?5

B=2?7?1?｜?9?5?3?6｜4?8

首先，兩個(gè)交叉點(diǎn)之間的中間段保持不變，得到

C₁=*?*?*?｜8?1?2?9｜*?*

C₂=*?*?*?｜9?5?3?6｜*?*

然后，記取父代個(gè)體B從第二個(gè)交叉點(diǎn)開(kāi)始城市碼的排列順序，當(dāng)?shù)竭_(dá)B的最后時(shí)，返回B的開(kāi)始繼續(xù)記錄代表城市的數(shù)字，直至到達(dá)第二個(gè)交叉點(diǎn)結(jié)束，這樣便得到了父代個(gè)體B從第二個(gè)交叉點(diǎn)開(kāi)始的城市排列順序?yàn)?-8-2-7-1-9-5-3-6；對(duì)于父代個(gè)體A而言，已有城市碼有8-1-2-9，將它們從父代個(gè)體B的城市碼排列順序中去掉，得到排列順序4-7-5-3-6，再將這個(gè)順序復(fù)制給父代個(gè)體A，復(fù)制的起點(diǎn)也是從第二個(gè)交叉點(diǎn)開(kāi)始，以此決定子代個(gè)體1對(duì)應(yīng)位置的未知碼*，得到的子個(gè)體1為：

C₁=5?3?6?｜8?1?2?9｜4?7

????同樣，可以產(chǎn)生子個(gè)體2為：

C₂=8?1?2?｜9?5?3?6｜7?4

其次，兩個(gè)父代個(gè)體中第二個(gè)交叉點(diǎn)后面的城市碼不變，將中間部分移到最前面，這樣變化后A和B兩個(gè)父代個(gè)體中城市碼的排列順序?yàn)?/p>

AA=8-1-2-9-3-4-6-7-5

BB=9-5-3-6-2-7-1-4-8

然后，將AA中4-8的城市碼去掉，將BB中7-5的城市碼去掉，得到1-2-9-3-6-7-5和9-3-6-2-1-4-8，再將7-5加到9-3-6-2-1-4-8的尾部，將4-8加到1-2-9-3-6-7-5的尾部，得到兩個(gè)子個(gè)體為：

C₃=9?3?6｜2?1?4?8｜7?5

C₄=1?2?9｜3?6?7?5｜4?8

這樣父代個(gè)體A和B經(jīng)過(guò)順序交叉后，產(chǎn)生了四個(gè)子代個(gè)體；

當(dāng)初始種群的規(guī)模為n時(shí)，通過(guò)順序交叉就可以得到2n個(gè)子代個(gè)體。