-A paper illustrates the use of two metaheuristics: Genetic Algorithm and Ant Colony Optimization in darts play. The goal of the game is to hit on the centre of the dartboard. Both the creation of physical model and the optimization of the problem (based on heuristic algorithms) are presented in details. Two approaches are discussed and compared with respect to the results.
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.
where
x
g
vx
hence
(
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: y = x tan( )
g 2 v2 x x2; distance, standard gravity (about 9.80665 ms ), horizontal speed.
Distance obtained by a dart may be expressed as:
x = vx t;
y(t) = vx t tan( )
g t2
2
The formula (
Fig. 2 presents view of Fig. 1 on plane y = 0. There are shown dependencies between vx and vz.
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:
x = pd2 + r2;
(
end 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 (
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:
Selection Genetic Operators – Mutation – Crossover
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 pc, probability of mutation pm Output: coordinates of minimum, value of fitness function
Creating the initial population P1 = fx1; x2; :::; xmg Searching xbest in initial population P1; xopt = xbest.
i = 1 while i < I do
Pi = Selection(Pi) Oi = Genetic Operators(Pi) Pi+1 = Succcession(Oi, Pi) Searching xbest in Pi+1.
j if xbest is better than xopt then
j xopt = xbest
j
end if
i++
end while
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:
(vx; ; ) = jpd2 + (d tan )2
1
tan(90
+ jpd2 + (d tan )2 tan
+ 0:5 g d2+(vdxt2an )2 (p
h)j,
)
sj +
(
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:
y = xik + r where xik r the i th genotype of k th population, 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:
y = xik + U(0;1)(xjk
xik)
where
xik 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 Pi+1 is formed by picking m best solutions from set Pi [ Oi, where Oi 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.
h] Pseudocode of Ant Colony Optimization Input: number of ants: m, number of iteration inside: I, number of iteration outside: n, boundary of the domain, initial parameters: , , coefficients: , ! Output: coordinates of minimum, value of fitness function
Creating the initial colony of ants. C1 = fx11; x21; :::; x1mg Searching xbest in initial colony; xopt = xbest.
i = 1 while i < n do j = 1 while j < I do
Moving the nest of ants - defining new territory of ant colony.
Searching xbest in present colony.
j if xbest is better than xopt then
j xopt = xbest
j end if end while
Defining new search area (narrowing of the territory). end while end
After fixing input parameters, the algorithm is generating m
ants in form:
xik =
xik;1; xik;2; :::; xik;S ;
(
i number of iteration Then is necessary to find the best ant in population in current iteration: xbest (it is best solution until this iteration).
Additionaly, it is assumed xopt = xbest. The next step is
(
8k xjk = xopt + dx; where dx = dx1; dx2; :::; dxS vector of pseudorandom value, dxi 2 [ j ; j ] in the case of angles, dxi 2 [ 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 (xjbest is better than xopt), then the nest is moving (xopt = xbest). Last step is decreasing the length of jump (searched j domain will be smaller).
j = j = ! j 1; j 1; 2 (0; 1) 2 (0; 1) 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.
V. RESULTS
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 (
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.
Heuristic algorithms are one of the best option in problems hard to optimization. The simple idea and in consequence implementation makes that these methods are often used by researchers in many fields. It is possible to find results with high precision by using these methods.
The calculations, which results were presented, were designed to study the mechanism and capabilities of both heuristics. All solutions are on satisfactory level what proves that both the mathematical model and optimization procedure have been chosen correctly. One can use heuristic algorithms to solving other real problems, perhaps another game or some more complicated models.