2
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

Another fitness function you could try is the following:

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – ex1led
    Aug 26, 2022 at 15:56
  • $\begingroup$ @ex1led, once the agent crashes into a wall, you should stop it right there - that is its final resting point, and you calculate the distance between its final resting point and G (and multiply by the penalty). $\endgroup$
    – D.W.
    Aug 26, 2022 at 15:58
  • $\begingroup$ Okay, thanks. I will give it a try and update you. $\endgroup$
    – ex1led
    Aug 26, 2022 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.