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.


Back to Griha