【文章內(nèi)容簡(jiǎn)介】 的編碼最為自然，最為簡(jiǎn)單表示的方法. 如，旅程（）可以直接的表示為，基于路徑的表示編碼的方法，需要一個(gè)個(gè)體染色體的編碼當(dāng)中不能允許有著重復(fù)基因碼，就是需要滿足任何一個(gè)鄉(xiāng)村都必須訪問(wèn)一次. 基本的遺傳算法交叉的操作而生成個(gè)體，其一般情況是不能夠滿足這種約束的條件. 因此，提供出一組被稱為重排的操作新操作來(lái)進(jìn)行處理這種表示，它主要包括以下三種的操作：部分的匹配的交叉對(duì)于下面所表示，任意選擇兩個(gè)不同的交叉點(diǎn)“|”. ： （1 2 3| 4 5 6 7| 8 9） ： （4 5 2| 1 8 7 6| 9 3）首先，兩交叉點(diǎn)在它們的中間段進(jìn)行交換，得到： ： （x x x| 1 8 7 6| x x） ： （x x x|4 5 6 7| x x）其中x表示暫時(shí)未進(jìn)行定義的編碼，得到： 1←→4,8←→5,7←→6,6←→7然后，對(duì)兩個(gè)個(gè)體中的x部分，保留鄉(xiāng)村碼2,3,9，得到： ： （x 2 3| 1 8 7 6| x 9） ： （x x 2|4 5 6 7| 9 3）最后，對(duì)上面的子個(gè)體1中的第一個(gè)x，來(lái)用最初的父碼1，由1←→4交換之后得到了首個(gè)為4，如此操作，子個(gè)體2的次個(gè)，來(lái)用最初的父碼8，由8←→，即為備選的交換有許多個(gè)碼，那么便選擇此前的未確定的某個(gè)碼來(lái)為交換. 如此進(jìn)行，最后得到的子個(gè)體是： ： （4 2 3| 1 8 7 6| 5 9） ： （1 8 2| 4 5 6 7| 9 3）順序交叉對(duì)于下面的表示，任意選擇兩個(gè)交叉點(diǎn)“|”. ： （1 2 3| 4 5 6 7| 8 9） ： （4 5 2| 1 8 7 6| 9 3）首先，保存在兩交叉點(diǎn)之間的中間的段,并且不改變，得到： ： （x x x| 4 5 6 7| x x） ： （x x x|1 8 7 6| x x）然后，記錄并提取父?jìng)€(gè)體2由第二個(gè)的交叉點(diǎn)1初始排列的順序，從到達(dá)表尾的時(shí)刻，向表頭返回繼續(xù)的對(duì)鄉(xiāng)村碼記錄，到達(dá)了第二個(gè)的交叉點(diǎn)便結(jié)束，這樣就能得到了自從第二個(gè)的交叉點(diǎn)初始的排列的順序是的父?jìng)€(gè)體2. 其中父?jìng)€(gè)體1，已經(jīng)有的鄉(xiāng)村碼有，將它們?nèi)サ?，能夠得到的次序可以?3218，然后復(fù)制這個(gè)排列的順序到父?jìng)€(gè)體1，復(fù)制的起點(diǎn)也就是由第二個(gè)的交叉的點(diǎn)初始，子個(gè)體1可以通過(guò)這種方法生成為： ： （2 1 8 4 5 6 7 9 3）同時(shí)，產(chǎn)生的子個(gè)體2為： ： （3 4 5 1 8 7 6 9 2）循環(huán)交叉下面的兩個(gè)的父?jìng)€(gè)體： ： （1 2 3 4 5 6 7 8 9） ： （4 1 2 8 7 6 9 3 5）先從父?jìng)€(gè)體1中取的首個(gè)鄉(xiāng)村碼，對(duì)子個(gè)體1進(jìn)行生成： ： （1 x x x x x x x x）子個(gè)體從任一一個(gè)父?jìng)€(gè)體相同的位置中取出，因?yàn)楦競(jìng)€(gè)體2里面與父?jìng)€(gè)體1里面的首個(gè)的鄉(xiāng)村碼1相對(duì)鄉(xiāng)村碼是4，所以決定得子個(gè)體1里面的第4的鄉(xiāng)村碼是4： ： （1 x x 4 x x x x x）接下來(lái)，選出鄉(xiāng)村碼是4相對(duì)于父?jìng)€(gè)體的1鄉(xiāng)村碼，等又選鄉(xiāng)村1，為一循環(huán)，獲得： ： （1 2 3 4 5 x x 8 x）最后，有： ： （1 2 3 4 5 6 7 8 9）同樣，可有子個(gè)體2為： ： （4 1 2 8 5 6 7 3 9）邊重組 如，一條旅程（3 1 2 8 7 4 6 9 5）中可定義的有（3 1），（1,2），（2,8），（8 7），（7,4），（4,6），（6,9），（9,5），（5,3）. 邊（1 3）與邊（3 1）表示的是鄉(xiāng)村1跟鄉(xiāng)村3之間的鄰接的關(guān)系. 下面的兩父?jìng)€(gè)體的表示： （1 2 3 4 5 6 7 8 9） （4 1 2 8 7 6 9 3 5）對(duì)每一鄉(xiāng)村來(lái)說(shuō)其邊表為： 鄉(xiāng)村1：通向的其他的鄉(xiāng)村邊有9 2 4 ； 鄉(xiāng)村2：通向的其他的鄉(xiāng)村邊有2 3 8 ；鄉(xiāng)村3：通向的其他的鄉(xiāng)村邊有3 4 9 5 ；鄉(xiāng)村4：通向的其他的鄉(xiāng)村邊有4 5 1 ；鄉(xiāng)村5：通向的其他的鄉(xiāng)村邊有5 6 3 ；鄉(xiāng)村6：通向的其他的鄉(xiāng)村邊有6 7 9 ；鄉(xiāng)村7：通向的其他的鄉(xiāng)村邊有7 8 ；鄉(xiāng)村8：通向的其他的鄉(xiāng)村邊有8 9 2 ；鄉(xiāng)村9：通向的其他的鄉(xiāng)村邊有9 1 5 3 ；子個(gè)體生成需要從子個(gè)體首個(gè)的鄉(xiāng)村碼的選擇初始，可以進(jìn)行隨機(jī)選擇任意兩父?jìng)€(gè)體首個(gè)的鄉(xiāng)村碼. 已選的鄉(xiāng)村邊表之中的所有的鄉(xiāng)村的對(duì)應(yīng)的邊表當(dāng)中邊數(shù)為最少鄉(xiāng)村碼需要成為下個(gè)的鄉(xiāng)村碼，若含有的邊表邊數(shù)相等，可從里面隨機(jī)的挑選鄉(xiāng)村碼. ，從里面選擇其中的一個(gè)鄉(xiāng)村當(dāng)做是下個(gè)的鄉(xiāng)村碼，其中，鄉(xiāng)村9邊表的長(zhǎng)是4，同時(shí)鄉(xiāng)村2以及鄉(xiāng)村4邊表的長(zhǎng)都是3，然后，那么第三個(gè)的鄉(xiāng)村碼就需由鄉(xiāng)村4的邊表中所列鄉(xiāng)村3和鄉(xiāng)村5中產(chǎn)生，由于鄉(xiāng)村3的邊表長(zhǎng)為4. 鄉(xiāng)村5邊表長(zhǎng)為3，因此，可以獲得一個(gè)字體：（1 4 5 6 7 8 2 3 9） 操作中可能存在邊失敗的問(wèn)題，即中間對(duì)應(yīng)的邊表所列鄉(xiāng)村，在該步之間已經(jīng)都進(jìn)入了選擇，在ER操作中不再保留父?jìng)€(gè)體中共同部分的序列[5].新的邊表為：鄉(xiāng)村1：通往的其他的鄉(xiāng)村邊有4 2 9 ； 鄉(xiāng)村2：通往的其他的鄉(xiāng)村邊有3 1 8 ；鄉(xiāng)村3：通往的其他的鄉(xiāng)村邊有4 2 9 5 ；鄉(xiāng)村4：通往的其他的鄉(xiāng)村邊有1 5 3 ；鄉(xiāng)村5：通往的其他的鄉(xiāng)村邊有4 3 6 ；鄉(xiāng)村6：通往的其他的鄉(xiāng)村邊有9 7 5 ；鄉(xiāng)村7：通往的其他的鄉(xiāng)村邊有8 6 ；鄉(xiāng)村8：通往的其他的鄉(xiāng)村邊有7 2 9 ；鄉(xiāng)村9：通往的其他的鄉(xiāng)村邊有1 8 3 6 ；依照新的邊表顯示，ER的操作中所子個(gè)體產(chǎn)生時(shí)，. 遺傳算法在背包問(wèn)題中的應(yīng)用 背包問(wèn)題概述 背包問(wèn)題事實(shí)上就是一個(gè)規(guī)劃的問(wèn)題的數(shù)學(xué)模型. 如若有n個(gè)物件，它的重量用來(lái)進(jìn)行表示，價(jià)值為（），定義的變量應(yīng)為=1，它的數(shù)學(xué)的模型的表示： （216） （217）或1,；j=1，…，n上式中，，均為正值. 二重結(jié)構(gòu)的編碼的遺傳算法二重結(jié)構(gòu)的編碼的方法如表21所示. ,下面一行為變量相對(duì)的附加碼的值.表21二重結(jié)構(gòu)的編碼……………………附加碼 變量碼 對(duì)某一個(gè)的個(gè)體的編碼時(shí)，第一先按照洗牌的方式隨機(jī)的產(chǎn)生該附加碼，于上行；在之后進(jìn)行隨機(jī)的產(chǎn)生下面一行的變量碼的值（或），這樣所構(gòu)成的一個(gè)個(gè)體二重的結(jié)構(gòu)的編碼.個(gè)體解碼的時(shí)侯，應(yīng)該考慮該約束的條件. 如表所示，依照由左向右的次序，依照次序考慮該變量之附加碼，也就是按照順序進(jìn)行考慮該附加碼是的物件，那么若要處理某一個(gè)物件的時(shí)候，違背了該約束的條件，強(qiáng)制性的使該物件變量值的變?yōu)?，相反，該物件變量值的為1，若全部的物件都被處理,那么即刻停止. 表22 二重結(jié)構(gòu)的編碼……………………附加碼變量解碼值解碼算法步驟如下所示：第1步 i=1 ，sum =0.第2步 若=0，則=0執(zhí)行第4步，否則，執(zhí)行第3步.第3步 若sum+≤b，則=1，否則=0.第4步 i=i+1，若i≤n，返回到第3步，若非如此,即中止.如，對(duì)一個(gè)為變量背包的問(wèn)題，假若隨機(jī)地產(chǎn)生附加碼的序列為4,3,8，1,6,2,5,7，那么此個(gè)體二重的結(jié)構(gòu)編碼的如表23所示. 則它是可行的解，也就是選擇序號(hào)為4,3,1,6的物件. 表23 一個(gè)隨機(jī)的二重的結(jié)構(gòu)的編碼4381625711011000 對(duì)于上面的二重的結(jié)構(gòu)的編碼交叉的操作及變異的操作算子所需要進(jìn)行重新的設(shè)計(jì). 表24所示為兩個(gè)個(gè)體X,Y經(jīng)PMX操作產(chǎn)生兩個(gè)子個(gè)體,的情況.表24 二重的結(jié)構(gòu)的PMH5728164310011010576248131000111071624835110100117428163510