INTRODUCTION
The Geometric Dilution of Precision (GDOP) concept was originally used as a
criterion for selecting the optimal 3D geometric configuration of satellites
in GPS. When enough measurements are available, the optimal measurements selected
with the minimum GDOP can help reduce the adverse geometry effects, thereby
improving the location accuracy. However, excessive or redundant measurements
may increase the computational overhead and may not provide significantly improved
location accuracy. It is very critical to select a subset with the most appropriate
measurement units rapidly before positioning (Chen and Su,
2010).
Several methods based on GDOP have been proposed to improve the GPS positioning
accuracy (Zhu, 1992; Hsu, 1994;
Phatak, 2001; Zhong and Huang, 2006;
Zhang and Zhang, 2009). Most, if not all, of those methods
need matrix inversion to calculate GDOP. Though they can guarantee to achieve
the optimal subset, the computational complexity is usually too intensive to
be practical.
The interest in Neural Networks (NNs) comes from the networks’ ability
to mimic human brain as well as its ability to learn and respond. As a result,
NNs have been used in a large number of applications and have proven to be effective
in performing complex functions in a variety of fields. These include pattern
recognition, classification, vision, control systems, approximation and prediction.
Adaptation or learning is a major focus of neural net research that provides
a degree of robustness to the NN model. In predictive modeling, the goal is
to map a set of input patterns onto a set of output patterns. NN accomplishes
this task by learning from a series of inputoutput data sets presented to the
network. The trained network is then used to apply what it has learned to approximate
or predict the corresponding output (Mosavi, 2007).
Instead of directly solving the GDOP equations and avoiding the complicated
processing of matrix inversion, Simon and ElSherief (1995)
rephrase the GDOP calculation as approximation problems and employ NNs to solve
such problems. However, solving classification and approximation problems using
NN usually suffer from the long training time and difficulty in determining
the NN architecture. Besides, the overfitting problem degrades the performance
of NN applications when the numbers of features and training patterns are large.
Though in the experimental results reported by Jwo and Chin
(2002) and Jwo and Lai (2007), NN outperforms the
traditional methods; the training time and performance can be further improved.
The Genetic Algorithm (GA) is a stochastic global search method that mimics
the metaphor of natural biological evolution. GAs operate on a population of
potential solutions applying the principle of survival of the fittest to produce
(hopefully) better and better approximations to a solution. At each generation,
a new set of approximations is created by the process of selecting individuals
according to their level of fitness in the problem domain and breeding them
together using operators borrowed from natural genetics. This process leads
to the evolution of populations of individuals that are better suited to their
environment than the individuals that they were created from, just as in natural
adaptation (Kim and Adeli, 2001).
In this study, GA approach is applied for GPS GDOP approximation and classification, without complicated matrix inversion. GA is employed to learn the functional relationships between the entries of the GDOP measurement matrix and the final GDOP equations. This method is applicable to general GDOP calculation regardless to the number of satellite signals being processed by the receiver. The performance and computational benefits of using GA for GDOP approximation and classification are discussed.
GDOP CALCULATION USING CONVENTIONAL MATRIX INVERSION METHOD
In GPS applications the GDOP is often used to select a subset of satellites
from all visible ones. In order to determine the position of a receiver, pseudoranges
from n≥4 satellites must be used at the same time. By linearizing the pseudorange
equation with Taylor’s series expansion at the approximate (or nominal)
receiver position, the relationship between pseudorange difference (Δρ_{i})
and positioning difference (Δx_{i}) can be summarized as follows
(Doong, 2009):
which is written in a compact form as:
The n≥4 matrix H is formed with direction cosines e_{i1}, e_{i2} and e_{i3} from the receiver to the ith satellite and V denotes a random noise with an expected value of 0. The difference between the estimated and true receiver positions is given by:
where, H^{T} denotes the transpose of H and M = H^{T}H, called the measurement matrix, is a 4x4 matrix no matter how large n is. It can be shown that the measurement matrix is symmetric and nonnegative and thus it has four nonnegative eigenvalues. Assuming E{V^{T}V} = σ^{2}I, then:
The GDOP factor is defined as the square root of the trace of the inverse measurement matrix:
Because GDOP provides a simple interpretation of how much positioning precision can be diluted by a unit of measurement error, it is desirable to choose the combination of satellites in a satellite constellation with GDOP as small as possible.
STANDARD GENETIC ALGORITHM
GA starts with an initial population whose elements are called chromosomes. The chromosome consists of a fixed number of variables which are called genes. In order to evaluates and rank chromosomes in a population, a fitness function based on the objective function should be defined. Three operators must be specified to construct the complete structure of the GA procedure; selection, crossover and mutation operators. The selection operator cares with selecting an intermediate population from the current one in order to be used by the other operators; crossover and mutation. In this selection process, chromosomes with higher fitness function values have a greater chance to be chosen than those with lower fitness function values. Pairs of parents in the intermediate population of the current generation are probabilistically chosen to be mated in order to reproduce the offspring. In order to increase the variability structure, the mutation operator is applied to alter one or more genes of a probabilistically chosen chromosome. Finally, another type of selection mechanism is applied to copy the survival members from the current generation to the next one. Steps of GA implementations are as follows:
• 
Step 1: Initialization: Generate an initial population
P_{0}. Set the crossover and mutation probabilities p_{c}∈(0,1)
and p_{m}∈(0,1), respectively. Set the generation counter t
=1 
• 
Step 2: Selection: Evaluate the fitness function F
at all chromosomes in P_{t}. Select an intermediate population P_{t}'
from the current population P_{t} 
• 
Step 3: Crossover: Associate a random number from (0,
1) with each chromosome in P_{t}' and add this chromosome to the
parents pool set SP_{t} if the associated number is less than p_{c}.
Repeat the following steps until all parents in SP_{t} are mated 

