Solving the 'Optimal Coin Denomination Problem' using Genetic Algorithms

Author: Thomas Egerer (formerly Washeim)

e-mail: thomas.washeim@gmx.net

Table of Contents

Introduction

Paying your bill in a shop can annoying: you have to pay $3.74 but you only got $3.55 in small change on you (this might be one reason why most people do not pay cache). It gets worse: even if you have sufficiently enough change, trying to find the smallest number of coins to make the change isn't as easy as you might expect. But the worst thing of all is that, assuming you have found the combination to make the change with the smallest number of coins, and you happen to have all the coins required to make that change: with all coin systems currently used on Earth there would be a way to use even less coins. For truth's sake it must be admitted that this is only partially correct. Some amounts like for example 1¢ cannot be made of a smaller amount of coins than one. The point is that for all coin systems present by now there are systems that on average use less coins to make all amounts of change.

This paper deals with the problem of finding the optimal denomination for coins to make change for all amounts possible from 0¢ through 99¢. Even though this problem has been addressed before ([1]) the approach used is somewhat different. This time the problem will be solved using Genetic Algorithms. The purpose of this document is solely theoretical; it is not aimed at any governmental authority with the expectation to change the denominations of the coins currently in use. It is meant to proove that the author is capable of applying the knowledge gained during the class 'Genetic Algorithms' to solve a (somewhat) practical problem.

Mathematical Background

This chapter is meant to briefly describe the mathematical ideas behind the coin denomination problem. Basic formulas, variable names etc. are almost identical to [1].

Variables

We define the following variables to describe our problem:

D ... number of coins in a set of coins, D∈N (N > 0)

T ... set of D coins {e1, e2, ..., eD} with e1 < e2 < ... < eD

V ... natural number, to be be expressed by V=Σ1≤i≤Dai*ei

L ... upper limit for V;

S ... Σ1≤i≤Dai for a particular V (i.e. number of coins required to make a change of V)

C ... Σ0≤n≤LSi for the total number of coins to make up all change from 0¢ to L¢.

We need to find individuals (a1, a2, ..., aD) such that S becomes minimal; We denote opt(V; e1, e2, ..., De) to be the optimal representation of V for the set of coins {e1, e2, ..., eD}

The optimal denomination problem

The optimal denomination problem tries to find a set of coins {e1, e2, ..., eD}, such that

C=Σ0≤n≤L opt(n; e1, e2, ..., eD)

becomes minimal. We need to make sure to have at least the 1¢ coin to be present in the set. If the smallest coin was not the 1¢ coin it was impossible to make certain amounts of change. For example, if the smallest coin was the 2¢ coin we would miss all odd amounts.

Informally speaking what we try to find is a set of D coins that make the change for all amounts from 0 to L with the minimum amount of coins. The following example will illustrate the problem:

Let's say we have a set of D=2 coins and want to limit the amounts of change to L=99. We now want to find the set T={e1, e2} that solves the minimal denomination problem for this example. We already know that e1 must be 1¢. For the remaining e2 we must choose from the set [2;9]. In this simple example we can try all combinations:

e2     total cost C using e2                                             
 2     C= 1 + 1 + 2 + 2 + 3 + 3 + ... + 47 + 48 + 48 + 49 + 49 + 50 = 2500
 3     C= 1 + 2 + 1 + 2 + 3 + 2 + ... + 32 + 33 + 32 + 33 + 34 + 33 = 1716
 4     C= 1 + 2 + 3 + 1 + 2 + 3 + ... + 25 + 26 + 24 + 25 + 26 + 27 = 1350
 5     C= 1 + 2 + 3 + 4 + 1 + 2 + ... + 22 + 19 + 20 + 21 + 22 + 23 = 1150
 6     C= 1 + 2 + 3 + 4 + 5 + 1 + ... + 19 + 20 + 16 + 17 + 18 + 19 = 1030
 7     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 16 + 17 + 18 + 19 + 14 + 15 =  960
 8     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 17 + 18 + 12 + 13 + 14 + 15 =  918
 9     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 14 + 15 + 16 + 17 + 18 + 11 =  902
