Journal of Software Engineering and Applications, 2011, 4, 447-464
doi:10.4236/jsea.2011.48052 Published Online August 2011 (http://www.SciRP.org/journal/jsea)
Copyright © 2011 SciRes. JSEA
447
Synthesis of Time-to-Amplitude Converter by
Mean Coevolution with Adaptive Parameters
Yerbol A. Sapargaliyev, Tatiana G. Kalganova
Brunel University, London, UK.
Email: {yerbol.sapar, tatiana.kalganova}@brunel.ac.uk
Received June 20th, 2011, revised July 17th, 2011, accepted July 26th, 2011.
ABSTRACT
The challenging task to synthesize automatically a time-to-amplitude converter, which unites by its functionality several
digital circuits, has been successfully solved with the help of a novel methodology. The proposed approach is based on
a paradigm according to which the substructures are regarded as additional mutation types and when ranged with
other mutations form a new adaptive individual-level mutation technique. This mutation approach led to the discovery
of an original coevolution strategy that is characterized by very low selection rates. Parallel island-model evolution has
been running in a hybrid competitive-cooperative interaction throughout two incremental stages. The adaptive popula-
tion size is applied for synchronization of the parallel evolutions.
Keywords: Analog Circuit Synthesis, Evolutionary Electronics, Computational Circuits, SPICE
1. Introduction
The analog circuit is much more difficult to design than
the digital one due to the complex and knowledge-inten-
sive nature of the analog electronics. Without an auto-
mated synthesis methodology, analog circuit design has
suffered from long design time, high complexity and cost,
and requires large experience. Therefore, automated syn-
thesis methodologies for analog circuits have received
much attention.
In recent years, evolutionary strategy (ES) has been
found to be one of the most powerful evolutionary algo-
rithms (EA) when applied toward the synthesis of elec-
tronic circuits [1-4]. Despite ES proving itself effective
in solving the scalability problem and reaching great ex-
perimental results, the existing ES-based circuit synthe-
sizers by their technique are far behind the state-of-the-
art EA theoretical developments. Moreover, in the area
of analog circuit synthesis, the number of publications on
ES applications converges are few in comparison with
those of genetic algorithms and genetic programming.
In this paper, the power of ES-based EHW system is
verified by a challenging task to design the time interval
meter circuit (TIMC), which is the core of up-to-date
laser rangefinder. The targeted analog TIMC belongs to a
class of devices that are known as “time to amplitude
converters” (TAC). “TAC generates a rectangular output
pulse whose peak amplitude is linearly proportional to
the time interval between a START and STOP input
pulse pair” [5]. To our knowledge, this is the first attempt
toward automatic synthesis of a TAC circuit.
To solve the problem, a recently developed ES-based
system [1] is upgraded with a combination of the novel
adaptive individual-level differentiated mutation (DM)
and the winner-dominates-winner-cooperates (WDWC)
coevolution strategy formed by means of parallel island-
model evolution.
These two techniques are combined into a “very nar-
row focused search tool” that we name for simplicity as
very narrow focused evolution (VNFE). The literature
review gives on the subject of “optimal selection rate “an
idea that the selection is a mechanism, which increases
the mean fitness of a population while “having the least
deleterious effect” [6] on the genotypes and thus is di-
rectly proportional to the size of a population. In this
work, we use relatively large populations (from 15,000 to
35,000 individuals evolving in parallel), each of which
uses very low selection rates (SR) from 0.2% to 2% and
aggregately the SR of the system reaches 0.048%. Fur-
thermore, the proposed technique theoretically enables
all the parallel evolutions “focus” on a single chromo-
some at one generation, which in our experimental case
can bring up to 0.0006% SR1.
1While during an experiment we have achieved a selection rate equal to
0.048%, theoretically the value 0.0006% is reachable.
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters
448
The idea of VNFE rather comes from experiments
than from theory of EA. In earlier works, we already had
reported about some aspects of DM and adaptation [1,3].
In later works, we found that the system performs better
at SRs 10 times lower than before (from 10% to 1%) [3].
Despite proving our recent technique to be a powerful
tool in comparison with others [7], we have failed with it
when evolving TIMC. Within research in the frame of
this paper, we have applied incremental approach, de-
composing TIMC into two subcircuits. However, the
second stage has failed to converge. Moving to strength-
ening the evolution power by increasing the population
size, we have applied parallel computing, which finally
has brought us to the WDWC strategy. Thus, the reported
methodology is figuratively a “success story” of where
our endeavors in searching for suitable technique have
brought us.
The rest of this paper proceeds as follows. Section 2
provides a background on adaptation, incremental evolu-
tion, and parallel evolution. Section 3 describes the sys-
tem, task description, and experimental setup. Section 4
discusses results of an experiment: the circuit designed
and the behavior of an evolution. Section 5 provides a
comparison of the successful results with the failed ones.
And, finally, in the last section we draw some conclu-
sions.
2. Background
2.1. Adaptation
To get successful results using an EA, one needs good
parameters such as the mutation rate (MR), SR, and the
crossover rate. They predetermine how the EA will solve
the particular task. Often parameters have to be prede-
fined or tuned manually and are only optimal for a spe-
cific problem [5]. To find optimized parameters for a
certain application, researchers generally base their
choices on tuning them by hand, that is, experimenting
with a multitude of values and selecting the one that ex-
hibits the best performance. For instance, different values
of MR are desired at different stages of the evolutionary
process to achieve balance between global and local
searches. Tuning the rates manually is very time con-
suming where the tuned result is only efficient for some
particular instance. The space of operators and parame-
ters is large. Therefore, hand-designed adaptive mecha-
nisms have had relatively less success, and there has
been natural interest in the application of adaptive tech-
niques. The important feature of adaptation is that the
algorithm can be adjusted to the particular task while
solving that task. In general, there are three levels where
the adaptation may take place inside evolution:
Population-level adaptation adjusts control parame-
ters that apply for the entire population. This ap-
proach is most presented in the literature;
Individual-level adaptation is focused on adapting
parameters for every chromosome. For instance, each
chromosome has its own crossover and MR [8]. They
may be varied depending on the convergence state of
the population, the fitness value of the chromosome,
the average fitness value of the population, and
whether the population tends to get stuck at a local
optimum or is scattered in the solution space. This
approach looks most perspective from our point of
view. The convincing example here is the work [9],
where the automatically defined function is an indi-
vidual-level adaptive genetic program where each in-
dividual adapts its definitions for a predetermined set
of subroutines.
Component-level adaptation dynamically alters how
the particular gene of each chromosome will be ma-
nipulated independently from each other [10].
In this paper, we propose a novel and feasible individ-
ual-level adaptive mutation and adaptive population size
schemes for our analog circuit synthesis system and ap-
ply it toward TIMC. The mutation operator has been
suggested to be the most sensitive parameter in the the-
ory of EA [10], as well as in a digital electronic circuit
synthesis domain [4]. In our approach, adaptation is
based on the concept of defining the particular mutation
type for every chromosome using the current and past
features of the chromosome and the population it comes
from. In our method, the parameters that control the MR
of a chromosome are not encoded into their correspond-
ing chromosome as additional genes [8], but are repre-
sented by such chromosome and population characteris-
tics as the chromosome length story, the chromosome
mutation story, and the chromosome and population fit-
ness stories. For example, the mutations that caused the
creation of better chromosomes are used more frequently
in further generations. On the other hand, operators who
produced chromosomes with a lower fitness should be
used more rarely.
There are two general features of the adaptive DM
technique that make it distinctive from others. Firstly, as
each chromosome has its own “personality,” described
by fitness, length, past behavior, etc., it requires a “per-
sonal approach” when choosing and applying a mutation
to it. In an evolutionary analog circuit synthesis, the mu-
tation is not just specified by rate, but could be classified
by types, for example, the mutation of a node connection,
parameter, component name, etc. This approach is more
individual specific and excludes additional randomiza-
tions, which are involved in the “evolution-of-mutation-
rate” approach. Secondly, the novel approach suggests an
economy of computing efforts. Because there is no need
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters449
of additional genes in the chromosome for coding MR,
the shorter chromosome requires less time for evaluation,
operation, memorization, etc.
2.2. Incremental Evolution
The incremental evolution is regarded as one of the main
techniques to tackle the scalability problem. One of the
first attempts to apply it was undertaken in [11] toward
digital circuits. Since then, many approaches have been
developed in the digital domain [2,12,13]. In the analog
area, few works have distinctly utilized these approaches
[14,15]. Furthermore, the targeted circuits were not com-
plex enough to exploit the potential of the technique. The
essence of the incremental evolution lies in “divide and
conquer” method, when the task is decomposed into
subtasks, and then the subtasks are solved step by step. In
the evolutionary electronics, the division can be made
based on parallel or series connection of the subcircuits.
The whole process of multistep evolution can be ar-
ranged in an automatic regime. However, we distinguish
the incremental approach from the “divide and conquer”
in how the subcircuits are united.
In the analog electronics, the subcircuits cannot be
easily connected to get the proper functioning solution.
That is, two perfectly working circuits, when connected
to a common input, are not guaranteed to perform the
same way; more likely each circuit will disturb the func-
tion of its neighbor. This comes from the physical nature
of the electronic components that get influenced from
each other by potentials and currents. This situation dif-
fers from digital circuits, where the Boolean algebra and
the complex task could be decomposed by Shannon’s
expansion theorem or output decomposition [2]. For in-
stance, in [13], the digital circuit with multiple outputs
was broken down into many smaller subcircuits (each
encoded by a single chromosome) with a single output.
Due to the digital nature of the target, the “divide and
conquer” approach enabled the parallel evolution per
each subcircuit. And the final solution was built by sim-
ple joining “bricks into a wall.”
In this context, when we mention incremental evolu-
tion we mean, first of all, not independent evolution of
the targets, but rather the evolution of the current target
together with all targets evolved previously. That is, if
one has the already evolved target, when evolving the
second one the first solution must participate in that evo-
lution, being encoded in the chromosome. This fact de-
creases the benefit of the “divide and conquer” approach
for analog circuit synthesis in comparison to other appli-
cations.
However, despite significant increase of the chromo-
some length with each stage, the need to involve every
gene of the previously evolved solution into every evolu-
tion operation is not necessary. What is obligatory is just
participation in the evaluation process, that is, in getting
the adequate fitness value of the whole chromosome. As
we use ES, where the recombination is not used, the
main evolution operation is a mutation. We regard three
options by degree of involving of genotypes of the pre-
vious solutions into mutation:
1) When the fragments of the chromosome that belong
to previous solutions do not participate in all kinds of
mutation. On one hand, this option keeps the solution
space constrained and saves computing efforts. On the
other hand, removing the opportunity of the previous
solutions to adapt their structures and parameters to a
new more general solution may obstruct finding a current
subcircuit and even leave the process out of any solution.
2) To avoid problems in the first option, the second
option suggests enabling some loci of the previous solu-
tions to participate in evolution along with the rest of the
chromosome. These loci represent the components’
names, nodes, and parameters of the evolved subcircuits
that are located at the junctions between the currently
evolving subcircuit and the previous one(s). These junc-
tions are predefined when one is decomposing the task
into subtasks at the start. One can expand the length of
the chromosome to be participated in mutation by adding
not only the genes coded for components at junctions,
but also by adding genes coded for their neighbors, and
the neighbors of neighbors, etc. (Figure 1).
3) And the third case is when the genotypes of the pre-
viously completed subtasks have the same rights to par-
ticipate in all kinds of evolutionary operations as the
genotypes related to the current subtask. In this case, the
power of “divide and conquer” method drastically falls
down due to extreme expansion of the search space.
Figure 1. Incremental approach: Two subcircuits that are
jointed in a point marked by a red circuit. On the right is a
subcircuit evolved first, on the left is a currently evolving
one. When evolving a subcircuit, there are three degrees of
involving of parts of the previous solution(s) in the current
process: non-involving (marked by dotted square 1), par-
tially where there are components neighboring to a junction
point (square 2) and full, when every component of a pre-
vious subcircuit(s) take(s) a part in the evolution along with
components on the left side of the figure (square 3).
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters
450
However, the positive side of such an approach, when it
is applied to a deliberately easy problem, is an unconven-
tional design and the foreseen component economy of
the solution.
When one is utilizing the extrinsic evolution with the
help of PSPICE, one could utilize the PSPICE built-in
function for subcircuits that are instantiated using letter
“X.” This statement causes the referenced subcircuit to
be inserted into the circuit “using the given nodes to re-
place the argument nodes in the definition” [16]. It allows
a block of circuitry to be defined once and then used in
several places. This build-in PSPICE coding can be
handy when one would like to protect some fraction of a
chromosome as well as to ease up the operations over the
too lengthy chromosomes. We call it X-coding for short.
2.3. Parallel Evolution
EA are inspired by biological evolution, which is a mas-
sively parallel system, where every individual can per-
form independently. Thus, countless numbers of indi-
viduals can be evaluated simultaneously. This feature
becomes increasingly important as grid and cluster com-
puting becomes more powerful. There have essentially
been three approaches to parallel EA: the master-slave
approach, the diffusion approach, and the migration ap-
proach.
The master-slave approach is the simplest form of par-
allel EA. A master node implements all aspects of the EA
itself, other than calculating the fitness; this has the ad-
vantage of introducing no new parameters. This approach
is used when calculating the fitness function that is a
very costly operation compared to ranking and mutation.
The string representation of parameters makes mutation
very simple and can thus be easily run on the master
node. For instance, in [13], they used parallel evolution
to design a multioutput digital circuit. Each slave node
was designing a particular subcircuit with a single output
selecting a particular part or a so-called multichromo-
some. Then, the master node joined the subchromosomes
and made the evaluation of the multichromosome.
The fine-grained approach (also called the diffusion
approach) concentrates on producing a large, interacting
population over a number of nodes, often with one or few
individuals per node.
The migration approach, often called the coarse-grained
approach (or the island-model approach), involves run-
ning a number of largely independent EA, each on a
separate processor, which occasionally exchanges infor-
mation with each other. Whereas the diffusion approach
has much in common with mainland population biology,
this approach is inspired by island population biology,
with populations connected together by migrations. In
[17], the parallel island-model evolution was applied
toward a synthesis of analog circuits, namely, “hierar-
chical fair competition model.” As the purpose of the
work was a comparison of different techniques, the cir-
cuits evolved were not complex enough to probe the
power of the parallel EA.
It has been noticed that ES would be particularly well
suited to the migration approach. Work [18] noted that an
island-ES could solve problems that a standard ES could
not. In [19], there was a parallel ES for use in a protein
structure determination, which behaved mostly like a
master-slave ES, but with coarse-grained elements. Se-
lection was done in parallel, with each slave node evalu-
ating a subset of the population. However, no extensive
study has been done on the implementation and the effi-
ciency of a purely migration-based parallel ES [20].
Another technique called coevolution often accompa-
nies a parallel evolution. The term coevolution is used for
describing two or more independent evolving subsystems
that are running in a parallel way with some kind of in-
terconnection and cooperation [10]. It should be pointed
out that coevolution has been considered as a promising
way for producing an adaptation. There are two classes
of coevolution that are conventionally recognized: coop-
erative and competitive. In brief, the competitive one is
supposed when individuals are rewarded if they defeat
the individuals with which they compete. These interac-
tions can support “arms races” in which the individuals
force each other to become increasingly competent [21].
The instances are the predator-prey kind of relations. In
[22], they performed an analog circuit sizing coevolving
two parallel competing evolutions. After each generation,
they compared the fitness of the fittest chromosomes
from each node and automatically corrected the evolution
parameters.
In the cooperative coevolution, conventionally, a
population represents a part of the potential solution, and
when different populations altogether cooperatively pro-
duce a complete solution to the problem. By partitioning
the problem in this manner, the search space that each
population has to cover would significantly reduce [23].
In [8], two evolutions coevolved in parallel one of which
was an evolution of fuzzy rule bases that produced suit-
able control parameter values for a second allowing the
genetic operator to show an adequate performance.
In the following section, we give details of the meth-
odology we propose, the basics of which is stated previ-
ously in [3].
3. The System Description and Experimental
Setup
3.1. Evolutionary Strategy
We use seven PCs of different power to run seven ESs.
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters451
The populations consist of a different number of chro-
mosomes depending on a power of a particular PC vary-
ing from 15,000 to 35,000 individuals. The following
basic parameters, operators, and features rule the every
evolution.
1) Representation (Coding). The linear (direct) cir-
cuit representation is proposed for use, similar to that one
exploited in [3,24], where each component in a circuit is
coded in a gene. Whether it is a transistor or a resistor or
a capacitor, the component’s features (nodes, parameter,
and name) are coded into four loci. The set of genes
composes a chromosome. A set of chromosomes com-
pose a population. The direct coding simplifies the ter-
minology. We mean, for example, “circuit” when we
mention “chromosome,” we mean “component” when we
mention “gene,” and vice versa. When evolution passes
to a second incremental stage, it applies X-coding of the
best chromosome. As we detailed in the second option of
the section “Incremental Evolution,” some fragments of
the first subcircuit become the ad hoc initial genes for the
next stage solution. For resistors and capacitors, we set
84 and 96 values of E-12 series, i.e., there are 7 and 8
decades correspondent with 12 parameters for each
available evolution.
2) Oscillating length genotype strategy (OLG). The
OLG strategy has been utilized similar to the one de-
scribed in [24] where different genotype varying strate-
gies have been compared. In OLG, the chromosomes are
enabled to increase as well to decrease their lengths.
However, in a long-term perspective, we enable geno-
types permanently to grow up. Due to OLG, during our
experiments, the difference in growth results in a differ-
ence of chromosome lengths that reaches 7 - 8 genes in
one population (Figure 2).
3) Selection rate. The roulette-wheel selection scheme
is used with a selection strength of β = [5]. From each
population, 0.2% - 2.0% of the best individuals are cho-
sen as parents to the next generation. The single best
Figure 2. Distribution of chromosomes after generation
No46 among different lengths in a 25,000-population lo-
cated in the 4-st PC.
chromosome with all its properties always stays as a ref-
erence for individuals of future generations until a new
one appeared with better features. The selection rates
0.2% - 2.0% are set based on previous experience [7] and
initial tests before the experiments.
4) Chromosome replication prevention. During rank-
ing procedure, when comparing two or more chromo-
somes with identical fitness values (with precision until 5
decimal digits) and genotype length, only one goes to a
next generation. This is because we suppose that chro-
mosomes with the exact properties must have identical
genotypes and thus replicate each other.
5) History inheritance. The best 0.2% - 2.0% indi-
viduals are cloned to create a complete population, that is,
every parent does clone from 30 to 700 descendants (for
populations from 15,000 to 35,000). Each descendant
inherits the mutation and fitness story of its ancestors
from previous generations. These stories are helpful at
mutating operation.
6) Adaptive Mutation. Each individual of a new
population yet consisting of clones is mutated according
to an individual adaptive mutation scheme (see next sec-
tion).
7) Fitness function. The fitness function similar to
one that used in [3] is scheduled that is calculated by the
following static fitness function set to a sum over p fit-
ness cases of the absolute weighted deviation between
the target value and the actual output value Voltage
produced by the circuit :
i
ideal
V
i
measured
V
0
p
ii
ideal measured
i
FVV

