Solutions of Subset Sum and OneMax problems by UMDA, PBIL and GA
Either the browser has disabled running ActiveX controls containing the Java Applet OR this browser does not have a Java Plug-in installed.
Download the latest version of Java Plug-in.
Description of the Software: The objective of this demo is to show how UMDA, PBIL and GA perform on the onemax and the subset sum problems. Download this software for offline browsing.

Definition of Subset Sum Problem: The problem of finding which subset of a list of integers has a given sum. The subset sum is an integer relation problem where the relation coefficients ai's are 0 or 1.

Definition of One Max Problem: It is a very simple problem in which the objective is to maximize the number of ones in an individual. An optimal solution consists of all ones in the individual.

Encoding of the problem: Each individual X={X1,X2,...,Xn) is a binary-coded string where if Xi is 1, the corresponding number of the set of numbers are selected. If there are n numbers in the set, each individual is an n-bit binary string.

Fitness calculation: The absolute difference between the expected sum and the sum of the numbers selected in an individual is used as fitness. Therefore, the optimum fitness is zero. However, during the drawing of the graph of the fitness of an individual, the natural logarithm of (fitness+1) is used.

BUG: The Stop button does not work. Some texts may overlaps due to font's problem.  

Steps in running the software:
Step 1. Enter the Number of Data (n). The default value is 500.
Step 2. Choose the type of the numbers: random numbers (0~1500), sequential numbers (1~n), odd numbers, even numbers or one max (all 1's for one max problem).
Step 3. Enter the expected sum by clicking Random Sum or putting the sum directly. If you do not provide any number, a random sum will be used. A random sum is generated by randomly picking some numbers from the set of numbers, and it is done to ensure that a solution always exists.
Step 4. Enter the values of different GA/EDA parameters.
Step 5. Run the method of your choice. For a given set of numbers, you can run different methods many times. If you need to clear the graphs, simply click Clear Graph.

Probability update in UMDA and PBIL: Let P(Xi,t) be the probability of Xi at generation t. The probability is updated as follows:
UMDA: P(Xi,t+1)=Q(Xi,t),
PBIL: P(Xi,t+1)=P(Xi,t)*(1-ALPHA)+Q(Xi,t)*ALPHA,
where Q(Xi,t) is the marginal distribution of Xi and ALPHA is the learning rate of PBIL. Q(Xi,t) is calculated from the M selected parents at generation t as follows: Q(Xi,t)=(X1i+X2i+...+XMi)/M  where Xji is the value of the bit i at selected parent j. Note here that if ALPHA=1, PBIL turns out to be a UMDA. The initial probability P(Xi,0) is 0.5. 

Offspring generation in EDA (UMDA and PBIL):
The value of each bit is generated as follows:
Xi=1 if P(Xi,t)>=r
Xi=0, otherwise;
where r is a random number.

Selection of parents:
For genetic algorithm, fitness proportionate selection method is used to select parents for crossover and mutation. However, for EDAs, truncation selection method is used. In truncation selection method, the best TAU*N (=population size) parents are selected for estimation of marginal distribution.

Replacement strategy:
Elitism is used to generate new population from old population and the new offspring with elite size=1, i.e., the best individual of the previous generation survives for the next generation.

For further reading:

Topon Kumar Paul and Hitoshi Iba , “Optimization in continuous domain by real-coded estimation of distribution algorithm,” in Design and Application of Hybrid Intelligent Systems, A. Abraham, M. Köppen, and K. Franke, Eds. The Netherlands: IOS Press, 2003, pp. 262–271.

Topon Kumar Paul and Hitoshi Iba, “Real-coded estimation of distribution algorithm,” in Proceedings of the Fifth Metaheuristics International Conference (MIC2003), Kyoto, Japan, 2003, pp. 60-1 to 60-6.

Topon Kumar Paul and Hitoshi Iba, “Reinforcement learning estimation of distribution algorithm,” in Proceedings of GECCO2003, ser. Lecture Notes in Computer Science (LNCS) 2724. Springer-Verlag, 2003, pp. 1259–1270.

Topon Kumar Paul and Hitoshi Iba, “Linear and combinatorial optimizations by estimation of distribution algorithms,” in Proceedings of the 9th MPS Symposium on Evolutionary Computation. IPSJ, 2003, pp. 99–106.

BibTeX entry:
@MANUAL{paul:2006:edasoft,
author = "Topon Kumar Paul",
title = "Solutions of Subset Sum and OneMax problems by UMDA, PBIL and GA",
year = "2006",
note = "Software available at http://www.iba.k.u-tokyo.ac.jp/english/"
}

Copyright@2006, Topon Kumar Paul, Iba Laboratory, The University of Tokyo. All rights reserved. Last update: November 01, 2006 12:08:12 PM.
Contact: iba@ibalab, topon@ibalab. ibalab=iba.k.u-tokyo.ac.jp The software is optimized for IE6.0 or above and Fire Fox 2.0 or above.