Some quick background: I'm a software engineer and have been a lurker on this site for a few years. Lately I've gotten really interested in AI again. I took one AI class in college, but it was mainly theory. So I've been reading these posts, going to some of your developer diaries, and researching on the web. Anyhow, something popped up at work where I actually may be able to use GAs. I'm on a project(c#) where we are taking Excel tables(blocks) and placing them on PowerPoint slides. I've got a very simple algorithm where it just places the block the user selects after the last block on the slide. The user can move the blocks around and then place more, and my simple algorithm will just find the last block and place the new block after it. What I'd like to do is use a GA to find the first space available where the new block could fit. My only problem is that I mainly know theory and am still new to actually implementing(though I've been playing with NNs a bit). So I thought I'd get some input from you guys. Do you have suggestions? Links, tutorials, code, etc...? I know I'd be able to figure it out if I had more time, but unfortunately this is something that the customer wanted last minute and I don't have a lot of time. Thanks for your help.

This is probably not a job for a genetic algorithm. Why can't you just loop through the already placed blocks, checking if there is space next to them, and choose that space based on whatever criteria you are using? Or what advantage would a genetic algorithm have over just doing a more brute force type search over the open space?

Maybe brute force is better. Like I said, I'm still new to AI, and I thought that it may be a more efficient solution then a lot of switch cases and if/elses.

Depending on how you want to deal with block and slides, you a problem involving elements of a Knapsack Problem, a Postage Stamp and a Bin Packing problem.

Now, the solution will depend on how much effort should be applied to the placement solution and to the development of an implementation.

I would suggest you read up on some literature on the aforementioned problems (there's plenty online) and give some thought to how much effort you want to put into this solution (which would presumably be a function of how much time you have and how important it is to have a 'neat' solution).

Cheers,

Timkin

I'm looking into those problems now, thanks for the research suggestions!

Some of the constraints I have:

Constant slide size
Variable block sizes
Certain blocks can be split to fit

So after quickly looking up those problems, it looks to me like this is most like the bin packing problem. I'll continue looking into it.

I've got my brute force contingency plan worked up, but I have some time to research some other methods.

edit: after looking at the problems again, now I think this is most like the knapsack problem because the knapsack(powerpoint slide) is a fixed size/volume, and the items(blocks) are of variable size.

Quote: Original post by silent1
edit: after looking at the problems again, now I think this is most like the knapsack problem because the knapsack(powerpoint slide) is a fixed size/volume, and the items(blocks) are of variable size.

Hehe... like I said, it has aspects of each. It's bin packing where you want to assign blocks to slides, but its knapsack if you look at the slide level (i.e., which blocks can go in a slide)... and its also postage stamp if you consider the value of a block being proportional to its display quality and want to maximise value while minimising number of blocks (but maximising area used)!

Sounds like a fun problem to tackle if you have the time! ;)

Cheers,

Timkin

I guess you can look at it as a bin packing problem. However, personally, I think the closest problem type would be the facility or equipment placement problem that arises in operation research. Basically, the problem is given a factory of a certain size and objects that require certain amounts of floor space, how do you find a placement of the objects such that space is not wasted and at the same time reduce the distance between interdependent objects. Say machine A's product needs to be fed into machine B, then you wouldn't want them very far apart.

So, that might be something to look into too, since I know that has been solved with GAs.