previously Copyright David Dodds 2008

Non-Stationarity and Meta-Objective Function in the Simple Genetic
Algorithm

David Dodds

Abstract - This paper focusses on the fitness function in the simple
genetic algorithm (SGA). Various ways and means are explored whereby
the objective function is made evolvable or at least tunable. The
notion of semantic consonance is discussed where the nature of the
domain wherein the SGA is operating is known to the performance
evaluation. Examples of fixed functions are given and the
meta-objective function is discussed. Means toward non-stationarity in
the function are considered in the final section.

1. INTRODUCTION

The focus of this paper is the fitness function, sometimes also
referred to as the objective function, in the simple genetic algorithm
[1], [2]. Stated briefly, the purpose of the fitness function is to
provide a rank ordering (or figure of merit) for each string produced
as a possible solution. the fitness function is, arguably, the only
component in a genetic algorithm (GA) which has to have any connection
with the semantics of the problem domain.

Assuming that the mapping chosen to associate the problem domain to
string representation in the SGA is reasonably optimal (which we
cannot always know) it is then the duty of the objective function to
find the string with the highest payoff. This string is not
necessarily the "best" one and in most cases this is sufficient for
the problem environment the SGA is in. This is because "best" is a
measure reflecting some specific human notion, which itself may be
imperfectly captured by the objective function used to evaluate the
performance of the system.

II. SGA TOOLS IN THE NON-EXPERT'S COMPUTING ENVIRONMENT

Oftentimes, the GA approach is used to solve a problem because it is
known or stated in the literature that this particular type of problem
yields good solutions from one or another GA approach. It would be
useful to collect these various published solutions / approaches and
codify them, perhaps making them into a "library" or even a "defacto
standard" (to which "proven" successors could be duly added.)

Certainly there are published collections of notable papers in GA. Yet
there is a distinct paucity of directly computer usable objective
functions either in the form of simple, library calls for C/C++ etc.,
let alone the availability of even a rudimentary expert system. These
for PC, MAC, UN*X, which might assist the GA user to select an
objective function based on answers to some simple questions about
such things as the nature of the "classical" search space. Simple old
style (non-learning) expert system technology could be used here to
provide the GA user with a "standardized" fixed objective function
keyed to his immediate problem domain.

