Remark 38.1 In Carp et al. (2013) we presented an accurate procedure for the
computation of the smallest minimizer from Step 2. of the algorithm H.
Han proves that the sequence (x
k ) k ! 0 generated with his algorithm converges to
a least squares solution of the inconsistent system (38.11). Unfortunately, in Step 1
of the algorithm he proposed the usage of the Moore-Penrose pseudoinverse of A I k ,
which is not a good choice for large and sparse matrices. In order to overcome this
difficulty we proposed in Carp et al. (2015) a modification of Step 1 of Han’s
algorithm as follows:
Step 1p. Find I k ¼ I(x
k ) and compute an approximation d
k , j
2 ℝ
n of the minimal
norm solution of the linear equalities least squares problem
k A I k d À b I k À A I k x
k
À
Á k¼ min!
ð38:15Þ
by performing j ! 1 iterations of the Extended Kaczmarz algorithm from Popa
(1998), with 0 as initial approximation on (14).
We will call MH the Han algorithm with Step 1 replaced by Step 1p. In Carp
et al. (2015) we proved a convergence result similar with Han’s one, for the
sequence (x
k ) k ! 0 generated with algorithm MH.
38.3 The Genetic Algorithm
Genetic Algorithms (GAs) are adaptive heuristic search algorithms, specially
designed to find good solutions to problems that were otherwise computationally
unsolvable. GAs are based on the evolutionary ideas of natural selection, applying
the principle of ‘survival of the fittest’ on a population of potential solutions
encoded as chromosomes, selecting individuals according to their level of fitness,
and mating them together using some recombination operators to produce better
approximations to a solution (see Sivanandam and Deepa 2008).
38.3.1 Encoding and Initialisation
A GA starts by chromosome encoding and initialisation. A chromosome is a
feasible sequence of genes and in our model is encoded using an integer array
having size equal to mn; each element of this array denotes the number of units
transported, y l (see (38.6)). In order to generate feasible chromosomes, the equality
constraints from (38.7) are imposed for each chromosome by applying a procedure
that randomly generates appropriate integers. After encoding the chromosomes, we
set the genetic algorithm parameters (population size, maximum number of generations, crossover and mutation probabilities) and generate the initial population.
38 Genetic Versus Han-Type Algorithms for Maritime Transportation Problems
635
computation of the smallest minimizer from Step 2. of the algorithm H.
Han proves that the sequence (x
k ) k ! 0 generated with his algorithm converges to
a least squares solution of the inconsistent system (38.11). Unfortunately, in Step 1
of the algorithm he proposed the usage of the Moore-Penrose pseudoinverse of A I k ,
which is not a good choice for large and sparse matrices. In order to overcome this
difficulty we proposed in Carp et al. (2015) a modification of Step 1 of Han’s
algorithm as follows:
Step 1p. Find I k ¼ I(x
k ) and compute an approximation d
k , j
2 ℝ
n of the minimal
norm solution of the linear equalities least squares problem
k A I k d À b I k À A I k x
k
À
Á k¼ min!
ð38:15Þ
by performing j ! 1 iterations of the Extended Kaczmarz algorithm from Popa
(1998), with 0 as initial approximation on (14).
We will call MH the Han algorithm with Step 1 replaced by Step 1p. In Carp
et al. (2015) we proved a convergence result similar with Han’s one, for the
sequence (x
k ) k ! 0 generated with algorithm MH.
38.3 The Genetic Algorithm
Genetic Algorithms (GAs) are adaptive heuristic search algorithms, specially
designed to find good solutions to problems that were otherwise computationally
unsolvable. GAs are based on the evolutionary ideas of natural selection, applying
the principle of ‘survival of the fittest’ on a population of potential solutions
encoded as chromosomes, selecting individuals according to their level of fitness,
and mating them together using some recombination operators to produce better
approximations to a solution (see Sivanandam and Deepa 2008).
38.3.1 Encoding and Initialisation
A GA starts by chromosome encoding and initialisation. A chromosome is a
feasible sequence of genes and in our model is encoded using an integer array
having size equal to mn; each element of this array denotes the number of units
transported, y l (see (38.6)). In order to generate feasible chromosomes, the equality
constraints from (38.7) are imposed for each chromosome by applying a procedure
that randomly generates appropriate integers. After encoding the chromosomes, we
set the genetic algorithm parameters (population size, maximum number of generations, crossover and mutation probabilities) and generate the initial population.
38 Genetic Versus Han-Type Algorithms for Maritime Transportation Problems
635