Инкрементное обучение на основе населения

В информатике и машинном обучении популяционное инкрементальное обучение ( PBIL ) — это алгоритм оптимизации и алгоритм оценки распределения . Это тип генетического алгоритма , в котором генотип всей популяции ( вектор вероятности ) эволюционирует, а не отдельных членов. ^[1] Алгоритм был предложен Шумитом Балуджей в 1994 году. Алгоритм проще стандартного генетического алгоритма и во многих случаях приводит к лучшим результатам, чем стандартный генетический алгоритм. ^{[2] [3] [4]}

Алгоритм

В PBIL гены представлены как действительные значения в диапазоне [0,1], указывающие вероятность того, что какой-либо конкретный аллель появится в этом гене .

Алгоритм PBIL выглядит следующим образом:

1. Популяция формируется из вектора вероятностей.
2. Оценивается и ранжируется физическая подготовка каждого члена.
3. Обновить генотип популяции (вектор вероятности) на основе наиболее приспособленной особи.
4. Мутировать.
5. Повторите шаги 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 [] 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 ; } } } }                                 

Смотрите также

• Алгоритм оценки распределения (EDA)
• Система классификаторов обучения (LCS)

Ссылки

1. Каррей, Фахреддин О.; де Сильва, Кларенс (2004), Мягкие вычисления и проектирование интеллектуальных систем , Эддисон Уэсли, ISBN 0-321-11617-8
2. Балуджа, Шумит (1994), «Популяционно-ориентированное инкрементальное обучение: метод интеграции оптимизации функций на основе генетического поиска и конкурентного обучения», Технический отчет , № CMU–CS–94–163, Питтсбург, Пенсильвания: Университет Карнеги-Меллона, CiteSeerX 10.1.1.61.8554 
3. Балуджа, Шумит; Каруана, Рич (1995), Удаление генетики из стандартного генетического алгоритма , Morgan Kaufmann Publishers, стр. 38–46, CiteSeerX 10.1.1.44.5424 
4. Балуджа, Шумит (1995), Эмпирическое сравнение семи итеративных и эволюционных эвристик оптимизации функций , CiteSeerX 10.1.1.43.1108