10     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 13 + 14 + 15 + 16 + 17 + 18 =  900
11     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 14 + 15 + 16 + 17 + 18 +  9 =  900
12     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 17 + 18 +  8 +  9 + 10 + 11 =  902
13     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 10 + 11 + 12 + 13 + 14 + 15 =  918
14     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 16 + 17 + 18 + 19 +  7 +  8 =  946
15     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 10 + 11 + 12 + 13 + 14 + 15 =  960
16     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 19 + 20 +  6 +  7 +  8 +  9 =  990
17     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 14 + 15 + 16 + 17 + 18 + 19 = 1030
18     C= 1 + 2 + 3 + 4 + 5 + 6 + ... +  9 + 10 + 11 + 12 + 13 + 14 = 1040
19     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 22 +  5 +  6 +  7 +  8 +  9 = 1080
20     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 18 + 19 + 20 + 21 + 22 + 23 = 1150
.                                  .                                     .
.                                  .                                     .
.                                  .                                     .
92     C= 1 + 2 + 3 + 4 + 5 + 6 + ... +  3 +  4 +  5 +  6 +  7 +  8 = 4222
93     C= 1 + 2 + 3 + 4 + 5 + 6 + ... +  2 +  3 +  4 +  5 +  6 +  7 = 4306
94     C= 1 + 2 + 3 + 4 + 5 + 6 + ... +  1 +  2 +  3 +  4 +  5 +  6 = 4392
95     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 94 +  1 +  2 +  3 +  4 +  5 = 4480
96     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 94 + 95 +  1 +  2 +  3 +  4 = 4570
97     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 94 + 95 + 96 +  1 +  2 +  3 = 4662
98     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 94 + 95 + 96 + 97 +  1 +  2 = 4756
99     C= 1 + 2 + 3 + 4 + 5 + 6 + ... + 94 + 95 + 96 + 97 + 98 +  1 = 4852

The example's solution are the sets {1, 10} and {1, 11} both with a total cost of 900 and it agrees with Jeffrey Shallit's solution in [1]. Many of the combinations have been omitted because the costs grow continuously starting from e2=11.

As you can see it is quite cumbersome to find the denomination for e2 that best solves the optimal denomination problem just by trying all possible combinations (that is why the above table has actually been calculated using a computer program). Trying all combinations is opportune here, as only 98 of them exist. The next section will go into some more detail concerning the possible combinations - and we will quickly see that 98 is an extremely small number compared to the number of combinations we have if we choose L=29, for example.

Combinatorial aspects

Let us have a quick look at the number of combinations possible assuming L=99. To find the number of possible combinations with D coins we simply calculate the binomial coefficent 98 over (D-1). We have to write D-1 because the first coin always is 1¢. For the same reason we have to use 98 instead of 99. The following gives an overview about D and the number of combinations possible:

• 1: 1
• 2: 98
• 3: 4,753
• 4: 152,096
• 5: 3,612,280
• 6: 67,910,864
• 7: 1,052,618,392
• 8: 13,834,413,152
• 9: 157,366,449,604

Considering the European currency system where you have 6 coins, there are approximately 68 million coin sets to choose from. Once you invent your own currency system, don't try to come up with a set of 9 coins. You would end up choosing from 157 billion coin sets. If you had a computer that could process 1,000 of these coin sets a second it would take you more than four years to find the best denomination (as for 6 coins it would still take you 7 days at the same speed). Figure 1 shows the number of possible coin sets over the number of coins in set. The y-axis is in logarithmic scale due to the huge number of possibilities for coin sets with a larger number of coins.

Figure 1 - The number of possible coins sets over the number of coins in a set

Solving the Problem

Now that we know about our problem let us try to solve it. It turns out that a lot of clever and gifted people have dealt with these kinds of problems before. They all figured out that trying all possible combinations is the only way to precisely solve this problem. [1]) gives us the following solutions for D=[1; 7]:

D   (e1, ... eD)              C     number of combinations
1   (1)                       495               1
2   (1, 10)                   900              98
    (1, 11)
3   (1, 12, 19)               515           4,753
4   (1, 5, 18, 25)            389         152,096
    (1, 5, 18, 29)
5   (1, 5, 16, 23, 33)        329       3,612,280
6   (1, 4, 6, 21, 30, 37)     292      67,910,864
    (1, 5, 8, 20, 31, 33)
7   (1, 4, 9, 11 26, 38, 44)  265   1,052,618,392
		 

There are some computational tricks to minimize the effort when trying all combinations. What we want to do is to take this problem to another level by solving it using Genetic Algorithms.

Applying Genetic Algorithms

Our problem is now well (and in a limited way mathematically) defined. We can start to apply genetic algorithms to it. For the first part this is trying to find a genome that represents our problem.

The Genome

