コンピュータサイエンスと機械学習において、集団ベース増分学習（PBIL）は最適化 アルゴリズムであり、分布推定アルゴリズムでもあります。これは遺伝的アルゴリズムの一種であり、個体ではなく集団全体の遺伝子型（確率 ベクトル）を進化させます。 [1]このアルゴリズムは1994年にシュミート・バルージャによって提案されました。このアルゴリズムは標準的な遺伝的アルゴリズムよりも単純であり、多くの場合、標準的な遺伝的アルゴリズムよりも優れた結果をもたらします。[2] [3] [4]
アルゴリズム
PBILでは、遺伝子は[0,1]の範囲の実数値として表され、特定の対立遺伝子がその遺伝子に現れる確率を示します。
PBIL アルゴリズムは次のとおりです。
- 確率ベクトルから集団が生成されます。
- 各メンバーのフィットネスを評価し、順位付けします。
- 最も適合した個体に基づいて集団の遺伝子型 (確率ベクトル) を更新します。
- 変異する。
- 手順1～4を繰り返します
ソースコード
これは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 [] cost = new double [ N ] ; for ( int j = 0 ; j < N ; j ++ ) { cost [ 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 = cost [ 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 ; } } } }
参照
- 分布推定アルゴリズム（EDA）
- 学習分類システム（LCS）
参考文献
- ^ Karray, Fakhreddine O.; de Silva, Clarence (2004),ソフトコンピューティングとインテリジェントシステム設計, Addison Wesley, ISBN 0-321-11617-8
- ^ Baluja, Shumeet (1994)、「人口ベース増分学習：遺伝的探索に基づく関数最適化と競合学習を統合する手法」、技術報告書、CMU–CS–94–163、ピッツバーグ、ペンシルベニア州：カーネギーメロン大学、CiteSeerX 10.1.1.61.8554
- ^ Baluja, Shumeet; Caruana, Rich (1995),標準遺伝的アルゴリズムから遺伝的要素を取り除く, Morgan Kaufmann Publishers, pp. 38– 46, CiteSeerX 10.1.1.44.5424
- ^ Baluja, Shumeet (1995)、「7つの反復的および進化的関数最適化ヒューリスティックスの経験的比較」、CiteSeerX 10.1.1.43.1108
