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

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:

  1. A population is generated from the probability vector.
  2. The fitness of each member is evaluated and ranked.
  3. Update population genotype (probability vector) based on fittest individual.
  4. Mutate.
  5. Repeat steps 1–4

Source code

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.

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++) {
        // Creates N genes
        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;
            }
        }

        // Calculate costs
        final double[] costs = new double[N];
        for (int j = 0; j < N; j++) {
            costs[j] = costFunc.cost(toRealVec(genes[j], domains));
        }

        // Find min and max cost genes
        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];
            }
        }

        // Compare with the best cost gene
        if (bestCost > minCost) {
            bestCost = minCost;
            bestGene = minGene;
        }

        // Update the probability vector with max and min cost genes
        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;
            }
        }

        // Mutation
        for (int j = 0; j < totalBits; j++) {
            if (rand.nextDouble() < mutProb) {
                probVec[j] = probVec[j] * (1d - mutShift) +
                        (rand.nextBoolean() ? 1d : 0d) * mutShift;
            }
        }
    }
}
gollark: As well as having special casing for stuff, it often is just pointlessly hostile to abstracting anything:- lol no generics- you literally cannot define a well-typed `min`/`max` function (like Lua has). Unless you do something weird like... implement an interface for that on all the builtin number types, and I don't know if it would let you do that.- no map/filter/reduce stuff- `if err != nil { return err }`- the recommended way to map over an array in parallel, if I remember right, is to run a goroutine for every element which does whatever task you want then adds the result to a shared "output" array, and use a WaitGroup thingy to wait for all the goroutines. This is a lot of boilerplate.
gollark: It also does have the whole "anything which implements the right functions implements an interface" thing, which seems very horrible to me as a random change somewhere could cause compile errors with no good explanation.
gollark: - `make`/`new` are basically magic- `range` is magic too - what it does depends on the number of return values you use, or something. Also, IIRC user-defined types can't implement it- Generics are available for all of, what, three builtin types? Maps, slices and channels, if I remember right.- `select` also only works with the built-in channels- Constants: they can only be something like four types, and what even is `iota` doing- The multiple return values can't be used as tuples or anything. You can, as far as I'm aware, only return two (or, well, more than one) things at once, or bind two returns to two variables, nothing else.- no operator overloading- it *kind of* has exceptions (panic/recover), presumably because they realized not having any would be very annoying, but they're not very usable- whether reading from a channel is blocking also depends how many return values you use because of course
gollark: What, you mean no it doesn't have weird special cases everywhere?
gollark: It pretends to be "simple", but it isn't because there are bizarre special cases everywhere to make stuff appear to work.

See also

References
  1. Karray, Fakhreddine O.; de Silva, Clarence (2004), Soft computing and intelligent systems design, Addison Wesley, ISBN 0-321-11617-8
  2. Baluja, Shumeet (1994), "Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning", Technical Report, Pittsburgh, PA: Carnegie Mellon University (CMU–CS–94–163), CiteSeerX 10.1.1.61.8554
  3. 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
  4. Baluja, Shumeet (1995), An Empirical Comparison of Seven Iterative and Evolutionary Function Optimization Heuristics, CiteSeerX 10.1.1.43.1108
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.