Finding a suitable data structure to represent the problem seems to be an easy task: simply take as many bytes that are necessary to hold L coins. As we agreed to set L to 99 we need floor(99/8)=13 bytes to represent an indiviual. But that is not enough: it turns out that the program will very often need the coin set in a compact fashion. The bit array does not suffice to that condition. Thus we introduce another data structure to hold all set coins in a compact way (this second data structure is not really required, it's sole purpose is to improve the performance of the program). Figure 2 shows the representation of the coin set within memory: the ones represent a present coin while the zeros stand for coins not available in the particular coin set.

Figure 2 - Visualization of the bit array representing the coin set

The parts marked with the colors magenta, green and blue represent the variables discussed in the section Mathematical Background. We can see these variables mapped to the genome. The missing variables V, S and C appear when the fitness is calculated. C turns out to be the fitness for all amounts in the range [1;V] giving us S - the minimal number of coins to make up V.

Determining the fitness

Once we have a way to represent the indiviuals we need a method to determine their fitness. At first glance you might consider a greedy algorithm to be the best choice. 'A greedy algorithm always makes the coice that looks best at the moment' ([2]). With coin sets and changes to be made the greedy coice is to subtract the largest possible coin from the amount of change until it finally becomes zero. This works fine if you chose only 1 or two coins to be in the coin set. It even works if the coin denominations for the coins greater than 1¢ are multiples of each other. In all other cases the greedy coice yields the wrong result.

Example: D=4, T={1, 5, 10 ,20}, L=99

  99=20+20+20+20+10+5+1+1+1+1=4*e4+1*e3+1*e2+4*e1 -> S99=10
  98=20+20+20+20+10+5+1+1+1  =4*e4+1*e3+1*e2+3*e1 -> S98=9
  97=20+20+20+20+10+5+1+1    =4*e4+1*e3+1*e2+2*e1 -> S97=8
  96=20+20+20+20+10+5+1      =4*e4+1*e3+1*e2+1*e1 -> S96=7
  95=20+20+20+20+10+5        =4*e4+1*e3+1*e2      -> S95=6
  94=20+20+20+20+10+1+1+1+1  =4*e4+1*e3+    +4*e1 -> S95=9
    .                        .                          .
    .                        .                          .
    .                        .                          .
   5=5                       =          1*e2      -> S5 =1
   4=1+1+1+1                 =               4*e1 -> S4 =4
   3=1+1+1                   =               3*e1 -> S3 =3
   2=1+1                     =               2*e1 -> S2 =2
   1=1                       =               1*e1 -> S1 =1

   --> C=500

The example suggests that the greedy algorithm does fine. But before we decide to use this algorithm once and for all, let us have a look at another example:

Example: D=4, T={1, 4, 19 ,44}, L=99

  99=44+44+4+4+1+1+1=2*e4+    +2*e2+3*e1 -> S99=7 wrong
->99=1+4+44+19+19+19=1*e4+3*e3+l*e2+1*e1 -> S99=6
  98=44+44+4+4+1+1  =2*e4+    +2*e2+2*e1 -> S98=6 correct
  97=44+44+4+4+1    =2*e4+    +2*e2+1*e1 -> S97=5 correct
  96=44+44+4+4      =2*e4+    +2*e2      -> S96=4 correct
  95=44+44+4+1+1+1  =2*e4+    +1*e2+3*e1 -> S95=6 wrong
->95=1+19+19+19+19  =     4*e3     +1*e1 -> S95=5
  94=44+44+4+1+1    =2*e4+    +1*e2+2*e1 -> S94=5 correct
    .               .                          .
    .               .                          .
    .               .                          .
  5=4+1             =          1*e2+2*e1 -> S5 =2 correct
  4=4               =          1*e2      -> S4 =1 correct
  3=1+1+1           =               3*e1 -> S3 =3 correct
  2=1+1             =               2*e1 -> S2 =2 correct
  1=1               =               1*e1 -> S1 =1 correct

   --> C=430 wrong
   --> C=408

This is exactly the same thing that Jeffrey Shallit points out in [1]), yielding in different (non-optimal) results:*

D    (e1, ..., eD)              C'
1    (1)                       495
2    (1, 10)                   900
     (1, 11)
3    (1, 5, 22)                526
     (1, 5, 23)
4    (1, 3, 11, 37)            410
     (1, 3, 11, 38)
5    (1, 3, 7, 16, 40)         346
     (1, 3, 7, 16, 41)
     (1, 3, 7, 18, 44)
     (1, 3, 7, 18, 45)
     (1, 3, 8, 20, 44)
     (1, 3, 8, 20, 45)
6    (1, 2, 5, 11, 25, 62)     313
     (1, 2, 5, 11, 25, 63)
     (1, 2, 5, 13, 29, 64)
     (1, 2, 5, 13, 29, 65)
7    (1, 2, 5, 8, 17, 27, 63)  286
               .
               .
               .
     (27 other sets omitted)
               .
               .
               .
     (1, 2, 5, 8, 19, 30, 63)
     (1, 2, 5, 8, 19, 30, 64)
     (1, 2, 5, 8, 19, 30, 66)
     (1, 2, 5, 8, 19, 30, 67)
   