None of the companies currently publishing expert systems presently
advertise that amongst the "ready made" knowledge bases they have to
offer is one which asks some questions about the nature of a problem a
user has and recommends / advises on whether or not a "genetic" /
"evolutionary" technology is appropriate to obtaining the solution.
The literature has provided enough material to populate a knowledge
base for this purpose. (For that matter, at least on the PC platform,
no one seems to have a knowledge base for sale which allows a problem
solver to characterize his problem and be advised as to which (or
which technology mix (of neural nets, expert systems, GA, fuzzy,
abductive, etc) to use as a solution provider. I have written a modest
system myself for my own research endeavours.

It is simple enough to collect a small library of standard objective
functions (OF) and provide a simple control mechanism to select one at
any given time. Much GA research appears to be done by people who are
able to write computer code and so they can hand-craft each nuance of
their algorithm and especially finely tune the objective function used
for a given problem. This can only occur because the user has good
semantic knowledge of the domain his GA searches in. In particular, he
is aware of what the most relevant payoff is in the context of his
problem and how to test or evaluate for it in some cases, the best
payoff is not apprehended from the start and some iteration is
involved in locating it.

This can be done because we humans have a wide semantic knowledge
background and an appreciation of relevant test in each. Neophyte
users may not have one or other of these backgrounds. How are they to
perform the same GA searches?

We the user / programmer are responsible for using the best / correct
OF in such a scenario. The best / correct OF is likely based on
either comparing our problem domain type with the published problem
domains and using the OF which the published solution used, or one
goes with one's own experience and / or judgment.

The latter could simply be a guess, inspired or not.

Case based reasoning (CBR, Kolodner et al.) has been used in similar
contexts. The literature on a GA distilled and put into a CBR system
as example cases and any problems that need solving can be
characterized and entered into the CBR system for recommendation of
objective function. CBR might also be used to pursue the expert system
opportunity mentioned above. Again, I have started constructing one.
(I am aware of generic CBR packages being available for the PC. One of
the advantages of doing it personally is that it is possible to
experiment with the utility of using GA technology to help locate the
best means of measuring similarity between various semantic objects, a
critical issue in the functioning of CBR systems.)

III. FIXED FITNESS FUNCTIONS

Hand-crafted GA systems <ital> may </ital> use a simple objective
function, such as f(x) = x^2 (x squared). There are contexts where
that which needs to be optimized can be succinctly characterized in
this fashion. The function, f(x), remains unchanged for the duration
of the search. The fixed function itself may be complex, having many
factors. Perhaps we wish to optimize a function.

y = ( (X1^2) + (X2^2) ) / 2 - cos(20 * PI * X1) cos(20 * PI * X2) +
2 (1)

This function is fixed and to people who are not mathematicians this
function expression would seem complex. GA researchers, as well as
system modellers, would see it as relatively simple, as f(x1, x2), but
non-mathematicians haven't got that insight. This function has 40,000
local minimum points in the region where X1 and X2 are within [-10,
10] [3].

What it means to optimize the former function can be perceived
clearly. For many people, upon inspecting the plot of its graph, the
second function, (1), is not as intuitive in its clear optimization as
the first. It is very "spiky". Is one spike or valley any "better"
than any other? Why? For many people the simple monotonicity of the
first kind of function provides a feeling of clarity if not
"exactitude" in some sense. Function (1) produces a dense, steep
landscape and it is much less intuitive as to where the optimum lies
therein. In this function, as in the real world, there may in fact not
be a single "optimum", there may be many, somewhat equal ones.

Another example of a fixed fitness function might generically look like:

f(x) = a( x^2 ) + b( y^3 ) + c( x * d/2 )
(1.1)

It shows that the objective is x squared, influenced by two, weighted
co-factors, y, and z. These can act as moderators and amplifiers.

The point of interest here is that regardless of the complexity of the
function itself it does not change during the search by the GA. That
is because the objective, such as maximizing profit in a truck packing
scenario, is itself unchanging. This brings us to an important point,
having decided that the objective is unchanging, maximizing profit in
this case, we are at liberty to describe the problem in language
appropriate to business profitability. In such an endeavour there are
business rules which can be stated for achieving that goal and
avoiding its opposite. In these rules are recommended actions and
informational elements that could profitably be monitored to judge
progress.

It is a regular occurrence that the ("genetic") operators need to
operate differently during the end phase of a search than at the
beginning and most hand-crafted ones are written that way. Some aspect
of the measure is moderated however the function remains largely
unchanged in its nature itself.

The activity of packing a truck could be viewed from (a) maximizing
the dollars earned by the packer, or by (b) maximizing the number of
packages in the truck, or by (c) maximizing the value of the capacity
of the truck, etc. It is entirely possible that the maximum dollar
profit is an epiphenomenon of maximizing the dollar value of the
packages of the truck's capacity. What this means is that even though
selecting (c) for the objective function we accomplish (a) as well.
Epiphenomena, or (benign) side-effects occur in any sufficiently
complex dynamical system. It may be the action of a serendipitous
correlated phenomena that one optimizes with the objective function.

Relevancy of items comes to mind here as means to identify that which
might be profitably attended to. Of all the functions that could be
generated to perform the role of objective function how might one best
decide what to measure. This is (what) relevance (is). In order for a
pertinent function to be arrived at, the system must be able to
represent and process relevance. Seemingly no utilization of a problem
domain description language is used by anyone such that identification
of the / a relevant OF can be made / assisted by machine. It may be
that our approach to automating this identification / selection is at
a very early stage and that we must iterate approaches to performing
this activity optimally. Most GA problems are hand-crafted and
hand-tuned. The coder knows or recognizes some of the relevant things,
but only some and never all of them, except for "toy" problems.
Unfortunately, the only place in the whole of the GA concept that
requires knowledge of the problem domain is the OF, and computers are
as of yet blissfully ignorant of the relevant knowledge any human
coder brings to bear on hand-crafting a GA for a problem. This is what
I have referred to as semantic consonance (SC), above. It is harmony,
or parallelism in semantic tokens, or "procedural intention".

IV. META-OBJECTIVE FUNCTION

Relevance is a measure whose magnitude increases as that which is
measured increases the value of a goal by its action. Measuring the
dollar cost of packing a truck is relevant because it allows one to
compare the amount charged to obtain the profit. Measuring the
physical dimensions of the packages may not be the best fitness
measure for a packing scheme. Should there be a working correlation
between the size of packages and their worth, and hence their cost and
their profit, then the system may be able to use size as a fitness
measure as well as direct profit. Another way of seeing this is, if we
allow the system the latitude of truly exploring the problem space it
might, in this case, show us an unseen way of making a profit. This is
a kind of discovery and it has been used in other situations.

The meta-objective function can be likened to a hierarchy or shell. I
shall now present a simple example of one.

continue functioning [top level goal]
maximize dollar profits [penultimate goal]
maximize dollar value of load [tertiary goal]

Continue functioning simply checks for flags in the program which
indicate that no activity is taking place at all, like a becalmed
ship. A program does only what it's programmed to do and if there is
no check for cessation of all activity the program may find a place
and permanently park there. Maximize dollar profits is simply an
example of the penultimate goal of the hierarchy. It is the one which
normally we would concentrate on when hand-crafting a GA, because we
perform the continue functioning check, outside the normal realm of
the GA. The purpose of the meta-objective is to reduce the myopia of
the SGA. When SGAs are hand-crafted for a particular purpose none of
this is required. In the situation where they are placed into a
complex dynamic system to govern themselves the single goal is no
longer adequate. The top-level goal becomes relevant once the
penultimate goal is achieved or activity in the performance of the
penultimate goal threatens to seriously diminish the magnitude of the
top-level goal. If SGAs are ever going to guide autonomous software
agents or real robots they must have a wider scope of attention in
goal attainment than the single goal most are fitted with today.

Perhaps another way of visualizing meta-objectives is:

O[j] = E A[i] W[i] (2)

where O[j] is the j'th meta-objective, A[i] is the i'th action, W[i]
is the i'th weight or contribution of the action. The series j is the
hierarchy of objectives, the meta-objectives, the sequence i is the
order in which sub-goals are executed to achieve a high-level goal.
Sub-goal monitoring vis-a-vis strings with low non-linearity is
explained in [4], and can profitably reduce the time to convergence
without encouraging the onset of premature convergence. Depending on
the degree of string non-linearity, it is practicable to deal with
ordered sub-goal development by employment of Lamarckian evolution
(where information ("knowledge") gained through experience by the
phenotype is passed to the genotype.)

A kind ofcontention could set in between objectives of different
levels, these would be resolved by forcing any lower level
contentious goal seeking behaviour to yield to the requirements of
"satisfying" the maintenance of the objective of a higher level
objective function. In other words, for example, the system would not
perform any profit making actions which would also seriously reduce
the magnitude of the continuity imperative (objective).

Another, more mechanical way of achieving something similar to the
above is to have a simple expert system structure such as:

if system-context is {a} then objective function is {f1}
if system-context is {b} then objective function is {f2}
if system-context is {c} then objective function is {f3}...

where fn measures the results (changes) from action defined by the
strings in the chromosomes, these affecting the system-context. The
system will be able to examine the problem domain automatically and
generate the most relevant measure of the fitness of solutions.

V. NON-STATIONARITY AND THE OBJECTIVE FUNCTION

By non-stationarity I mean that the nature of the problem changes with
time. This is the case with systems in the real world of biology, for
example. Biological systems are complex dynamic systems which operate
in a physical domain governed by certain laws of interaction. Complex
dynamic systems, whether biological or not, interact and the
interaction produces change, often with an increase in the complexity
of the system and in some sense a movement towards a co-adapted state.
There is strong evidence that there exist attractors in the space of
these different levels of dynamic systems. These attractors provide a
tendency toward particular system configurations and interactions. In
biology, they show up as tendencies toward certain functional
morphologies, such as eyes, for example.

In the case of maximizing th profit of a truck packing enterprise the
objective remains constant. In the case of an autonomous software
agent or real robot the changes introduced by interaction with other
agents or other robots requires that the focus of attention be movable
with time. Rarely, however, is it possible to predict the exact nature
of the change such that we could simply program the GA such as, f(x,t)
= factor[i][t] i=1,n; which is to say that the n factors for each
epoch of time t are known in advance and the program simply plugs in
the factors relevant to the time t. Through experience it is possible
for the system to learn that in a given context, which existed at time
t, the factors[i] are such and such according to the regime sought by
the then current objective function. This learning can then be applied
in the future to another time t wherein the context is the same or
sufficently similar. (Similarity in contexts can be managed through
use of fuzzy sets [8],[9],[10],[11].) The Lamarckian operator [4] is
able to provide the genotype (the string) with this knowledge as it is
learned. We see that t, then, initially conceived as a time-date
value, turns out to be the identity of a context, which is time
independent. Non-stationarity can be also handled by gracefully
including a co-search technology like simulated annealing [5],[6]. A
technique called <it> guided evolutionary simulated annealing </it>
(GESA) [3] marries the benefits of annealing directly into the
evolutionary technology.

VI. CONCLUSION

We see that there are circumstances where a fixed objective function
of whatever relative complexity is sufficient for the purposes at
hand. Such a situation might be packing a truck. There are other
situations, such as automomous software agents and robots where the
richness of the interaction of these hosts bearing the SGA with other
agents or robots or the environment generates change of increasing
complexity. This because in these latter systems change is a kind of
accretion in the system's long term behaviour, although the change
itself might be morphological or structural. The SGA may be adapted to
this change via complex interaction by several means:

a) having multiple fixed functions, any one of which is used at a
given time selected randomly or by means of some matching scheme, such
as similarity measures on the semantic descriptors of the problem domain

b) having a function which is parameterized in one sense or another,
where the parameter is adjusted according to the system's perception
of the payoff environment.