• 
Choose two parents p_{1} and p_{2} from SP_{t}.
Mate p_{1} and p_{2} to reproduce children c_{1}
and c_{2} 

• 
Update the children pool set Sc_{t} through SC_{t}:=
SC_{t }∪ {c_{1}, c_{2}} and update SP_{t}
through SP_{t}:= SP_{t}{p_{1}, p_{2}} 
• 
Step 4: Mutation: Associate a random number from (0,1)
with each gene in each chromosome in P_{t}', mutate this gene if
the associated number is less than p_{m} and add the mutated chromosome
only to the children pool set SC_{t} 
• 
Step 5: Stopping conditions If stopping conditions
are satisfied, then terminate. Otherwise, select the next generation P_{t+1}
from P_{t}∪SC_{t}. Set SC_{t} to be empty, set
t:= t+1 and go to step 2 
GPS GDOP approximation using GA: In Eq. 4, GDOP is
mainly evaluated by (H^{T}H)^{1}, where geometry matrix H is
given by Parkinson and Spilker (1996):
where, Ei and Azi are elevation and azimuth angles of satellite views in space
with respect to receiver position, respectively. Nevertheless, it is not a good
practice to invert the normal equations matrix (Su and Wu,
2008; Wu and Su, 2009). Since, M is a symmetric
matrix, so it can be represented by Eq. 6:
This study proposes GDOP approximation by linear combination of a_{i} as Eq. 7:
The fitness function is the sum of squared error and is defined as:
where e = dy, d is the target output and
is the output of method. Obviously the objective is to minimize J subject to weights w_{i}. The w_{i} coefficients are calculated by using GA.
GPS GDOP classification using GA: Suppose there are some 2D data as are shown in Fig. 1. For classifying them, we can specify two lines F_{1}(x,y) = a and F_{2}(x,y) = b that make 3 areas as follows:

Fig. 1: 
2D data classification (the legends of (*), (ο)
and (□) present three types data) 
In the search space, every constellation of four GPS satellites is represented
as a seven dimensional element containing arrays of matrix that use for the
GDOP calculation:
GA by using these characteristics provides two linear vectors that classify GDOP into 3 groups.
where, F_{1} and F_{2} are two thresholds for GDOP classification. The w_{i} coefficients are calculated by using GA. Similarly, classification into more groups is feasible based on the same philosophy.
COMPUTER SIMULATIONS
The data file containing of 900 patterns was used for testing the proposed
method. In Fig. 2a and b, the GDOP solutions by matrix inversion
(using Eq. 4) is represented with , the while the GDOP approximated
by the proposed methods is shown by *. The GDOP residual is defined as the difference
between the GDOP value by matrix inversion and by the proposed approach:
GDOP_{Matrix inversion}GDOP_{Approximated} 
The maximum, minimum and RootMeanSquare (RMS) error are used as the error measure for evaluating approximation performance. RMS value is computed using:
where, M is number of tests, GDOP_{Matrix inversion} is the GDOP from
direct matrix inversion obtained from Eq. 4 and GDOP_{Approximated}
is output of the model.

Fig. 2: 
(a) Real versus approximated GPS GDOP and (b) its approximation
error 
Table 1: 
Error of GPS GDOP approximation using the proposed method 

Table 2: 
Comparison of accuracy and CPU time of GA and NN approaches
for GPS GDOP calculation 

Table 3: 
GDOP classification 

Table 1 shows three statistical measures of approximations
error using the proposed method.
Table 2 presents the comparison of accuracy and CPU time of GA and NN approaches for GPS GDOP calculation. The simulation results demonstrate that GA approach is accurate and faster than NN approach.
The data file containing of 900 patterns was used for testing the proposed classification method. For data classification according Table 3, G_{1} = 3 and G_{2} = 5 are considered.

Fig. 3: 
The value of fitness function for GPS GDOP classification
(GDOP<3 and GDOP>3) 

Fig. 4: 
The value of fitness function for GPS GDOP classification
(3<GDOP<5 and GDOP>5) 
At first, all data were divided into two categories. Class1 that their GDOP values are smaller or equal to 3. Class 2 that their GDOP values are lager than 3. Then, the data with GDOP>3 were divided into two categories. First class that their GDOP values are smaller or equal to 5. Second class that their GDOP values are lager than 5.
Figure 3 and 4 show the value of fitness function that expresses the number of errors in classification. As you can see GA classify these data with 100% accuracy. This experiment was performed with G_{1} = 3 and G_{2} = 6 and similar results were obtained.
Simon and ElSherief (1995), Jwo
and Chin (2002) and Jwo and Lai (2007) approximate
and classify GPS GDOP using NNs. Advantages of the proposed method based on
GA in this study than references of mentioned are simple, low cost, easy to
design and accurate. It has the structure complexity less than for hardware
implementation. It also requires the memory less than for software implementation.
CONCLUSIONS
To analyze the performance of navigation it is necessary to calculate the DOP that provides positioning accuracy. Among number visible satellites from the user’s position, a set of satellites which are in better geometry is needed to find minimum GDOP. The matrix inversion method for GDOP calculation is rather time consuming and presents a calculation burden. This paper has presented application of GA for GPS GDOP precise modeling without complicated matrix inversion. GAs are computer programs that mimic the processes of biological evolution in order to solve problems and to model evolutionary systems. Using the proposed method, the calculations costs of GPS GDOP can be reduced. In compare with neural network approach, GA is faster and more precise for approximation and classifying GPS GDOP. So with the proposed method, the processing costs for GPS positioning with low GDOP can be reduced (no need to training time and powerful processor). The results show that the proposed method has high degree of accuracy and the number of training iterations is greatly reduced.