Loading article…
コンピュータサイエンスと機械学習において、集団ベース増分学習（PBIL）は最適化アルゴリズムであり、分布推定アルゴリズムです。これは、個々のメンバーではなく、集団全体（確率ベクトル）の遺伝子型が進化するタイプの遺伝的アルゴリズムです。 [ 1 ]このアルゴリズムは、1994 年に Shumeet Baluja によって提案されました。このアルゴリズムは、標準的な遺伝的アルゴリズムよりも単純であり、多くの場合、標準的な遺伝的アルゴリズムよりも優れた結果をもたらします。[ 2 ] [ 3 ] [ 4 ]
PBILでは、遺伝子は[0,1]の範囲の実数値で表され、特定の対立遺伝子がその遺伝子に現れる確率を示します。
PBILアルゴリズムは以下のとおりです。
これはJavaで実装されたソースコードの一部です。論文では、learnRate = 0.1、negLearnRate = 0.075、mutProb = 0.02、mutShift = 0.05が使用されています。N = 100、ITER_COUNT = 1000は、小規模な問題には十分です。
public void optimize () { final int totalBits = getTotalBits (); final double [] probVec = new double [ totalBits ] ; Arrays.fill ( probVec , 0.5 ); bestCost = POSITIVE_INFINITY ; for ( int i = 0 ; i < ITER_COUNT ; i ++ ) { // N個の遺伝子を作成final boolean [ ][] genes = new [ N ][ totalBits ] ; for ( boolean [ ] gene : genes ) { for ( int k = 0 ; k < gene.length ; k ++ ) { if ( rand_nextDouble ( ) < probVec [ k ] ) gene [ k ] = true ; } }// コストを計算するfinal double [] costs = new double [ N ] ; for ( int j = 0 ; j < N ; j ++ ) { costs [ j ] = costFunc . cost ( toRealVec ( genes [ j ] , domains )); }// 最小コスト遺伝子と最大コスト遺伝子を見つけるboolean [] minGene = null , maxGene = null ; double minCost = POSITIVE_INFINITY , maxCost = NEGATIVE_INFINITY ; for ( int j = 0 ; j < N ; j ++ ) { double cost = costs [ j ] ; if ( minCost > cost ) { minCost = cost ; minGene = genes [ j ] ; } if ( maxCost < cost ) { maxCost = cost ; maxGene = genes [ j ] ; } }// 最もコストの低い遺伝子と比較するif ( bestCost > minCost ) { bestCost = minCost ; bestGene = minGene ; }// 最大コスト遺伝子と最小コスト遺伝子で確率ベクトルを更新しますfor ( int j = 0 ; j < totalBits ; j ++ ) { if ( minGene [ j ] == maxGene [ j ] ) { probVec [ j ] = probVec [ j ] * ( 1d - learnRate ) + ( minGene [ j ] ? 1d : 0d ) * learnRate ; } else { final double learnRate2 = learnRate + negLearnRate ; probVec [ j ] = probVec [ j ] * ( 1d - learnRate2 ) + ( minGene [ j ] ? 1d : 0d ) * learnRate2 ; } }// 突然変異for ( int j = 0 ; j < totalBits ; j ++ ) { if ( rand . nextDouble () < mutProb ) { probVec [ j ] = probVec [ j ] * ( 1d - mutShift ) + ( rand . nextBoolean () ? 1d : 0d ) * mutShift ; } } } }