This latter approach may be effected by the Lamarckian operator, GESA,
and through the use of meta-objective shells containing knowledge [12]
of the relevancy of each shell layer to the context of a problem. The
Lyapunov exponent might be used to "sniff out" convergence /
divergence in dynamic systems, using GA to explore dynamic systems
space to determine / characterize the attractor landscape. Faced with
a fitness landscape which is densely populated with steep peaks, a
suggestion of a community of systems which have co-adapted with each
other through complex interaction, these means of evaluating the GA's
fitness are a beginning.

[1] J. H. Holland, <it> Adaptation in Natural and Artificial Systems
</it>. Ann Arbor: The University of Michigan Press, 1975.

[2] D. E. Goldberg, <it> Genetic Algorithms in Search, Optimization,
and Machine Learning </it>, Addison-Wesley, Reading MA, 1989.

[3] P. Yip, Y-H Pao, <it> Combinatorial Optimization with Use of
Guided Evolutionary Simulated Annealing </it>, IEEE Transactions on
Neural Networks, Vol 6, No. 2, March 1995.

[4] Y. Davidor, <it> Genetic Algorithms and Robotics </it>, World
Scientific Publishing Co Pte Ltd. 1991.

[5] E. Aarts and J. Korst, <it> Simulated Annealing and Boltzmann
Machine </it>, New York, Wiley, 1989.

