A voxel-based shape representation when integrated with an evolutionary algorithm offers a number of potential advantages for shape optimization. Topology need not be predefined, geometric constraints are easily imposed and, with adequate resolution, any shape can be approximated to arbitrary accuracy. However, lack of boundary smoothness, length of chromosome, and inclusion of small holes in the final shape have been stated as problems with this representation. This paper describes two experiments performed in an attempt to address some of these problems. First, a design problem with only a small computational cost of evaluating candidate shapes was used as a testbed for designing genetic operators for this shape representation. Second, these operators were refined for a design problem using a more costly finite element evaluation. It was concluded that the voxel representation can, with careful design of genetic operators, be useful in shape optimization.