This paper presents a virtual reconfigurable architecture (VRA)-based evolvable hardware for automatic synthesis of combinational logic circuits. The VRA processor is implemented on a Xilinx FPGA and works through two-stage evolutions: (1) finding a functional circuit, and (2) minimizing the number of gates used. To optimize the algorithm performance in the evolutionary process, a self-adaptive mutation rate control scheme is introduced. The efficiency of the proposed methodology is tested with the evolution of a 3-bit multiplier. The obtained results demonstrate that our approach improves the evolutionary design of electronic circuits in terms of quality of the evolved circuit as well as the computational effort.