17-03-2014, 06:06 PM
Abstract
In this paper we introduce an Efficient Multi-
Objective Evolutionary Algorithm (EMOEA) to design
circuits. The algorithm is based on non-dominated set
for keeping diversity of the population and therefore,
avoids trapping in local optimal. Encoding of the
chromosome is based on J. F. Miller's
implementation[1], but we use efficient methods to
evaluate and evolve circuits for speeding up the
convergence of the algorithm. This algorithm evolves
complex combinational circuits (such as 3-bit
multiplier and 4 bit full adder) without too much long
time evolution (commonly less than 5,000,000).
Keywords
Gartesian Genetic Programming; Combinational logic
Circuit; Multiobjective Evolutionary Algorithm.
1. Introduction
The evolving circuit design is an approach of
automate circuit design. It is proved to provide more
optimized and various designs of circuit than human
designs. This process doesn’t rely on the designer's
knowledge and experiences. It can also design circuits
with totally different architectures, which import the
feature of fault tolerance. Evolving circuit design will
contribute to synthesis optimization, fault tolerance,
and adaptive controllers in the near future.
Genetic Algorithm (GA) [2] employs the principle
of Darwinian to solve complicated problems. It has the
ability to solve complicated problem. But for automate
circuit design, while the scale of circuits increase, the
truth table and search space become very large, and it
is hard to evolve a circuit that satisfy every output's
function to the truth table. So GA is not that an
efficient approach for this kind of problem. In this
paper, we treat each output's function as a object, using
MOEA to reserve individuals more satisfies the
function of certain outputs instead of washing out
individuals which less satisfy the whole truth table.
Although GA is used to evolve some simple circuit,
it is proved not fit for larger scale circuit design, for
example, a 3 bit multiplexer. As the inputs and outputs
of a circuit increases, the algorithm becomes very
ineffective, it will be harder and harder to get a perfect
circuit design. In our paper we import some
optimization to the chromosome. First of all, the
fitness of individuals is not simply judged by the
combination of all outputs, but calculated for each
output. The comparison of two individuals is based on
the comparison for each output. Another improvement
is on the mutation operation. In earlier researches,
chromosome of individuals is mutated by a fixed rate,
in spite of which bit is being changed. In this paper,
each mutation of a bit follow a float rate, which
depends on how much contribution the bit do to the
individual. The third one is output bits are no longer
gained by evolving. We use a greed strategy to
calculate them.
In this paper we introduce an Efficient Multi-
Objective Evolutionary Algorithm (EMOEA) to design
circuits. The algorithm is based on non-dominated set
for keeping diversity of the population and therefore,
avoids trapping in local optimal. Encoding of the
chromosome is based on J. F. Miller's
implementation[1], but we use efficient methods to
evaluate and evolve circuits for speeding up the
convergence of the algorithm. This algorithm evolves
complex combinational circuits (such as 3-bit
multiplier and 4 bit full adder) without too much long
time evolution (commonly less than 5,000,000).
Keywords
Gartesian Genetic Programming; Combinational logic
Circuit; Multiobjective Evolutionary Algorithm.
1. Introduction
The evolving circuit design is an approach of
automate circuit design. It is proved to provide more
optimized and various designs of circuit than human
designs. This process doesn’t rely on the designer's
knowledge and experiences. It can also design circuits
with totally different architectures, which import the
feature of fault tolerance. Evolving circuit design will
contribute to synthesis optimization, fault tolerance,
and adaptive controllers in the near future.
Genetic Algorithm (GA) [2] employs the principle
of Darwinian to solve complicated problems. It has the
ability to solve complicated problem. But for automate
circuit design, while the scale of circuits increase, the
truth table and search space become very large, and it
is hard to evolve a circuit that satisfy every output's
function to the truth table. So GA is not that an
efficient approach for this kind of problem. In this
paper, we treat each output's function as a object, using
MOEA to reserve individuals more satisfies the
function of certain outputs instead of washing out
individuals which less satisfy the whole truth table.
Although GA is used to evolve some simple circuit,
it is proved not fit for larger scale circuit design, for
example, a 3 bit multiplexer. As the inputs and outputs
of a circuit increases, the algorithm becomes very
ineffective, it will be harder and harder to get a perfect
circuit design. In our paper we import some
optimization to the chromosome. First of all, the
fitness of individuals is not simply judged by the
combination of all outputs, but calculated for each
output. The comparison of two individuals is based on
the comparison for each output. Another improvement
is on the mutation operation. In earlier researches,
chromosome of individuals is mutated by a fixed rate,
in spite of which bit is being changed. In this paper,
each mutation of a bit follow a float rate, which
depends on how much contribution the bit do to the
individual. The third one is output bits are no longer
gained by evolving. We use a greed strategy to
calculate them.