Population-based incremental learning
In computer science and machine learning, population-based incremental learning (PBIL) is an optimization algorithm, and an estimation of distribution algorithm. This is a type of genetic algorithm where the genotype of an entire population (probability vector) is evolved rather than individual members.[1] The algorithm is proposed by Shumeet Baluja in 1994. The algorithm is simpler than a standard genetic algorithm, and in many cases leads to better results than a standard genetic algorithm.[2] [3] [4]
Algorithm
[edit ]In PBIL, genes are represented as real values in the range [0,1], indicating the probability that any particular allele appears in that gene.
The PBIL algorithm is as follows:
- A population is generated from the probability vector.
- The fitness of each member is evaluated and ranked.
- Update population genotype (probability vector) based on fittest individual.
- Mutate.
- Repeat steps 1–4
Source code
[edit ]This is a part of source code implemented in Java. In the paper, learnRate = 0.1, negLearnRate = 0.075, mutProb = 0.02, and mutShift = 0.05 is used. N = 100 and ITER_COUNT = 1000 is enough for a small problem.
publicvoidoptimize(){ finalinttotalBits=getTotalBits(); finaldouble[]probVec=newdouble[totalBits]; Arrays.fill(probVec,0.5); bestCost=POSITIVE_INFINITY; for(inti=0;i<ITER_COUNT;i++){ // Creates N genes finalboolean[][]genes=new[N][totalBits]; for(boolean[]gene:genes){ for(intk=0;k<gene.length;k++){ if(rand_nextDouble()<probVec[k]) gene[k]=true; } } // Calculate costs finaldouble[]costs=newdouble[N]; for(intj=0;j<N;j++){ costs[j]=costFunc.cost(toRealVec(genes[j],domains)); } // Find min and max cost genes boolean[]minGene=null,maxGene=null; doubleminCost=POSITIVE_INFINITY,maxCost=NEGATIVE_INFINITY; for(intj=0;j<N;j++){ doublecost=costs[j]; if(minCost>cost){ minCost=cost; minGene=genes[j]; } if(maxCost<cost){ maxCost=cost; maxGene=genes[j]; } } // Compare with the best cost gene if(bestCost>minCost){ bestCost=minCost; bestGene=minGene; } // Update the probability vector with max and min cost genes for(intj=0;j<totalBits;j++){ if(minGene[j]==maxGene[j]){ probVec[j]=probVec[j]*(1d-learnRate)+ (minGene[j]?1d:0d)*learnRate; }else{ finaldoublelearnRate2=learnRate+negLearnRate; probVec[j]=probVec[j]*(1d-learnRate2)+ (minGene[j]?1d:0d)*learnRate2; } } // Mutation for(intj=0;j<totalBits;j++){ if(rand.nextDouble()<mutProb){ probVec[j]=probVec[j]*(1d-mutShift)+ (rand.nextBoolean()?1d:0d)*mutShift; } } } }
See also
[edit ]References
[edit ]- ^ Karray, Fakhreddine O.; de Silva, Clarence (2004), Soft computing and intelligent systems design, Addison Wesley, ISBN 0-321-11617-8
- ^ Baluja, Shumeet (1994), "Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning", Technical Report, no. CMU–CS–94–163, Pittsburgh, PA: Carnegie Mellon University, CiteSeerX 10.1.1.61.8554
- ^ Baluja, Shumeet; Caruana, Rich (1995), Removing the Genetics from the Standard Genetic Algorithm, Morgan Kaufmann Publishers, pp. 38–46, CiteSeerX 10.1.1.44.5424
- ^ Baluja, Shumeet (1995), An Empirical Comparison of Seven Iterative and Evolutionary Function Optimization Heuristics, CiteSeerX 10.1.1.43.1108