【正文】 9 3）首先，兩交叉點在它們的中間段進行交換，得到： ： （x x x| 1 8 7 6| x x） ： （x x x|4 5 6 7| x x）其中x表示暫時未進行定義的編碼，得到： 1←→4,8←→5,7←→6,6←→7然后，對兩個個體中的x部分，保留鄉(xiāng)村碼2,3,9，得到： ： （x 2 3| 1 8 7 6| x 9） ： （x x 2|4 5 6 7| 9 3）最后，對上面的子個體1中的第一個x，來用最初的父碼1，由1←→4交換之后得到了首個為4，如此操作，子個體2的次個，來用最初的父碼8，由8←→，即為備選的交換有許多個碼，那么便選擇此前的未確定的某個碼來為交換. 如此進行，最后得到的子個體是： ： （4 2 3| 1 8 7 6| 5 9） ： （1 8 2| 4 5 6 7| 9 3）順序交叉對于下面的表示，任意選擇兩個交叉點“|”. ： （1 2 3| 4 5 6 7| 8 9） ： （4 5 2| 1 8 7 6| 9 3）首先，保存在兩交叉點之間的中間的段,并且不改變，得到： ： （x x x| 4 5 6 7| x x） ： （x x x|1 8 7 6| x x）然后，記錄并提取父個體2由第二個的交叉點1初始排列的順序，從到達表尾的時刻，向表頭返回繼續(xù)的對鄉(xiāng)村碼記錄，到達了第二個的交叉點便結(jié)束，這樣就能得到了自從第二個的交叉點初始的排列的順序是的父個體2. 其中父個體1，已經(jīng)有的鄉(xiāng)村碼有，將它們?nèi)サ簦軌虻玫降拇涡蚩梢允?3218，然后復制這個排列的順序到父個體1，復制的起點也就是由第二個的交叉的點初始，子個體1可以通過這種方法生成為： ： （2 1 8 4 5 6 7 9 3）同時，產(chǎn)生的子個體2為： ： （3 4 5 1 8 7 6 9 2）循環(huán)交叉下面的兩個的父個體： ： （1 2 3 4 5 6 7 8 9） ： （4 1 2 8 7 6 9 3 5）先從父個體1中取的首個鄉(xiāng)村碼，對子個體1進行生成： ： （1 x x x x x x x x）子個體從任一一個父個體相同的位置中取出，因為父個體2里面與父個體1里面的首個的鄉(xiāng)村碼1相對鄉(xiāng)村碼是4，所以決定得子個體1里面的第4的鄉(xiāng)村碼是4： ： （1 x x 4 x x x x x）接下來，選出鄉(xiāng)村碼是4相對于父個體的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）同樣，可有子個體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)系. 下面的兩父個體的表示： （1 2 3 4 5 6 7 8 9） （4 1 2 8 7 6 9 3 5）對每一鄉(xiāng)村來說其邊表為： 鄉(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 ；子個體生成需要從子個體首個的鄉(xiāng)村碼的選擇初始，可以進行隨機選擇任意兩父個體首個的鄉(xiāng)村碼. 已選的鄉(xiāng)村邊表之中的所有的鄉(xiāng)村的對應的邊表當中邊數(shù)為最少鄉(xiāng)村碼需要成為下個的鄉(xiāng)村碼，若含有的邊表邊數(shù)相等，可從里面隨機的挑選鄉(xiāng)村碼. ，從里面選擇其中的一個鄉(xiāng)村當做是下個的鄉(xiāng)村碼，其中，鄉(xiāng)村9邊表的長是4，同時鄉(xiāng)村2以及鄉(xiāng)村4邊表的長都是3，然后，那么第三個的鄉(xiāng)村碼就需由鄉(xiāng)村4的邊表中所列鄉(xiāng)村3和鄉(xiāng)村5中產(chǎn)生，由于鄉(xiāng)村3的邊表長為4. 鄉(xiāng)村5邊表長為3，因此，可以獲得一個字體：（1 4 5 6 7 8 2 3 9） 操作中可能存在邊失敗的問題，即中間對應的邊表所列鄉(xiāng)村，在該步之間已經(jīng)都進入了選擇，在ER操作中不再保留父個體中共同部分的序列[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的操作中所子個體產(chǎn)生時，. 遺傳算法在背包問題中的應用 背包問題概述 背包問題事實上就是一個規(guī)劃的問題的數(shù)學模型. 如若有n個物件，它的重量用來進行表示，價值為（），定義的變量應為=1，它的數(shù)學的模型的表示： （216） （217）或1,；j=1，…，n上式中，均為正值. 二重結(jié)構(gòu)的編碼的遺傳算法二重結(jié)構(gòu)的編碼的方法如表21所示. ,下面一行為變量相對的附加碼的值.表21二重結(jié)構(gòu)的編碼……………………附加碼 變量碼 對某一個的個體的編碼時，第一先按照洗牌的方式隨機的產(chǎn)生該附加碼，于上行；在之后進行隨機的產(chǎn)生下面一行的變量碼的值（或），這樣所構(gòu)成的一個個體二重的結(jié)構(gòu)的編碼.個體解碼的時侯，應該考慮該約束的條件. 如表所示，依照由左向右的次序，依照次序考慮該變量之附加碼，也就是按照順序進行考慮該附加碼是的物件，那么若要處理某一個物件的時候，違背了該約束的條件，強制性的使該物件變量值的變?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步，若非如此,即中止.如，對一個為變量背包的問題，假若隨機地產(chǎn)生附加碼的序列為4,3,8，1,6,2,5,7，那么此個體二重的結(jié)構(gòu)編碼的如表23所示. 則它是可行的解，也就是選擇序號為4,3,1,6的物件. 表23 一個隨機的二重的結(jié)構(gòu)的編碼4381625711011000 對于上面的二重的結(jié)構(gòu)的編碼交叉的操作及變異的操作算子所需要進行重新的設(shè)計. 表24所示為兩個個體X,Y經(jīng)PMX操作產(chǎn)生兩個子個體,的情況.表24 二重的結(jié)構(gòu)的PMH5728164310011010576248131000111071624835110100117428163510101011交叉點1 交叉點2對于操作時產(chǎn)生的變異,，對于父個體的隨機的選擇有兩個變異點，兩個點間上行的附加碼應該按照相反的順序進行重新的排列，而下行的變量碼順序不變.表25 二重結(jié)構(gòu)的逆位的變異72614853100110107258416310011010 交叉點1 交叉點2 模擬結(jié)果結(jié)合實例將基本的遺傳算法SGA