FITNESS EVALUATION BASED ON LEARNING FOR AUTOMATIC ANALOGUE CIRCUIT
SYNTHESIS USING GENETIC ALGORITHMS
-Varun Aggarwal
Hypothesis Paper, September 2002
GAs are being used for automatic circuit synthesis for quite some time now. In general,
fitness evaluation in these algorithms is carried by taking the inverse of sum of distance
between response of the sample circuit and desired circuit over check points in the
frequency response [1]. This seems to be a suitable scheme and has also shown good
results. But, it is often observed by analog circuit designers, that though many
topologies give very close performance to a desired design, they are actually very
different from the desired topology and in principle the desired/best circuit cannot be
achieved from the given circuit. The existence of such circuits in a population shall
hamper the progress of the algorithm, lower its convergence rate or lead to premature
convergence (due to stagnation).
The argument that the desired topologies may not result from the given topology seems
vague, till we discuss what transformations are being carried out on a given circuit to
facilitate the search for a better circuit. The scheme used earlier [1] is uniform
crossover in a spice-netlist like representation. The way in which this operator
translates into the phenotype (actual topology) is vague. As far as nodes connected to the
input, output and ground are concerned, it seems plausible to understand their exchange
between the circuits undergoing crossover. But the result of exchange of elements
connected to other nodes to the topology of the circuit seems random. However, circuits
synthesized in [1], show that the evolved topology has very few components maximum being
connected to input, output or ground. This explains the genotype-phenotye relation to some
extent.
The aforesaid argument suggests that whether learning shall work with the transformation
used earlier is doubtful and can be ascertained only by experiments. Therefore, a new
crossover operator is prescribed i.e. sorting the netlist by one of the nodes (each
element has two connecting nodes) and then performing two-point crossover. This scheme
shall exchange nearby nodes in the circuits undergoing crossover, maintaining the rest of
the topology more or less same. This operator loosely transforms as exchange of building
blocks between the two phenotypes. Learning with such transformation seems to make sense
theoretically. Another potential crossover operator could be to exchange the elements
connected to the same node between two circuits. The learning scheme shall also work well
with GP based circuit synthesis [2].
The following scheme inspired loosely inspired by Lamarckian Search is thus suggested. A
sample circuit's fitness shouldn't only depend on its comparison with the desired circuit,
but also on its learning capability. An estimate of the learning capacity of a circuit can
be made by simply recording the change in fitness value of the circuit before and after
applying crossovers and mutations (assuming that these operators are bringing about change
in building blocks of the topology). According to this value, a percentage change can be
made in the fitness value of the circuit, increasing it in case fitness increases and
decreasing it in case of stagnant or decreasing fitness value. This way at cost of no
extra fitness value calculations, one can base the fitness partially on the learning
capability of the circuit. While deciding upon the penalty to be imposed on stagnant or
poor learning circuits, care should be taken that highly evolved circuits shall show
lesser improvement, which is amicable and acceptable. Therefore penalty should also depend
on fitness in an inverse fashion.
Another method previously suggested is to accept the offspring to replace the parent only
if the offspring has higher fitness than the parent. A slight and simple modification to
this technique could be to decrease the fitness of the parent by a given percentage if it
is unable to evolve fitter offspring. Also, a record can be kept of the number of times a
circuit has yielded undesired offsprings (n) and at a particular high value of this
number, the circuit can be segregated from the population. At the same time, are should be
taken, that those circuits, which have high fitness and are being segregated should be
recorded, because they might be potential solutions.
This technique will broadly serve 2 purposes.
1. Reduce the fitness value or weed out circuits having high absolute fitness value but
little learning capability.
2. Encourage circuits though having lower absolute fitness value but high learning
capacity.
To make this technique useful, one will have to carefully decide upon parameter values
such as the value of the percentage change according to the change in fitness value of the
offspring from the parent in learning, the value of n for which a circuit is weeded out,
etc. These values can be decided by carrying out experiments. For the same reason, a
variant of this technique was used in the Oscillator
Synthesis Experiment. The technique has shown better results.
Learning techniques may also show merit for synthesis when only a particular circuit (eg.
an exact transfer function) is desired and fitness for other circuits except the
particular circuit is zero. A fitness function based partially on learning and some
approximate absolute fitness calculations may give desired results. Though, it has to be
remembered, that it shall make the algorithm expensive. Further refinement of idea and
experimental work is required in this direction.
The aforesaid learning based fitness function can be used both in intrinsic and extrinsic
hardware evolution.
References
1. J. B. Grimbleby, "Automatic Analogue Circuit Synthesis Using
Genetic Algorithms," IEE Proceedings: Circuits, Devices and Systems (2000) Vol. 147,
No 6, pp 319-323
2. J. R. Koza, F. H Bennett, D. Andre, M. A. Keane and F. Dunlap, “Automated synthesis of analog electrical circuits by means of genetic programming,” in IEEE transactions on Evolutionary Computation, Vol. 1, pp 109-128, July 1997
© Reproduction or usage of this idea should be done after seeking permission of the author.