# Navigation of Autonomous Tug via Evolutionary Algorithms with Radar Plot Fitness Evaluation
## 2 Determining a Local Passage Route Using Evolutionary Algorithms
Mutation occurs with a certain probability, usually at the level of 1-5%, and allows the algorithm to explore new areas of the solution space that could be missed without this operation. After the process of crossing and mutation is completed, the new population of individuals replaces the old one. Then, the whole process of fitness assessment, selection, crossing and mutation is repeated for many iterations (generations), until the algorithm's termination criteria are met, such as reaching a satisfactory solution or reaching a designated number of iterations. Using an evolutionary algorithm to determine a local route for a ship's passage involves determining the starting point, which is usually the position of the ship at the start of the calculations, the destination point, and the static and dynamic navigation constraints existing in a given water body. The initial population of individuals is initiated with randomly determined passage routes, where each is a broken line connecting the starting point of the passage route with the destination point, and each of the route sections has a given speed on this section. The number of individuals, the range of coordinates of the turning points in longitude and latitude, and the range of randomized speeds on each section are the algorithm's control parameters. Algorithm 1 presents the main steps of the evolutionary algorithm determining the passage route of a ship:  
```
BEGIN Load navigational data Initialize random population, encode data on chromosomes | | LOOP Iteration over set number of iterations | | | | | Calculate fitness of every individual | | | | | Select best individuals | | | | | | | | | | | | | | | | | | | Update number of iterations, check if reached maximum | | Return result solution END
```  
**Algorithm 1**Evolutionary Algorithm calculating the ship navigation route  
In order for the genetic algorithm to effectively determine optimal navigation routes, it is necessary to take into account existing navigation constraints already at the stage of generation and evaluation of individual individuals. Generated routes, although initially created randomly, must be subject to thorough verification to ensure that none of the route sections violate applicable navigation rules, such as avoiding obstacles or following fairways. Each individual representing one route must be checked for compliance with these constraints, and verification includes checking for violations of both static and dynamic constraints. A route may be considered incorrect if any of its sections intersects with terrain obstacles, areas excluded from navigation, or passes dangerously close to any of the ships navigating in a given body of water. In such a case, an individual whose route violates these constraints may be rejected or receive a significantly lower value in the fitness assessment. The most important static constraints include terrain obstacles and related shallows; various objects with known positions such as navigation buoys, breakwaters, mooring piles; dangerous objects such as wrecks and boulders on the bottom; navigation zones requiring specific behavior, e.g., areas temporarily or completely excluded from navigation or waterways with a specific direction and/or speed of movement. Dynamic restrictions include moving objects in a given water area, primarily other vessels, but also non-ship objects such as icebergs or lost containers. Due to their invariability over time, static restrictions have a fixed position and dimensions, which can be saved in the form of a digital map and thus used by the algorithm to determine areas that the planned route of passage cannot violate. In order to maintain a certain margin of error in the knowledge of the position of these restrictions, the prohibited area may include the boundaries of known restrictions increased by a certain assumed distance [38].