Need help solving a problem with Genetic Algorithm

Question

I have this program that simulate a soccer penalty kick between 2 teams.

-The goal is 24 x 8 with coordinate (0,0) at the bottom left corner.

-Each team has 5 kickers and 1 goalkeeper (for convenience, I'll call the 2 team Team A and Team B)

-Team A - there are 5 strategies for the kickers (one for each), and there are 5 strategies for the goalkeeper (because he need a strategy for each kicker on team B)

-Team B - there are 5 strategies for the kickers (one for each), and there are 5 strategies for the goalkeeper (because he need a strategies for each kicker in team A)

• Strategy for the kicker is the coordinate (x,y) and power value. The coordinate is the location of the kick and the power is how strong the kick is. ( I will explain more on the Power attribute later). For example each kicker input strategy would be like this: (1,2) 100 or (24,7) 25

• Strategy for the goalkeeper is a coordinate and a +Width and +Height values. The goalkeeper coverage region is a rectangle whose bottom left corner is the (x,y) position and the top right corner is (x+width, y+height). For example, (3,4) 5 5 His bottom left coor is at (3,4) and (3+5,4+5) is his top right corner of the rectangle (coverage area).

• MAX RANGE OF COVERAGE AREA IS 25% OF GOAL AREA (the program will check this)

• Power: 0-24; kick will have no error; kick hit goalkeeper coverage area 100% save Power: 24-49 kick will have 10% error (-/+10% wide of coor); 90% save Power: 50-75 kick will have 20% error; 80% save Power: 76-100 kick will have 30% error; 50% save

EXAMPLE INPUT: power must be 0-100, all other values must be positive integer with 0-(2^7-1) TEAM A kicker: (14,3) 25 goalkeeper: (2,3) 4 4 (3,5) 50 goalkeeper: (1,1) 5,5 and so on ...

TEAM B: Kicker: (9,3) 75 goalkeeper: (1,2) 5 5 (3,13) 100 goalkeeper: (2,3) 6 6 (assuming this won't go over 25% of goal area and so on ....

Ok that was the simulator program

Now I need to create a GA that come up with the best team strategy for the simulator.

Let simplify the problem so everyone can conceptionalize it:

Inputs: -population (random creation of n team, for ex. if n=5, 5 random teams are created with each team's attribute include 5 kickers' strats, 5 goalkeeper strats)

Output: -best team strategy (each team will play each other and the best is selected for the next iteration, remember each team has 5 kickers' strats, 5 goalkeeper strats)

So I am looking for 1 solution afterall in a field of n population

My problem is how to start encoding the solutions. Should I encode the solution as team or as player/goalkeeper pair?

for example, encoding it as team: Chromosome:= [player1, player2, player3, player4, player5, goalkeeper1, goalkeeper2, goalkeeper3, goalkeeper4, goalkeeper5]

class Player {
 int
 int
 int
}

class Goalkeeper {
 int
 int
 int
 int
}

Or encoding it as player/goalkeeper pair:

 Chromosome:= [player, goalkeeper] = [x,y,power,x,y,weight,height]

The problem I have with encoding like this is I have to get 5 best player/goalkeeper pair at the end to make up a team.

Another question is binary and value encoding. Lets say I were to go with player/goalkeeper pair, would value encoding like this [x,y,power,x,y,weight,height] = [2,3,100,3,3,4,5] make more sense than binary representation [0010, 0011, 1100100, 0011, 0011, 0100, 0101] = [0010 0011 1100100 0011 0011 0100 0101]. I would figure it's easier to do crossover and mutation represent it as binary, no?

I am just trying to gather ideas so I have somewhere to start.

Thanks in advance

Answer 1

Do I assume correctly that this is for an academic project? In that case I would do both, encoding the whole team in one chromosome and also on a per-player/keeper basis. That way you can examine both approaches and see which one will produce better results. And since the whole-team-encoding will end up in a range of different (winning) players/keepers, you can also compare them with those individuals resulting from the per-player-encoding.

As for the representation of the values, I like to encode them in binary format as you have suggested, since mutation is a bit more straight forward that way. But of course you can also use a random mutation approach if you use real numbers instead of 0 and 1. Again, if this is for an academic project, you can do both approaches and compare them in your analysis.

Hope that helps!

Answer 2

I don't have a full response for you, but it may be something...

I'd say yes to encoding everything as binary. If you don't actually store it as a bit string, you should make sure that it's easy to convert to one. Like you point out, if your data is encoded as bit strings, crossover and mutation are trivial.

As for the structure of your chromosomes, I think you may be headed into hairy territory if you go for player/keeper pairs. Fitness will only make sense if you look at teams as a whole. Even if you find a great pair, you'll have a pretty poor team if all of your players behave alike. Your fitness function needs to account for player dynamics.

Hope that helps...

Answer 3

First of all, what are you looking for? Good strategies for kickers or for keepers?

If for both, this sounds to be an ideal scenario for co-evolution.

Yes to encoding everything as binaries, do not complicate your life if you cannot find a good reason to do so.