• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 12,  comments - 54,  trackbacks - 0
            基因交叉,或者基因重組,就是把兩個(gè)父體部分結(jié)構(gòu)加以替換,生成新的個(gè)體的操作,習(xí)慣上對(duì)實(shí)數(shù)編碼的操作叫做重組(Recombination),對(duì)二進(jìn)制編碼的操作稱(chēng)為交叉(crossover)。

            比較常用的一些算法介紹如下:
            1. 重組算法(Recombination)
             實(shí)值重組產(chǎn)生子個(gè)體一般是用下邊這個(gè)算法:
             子個(gè)體=父?jìng)€(gè)體1 + a × ( 父?jìng)€(gè)體2 - 父?jìng)€(gè)體1 )
            這里a是一個(gè)比例因子,可以由[ -d, 1+d] 上邊服從均勻分布的隨機(jī)數(shù)產(chǎn)生。
            不同的重組算法,a的取值是不同的,一般來(lái)講,d=0.25是一個(gè)比較好的選擇。
            下邊一段c++代碼片斷,實(shí)現(xiàn)一個(gè)中值重組算法,其中d取值為0。

             1 /*
             2 Gene Crossover Algorithm
             3 Linear Recombination Xover Algorithm
             4 
             5 A crossover operator that linearly combines two parent
             6 chromosome vectors to produce two new offspring a
             7 ccording to the following equations:
             8 
             9 Offspring1 = a * Parent1 + (1- a) * Parent2
            10 Offspring2 = (1 – a) * Parent1 + a * Parent2
            11 
            12 
            13 where a is a random weighting factor (chosen before each
            14 crossover operation).
            15 
            16 Consider the following 2 parents (each consisting of 4
            17 float genes) which have been selected for crossover:
            18 
            19 Parent 1: (0.3)(1.4)(0.2)(7.4)
            20 Parent 2: (0.5)(4.5)(0.1)(5.6)
            21 
            22 If a = 0.7, the following two offspring would be produced:
            23 
            24 Offspring1: (0.36)(2.33)(0.17)(6.86)
            25 Offspring2: (0.402)(2.981)(0.149)(6.842)
            26 */
            27 template< class GENE >
            28 class Intermediate_Recombination_Gene_Crossover_Algorithm
            29 {
            30     public:
            31             void operator()( GENE& g1, GENE& g2 )const
            32             {
            33                 assert( g1.Upper == g2.Upper );
            34                 assert( g1.Lower == g2.Lower );
            35 
            36                 const long double Ran = ran();
            37                 const long double sum = g1.Value + g2.Value;
            38 
            39                 if ( sum < g1.Upper )
            40                 {
            41                     g1.Value = Ran * sum;
            42                     g2.Value = sum - g1.Value;
            43                 }
            44                 else
            45                 {
            46                     const long double sub = 2.0L * g1.Upper - sum;
            47                     g1.Value = g1.Upper - sub * Ran;
            48                     g2.Value = g1.Upper - sub + sub * Ran;
            49                 }
            50             }
            51 };

            2.  交叉算法
            如上文遺傳算法中的數(shù)據(jù)結(jié)構(gòu)中所講,基因的二進(jìn)制編碼有直接編碼(Normal)和Gray編碼之分,以下所說(shuō)算法,均適用于這兩種算法。

            假設(shè)基因的二進(jìn)制編碼長(zhǎng)度為N,那么這些編碼之間有N-1個(gè)空隙,可供交叉使用。
            二進(jìn)制交叉算法就是
            如何選擇空隙,選擇多少個(gè)空隙。
            以下將各走極端的選擇一個(gè)空隙交叉的單點(diǎn)交叉算法,和選擇N-1個(gè)空隙進(jìn)行交叉的洗牌交叉算法大致說(shuō)一下。

            (1) 單點(diǎn)交叉
            在二進(jìn)制編碼中,隨機(jī)選擇一個(gè)點(diǎn),以這個(gè)點(diǎn)為界限,相互交換變量。

            父?jìng)€(gè)體1      011111110000000000
            父?jìng)€(gè)體2      000000001111111111
            如粗體前邊位置為所選擇的交叉點(diǎn),那么生成的子個(gè)體為:
            子個(gè)體1      011111111111111111
            子個(gè)體2      000000000000000000
            以下為c++實(shí)現(xiàn),采用Gray編碼,直接編碼的類(lèi)似。
             1 /*
             2 Gene crossover algorithm
             3 One Point Crossover using Gray binary encoding
             4 
             5 A crossover operator that randomly selects a crossover point
             6 within a chromosome then interchanges the two parent chromosomes
             7 at this point to produce two new offspring.
             8 
             9 Consider the following 2 parents which have been selected for
            10 crossover. The “|” symbol indicates the randomly chosen
            11 crossover point.
            12 
            13 Parent 1: 11001|010
            14 Parent 2: 00100|111
            15 
            16 After interchanging the parent chromosomes at the crossover
            17 point, the following offspring are produced:
            18 
            19 Offspring1: 11001|111
            20 Offspring2: 00100|010
            21 */
            22 template< class GENE >
            23 class Gray_Binary_Single_Point_Xover_Gene_Crossover_Algorithm
            24 {
            25     public:
            26             void operator()( GENE& g1, GENE& g2 )const
            27             {
            28                 encoding( g1 );
            29                 encoding( g2 );
            30                 assert( g1.Binary_Array.size() == g2.Binary_Array.size() );
            31 
            32                 normal2gray( g1 );
            33                 normal2gray( g2 );
            34 
            35                 const unsigned int Pos = static_cast<unsigned int>
            36                                 ( g1.Binary_Array.size() * ran() );
            37 
            38                 for ( unsigned int i = 0; i < Pos; ++i )
            39                 {
            40                     if ( g1.Binary_Array[i] xor g2.Binary_Array[i] )
            41                     {
            42                         if ( g1.Binary_Array[i] )
            43                             {
            44                                 g1.Binary_Array[i] = 0;
            45                                 g2.Binary_Array[i] = 1;
            46                             }
            47                             else
            48                             {
            49                                 g1.Binary_Array[i] = 1;
            50                                 g2.Binary_Array[i] = 0;
            51                             }
            52                     }
            53                 }
            54 
            55                 gray2normal( g1 );
            56                 gray2normal( g1 );
            57                 decoding( g1 );
            58                 decoding( g2 );
            59             }
            60 };
            61 
            62 
            63 

            (2)洗牌交叉
            洗牌交叉就是,將一個(gè)父基因取一半,再上來(lái)自另外一個(gè)父基因的一半,構(gòu)成一個(gè)新的子基因。
            算法代碼如下:

             1 template< class GENE >
             2 class Gray_Binary_Shuffle_Xover_Gene_Crossover_Algorithm
             3 {
             4     public:
             5             void operator()( GENE& g1, GENE& g2 )const
             6             {
             7                 encoding( g1 );
             8                 encoding( g2 );
             9                 assert( g1.Binary_Array.size() == g2.Binary_Array.size() );
            10 
            11                 normal2gray( g1 );
            12                 normal2gray( g2 );
            13 
            14                 const unsigned int Size = g1.Binary_Array.size();
            15 
            16                 for ( unsigned int i = 0; i < Size; ++i )
            17                 {
            18                     if ( ( i & 1&&
            19                          ( g1.Binary_Array[i] xor g2.Binary_Array[i] )
            20                         )
            21                     {
            22                         if ( g1.Binary_Array[i] )
            23                             {
            24                                 g1.Binary_Array[i] = 0;
            25                                 g2.Binary_Array[i] = 1;
            26                             }
            27                             else
            28                             {
            29                                 g1.Binary_Array[i] = 1;
            30                                 g2.Binary_Array[i] = 0;
            31                             }
            32                     }
            33                 }
            34 
            35                 gray2normal( g1 );
            36                 gray2normal( g1 );
            37                 decoding( g1 );
            38                 decoding( g2 );
            39             }
            40 };
            41 
            42 

            3.  另外的一些代碼
            (1)群體中的交叉算法
            將經(jīng)過(guò)選擇考驗(yàn)的個(gè)體放入一個(gè)群體,當(dāng)放入的個(gè)體數(shù)量達(dá)到要求后,對(duì)里邊的個(gè)體進(jìn)行兩兩交叉。

             1 //Population Crossover Algorithm
             2 //1. get the number of Chromosomes in the Population
             3 //2. get the number of Gens in a Chromosome
             4 //3. generate a random number
             5 //4. if the random number is bigger than the probability, skip
             6 //5. if the selected two genes are of the same value, skip
             7 //6. crossover the two genes using the selected Gene crossover algorithm
             8 template< class POPULATION, class GENE_CROSSOVER_ALGORITHM >
             9 class Population_Crossover_Algorithm
            10 {
            11     public:
            12         void operator()( POPULATION& population ) const
            13         {
            14             //1
            15             const unsigned int C_Size = population.Chromosome_Array.size();
            16             assert( C_Size > 1 );
            17 
            18             //2
            19             const unsigned int G_Size = population.Chromosome_Array[0].Gene_Array.size();
            20 
            21             for ( unsigned int i = 0; i < C_Size / 2++i )
            22             {
            23                 for( unsigned int j = 0; j < G_Size; ++j )
            24                 {
            25                     //3
            26                     const long double Ran = ran();
            27                     //4
            28                     if ( Ran > population.Crossover_Probability )
            29                         continue ;
            30                     //5
            31                     if ( population.Chromosome_Array[i].Gene_Array[j].Value ==
            32                          population.Chromosome_Array[C_Size-i-1].Gene_Array[j].Value
            33                         )
            34                         continue;
            35                     //6
            36                     crossover(
            37                             population.Chromosome_Array[i].Gene_Array[j],
            38                             population.Chromosome_Array[C_Size-i-1].Gene_Array[j],
            39                             GENE_CROSSOVER_ALGORITHM()
            40                                 );
            41                 }
            42             }
            43         }
            44 };




            (2) 交叉函數(shù)定義
            種群的交叉只涉及一個(gè)交叉主體,而基因/個(gè)體的交叉涉及兩個(gè)交叉主體,定義如下:

             1 //Population crossover only
             2 template<class POPULATION, class ALGORITHM>
             3 void crossover( POPULATION& p,          //the Population to perform crossover
             4                 const ALGORITHM& a )    //the Algorithm used for the crossover
             5 {
             6     assert( p.Chromosome_Array.size() > 1 );
             7     a( p );
             8 }
             9 
            10 
            11 //gene crossover algorithm
            12 template<class GENE, class ALGORITHM>
            13 static void crossover(  GENE &g1,               //Gene1 to perform crossvoer
            14                         GENE &g2,               //Gene2 to perform crossvoer
            15                         const ALGORITHM& a )    //the Algorithm employed
            16 {
            17     a( g1, g2 );
            18 }
            19 




            posted on 2008-06-18 15:56 Wang Feng 閱讀(12056) 評(píng)論(1)  編輯 收藏 引用 所屬分類(lèi): Numerical C++

            FeedBack:
            # re: 遺傳算法系列 (3) 交叉算法
            2010-02-12 00:32 | hello
            請(qǐng)教:“洗牌交叉”如果按該文的代碼,和單點(diǎn)交叉又有何區(qū)別呢?
            “洗牌交叉”應(yīng)該在交叉之前在父代中有shuffle運(yùn)算,交叉后在子代中有unshuffle運(yùn)算,但不知道是如何進(jìn)行的,作者如有知曉,不吝賜教,謝謝:)
            email: hwei2007@qq.com  回復(fù)  更多評(píng)論
              

            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(4)

            隨筆分類(lèi)

            隨筆檔案

            Link List

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久免费小视频| 久久青草国产手机看片福利盒子 | 国产三级精品久久| 久久久老熟女一区二区三区| 青青久久精品国产免费看| 狠狠色丁香婷婷综合久久来来去| 久久99国内精品自在现线| 性欧美大战久久久久久久久| 久久无码高潮喷水| 欧美精品丝袜久久久中文字幕| 亚洲欧洲久久av| 国产精品国色综合久久| 久久综合九色综合欧美就去吻| 97久久精品人人做人人爽| 99久久99这里只有免费费精品| 久久久久久无码Av成人影院| 久久婷婷五月综合色奶水99啪| 久久偷看各类wc女厕嘘嘘| 精品国产一区二区三区久久久狼| 久久精品九九亚洲精品| 国产精品一区二区久久| 岛国搬运www久久| 久久久久这里只有精品| 久久这里都是精品| 亚洲AV无码久久精品成人| 久久丫精品国产亚洲av| 99久久99久久精品国产| 久久乐国产精品亚洲综合| 久久丫忘忧草产品| .精品久久久麻豆国产精品 | 久久久精品人妻一区二区三区蜜桃 | 日本强好片久久久久久AAA| 久久国产精品无码一区二区三区| 狠色狠色狠狠色综合久久| 精品人妻伦九区久久AAA片69 | 久久综合九色综合网站| 中文字幕久久欲求不满| 久久综合久久美利坚合众国| 97精品伊人久久大香线蕉app| 久久精品国产欧美日韩| 囯产极品美女高潮无套久久久|