Evolvable hardware is an artificial-evolution based promising path to automated design of circuits and discovery of fancy modules and principles. To improve gate-level evolution of logic circuits in speed and scale for synthetically optimized design results, an adaptive genetic algorithm based approach is presented in this paper. First, it employs an array-model-based encoding scheme that allows flexible changes of comprised logic cells' logic functions and interconnections. Second, it adopts a multi-objective fitness evaluation mechanism with weight-vector adapting and circuit simulation. Third, it features an adaptation strategy that enables crossover probability and mutation probability to vary with the individual diversity and the genetic process. By virtue of these measures, it was validated effective, efficient and innovative by some experiments on arithmetic circuits, in which we obtained functionally correct circuits with novel structures, fewer logic cells and higher operating speed as compared with results of some conventional or evolutionary approaches.