. (1)
The p equals 11 time points for TIMC. The smaller the
fitness value is, the closer the circuit is to the target. The
fitness penalizes the output Voltage by 10 if it is not
within the specified percentage range of the target Volt-
age value. For TIMC, where the output from the circuit is
supposed to be a constant Voltage, all 11 measured
points are equidistanced within the range from 1ms to
10ms (which is quite a long period of time for ADC to
catch up the signal for further coding).
The fitness threshold is set to 0.3%, that is, the evolu-
tion ranks the fitness of a new chromosome as the best of
current one if the relative fitness difference between the
best previous and pretending chromosome is more than
0.3%. This barrier enables pressure to be applied on dur-
ing ranking that stimulates an application of more radical
mutations (see next chapter). Furthermore, it prevents
appearance of chromosomes with negligible differences
that any simulation software like xSPICE is inherent to
detect.
We meet the problem of generalization during the ex-
periment. The problem of generalization appears when
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters
452
the validity of the circuit functioning is limited only by a
case of source signals used during evolution and is not
extending to arbitrary signals. We suggested seven cases
of coupled signals corresponding to distances 0.4, 2, 10,
30, 45, 65, and 95 km to tackle the problem of generali-
zation. This number means that every chromosome of a
population at each generation is tested seven times for
seven different incoming signals, and the final fitness
value for that particular chromosome is created by a sim-
ple sum of seven normalized fitness values:
7
1
j
j
j
j
F
wF
, where
j
F
is defined by expression (1)
and wj is a weight that normalizes the contribution of the
each case. For the mentioned distances, the weights are:
237.5, 47.5, 9.5, 3.167, 2.11, 1.462, and 1.
1) Ranking. First of all, we should distinguish a chro-
mosome with the best fitness from the best chromosome.
For the first case, an individual attains the best fitness
value according to the fitness function (described earlier).
In the second case, an individual has gone through rank-
ing and been ranked as number one among the popula-
tion. In most of the cases, these two are represented by
the same chromosome, though not always, because the
chromosome length is taken as the second objective dur-
ing ranking. Thus, if one looks at the graph of fitness
function of the best chromosome, it will not be always
slowing down (improving), but there may appear some
ridges.
By ranking, we have got an opportunity to apply the
pressure: along with the functionality of the circuit, we
also prefer shorter chromosomes to longer ones. The
fine-grained open-ended evolution of analog circuits with
dynamic encoding has a side effect when a resulted cir-
cuit integrates in its structure along with functional
components, the ones that had no effect to circuit’s be-
havior [25]. Figure 3 shows a fragment of the experi-
ment where a circuit resulted in 34 components has four
of them (Nos. 14, 15, 25, and 28) with no influence to a
circuit’s functionality. As an experiment displayed, the
hint with pressure at ranking reduces the number of re-
dundant components from about 20% - 40% to 5% -
10%.
It should be mentioned that including the parameter of
a genotype length in the ranking operator represents the
case of multiobjective evolution, where to each objective
corresponds its own weight, what in its turn could be
evolved [26]. However, in our case, we use the second
objective as an ad hoc parameter, whose purpose is to
handle the evolution and chromosome behavior in the
right way. Thus, in the ranking procedure at each sub-
system, we uniformly utilize a simple pressure constant
that behaves adaptively, that is, depending on the progress
Figure 3. The relative fitness sensitivity of every component
in a 34-element circuit. It could be noticed that the earlier
designed components (on the left) are most important for
the circuit functionality than others. There are also 4 com-
ponents (No14, 15, 25, 28) that do not deteriorate the circuit.
Furthermore, the presence of a component No15 in the cir-
cuit structure makes the functioning worse, pruning this
component will lead to a fitness improvement.
of the evolution it varies by maximum 60%.
When comparing two chromosomes, the procedure of
choosing the higher ranked is as follows:
The shorter length at better (smaller) fitness, the
higher is the ranking;
The chromosome’s rank is higher if its fitness is less
at a longer length such that the following inequality is
true:

