Next Attempt for the design of a FitnessFunction

The class TestResult

Before explaining the new Fitnessfunction I want to introduce the Class TestResult which supplies all necessary data for the calculation of a fitness-value.
The idea of creating TestResult was to provide the results of multiple testbattles in a neutral way. Programs using the test results should be able to decide on their own how to interpret them.
Here the source code:

 case class TestResult (  
   relWinCount: Double, relUndecidedCount: Double, relLossCount: Double,   
   relDurationMeanOnWin: Double, relDurationMeanOnLoss: Double) {  

For details see Design of a Fitnessfunction

The new Fitnessfunction

Here the code for the new Fitnessfunction:

  def fitness(result: TestResult): Double = {  
   // Duration makes only sense if any match was lost or won. Otherwise take fixed value  
   val relDurationMeanOnLoss = if (almostZero(result.relLossCount)) 1.0 else result.relDurationMeanOnLoss  
   val relDurationMeanOnWin = if (almostZero(result.relWinCount)) 1.0 else result.relDurationMeanOnWin  
   // Increasing fitness function  
   val inc = 2.0 + winLossFactor -   
             (result.relLossCount * winLossFactor + (1.0 - relDurationMeanOnLoss)) +   
             (result.relWinCount * winLossFactor + (1.0 - relDurationMeanOnWin))  
   // Invert to get a decreasing fitness  
   (1.0 / inc) * 1000  
  }  

This function also creates (reasonable) results in the case of winning games.
Here are the resuts.

A WinnLossFactor smaller than 5 seems not to make sense because it would probably get stuck in situations where all matches are lost, but the loss of matches is deferred as long as possible.

Problems with winning and loosing games during the same test

The statistics above show only the (simplified) situation that all matches are weather undecided/winning or undecided/loosing. For the case that e.g. most games are lost and some are won, the fitness value is much lower than for 'all matches undecided'. This leads to the problem of getting stuck in 'all matches undecided'
To overcome that situation I am planning to introduce some kind of winFactor that increases the priority of won games to lost games.

Details see future posts

Design of a Fitnessfunction

Good design of a fitnessfunction is essential for the success of a genetic algorithm. In sumosim fitness is evaluated by playing multiple matches against reference robots. The reference robot might be the same for all matches. A match might be won, undecided or lost. Undecided means that no robot won within a certain amount of time. After finishing a number of games the following parameters are collected.

1. relWinCount: Relative number of winning matches. A number between 0 and 1 where 0 means, no matches won and 1 means all matches won.
2. relUndecidedCount: Relative number of undecided games. Also a number between 0 and 1. 0 means no match was undecided and 1 means all matches where undecided.
3. relLossCount: Relative number of lost games. Also a number between 0 and 1 with the same meaning as above.
4. relDurationMeanOnWin: The mean relative duration of winning games. A value between 0 and 1. 0 means that the mean duration of all winning matches was 0 and 1 means that all won games had exactly the maximum allowed time. Generally a low value indicates a better robot than a high value because it could faster defeat the opponent. If no match was won the value is set to 0.
5. relDurationMeanOnLoss: The mean relative duration of lost games. A value between 0 and 1. 0 means all matches where finished immediately and 1 means all matches lasted exactly the maximum allowed time. So a high value indicates a fairly good robot as it did not win but could resist longer than a robot with a low duration value. If no match is lost the value is set to 1.

The sum of relWinCount, relUndecidedCount and relLossCount must (of course) always be 1.
For the GEVA  genetc algorithm a decending fitnessfunction is needed. Meaning that high positive values indicate bad fitness and low values stand for good fittness. 0 would be the best possible fitness value.

Fitnessfunction for lost matches

To keep it simple at first a fitnessfunction for lost matches is designed. In scala it looks like the following. The values for relWinCount and relDurationMeanOnWin are 0 for the following considerations.

Here is the sourcecode in scala.

  def fitness(result: TestResult): Double = {  
   // Duration makes only sense if any match was lost or won. Otherwise take fixed value  
   val relDurationMeanOnLoss = if (almostZero(result.relLossCount)) 1.0 else result.relDurationMeanOnLoss  
   val relDurationMeanOnWin = if (almostZero(result.relWinCount)) 0.0 else result.relDurationMeanOnWin  
   // Increasing fitness function  
   val inc = 1.0 + (1.0 - result.relLossCount) * winLossFactor + relDurationMeanOnLoss +   
             result.relWinCount * winLossFactor + (1.0 - relDurationMeanOnWin)  
   // Invert to get a decreasing fitness  
   1.0 / inc  
  }  

This is actually an increasing fitnessfunction based on the parameters described before. In the last codeline the value is inverted to get a decreasing fitnessfunction.

It was now a challange to find a sensible value for the winLossFactor. Trying it out was my way.
I calculated fitnessvalues for different relLossCount, relDurationMeanOnLoss and winLossFactors.
The following diagrams show the results.

A factor of 20 favors the winning of games where a lower factor as 2 favors quick winning. As both is necessary an intermediate value of 5 will be chosen for the beginning.

First Results in Rule Optimizing

Using the geva library from the natural computing research and application group leads to the first results.

Using geva you must invert the fitness value. Low value means high fitness. A value of 9000 means that the opponent is almost immedately thrown out of the arena. So we can see the breeding was really very successful.
This are the rules that where breeded.

RULEBLOCK GENERATED
 OR : MAX ; 
 ACCU : MAX;
 RULE 1 : IF  opponentDir IS invisible THEN leftVelo IS backward , rightVelo IS forward  ;
END_RULEBLOCK

 
The only generated rule focuses only on the opponent, and means turn around as long as you do not see the opponent. Otherwise use the default behaviour, which is go straight ahead if no rule matches. Very simple but effective.

The opponent was the manually desined fuzzy controlled robot using the following rules.

RULEBLOCK No1
    AND : MIN;
    ACT : MIN;
    ACCU : MAX;

    RULE 1 : IF opponentDir IS invisible
                    AND frontBorderDist IS near
                    AND leftBorderDist IS near
                    AND rightBorderDist IS near 
                THEN
                    rightVelo IS fastBackward,
                    leftVelo IS fastforward;

    RULE 3 : IF opponentDir IS invisible
                    AND (leftBorderDist IS medium OR leftBorderDist IS far)
                    AND rightBorderDist IS near
                THEN
                    leftVelo IS standstill,
                    rightVelo IS forward;

    RULE 2 : IF opponentDir IS invisible
                    AND leftBorderDist IS near
                    AND (rightBorderDist IS medium OR rightBorderDist IS far)
                THEN
                    rightVelo IS standstill,
                    leftVelo IS forward;

    RULE 4 : IF opponentDir IS left
                THEN
                    leftVelo IS fastforward,
                    rightVelo IS forward;

    RULE 5 : IF opponentDir IS right
                THEN
                    leftVelo IS forward,
                    rightVelo IS fastforward;

    RULE 6 : IF opponentDir IS center
                THEN
                    leftVelo IS fastforward,
                    rightVelo IS fastforward;

END_RULEBLOCK


You can see that robot, fighing against a clone of itself using the follwing link: Manual vs Manual

The robot simulation

Another low variance long running session

This will probably be the last parameter optimizing session, as parameter optimizing does not bring the expected results.

The average fitness never exceeds 1000. After 1000 generations there is an improvement in the maximum values, but the no further advancements.
Have a look at the robots after 0, 300, 1000 and 2216 generations.

A long running low variance breeding session

This breeding session generated the absolute maximum average (and max) fitness. Relatively fast it rises to more than 10000 in average. That means that more than half of the individuals of a population could win their matches against the reference robot.
Why could there no further improvement? No idea.
See the robots in action after:
0, 1000, 2000 and 2384 generations

Low variance initial generation

As the performace of the results of parameter optimizing did never get even near the results of the manually designed fuzzy controllers, I tryed to make the inital generation almost equal to the manually choosen parameters (low variance). The GA sould not find a better solutioion somewhere in the waste area of parameters, but find an optimized solution staring at a almost optimal solution.
Here are the results of that.

The fitness rises immediately to a much higher average and maximum than in the sessions with random initial generation (see the results in older posts).
Here are some of the best performers of their generations. The violet sumo is the 'breeded' one.

• 0 generation
• 1 generation
• 100 generations
• 500 generations
• 800 generations