Fitting blocks into an asymmetrical shape (Python, Genetic Algorithm)

Question

Hi I'm trying to fit Lego Blocks into an asymmetrical shape.

The shape looks like this:

I can choose between all Lego blocks (different weights) which are:

• 8x2 (0.35)
• 8x1 (0.29)
• 6x2 (0.28)
• 6x1 (0.25)
• and so on

all the bricks can be align vertically and horicontally

to bring the shape into code I use an Array like:

  0 0 1 1 1 1 1 1 0 0 0 0
  1 1 1 1 1 1 1 1 0 0 0 0
  0 0 0 0 1 1 1 1 0 0 0 0
  0 0 0 0 1 1 1 1 0 0 0 0
  1 1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1 1 1
  0 0 0 0 1 1 1 1 1 1 1 1
  0 0 0 0 1 1 1 1 0 0 0 0

I now need to fit the blocks into this shape with the lowest cost I think about using genetic algorithm for this, but not sure actually how to start

Can anyone help me with this problem ?

Answer 1

For start, you can limit the possible coordinates only to the interior squares by maintaining a precomputed coordinate array and using it as part of DNA. If the interior area is only half of total area, it should have at least 100% more performance.

Then the DNA can be made of the following genes:

• type or index of type of lego
• rotation of lego
• translation of lego --> maps to interior-squares array

then the fitness can be computed by:

• for all legos placed:
• • penalty += a1 * (each square of lego that overlaps with other lego)^2
• • penalty += a2 * (each square of lego that overflows the shape)^2
• • penalty += a3 * (cost of a lego)^2
• finally:
• • fitness = (a4 * the percentage of interior filled) - penalty