Template Design using Extremal Optimization with Multiple Search Operators

Authors

Abstract

The template design problem is a constrained optimization problem originated from the printing industry. It involves printing several variations of a design onto one or more stencil sheets, where the aims are to minimize the number of stencils as well as the overproduction of prints of a particular design. Over the years, exact solution methods have been used to solve the problem. These methods could be useful for small to moderate-sized problem instances. However, when the problem instances are huge, the search space may easily grow too large for the systematic approaches. To date, no meta-heuristic or soft computing techniques have been used for this problem. In this paper, we propose the use of Extremal Optimization (EO) with multiple search operators for solving the template design problem. Different combinations of the search operators are tested via extensive numerical experiments. The results show that EO is indeed a feasible approach for template design optimization. The hybridization of EO with a deterministic local search has proven to be particularly effective.

Keywords

Template Design Problem, TDP, Extremal Optimization, EO, Multi-Objective Optimization, MOOP

BibTeX

@inproceedings{CW2009TDUEOWMSO,
  author                    = {Raymond Chiong and Thomas Weise and Bee Theng Lau},
  title                     = {{Template Design using Extremal Optimization with Multiple Search Operators}},
  booktitle                 = {International Conference on SOft Computing and PAttern Recognition (SoCPaR'09)},
  editor                    = {Nanna Suryana Herman and Siti Mariyam Shamsuddin and Ajith Abraham},
  publisher                 = {{IEEE (Institute of Electrical and Electronics Engineers): {Piscataway, NJ, USA}}},
  pages                     = {202--207},
  year                      = {2009},
  location                  = {{Melaka International Trade Centre (MITC): {Malacca, Malaysia}}},
  url                       = {http://www.it-weise.de/documents/files/CWL2009TDUEOWMSO.pdf},
  doi                       = {10.1109/SoCPaR.2009.49},
  key                       = {CW2009TDUEOWMSO},
},

Links