In comparison to the optimal results we can see, that - except for coinsets with one or two coins, or those containing only coins that are multiples of each other - the greedy result is always worse. Thus we need to look for a better fitness algorithm.

Sticking to the greedy choice does not give us a satisfying fitness function. What we need is an algorithm that is capable of determining the minimal number of coins required for a particular amount without any restrictions. And there is indeed such an algorithm: it employs a technique called dynamic programming. Dynamic programming solves problems by splitting them into small subproblems of the same kind. The subproblems depend on each other's solution: once you find the solution for the first subproblem you can solve all other subproblems depending on the solution of the first subproblems (and so forth) [3].

In order to find us an algorithm that uses dynamic programming we at first need to split our problem into subproblems: we know the amounts that minimally can be made by using one coin: it's e1, e2, ..., eD. Let us consider this to be the first subproblem solved. The next step is to find all amounts that can be made by using two coins: it's e1+e1, e1+e2, ..., eD+eD-1, eD+eD. The next step finds us all amount to be made using three coins, and so forth. If we find that an amount we could make by let's say three coins already was made up by two coins we leave the smaller value in the solution matrix and continue. The algorithm ends after at most L steps. At this point all minimal changes have to be found. If some amounts are missing, then the coin set used does not suffice to the restriction that at least the 1¢ coin is present.

Let us have a look at the pseudocode of our fitness function:

 1:  -> initialize solution[L]
 2:  
 3:  // initialize our solution matrix with the maximum number of coins+1
 4:  for i 1 to L
 5:    solution[i] = L + 1
 6:  
 7:  // these are the first solved subproblems
 8:  for i 1 to D
 9:    solution[ei] = 1
10:  
11:  // number of solutions found
12:  count = D
13:  for i 2 to L
14:    do for j 1 to L
15:      // refer the solution to the last subproblem solved
16:      if solution[j] == i-1
17:        // add all coins the the last minimal solution
18:        then for k 1 to D
19:          do if solution[j] > i
20:            // assign count if it is the best solution
21:            then solution[j] = i
22:            ++count

Again let us illustrate with a little example:

Let's say we have a set of D=3 coins T={1, 4, 9} and want to limit the amounts of change to L=25. We now want to find the set minimal number of coins to make all the change:

no.	amount	found in run	depends on no./amount	used coins
1	1	1	-	1
2	4	1	-	4
3	9	1	-	9
4	2	2	1/1	1, 1
5	5	2	1/1	1, 4
6	10	2	1/1	1, 9
7	8	2	2/4	4, 4
8	13	2	2/4	4, 9
9	18	2	3/9	9, 9
10	3	3	4/2	1, 1, 1
11	6	3	4/2	1, 1, 4
12	11	3	4/2	1, 1, 9
13	14	3	5/5	1, 4, 9
14	12	3	7/8	4, 4, 4
15	17	3	7/8	4, 4, 9
16	19	3	6/10	1, 9, 9
17	22	3	8/13	4, 9, 9
18	7	4	10/3	1, 1, 1, 4
19	15	4	11/6	1, 1, 4, 9
20	20	4	12/11	1, 1, 9, 9
21	16	4	14/12	4, 4, 4, 4
22	21	4	14/12	4, 4, 4, 9
23	23	4	13/14	1, 4, 9, 9
24	24	4	19/15	1, 1, 4, 9, 9
25	25	4	21/16	4, 4, 4, 4, 9

There is one major drawback of the dynamic solution. Given a number V in [1; L] you cannot determine the coins used to make up this number optimally. Instead you have to find all predecessors of this coin set. Let's say you are interested in the optimal change for 15¢. This amount depends on 6¢ which itself depends on 2¢ and 1¢. The worst thing is that we cannot determine these dependencies beforehand. They are found by the algorithm which has to be run recursively.

Before we continue with Mating for our indiviuals, let's look at the running time of the fitness algorithm. The fitness algorithm is called for every indiviual in every generation. So it should better be a fast running time. Line 1 add L to the runtime. Lines 4-5 also contribute L. Lines 8-9 add another D. Now it gets really interesting: the loop in line 13 is executed at most L times. It contains another loop on line 14 that is executed L. With D=L (worst case) the loop in line 18 is also executed L times. With a total running time of L3 we can easily ignore the linear running time of lines 1-12. Thus the total running time (worst case) is: L3. With a little bit of 'cheating' (i.e. using counters and not iterating from 0 through L) we can improve the running time significantly (unfortunatelly this does not change the factor L3). Still for the work the algorithm is doing this runtime is acceptable.

