University Lowbrow Astronomers

Genetic Competition.

by Tom Ryan
Printed in Reflections: March, 2004.

I was having a discussion with the mechanical engineers at one of the companies I occasionally work for, and they wanted to know about Zemax.  I had been brought in as an optical engineer to solve a couple of their product’s more puzzling problems, and they were frankly irritated that management had given me carte blanc to change their mechanical designs in any way I chose, and became even more unhappy when the changes worked.  It couldn’t be me, they reasoned.  After all, I’m old, short, and my memory isn’t so good, which probably reflects the condition of my brain in general.  It must be the optical design software I was using, and they wanted to know about it, so they could wield the power of the Ring.

I explained that Zemax was a little like the Autocad program they were using, in that it could make drawings of lens systems, and trace light rays through the resulting system to see where they ended up.  They already knew that, since they had been instructed to match the positions of the lens mounts in Autocad to the positions that Zemax dictated.  They had seen Zemax’s drawings, and they felt that they were pretty crude.  One of the guys showed me that he had an add-on program to Autocad that traced rays, and it looked a whole lot better on the screen than the output of Zemax, so what was so special about Zemax?

Now, these guys were using Autocad, which is still a very popular program.  Autocad produces absolutely beautiful blueprints, but it had its finest hour sometime in the 1980’s.  Mechanical CAD programs have moved on in many ways.  Ways which are mysterious to most Autocad fans.  One of these ways is automatic design optimization, and Zemax has got it, and Autocad doesn’t.

Automatic design optimization is what takes place when a design engineer draws a giant hunk of cast iron between the alternator and the engine block, and tells the program to change it’s dimensions and material type to produce the lightest possible bracket that will keep the alternator attached to the engine until the warranty period is over.  Pro/Mechanica does this, and so do a couple of other mechanical design programs.  Zemax does this with lenses.  I told the guys that Zemax could start an optical design with a bunch of parallel plates instead of lenses, and it would produce an excellent optical design, sometimes the best one possible, at the press of its “Optimize” button.

Their suspicions were immediately confirmed.  “If Zemax will do that, then what the hell do we need you for?”

A good question.  When people spend a lifetime listening to just one news source (Autocad is best!) they can appear naive when they get into the wide, wide world, and giving advice to the willfully naive is an impulse that I try to resist.  There’s no percentage in it.  People who need advice usually won’t take it, and people who will take advice usually don’t need it.

There is, however, something to be gained by keeping your customers happy.  I told them that Zemax occasionally produces designs which are impossible to build.  Lenses with negative thicknesses, spaces between lenses where the light goes backwards, and other impossibilities.  Oh, they said.

The truth is a little more complicated.  Zemax has two methods of optimizing a design, which it calls Local and Global.  In both cases, Zemax is trying to minimize a value that the lens designer constructs out of the desired performance of the system.  You could call it a merit function, or performance, or attractiveness, but in all cases, it is a function of the parts of the optical system that Zemax is allowed to change.  It may be constructed out of the size of the focused spot that the system forms at certain field angles and wavelengths, or the angle that the rays strike the focal plane, or anything else that you want to control.  Whatever it is, Zemax changes the lens spacings, radii, and other things to make this value as small as possible.

The Local optimization routine is based on damped least squares, which means that Zemax looks at the optical system that the designer provided, computes the merit function, calculates the derivative of the merit function with respect to all of the variables that it can change, and moves the system “downslope” in variable space.  It’s like what you would do if you were blindfolded on a hill, and were asked to find the lowest point possible.  You’d feel around in all directions, and then take a step in the steepest down direction.

This method works very well in finding a local minimum.  Optical space is vast, however, and usually looks more like West Virginia than Meteor Crater.  A local minimum may not be a very good solution, but the optimization routine can’t climb up over a hill to find a lower valley on the other side.  Why, you ask, can’t Zemax, or any other optimization program, just calculate the merit function for all possible solutions, up hill and down?  The answer involves the meaning of the word Never.  J. Jeans said that “six monkeys, set to strum unintelligently on typewriters for millions of millions of years, would be bound in time to write all of the books in the British Museum.”  Though it sounds good in a public lecture, Jeans’ failure to actually do the math on this type of problem would lead him to buy lottery tickets today.  The truth is that the probability that 10^10 monkeys, seated at typewriters throughout the age of the universe, each hitting 10 keys per second, would type out even one single book (Hamlet, for example, at 10^5 characters), is 10^(-164,316).  That means Never.

