Genetic Algorithms
I have a problem I want to solve using genetic algorithms and would like some advice. It is kind of hard to explain what I actually want to do, but I have simplified the problem to make it more understandable (the principle is still the same).
Simplified problem:
I have 4 containers of different sizes and shapes, which I balance on a beam that is supported in the middle by a hinge and at each end there is a spring that provides an upward force. Seeing the containers are different sizes their tare weight is also different, so the initial condition of the beam is out of balance.
I want to divide a volume, inputted by the user, over the 4 containers. The user may also chose the target condition: does he want the beam to be perfectly balanced or does he want the beam to be x?out of balance (keep in mind that there are springs supporting the beam so it is possible to find a balance even when the beam isn抰 perfectly horizontal)
When calculating the momentum one has to take account that the containers aren抰 just boxes, but irregular shapes (the position of the center of gravity for a given volume will be calculated using complex formulas). The specific gravity is also inputted by the user so the for a given division of weights (volumes) the program is able to calculate the resulting momentum.
In short the problem is how do I get the program to divide the volumes. I talk about volumes because this is the limiting factor: each container can hold a maximum volume, but in theory an unlimited weight (the container won抰 bend).
My first step was to think about encoding. I think it would be best to use real value encoding. I think the problem with binary encoding is that floating point values are harder to encode. The advantage of using binary encoding is that it makes functions as crossover and mutation easier, but keep in mind that when I have a valid chromosome that is binary encoded it represents an array of volumes. The sum of these volumes is a constant, namely the to be loaded volume. The containers also have a maximum value so if I would randomly crossover and mutate ones and zeros none of the resulting chromosomes would give me a valid solution (chances are very slim anyway).
So I thought about encoding every chromosome as an array of floating points representing the volume of each container. Writing an algorithm to randomly distribute volumes taking into account a max volume isn抰 really difficult. The fitness of each chromosome can easily be evaluated when looking at the momentum created by this specific distribution.
The main problem are the two most important functions when writing genetic algorithms, namely crossover and mutation.
Regarding crossover I had following ideas:
-Calculate the mean value between to chromosomes, this would provide a valid solution, but it is hard to say if this would provide good results.
-Use the following approach:
Take a random number between 0 and the volume to load.
For example if the volume to load is 23 m^4 and you have following chromosomes:
A: 4 , 8 , 9 , 2
B: 13 , 2 , 5 , 3
Random number is for example 13
Start at the beginning of A until you take 13 m^4 from A.
So you take A: 4, 8, 1, x
Then take the rest of the load (10) from B starting at the end.
B: x , 2 , 5, 3
Now add both arrays and see if the result is valid (it could be that a max volume of one of the containers is exceeded). The solution in this case would be:
C: 4 , 10, 6, 3
If the solution wasn抰 valid you could try again with a different random number.
Regarding mutation I had following ideas:
-Values could be swapped:
A: 4 , 8 , 9 , 2
A: 8 , 4 , 9 , 2
It would always check if the max volume of each container always this swap.
-Volumes could be swapped:
Get a random volume, subtract it form one container and add it to another
Somebody might note that this specific problem could be solved using simple maths instead of searching with genetic algorithms and they would be absolutely right. The reason why I want to program this using genetic algorithms is that I want to be able to expand the problem. At a later stage I want to be able to take distribution of stress on the beam into account. The program would have to find an optimization between the two.
I first want to focus on one criteria and it should be possible. A genetic algorithm is used to find the best solution out of all the possible solution and in this case it would be possible to distribute the volume in many different ways. I want to find the distribution which lands me the closest to the wanted state of the beam.
I did my best to explain everything as clear as possible (which wasn抰 easy). If you have any questions just ask.
I do not have much experience with genetic programming so suggestions and comments would be greatly appreciated.
[4993 byte] By [
phalkonea] at [2007-11-26 15:10:29]
# 1
> keep in mind that there are springs supporting the beam so it is
> possible to find a balance even when the beam isn抰 perfectly horizontal
Do the springs have equal k factor? How far along the beam are the
springs located?
> The specific gravity is also inputted by the user so the for a given
> division of weights (volumes) the program is able to calculate the
> resulting momentum.
Momentum? Don't you mean downward force?
So you have 4 containers, are there 2 at each end?
Are the containers located at equal distance from the hinge?
Assume the beam position is > 0 degrees
Then the only way to get closer to 0 degrees is to add volume to the
right side.
Assume the beam position is < 0 degrees
Then the only way to get closer to 0 degrees is to add volumn to the
left side.
That same logic can be applied to whatever target angle is entered.
The point is, why would you add volume to both sides?
With a physics problem like this, it's hard to see why an GA is required.
# 2
>> Do the springs have equal k factor? How far along the beam are the springs located?
The springs indeed have a k factor. When pressed they will result in an upward force which is -kx. Keep in mind that the springs aren't attached to the beam, so they don't pull the beam down (when one end is up). They are used to support.
>> The specific gravity is also inputted by the user so the for a given
>> division of weights (volumes) the program is able to calculate the
>> resulting momentum.
>Momentum? Don't you mean downward force?
The beam is hinged in the middle so there will be a momentum clockwise or counter clockwise. It will be a momentum since a weight that is further from the hinge will have more impact on the balance of the beam. M = w . d . Specific gravity is needed to know the weight of each volume. On one end there will be a downward force on the spring.
>So you have 4 containers, are there 2 at each end?
>Are the containers located at equal distance from the hinge?
2 containers at each end but not at equal distances. Every container is also different. This doesn't really matter. I mainly want to talk about the principle. I have written a program that can do all the calculations when the volumes are distributed manually. Now I want the program to distribute the volumes.
> With a physics problem like this, it's hard to see why a GA is required.
As I explained in the original text a GA is not required when only looking at balance. But I want to jude the volume distribution on more criteria in the future. GA will be required at this time.
Criteria I want to implement:
- Stress distribution: will the beam bend
- Shear forces
- Transversal balance: replacing the hinge with a single point around which the beam has to be balanced
When having 4 criteria it becomes difficult to find an optimum. That's why I want to use GA. I want to FIND a solution to satisfy all criteria as best as possible.
# 3
The first step is to first create the initial population by randomly selecting volumes for each side of the beam.
Choose a random percentage of it to fill each container.
The ranking system is how close the angle is to the target angle.
When you combine 2 possible solutions, you must change 2 of the containers (one at both end).
Suppose your 2 solutions are:
a1, b1 - c1, d1
a2, b2 - c2, d2
The children generated from this would be:
a2, b1 -- c1, d2
a2, b1 -- c2, d1
a1, b2 -- c1, d2
a1, b2 -- c2, d1
Once you've ranked all the children solutions, sort them by rank.
Take the top whatever. Repeat the process.
The code would look like:
int[] container = new int[] { 40, 20, 30, 15 }; // max volumes
int maxPopulationSize = 1000;
int nextGenSize = maxPopulationSize * 4 * 10;
Object[][] soln = new Object[maxPopulationSize][]
Object[][] nextGen = new Object[nextGenSize][];
for (int i = 0; i < soln.length; i++) {
int[] s = new int[container.length];
for (int j = 0; j < s.length; j++) {
soln[j] = container[j] * Math.random();
}
soln[i] = s;
}
// sort the soln array
bestSoln = soln[0];
int numChildren = 0;
while (numChildren < nextGen.length) {
// pick 2 solutions at random
// generate the 4 children and store in the nextGen array
}
// nextGen array is now full, sort it
//-this assumes you have a comparator that can evaluate
// the physics, angle, springs, etc.
// take the top maxPopulationSize and copy into the
// soln array.
// always keep a reference to the best solution
if (nextGen[0] is better than bestSoln)
bestSoln = nextGen[0];
// once you get here, you have completed 1 generation.
// it is up to you how many generations you want to try.
# 4
>When you combine 2 possible solutions, you must change 2 of the containers (one at both end).
>
>Suppose your 2 solutions are:
>
>a1, b1 - c1, d1
>a2, b2 - c2, d2
>
>The children generated from this would be:
>
>a2, b1 -- c1, d2
>a2, b1 -- c2, d1
>a1, b2 -- c1, d2
>a1, b2 -- c2, d1
This is the whole problem. In my original post I talked about encoding and crossover. When you crossover like this, it is not likely that the children are valid solutions. Keep in mind that the user may input both the volume he wants to see distributed and the balance he wants to achieve. So when a users inputs following parameters:
Balance: 0?br>Volume: 50
Initial population creates solutions (this is not the hard part):
10, 15 - 5 , 20
7 , 20 - 13, 10
(total is always 50)
crossover (as you suggested):
7 , 15 5 , 10 (total = 37)
7, 15 13, 20 (total =55)
10, 20 5, 10 (total = 35)
10, 20 13, 20 (total = 63)
None of the children are valid solutions. In my original post I introduced some ideas about crossover and mutation. I would really like to hear some opions on them. Suggestions are offcourse also welcome.
# 5
> When you crossover like this, it is not likely that the children are valid solutions.
I see. Is the volume constraint rigid? If not, then you can build it into the ranking function. Solutions with total volume closer to target volume get ranked better.
I don't think shifting volumes after the cross over is complete will produce very good results. The reason is because shifting volume is analogous to changing the DNA code of the child, in other words, it's more like a mutation. Mutations are in essence random and I think the rule of thumb is to have < 10% mutations, but the solution to shift volumes means the solution will be 100% mutation.
You could always try a few different ways of distributing the volume.
e.g. distribute volume equally
distribute volume so ratios stay the same
distribute volume in some average function (as you suggested)
# 6
>>Momentum? Don't you mean downward force?
> The beam is hinged in the middle so there will be a momentum clockwise or counter clockwise
The word you're looking for is "moment". Momentum is (in classical mechanics, at least) the product of an object's velocity and mass.
# 7
>The word you're looking for is "moment". Momentum is (in classical mechanics, at least) the product of an object's velocity and mass.
This is indeed the word I was looking for. I'm not a native english speaker so accidently used the wrong term.
>I see. Is the volume constraint rigid? If not, then you can build it into the ranking function. Solutions with total volume closer to target volume get ranked better.
The volume is indeed a constraint rigid.
>distribute volume equally
I don't really see how this is a mutation and would lead to the optimal solution.
>distribute volume so ratios stay the same
Can you explain this a little further please
>distribute volume in some average function (as you suggested)
although it was my own suggestion I have given it a great deal of thought and think that this solution isn't usable because this would always even out the distribution; which doesn't necessarily provide the right balance. Extreme values would be event out so a container would probably never hold the maximum.
# 8
> I don't really see how this is a mutation and would lead
> to the optimal solution
Anytime the constituents (members of the initial set) are modified, this is a mutation. I am not sure if this an accurate definition of mutation or not. However, it seems to make sense. Suppose I had a set of blocks and I wanted to know which blocks fit together to produce some optimal whatever. If the final set of blocks I use only contain those blocks that were in my initial set, then there is no mutation.
> Can you explain this a little further please
Ok, let's use the example:
Volume: 50
Initial population creates solutions (this is not the hard part):
10, 15 - 5 , 20
7 , 20 - 13, 10
(total is always 50)
crossover (as you suggested):
Child 1.
7 , 15 5 , 10 (total = 37)
Child 2.
7, 15 13, 20 (total =55)
Child 3.
10, 20 5, 10 (total = 45)
Child 4.
10, 20 13, 20 (total = 63)
Child 1. Need to add a 13 volume units.
The total volume of side one is 22
The total volume of side two is 15
The ratio is 22:15
Thus, 59.5% of 13 volume units will go to side 1
and 40.5% of 13 volume units will go to side 2
One side 1, the ratio is 7:15
So 46.7% of (13 * 0.595) will go to container 1
and 53.3% of (13 * 0.595) will go to container 2
for the other side
33.3% of (13 * 0.405) will go to container 3
66.7% of (13 * 0.405) will go to container 4
the same calculation can be done for the other children.
You will also have to consider what to do if the volume added is
greater than the volume capacity and if the volume taken away would produce a negative volume.
You might even want to take it a step further and use the ratios of the "moment", and not the volume. In essense, because of the volume contraint, we want to match the volume, but produce a solution that also has the same properties as the original child that was generated.
# 9
I think you will find that this is easier to do and easier to understand if you use integers rather than floating point. First of all notice that a single positive int P can be considered to be a fraction between 0 and 1. Just think of the integer as the numerator of an fraction where the denominator is maxint.
Secondly, observe that a single fraction between 0 and 1 will deal with the split between two buckets, and that a sequence of N fractions will uniquely define a distribution between N+1 buckets.
In particular any binary tree of any shape with N+1 leaves will have N internal nodes. If you just assign each of the N fractions to the N internal nodes you get a way of dividing a total quantity among the leaves. Just split the amount that comes into a node between the two children using the fraction that sits at the node.
In your case where you have 4 buckets if you used a balanced tree shape, the first fraction can be the division between the left side and the right side of the lever and the other two fractions can each be the split between the inside and the outside containers on each arm.
Any distribution of positive values in those 3 integers will give you a distribution of fluid among your 4 containers. If you already have a function that tells you the tilt of the system based on floating point values it is an easy matter to decode the 3 ints into the values you will pass into your evaluation function. It is easy to force the numbers to be positive and the only thing that you give up by using ints is dynamic range. Since the dynamic range is about 1 in a billion for 32 bit ints, it seems unlikely that you need anything more than that for any physical system that is made of levers and springs.
Basically you will keep you genome as a simple array of ints, you will do all your crossover and mutation at a bit level and you will decode that array of ints to be anything that is convenient for your problem.
I assume that you know how to do mutations and crossover on a bit level.
Random rnd = new Random();
int[] randomBit = {1,2,4,8,0x10,0x20,0x40,0x80,0x100,....}
//mutation
int randomMutation(){
int result = 0;
while(rnd.nextInt() < mutationRate){result |= randomBit[rnd.nextInt[32]; }
return result
}
//crossover
void breed(int[] newGene, int[] parent1, int[] parent2){
for(int i = 0; i<n; i++){
int mask = rnd.nextInt();
newGene[i] = (parent1[i] & mask) | (parent2[i] & ~mask) ^ randomMutation();
}
}
Clearly if you need anything else in your genome, just jamb in a few more ints and decode it however you like. This is the reason GAs are so hip. Not becasue they are a particularly great search algorithm but because the code is so trivial and so forgiving.
Also, the other word you were looking for was "density" not "specific gravity" unless your lever and springs are all underwater.>
# 10
I have a problem I want to solve using genetic algorithms to find a word. Any ideea?
