As far as I understand, the hill climbing algorithm is a local search algorithm that selects any random solution as an initial solution to start the search. Then, should we apply an operation (i.e., mutation) on the selected solution to get a new one or we replace it with the fittest solution among its neighbours?
This is the part of the algorithm where I am confused.
In general, hill climbing algorithms select a random initial solution, then takes the best move available after evaluating all possible operations available. The possible operations are determined by the search operators (which you determine and is dependent on the problem setting). So by your words, you should 'replace it with the fittest solution among its neighbours'.
Mutation can be applied as a search operator, but this varies by degree and context. For example, in structure learning for bayesian networks, a random sequence of search operators are sometimes applied to escape local optima during the search process.
See https://www.cs.helsinki.fi/u/bmmalone/probabilistic-models-spring-2014/StructureLearning.pdf - slide 9 for random restarts