Mating

With our indiviual out on the loose, there is only one thing left to worry about: Mating.

There are two different approaches how to make the indiviual mate:

• split the genome randomly in half and use the resulting indiviuals
• randomly selecting half the number of coins from each of the parents

The first approaches turns out to produce children that in at least 50% of all cases have either too little or too many coins in their set. As these children would not be able to survive: they would have to be repaired. Repair of children is quite cumbersome and contradicts our intention to work Biology-inspired.

So we decide to chose the second mating approach. The following figure displays the way this will be implemented

This mating algorithm ensures that the generated child is a totally random creating. It is able to survive even if both the parents are identical (in this case the child would be identical to the parents, too.)

Figure 3 - flow chart of mating procedure

Implementation

The implementation to solve the coinproblem using Genetic Algorithms is done in C. There are basically two important structures: one representing an individual, called item and another one representing a population, called set.

Even though we found a suitable Genome in The Genome we extend the set by a character array that contains the values of all coins of an individual. This improves the runtime of mating procedure and the fitness calculation. We furthermore add the count of coins in the individual and it's fitness to the structure. The number of coins seems somewhat superfluous but makes great sense if you consider the possibility to possibly use mating procedures that do not necessarily create healthy individual (i.e. items with less or more coins than required). The presence of the fitness is straightforward considering the running time of the fitness algorithm. Whenever we change the item's coins we update it's fitness. Ensuring it only needs to be run after modifications we can guarantee that the expensive fitness function is called only whenever really necessary. Eventually the complete structure of an item looks like that:

struct item {
    unsigned char  coin[13]; /* an array where a bit represents a coin */
    unsigned char *coins;    /* an array holding the values of the coins */
    unsigned int   count;    /* the total number of coins */
    unsigned int   fitness;  /* the fitness of the item */
};

The second structure, the set includes an array cointaining all items of the set, their average fitness and the number of items per set. This structure is straightforward and self-explanatory:

struct set {
    struct item *items; /* pointer to items of set */
    float        avg;   /* average fitness of set */
    int          count; /* count of coins per set */
};

The following flow chart is meant to display the main structure of the program. For further information on the implementation please consult the source code that can be found here.

Figure 4 - flow chart of the main program

Using the Program

To start the program run the executable by typing ./coinproblem (Unix assumed). This will start coinproblem with its default parameters.

If you are interested in the options of coinproblem, simply type ./coinproblem -h. Furthermore coinproblem supports the following options:

-i <integer>
     Sets up the number of items in a set.
     Must be greater than two and a multiple of two.
     The default value is 10.

-c <integer>
     Set the number of coins per item.
     The value must be in the interval [1; 99].
     The default value is six.

-o <percentage>
     This sets the percentage of overpopulation.
     It must be in the interval [0; 100]. 
     An overpopulation of more than 100% is not considered useful.
     The default overpopulation is 20%.

-m <percentage>
     Sets up the percentage of mutation probability.
     It must be in the interval [0; 100].
     The default value is 5%;

-e <weak|drop|none>
     Select the elitism method.
     It is one of the values 'weak', 'drop' or 'none'.
     - weak implements a weak elitism;
     - drop drops the strongest individuals;
     - none disables elitism;
     The default elitism mode is 'weak'.

-k <yes|no>
     Enables or disables the killing of super individuals.
     This value must be either 'yes' or 'no'.
     Killing of super individuals is enabled by default

-s <integer>
     Force program to stop after population's best item has note
     impoved for that many runs.
     Value must be positive.
     The default for stop number is 2000.

-g <integer>
     Similar to verbose mode this prints out the average fitness of
     the population, best item in a population and the
     range from bast to worst item in a population every 'n' runs in
     gnuplot compatible format. The difference to -v is that you can 
     define the interval giving the number after this option.
     When the program has finished it prints out the command to run 
     gnuplot on stderr assuming the file containing the gnuplot data
     is called results.dat.
     This way you can do the following cool thing:
     ./coinproblem -g 10 >results.dat 2>plot_results.gpi && \
     gnuplot plot_results.gpi

-r
     Force the program to use the greedy algorithm instead of the dynamic
     one to calculate the fitness of an indiviual.
     Even though this algorithm is faster, it will yield results not being
     optimal. Thus it should be used with care!

-v
     Enable verbose mode. This prints out the configuration coinproblem has
     been started with, the first items, and every 100 populations the 
     average fitness of the population, best item in a population and the 
     range from bast to worst item in a population. It furthermore prints
     out when superkill is turned off.
     Verbose mode is not enabled by default.

Results

