  We present a novel approach for designing complex approximate arithmetic
circuits that trade correctness for power consumption and play important role
in many energy-aware applications. Our approach integrates in a unique way
formal methods providing formal guarantees on the approximation error into an
evolutionary circuit optimisation algorithm. The key idea is to employ a novel
adaptive search strategy that drives the evolution towards promptly verifiable
approximate circuits. As demonstrated in an extensive experimental evaluation
including several structurally different arithmetic circuits and target
precisions, the search strategy provides superior scalability and versatility
with respect to various approximation scenarios. Our approach significantly
improves capabilities of the existing methods and paves a way towards an
automated design process of provably-correct circuit approximations.
