View Full Version : Organic Computing, Dont Design it, Evolve It :|

10th July 2007, 12:53 AM
[leached from a post in Atomic.com.au forums]

On the Origin of Circuits

In a unique laboratory in Sussex, England, a computer carefully scrutinized every member of large and diverse set of candidates. Each was evaluated dispassionately, and assigned a numeric score according to a strict set of criteria. This machine's task was to single out the best possible pairings from the group, then force the selected couples to mate so that it might extract the resulting offspring and repeat the process with the following generation. As predicted, with each breeding cycle the offspring evolved slightly, nudging the population incrementally closer to the computer's pre-programmed definition of the perfect individual.

The candidates in question were not the stuff of blood, guts, and chromosomes that are normally associated with evolution, rather they were clumps of ones and zeros residing within a specialized computer chip. As these primitive bodies of data bumped together in their silicon logic cells, Adrian Thompson– the machine's master– observed with curiosity and enthusiasm.

Dr. Adrian Thompson is a researcher operating from the Department of Informatics at the University of Sussex, and his experimentation in the mid-1990s represented some of science's first practical attempts to penetrate the virgin domain of hardware evolution. The concept is roughly analogous to Charles Darwin's elegant principle of natural selection, which describes how individuals with the most advantageous traits are more likely to survive and reproduce. This process tends to preserve favorable characteristics by passing them to the survivors' descendants, while simultaneously suppressing the spread of less-useful traits.

Dr. Thompson dabbled with computer circuits in order to determine whether survival-of-the-fittest principles might provide hints for improved microchip designs. As a test bed, he procured a special type of chip called a Field-Programmable Gate Array (FPGA) whose internal logic can be completely rewritten as opposed to the fixed design of normal chips. This flexibility results in a circuit whose operation is hot and slow compared to conventional counterparts, but it allows a single chip to become a modem, a voice-recognition unit, an audio processor, or just about any other computer component. All one must do is load the appropriate configuration.

The informatics researcher began his experiment by selecting a straightforward task for the chip to complete: he decided that it must reliably differentiate between two particular audio tones. A traditional sound processor with its hundreds of thousands of pre-programmed logic blocks would have no trouble filling such a request, but Thompson wanted to ensure that his hardware evolved a novel solution. To that end, he employed a chip only ten cells wide and ten cells across– a mere 100 logic gates. He also strayed from convention by omitting the system clock, thereby stripping the chip of its ability to synchronize its digital resources in the traditional way.

He cooked up a batch of primordial data-soup by generating fifty random blobs of ones and zeros. One by one his computer loaded these digital genomes into the FPGA chip, played the two distinct audio tones, and rated each genome's fitness according to how closely its output satisfied pre-set criteria. Unsurprisingly, none of the initial randomized configuration programs came anywhere close. Even the top performers were so profoundly inadequate that the computer had to choose its favorites based on tiny nuances. The genetic algorithm eliminated the worst of the bunch, and the best were allowed to mingle their virtual DNA by swapping fragments of source code with their partners. Occasional mutations were introduced into the fruit of their digital loins when the control program randomly changed a one or a zero here and there.

For the first hundred generations or so, there were few indications that the circuit-spawn were any improvement over their random-blob ancestors. But soon the chip began to show some encouraging twitches. By generation #220 the FPGA was essentially mimicking the input it received, a reaction which was a far cry from the desired result but evidence of progress nonetheless. The chip's performance improved in minuscule increments as the non-stop electronic orgy produced a parade of increasingly competent offspring. Around generation #650, the chip had developed some sensitivity to the 1kHz waveform, and by generation #1,400 its success rate in identifying either tone had increased to more than 50%.

Finally, after just over 4,000 generations, test system settled upon the best program. When Dr. Thompson played the 1kHz tone, the microchip unfailingly reacted by decreasing its power output to zero volts. When he played the 10kHz tone, the output jumped up to five volts. He pushed the chip even farther by requiring it to react to vocal "stop" and "go" commands, a task it met with a few hundred more generations of evolution. As predicted, the principle of natural selection could successfully produce specialized circuits using a fraction of the resources a human would have required. And no one had the foggiest notion how it worked.

