=Paper=
{{Paper
|id=Vol-1712/p09
|storemode=property
|title=On Application of Annealing Algorithm to Birthday Paradox Problem Solving
|pdfUrl=https://ceur-ws.org/Vol-1712/p09.pdf
|volume=Vol-1712
|authors=Adrianna Benna
}}
==On Application of Annealing Algorithm to Birthday Paradox Problem Solving==
https://ceur-ws.org/Vol-1712/p09.pdf
On Application of Annealing Algorithm
to Birthday Paradox Problem Solving
Adrianna Benna
Faculty of Applied Mathematics
Silesian University of Technology
Kaszubska 23, 44-100 Gliwice, Poland
Email: ada.benna@gmail.com
Abstract—In this paper, the idea of solving birthday paradox was implemented using developed model of fireflies behav-
problem is proposed. Presented method is based on the appli- ior in the summer [11]. There are also methods simulating
cation of Computational Intelligence. For different parameters changes in genes while adaptation to new environment. These
the proposed solution has been performed. Research results has
been gathered and presented to show possible advantages. can be used for sizing of solar thermal electricity panels [12].
Similarly CI methods can serve in games, to compose scenar-
I. I NTRODUCTION ios and control plot [13] and [14]. Stability and optimization
Computational Intelligence (CI) is a methodology which of these methods is not a trivial problem [15], however it
involves computing to obtain systems with the ability to is possible to modem adequately to the implementation to
learn specific behavior and act like intelligent one. There are achieve sufficient precision in the calculations [16].
three main pillars of CI - fuzzy logic, neural networks and The first version of simulated annealing algorithm was pre-
evolutionary computation. These methodologies are usually sented in [17], where the authors proposed its implementation
inspired by nature but we can find their application in the for optimization purposes. With time computer scientists used
real - world problems in which mathematical or traditional it for various purposes and therefore some improvements
modeling are impossible to employ for a few reasons: and developments were proposed to simulated annealing to
1) process is to complex for traditional modeling or simply increase precision of calculations [18]. Later, this method, and
there is no mathematical algorithm available other bio-inspired algorithms, were reported for efficiency and
2) imprecise or incomplete data precision in widely used minimization of various continues
3) process might have stochastic nature and the optimal functions [19] and [20]. Moreover we can find comments on
solution is unknown restoration of low resolution structures of macromolecules by
application of annealing algorithm [21]. Simulated annealing
CI provides solutions for such problems by creating tools or
approach can be used to compose structures of various popu-
systems which can imitate intelligent behavior and have some
lations [22] and cloud-based users verification systems [23].
human - like abilities, i.e. learning, dealing with new situations
In this article simulated annealing algorithm was used to
or decision making.
solve a birthday paradox, where implemented procedure was
II. R ELATED W ORKS made to calculate possibility of similarity in dates.
CI methods take inspiration from our natural environment.
III. B IRTHDAY PARADOX P ROBLEM
They are based on observations of human organism - i.e.
nervous or immune system and animals’ behavior - their Common probability problem, proposed by Richard von
lifestyle, adaptation to new conditions and scrabbling. Mises in 1939 can be stated: what is the minimal number n of
They find their applications in many areas like optimization people in the randomly chosen group for whom the probability
[1], simulation of human decision processes [2], mass service that some pair of them will share the same birthday is greater
systems positioning [3], image processing [4]; [5], optimiza- than there is no pair like that? In other words, probability
tion of semantic web services [6], reconstruction of missing that there are two people with the same birthday date must be
data [7], and more. greater than 50%. The answer is that there must be at least
Algorithm simulating cuckoo search for nests in the forest 23 people in the random group. Many people says that it is
was applied to intelligent video frames targeting [8]. Similarly, surprisingly little number and that is why problem is called
this approach was also implemented for optimal synthesis of paradox. Pigeonhole principle says that probability reaches
six-bar double dwell linkage problem [9]. Cuckoos motion 100% when there are at least 366 (or 367 at leap years) people
model was also applied to multi objective scheduling problem in the group, so for 50% likelihood there should be 183 (184)
[10]. Solving dynamic multidimensional knapsack problem people. The thing is that in the group of 23 people there is
more than 22 comparisons. We have to compare everyone to
Copyright c 2016 held by the authors. everyone, not only one person. This way, for 23 people we
have 23·22
2 = 253 comparisons. Another counter - intuitive
47
thing is that growth of the probabilities, which depends of V. S IMULATED A NNEALING M ETHOD
number of people, is not linear. To simplify the problem we Annealing is a metallurgical process based on heating the
can make a few assumptions: metal up to a high temperature, then keeping it at given
1) no leap years, every year has 365 days conditions and after that, slow cooling it down. The last stage
2) two people have the same birthday when month and day of this process is the most important step to achieve final
are the same, year is ignored conditions. It has to be monitored in order to keep the metal in
3) all dates are equally likely (in fact, more babies are born the state similar to thermodynamic equilibrium, i.e. the state
in Spring then in other seasons) in which parameters such as volume and pressure are constant
4) multiple births are considered as one birthday in time. We have three main elements that thermodynamic
equilibrium consists of:
IV. T RADITIONAL A PPROACH 1) thermal equilibrium - constant temperature as a result of
Sometimes it is easier to calculate probability of the oppo- no heat exchange with the environment
site event to ours. In our case, instead of calculating probability 2) mechanical equilibrium - constant pressure at any point
that two people have birthday at the same day, we will 3) chemical equilibrium - no chemical reactions, no
find probability that they don’t. For showing it, we can use changes in the structure of the metal
inequality that follows from probability: We can describe the thermodynamics of the whole process by
equation below:
p(k, n) = pk = E
P (E) ≈ e− kT (5)
= 1 · (1 − n1 ) · (1 − n2 ) · . . . · (1 − k−1
n )= (1)
Qk−1
= i=1 (1 − ni ) where E is the thermodynamic system, T is the absolute
temperature and k is the Boltzmann’s constant.
where p(k, n) is the probability that sequence of k elements
(number of people) chosen from n elements (365 days of the A. Mathematical Model
year) will be injective. Let’s note it pk using 1.
Mathematical models are to describe processes and relations
This event is opposite to ours. Because we want our event to
that are present in nature, science and technology by applica-
be more probable than 50%, 0 ≤ pk ≤ 0, 5. We have to find
tion of devoted sequences of equations describing modeled sit-
minimal k for which pk ≤ 0, 5.
uation in a mathematical way, where we use these equations to
calculate the state of the simulated objects in initial conditions
By using inequality 1 + x ≤ ex that is true ∀x ∈ R,
and convert it after changes in the following operations. These
we can estimate pk :
operations are performed by application of various computer
pk 1
= (1 − 365 ) · (1 − 365 2
) · . . . · (1 − k−1 procedures where we use computational power to perform
365 ) =
≤e
1
− 365
·e
2
− 365 k−1
· . . . · e− 365 = numerical experiments simulating the object. In the presented
1+2+...+(k−1) (2) approach one of important CI methods was implemented to
= e− 365 =
k(k−1) solve the birthday paradox in a way similar to annealing
− 730
=e processes i.e. discussed for application in verification systems
To satisfy pk ≤ 0, 5, we need to find the minimal k, for which [23] or compose structures of various populations [22].
we have Simulated Annealing Method (SAM) assumes that tempera-
ture at the beginning of the process is high. It enables frequent
k 2 − k − 730 ≥ 0 (3)
changes in configurations. When the temperature is lower,
The least positive solution of this inequality is there is less possibility for choosing the worst solution so it is
√ the criterion of acceptation of the solution. Therefore, we use
1 + 1 + 4 · 730 · ln 2 modified equation (5) in a simplified form:
= 22.99994315 (4)
2 δ
P (E) ≈ e− T (6)
Hence, the analytical solution of the problem is k = 23.
where δ is the difference between the value of fitness function
Due to shortening operation time of every program, we are calculated at the new random solution chosen from neighbor-
looking for the fastest solutions. This is the main reason for hood x0 and current solution x according to:
using CI to solve birthday paradox problem. We want to know
δ = f (x0 ) − f (x) (7)
how many people must be in the randomly chosen group to
make sure that probability that there is a pair of people that For a benchmark tests a simplified fitness condition was
have birthday at the same day is greater than 50%. By doing it chosen
on traditional way, we have to take many samples of 1,2,3,... x
f (x) = (8)
person group (randomly chosen) and count the probability. 2
By using CI we can get the minimum number of people much This equation is enough to perform experiments since linear
quicker. function is enough to simulate controlled growth of numerical
48
data in this experiment. For a new solution we have criterion Algorithm 1 The contrast enhancement algorithm with a
of acceptance: threshold value
δ 1: Define the value of the initial temperature T , the fitness
γ < e− T (9)
function f (·), the radius of neighbourhood p, the temper-
where γ is chosen randomly, and γ ∈ (0, 1). Change of ature change r and number of samples in each iteration
temperature we can denote as : pr,
2: Set counter := 0 and k := 0,
Tk+1 = Tk · r (10) 3: Declare lists: date, average,
4: while counter ≤ pr do
where Tk is the temperature in the k-th iteration and r is
5: decision = 0,
constant given at the beginning, where r ∈ (0, 1). For the
6: Generate random initial solution x,
benchmark test stop criterion was adapted to the modeled
7: Add x to the list date,
object.
8: k := 1,
B. Implemented Algorithm 9: while decision = 0 do
10: Generate a random neighboring solution y,
In the test method presented in Algorithm 1 was imple- 11: Calculate the difference delta using (7),
mented, for which we can also present a block diagram show 12: if delta < 0 then
in Fig. 1. Firstly we establish initial values and random initial 13: Add y to the list date,
solution x. The list date was created to remember x and next 14: x = y,
solutions which satisfy our algorithm. When new solution, y, 15: Increase the iterator variable k + +,
gratify condition (9), we add it to the list date. After every 16: else
iteration we check if there are two the same numbers in the 17: Generate a random value gamma,
list date. If so, we break our loop and save the length of the 18: if gamma satisfy equation (9) then
list in the next list average. After clearing date, we are doing 19: Add y to the list date,
the same as long as length of average is less then or equal to 20: y = x,
number of samples in each iteration which was given at the 21: Increase the iterator variable k + +,
beginning. When average is complete, we take the average 22: end if
value of all elements from average and that is our result for 23: end if
given parameters. 24: for h = 0 to k − 1 do
25: if date[h] = x then
VI. B ENCHMARK T ESTS
26: Add k to the list average,
Results of numerical experiments are shown in Tab. II - 27: Increase the iterator variable counter + +,
Tab. III. For these results changes of probability that among 28: decision = 1,
selected population are people for whom birthday paradox can 29: Clear the list date,
be encountered are presented in Tab. I and depicted in Fig. 2. 30: Break the loop,
For each set of parameters, 28 results has been received and 31: end if
then by taking the average of them, we get out final result - 32: end for
number of people. Outcomes presented in Tab. II - Tab. III 33: Reduce the temperature using (10),
are very close to expected 23. In two cases we get exactly 34: end while
this number - presented in Tab. III for parameters T = 1050, 35: end while
p = 103, r = 0, 84, pr = 850 and T = 1049, p = 103, 36: for i = 0 to pr do
r = 0, 83, pr = 850, as we can see, very similar to each 37: Sum = Sum + average[i],
other. 38: end for
39: Result = round(sum/pr),
A. Conclusions 40: Return Result.
We can state parameters for which, by rounding out we
get the expected value for our paradox - 23. As a fitness
function linear one was chosen but it turn out that for power VII. F INAL R EMARKS
and exponential function we obtain similar results. The most
important was choosing optimal parameters. The greatest In this article simulated annealing method was used to
impact for value of result have initial temperature and radius solve a problem of birthday paradox. This is definitely better
of neighbourhood - along with their decrease, values of results way to obtain solution than traditional counting probability by
are also lower. Drop of number of samples in each iteration taking many samples of 1,2,3,... person groups. By using CI
causes bigger range of received solutions. What is surprising, methods,we get the solution easier and what is very important,
different values of the temperature change, don’t change the faster. Benchmark tests have been performed to indicate the
results. best paramaters for our algorithm.
49
Fig. 1: Block diagram of the implemented processing software.
50
TABLE I: Probability of sharing birthday
number of people 2 3 4 5 6 7 8 9 10
probability of sharing birthday 0,26% 0,83% 1,56% 2,72% 4,17% 5,42% 7,16% 9,40% 11,59%
number of people 11 12 13 14 15 16 17 18 19
probability of sharing birthday 14,41% 16,60% 20,03% 22,00% 25,39% 28,54% 31,66% 34,75% 37,94%
number of people 20 21 22 23 24 25 30 35 50
probability of sharing birthday 40,89% 43,66% 47,51% 50,48% 53,83% 56,87% 70,63% 81,44% 97,00%
TABLE II: Results of numerical experiments
T 1000 1000 1000 1000 1000 1000 1100 1001 1000 1000 1000 1000 1000
p 100 100 100 100 100 100 100 100 110 105 104 102 100
r 0,9 0,9 0,9 0,9 0,8 0,85 0,85 0,85 0,85 0,85 0,85 0,85 0,84
pr 700 800 900 750 800 800 800 800 800 800 800 800 800
23 22 23 24 22 23 23 23 23 23 23 23 23
24 22 23 22 22 23 24 23 23 22 24 24 23
23 23 22 22 23 22 24 23 24 23 23 23 22
22 23 23 24 23 23 23 23 22 23 23 23 22
23 22 23 23 23 23 23 23 24 23 23 23 23
24 23 23 23 23 23 23 23 23 23 23 23 24
23 23 23 23 23 24 23 23 23 23 22 22 22
23 23 23 22 23 23 23 23 23 23 23 23 23
23 23 23 23 23 23 23 23 24 22 24 24 23
23 23 23 23 22 23 23 23 24 23 23 23 22
24 23 23 22 23 23 22 23 23 22 23 23 22
22 23 22 23 22 23 22 22 23 23 23 23 22
23 23 23 23 23 23 23 23 22 24 23 23 23
23 23 23 23 22 23 22 22 23 23 23 23 23
22 23 23 22 22 23 23 23 24 23 23 23 23
22 22 22 23 23 23 23 22 23 24 23 23 23
22 23 23 23 23 23 23 23 23 23 23 23 23
23 23 23 23 23 23 23 23 24 24 23 23 23
22 24 22 23 23 23 23 23 24 23 22 22 23
23 24 23 23 22 23 23 22 23 23 23 23 23
23 22 23 22 23 23 22 22 23 23 24 24 23
23 23 23 23 23 23 22 22 23 23 23 23 23
22 23 23 23 23 22 23 23 23 23 23 23 23
22 23 23 23 23 24 23 23 23 23 23 23 23
23 22 22 22 23 22 23 22 23 24 23 23 23
23 23 23 23 23 23 23 22 23 23 23 23 23
22 23 23 22 23 24 22 24 23 23 24 24 23
23 24 22 22 23 22 23 23 23 23 23 23 23
average 22,79 22,89 22,79 22,75 22,75 22,96 22,89 22,75 23,18 23,04 23,07 23,07 22,82
2014 IEEE Symposium on Computational Intelligence in Vehicles and
Transportation Systems, Proceedings. 9-12 December, Orlando, Florida,
USA: IEEE, 2014, pp. 108–114, DOI: 10.1109/CIVTS.2014.7009485.
[2] M. Woźniak, D. Połap, L. Kosmider, C. Napoli, and E. Tramontana,
“A novel approach toward x-ray images classifier,” in Proceedings of
IEEE Symposium Series on Computational Intelligence (SSCI). 8-
10 December, Cape Town, RSA: IEEE, 2015, pp. 1635–1641, DOI:
10.1109/SSCI.2015.230.
[3] M. Woźniak, M. Gabryel, R. K. Nowicki, and B. Nowak, “An applica-
tion of firefly algorithm to position traffic in nosql database systems,”
Advances in Intelligent Systems and Computing - KICSS’2014, vol. 416,
pp. 259–272, 2016, DOI: 10.1007/978-3-319-27478-2 18.
[4] D. Połap, M. Woźniak, C. Napoli, E. Tramontana, and R. Damaševic̆ius,
“Is the colony of ants able to recognize graphic objects?” Proceedings
of International Conference on Information and Software Technologies
(ICIST), vol. 538, pp. 376–387, 2015, DOI: 10.1007/978-3-319-24770-
Fig. 2: Chart of changes of probability that among selected 0 33.
population we can encounter a birthday paradox. [5] M. Woźniak, D. Połap, M. Gabryel, R. K. Nowicki, C. Napoli, and
E. Tramontana, “Can we preprocess 2d images using artificial bee
colony?” Proceedings of International Conference on Artificial Intelli-
gence and Soft Computing (ICAISC), vol. 9119, pp. 660–671, 2015, DOI:
R EFERENCES 10.1007/978-3-319-19324-3 59.
[6] V. Chifu, C. Pop, I. Salomie, D. Suia, and A. Niculici, “Optimizing
[1] M. Woźniak, “Fitness function for evolutionary computation applied in the semantic web service composition process using cuckoo search,” in
dynamic object simulation and positioning,” in IEEE SSCI 2014: 2014 IDC’2012 - Studies in Computational Intelligence, no. 382. Springer,
IEEE Symposium Series on Computational Intelligence - CIVTS 2014: 2012, pp. 93–102.
51
TABLE III: Results of numerical experiments
T 1000 1000 1000 1000 1100 1000 1100 1050 1040 1045 1048 1049 1049
p 100 100 100 102 100 103 103 103 103 103 103 103 103
r 0,83 0,83 0,84 0,84 0,84 0,84 0,84 0,84 0,84 0,84 0,84 0,84 0,83
pr 800 850 850 850 850 850 850 850 850 850 850 850 850
22 23 23 24 23 23 23 23 23 23 23 23 23
23 22 23 23 23 23 23 23 23 23 23 23 23
22 23 23 23 23 23 23 23 23 22 24 23 23
23 23 23 23 23 23 23 23 23 23 23 23 23
22 23 23 23 23 23 23 23 23 23 23 24 23
23 23 22 22 23 22 23 23 23 22 23 24 23
23 23 23 23 23 23 23 23 23 23 23 22 23
23 23 24 22 22 23 23 23 23 23 23 22 23
23 23 23 23 22 23 23 23 23 23 23 23 23
22 23 22 23 22 22 23 23 23 23 23 23 23
23 23 23 23 23 22 23 24 23 23 22 23 23
23 23 22 23 22 23 23 23 23 23 23 23 22
23 23 22 23 23 23 23 23 23 23 23 23 24
23 23 23 23 23 23 24 23 22 23 23 23 23
22 23 23 23 22 22 23 23 23 22 23 23 22
23 23 23 23 22 23 23 23 23 23 22 22 23
23 23 23 23 22 23 22 23 23 23 23 23 23
23 23 23 23 23 23 23 23 22 23 23 23 23
22 22 23 23 23 23 23 23 23 23 23 22 23
23 23 23 23 22 23 22 23 23 23 23 24 23
23 23 22 23 23 22 23 23 23 22 23 23 23
23 23 23 24 23 23 23 22 23 23 23 23 23
23 23 23 23 23 23 23 22 22 23 22 23 22
23 23 22 23 23 23 22 23 23 23 23 23 24
23 23 23 23 23 23 23 23 23 23 23 23 23
22 22 23 23 23 23 22 23 23 22 24 23 23
23 22 23 23 22 23 22 24 23 23 23 23 23
23 22 23 22 23 23 23 23 23 22 23 23 24
average 22,75 22,82 22,82 22,96 22,68 22,82 22,86 23 22,89 22,79 22,96 22,96 23
[7] M. Woźniak, D. Połap, R. K. Nowicki, C. Napoli, G. Pappalardo, and [17] S. Kirkpatrick and M. Vecchi, “Optimization by simulated annealing,”
E. Tramontana, “Novel approach toward medical signals classifier,” in Science, vol. 220, no. 4598, pp. 671–680, 1983.
Proceedings of IEEE International Joint Conference on Neural Networks [18] L. Ingber, “Very fast simulated re-annealing,” Mathematical and Com-
(IJCNN). 12-17 July, Killarney, Ireland: IEEE, 2015, pp. 1924–1930, puter Modelling, vol. 12, no. 8, pp. 967–973, 1989.
DOI: 10.1109/IJCNN.2015.7280556. [19] M. Woźniak and D. Połap, “On some aspects of genetic and evo-
[8] G. S. Walia and R. Kapoor, “Intelligent video target tracking using an lutionary methods for optimization purposes,” International Journal of
evolutionary particle filter based upon improved cuckoo search,” Expert Electronics and Telecommunications, vol. 61, no. 1, pp. 7–16, 2015, DOI:
Systems with Applications, vol. 41, no. 14, pp. 6315–6326, 2014. 10.1515/eletel-2015-0001.
[9] R. Bulatović, S. Bordević, and V. Dordević, “Cuckoo search algorithm: a [20] A. Corana, M. Marchesi, C. Martini, and S. Ridella, “Minimizing mul-
metaheuristic approach to solving the problem of optimum synthesis of a timodal functions of continuous variables with the simulated annealing
six-bar double dwell linkage,” Mechanism and Machine Theory, vol. 61, algorithm,” ACM Transactions on Mathematical Software, vol. 13, no. 3,
pp. 1–13, 2013. pp. 262–280, 1987.
[10] K. Chandrasekaran and S. Simon, “Multi-objective scheduling problem: [21] D. Svergun, “Restoring low resolution structure of biological macro-
hybrid approach using fuzzy assisted cuckoo search algorithm,” Swarm molecules from solution scattering using simulated annealing,” Biophys-
and Evolutionary Computation, vol. 5, no. 1, pp. 1–16, 2012. ical Journal, vol. 76, no. 6, pp. 2879–2886, 1999.
[11] A. Baykasoğlu and F. B. Ozsoydan, “An improved firefly algorithm for [22] I. Dupanloup, S. Schneider, and L. Excoffier, “A simulated annealing
solving dynamic multidimensional knapsack problems,” Expert Systems approach to define the genetic structure of populations,” Molecular
with Applications, vol. 41, no. 8, pp. 3712–3725, 2014. Ecology, vol. 11, no. 12, pp. 2571–2581, 2002.
[12] J. Cabello, J. Cejudo, M. Luque, F. Ruiz, K. Deb, and R. Tewari, [23] M. Woźniak, D. Połap, G. Borowik, and C. Napoli, “A first attempt
“Optimization of the sizing of a solar thermal electricity plant: Mathemat- to cloud-based user verification in distributed system,” in Proceedings
ical programming versus genetic algorithms,” in CEC’2009 Proceedings. of Asia-Pacific Conference on Computer Aided System Engineering (AP-
IEEE, 2009, pp. 1193–1200. CASE). 14-16 July, Quito, Ecuador: IEEE, 2015, pp. 226–231, DOI:
[13] D. Połap, M. Woźniak, C. Napoli, and E. Tramontana, “Is swarm 10.1109/APCASE.2015.47.
intelligence able to create mazes?” International Journal of Electronics
and Telecommunications, vol. 61, no. 4, pp. 305–310, 2015, DOI:
10.1515/eletel-2015-0039.
[14] D. Połap, M. Woźniak, C. Napoli, and E. Tramontana, “Real-time
cloud-based game management system via cuckoo search algorithm,”
International Journal of Electronics and Telecommunications, vol. 61,
no. 4, pp. 333–338, 2015, DOI: 10.1515/eletel-2015-0043.
[15] M. Clerc and J. Kennedy, “The particle swarmexplosion, stability and
convergence in a multidimensional complex space,” IEEE Transactions
on Evolutionary Computation, vol. 6, no. 1, pp. 58–73, 2002.
[16] I. Fister, X. S. Yang, J. Brest, and I. F. Jr., “Modified firefly algorithm us-
ing quaternion representation,” Expert Systems with Applications, vol. 40,
no. 18, pp. 7220–7230, 2013.
52