kk
bestbest best
f
ff ll c
(1)
Here best
f
and best are the fitness and the length of
the best chromosome,
l
k
and are the fitness and
the length of the current one. The is a pressure con-
stant, the meaning of which is a predicted number of
genes (components) in the target; the smaller the number,
the higher the pressure is applied. The adaptive features
are described further.
k
l
c
The same formula (1) is applicable in case the chro-
mosome rank is higher if its fitness is higher (worse) at a
shorter chromosome length.
The advantage of the described ranking scheme is that
it enables the comparison of different length genotypes,
which will be useful also during a migration operation.
2) Pruning. The idea under the pruning procedure is to
prune the components that have no influence to the cir-
cuit’s functionality. As the procedure is time consuming,
it has not been applied toward every chromosome of a
population and even toward the 0.2% - 2.0% of the best
ones (after ranking). In more detail, after evaluation and
ranking, each chromosome gets in the special subsystem,
which tries to eliminate one by one each gene from a
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters453
chromosome. The dangling nodes after elimination are
connected to each other in all possible variations and
each time a new variant of a chromosome is tested. Fi-
nally, the gene is eliminated, and the new chromosome is
adopted if any variant is evaluated with a fitness better
that was initially before the procedure. However, ex-
periments show that applying this procedure at each, one
of two, one of three, and one of four generations toward
the best single as well as toward the 0.2% - 2.0% best
individuals does not guarantee an improvement. After
getting these results, and taking into account the crucial
role that some works [25] provide for the neutral muta-
tion, we decided to apply this procedure only twice to-
ward a final chromosome after each stage.
3) Initial circuit buildup. At the beginning of each
stage, the initial circuit is built up from the embryo cir-
cuit. We start evolution from the first evaluation when an
embryo consists of at least 5 components. The lower
number results in a large amount of identical chromo-
somes in a population.
4) Termination criteria. First of all, we should de-
termine that the whole system terminates only if every
subsystem terminates. We should distinguish the termi-
nation criteria for the first stage and for the second one,
that is, a complete experiment. Two most probable
events may happen that could cause the evolution to be
terminated. The first one is reaching a goal in the form of
exceeding the preset threshold fitness. If this happens
during the initial stage, two main events are automati-
cally triggered: the best chromosome that attained the
threshold is X-coded and all other parallel subsystems are
forced to stop searches and activate a migrant operator,
that is, to receive that individual as a migrant with all its
data, initiate a new population and all other standard
procedures after migration. If the same happens by the
end of the second stage, it means “happy end” for the
whole experiment. For both cases, the threshold is set as
reaching the fitness less than 1.0, which is equivalent to
an average deviation from the ideal reply function per
point 0.031 V for the first subcircuit and 0.044 V for the
whole circuit.
The second reason of the most probable termination is
when a subsystem is not able to update the best chromo-
some for over L consecutive generations. During L gen-
erations, every evolution, in case of its fitness stuck, re-
ceives some number of migrants, and if every migrant is
worse or equal to the subsystem’s best individual (what
means all other subsystems did not improve too), the
experiment stops. However, if some subsystem finds a
better solution, it is able to revive others. In last case, the
subsystems that stopped the search can join the process
under the same conditions, as if they just have activated
the migrant operator.
If the first term terminates all subsystems simultane-
ously, the second one acts independently for per subsys-
tem.
3.2. Adaptation
3.2.1 Differentiated Mutation
Every chromosome at each generation may go through
mutations of different values (except the several initial
generations). The essence of our individual-level adap-
tive mutation approach is based on the following rules.
1) Rate. The different MRs are associated with differ-
ent typ es of mutations. The reference rate of mutation is
set by us to 4%. That means this rate is a minimum level
that could take place in a subsystem.
2) Types and ways of mutations. The available
types of mutation to be applied to chromosomes are in
Table 1.
Combined each other, the mutation types suggest the
variety of mutation ways. In Table 2 there are 5 exam-
ples of chromosomes against the list of different ways of
mutations that may be applied to a corresponding indi-
vidual. For instance, the 100-gene chromosome can be
mutated in 13 different ways, each of which is a combi-
nation of 7 different mutation types. The choice of the
particular way is set as a random procedure, if it is not
specified elsewhere.
Thus, it is suggested to differentiate mutation in analog
circuit evolution not just by rates, but also by types and
ways. In the following are described the aspects of the
Table 1. The types of mutation.
NoMutation Type
1
Node_number_, Parameter_ or Component_name_ mutation
phenotypically means reducing, adding or replacement of only 1
locus. There are no limitations on where to use it. In most of the
cases it is applied in combinations with Compo- nent_mutation
and Substructure_X_mutation.
2
Component_mutation phenotypically means reducing, adding o
r
replacement of a component by another component. It concerns
4 loci at once.
3
Substructure_1_mutation concerns 8 loci. It adds/reduces 2
genes at once to/from a chromosome. These two genes compose
the first substructure.
4
Substructure_2_mutationconcerns 12 loci. It adds/reduces 3
genes at once to/from a chromosome. These three genes com-
pose the second substructure.
5
Substructure_3_mutationconcerns 16 loci. It adds/reduces 4
genes at once to/from a chromosome. These four genes com-
pose the third substructure.
6
Substructure_4_mutationconcerns 20 loci. It adds/reduces 5
genes at once to/from a chromosome. These five genes compose
the fourth substructure.
7*
Substructure_5_mutationconcerns 24 loci. It adds/reduces 6
genes at once to/from a chromosome. These six genes compose
the fifth substructure.
*This type of mutation was not applied in the following experiment. How-
ever, the substructure was stored and prepared to be applied.
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters
454
Table 2. Examples of the ways of mutation for 5 different
chromosomes.
Chromo-s
ome size,
genes
No of loci
mutated
at 4%
The mutation way list applied to different
chromosomes (by combining mutation types
No1-No7)
10 2 1) No1×2;
20 4 1) No1×4; 2) No2;
50 8 1) No1×8; 2) No1×4+No2; 3) No3;
80 13
1) No1×13; 2) No1×9+No2;
3) No1×5+No2×2;
4) No1×5+No3; 5) No1×1+No2×3;
6) No1×1+No2+No3;
100 16
1) No1×16; 2) No1×12+No2;
3) No1×8+No2×2; 4) No1×8+No3;
5) No1×4+No2×3; 6) No1×4+No2+No3;
7) No2×4; 8) No2×2 +No3; 9) No3×2;
10) No1×4+No4; 11) No1×4+No4;
12) No2+No4; 13) No5;
mutation strategy.
3) Substructures’ sources. The best chromosomes of
sizes 5 and 6 genes are stored for use as substructures
and to be applied as mutations of type Nos. 6 and No. 7
correspondingly. The substructures of size 2, 3, and 4
genes are obtained by decomposing the best chromo-
somes of size 5 and 6 genes. They are memorized to be
applied as mutation Nos. 3, 4, and 5 correspondingly.
4) Substructure database. We enable the system to
memorize per one substructure of size 4, 5, and 6 genes
and, per two substructures of size 2 and 3 genes for evo-
lution to have a choice. For each stage, the substructure
database is built independently. The substructures to the
second stage are taken aside from the X-coded part of a
chromosome.
5) Diversification of a mutation history. Each indi-
vidual carries its own history about mutations its ances-
tors had gone through. If the chromosome is ranked in
10% worst of the best 0.2% - 2%, the random choice of
mutation is replaced by the following rule: the most sel-
dom mutation type from the individual’s history should
be applied in the first place at the current generation.
6) Mutation. If the chromosome does not improve its
fitness for the last two generations, the following rule is
activated: the lowest mutation way number temporarily
leaves out the potential mutation way list (Table 2) in-
creasing the probability of the others to be chosen. That
brings more radical changes to a genotype by joining
bigger substructures. The MR is yet staying in the frame
of the initial 4%. The mutation may continue until there
is only one mutation way left. This kind of pressure dis-
appears once a chromosome improved its fitness.
7) Radical mutations. If the chromosome has not im-
proved within the last 4 generations, the next should be
applied is the mutation of an upper type number than it is
allowed within the standard 4% (3rd column of Table 3).
Say, 10-gene chromosome at 4% MR is allowed only a
single No. 1 (Node_number_, Parameter_ or Compo-
nent_name_) mutation type. However, now due to the
fitness stuck, it should go through No. 2 (Compo-
nent_mutation), which is equivalent to a 10% rate muta-
tion. Furthermore, if the chromosome has not improved
within the last 6 generations, the next to be applied is the
mutation of an even higher type number (5th column of
Table 3). The same instantiated 10-gene chromosome
now goes through mutation No. 3 (Substructure_1_mu-
tation), and the rate will be 50%.
The radical MR-2 depends on the length of the chro-
mosome to which it should be applied and may vary
from 80% for a 5-gene individual to lower than 6% for
ones that contain more than 100 genes. The radical mu-
tation is a very important part of VNFE; it provides the
essential modifications to uncommonly homogeneous
individuals peculiar to VNFE, especially during stuck
periods.
3.2.2. Other Adaptive Parameters
Besides the mutation, two more parameters are enabled
for each evolution to adapt. We set different initial popu-
lations and SRs.
The strategy for population size adaptation is to keep
equal times per generation of different populations. If
initially the weaker processors keep pace with others,
later, starting from the average chromosome length of 10
- 15 genes, they need their cycle periods to be reduced.
To enable this synchronization, we set the evolving pe-
riod of the first population (at 1-st PC) as a reference for
others. Thus, during the migrant operator active, each
subsystem, except the 1st one, adjusts its population size
to a new one 1 to keep pace with the population on
the first processor according to the following simple
formula:
P P
Table 3. Examples of radical mutations for 5 different
chromosomes.
Radical
mutation 1
Radical
mutation 2
Chromosome
size, genes
Standard
mutation type
within 4%,,
No(gene size)
Mutation
type,
No(gene size)
% Mutation type,
No(gene size)%
10 1(0) 2(1) 10 3(2) 50
20 2(1) 3(2) 10 4(3) 15
50 3(2) 4(3) 6 5(4) 8
80 4(3) 5(4) 5 6(5) 6.25
100 5(4) 6(5) 5 7(6) 6
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters455
11
PtPt , where 1 and are generation times at
the 1st subsystem and the synchronizing subsystem.
tt
Seven SRs from 0.2% to 2% (Table 4) are enabled to
migrate from a “winner” evolution to a “loser” evolution
along with a “winner’s” genotype and its history. This is
going to enable some statistics to be accumulated at the
end of an experiment on: which SR is become the most
frequent “winner” and finally has dominated others?
3.3. Evolutionary Strategy
3.3.1. Parallel Subsystems
Like in a typical island-model algorithm, we have dif-
ferent populations, each of which acts as an independent
ES, with each one separately initializing, ranking, selec-
tion, cloning, and mutation performing only within popu-
lations. Each population runs on a separate processor;
thus, all these operations can be performed locally,
keeping down communication time. Totally, seven PCs
have been running in parallel connected to a hub.
3.3.2. Migrant Strategy
The populations are connected together by a migration
operation, which is performed by communication be-
tween processors. There is no centralized (“master-slave”
mode) schedule set for communication frequency and
magnitude of migration. On the contrary, each evolution
“decides itself” when to start migration and what it needs
for migration. There is only one condition set when a
communication among the parallel subsystems can take
place. Each evolution is allowed to run without commu-
nication as long as the best chromosome improves (for
the term the “best chromosome improvement,” see
“Ranking” in chapter “Evolutionary Strategy”). As soon
as any population does not improve for at least N genera-
tions, the built-in migration operator activates and makes
Table 4. Initial conditions at 7 parallel PCs.
1 PC description Initial pop. size*,
individ.
Initial selection
rate, %
1 Intel Core2Quad, 2.4 Ghz,
4 GB 35,000 0.2
2 Intel Core2Quad, 2.4 Ghz,
4 GB 35,000 0.5
3 Intel Core2Duo, 2.2 Ghz, 2
GB 25,000 0.8
4 Intel Core2Duo, 2.2 Ghz, 2
GB 25,000 1.1
5 Pentium4, 2.8 Ghz, 2.0 GB 18,000 1.4
6 Pentium4, 2.5 Ghz, 1.0 GB 16,000 1.7
7 Pentium4, 2.8 Ghz, 0.5 GB 15,000 2.0
* The population sizes are chosen in accordance with operational powers of
each PC, so that times to be taken by initial generations are approximately
equal.
the subsystem search for help from other subsystems.
First of all, the stagnated subsystem collects the data files
(Figure 4) from all the parallel nodes, analyzes them,
and decides what the most successful evolution among
all until now is. It applies the ranking rules, including
formulas (1) and (2), to rank out the best chromosome
among the latest of each evolution. So, the subsystem
gets a ranking list consisting of 6 members, a top mem-
ber of which becomes a “winner” chromosome from a
“winner” subsystem. Then, the subsystem gets a clone of
the “winner” with all his history, checks the substructures
(see paragraph below), updates its SR and population
size. It clones a single individual to the total population
and continues with its further isolated evolution proce-
dures. Here, our approach differs from the others. Usu-
ally, the migrant strategy implies the highest-ranking
individual to replace the lowest-ranking individual with-
out dumping out the rest of the genotype material. An
experiment revealed the last approach did not bring the
valuable results at least within the time twice longer than
taken by the proposed technique.
The advanced feature of the migrant strategy described
is an ability of the whole system to adapt the activity of
the migrant operator varying it from 0-power, when no
one subsystem met any problem during evolution, till the
full 7-power regime, when every processor gets a N-
generation stuck period and 7 migrations happened.
In the previous paragraph, we described the general
migrant operation that is liable during all the evolution.
However, there is a migration of the substructures. The
Figure 4. The fragment of a data-file. By columns:
1-“Generation number,” 2- “The best chromosome num-
ber,” 3- “The best chromosome’s fitness value,” 4- “Gene
(component) number,” 5- “The number of cripple chromo-
somes,” 6- “The substructure reuse story,” where the num-
bers are the substructure numbers: “1” is Substruc-
ture_1_mutation, etc.
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters
456
substructures are limited to 6 genes in our approach.
When a stagnated subsystem analyzes the data files (see
paragraph earlier), it makes two independent rankings for
individuals of length 5 and 6 genes. The best are decom-
posed and stored in a substructure database. The subsys-
tems that donate the best chromosomes may differ. The
procedure of substructure checks is performed every time
before the start of a new generation until all the subsys-
tems past the 11-gene (or higher) chromosome in their
data file cause, as the experiment has shown, the oscilla-
tion to never come back from 11 to 6-gene length at this
stage of evolution.
3.3.3. Coevolution
In general, our approach represents a competitive coevo-
lution, where with more time some evolution produces
“winners” as more dominating than others. Notice that
while migrating to a new subsystem the best chromo-
some destroys all the previous genotype material of the
subsystem as unwarranted, enforcing to adopt its own.
Despite different initial conditions set for separate evolu-
tions, due to migration, it may happen that the descen-
dants of one ancestor compete with each other. Further-
more, the approach theoretically enables that all 7 sub-
systems during our experiment (that is totally about
169,000 individuals) evolve the same one chromosome at
the same time. Together with the extremely narrow SR
(0.2% - 2.0%), it seems quite contradictory to a conven-
tional opinion in EA theory hailing the diversity of
genotypes. However, the experiment proved that the
technique is able successfully to solve this problem;
moreover, it appears as the only way to find a solution.
The feature that plays the main role is the DM technique,
where a single individual requires quite numerous clones
to enable the variety of mutation ways to take their
chances.
Thus, the competition aspect consists of a constant
threat of destruction of the whole population when a sys-
tem “defeats.” Even the subsystem that imported in past
the genotypes from a “winner” subsystem is regarded as
a competitor to the “winner,” because due to the radical-
ism of the DM strategy, these two become different
much faster than during a conventional evolution with a
standard MR.
The competition aspect also plays the important role
when the termination criteria appear during the first stage:
the most competitive subsystem at that moment becomes
a “winner” and only “he” who is allowed to save and
transfer its population into the next stage. All others must
obey a migrant operation.
On the other hand, the competitive coevolution we
present has some features of cooperation. The apparent
one is when a “winner” shares the successful SR and
genotypes with a “loser.” A “winner” does not allow a
stagnated subsystem to stop. It shares with last one the
best what it has, in spite of latter, the “loser,” becoming
its competitor. Another aspect that makes all subsystems
cooperative is a substructure database that may consist of
genotypes (totally 7 substructures from two 5- and
6-gene individuals) from different evolutions and is ac-
cessible by everyone. Moreover, all the subsystems focus
in their work toward the same target and have the same
fitness function, which is unconventional for competitive
coevolution. If one could watch the coevolving subsys-
tems at work, it would find in common with rugby game,
where everyone in a team at an attack tries to get the
same target, and if any player has a trouble with going
forward, he passes a ball to one who has the most favor-
able position. In this kind of sense, the ball plays the role
of a migrant operator activated by a “problematic
player.” Further, we call our parallel coevolution ap-
proach as winner-dominates-others-winner-cooperates-
loser or winner- dominates-winn er-coopera tes (WDWC)
strategy.
3.3.4. Incremental Procedure
Upon the end of the first subcircuit, the second one starts
to be evolved. We enable evolution to involve two levels
of components from the junction point (see the second
option in chapter “Incremental Evolution”), which is
totally three components that belong to a first subcircuit
take part in further evolution toward the second one. The
rest of the subchromosome is frozen up with the help of
X-coding.
3.4. The Problem Description: TIMC for the
Laser Rangefinder
A laser rangefinder is a device that uses a laser beam to
determine the distance to an object. The most common
laser rangefinder operates on the time-of-flight principle
by sending a laser pulse in a narrow beam toward the
object and measuring the time taken by the pulse to be
reflected off the target and returned to the sender. The
distance is given by:
2
ct
S, (2)
where c is the speed of light and t is the amount of time
for the round trip between the device and the target. The
typical laser rangefinder has two main parts: optical and
electrical. The optical block sends the laser beam and
receives the reflection, providing the electrical block
with two Voltage pulses, upon which the electrical block
calculates the distance.
As a prototype, we took the artillery quantum range-
finder “DAQ-2” [27] with the following data:
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters457
working at range is 0.2 - 100 km,
measurement accuracy is 6 - 30 m,
the width of both pulses is 50ns; the fall/rise time of
the pulse is up to 5 ns; the first pulse has 9-V ampli-
tude, the reflected one has 6 V.
power supply required is 29 V.
The core part of the electrical block of the device is a
time interval meter sub-block (TIMSB). The working
principle of a conventional TIMSB consists of three
functional stages.
1) At the first stage, two electrical pulses received
from an optical block should be reshaped into the Volt-
age gate pulse, where the first incoming pulse is caused
by the laser beam sent toward a target, and the second
one is caused by the beam reflected off the target. The
gate pulse is a pulse of some constant potential that
should have the same time width as the interval between
two narrow pulses caused by a laser beam.
2) At the second stage, the gate pulse (i.e., the time in-
terval of the gate pulse) is filled up by the clock signals
from crystal oscillator. According to (1), the gate pulse
width varies from about 0.667 μs for the minimum meas-
ured distance (0.1 km) to 0.667 ms for the maximum
measured distance (100 km).
3) And finally, to count the number of pulses con-
tained in the packet. The result of counting in binary
code should be sent to a decoder for further conversion
into a decimal code.
Figure 5 is a general schematic of the TIMSB of the
up-to-date laser rangefinder. Based on a description
available for public, we set as a goal to synthesize the
analog circuit that is able in its functioning to unite
stages 1), 2), and 3) described earlier, and replace 5 digi-
tal units from Figure 5. A new circuit receives two
pulses from an optical block and produces the particular
constant Voltage. The linear correlation between time
gap, and the Voltage produced is set, ranging between
the maximum 5V (against the maximum 100 km) and
5mV (for a distance 0.1 km). The proposed TIMSB
based on an analog circuit is shown in Figure 6(a). The
decomposition method is shown in Figure 6(b), where
we suggest two subcircuits to be evolved during two in-
cremental stages.
4. Experimental Results
4.1. The Circuit
For TIMC, initially we have tried to evolve the whole
circuit at once without exploiting the task decomposition,
but the evolution has failed to converge toward the ac-
ceptable solution. Then, the problem was decomposed
into two subtasks (Figure 6(a)). The initial stage is the
evolution of two-input-one-output gate pulse producing
Gate
pulse
Packet of
pulses
To Decoder
Gate
circuit
Selec-
tor
circuit
Crystal oscillator
Pulse
Coun-
ter
Analog
/digital
con-
verter
From Optical block
Coupled
il
Figure 5. The TIMSB of an up-to-date laser rangefinder
made of digital logic. The shapes of the signals are shown
under each pin. From left to right: there are two pulses
coming in from an optical block, 9 V and of 6 V, separated
by a time taken for the beam to be reflected and returned;
they are converted to a digital form by ADC. Then, they are
transformed to a gate pulse by gate circuit; a selector circuit
fills up the gate with clock pulses generated by a crystal
oscillator; a pulse counter circuit gets the packet of pulses
and counts the clock pulses; a decoder converts that count
to a decimal form.
ADC
Analog
circuit
From Optical block
To Decode
r
Coupled
signals
Gate
pulse Constant
voltage
Sub circuit 1
Sub circuit 2
Gate
pulse
Coupled
signals
To ADC
From O
p
tical block
(a) (b)
Figure 6. (a) The proposed TIMSB with the targeted analog
circuit. The shapes of the signals are shown under each pin.
From left to right: two pulses are converted into constant
voltage; the voltage level is in linear proportion to the time
interval between two pulses; the ADC converts the voltage
into the binary code for further decoding. Due to the reso-
lution of the circuit is preferred to be at least 50 μV (corre-
sponds to 1 meter), that is totally 1e+5 discrete values, the
18-bit ADC with 262,144 quantization levels will meet the
requirement. (b) The proposed decomposition of the tar-
geted analog circuit. The first subcircuit’s task is to form
the gate pulse based on a coupled signal. The aim of the
second is to produce a constant voltage.
subcircuit and the next one is the evolution of an one-
input-one-output subcircuit, which is in series with the
first one.
The experiment has been running nonstop throughout
all stages. To design the whole circuit it took about a
week, where 17% of time was spent for the first subcir-
cuit and the rest 83% for the second one. The first sub-
circuit with 2 inputs and 1output, with a primary task to
provide a gate pulse, consisted of 34 components. Before
the next evolution start, the fitness of the best first sub-
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters
Copyright © 2011 SciRes. JSEA
458
circuit is 0.906. The pruning procedure has eliminated 3
components that have no influence to a circuit’s behavior
(until 31). The second subcircuit, with a task to accept a
gate pulse and produce the required constant Voltage,
consists of 61 elements. Five components are pruned.
The final whole design consists of 95 components before
pruning and 87 components after pruning, among which
are 29 resistors, 26 p-n-p transistors, 17 n-p-n transistors,
and 15 capacitors. The second termination criteria stop
an experiment at the total fitness 1.137 at generation 105.
The resulted device is presented in Figure 7, and its
functionality is shown on six arbitrary instances in Fig-
ure 8(a). To one of the features of the circuit can be
added the lower Voltage supply in comparison with the
“DAQ-2,” 15 V against 29 V.
The PSpice’s performance analysis enables to measure
the generalization ability of the circuit by tracing the de-
pendence of circuit replies on a swept parameter. If we
take as a swept parameter the absolute average deviation
from the ideal circuit response and apply it to a family of
waveforms, we produce a trace that is a function of the
variable that changed within the family. As seen from
Figure 8(b), which represents the absolute average de-
viation along 1000 equidistant circuit replies, the meas-
urement accuracy of TIMC could be approximately split
into three groups: 2.4 meters for distance range 0.1 ÷ 3 m,
16 meters for 3 ÷ 14 km, and 54 meters for 16 ÷ 100 km.
In comparison with conventional digital TIMC, where
the measurement accuracy varies within the range 6÷30m,
it should be mentioned that for shorter distances the ana-
log TIMC does much more accurate measurements, and
in general looks relatively competitive. Furthermore, the
resulting device is able to work out measurements within
distances from 0.1 to 0.2 km, for which the “DAQ-2”
cannot. Moreover, while solving the generalization
problem2, we noticed the tendency during which the ac-
curacy of the measurements directly depends on a num-
ber of input cases during evolution. Thus, it is logical to
conclude that reaching the same accuracy (30 m) for
longer distances and even exceeding it is just a matter of
computing time.
4.2. The Evolution
The general view of the experiment, consisting of seven
evolving subsystems with the details of each migration,
is shown in Figure 9. Totally, 33 times the migrant op-
erator has taken place, where only once it has happened
during the first stage. The first subtask is significantly
easier than the second one: only one subsystem has
turned to a migrant operation while six others have fin-
ished the task on their own. During the second stage, no
one eVolution has come directly to a global solution.
Due to the complexity of the problem, all of them hav
got into the local optimum and have required “assis-
R2 12KC8
3. 3e-7
Qn0
R22
3.3e+6
R13 8.2e+6
Qn3
Qn4
R6
3.3e+4
C9
4.7e-11
Qn6
Qn1
Qp14
Qn15
Qn2 Qn11
15V
Qn14
R17
1.8K
C15
4.7e-8 Qp16
C111.8e-7
R8
2.7e+2
Qp0
Qp10
R7
8.2e+3
Qp1
R0 1.49K
Qp3
C16 3.9e-7
Qp4
Qn12
R24
1e+10
Qp6
Qp24
C13
4.7e-8
C0
1e-6
Qn13
R10
3.9e+6
Qn24
C1
6.8e-6
C5
5.6e-5
Qp19
R18
1.3e+6 Qp25
R11 1.5e+5
Qn7
Qp15
R14 100K
15V
C4
1.2e-5
C3
8.2e-7
R12
8.2e+4
15V
Qp18
C14
1e-7
R1
2.2e+6
Qp22
C6
5.6e-7
Qn8
Qp23
15V
Rs
0.1K
Rl
1K
V_IN_2
Rs1
0.1K
V_IN_1
Qn5
C10
1.8e-10
R15
15
Qp11
Qp8
R3 3.9e+5
R23
4.7e+5
R4 1.5e+4
R5
5.6e+6
Qp26
15V
R5
1.5e+5
Qp13
Qn9
Qn10
Qp17
C12 6.8e-7
R26
5.6
Qp7
R25
1e+10
R19
1e+10
R21
17K
R9
1.8e+5
Qp12
Qp5
C2
3.9e-7
R16 1.2e+6
Qp20
R20
1.5e+5 Qp9
Qp21
SubCircuit 1
SubCircuit 2
Figure 7. The evolved TIMC is consisted of 2 subcircuits: the first subcircuit (dashed) passes the gate pulse to the second one.
2The problem of generalization appears when the validity of the circuit function is limited only to a case of source signals used during evolution and
does not extend to arbitrary signals.
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters459
Figure 8. (a) The voltage replies of the evolved TIMC to six arbitrary incoming signals corresponding to 10, 26, 42, 58, 74 and
90 km. (b) The function of the integrated absolute average deviation from the ideal circuit response along 1000 equidistant
circuit replies.
Figure 9. The migrant schedule. The diagram shows when and how the migrant takes place along a horizontal axis repre-
senting generation numbers. Seven numbered subsystems with initial population size (PS) and SR evolve in parallel from left
to right. The arrow indicates which subsystem is a receiver, from where and at which generation. Totally, 33 migrants are
shown where only one is happened during the first substage. Each migrant is described by the fitness value of the migrant
individual and its length in genes. The table bellow carries additional information on the process of how selection rates mi-
grate along the same axis. The rates just imported are bolded. Since generation 77 the selection rate 0.2 has dominated over
the last fifth evolution.
tance” from others many times (Table 5).
From Table 5 and Figure 9, it can be noticed that the
most influential aspect during the experiment is a sub-
system No1, whose SR (0.2%) has dominated others and
whose genotype have spread to every subsystem. Surely,
it is not the case where we could declare the principal
dominance of lower SRs over the higher ones; more sta-
tistics is needed for that. However, two facts show a
general tendency on SR. First is statistics on how many
times systems with a particular SR become a winner.
Systems with the minimum SR 0.2 have become a win-
ner 7 times, systems with 0.8 3 times and no winners
with any other SR. Second, it takes 77 generations for SR
0.2 to occupy every system.
What is interesting is that during the process each
subsystem, powerful ones as well as weak, has been a
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters
460
Table 5. Initial vs. final parameters and migrant import/
export numbers against the properties of 7 parallel subsys-
tems.
Initial population
size, individ. Initial SR, % Migrants,
No
PC No
Initially Finally Initially Finally ImportExport
1 PC1 35000 35000 0.2 0.2 3 3
2 PC2 35000 36800 0.5 0.2 5 1
3 PC3 25000 19400 0.8 0.2 5 7
4 PC4 25000 19900 1.1 0.2 3 15
5 PC5 18000 11800 1.4 0.2 5 3
6 PC6 16000 6600 1.7 0.2 6 2
7 PC7 15000 7200 2.0 0.2 5 1
“winner” for several times. This fact assures that the
WDWC strategy has uniformly distributed the probabil-
ity of finding successful solutions among all processors.
The case of tough competition is expressed at the mo-
ment in between the stages, when only one chromosome
is enabled to be bred by every subsystem except a “win-
ner.” This extreme migrating act is implemented by us,
instead of release of a system to transfer gradually to the
next stage, due to the proven fact of the superiority of the
first approach over the second.
From generation 91 to 105, the 4th subsystem domi-
nates the rest, spreading out its best genotype to every PC.
But from generation 106 none showed improvement, and
after 15 generations the experiment has stopped.
Figure 10 shows the result of the population size ad-
aptation. It should be noticed from there a tendency ac-
cording to which the difference in computing properties
of the subsystems brings as more diverging population
sizes as longer the average length of the chromosome.
On average, the productivity of PC Nos. 6 and No. 7 has
fallen down more than twice of an initial population size.
The best chromosomes of length 5 and 6 genes from
subsystem Nos. 1 and No. 4 and their fragments were
stored in and used as substructures.
Figure 11 demonstrates seven fitness cases (the fitness
of the best individuals) during the experiment and in be-
tween the stages. The high complexity of the second
subcircuit makes the fitness value to scale for longer than
3 decades. The “waves” of migrations are distinctly visi-
ble when straight vertical lines connect one function with
another.
Another very important notion is about an aggregated
selection rate (ASR), which is a correlation between the
total number of selected individuals of the whole sys-
temat each generation and the current total number of
Figure 10. Adaptation schedule of population size. Seven
curves correspond to seven populations along the horizontal
axis representing the generation number. The curve No1
plays as an etalon for which all others must synchronize
their generation cycles by varying the number of individu-
als during each migrant operation.
individuals inside all populations. It is introduced by us
to differentiate local SRs and the global one of the sys-
tem. At starting conditions when SRs are fixed from
0.2% to 2.0% and the total number of individuals is
169,000, ASR equals to 0.914%. However, during the
experiment, there are two events that lead to change in
ASR:
1) When some subsystem activates a migrant operator.
According to our methodology, only one chromosome is
migrating to the stuck subsystem; in other words, one is
selected, and ASR and SR of the subsystem fall down.
Furthermore, together with an individual, a new SR
comes from a “winner”. Because the subsystem No. 1
has been dominating others, ASR finally has converged
to a rate 0.2. Migrations bring spikes in ASR happening
more frequently and longer to the end of an experiment
(Figure 12) leading ASR to 0.124%.
2) When evolution is incrementing to the next stage.
At this moment, only one chromosome among all popu-
lations (except the “winner” population) is selected to
next generations, and ASR falls down drastically. In
Figure 13, this moment happens at generation 41 where
ASR reaches 0.048%.
Watching the adaptive behavior of ASR is useful be-
cause one can notice the rule according to which the
evolution moves forward: as the harder it is for evolution
to continue as lower the average ASR becomes. Other-
wise, during the successful periods, the system tries to
expand its gene pool, but at “crisis” periods it sharply
reduces a gene pool focusing on breeding the populations
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters
Copyright © 2011 SciRes. JSEA
461
0,00
10,00
20,00
30,00
40,00
50,00
5 152535455565758595105115
Generation, No
Fitness
No1
No2
No3
No4
No5
No6
No7
Figure 11. Seven fitness cases (the fitness of the best individuals) during both incremental substages is in the upper right cor-
ner. It shows how different are they scaled to each other due to unlike levels of complexity. The central picture is focused on a
fragment between the stages. At generation 41 there is a transition to a second substage. The frequent migrating “waives” are
distinctly visible at the end of the second substage (lower right corner).
Figure 13. By dotted lines there are six fitness cases No. 1s -
No. 6s along the generation No correspondent to SR from
0.5% to 5.0% and 7 cases No. 1 – No. 7 of VNFEs with se-
lection rates from 0.2% to 2.0%. All six “conventional”
evolutions have stuck far away from the targeted fitness.
Figure 12. The ASR along the generation number. The ASR
is converging to 0.2 selection-rate initially set at PC No. 1.
The spikes are representing the moments at migrations. The
ASR narrowings are visible where the largest is reaching
0.048% at the first generation of the second substage.
5. Comparison
from fewer individuals. We find this methodology simi-
lar to natural evolution, when such kinds of crisis like
natural disasters, pandemics, and wars force a few sur-
vivals to regenerate the rest of the kind.
The methodology that has been presented so far was dis-
covered after a number of failed attempts to evolve
TIMC by means of standard nonparallel ES-based evolu-
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters
462
tion with more conventional SRs. In this chapter, we
present some of these failed attempts to enable a com-
parison.
When applied toward less complicated circuits [1,3,7],
our previous approach was able to solve successfully all
the tasks set including low-pass filters, computational
circuits, and 4-output Voltage distributor with superior
functional and physical features. If earlier experiments [1]
utilized 10%, the latter ones [3,7] applied 1% - 10% SRs.
In this work, being inspired by previous 1%-rate ap-
proach success, we have tried to run three independent
evolutions with an SR 1%. Then, we have tried to apply
SRs 5.0%, 3%, and 0.5% running another three evolu-
tions. Here, we present six independent nonparallel evo-
lutions with SRs 5%, 3%, 1%, and 0.5% applied toward
TIMC (Table 6). All of them have been applied at the
second incremental stage of the experiment, as the first
one is too easy to play a role of a challenging task. All
the evolutionary parameters and operators have been the
same as described in this paper except SRs and the ab-
sence of communication among subsystems.
We have used the X-coded chromosome from the 1st
stage that differs from that one presented earlier, because
it is obtained during the nonparallel evolution, but due to
ease of the first subtask it is very similar by length 32
against 31 and by a fitness value 0.96 against 0.91.
In Figure 13, there are 6 fitness cases of evolutions
that are superposed with 7 cases of VNFEs. It should be
noticed that there is a very high fitness barrier at about 40
- 43 chromosome length for both evolutions. That repre-
sents the specific feature that is inherent to the function-
ing of TIMC. Once an evolution gets over this barrier,
the fitness improves from about 2200 till 1000. If in co-
evolution case 3 subsystems that stuck at this barrier
continued eVolving after the migrant operation, 3 sub-
systems of the standard evolution left the experiment
Table 6. The population size and initial conditions of the 3
non-parallel PCs.
PC description
Initial
population size,
individ.
SR, % Best fitness
achieved
1s Intel Core2Quad,
2.4 Ghz, 4 GB 35,000 1.0 2410.8
2s Intel Core2Quad,
2.4 Ghz, 4 GB 35,000 1.0 873.4
3s Intel Core2Duo,
2.2 Ghz, 2 GB 25,000 1.0 985.6
4s Intel Core2Quad,
2.4 Ghz, 4 GB 35,000 5.0 2303.5
5s Intel Core2Duo,
2.2 Ghz, 2 GB 25,000 3.0 2389.5
6s Intel Core2Quad,
2.4 Ghz, 4 GB 35,000 0.5 507.4
after 15 futile generations. The second barrier appears at
length 48 - 50 and fitness about 100. However, the con-
ventional evolution has met it much earlier at a fitness
higher than 500. We can suppose that this happens due to
relatively high SRs. That is, as the DM is applied to both
cases, it requires the same large amount of clones per
individual for manifesting itself, what evolutions with
higher SRs provide worse. So, the rest of conventional
evolutions have been stopped in there.
6. Conclusions
In this paper, we have described a novel methodology of
coevolution of parallel island model subsystems with
adaptive parameters. The methodology is named very
narrow focused evolution (VNFE) as it possesses very
small SRs. It has been described why authors are obliged
to apply narrow SRs and have enabled the subsystems to
destroy the genotypes of competitors during the coevol-
ving strategy called winner-dominates-winner-cooper-
ates (WDWC). The novel differentiated mutation (DM)
strategy that we “blame” is built up based on a paradigm
where substructures are regarded as mutation types. To-
gether with such the operating tools as diversification of
mutation history, muta tion, and radical mutation, the
DM strategy represents a quite aggressive operator,
whose stimulating “credo” is increasing an MR each time
a chromosome does not bring an improvement. These
two relatively extreme approaches, DM and WDWC,
work in a balance with each other at “crisis” and
“wealth” periods: whenever the mutation adapts to oper-
ate more aggressively without success, the more actively
WDWC operates bringing the aggregated selection rate
(ASR) to lower values. And vice versa, if evolutions al-
together gradually move forward, both operators let the
system work alone in the frames of standard parameters.
Thus, the proposed system is able to apply two adaptive
regimes, one is a “standard evolution” in the frames of
conventional mutation (4%) and selection (0.2% - 2.0%)
parameters. And another, VNFE, that is triggered when-
ever the first regime meets any problem, and which in-
volves DM (up to 80%) and WDWC (down till 0.124%).
Indeed, this technique has expressed itself in full dur-
ing an experiment. At the first stage, WDWC has brought
little help in solving an initial subtask with only one mi-
gration. That is, it is the “standard evolution” that has
been “running the show” and is able to tackle the prob-
lem by itself. On the contrary, as the generation 53 of the
second stage during the rest 67 generations there are 32
migrations, which means it is VNFE that mostly pulled
the process through.
It is obvious that if we made the migrant operator ac-
tivation term as adaptive to the complexity level of sub-
tasks, the first stage would be involved in the coevolution
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters463
more actively and would converge in much quicker with
a better result, in terms of component economy and func-
tionality. The question that arises here on the effective-
ness of VNFE toward such easy problems is the tradeoff
between “standard evolution” and VNFE, that is, what is
better: 7 independently made solutions to choose among
or only 1 solution made in a team by 7? The last one is
solvable to run tests for both approaches on relatively
easy tasks.
The described approach has some features in common
with Niche GA [28,29]. The similarities are the low se-
lection rates, where a single individual is selected as a
parent for the whole subpopulation and niches that in our
case are represented by subpopulations. However, the
differences that do not enable call the approach as Niche
ES are much more numerous: the niches in our case in-
teract each other via a migrant operator, they are not
synchronized, there are no clearing and sharing proce-
dures, etc.
Though the DM technique has been derived from the
properties that are inherent particularly to analog circuits,
it may be extended to other real-world instances that en-
able to mean under “mutation” term not just the numeri-
cal change of genotype fragments, but first of all, the
change of phenotypical features of the instance.
The initial target of research described in this paper is
the application aspect of how to succeed in evolution of
such the complex tasks as TIMC. The VNFE has come to
us and has been explored as an ad hoc problem. There-
fore, as the research does not pretend to be deep enough
from the EA theory point of view, future work is neces-
sary on accumulating statistics.
REFERENCES
[1] Y. Sapargaliyev and T. Kalganova, “On Comparison of
Constrained and Unconstrained Evolutions in Analogue
Electronics on the Example of LC Low-Pass Filters,”
IEICE Transactions on Electronics, Vol. E89-C, No. 12,
2006, pp. 1920-1927.
[2] T. Kalganova, “Bidirectional Incremental Evolution in
Evolvable Hardware,” Proceedings of 2nd NASA/DoD
Workshop Evolvable Hardware, 13-15 July 2000, pp.
65-74.
[3] Y. Sapargaliyev and T. Kalganova, “Challenging the
Evolutionary Strategy to Synthesis Analogue Computa-
tional Circuits,” Journal of Software Engineering and
Applications, Vol. 3, No. 11, November 2010, pp. 1032-
1039.
[4] E. Stomeo, T. Kalganova and C. Lambert, “Mutation Rate
for Evolvable Hardware,” International Conference on
Computational Intelligence—ICCI 2005, Prague, Czech
Republic, 26-28 August 2005, pp. 117-124.
[5] “Model 2145 Time to Amplitude Converter/Single Chan-
nel Analyzer,” Datasheet, Canberra Industries, Inc.
heep://www.canberra.com/pdf/Products/Model-2145-SS-
0226.pdf
[6] J. Shapiro, A. Prügel-Bennett and M. Rattray, “A Statis-
tical Mechanical Formulation of the Dynamics of Genetic
Algorithms,” Lecture Notes in Computer Science, Vol.
865, 1994, pp. 17-27.
[7] Y. Sapargaliyev and T. Kalganova, “Automated Synthesis
of 8-Output Voltage Distributor using Incremental Evolu-
tion,” Proceedings of 2010 NASA/ESA Conference on
Adaptive Hardware and Systems, IEEE, 15-18 June 2010,
pp. 186-193.
[8] F. Herrera and M. Lozano, “Adaptive Genetic Operators
Based on Coevolution with Fuzzy Behaviors,” IEEE
Transactions on Evolutionary Computation, Vol. 5, No. 2,
2001, pp. 149-165. doi:10.1109/4235.918435
[9] J. R. Koza and D. Andre, “Evolution of Both the Archi-
tecture and the Sequence of Workperforming Steps of a
Computer Program Using Genetic Programming with
Architecture-Altering Operations,” In: P. Angeline and K.
Kinnear, Eds., Advances in Genetic Programming, Vol. 2,
1996.
[10] T. Bäck, “The Interaction of Mutation Rate, Selection,
and Adaptation within Genetic Algorithm,” In: R. Männer
and B. Manderick, Eds., Parallel Problem Solving from
Nature 2, Elsevier, Amsterdam, The Netherlands, 1992,
pp. 85-94.
[11] J. Torresen, “A Divide-and-Conquer Approach to Evolv-
able Hardware,” In: M. Sipper, D. Mange and A.
Pérez-Uribe, Eds., ICES 1998, LNCS, Springer, Heidel-
berg, Vol. 1478, 1998, pp. 57-65.
[12] J. Wang, K. Je, Y. Lee and H. Chong, “Using Recon-
figurable Architecture-Based Intrinsic Incremental Evolu-
tion to Evolve a Character Classification System,” In: Y.
Hao, J. Liu, Y.-P. Wang, Y.-M. Cheung, H. Yin, L. Jiao,
J. Ma and Y.-C. Jiao, Eds., CIS 2005. LNCS (LNAI),
Springer, Heidelberg, Vol. 3801, 2005, pp. 216-223.
[13] J. Walker, K. Völk, S. Smith and J. F. Miller, “Parallel
Evolution Using Multi-Chromosome Cartesian Genetic
Programming,” Genetic Programming and Evolvable
Machines, Vol. 10, No. 4, 2009, pp. 417-445.
doi:10.1007/s10710-009-9093-2
[14] C. Mattiussi and D. Floreano, “Analog Genetic Encoding
for the Evolution of Circuits and Networks, “IEEE Trans.
on Evolutionary Computation, Vol. 11, 2007, pp. 596-607.
doi:10.1109/TEVC.2006.886801
[15] W. Feng, L. Yuanxiang, L. Kangshun and L. Zhiyi, “A
New Circuit Representation Method for Analog Circuit
Design Automation,” IEEE World Congress on Compu-
tational Intelligence, IEEE Press, Hong Kong, 2008.
doi:10.1109/CEC.2008.4631059
[16] PSpice A/D Reference Guide, (includes PSpice A/D,
PSpice A/D Basics, and Pspice. Product Version 15.7),
Cadence, July 2006.
[17] J. Hu, E. D. Goodman, K. Seo and M. Pei, “Adaptive
Hierar-Chical Fair Competition (AHFC) Model for Par-
allel Evolutionary Algorithms,” Proceedings of the Ge-
netic and Evolutionary Computation Conference (GECCO),
Copyright © 2011 SciRes. JSEA
Synthesis of Time-to-Amplitude Converter by Mean Coevolution with Adaptive Parameters
Copyright © 2011 SciRes. JSEA
464
New York, 2002, pp. 772-779.
[18] R. Lohmann, “Application of Evolution Strategy in Par-
allel Populations,” In: H. P. Schwefel and R. Mäanner,
Parallel Problem Solving from Nature—Proceedings of
1st Workshop, (PPSN 1), Vol. 496 of Lecture Notes in
Computer Science, Springer-Verlag, Berlin, 1991, pp.
198-208.
[19] A. Ngom, “Parallel Evolution Strategy on Grids for the
Protein Threading Problem,” Journal of Parallel and Dis-
tributed Computing, Vol. 66, No. 12, 2006, pp.1489-1502.
doi:10.1016/j.jpdc.2006.08.005
[20] L. Jostins, “A Comparison of Parallel Global Optimisa-
tion Algorithms for Reverse Engineering Gene Net-
works,” MPhil Thesis, University of Cambridge, Cam-
bridge, 21 August 2008.
[21] J. Lohn, W. Kraus and G. Haith, “Comparing a Coevolu-
tionary Genetic Algorithm for Multiobjective Optimiza-
tion,” Proceedings of the Evolutionary Computation,
CEC’02. Proceedings of the 2002 Congress, 12-17 May
2002, pp. 1157-1162.
[22] B. Liu, Y. Wang, Z. Yu, L. Liu, M. Li, Z. Wang, J. Lu
and F. Fernandez, “Analog Circuit Optimization System
Based on Hybrid Evolutionary Algorithms,” Integration,
the VLSI Journal, Vol. 42, No. 2, February 2009, pp. 137-
148.
[23] K. Maneeratana, K. Boonlong and N. Chaiyaratana,
“Multi-Objective Optimisation by Co-Operative Co-Evo-
lution,” In: X. Yao, et al., Eds, Parallel Problem Solving
from Nature—PPSN VIII, Lecture Notes in Computer
Science, Vol. 3242, September 2004, Springer-Verlag,
Birmingham, pp. 772-781.
doi:10.1007/978-3-540-30217-9_78
[24] R. Zebulum, M. Vellasco and M. Pacheco, “Variable
Length Representation in Evolutionary Electronics,”
Evolutionary Computation, Vol. 8, No. 1, March 2000, pp.
93-120. doi:10.1162/106365600568112
[25] A. Thompson, “Artificial Evolution in the Physical
World,” In: Gomi, Ed., Evolutionary Robotics, AAI
Books, 1997, pp. 101-125.
[26] I. Guerra-Gomez, E. Tlelo-Cuautle, Luis G. de la Fraga, T.
McConaghy and G. Gielen, “Sizing Mixed-Mode Circuits
by Multi-Objective Evolutionary Algorithms,” Proceed-
ings of IEEE Midwest Symposium on Circuits and Sys-
tems (MWSCAS), Seattle, 2010, pp. 813-817.
[27] Feodosia State Optical Factory, “The Artillery Quantum
Rangefinder (Online),” February 2011.
http://fkoz.feodosia.com.ua/main3.phtml?link=23
[28] J. Hu, E. D. Goodman, K. Seo and M. Pei, “Adaptive
Hierar-Chical Fair Competition (AHFC) Model for Par-
allel Evolutionary Algorithms,” Proceedings of the Ge-
netic and Evolutionary Computation Conference (GECCO),
New York, 2002, pp. 772-779.
[29] A. Petrowski, “A Clearing Procedure as a Niching
Method for Genetic Algorithms,” Proceedings of the
IEEE International Conference on Evolutionary Compu-
tation, 1996, pp. 798-803.