Solutions of Subset Sum and OneMax problems by UMDA, PBIL and
GA

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 a_{i}'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={X_{1},X_{2},...,X_{n})
is a binary-coded string where if X_{i} 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(X_{i},t)
be the probability of X_{i}at generation t. The
probability is updated as follows:
UMDA: P(X_{i},t+1)=Q(X_{i},t),
PBIL: P(X_{i},t+1)=P(X_{i},t)*(1-ALPHA)+Q(X_{i},t)*ALPHA,
where Q(X_{i},t) is the marginal distribution of X_{i} and
ALPHA is the learning rate of PBIL. Q(X_{i},t) is calculated
from the M selected parents at generation t as follows: Q(X_{i},t)=(X_{1i}+X_{2i}+...+X_{Mi})/M
where X_{ji} 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(X_{i},0) is 0.5.

Offspring generation in EDA (UMDA and PBIL):
The value of each bit is generated as follows: X_{i}=1 if P(X_{i},t)>=r X_{i}=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.