Dr. Thompson peered inside his perfect offspring to gain insight into its methods, but what he found inside was baffling. The plucky chip was utilizing only thirty-seven of its one hundred logic gates, and most of them were arranged in a curious collection of feedback loops. Five individual logic cells were functionally disconnected from the rest– with no pathways that would allow them to influence the output– yet when the researcher disabled any one of them the chip lost its ability to discriminate the tones. Furthermore, the final program did not work reliably when it was loaded onto other FPGAs of the same type.

It seems that evolution had not merely selected the best code for the task, it had also advocated those programs which took advantage of the electromagnetic quirks of that specific microchip environment. The five separate logic cells were clearly crucial to the chip's operation, but they were interacting with the main circuitry through some unorthodox method– most likely via the subtle magnetic fields that are created when electrons flow through circuitry, an effect known as magnetic flux. There was also evidence that the circuit was not relying solely on the transistors' absolute ON and OFF positions like a typical chip; it was capitalizing upon analogue shades of gray along with the digital black and white.

Today, researchers are just beginning to explore the real-world potential of evolving circuitry. Engineers are experimenting with rudimentary adaptive hardware systems which marry evolvable chips to conventional equipment. Such hybrids quickly adapt to new demands by constantly evolving and adjusting their control code. The space exploration industry is intrigued by the technology– an evolving system could dynamically reprogram itself to avoid any circuits damaged by radiation, reducing the need for heavy shielding and redundant systems. Similarly, researchers speculate that robots might one day use evolution-inspired systems to quickly adapt to unforeseen obstacles in their environment.

Modern supercomputers are also contributing to artificial evolution, applying their massive processing power to develop simulated prototypes. The initial designs are thoroughly tested within carefully crafted virtual environments, and the best candidates are used to breed successive batches until a satisfactory solution has evolved. These last-generation designs are then fabricated and tested in the real world. NASA recently used this approach to produce the antenna for a spacegoing vessel, resulting in flamboyant-yet-effective shapes that vaguely resemble organic lifeforms– unlike anything an engineer would design without the benefit of mood-altering drugs. Scientists hope to eventually use genetic algorithms to improve complex devices such as motors and rockets, but progress is dependent upon the development of extremely accurate simulations.

These evolutionary computer systems may almost appear to demonstrate a kind of sentience as they dispense graceful solutions to complex problems. But this apparent intelligence is an illusion caused by the fact that the overwhelming majority of design variations tested by the system– most of them appallingly unfit for the task– are never revealed. According to current understanding, even the most advanced microchips fall far short of the resources necessary to host legitimate intelligence. On the other hand, at one time many engineers might have insisted that it's impossible to train an unclocked 10×10 FPGA to distinguish between two distinct audio tones.

There is also an ethical conundrum regarding the notion that human lives may one day depend upon these incomprehensible systems. There is concern that a dormant "gene" in a medical system or flight control program might express itself without warning, sending the mutant software on an unpredictable rampage. Similarly, poorly defined criteria might allow a self-adapting system to explore dangerous options in its single-minded thrust towards efficiency, placing human lives in peril. Only time and testing will determine whether these risks can be mitigated.

If evolvable hardware passes muster, the Sussex circuits may pave the way for a new kind of computing. Given a sufficiently well-endowed Field-Programmable Gate Array and a few thousand exchanges of genetic material, there are few computational roles that these young and flexible microchips will be unable to satisfy. While today's computers politely use programmed instructions to solve predictable problems, these adaptable alternatives may one day strip away such limits and lay bare the elegant solutions that the human mind is reluctant– or powerless– to conceive on its own.

10th July 2007, 12:54 AM
Link to Original Article here... Note Stupid 10,000 Character word limit on posts.


10th July 2007, 12:55 AM
[Also leached from original post on Atomic.com.au Forums :P]

Automated Antenna Design

The spectrum of antenna designs for applications in communication, radar, and remote sensing systems is vast, and there is an increasing need for high-performance, customized antennas. Current methods of designing and optimizing antennas by hand are time and labor intensive, limit complexity, increase the time and cost expended, and require that antenna engineers have significant knowledge of the universe of antenna designs.

The use of evolutionary programming techniques to automate the design of antennas has recently garnered much attention. Considerable research has been focused on determining whether evolutionary techniques can be used to automatically design and optimize antennas so that they outperform those designed by expert antenna designers, and even whether evolutionary techniques can be used to design antennas in cases where humans are simply unable to.

