Page 46 - Read Online

Wang et al. Intell Robot 2023;3(4):538-64 I http://dx.doi.org/10.20517/ir.2023.30 Page 13 of 27

5. SOLUTION ALGORITHM
It is the key to obtaining the optimal control input in the current step among numerous control decision sets
for CSMTPE; therefore, this problem can be transformed into a standard nonlinear optimization problem.
Among the normal solutions, the genetic algorithm (GA) is a general optimization algorithm with strong
adaptability [27] . GA is designed and proposed according to the evolution law of organisms in nature. It is a
computational model simulating the natural selection and genetic mechanism of Darwin’s biological evolution
theory and is a method of searching for the optimal solution by simulating the natural evolution process.

In this section, a priority-encoding method for CSMTPE is proposed, and a fine-adjustment mechanism based
on this encoding method is designed. Finally, this mechanism is applied to various chromosome operations
of traditional GA, forming a priority-encoded IGAFA algorithm to solve the problem above.

5.1. Priority-encoded IGAFA algorithm
5.1.1. Priority-encoding method
Considering the potential issue of chromosomes being sensitive to small changes and having a high proba-
bility of illegitimate offspring caused by traditional direct encoding method, a priority list of the indices of
mission grid cells is used as an indirect encoding method in this paper. The chromosome is encoded as
} where , = 1, 2, , represents the index of destination cell in mission grid and
= { 1 , 2 , , , ,
is the length of the priority list. The UAVs sequentially obtain their current destination cells from the priority
list, and similarly obtain the next destination cells after reaching the current ones until the end of the search
steps. In order to move to the destination cell, a UAV will move one cell toward the nearest, unoccupied, and
reachable cell in the direction of the destination cell in each search step. Due to the fixed search step size,
denoted as , the probability of activated genes in chromosomes decreases with the shift of chromosomal lo-
cation of genes, and the chromosome with such characteristic is defined as the priority-encoded chromosome
in this paper.

Firstly, this encoding method can solve the problem of illegal offspring chromosomes, ensuring the efficiency
oftheiterativeprocessbycomplyingwiththeUAVmovingrules. Secondly, changingasinglegenewillnotalter
or only slightly alter the search path of the destination cells before and after that gene, reducing the sensitivity
of the chromosome while ensuring the randomness of the search path; in other words, the priority-encoded
path will be more conducive to focusing on the long-term search benefits, rather than the short-term benefits
of each move.

5.1.2. Fine-adjustment mechanism
A fine-adjustment mechanism is proposed to improve the efficiency of evolution in traditional GA in this
paper, which mainly optimizes the stochastic process in the evolution to fine-adjust the evolution direction.
The fine-adjusted localization and mutation of genes are included in the specific applications as follows:
(i) Fine-adjusted localization of genes
Considering the problem of uneven distribution of key genes in priority-encoded chromosomes, a ran-
dom probability density function for selecting genes with the iteration step is designed as follows:

− ·
( ) = (26)
1 − −
where ∈ [0, 1) is the random variable, and is the distribution influence factor that changes with the
iteration step , which is defined as:

( )
2 −1
= · · (27)