Finding Still Lifes with Memetic/Exact Hybrid Algorithms

Details Finding Still Lifes with Memetic/Exact Hybrid Algorithms Finding Still Lifes with Memetic/Exact Hybrid Algorithms

2008-12-22

arxiv.org/abs/0812.4170v1

Computer Science

Neural and Evolutionary Computing

Scientific paper

The maximum density still life problem (MDSLP) is a hard constraint optimization problem based on Conway's game of life. It is a prime example of weighted constrained optimization problem that has been recently tackled in the constraint-programming community. Bucket elimination (BE) is a complete technique commonly used to solve this kind of constraint satisfaction problem. When the memory required to apply BE is too high, a heuristic method based on it (denominated mini-buckets) can be used to calculate bounds for the optimal solution. Nevertheless, the curse of dimensionality makes these techniques unpractical for large size problems. In response to this situation, we present a memetic algorithm for the MDSLP in which BE is used as a mechanism for recombining solutions, providing the best possible child from the parental set. Subsequently, a multi-level model in which this exact/metaheuristic hybrid is further hybridized with branch-and-bound techniques and mini-buckets is studied. Extensive experimental results analyze the performance of these models and multi-parent recombination. The resulting algorithm consistently finds optimal patterns for up to date solved instances in less time than current approaches. Moreover, it is shown that this proposal provides new best known solutions for very large instances.

Affiliated with

Also associated with

No associations

Rating

Finding Still Lifes with Memetic/Exact Hybrid Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding Still Lifes with Memetic/Exact Hybrid Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding Still Lifes with Memetic/Exact Hybrid Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-538934