After all we are able to run our program. We have described the problem, modeled a genome matching the problem, found a clever fitness function, and implemented a little c-program. Now it's time to see the results.

We want the program to examine sets from 1 through 12 coins. To have significant results we start the program in 10 cycles for 10,000 times (summing up to a total of 100,000 runs). Afterwards we examine the results of each of the 10 cycles separately and calculate the following indicators:

• the best item found**
• the number of times the program was run in each cycle (is 10,000 for all cycles)
• the run of a cylce in which the supposedly best item had been found first
• the number of items processed before the best item had been found over the total number all possible coin sets (% of combs)

But now let us finally look at the results:

1:

best	times	after	% of combs
4950	10000	1	2201200.00%
4950	10000	1	2201200.00%
4950	10000	1	2201200.00%
4950	10000	1	2201200.00%
4950	10000	1	2201200.00%
4950	10000	1	2201200.00%
4950	10000	1	2201200.00%
4950	10000	1	2201200.00%
4950	10000	1	2201200.00%
4950	10000	1	2201200.00%

1 optimal set:

4950

[1]

2:

best	times	after	% of combs
900	10000	1	22593.87%
900	10000	1	22553.06%
900	10000	1	22532.65%
900	10000	1	22491.83%
900	10000	1	22512.24%
900	10000	1	22471.42%
900	10000	1	22685.71%
900	10000	1	22716.32%
900	10000	1	22675.51%
900	10000	1	22491.83%

2 optimal sets:

900	[1, 10]
900	[1, 11]

3:

best	times	after	% of combs
515	9631	1	465.01%
515	9615	1	608.71%
515	9646	1	975.00%
515	9627	1	911.04%
515	9631	1	522.02%
515	9622	1	473.84%
515	9626	1	509.19%
515	9621	1	476.58%
515	9616	1	474.47%
515	9627	1	474.68%

1 optimal set:

515	[1, 12, 19]

4:

best	times	after	% of combs
389	6457	1	14.59%
389	6537	4	97.96%
389	6463	1	14.81%
389	6440	1	19.65%
389	6491	2	37.17%
389	6495	1	15.45%
389	6479	2	29.35%
389	6469	2	32.66%
389	6489	2	30.72%
389	6485	1	28.72%

2 optimal sets:

389	[1, 5 , 18, 25]
389	[1, 5 , 18, 29]

5:

best	times	after	% of combs
329	585	33	26.23%
329	580	13	10.27%
329	584	2	1.59%
329	591	20	15.73%
329	610	2	1.98%
329	615	6	4.32%
329	598	6	5.65%
329	608	4	3.31%
329	591	55	42.91%
329	576	39	28.73%

1 optimal set:

329	[1, 5 , 16, 23, 33]

6:

best	times	after	% of combs
292	640	27	1.05%
292	628	42	1.80%
292	639	29	1.10%
292	626	33	1.30%
292	648	25	0.96%
292	627	3	0.11%
292	649	8	0.37%
292	629	1	0.03%
292	642	12	0.49%
292	641	31	1.20%

2 optimal sets:

292	[1, 4 , 6 , 21, 30, 37]
292	[1, 5 , 8 , 20, 31, 33]

7:

best	times	after	% of combs
265	111	4	0.01%
265	98	132	0.36%
265	105	9	0.02%
265	105	67	0.18%
265	113	5	0.01%
265	110	55	0.14%
265	105	31	0.08%
265	111	41	0.11%
265	104	177	0.48%
265	111	15	0.04%

1 optimal set:

265	[1, 4 , 9 , 11, 26, 38, 44]

8:

best	times	after	% of combs
248	39	106	0.021%
248	43	449	0.098%
248	47	187	0.038%
248	47	167	0.035%
248	42	188	0.038%
248	44	164	0.034%
248	47	135	0.027%
248	42	151	0.031%
248	42	135	0.028%
248	45	127	0.026%

1 optimal set:

248	[1, 3 , 8 , 9 , 20, 30, 44, 48]

9:

best	times	after	% of combs
237	500	22	0.00040%
237	497	11	0.00019%
237	512	21	0.00043%
237	483	25	0.00043%
237	513	15	0.00028%
237	504	29	0.00051%
237	507	3	0.00005%
237	509	27	0.00048%
237	522	31	0.00062%
237	500	13	0.00023%

77 optimal sets:

