# EvoPathfinding - Stuck in local optimal

I am using a Genetic Algorithm framework to solve a path-finding problem. Specifically, given the following 32x32 maze:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X                      |         X
X                      |         X
X                      |         X
X                      |     G   X
X                      |         X
X                      |         X
X                      |         X
X                      |         X
X                      |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |             |         X
X        |                       X
X        |                       X
X        |                       X
X    S   |                       X
X        |                       X
X        |                       X
X        |                       X
X        |                       X
X        |                       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


I wish to reach point G by starting from point S. The fitness function that I am using here is based on the manhattan distance and for every individual, it goes as follows:

• if the individual crashes on a wall ('|') or an outer bound ('X') his fitness is 0
• if the individual final coordinates match point G his fitness is 100
• in any other case his fitness is 100 - manhattan_distance_from(G)

The problem is, that the evolution process is halted after a maximum number of steady-state generations i.e., the fitness of the generated individuals is saturated and cannot improve further.

The best final solutions that are refined via the evolution process are like the one below:

### Best Solution

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X                      |         X
X                      |         X
X                      |         X
X                      |    G    X
X    ******************|         X
X    *                 |         X
X    *                 |         X
X    *                 |         X
X    *                 |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |             |         X
X    *   |                       X
X    *   |                       X
X    *   |                       X
X    S   |                       X
X        |                       X
X        |                       X
X        |                       X
X        |                       X
X        |                       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


This is to be expected though from the standpoint of my fitness function. Because in order to overcome the wall, the algorithm has to generate and maintain individuals by worsening their fitness values since the path has to go down and so the fitness value must get worse.

While I have tried to increase the impact of the mutation operators in order to generate and maintain diverse populations in my generations I did not manage to overcome the problem of this local optimal and so I am thinking of ways to improve my fitness function.

Are there any suggestions?

Consider the final point of the agent (if it crashes into a wall or outer bound, this the point where it crashed). Then use (100 - manhattan_distance_from(G)) * penalty as the fitness function, where penalty is 1.1 if it crashed into a wall or outer bound, and penalty is 1 if it didn't crash.
• Aha, so you suggest not being that strict if there is a collision? But in that case, if the individual/agent crosses the wall for example, starting from S his first move is (L,9) he is not only crashing on the wall, but also getting outside of the search space. So in that case, shouldn't he be zeroed? Unless if I did not understand correctly your suggestion. Aug 26, 2022 at 15:56