Heuristic algorithms are versatile method to solve many problems in which, for various reasons it is difficult to find a solution. These methods do not guarantee obtaining the optimal solution, but found with their help solutions are usually accurate enough and sufficient to deal with analyzed problems.
The word 'heuristic' comes from the Greek 'heurisko' (it means: I find) [18] These are rules which help to find (discover) best approximation of solution. Various applications of these methods show that evolutionary computation can help in decision support systems. Heuristic methods are efficient in image processing [13], [15] but also voice recognition [10], while devoted combinations of artificial intelligence approaches are implemented together with other solutions into complex systems [8] and robotics [17]. The paper presents use of two population heuristics in darts play. Darts is a game in which darts are thrown at a dartboard fixed to a wall [1]. Generally, the accuracy of hitting into the appropriate pole of the dartboard is the main goal of the game. Appropriate speed and angle of throw is necessary to obtain success. In the paper the main goal is to demonstrate how to use heuristics in order to choose the parameters mentioned. It will be also analyzed a situation in which the setting of the player is not optimal, ie. when he stays not directly in front of the dartboard. To solve the problem, the Genetic Algorithm and Ant Colony Optimization (ACO) is applied. Evolutionary algorithm is treated as the classical metaheuristic using genetic Copyright c 2017 held by the authors. operators like mutation or crossover. ACO is a type of Swarm Intelligence based on real ants behaviour. The results obtained in both methods and approptiate comparison is also presented at the end of work.
The article is divided into several sections. In section 2. it will be explained physical model playing darts. Genetic Algorithm, genetic operators like mutation and crossover, selection and other details connected with this topic will be analyzed in section 3. In section 4. there is described second metaheuristic: Ant Colony Optimization. In the last section, the results of both methods will be compared.
In dart game player is obliged to collect fixed sum of points that are signed to his account only if a thrown dart hits an appropriate part of the dartboard. Considering this short description of rules it seems obvious that accuracy of throw plays main role in dart game. In the presented approach the model simulates trajectory of a throw based on three variables: speed, α and β angles; speed is initial speed of a dart, α angle lies between vertical and horizontal components of velocity and β describes angle between horizontal and side velocity as shown on Fig. 1. Friction force was skipped because its role is negligible -it is assumed that competitions take place in closed spaces. Dart is treated as a point. General formula to determine trajectory of a thrown dart is:
where x − distance, g − standard gravity (about 9.80665 m s ), v x − horizontal speed.
Distance obtained by a dart may be expressed as:
hence The formula (3) describes height of a dart dependent on time while the rest of unknowns are treated as parameters. In order to describe the curvature of dart's trajectory the following formula can be used:
where v z − initial side speed of the dart (shown on Fig. 1), t − time. Fig. 2 presents view of Fig. 1 on plane y = 0. There are shown dependencies between v x and v z .
To estimate the accuracy of a throw we need to know when exactly a dart hits the wall. According to official rules of a dart game the distance between dartboard and players has to be exactly 2.37m. Once it is assumed that player may stand not perfectly in front of the dartboard the whole horizontal distance will be as followed:
where d − vertical distance from a perfect position (2.37m), r − difference between optimum position and actual position of a player. The last step is introduction of (5) into equation (1) and on the basis of it, to determine the vertical position of the dart. Both vertical and horizontal distance from center of the dartboard will be used to judge the value of fitness function.
Genetic Algorithm is a multi-agent algorithm based on idea of evolution that leads to survival only the best genotypes in whole population. Genetic algorithms have grown in popularity through the work of John Holland, especially by his book [2]. Until Genetic Algorithm Conference in Pittsburgh (Pennsylvania), the research was mainly theoretical, however after that more and more applications has been introduced. Evolutionary methods are one of the most popular and they begin to play significant role of classical heuristics. This makes that the action of heuristics of different types are compared with the work of GA.
The main body of the Genetic Algorithm consists of modules that might be modified up to needs of user. Three basic modules of an algorithm are:
• Succession General structure of GA is presented below in a form of pseudocode.
h] Pseudocode of Genetic Algorithm Input: number of genotypes in population: m, number of iteration: I, boundary of the domain, coefficients: probability of crossover p c , probability of mutation p m Output: coordinates of minimum, value of fitness function Initialisation:
Creating the initial population
At the beginning, the algorithm randomly generates genotypes. In presented case each genotype consists of three genes: speed, α and β. Every genotype is separately graded by fitness function:
where s − distance from perfect position, v x − speed of dart, h − height of throw. g − standard gravity d − vertical distance from a perfect position (2.37m) p − height of a center of a dartboard (1.73m) perfect position − a thrower is standing exactly on the center in front of a dartboard Selection module picks two genotypes selected randomly and compares their fitness functions. The better one is picked to temporary population. Whole procedure is repeated until new population has m genotypes in it. This classical approach is called Tournament Selection.
Mutation is an genetic operation which works on single genotype and probability of its occurrence is usually smaller than 10%. The following formula presents mechanism of averaging mutation:
where x k i − the i − th genotype of k − th population, ξ r − vector random generated with normal distribution N (0, 1) Crossover process takes two parental genotypes from temporary population to evolve them into one new genotype by mixing their genes. There also exist modifications where e.g. each gene is mixed separately with different genotypes, however to keep this procedure simple and transparent the first approach was implemented:
where x k i − the i − th genotype of k − th population, ξ U (0,1) − number randomly generated from uniform distribution U (0, 1), Elitism Succession relies that the population P i+1 is formed by picking m best solutions from set P i ∪ O i , where O i is a set of offsprings − solutions coming from genetic operators.
Ant Colony Optimization is biologically inspired multiagent algorithm. The base of this algorithm was invented by Marco Dorigo [4] -he used it to solve combinatorial problem (more specifically, travelling salesman problem). The approach presented in the paper was developed by M. Duran Toksari [7] -he applied Ant Colony Algorithm in continuous problem. It is not the only proposition of ACO for solving continuous problem. Other modification of this algorithm based on different approach was analyzed by K. Socha and M. Dorigo [11]. The idea of Ant System Algorithm is based on behaviour of real ant colony. In the presented case ants are solutions (optimum of a function). Ants during search can communicate with each other by using chemical substance called pheromone. On more attractive roads ants leave more quantity of pheromone so next ants know which path is more promising. Furthermore, pheromone is evaporating from nonused paths. It means that pheromone is impulse to search. On the following iterations search area is narrowed so ants try to find more accurate solution and they abandon unpromising roads. After fixing input parameters, the algorithm is generating m ants in form:
where k − number of ant, k = 1, ..., m, S − number of dimensions. i − number of iteration Then is necessary to find the best ant in population in current iteration: x best (it is best solution until this iteration). Additionaly, it is assumed x opt = x best . The next step is attempt to find a better place for the nest, what is realized by formula:
where dx = dx 1 , dx 2 , ..., dx S − vector of pseudorandom value, dx i ∈ [−α j , α j ] in the case of angles, dx i ∈ [−β j , β j ] in the case of speed, α j , β j -parameters of ACO procedure, j − number of iteration.
This part of program is intended to exploration the domain. Now it should be checked if colony found better place to the nest. If at least one point has better value of fitness function (x best j is better than x opt ), then the nest is moving (x opt = x best j ). Last step is decreasing the length of jump (searched domain will be smaller).
In this case λ is responsible for reduction of domain during finding angles: α and β. ω is in charge of narrowing neighbourhood in search of speed. Then calculations are continued in smaller domain. The parameters λ and ω should be chosen carefully. If the domain is wide, λ and ω could be greater than 0.5. If a territory for ants is relatively narrow, λ or ω may be close to 0.1. In multi-dimensional problems it may define other parameter for every coordinate.
The purpose of this paper is presenting heuristic approach to the game of darts. Two algorithms have been tested: Genetic Algorithm and And Colony Optimization. It was done for the same input data and results were compared in Tab I, obviously both algorithms had exactly the same fitness function (6). The stopping criterium was number of iterations. In the case of Genetic Algorithm it was 50 iterations for all measurements while researches by using of Ant Colony Optimization was done by 20 internal iterations and 30 external iterations. Generally Ant Colony Optimization algorithm provides higher precision results (in two tested positions of thrower results was better by using Genetic Algorithm − font is bold in better scores). It was explored different distances from center position and height of thrower. In every case it was obtained great approximation of perfect throw. Graphic interpretation of our results is presented on the Fig. 6-7, what can be treated as warranty that given results are right data.
In the physical model it was applied Manhattan metrics [12] in order to describe the distance between center of a dartboard and the point where dart hits. Due to the fact that heuristic algorithms give only approximate results it is unlikely to obtain fitness function equal to 0, however presented results, especially from Ant Colony Optimization are close enough to claim that presented algorithms solve this problem really well. The calculations, which results were presented, were designed to study the mechanism and capabilities of both heuris-