Thoroughly evaluating the solution space of a very simple lens system with just 12 different variables (three lenses having six surfaces, three glass thicknesses and three air gaps) would take about 300 billion years on a fast computer.  This illustrates what I think of as the failure of the deterministic method.

I might add at this point that Zemax will only produce impossible solutions if the designer has done an incomplete job of setting limits on how far Zemax is allowed to change variables.  When exploring the initial stages of a design, though, it’s often just not worthwhile to type in all the possible limits.

To get over a local hill, Zemax must switch gears to its Global optimization routine.  Its Global optimization routine is based on Genetic Algorithms which, in turn, are modeled on life itself.  Genetic algorithms model the variables of a system as bits of an imaginary creature’s genetic code, and they evaluate the creature’s code in terms of its suitability for survival.  A number of creatures are created, perhaps 100, and creatures whose suitability for survival is high are bred with one another to form new creatures.  The least suitable are eliminated, and the population is tested again.  Sometimes random mutations are inserted into the population.  A superior creature can last many generations before it is out-competed by its offspring.

To give you some idea of how this really works, lets say that a variable, such as the conic constant of a mirror (which determines whether it is a sphere, parabola, hyperbola, or something else entirely) is allowed to take on values within a certain range.  In a simple four bit (not 32-bit) computer, one end of the range is assigned the value of 0000, and the other end the value of 1111.  Perhaps one particular creature’s conic constant is randomly assigned the value 1010.  All of the other variables (like radius and thicknesses) are also assigned ranges and values, and all of the resulting four-bit numbers are strung together to make one large number.  That number is the creature’s genetic code.  Every creature’s code is then examined for its suitability to survive.  In a simple case, that might just mean asking whether the creature brings the light closer to a focus or not.  Creatures whose genetic code happens to focus light better than others are more suitable to survive.  The best perhaps half of the population are chosen to reproduce.  Reproduction is carried out by randomly selecting bits from one parent’s code (say 10XX) and taking the remaining bits from another parent (XX11) to produce the offspring’s code (1011).  The population has now grown by the number of offspring, and in the interests of keeping the calculations to a manageable number, an equal number of least suitable codes is eliminated from the pool.

Since the initial population has the components of its genetic code chosen completely at random, the variables can be said to range across all of the hills and valleys that the lens designer permits, when he or she initially sets the ranges of the variables.  The global search space can be as large as the designer wishes.  The designer is also responsible for deciding which traits are selected, when he creates the merit function.

How well does this work, you ask?  When the problem of a three lens system with 12 variables was analyzed by the Genetic Algorithm optimization routine, starting from parallel plates, the routine found a very good solution in six seconds.  It found a slightly better solution in four hours.  Did it find the global best solution?  There is no way to know, unless you are willing to wait 300 billion years.

The speed with which this method produces a very good solution should be a wake up call to creationists.  The likelihood of a pile of mud self-assembling into a human, a tree, or a butterfly is much worse than 10^(-164,316), but the likelihood of any adaptable, self-reproducing, unlimited process, starting from a small population of interacting simple hydrocarbons, eventually taking over the universe, is very close to 1.

So, the real reason that the above-mentioned company might need me is to set reasonable limits on where to look for solutions, and to decide what constitutes a good solution when one is found.  This process is not foolproof, though, and I will admit, I make mistakes from time to time.

Two examples of Genetic Competition-driven design.

Links

Copyright Info

Copyright © 2013, the University Lowbrow Astronomers. (The University Lowbrow Astronomers are an amateur astronomy club based in Ann Arbor, Michigan).
This page originally appeared in Reflections of the University Lowbrow Astronomers (the club newsletter).
This page revised Sunday, March 9, 2014 4:30 PM.
This web server is provided by the University of Michigan; the University of Michigan does not permit profit making activity on this web server.
Do you have comments about this page or want more information about the club? Contact Us.