237	[1, 3 , 4 , 10, 17, 25, 37, 43, 48]
237	[1, 3 , 4 , 10, 18, 22, 31, 42, 47]
237	[1, 3 , 4 , 10, 19, 24, 36, 41, 49]
237	[1, 3 , 4 , 11, 20, 26, 33, 38, 47]
237	[1, 3 , 4 , 12, 17, 24, 39, 43, 49]
237	[1, 3 , 4 , 12, 19, 29, 36, 42, 56]
237	[1, 3 , 4 , 13, 19, 27, 33, 44, 49]
237	[1, 3 , 4 , 13, 20, 27, 37, 42, 48]
237	[1, 3 , 4 , 13, 20, 28, 34, 39, 57]
237	[1, 3 , 4 , 13, 20, 28, 38, 43, 49]
237	[1, 3 , 4 , 13, 20, 30, 35, 41, 49]
237	[1, 3 , 4 , 13, 20, 30, 38, 44, 49]
237	[1, 3 , 4 , 9 , 16, 27, 37, 44, 49]
237	[1, 3 , 5 , 6 , 18, 28, 37, 44, 48]
237	[1, 3 , 7 , 11, 13, 28, 33, 42, 47]
237	[1, 3 , 7 , 12, 20, 25, 31, 32, 46]
237	[1, 3 , 7 , 12, 20, 25, 32, 46, 48]
237	[1, 3 , 7 , 12, 20, 29, 31, 32, 47]
237	[1, 3 , 7 , 12, 22, 30, 33, 46, 47]
237	[1, 3 , 7 , 12, 22, 30, 39, 42, 55]
237	[1, 3 , 7 , 12, 22, 31, 33, 34, 47]
237	[1, 3 , 7 , 12, 22, 32, 40, 45, 49]
237	[1, 3 , 7 , 8 , 18, 24, 37, 46, 49]
237	[1, 3 , 7 , 9 , 10, 23, 34, 44, 49]
237	[1, 3 , 7 , 9 , 10, 24, 36, 44, 49]
237	[1, 3 , 7 , 9 , 10, 28, 32, 43, 48]
237	[1, 3 , 8 , 10, 11, 27, 31, 43, 49]
237	[1, 3 , 8 , 10, 11, 28, 32, 41, 47]
237	[1, 3 , 8 , 10, 11, 28, 34, 43, 47]
237	[1, 3 , 8 , 11, 12, 28, 34, 47, 49]
237	[1, 3 , 8 , 11, 17, 29, 44, 48, 49]
237	[1, 3 , 8 , 12, 18, 27, 40, 47, 48]
237	[1, 3 , 8 , 12, 18, 27, 41, 48, 49]
237	[1, 3 , 8 , 12, 18, 31, 40, 42, 56]
237	[1, 3 , 8 , 12, 18, 34, 41, 42, 55]
237	[1, 3 , 8 , 12, 22, 28, 43, 45, 46]
237	[1, 3 , 8 , 12, 22, 29, 35, 45, 49]
237	[1, 3 , 8 , 9 , 19, 31, 33, 44, 48]
237	[1, 3 , 8 , 9 , 19, 31, 34, 44, 48]
237	[1, 3 , 8 , 9 , 20, 29, 33, 43, 47]
237	[1, 3 , 8 , 9 , 20, 30, 33, 44, 48]
237	[1, 3 , 8 , 9 , 20, 30, 35, 44, 48]
237	[1, 3 , 8 , 9 , 20, 31, 35, 45, 49]
237	[1, 3 , 8 , 9 , 20, 33, 43, 47, 49]
237	[1, 3 , 8 , 9 , 21, 25, 40, 44, 54]
237	[1, 3 , 8 , 9 , 22, 26, 38, 42, 53]
237	[1, 4 , 5 , 11, 16, 29, 38, 46, 48]
237	[1, 4 , 5 , 12, 14, 29, 35, 45, 48]
237	[1, 4 , 5 , 12, 18, 27, 33, 41, 43]
237	[1, 4 , 5 , 12, 18, 27, 37, 46, 48]
237	[1, 4 , 5 , 12, 18, 27, 38, 46, 48]
237	[1, 4 , 5 , 12, 18, 28, 34, 43, 45]
237	[1, 4 , 5 , 12, 18, 28, 37, 39, 59]
237	[1, 4 , 5 , 12, 18, 28, 37, 47, 49]
237	[1, 4 , 5 , 12, 18, 28, 38, 47, 49]
237	[1, 4 , 5 , 14, 16, 21, 39, 45, 47]
237	[1, 4 , 6 , 10, 18, 25, 34, 45, 47]
237	[1, 4 , 6 , 13, 16, 30, 41, 48, 49]
237	[1, 4 , 6 , 13, 18, 28, 39, 47, 48]
237	[1, 4 , 6 , 13, 19, 21, 35, 45, 46]
237	[1, 4 , 6 , 13, 21, 23, 37, 47, 48]
237	[1, 4 , 6 , 14, 16, 19, 36, 40, 47]
237	[1, 4 , 6 , 14, 16, 19, 36, 43, 47]
237	[1, 4 , 6 , 14, 17, 18, 37, 39, 46]
237	[1, 4 , 6 , 14, 17, 18, 38, 40, 47]
237	[1, 4 , 6 , 15, 16, 23, 41, 43, 47]
237	[1, 4 , 6 , 15, 17, 21, 39, 40, 47]
237	[1, 4 , 6 , 15, 17, 21, 39, 46, 47]
237	[1, 4 , 6 , 15, 17, 21, 40, 47, 48]
237	[1, 4 , 6 , 15, 18, 28, 41, 48, 49]
237	[1, 4 , 6 , 15, 20, 27, 37, 44, 45]
237	[1, 4 , 6 , 9 , 10, 25, 32, 43, 45]
237	[1, 4 , 6 , 9 , 10, 26, 33, 45, 47]
237	[1, 4 , 6 , 9 , 16, 30, 36, 47, 49]
237	[1, 4 , 6 , 9 , 19, 26, 35, 47, 49]
237	[1, 4 , 7 , 8 , 21, 26, 37, 39, 49]
237	[1, 4 , 7 , 8 , 21, 26, 37, 47, 49]

