THE DARWINIAN
      RANDOM SEARCH METHOD
      
      During the course
      of some work on a certain klystron, it became desirable to come up with a
      lumped element "equivalent" network to represent a distributed
      element 2-cavity network coupled to a waveguide. Walt Gasta and I
      presented a paper at the Monterey tube conference on our work toward this
      end. This presentation was brief and highly technical and not suitable for
      anyone not directly concerned with the issues. But I feel that the ideas
      and the results are, or should be, of much broader interest to some, thus
      this effort here.
      Some technical
      discussion is, however, necessary (or so I feel) for my reader to grasp
      the full impact of my thesis. My introduction to "lumped element
      equivalent networks" came down from Jim Ebers, my professor and
      thesis advisor, when I was at Ohio State University in 1951. The specific
      course was entitled "Network Synthesis". I was pretty well
      versed in "Network Analysis" by this time. The problem in N.A.
      is this: given a network of specific elements and the driving function…
      the applied voltages and/or currents… find the response function. The
      problem in N.S. is this: given the driving function and the desired
      response, find the network elements. In the first case, the solution is
      almost always unique, while in the latter case the solution is generally
      impossible and usually an approximation at best. As graduate students, the
      class was abundantly familiar with lumped circuit elements, Inductors, L
      (Henries), Capacitors, C (Farads), and resistors, R (Ohms), as well as
      Voltages, V (Volts), and Currents, I (Amperes).
      But any
      fundamental understanding of Electricity and Magnetism requires some
      understanding of Maxwell’s Equations. These are a set of partial
      differential equations in 4-dimensions (3-space and 1-time) describing
      Electric Fields, E (Volts/Meter), and Magnetic Fields, H (Ampere/Meter). A
      "Field" may be thought of as a region in space and time to which
      we may assign numerical values, magnitude and direction, to various
      quantities at each point. Many relatively simple solutions to Maxwell’s
      Equations, for certain geometries, are quite familiar to students of
      electrical engineering, but (except for electrolytic tank and deformable
      membrane analogs, etc.) the general solutions for more complex geometries
      were practically insoluble before the advent of fast digital computers and
      sophisticated software. Before this, Human Intuition was all-powerful.
      Ebers once
      returned from his summer vacation and told several of his students of
      watching a school of porpoises leaping and playing ahead of the ship he
      was on somewhere in the South Pacific. How such marvelous creatures came
      to be was a great challenge to him, for one of his oft-repeated basic
      principles was that "things usually happen for a reason, unless, of
      course, they just happen". This latter proposition was, of course,
      pure anathema to us budding scientists.
      Ebers built and
      studied a variety of vacuum tubes, called klystrons, in the Vacuum Tube
      Laboratory at Ohio State where I served as a graduate student-intern. The
      active element in his klystrons was an electron beam flowing through a
      resonant cavity coupled to an output waveguide. The electron beam excited
      an electric field in the cavity and some of the kinetic energy of the beam
      electrons was converted to electromagnetic energy that appeared as an
      electromagnetic wave in the output waveguide. This E-M wave was useful for
      all manner of stuff.
      Almost any
      hardware configuration of like elements… electron beam, resonant cavity,
      and output waveguide… worked in some sense, but Ebers and all others at
      his level insisted on a theory to explain all or most of the observed
      performance. Without such a theory there was no meaningful understanding
      and no likelihood of fine tuning the performance of any specific device or
      branching off into new territory. The ideal procedure was a complete field
      solution coupled with the equations of motion and the applicable
      conservation laws of physics, but in those slide rule days and with time
      being recognized as money, almost no one could afford the luxury. Not
      everyone was wholly satisfied with this conclusion. Ebers’ and my boss,
      Prof. E. M. Boone, once reminded us of one of his heroes in science who
      compiled extensive tables of logarithms and trigonometric functions
      longhand over a period of years.
      Ebers’ approach
      was to reduce the resonant cavity to a simple "equivalent"
      lumped element network and the electron beam and consequent Electric and
      Magnetic fields to Voltages and Currents. A resonant frequency and a loss
      factor, or "Q", could characterize the electro-magnetic fields
      in the cavity almost uniquely over a narrow, but more than adequate, band
      of frequencies. A simple lumped element network of an inductor, L, a
      capacitor, C, and a resistor, R, connected in parallel could be similarly
      characterized. If the stored energy in terms of the Electric and Magnetic
      fields in the cavity were made identical, the two devices were
      mathematically indistinguishable in the vicinity of the resonant
      frequency. The mathematics of network analysis was far simpler than field
      analysis while Voltages and Currents were far simpler to deal with than
      Electric and Magnetic fields and the equations of motion with regard to
      the electron beam. The subsequent theory of klystron behavior based on
      these ideas accurately predicted the behavior of the real devices and did,
      indeed, lead to the discovery of more and more advanced devices.
      Another matter
      that interested Ebers greatly in his few idle hours was the protective
      coloration of certain creatures in nature. Boone liked to take his
      vacations climbing mountains out West or wandering over the cactus deserts
      in Arizona. He once brought in some photographs of horned toads barely
      visible against the background of the desert floor. Ebers later made the
      comment to a couple of his students that this probably happened for a
      reason, unless, of course, it just happened. He saw it as an advanced
      exercise in Network Synthesis thus: given the driving functions and the
      desired response, find the network elements. The driving function here was
      sunlight while the desired response was invisibility as referred to your
      predators, and the network elements were the myriad details of your
      coloration. He suggested that one-day, perhaps, we might have computers
      powerful and fast enough to address such problems in a meaningful way.
      At the outset of
      the klystron project, a 2-cavity Extended Interaction Output Circuit, EIOC,
      had been built following our best understanding and intuition, but the
      actual response in terms of the output power across a specified band of
      frequencies fell short of the project requirements. It was not clear how
      to adjust the geometry to improve matters and the need for a lumped
      element model and an advanced analysis of beam kinetics to more precisely
      define the driving function was indicated. Our competitors, at Brand-X a
      few miles down the street, were following an approach based on a complete
      field analysis coupled with the electron beam kinetics. This analysis was
      based on the latest and most advanced PIC (Particle-In-Cell) software from
      the National Laboratories. A single case (frequency) could take up to 36
      hours to converge. We did not have the luxury of the software or an
      operator who knew how to run it. In the end, this competitor told the
      customer that the goals of the project were impossible to meet.
      Ebers was able to
      develop his klystron theory for a single cavity device based on a
      3-element lumped equivalent model. When, in the 1990s, we tried to find a
      lumped element network to simulate a 2-cavity distributed network, the
      simplest network we could envision had at least 12 elements. Two of these
      elements, the interaction gaps, could be simulated reasonably well by
      capacitors that were found directly from a field analysis of the actual
      geometry, thanks to powerful fast computers and advanced software. This
      analysis was required only once, but we were left with 10 elements to
      find. From the Network Synthesis course I recalled, after some effort,
      that we might somehow, in principal, measure the "impedance" of
      the real EIOC at 10 frequencies and then derive a 10 x 10 impedance matrix
      for a lumped element model. We could then, in principle, invert the matrix
      to find the 10-element values uniquely. The concept boggled my mind. I did
      not have the ability, nor did anyone else available to me.
      Another standard
      approach was to reduce the number of elements to a tractable few by
      discretely modifying the actual hardware. It was easy, for example, to
      place a shorting bar through the beam hole of each cavity, in turn, and to
      measure the resonant frequency of each cavity. Knowing the capacitance
      from field analysis made it a simple matter to calculate the equivalent
      inductance. When the shorting bars, equipped with very weakly coupled
      electric probes, were placed so as to excite both cavities in coupled mode…
      with the waveguide output iris shorted… it was possible to find an
      equivalent element for the coupling iris between the cavities. It was then
      possible to remove the short over the output iris and measure the loaded
      "Q" of the lot and, hopefully, find the remaining elements.
      This done, it was
      a fairly simple matter to calculate the impedance response of the entire
      lumped element network based on the element values thus found and compare
      this with the impedance of the actual hardware. The results were far from
      satisfactory. One factor was the fundamental fact that "Waveguide
      Impedance" and "Network Impedance" and not entirely
      compatible ideas for reasons we need not go into here. The phase angle of
      the reflection coefficient, however, was easily measured as well as
      calculated and did, in principle, relate directly. Even so the element
      values found by perturbing the hardware in various ways did not lead to
      useful results.
      I have long since
      been accustomed to assigning such matters to my sub-conscious during
      sleep. I make it a point to think about the problem as I am falling asleep
      and quite often I wake up with either a partial solution or a restatement
      of the problem. I find nothing mysterious or mystical about this process.
      In this case, after several attempts, I woke up thinking about an article
      I had seen on TV or read somewhere in a nature magazine. A certain family
      of entomologists in England had been collecting a species of moths for
      several generations. Over an extended period of time, the color patterns
      of these moths had become darker and darker. A theory was advanced based
      on the fact that this coincided with the darkening of the bark of the
      trees the moths were accustomed to resting on, due to the burning of coal
      to heat the homes in the region. Perhaps, so went the speculation, the
      darker moths were less visible to hungry birds, a direct example of Darwin’s
      theory of survival by adaptation to the external environment.
      I tried, without
      success, to recall the details of Ebers’ comments related to the
      protective coloration of horned toads. I had no basis for such
      speculation, but I supposed that each generation of moths or horned toads
      might be expected to have a wide variation in the precise fine details of
      their pattern of coloration. Certainly I had observed among horned tomato
      worms, that while each was almost invisible on a tomato vine, no two were
      exactly alike when examined closely. I was also familiar with the argument
      for bi-sexual reproduction in that the offspring, though very similar,
      were each slightly different genetically, individual to individual. If
      reproduction by cloning were to be the rule, so goes the argument,
      parasites would have a much simpler task in decoding the defenses of hosts
      and defeating them.
      How did all this
      gobble-de-gook apply to my Network Synthesis problem?
      I reckoned that
      if I started with a crude, but reasonable, approximation to a set of
      values for my 10 or so lumped elements and made some sort of a comparison
      to the actual EIOC hardware, I could define a numerical "error"
      value. In this case, the RMS (Root Mean Square) of the difference between
      the calculated values of the phase angle of the reflection coefficient
      based on trial values of the elements and the measured value of the same
      angle from the hardware seemed most appropriate. With the most simple
      basic computer software I could make hundreds, or perhaps thousands, of
      such calculations per second. It was then a simple matter to envision the
      process suggested by the flow diagram illustrated below here:
      
      
      
      I would start
      with a set of values based on the crude perturbation methods described
      earlier, and call these the "Parent Values". I would then create
      a similar, but not identical, set of values, I would call "Offspring
      Values" by modifying each of the separate "Parent Values"
      by a small, and wholly independent, random amount. The calculated angle of
      the reflection coefficient for this offspring set of values could then be
      calculated and compared to the measured values. The RMS error value was
      then found, all in a few milliseconds. If the RMS error was greater than
      the value already found, clearly this trial offspring had even less
      survival value than the parent and would be discarded. If, however, on
      rare occasions, the offspring network was a better fit to the data than
      the parent network, it made sense to replace the old parent with the newly
      found offspring. Since we can make hundreds or thousands of such
      comparisons per second we should, perhaps, not be surprised to find better
      and better networks in a reasonable time. It was a bit tricky learning
      just how much to make the random changes for optimum convergence, but in
      due course we were finding lumped element networks that were
      indistinguishable from the actual EIOC hardware in the vital senses that
      1) the impedance levels at the beam interaction gaps were the same and 2)
      that the phase relationships between voltages and currents were the same
      at all nodes.
      Although we
      started finding better and better sets of lumped element values from the
      outset, there was still a small, but annoying, lack of conformity between
      the measured data and the calculated results. It eventually occurred to me
      that there might be some non-negligible amount of electric field energy in
      the coupling iris between the cavities. I went to the laboratory and
      measured the resonant frequency of this iris and found it to be at roughly
      the second harmonic of the frequency band of interest. When I included a
      small capacitance of the right value suggested in the overall network, the
      observed discrepancy went away. In the end, the RMS values of the error
      results across the frequency band were on the order of the reproducibility
      of the test equipment. It made a powerful impression on me that this
      random search method did not allow me to find a good set of values for an
      inappropriate configuration of lumped elements.
      It also became
      clear that, as in the case of moths and horned toads, there was no unique
      set of network elements. When the routine was run again after changing any
      one element in the original Parent Network, a new Offspring Network as
      good as the original would always be found, although the individual
      elements might vary from the original values by a few percent, more or
      less. Pressing matters elsewhere precluded further work on this matter.
      
       
      
      Just how much
      this development contributed to the ultimate success of the project I
      could not say, but it did a great deal for the intuition of all those
      concerned and we did successfully complete the overall project. The
      original goals were possible, after all.
      The prime impetus
      for developing this method was, as stated, finding a lumped element
      "equivalent" model for the EIOC, but several more interesting
      problems came to my attention along the way. One involved the
      transition-matching network between a CCTWT (Coupled Cavity Traveling Wave
      Tube) output section and the output waveguide. This device had been in
      production for many years, but the yield was less-than-optimum and there
      was often a lot of hands-on work required on the match during the final
      stages. The responsible technician, for whom I consulted in my spare time,
      was accustomed to characterizing the transition (waveguide to CC Stack) by
      first terminating the CC Stack using a length of lossy paper inserted into
      the beam hole. This was the way I was taught to terminate a CC Stack in
      1956. I didn’t like it then and when I inserted a metal bar into the end
      of the stack after the paper, I could still detect some reflections from
      it looking into the output waveguide. The lossy paper was not a perfect
      termination.
      Thanks to Walt
      Gasta, we had recently become immersed in "The 3-Short Method"
      for characterizing certain common microwave networks. The CC Stack seemed
      like an ideal candidate. This involved a measurement of the angle of the
      reflection coefficient looking into the output waveguide with the CC Stack
      shorted by a copper shorting bar in the beam hole. The shorting bar is
      carefully placed at 3 precisely periodic positions. From the Omega-Beta
      characteristics of the CC Stack and the angle of the reflection
      coefficient for each case we can then accurately calculate the
      S-Parameters of the transition network between the CC Stack and the
      waveguide. With this data in hand, we can then go about a systematic
      Darwinian Random Search for sets of reflecting elements in the output
      waveguide likely to give a good match.
      One of the
      essential ingredients in a suitable computer routine is a set of
      sub-routines designed to return the reflection characteristics of some
      basic elements such as inductive posts, height steps, and dielectric
      windows. Our subroutines were based on the solutions set forth in the MIT
      Radiation Labs Handbooks developed at MIT during WWII, N. Marcuvits,
      Editor.
      The starting
      point for a set of "Parent Values" for a CC Stack-to-Waveguide
      match was determined by intuition. In this case, a set of two inductive
      posts in the output waveguide was chosen. My intuition would have been
      hard pressed to place them where the Random Search routine liked to have
      them, but I couldn’t argue with the results. In the laboratory the
      results were confirmed.
      Before the
      S-Parameters looking into the waveguide could be determined, it was
      necessary to extract the S-Parameters of the vacuum window. This was done
      using several windows that had not yet been incorporated into production
      TWTs. It was apparent that these windows were roughly the same, but
      certainly not ideal so far as their microwave characteristics was
      concerned. At our earliest convenience an attempt was made to find a
      better window configuration. This window was also matched using two
      inductive posts, one each on either side of the ceramic disk and the
      housing for it. Again we found significantly better locations for these
      inductive posts using these random search methods. The last I heard the
      production yield for these CCTWTS was still significantly improved over
      what they were before we began this work.
      Rene M. Rogers