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