laster - genetic algorithm backpack problem solver
laster [--help] [--size <sz>] [--all] [--dumpf <f>] [--nooss] [--eff <p>] [--iter <n>] file0 [file1 ...]
Type short help instructions regarding usage and default values.
Specify target size for optimization. K,M,G suffixes are recognized, kilo, mega and gigabytes.
Process all files, generate multiple volumes. The results for each medium are separated by single newline.
Dump optimization progress into file f. Fitness coefficient of each iteration is written. The output is suitable for drawing in gnuplot.
Do not try to generate optimal starting solution. With this option the algorithm starts with very bad starting solution.
Set efficiency limit 0 <= e <= 1. The algorithm ends whenever fitness coefficient reaches value of e.
Specify maximal number of iterations.
Solution of the backpack problems lies in finding suitable combination of objects which fit into a limited space so that the used capacity is highest possible. Laster works with files and directories which shall be written on a medium.
laster --size=1.44M /usr/bin/*
This command tries to find the best combination of files and directories from /usr/bin which would fit best on a 1.44MB floppy.
First, after removing objects which are too large and exceed target capacity, a starting optimal solution is generated which is then processed with a loop performing optimizations on GA basis. The program works with array of 100 solution candidates. Each single solution candidate contains an array of items with value of 1, if the object is considered in the backpack, or 0 if not.
Optimal starting solution, unless --nooss is specified, is generated as 100 starting solution candidates with knowledge of target media capacity and total size of all processed files and directories. Sample candidate's backpack vector is then generated randomly, generating random float number from the interval [0;1] and to each respective object assigning 1 if the random number is lower than computed weight (backpack capacity/total weight of all objects ratio) and vice-versa. The first candidate has vector (1,0,0,...). This is to ensure at least one acceptable solution and to forego possible algorithm divergence in case that all starting solution were unacceptable.
The fitness coefficient ratio of sum of all items in backpack vector and target capacity. If a solution candidate exceeds the target capacity, its fitness is set to 0.
Before every genetic iteration, fitness coefficients are computed for every solution candidate. If the fitness of the best candidate reached minimal required fitness, the algorithm ends.
The list of candidates is sorted and the worse half of it as well as all candidates with zero fitness are released. The best candidates are the iteratively copied on free space and mutated. Because the best solution stays alway on top and is always acceptable, the algorithm converges and in the next step of iteration returns equal or better solution.
Thanks to good optimal starting solution finding method, even the initial solution is often usable, and even without it (--nooss) the GA iterative kill/mutate algorithm converges very quickly and for its purpose achieves excellent results in very short even with high number of input objects which were already unsolvable for non-GA recursive algorithm implementation.
The mutation function is simple process which sets 5% of randomly selected items (but at least 1) to 1 and 5% of randomly selected items (but at least 1) to 0 (further values of selected items could already be 1 or 0 respectively). This quantity showed to be adequate and provides fast convergence.
Ondra Havel <ondra.havel@gmail.com>