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 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: Offspring generation in EDA (UMDA and PBIL): Selection of parents: Replacement strategy: 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. BibTeX entry: Copyright@2006, Topon Kumar Paul, Iba
Laboratory, The University of Tokyo. All rights reserved. Last update:
November 01, 2006 12:08:12 PM. |