In the Evolvable Systems Group, we have been conducting research on automated antenna design. Our approach has been to encode antenna structure into a genome and use a GA to evolve an antenna that best meets the desired antenna performance as defined in a fitness function. Antenna evaluations are performed by first converting a genotype into an antenna structure, and then simulating this antenna using the Numerical Electromagnetic Code (NEC) antenna simulation software.

To date, we have conducted a benchmark study attempting to optimize the well-known but difficult-to-design Yagi-Uda antenna, and conducted research on the automated design of several different spacecraft antennas, including the Mars Odyssey UHF antenna and the ST5 antenna.

Mars Odyssey UHF Antenna

The Mars Odyssey spacecraft is an orbiter carrying science experiments designed to make global observations of Mars. It carries onboard an UHF antenna, responsible for the primary, full-duplex, data link between the spacecraft and landed assets. The currently deployed antenna is a graphite/epoxy quadrifilar helix antenna (QHA) with a small ground plane.

The performance characteristics of an antenna can be affected by nearby structures. However, the currently deployed UHF antenna was not designed with surrounding structures in mind. As a result, the solar panels on the spacecraft sometimes have to be moved in order to optimize antenna performance. We therefore used the NEC simulator to evaluate the performance of various antenna designs in the presence of models representing the solar panel and fuel tanks.

Using a coevolutionary algorithm, we optimized the design parameters for a quadrifilar helical antenna by encoding various parameters that control the shape and size of the antenna into a linear representation.

We were able to evolve a quadrifilar helix antenna that was a quarter of the volume of the currently deployed Mars Odyssey antenna yet still achieving the performance characteristics of the latter.

ST5 Antenna

The Space Technology 5 Project (ST5) is one of NASA's New Millennium Program missions that will launch multiple miniature spacecraft to test innovative concepts and technologies in the harsh environment of space. During flight validation of its technologies, ST5 may measure the effect of solar activity on the Earth's magnetosphere. ST5's objective is to demonstrate and qualify innovative technologies and concepts for application to future space missions.

The three ST5 spacecraft will communicate with a 34 meter ground-based dish antenna. The antenna specifications for the mission present a challenging design problem, requiring both a wide beamwidth for a circularly-polarized wave and a wide bandwidth. Based on the requirements, a contractor was awarded the contract to design and build the antennas for the ST5 mission. The contractor proceeded using conventional design practices, relying on human expertise and antenna computer-aided design software to produce a compliant design and protoype. In parallel, our group worked on the evolutionary design and fabrication.

We devised a LOGO-like antenna constructing programming language where each node in the tree-structured representation is an antenna-construction command. An antenna is created by starting from the root of the tree and executing the commands at each node in the tree. In constructing an antenna, the current state (location and orientation) is maintained, and subsequent commands add wires or change the current state. We then used a genetic algorithm (GA) to evolve genotypes that specify the design for one arm, and built the complete antenna using four copies of the evolved arm.

The fitness function used to evaluate antennas is a function of the voltage standing wave ratio (VSWR) and gain values on the transmit and receive frequencies. VSWR is a way to quantify reflected-wave interference, and thus the amount of impedance mismatch at the junction. VSWR is the ratio between the highest voltage and the lowest voltage in the signal envelope along a transmission line.

The two best antennas found, one (ST5-3-10) from a GA that allowed branching and one (ST5-4W-03) from a GA that did not, were fabricated and tested. Antenna ST5-3-10 is a requirements-compliant antenna that was built and tested on an antenna test range. While it is slightly difficult to manufacture without the aid of automated wire-forming and soldering machines, it has a number of benefits as compared to the conventionally-designed antenna.

First, there is the potential of needing less power. Antenna ST5-3-10 achieves high gain (2-4dB) across a wider range of elevation angles. This allows a broader range of angles over which maximum data throughput can be achieved. Also, less power from the solar array and batteries may be required.

Second, the evolved antenna does not require a matching network nor a phasing circuit, removing two steps in design and fabrication of the antenna. A trivial transmission line may be used for the match on the flight antenna, but simulation results suggest that one is not required.

Third, the evolved antenna has more uniform coverage in that it has a uniform pattern with small ripples in the elevations of greatest interest (between 40 and 80 degrees). This allows for reliable performance as elevation angle relative to the ground changes.

Finally, the evolved antenna had a shorter design cycle. It was estimated that antenna ST5-3-10 took 3 person-months to design and fabricate the first prototype as compared to 5 person-months for the conventionally designed antenna.