Evolutionary Robotics and Open-Ended Design Automation - Biomimetics: Biologically Inspired Technologies - page 149

An approximate solution will suffice . Evolutionary algorithms do not provide guarantees on the solu-
tion optimality, and do not necessarily find the optimal solution. In many practical problem domains,
we do not require strict optimality; a solution is good enough if it is better than the competition.

.

Computer scientists often compare algorithms on the basis of their computational efficiency —
how fast can the algorithm solve a problem. A second (often neglected) factor affecting
the usefulness of algorithms is their economy: How many resources do you need to invest in
designing and implementing an algorithm before it can produce useful results? Evaluating algo-
rithms based on performance alone is equivalent to pricing products without amortizing their
development costs. As the cost of development labor increases and the cost of computing power
decreases, we begin to favor algorithms that are easy to implement and require little formal
knowledge in the problem domain, even if they are computationally less efficient. These trends
are becoming more pronounced as we venture into new scientific and engineering domains where
human intuition is poor.
Robotics is one area where these criteria are met: the physics are well understood, the building
blocks are well known, there is little formal design knowledge, and approximate solutions will
suffice. There are many more examples, especially in emerging fields. A typical domain where
these criteria are met is micro-scale design. For example, microphotonics devices manipulate light
(like microelectronic devices manipulate electrons). Their function depends on manipulating
photons at the quantum level. The physics is well understood, as we can predict the behavior
of photons by solving Maxwell's equations; the building blocks are well defined, as we know
the capabilities of microfabrication tools; little design knowledge exists as few people have the
intuition to design structures that manipulate light at subwavelength scales; and approximate
solutions will suffice as current solutions are suboptimal anyway. One notable challenge is
the design of regular (periodic) structures that confine light, known as photonic crystals . Figure
4.10a shows a way of representing the geometry of photonic cells as a hierarchy of partitions.
Evolving cell representations and checking their ability to confine light using a simulator produced
an interesting pattern shown in Figure 4.10b. This pattern outperforms human-designed patterns by

39383736353433323130

0
1
2
3
4
5
6
7
8
9

29
28
27
26
25
24
23
22
21
20

Split 5 to 24

Split 3 to 26 Split 7 to 22

10111213141516171819

1

Split 13 to 36 Split 13 to 36 1

1

1 Split 17 to 32 Split 17 to 32

0 1 0 1

(a) (b) (c)

Figure 4.10 Evolving photonic crystal geometries. (a) A tree representation is used to encode geometry of a
photonic cell by specifying a hierarchy of partition lines. The tree shown encodes the square ring shown at the top
right. (b) Evolving structures with large photonic bandgaps produced this structure (unit cell shown in inset). This
structure has a bandgap that is 10% larger than any human-designed pattern. (From Preble, S. F., Lipson, H.,
Lipson, M. (2005) Applied Physics Letters, 86 (c) A transmission electron micrograph of the Sea Mouse
spine (notoseta). The dark areas are chitin and the light areas are voids, with a spacing of 510 nm. (From Parker,
A. R., McPhedran, R. C., McKenzie, D. R., Botten, L. C., Nicorovici, N.-A. P. (2001) Nature, 409, 36-37.
With permission.)