[6] S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, <it>
Optimization by simulated annealing </it>, Sci., vol 220, pp.671-680,
May 1983.

[7] Park, D., Kandel, A., Langholz, G., <it> Genetic-Based New Fuzzy
Reasoning Models with Application to Fuzzy Control </it>, IEEE Trans.
on Systems, Man and Cybernetics, Vol. 24, Number 1, January 1994.

[8] Dodds, D. R., <it> Navigation of an Autonomous Mobile Intelligence
Unit in the Unstructured Natural Environment </it>, Second Workshop on
Military Robotic Applications, Royal Military College of Canada and
Defence & Civil Institute of Environmental Medicine, National Defence,
1989.

[9] Dodds, D. R., <it> Fuzziness in Knowledge-Based Robotics Systems
</it>, International Journal of Fuzzy Sets and Systems, Elsevier
Science Publishers B. V. (North Holland), FSS Vol. 26, April 1988.

[10] Dodds, D. R., <it> Common Sense Planning Applied to Grasping and
Manipulating </it>, The International Society for Optical Engineering,
Space Station Automation III, SPIE Vol 851, 1987.

[11] Dodds, D. R., <it> Fuziness in Approximate and Common-Sense
Reasoning in Knowledge-Based Robotics Systems </it>, The International
Society for Optical Engineering, Space Station Automation III, SPIE
Vol 851, 1987.

[12] J. Suzuki, <it> A Markov Chain Analysis on Simple Genetic
Algorithms </it>, IEEE Trans. on SMC Vol 25, No. 4, April 1995,
pp.655-659.

(original date of paper 1995)

the other parts of PART TWO continue in a future posting, including
discussion on
The Touchstone Process of Meaning (TPM)

AND
ontology W3C OWL explaining stuff like:

Thing->yadda->object-oriented-class ::'references'
(rdfs:seeAlso):: CLASS Planet {
NAME name
DATA M, X0, Y0, XP0, YP0, FI
INITIAL
FIR:=FI*PI/180
CFI:=COS(FIR)
SFI:=SIN(FIR)
:
:
}

An ontology [such as NASA JPL 'SWEET', Numerics.owl]
(URL:, http://sweet.jpl.nasa.gov/sweet/numerics.owl) which contains
(A) the ontological information about (what is) 'mathematical
equation' has references to
(B) parts of the OOCSMP-code Class definition such as 'FIR:=FI*PI/180'.

The 'meaning' (by occurrence, by instance, ie by use) is:
" (B) 'FIR:=FI*PI/180' is a (A) 'mathematical equation' ".
ISA

for example, extract from ./numerics.owl
<owl:Class rdf:ID="Function">
231 <rdfs:subClassOf>
232 <owl:Restriction>
233 <owl:onProperty rdf:resource="#hasExpression"/>
234 <owl:allValuesFrom rdf:resource="#ScalarOrVariableOrOperation"/>
235 </owl:Restriction>
236 </rdfs:subClassOf>
237 <rdfs:subClassOf rdf:resource="#Operation"/>
238 </owl:Class>

we can find that (B) FIR:=FI*PI/180 has the property of having an
expression and thus meets the (required) restriction (seen as a
criteria) for being an Operation of (type) Function.

also ./numerics.owl ontology 'has knowledge of' scalar multiplication
and division, and so can individually deal with subcomponents of (B)
which are "*" (multiply) and "/" (division).

the ontological elements (such as rdf:ID="Function") can be associated
with instantiations of them (such as FIR:=FI*PI/180) by means of a
topic-map-graph (such as I describe in my paper "Reflection in
Ontology" (EML2007).