Transcript SEC111. - University of Georgia

Improving the Genetic Algorithm Performance in
Aerial Spray Deposition Management
University of Georgia
L. Wu, W.D. Potter, K. Rasheed
USDA Forest Service
J. Ghent, D. Twardus, H. Thistle
Continuum Dynamics
M. Teske
Presentation Overview






SAGA
From SAGA to SAGA2
From SAGA2 to SAGA2NN
SAGADO
Results
Conclusion and future work
SAGA:
aerial spray deposition management problem



AGDISP (Aerial Spray Simulation Model) predicts the
deposition of spray material released from an aircraft.
The prediction is based on a set of spray parameter values
as well as constant data. The total combination of possible
spray parameters generates a huge search space (NP hard).
SAGA (Spray Advisor using Genetic Algorithm) was
developed to heuristically search for an optimal or nearoptimal set of input parameters needed to achieve a certain
aerial spray deposition.
SAGA:
how does SAGA work



SAGA sends a set of spray parameters to AGDISP.
AGDISP returns three spray output values: VMD (the
deposition composed of Volume Median Diameter), drift
fraction, and COV (the Coefficient of Variance).
Based on the fitness function values mapped from the
spray output values, the GA attempts to evolve an
improved set of parameters.
SAGA:
fitness function



The goal is to minimize the drift fraction, minimize the
COV, and minimize the difference between the output
VMD and the desired VMD.
This is actually a multi-objective optimization problem,
where a weighted-sum approach is applied.
Fitness = 100  [50  (1.0 – DriftFraction) + 25  (1 COV) + 25  VMDTerm], where
VMDTerm = 1.0 – abs(1.0 – VMD/VMDCenter)
From SAGA to SAGA2:
the improvement of SAGA2



The weakness of SAGA
The development of SAGA2 ((Spray Advisor using
Genetic Algorithm version 2)
The improvement of SAGA2
– SAGA2 replaces the original generational genetic
algorithm with a steady-state genetic algorithm.
– SAGA2 replaces the original roulette wheel selection
with tournament selection.
– SAGA2 combines several kinds of crossover and
mutation operators, and applies them with respective
possibilities.
From SAGA to SAGA2:
the interface of SAGA2
the interface to customize
SAGA2 parameters
the main interface of SAGA2
the interface to preset spray parameters
From SAGA2 to SAGA2NN:
the improvement of SAGA2NN


The development of SAGA2NN (Spray Advisor using Genetic
Algorithm version 2 with Neural Network)
The improvement of SAGA2NN
– SAGA2NN generates the initial population from a large pool
of individuals.
– SAGA2NN does various crossover and mutation operations
for each crossover and mutation, and selects the one with the
highest fitness as the candidate.
– SAGA2NN uses a neural network to approximate the fitness
during the above process.
From SAGA2 to SAGA2NN:
how does a neural network work



Data mining
Data training
– Learning rule: backpropagation with momentum
– Interface of ANN:
Data mapping
SAGADO

GADO (Genetic Algorithm for Design Optimization) is a
general-purpose approach to solving the parametric design
problem.
– GADO uses a steady-state GA.
– The selection scheme is ranking selection.
– The replacement strategy is a crowding technique.
– Several crossover and mutation operators are used, in
which the most important one is guided crossover.
 The development of SAGADO (Spray Advisor using
Genetic Algorithm for Design Optimization).
Results:
general result



We ran these methods on several practical spray parameter
specifications provided by Forest Service managers.
The convergence criterion is avgfitness/maxfitness>0.999.
The GA will stop when it meets the convergence criterion,
otherwise it stops after 5000 evaluations.
The maximum fitness values SAGA2 and SAGADO
achieved are better than SAGA in every parameter setting.
SAGA2NN obtains much better maximum fitness value in
the first few hundred evaluations. Its lead is offset later,
but it takes far fewer evaluations to converge.
Results:
evolution process of some parameter settings
no variable constraint
variable constraint:
Aircraft ID=106,
Swath Width=2.25
variable constraint:
Aircraft ID=5,
Swath Width=2.3
Conclusion and future work

Exquisite choice of type of GA, selection, crossover and
mutation operator can boost GA performance.
 Applying a neural network to the genetic algorithm does
not achieve a much better result. We think the reason is
that the advantage of the neural network is counteracted by
premature convergence of the GA. SAGA2NN converges
very fast, which is useful in real aerial spray applications
because it can get the near-optimal result by far fewer
simulations.
 Currently we are working to apply other heuristic search
approaches, such as simulated annealing, in aerial spray
deposition management, and plan to compare their
performance with SAGA2, SAGADO and SAGA2NN.