Evolution-in-materio: Solving bin packing problems using materials
Maktuba Mohid, Julian Francis Miller, Simon L. Harding, Gunnar Tufte, Odd Rune Lykkebø, Mark Kieran Massey, Michael C. Petty · 2014
Evolution-in-materio (EIM) is a form of intrinsic evolution in which evolutionary algorithms are allowed to manipulate physical variables that are applied to materials. This method aims to configure materials so that they solve computational problems without requiring a detailed understanding of the properties of the materials. The concept gained attention through the work of Adrian Thompson who in 1996 showed that evolution could be used to design circuits in FPGAS that exploited the physical properties of the underlying silicon [21]. In this paper, we show that using a purpose-built hardware platform called Mecobo, we can solve computational problems by evolving voltages, signals and the way they are applied to a microelectrode array with a chamber containing single-walled carbon nanotubes and a polymer. Here we demonstrate for the first time that this methodology can be applied to the well-known computational problem of bin packing. Results on benchmark problems show that the technique can obtain results reasonably close to the known global optima. This suggests that EIM is a promising method for configuring materials to carry out useful computation.