From: "Frank Q" 
To: 
Reply-To: "Frank Q" 


Hi All

For those who may not be familiar with genetic algorithms (GA) etc, I'll
explain how these things work.

The user has to supply (or decide on, or write, or scrounge) the following:

1 - A set of parameters (and their upper & lower bounds) which the GA will vary

2 - A set of requirements or criteria that must be approached, met or satisfied.

3 - An algorithm which takes these parameters as input and produces a
number "NUM"
which represents how closely the parameters produce the required result. Usually
this number is a large positive number for a "bad design" and
close to zero depending
on how well the design meets your criteria. This algorithm is called the
"objective
function", however, it does not need to be a mathematical function in
the "traditional
sense". It can be anything!!

4 - A genetic algorithm. Get one off the WEB and modify to your
application. There's plenty of tutorial material as well.

Now for a practical example: We want to design an achromatic doublet.

This is where the user has to decide on what parameters to optimise. The
parameters available are:

* Radii of curvature of all the elements of the doublet (R1, R2, R3, R4)
* Types of glass that each component is made from
* Separation of the components
* Shape of the surfaces - spherical, paraboloid etc.
* Others that I haven't thought of

Our criteria can be any combination of the following:

* Optimise the colour correction
* Optimise the flatness of the focal plane
* Minimise spherical aberration
* Minimise coma
* Others that I haven't thought of

For this example, I shall decide/set the following:

The lens will be a 4" F/15 made from specific crown and flint glasses.
It will be a cemented doublet so two of the surfaces will mate. I want to
have minimum chromatic aberration at wavelengths of 0.45, 0.5, 0.55, 0.6
microns and I will NOT optimise it for any other aberration.

From this, the parameters are R1, R2(=R3), R4.

The objective function that I will use is the ray-tracing program that I wrote
for this application (oops, I let the cat out of the bag). Program the ray tracer
to compute the extents, (eg standard deviations) E1, E2 ... of the circles of least
confusion at the required coordinates (focal plane) for each of the above
wavelengths. To get our positive number NUM, we can proceed as follows
(there
are probably much better ways):

Find the mean (EM) = (E1 + E2 + ...) / N

Find the sum of the absolute deviation from the mean: ED = abs(E1-EM) +
abs(E2-EM) + .....    [abs(arg) is a maths function that
returns the absolute value of its argument "arg"].

The number that the objective function returns is NUM = EM + ED. Note that
here, both the size of the circles of least confusion AND the difference
between
sizes contribute to NUM - thus NUM gets smaller as the circles AND the differences
between them gets smaller. Note, it will never get to zero, so we're looking for
a minimum value for NUM.

Description of GA operation:

The GA operates as follows:

Step 1 - The GA generates a population of individuals (say 100). Each individual is
described by 3 genes (the three radii of curvature - R1, R2(=R3), R4) and a
"survival coefficient" which is NUM. The lower NUM is, the better
the chance of
survival of this individual in the population. The population is sorted in
ascending order
according to NUM. This results in the fittest individuals being at the
front of the list.

Step 2 - The population breeds. This is where you the programmer can use
your imagination
to invent any bizarre breeding scheme. Here is one scheme: Choose as
parents the 2 fittest
individuals in the population. These produce an offspring who inherits
their genes (R1, R2, R4).
You, the programmer decide from which parent the child inherits each gene.
One method is
as follows: The child has a 33.333% chance of inheriting the R1 gene from
one parent, a 33.333%
chance of inheriting the R1 gene from other parent and a 33.333% chance of
mutating - that
is, R1 gene is randomly generated. This is repeated for each of the three
genes (Radii of curvature).

Step 3 - Calculate how fit the child is. This means calculating the
objective function - so the
raytrace engine is run for lots of rays for the wavelengths stipulated and
a value of NUM is
arrived at. If the gene combination results in a physically impossible
situation eg 2 lens surfaces
intersecting, then set NUM to a very large value (extremely unfit -
probably stillborn)

Step 4 - Insert the child into the population. Remember that the population
is sorted into order
of fitness. Eliminate from the population the least fit individual
(survival of the fittest).

Step 5 - If the fittest individual meets your specifications, then stop,
else go to Step 2.

Comments.

The GA concept is very simple. However the implementation can be a
nightmare. For this example,
it is an iterative process within an iterative process so it will take a
while to get any results. Also,
you have to write your raytrace program such that is can easily be
configured to give you the required outputs. And most importantly, it must
be easily "re-configurable".

The breeding scheme is one of many. There are probably as many different
breeding schemes as
there are programmers!!

There is a random element present. Random numbers govern the inheritance
paths and this stops the
GA from getting trapped in "local minima".

This method will not give you "the correct answer" but it will
generate lots of possible combinations
of (R1, R2, R4) that satisfy your criteria to varying degrees.

Note that the above example is just that - an example. It will not work
because of all the
" * Others that I haven't thought of " things like lens
thicknesses. My raytrace program requires
a thickness otherwise it refuses to run.

You are in no way restricted to spherical surfaces as someone else on this
list suggested.
You can try and optimise ALL of the aberrations mentioned above. Warning -
be prepared to wait!
This also stresses the importance that the raytrace engine must be easily
"re-configurable".

I'm also uncertain that any miracles of compactness and economy are waiting
for us.(Mark)

BUT HELL, IT'S GREAT FUN TO PLAY WITH !!!!

Well, that's my contribution to the ATM community. Hope it's shed some
light (not light pollution)
on a new ??? avenue of doing things.

Cheers
Frank Q

--- BBBS/NT v4.01 Flag-4