10:

best	times	after	% of combs
226	15	664	0.001270%
226	19	1341	0.002544%
226	20	51	0.000090%
226	14	37	0.000065%
226	20	75	0.000135%
226	16	24	0.000042%
226	18	4	0.000006%
226	17	12	0.000021%
226	21	375	0.000720%
226	18	692	0.001317%

3 optimal sets:

226	[1, 3 , 8 , 12, 18, 32, 38, 42, 47, 49]
226	[1, 3 , 8 , 12, 18, 34, 38, 43, 45, 46]
226	[1, 3 , 8 , 12, 22, 28, 38, 42, 47, 49]

11:

best	times	after	% of combs
214	27	294	0.000064%
214	26	61	0.000014%
214	31	368	0.000081%
214	28	433	0.000096%
214	25	459	0.000102%
214	28	419	0.000093%
214	34	402	0.000089%
214	29	398	0.000088%
214	26	78	0.000017%
214	25	394	0.000087%

1 optimal set:

214	[1, 3 , 8 , 12, 18, 31, 37, 41, 46, 48, 49]

12:

best	times	after	% of combs
206	25	630	0.000018%
206	29	694	0.000019%
206	29	684	0.000019%
206	27	673	0.000019%
206	29	665	0.000019%
206	24	663	0.000018%
206	28	656	0.000018%
206	24	649	0.000018%
206	26	641	0.000018%
206	30	639	0.000018%

1 optimal set:

206[1, 3 , 4 , 9 , 16, 20, 30, 34, 41, 46, 47, 49]

For the coin sets with 1-3 coins we see that the genetic algorithm solves the problem perfectly (i.e. it finds the best item in over 98% of the runs, on average). The good exactness of the results is disfigured by the fact, that the number of items processed in each run is preposterously larger than the number of actual combinations (1, 98 and 4,753). This is not surprising - it is indeed what we expected. It gets more interesting with the four coin sets: here we do not process all possible items for once (although admittedly 98% is quite close). Starting with 5 coins the program proves to work perfectly: not even 50% in the worst case (2% in the best case) before the best item is found. And the numbers drop once we reach the 7 coins. They get so low, that not once the percentage of items processed is over 0.5%. This means, that - considering the 100,000 runs and adding all worst cases - it would have taken us ca 1% of the time it takes someone who brute forces through all combinations. The results for coin sets containing 8-12 coins speak for themselves: due to the huge number of combinations the percentage of combinations processed before the best item was found is far below 1%. There is one remarkable thing though: while all the sets have at most 3 best coin sets, the coin set cointaining 9 coins comes up with 77. This suggests that there might be an even 'better optimum' (or in other words: what we have found to be best might not be optimal - or it might). But to find out exactly we would have to go through 1 billion combinations (and that is not exactly what we want right now).

It gets quite obvious, though, that with the increasing number of combinations for the coin sets the genetic algorithm gives us superiour results by processing only a small piece of all possible combinations.

Conclusion

With our genetic algorithm we managed to find the best items in the number of combinations of coin sets faster than any other algorithm***. Even though we do not know for sure that the optimal coin sets we found are really the best, we proved our point: using genetic algorithms helps us to find superiour solutions (perhaps the best) faster than using other techniques. For real life applications this means: finding a very good solution in a short time is far better than spending hundreds or thousands of times longer to come up with a 2% better solution.

Citations and References