Information Technology Reference
In-Depth Information
rules or theorems such as the De Morgan's theorems or Karnaugh maps to
design parsimonious solutions; rather, it relies on the same evolutionary prin-
ciples we've been discussing throughout this topic of constantly creating
and experimenting with functional building blocks and, therefore, is imper-
vious to which kinds of gates one chooses to build logical circuits.
On the other hand, logic synthesis problems are special in the sense that
they all can be solved exactly, that is, it is always possible to design a perfect
solution to the problem at hand. So the question is: How to make sure that we
are looking at the most parsimonious solution? And what can be done to find
the elusive parsimonious solution?
Despite giving no certain answers to the first question, gene expression
programming can help us find, if not the most parsimonious, at least one of
the most parsimonious solutions to the problem at hand, no matter what kind
of universal system one chooses to work with. How this is achieved is ex-
plained in the next section.
4.3.1 Fitness Functions with Parsimony Pressure
The question of parsimony is intricately connected with neutrality and we
now know that less compact systems (that is, systems with more room for
the existence of neutral blocks) evolve much more efficiently than more com-
pact ones (see a discussion of The Role of Neutrality in Evolution in chapter
12). This means, obviously, that if we try to optimize a solution not only
based on its efficiency at the task at hand but also on its size, one must be
careful in not hindering evolution completely by applying too high a pres-
sure on parsimony.
But in logic synthesis problems one can have the best of both worlds and
let the system evolve freely at first by using a good, far from compact organi-
zation until a perfect solution is found and only then start selecting solutions
for their size as well. This way, the discovery of perfect solutions is com-
pletely unconstrained and as soon as a perfect solution is found the system
will start applying pressure on the size of the evolving programs and, if there
is a way of representing the perfect solution more compactly, it will most
probably be found, for the system is relentless and will only stop until no
more simplifications can be done.
So, in order to design such a fitness function, one must distinguish raw
fitness from overall fitness (referred just as fitness for simplicity). As a meas-
ure of raw fitness one can use any of the fitness functions described in
