# Multi-Objective Ship Route Optimisation Using Estimation of Distribution Algorithm
## 2 Related Research
### Estimation of Distribution Algorithms  
Estimation of distribution algorithms (EDAs) are a specific branch of evolutionary algorithms (EAs) characterised by a way of generating new solutions using a probability distribution model [29; 30]. This model is estimated based on the best individuals currently available in the population. The random sampling of offspring individuals ensures population diversity and robustness of the algorithm [30; 31].  
Most of the proposed EDAs generate a set of new solutions using the estimated Gaussian model, and thus they are called Gaussian estimation of distribution algorithms (GEDAs) [30; 32]. Two types of GEDAs can be distinguished based on whether the correlation between variables is taken into account, univariate GEDAs (UGEDAs) and multivariate GEDAs (MGEDAs), which obtain better results for problems with many interacting variables [31; 32; 33].  
However, MGEDAs have problems with premature convergence in the case of multi-modal optimisation problems with many flat and wide basins of attraction due to the rapid reduction in variances [31; 33]. To deal with this problem, many techniques for avoiding premature convergence and improving EDAs efficacy in the case of multi-modal optimisation problems have been proposed. Such techniques include a correlation-triggeredadaptive covariance scaling strategy [34], a standard-deviation ratio indicator [35], a cross-entropy-based adaptive covariance scaling method [36], a multiple submodels maintenance technique [37], a multi-modal estimation of distribution algorithm based on cooperative clustering strategy [38], and a layered learning EDA, which maintains multiple probability distribution models in each generation [30].  
Estimation of distribution algorithms have also been adapted for multi-objective optimisation problems. Multi-objective EDAs (MOEDAs) include, among others, the Multi-Objective Hierarchical Bayesian Optimisation Algorithm [39], Multi-Objective Mixed Bayesian Optimisation Algorithm [40], and Multi-Objective Extended Compact Genetic Algorithm [41]. Many-objective optimisation problems have been addressed by the Multi-Dimensional Bayesian Network Estimation of Distribution Algorithm [42]. EDA based on domain adaptation and non-parametric estimation for solving dynamic multi-objective optimisation problems was proposed in [43]. The Directed Multi-Objective Estimation of Distribution Algorithm proposed in [44] addressed the problem of premature stagnation of MOEDAs on local Pareto fronts. The proposed algorithm avoided stagnation by reorienting the covariance matrix of a multivariate Gaussian distribution.  
Combinatorial optimisation is another area of research in which estimation of distribution algorithms have been used. An EDA-based algorithm for Unmanned Aerial Vehicle (UAV) path planning was proposed in [45]. A method using EDA for trajectory optimisation in low-thrust orbit transfers was introduced in [46].  
Some EDAs for combinatorial optimisation problems were used together with local search algorithms. For example, a hybrid algorithm for the quadratic assignment problem, combining EDA and the 2-opt local search algorithm, was proposed in [47]. The authors of [48] used a hybrid of EDA and variable neighbourhood search (VNS) for minimising the total flowtime in the permutation flowshop scheduling problem. A hybrid of EDA and VNS was also applied to distributed flexible job shop scheduling with the crane transportation problem [49].  
In this paper, an innovative adaptation of the estimation of distribution algorithm (EDA) for multi-objective optimisation of a ship's route in a non-stationary environment (tidal waters) is proposed. The proposed method uses the adaptive Markov chain-based path generator and the dynamic programming-based local search algorithm. All these elements distinguish the proposed approach from the EDA algorithms discussed above (see Table 1).