-In this paper, the application of heuristic methods to solve birthday paradox problem is presented. Methods are compared to show which of them gives better and quicker solution. Benchmark tests have been performed and discussed to show the results.
Heuristic methods are used to find a solution or solve problems which for some reasons cannot be solved by traditional way. Sometimes finding the optimal or exact solution, using classical methods is just immposible or takes too much time. Then we can use heuristic solving to speed up time of work or find approximate solution. It can be called a shortcut but due to shortening the operation time it makes those methods very practical. Even if our solution is not exact, our approximated one can be only slightly different. Those methods do not guarantee us the exact solution but in some cases it is not necessary us necessary as for example saving time.
Cuckoo Search Algorithm (CSA) and Simulated Annealing (SA) are the examples of the heuristic methods. To create those alorithms, Computational Intelligence is used. Computational Intelligence (CI) is considered as a methodology which uses computer’s ability to learn specified skills or learn how to behave in the new conditions. Created programs imitiate intelligent behaviour of animals’ or humans’ organism. Despite the fact that they are inspired by nature, the reason why they are created is to solve real-world problems which for some reasons, described in the prior paragraph, cannot be solved by traditional way.
CI methods find their applications in many different fields
of science. We can use them to perform some optimalisation
processes [
The very first application of Simulated Annealing algorithm
was presented in [
Cuckoo Search Algorithm allow us to describe changes in
genes while adapting to the new environment. It can be used
to sizing thermal electricity panels [
In this article Simulated Annealing and Cuckoo Search Algorithm are used to solve the Birthday Paradox Problem. Algorithms are implemented in such way that they can help us with searching probability to find similar dates.
Presented in this article famous probability problem can be
solved both traditionally and using CI methods. Traditional
approach and all details about paradox are described in [
Simulated Annealing (SA) is a method that is based on
the metallurgical process. The whole process consists of three
stages: heating the metal up to the high temperature, keep it in
those conditions and slowly cooling down. It is important to
keep thermodynamic equilibrium during the whole process and
that is why we can describe it by mathematical equations. In
[
Cuckooo Search Algorithm (CSA) is a method of optimalization, based on the Gauss distribution and simulate the behaviour of some species of cuckoos which use others’ birds nests to lay their own eggs. Those birds try to choose nests where eggs have been recently laid to minimize probability that hosts will drop them out. They can even imitiate the colour or texture of those eggs to stay unnoticed. When hosts find out the cuckoo egg, they can get rid of it or just ignore.
To use CSA to solve Birthday Paradox Problem we need a few assumptions: 1) We have 365 nests which represent 365 days in the year 2) Number of cuckoos is constant 3) Each cuckoo has one egg to lay 4) Chance that the egg will be detected by hosts is chance 2 (0; 1) We can describe the process of finding the new solution by equation xt+1 = xit + L( ; ; ) i (1) where xt+1 = (x1; x2; : : : ; xk)t+1 is the (t + 1) th CSA solution, n - number of cuckoos in the population and L( ; ; ) is a Le´vy flight determined for the given parameters: step lenght, - minimum step lengh, - Le´vy flight scalling parameter. We can obtain the value of the Le´vy flight by using formula 8 >>r > > L( ; ; ) = <
2 > > > >:0; exp[ ( 2( where H(xit+1) is a hosts’ decision about cuckoo egg, chance is a value generated randomly during every decision and p is defined at the beggining of the whole process, chance; p 2 (0; 1).
The aplication of the CSA that was implemented for solving Birthday Paradox Problem is presented in Algorithm 1. Instead of generating full dates, we can use numbers 1 - 365 which represent 365 days of the year (we don’t consider lap years). At the beggining, we establish all the initial values and generate the random population on the list population. Cuckoos are flying according to (1), (2) and (3) and then, the lacking cuckoos are replaced randomly at once. After that, we check if there are two cuckoos with the same number in one generation. If so, we write down the number of generation - generations in the list result. When the list result is completed, we take the average of all summands and that way we get the final outcome for given parameters.
To find the optimal solution, two different fitness functions have been performed. First of them is a simple linear function f (x) = x. Received results are placed in the Tab. I. As we can see, this function does not allow as to obtain the exact wanted value - 23. What is more, the particular outcomes are not similar to each other in many cases. After many trials, it has been stated that the most important impact to the value of outcome has p and number of cuckoos. If they are lower - we obtain too high values and when they are higher - received values are too low. We can also notice that when we take 500 or more samples, our results are more similar and close to each other. What is surprising, the parameters , and does not have any significant influence to the final result. The only noticed difference is that if those parameters become high, the score is albo slightly higher. In the Tab. I we can find two sets of parameters for each we got the value very close to 23: p = 0; 105, = 2, = 6, = 7, cuckoos = 12, samples = 100 and p = 0; 105, = 2, = 6, = 7, cuckoos = 12, samples = 500 - the only difference is in number of samples. In the Tab. I we can see that particular results form the the first set are more divergent than those form the second one. (2) Algorithm 1 Cuckoo Search Algorithm to obtain Birthday Paradox Problem Solution 1: Define the value of the probability p , fitness function f (x), parameters , , , number of cuckoos in each generation and number of samples in each iteration 2: Set counter := 0, generations := 0 and decision := 0, 3: Declare lists: population, result, 4: while counter samples do 5: Generate a random population (on the list population), 6: while decision == 0 do 7: Cuckoos fly according to (1) and (2), 8: Hosts decide on eggs by (3), 9: Lacking cuckoos replaced randomly, 10: for i = 0 to cuckoos 1 do 11: for j = i + 1 to cuckoos do 12: if f (population[i]) == f (population[j]) then 13: decision = 1, 14: end if 15: end for 16: end for 17: if decision == 0 then 18: generations + +, 19: end if 20: end while 21: Add generations to the list result’ 22: decision = 0, generations = 0, 23: counter + +, 24: Clear the list population, 25: end while 26: counter = 0, 27: Set sum = 0, 28: for i = 0 to samples do 29: Sum = Sum + result[i], 30: end for 31: Outcome = round(sum=samples), 32: Return Outcome.
As the second fitness function, the power function has been performed, f (x) = x6. Results are shown in the Tab. II. It turns out that it gives better average outcomes. We can determine parameters for which results are closer to 23 than in the prior testing. While changing parameters, we can notice similar actions to the function f (x) = x. When p and number of cuckoos get higher, the result is lower and conversly. The more samples we take, differences between particular outcomes are lower. What is new, parameters , and are more important - while and are singinificantly higher than , the results get lower so in order to keep it in the neighbouring of 23, we have to decrease p or number of cuckoos. For parameters p = 0; 083, = 10, = 200, = 300, cuckoos = 10, samples = 100 the excact value 23 has been received but because there were only 100 samples in each iteration, the divergence in results is very serious so we can say that it just happend accidentally. Anyway, there is another set: p = 0; 210, = 1, = 2, = 3, cuckoos = 8, samples = 500 for which divergence is not that high and final result is still very close to 23.
Firstly, we have to choose which of two presented fitness functions is better for Cuckoo Search Algotithm. Secondly, we have to compare numerical results form both CSA and SA algorithms to find the best one. For SA, 26 different sets of parameters have been prestented for which average value was the closest to 23. For CSA it was 13 sets of parameters for first fitness function and 13 for second. 13 samples form every kind have been taken to further calculations. While taking the average of those averages we receive 22,87 for SA, 23,26 for CSA f (x) = x, 22,92 for CSA f (x) = x6. We can see that for SA and CSA f (x) = x6 the average is closer to 23 than in case of CSA f (x) = x. However, by counting average we cannot say how large are divergences between particular samples or averages. Of course, we want them to be as little as possible to make our result more stable. On the Fig. 1 the divergence between particular samples for single set of parameters is presented - purple from SA, red form CSA, f (x) = x6 and green from CSA, f (x) = x. As we can see, the smallest differences we have for SA, the most incompatible are results from CSA, f (x) = x. Similar conclusions we have after studying the standard deviation of those numbers. We want to know how wide those results are interspersed around 23. The lower standard deviation is, the lower is dissipation of averages. Indeed, we get standard deviation 0,215 for CSA f (x) = x, 0,027 for CSA f (x) = x6 and 0,026 for SA. It only confirms prior findings. On the Fig. 2, 3 and 4 we can see that with the same values on the vertical axis, the highest amplitude is for the CSA, f (x) = x and the most stable is chart for SA samples. This explains values of standard deviation.
To sum up, there is no doubt that application the second fitness function gives us better results but if we compare Cuckoo Search Algorithm and Simulated Annealing it turns out that for this problem SA is unbeatably better. In our comparisons, samples for CSA, f (x) = x6 gave us results very similar to samples from SA but we have to remember that in the SA we could set parameters in such a way that almost every particular result which is taken to average equals 23. In CSA it is immposible to establish parameters to obtain such exact value in the final result. We have numbers from the range 16-29 and that is why Simulated Annealing is better to use than Cuckoo Search Algirithm in this problem.
In this article Cuckoo Search Algorithm has been implemented to obtain the solution for the Birthday Paradox Problem. Benchmark tests have been performed to establish the best parameters which gives us the solution. The results have been compared to the prior results for the same problem but solved using Simulate Annealing Algorithm. Algorithm with the best solution for this problem has been chosen. 27 22 24 24 19 20 22 24 24 25 23 22 24 24 23 20 23 25 19 22 23 24 21 23 20 17 25 25 24 23 Fig. 4: Chart of distribution of averages for samples from SA.