H. B. Zhu et al. / Natural Science 3 (2011) 301-306

Copyright © 2011 SciRes. OPEN ACCESS

303

lation.

3) Make selection of the best-fit individuals for re-

production.

4) Breed new individuals through crossover and

mutation operations to give birth to offspring.

5) Evaluate the individual fitness of new individuals.

6) Replace least-fit population with new individuals.

3.2. GA in the PF Process

The particles degeneration phenomenon is a wide-

spread problem of particle filter algorithm. In order to

eliminate that phenomenon, the re-sample algorithm is

introduced as depicted in the Section 2. In the re-sam-

pling process of regular particle filtering, the particles

with bigger weights will have more offspring, while the

particles with smaller weights will have few or even on

offspring. It inspires us to reduce the number of particles

with small weights and find more particles with big

weights, which will make the proposal distribution more

closed to the poster distribution. But re-sampling algo-

rithm causes another problem which loses particle diver-

sity and reduces the performance of the particle filter

algorithm, and even makes the distribution function of

particle filter algorithm spread. Therefore GA is pro-

posed in PF process.

The choice of fitness function is the most important

issue of using genetic algorithm. In the proposed algo-

rithm, each particle in particle algorithm is looked upon

a pair of chromosome. We want to find more particles

with bigger weights, so the fitness can be chosen as the

value of weights directly. As usually the aim of GA al-

gorithms is to minimize the fitness function, so the fit-

ness is the minus value of particle weight in the GA-PF

as follows:

1

0: 11:

ˆ

ˆˆ ,

iii

ttt t

i

tii

tt t

pyxpxx

fitness

qx xy

(8)

Secondly, it’s already so large to compute consump-

tion of particle filtering that the GA process computing

consumption introduced should be reduced. In the

GA-PF algorithm, for every particle, at first, a random

number in the range of 0 and 1 will be generated, and

only when the number is smaller than a predefined

threshold, the GA process can be conducted. A new type

of GA process – one step predefined GA is introduced.

In this process, only when the new location is better than

the original one, the particle will move to the new one,

and the location updating process will be conducted only

one time in each particle filtering generation. The new

particle is then used in the next iteration of the algorithm.

Commonly, the algorithm terminates when either a

maximum number of generations has been produced, or

a satisfactory fitness level has been reached for the par-

ticle.

Finally, the location of best particle determines the

direction of particle updating in current generation and

itself location. And as in the one-step predefined GA

process, particle need not remember its individual best

location of history; the updating mode uses the social

only mode of GA algorithm.

3.3. The GA-UPF Algorithm

In this section, a brief description of UPF is presented

as follow:

11

ijij ij

xtxt vt

(9)

max min

max

max

t

wwt

ww g

(10)

The mentioned one-step predefined GA process is

used in the UPF algorithm. The information of UPF al-

gorithm can be found in [3,4]. Where

1, 2,,jDn,

1, 2,,in, n is the size of the

population and Dn is the Dimension of the space sear-

ched; w is the inertia weight, generally updated as

Eq.3 [4], and max

is the maximal evolution genera-

tions. 1

c and 2

c are two positive constants. And the

GA-UPF algorithm can be decried as Figure 2.

The detailed process of GA-UPF is as follow:

1) Initial chromosome sample: Draw the new particle

group

, 1,2,,

i

t

iNfrom the prior

1tt

pxx

;

2) Assign weights: Every kind of GA has to find an

effective coding scheme. Real matrix encoding is ap-

plied to estimate the parameters for sequential UPF al-

gorithm.

For each loop:

3) Selection: The fitness of each chromosome set as

measuring probability in [5], and using Roulette Wheel

Selection which the most commonly methods to choose

the higher fitness chromosomes, the terminal chromo-

somes is the model of offspring;

4) Crossover: At this stage, arithmetic crossover is

widely used for the chromosome encoded by Real matrix.

In arithmetic crossover, a pair of new individual is gen-

erated by the linear combination of a pair of parent indi-

vidual:

1

1

ii j

tt t

ji

tt t

xx

xx

(11)

Here

0, 1

, ,

ij

tt

x is the pair of parent indi-

vidual

,

ij

tt

x

is the pair of new individual

5) Mutation:

is a random real;