Atomic force microscopy

From Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/Atomic_force_microscopy

An AFM generates images by scanning a small cantilever over the surface of a sample. The sharp tip on the end of the cantilever contacts the surface, bending the cantilever and changing the amount of laser light reflected into the photodiode. The height of the cantilever is then adjusted to restore the response signal, resulting in the measured cantilever height tracing the surface.

Atomic force microscopy (AFM) or scanning force microscopy (SFM) is a very-high-resolution type of scanning probe microscopy (SPM), with demonstrated resolution on the order of fractions of a nanometer, more than 1000 times better than the optical diffraction limit.

Overview

An atomic force microscope on the left with controlling computer on the right

Atomic force microscopy (AFM) is a type of scanning probe microscopy (SPM), with demonstrated resolution on the order of fractions of a nanometer, more than 1000 times better than the optical diffraction limit. The information is gathered by "feeling" or "touching" the surface with a mechanical probe. Piezoelectric elements that facilitate tiny but accurate and precise movements on (electronic) command enable precise scanning. Despite the name, the Atomic Force Microscope does not use the Nuclear force.

Abilities

The AFM has three major abilities: force measurement, topographic imaging, and manipulation.

In force measurement, AFMs can be used to measure the forces between the probe and the sample as a function of their mutual separation. This can be applied to perform force spectroscopy, to measure the mechanical properties of the sample, such as the sample's Young's modulus, a measure of stiffness.

For imaging, the reaction of the probe to the forces that the sample imposes on it can be used to form an image of the three-dimensional shape (topography) of a sample surface at a high resolution. This is achieved by raster scanning the position of the sample with respect to the tip and recording the height of the probe that corresponds to a constant probe-sample interaction (see § Topographic image for more). The surface topography is commonly displayed as a pseudocolor plot.

Although the initial publication about atomic force microscopy by Binnig, Quate and Gerber in 1986 speculated about the possibility of achieving atomic resolution, profound experimental challenges needed to be overcome before atomic resolution of defects and step edges in ambient (liquid) conditions was demonstrated in 1993 by Ohnesorge and Binnig. True atomic resolution of the silicon 7x7 surface—the atomic images of this surface obtained by STM had convinced the scientific community of the spectacular spatial resolution of scanning tunneling microscopy—had to wait a little longer before it was shown by Giessibl.

In manipulation, the forces between tip and sample can also be used to change the properties of the sample in a controlled way. Examples of this include atomic manipulation, scanning probe lithography and local stimulation of cells.

Simultaneous with the acquisition of topographical images, other properties of the sample can be measured locally and displayed as an image, often with similarly high resolution. Examples of such properties are mechanical properties like stiffness or adhesion strength and electrical properties such as conductivity or surface potential. In fact, the majority of SPM techniques are extensions of AFM that use this modality.

Other microscopy technologies

The major difference between atomic force microscopy and competing technologies such as optical microscopy and electron microscopy is that AFM does not use lenses or beam irradiation. Therefore, it does not suffer from a limitation in spatial resolution due to diffraction and aberration, and preparing a space for guiding the beam (by creating a vacuum) and staining the sample are not necessary.

There are several types of scanning microscopy including scanning probe microscopy (which includes AFM, scanning tunneling microscopy (STM) and near-field scanning optical microscope (SNOM/NSOM), STED microscopy (STED), and scanning electron microscopy and electrochemical AFM, EC-AFM). Although SNOM and STED use visible, infrared or even terahertz light to illuminate the sample, their resolution is not constrained by the diffraction limit.

Configuration

Fig. 3 shows an AFM, which typically consists of the following features. Numbers in parentheses correspond to numbered features in Fig. 3. Coordinate directions are defined by the coordinate system (0).

Fig. 3: Typical configuration of an AFM.
(1): Cantilever, (2): Support for cantilever, (3): Piezoelectric element (to oscillate cantilever at its eigen frequency), (4): Tip (Fixed to open end of a cantilever, acts as the probe), (5): Detector of deflection and motion of the cantilever, (6): Sample to be measured by AFM, (7): xyz drive, (moves sample (6) and stage (8) in x, y, and z directions with respect to a tip apex (4)), and (8): Stage.

The small spring-like cantilever (1) is carried by the support (2). Optionally, a piezoelectric element (typically made of a ceramic material) (3) oscillates the cantilever (1). The sharp tip (4) is fixed to the free end of the cantilever (1). The detector (5) records the deflection and motion of the cantilever (1). The sample (6) is mounted on the sample stage (8). An xyz drive (7) permits to displace the sample (6) and the sample stage (8) in x, y, and z directions with respect to the tip apex (4). Although Fig. 3 shows the drive attached to the sample, the drive can also be attached to the tip, or independent drives can be attached to both, since it is the relative displacement of the sample and tip that needs to be controlled. Controllers and plotter are not shown in Fig. 3.

According to the configuration described above, the interaction between tip and sample, which can be an atomic-scale phenomenon, is transduced into changes of the motion of cantilever, which is a macro-scale phenomenon. Several different aspects of the cantilever motion can be used to quantify the interaction between the tip and sample, most commonly the value of the deflection, the amplitude of an imposed oscillation of the cantilever, or the shift in resonance frequency of the cantilever (see section Imaging Modes).

Detector

The detector (5) of AFM measures the deflection (displacement with respect to the equilibrium position) of the cantilever and converts it into an electrical signal. The intensity of this signal will be proportional to the displacement of the cantilever.

Various methods of detection can be used, e.g. interferometry, optical levers, the piezoelectric method, and STM-based detectors (see section "AFM cantilever deflection measurement").

Image formation

This section applies specifically to imaging in § Contact mode. For other imaging modes, the process is similar, except that "deflection" should be replaced by the appropriate feedback variable.

When using the AFM to image a sample, the tip is brought into contact with the sample, and the sample is raster scanned along an x–y grid (fig 4). Most commonly, an electronic feedback loop is employed to keep the probe-sample force constant during scanning. This feedback loop has the cantilever deflection as input, and its output controls the distance along the z axis between the probe support (2 in fig. 3) and the sample support (8 in fig 3). As long as the tip remains in contact with the sample, and the sample is scanned in the x–y plane, height variations in the sample will change the deflection of the cantilever. The feedback then adjusts the height of the probe support so that the deflection is restored to a user-defined value (the setpoint). A properly adjusted feedback loop adjusts the support-sample separation continuously during the scanning motion, such that the deflection remains approximately constant. In this situation, the feedback output equals the sample surface topography to within a small error.

Historically, a different operation method has been used, in which the sample-probe support distance is kept constant and not controlled by a feedback (servo mechanism). In this mode, usually referred to as "constant-height mode," the deflection of the cantilever is recorded as a function of the sample x–y position. As long as the tip is in contact with the sample, the deflection then corresponds to surface topography. This method is now less commonly used because the forces between tip and sample are not controlled, which can lead to forces high enough to damage the tip or the sample. It is, however, common practice to record the deflection even when scanning in "constant force mode," with feedback. This reveals the small tracking error of the feedback, and can sometimes reveal features that the feedback was not able to adjust for.

The AFM signals, such as sample height or cantilever deflection, are recorded on a computer during the x–y scan. They are plotted in a pseudocolor image, in which each pixel represents an x–y position on the sample, and the color represents the recorded signal.

Fig. 5: Topographic image forming by AFM.
(1): Tip apex, (2): Sample surface, (3): Z-orbit of Tip apex, (4): Cantilever.

History

The AFM was invented by IBM scientists in 1985. The precursor to the AFM, the scanning tunneling microscope (STM), was developed by Gerd Binnig and Heinrich Rohrer in the early 1980s at IBM Research – Zurich, a development that earned them the 1986 Nobel Prize for Physics. Binnig invented the atomic force microscope and the first experimental implementation was made by Binnig, Quate and Gerber in 1986.

The first commercially available atomic force microscope was introduced in 1989. The AFM is one of the foremost tools for imaging, measuring, and manipulating matter at the nanoscale.

Applications

The AFM has been applied to problems in a wide range of disciplines of the natural sciences, including solid-state physics, semiconductor science and technology, molecular engineering, polymer chemistry and physics, surface chemistry, molecular biology, cell biology, and medicine.

Applications in the field of solid state physics include (a) the identification of atoms at a surface, (b) the evaluation of interactions between a specific atom and its neighboring atoms, and (c) the study of changes in physical properties arising from changes in an atomic arrangement through atomic manipulation.

In molecular biology, AFM can be used to study the structure and mechanical properties of protein complexes and assemblies. For example, AFM has been used to image microtubules and measure their stiffness.

In cellular biology, AFM can be used to attempt to distinguish cancer cells and normal cells based on a hardness of cells, and to evaluate interactions between a specific cell and its neighboring cells in a competitive culture system. AFM can also be used to indent cells, to study how they regulate the stiffness or shape of the cell membrane or wall.

In some variations, electric potentials can also be scanned using conducting cantilevers. In more advanced versions, currents can be passed through the tip to probe the electrical conductivity or transport of the underlying surface, but this is a challenging task with few research groups reporting consistent data (as of 2004).

Principles

Electron micrograph of a used AFM cantilever. Image width ~100 micrometers

 

Electron micrograph of a used AFM cantilever. Image width ~30 micrometers

The AFM consists of a cantilever with a sharp tip (probe) at its end that is used to scan the specimen surface. The cantilever is typically silicon or silicon nitride with a tip radius of curvature on the order of nanometers. When the tip is brought into proximity of a sample surface, forces between the tip and the sample lead to a deflection of the cantilever according to Hooke's law. Depending on the situation, forces that are measured in AFM include mechanical contact force, van der Waals forces, capillary forces, chemical bonding, electrostatic forces, magnetic forces (see magnetic force microscope, MFM), Casimir forces, solvation forces, etc. Along with force, additional quantities may simultaneously be measured through the use of specialized types of probes (see scanning thermal microscopy, scanning joule expansion microscopy, photothermal microspectroscopy, etc.).

Atomic force microscope topographical scan of a glass surface. The micro and nano-scale features of the glass can be observed, portraying the roughness of the material. The image space is (x,y,z) = (20 µm × 20 µm × 420 nm).

The AFM can be operated in a number of modes, depending on the application. In general, possible imaging modes are divided into static (also called contact) modes and a variety of dynamic (non-contact or "tapping") modes where the cantilever is vibrated or oscillated at a given frequency.

Imaging modes

AFM operation is usually described as one of three modes, according to the nature of the tip motion: contact mode, also called static mode (as opposed to the other two modes, which are called dynamic modes); tapping mode, also called intermittent contact, AC mode, or vibrating mode, or, after the detection mechanism, amplitude modulation AFM; and non-contact mode, or, again after the detection mechanism, frequency modulation AFM.

Despite the nomenclature, repulsive contact can occur or be avoided both in amplitude modulation AFM and frequency modulation AFM, depending on the settings.

Contact mode

In contact mode, the tip is "dragged" across the surface of the sample and the contours of the surface are measured either using the deflection of the cantilever directly or, more commonly, using the feedback signal required to keep the cantilever at a constant position. Because the measurement of a static signal is prone to noise and drift, low stiffness cantilevers (i.e. cantilevers with a low spring constant, k) are used to achieve a large enough deflection signal while keeping the interaction force low. Close to the surface of the sample, attractive forces can be quite strong, causing the tip to "snap-in" to the surface. Thus, contact mode AFM is almost always done at a depth where the overall force is repulsive, that is, in firm "contact" with the solid surface.

Tapping mode

Single polymer chains (0.4 nm thick) recorded in a tapping mode under aqueous media with different pH.

In ambient conditions, most samples develop a liquid meniscus layer. Because of this, keeping the probe tip close enough to the sample for short-range forces to become detectable while preventing the tip from sticking to the surface presents a major problem for contact mode in ambient conditions. Dynamic contact mode (also called intermittent contact, AC mode or tapping mode) was developed to bypass this problem. Nowadays, tapping mode is the most frequently used AFM mode when operating in ambient conditions or in liquids.

In tapping mode, the cantilever is driven to oscillate up and down at or near its resonance frequency. This oscillation is commonly achieved with a small piezo element in the cantilever holder, but other possibilities include an AC magnetic field (with magnetic cantilevers), piezoelectric cantilevers, or periodic heating with a modulated laser beam. The amplitude of this oscillation usually varies from several nm to 200 nm. In tapping mode, the frequency and amplitude of the driving signal are kept constant, leading to a constant amplitude of the cantilever oscillation as long as there is no drift or interaction with the surface. The interaction of forces acting on the cantilever when the tip comes close to the surface, van der Waals forces, dipole-dipole interactions, electrostatic forces, etc. cause the amplitude of the cantilever's oscillation to change (usually decrease) as the tip gets closer to the sample. This amplitude is used as the parameter that goes into the electronic servo that controls the height of the cantilever above the sample. The servo adjusts the height to maintain a set cantilever oscillation amplitude as the cantilever is scanned over the sample. A tapping AFM image is therefore produced by imaging the force of the intermittent contacts of the tip with the sample surface.

Although the peak forces applied during the contacting part of the oscillation can be much higher than typically used in contact mode, tapping mode generally lessens the damage done to the surface and the tip compared to the amount done in contact mode. This can be explained by the short duration of the applied force, and because the lateral forces between tip and sample are significantly lower in tapping mode over contact mode. Tapping mode imaging is gentle enough even for the visualization of supported lipid bilayers or adsorbed single polymer molecules (for instance, 0.4 nm thick chains of synthetic polyelectrolytes) under liquid medium. With proper scanning parameters, the conformation of single molecules can remain unchanged for hours, and even single molecular motors can be imaged while moving.

When operating in tapping mode, the phase of the cantilever's oscillation with respect to the driving signal can be recorded as well. This signal channel contains information about the energy dissipated by the cantilever in each oscillation cycle. Samples that contain regions of varying stiffness or with different adhesion properties can give a contrast in this channel that is not visible in the topographic image. Extracting the sample's material properties in a quantitative manner from phase images, however, is often not feasible.

Non-contact mode

In non-contact atomic force microscopy mode, the tip of the cantilever does not contact the sample surface. The cantilever is instead oscillated at either its resonant frequency (frequency modulation) or just above (amplitude modulation) where the amplitude of oscillation is typically a few nanometers (<10 nm) down to a few picometers. The van der Waals forces, which are strongest from 1 nm to 10 nm above the surface, or any other long-range force that extends above the surface acts to decrease the resonance frequency of the cantilever. This decrease in resonant frequency combined with the feedback loop system maintains a constant oscillation amplitude or frequency by adjusting the average tip-to-sample distance. Measuring the tip-to-sample distance at each (x,y) data point allows the scanning software to construct a topographic image of the sample surface.

Non-contact mode AFM does not suffer from tip or sample degradation effects that are sometimes observed after taking numerous scans with contact AFM. This makes non-contact AFM preferable to contact AFM for measuring soft samples, e.g. biological samples and organic thin film. In the case of rigid samples, contact and non-contact images may look the same. However, if a few monolayers of adsorbed fluid are lying on the surface of a rigid sample, the images may look quite different. An AFM operating in contact mode will penetrate the liquid layer to image the underlying surface, whereas in non-contact mode an AFM will oscillate above the adsorbed fluid layer to image both the liquid and surface.

Schemes for dynamic mode operation include frequency modulation where a phase-locked loop is used to track the cantilever's resonance frequency and the more common amplitude modulation with a servo loop in place to keep the cantilever excitation to a defined amplitude. In frequency modulation, changes in the oscillation frequency provide information about tip-sample interactions. Frequency can be measured with very high sensitivity and thus the frequency modulation mode allows for the use of very stiff cantilevers. Stiff cantilevers provide stability very close to the surface and, as a result, this technique was the first AFM technique to provide true atomic resolution in ultra-high vacuum conditions.

In amplitude modulation, changes in the oscillation amplitude or phase provide the feedback signal for imaging. In amplitude modulation, changes in the phase of oscillation can be used to discriminate between different types of materials on the surface. Amplitude modulation can be operated either in the non-contact or in the intermittent contact regime. In dynamic contact mode, the cantilever is oscillated such that the separation distance between the cantilever tip and the sample surface is modulated.

Amplitude modulation has also been used in the non-contact regime to image with atomic resolution by using very stiff cantilevers and small amplitudes in an ultra-high vacuum environment.

Topographic image

Image formation is a plotting method that produces a color mapping through changing the x–y position of the tip while scanning and recording the measured variable, i.e. the intensity of control signal, to each x–y coordinate. The color mapping shows the measured value corresponding to each coordinate. The image expresses the intensity of a value as a hue. Usually, the correspondence between the intensity of a value and a hue is shown as a color scale in the explanatory notes accompanying the image.

Operation mode of image forming of the AFM are generally classified into two groups from the viewpoint whether it uses z-Feedback loop (not shown) to maintain the tip-sample distance to keep signal intensity exported by the detector. The first one (using z-Feedback loop), said to be "constant XX mode" (XX is something which kept by z-Feedback loop).

Topographic image formation mode is based on abovementioned "constant XX mode", z-Feedback loop controls the relative distance between the probe and the sample through outputting control signals to keep constant one of frequency, vibration and phase which typically corresponds to the motion of cantilever (for instance, voltage is applied to the Z-piezoelectric element and it moves the sample up and down towards the Z direction.

Topographic image of FM-AFM

When the distance between the probe and the sample is brought to the range where atomic force may be detected, while a cantilever is excited in its natural eigenfrequency (f₀), the resonance frequency f of the cantilever may shift from its original resonance frequency. In other words, in the range where atomic force may be detected, a frequency shift (df =f–f₀) will also be observed. When the distance between the probe and the sample is in the non-contact region, the frequency shift increases in negative direction as the distance between the probe and the sample gets smaller.

When the sample has concavity and convexity, the distance between the tip-apex and the sample varies in accordance with the concavity and convexity accompanied with a scan of the sample along x–y direction (without height regulation in z-direction). As a result, the frequency shift arises. The image in which the values of the frequency obtained by a raster scan along the x–y direction of the sample surface are plotted against the x–y coordination of each measurement point is called a constant-height image.

On the other hand, the df may be kept constant by moving the probe upward and downward (See (3) of FIG.5) in z-direction using a negative feedback (by using z-feedback loop) while the raster scan of the sample surface along the x–y direction. The image in which the amounts of the negative feedback (the moving distance of the probe upward and downward in z-direction) are plotted against the x–y coordination of each measurement point is a topographic image. In other words, the topographic image is a trace of the tip of the probe regulated so that the df is constant and it may also be considered to be a plot of a constant-height surface of the df.

Therefore, the topographic image of the AFM is not the exact surface morphology itself, but actually the image influenced by the bond-order between the probe and the sample, however, the topographic image of the AFM is considered to reflect the geographical shape of the surface more than the topographic image of a scanning tunnel microscope.

Force spectroscopy

Besides imaging, AFM can be used for force spectroscopy, the direct measurement of tip-sample interaction forces as a function of the gap between the tip and sample. The result of this measurement is called a force-distance curve. For this method, the AFM tip is extended towards and retracted from the surface as the deflection of the cantilever is monitored as a function of piezoelectric displacement. These measurements have been used to measure nanoscale contacts, atomic bonding, Van der Waals forces, and Casimir forces, dissolution forces in liquids and single molecule stretching and rupture forces. AFM has also been used to measure, in an aqueous environment, the dispersion force due to polymer adsorbed on the substrate. Forces of the order of a few piconewtons can now be routinely measured with a vertical distance resolution of better than 0.1 nanometers. Force spectroscopy can be performed with either static or dynamic modes. In dynamic modes, information about the cantilever vibration is monitored in addition to the static deflection.

Problems with the technique include no direct measurement of the tip-sample separation and the common need for low-stiffness cantilevers, which tend to "snap" to the surface. These problems are not insurmountable. An AFM that directly measures the tip-sample separation has been developed. The snap-in can be reduced by measuring in liquids or by using stiffer cantilevers, but in the latter case a more sensitive deflection sensor is needed. By applying a small dither to the tip, the stiffness (force gradient) of the bond can be measured as well.

Biological applications and other

Force spectroscopy is used in biophysics to measure the mechanical properties of living material (such as tissue or cells) or detect structures of different stiffness buried into the bulk of the sample using the stiffness tomography. Another application was to measure the interaction forces between from one hand a material stuck on the tip of the cantilever, and from another hand the surface of particles either free or occupied by the same material. From the adhesion force distribution curve, a mean value of the forces has been derived. It allowed to make a cartography of the surface of the particles, covered or not by the material. AFM has also been used for mechanically unfolding proteins. In such experiments, the analyzes of the mean unfolding forces with the appropriate model leads to the obtainment of the information about the unfolding rate and free energy profile parameters of the protein.

Identification of individual surface atoms

The AFM can be used to image and manipulate atoms and structures on a variety of surfaces. The atom at the apex of the tip "senses" individual atoms on the underlying surface when it forms incipient chemical bonds with each atom. Because these chemical interactions subtly alter the tip's vibration frequency, they can be detected and mapped. This principle was used to distinguish between atoms of silicon, tin and lead on an alloy surface, by comparing these "atomic fingerprints'" with values obtained from density functional theory (DFT) simulations.

The trick is to first measure these forces precisely for each type of atom expected in the sample, and then to compare with forces given by DFT simulations. The team found that the tip interacted most strongly with silicon atoms, and interacted 24% and 41% less strongly with tin and lead atoms, respectively. Thus, each different type of atom can be identified in the matrix as the tip is moved across the surface.

Probe

An AFM probe has a sharp tip on the free-swinging end of a cantilever that protrudes from a holder. The dimensions of the cantilever are in the scale of micrometers. The radius of the tip is usually on the scale of a few nanometers to a few tens of nanometers. (Specialized probes exist with much larger end radii, for example probes for indentation of soft materials.) The cantilever holder, also called the holder chip—often 1.6 mm by 3.4 mm in size—allows the operator to hold the AFM cantilever/probe assembly with tweezers and fit it into the corresponding holder clips on the scanning head of the atomic force microscope.

This device is most commonly called an "AFM probe", but other names include "AFM tip" and "cantilever" (employing the name of a single part as the name of the whole device). An AFM probe is a particular type of SPM (scanning probe microscopy) probe.

AFM probes are manufactured with MEMS technology. Most AFM probes used are made from silicon (Si), but borosilicate glass and silicon nitride are also in use. AFM probes are considered consumables as they are often replaced when the tip apex becomes dull or contaminated or when the cantilever is broken. They can cost from a couple of tens of dollars up to hundreds of dollars per cantilever for the most specialized cantilever/probe combinations.

Just the tip is brought very close to the surface of the object under investigation, the cantilever is deflected by the interaction between the tip and the surface, which is what the AFM is designed to measure. A spatial map of the interaction can be made by measuring the deflection at many points on a 2D surface.

Several types of interaction can be detected. Depending on the interaction under investigation, the surface of the tip of the AFM probe needs to be modified with a coating. Among the coatings used are gold – for covalent bonding of biological molecules and the detection of their interaction with a surface, diamond for increased wear resistance and magnetic coatings for detecting the magnetic properties of the investigated surface. Another solution exists to achieve high resolution magnetic imaging : having the probe equip with a microSQUID. The AFM tips is fabricated using silicon micro machining and the precise positioning of the microSQUID loop is done by electron beam lithography. The additional attachment of a quantum dot to the tip apex of a conductive probe enables surface potential imaging with high lateral resolution, scanning quantum dot microscopy.

The surface of the cantilevers can also be modified. These coatings are mostly applied in order to increase the reflectance of the cantilever and to improve the deflection signal.

Forces as a function of tip geometry

The forces between the tip and the sample strongly depend on the geometry of the tip. Various studies were exploited in the past years to write the forces as a function of the tip parameters.

Among the different forces between the tip and the sample, the water meniscus forces are highly interesting, both in air and liquid environment. Other forces must be considered, like the Coulomb force, van der Waals forces, double layer interactions, solvation forces, hydration and hydrophobic forces.

Water meniscus

Water meniscus forces are highly interesting for AFM measurements in air. Due to the ambient humidity, a thin layer of water is formed between the tip and the sample during air measurements. The resulting capillary force gives rise to a strong attractive force that pulls the tip onto the surface. In fact, the adhesion force measured between tip and sample in ambient air of finite humidity is usually dominated by capillary forces. As a consequence, it is difficult to pull the tip away from the surface. For soft samples including many polymers and in particular biological materials, the strong adhesive capillary force gives rise to sample degradation and destruction upon imaging in contact mode. Historically, these problems were an important motivation for the development of dynamic imaging in air (e.g. "tapping mode"). During tapping mode imaging in air, capillary bridges still form. Yet, for suitable imaging conditions, the capillary bridges are formed and broken in every oscillation cycle of the cantilever normal to the surface, as can be inferred from an analysis of cantilever amplitude and phase vs. distance curves. As a consequence, destructive shear forces are largely reduced and soft samples can be investigated.

In order to quantify the equilibrium capillary force, it is necessary to start from the Laplace equation for pressure:

Model for AFM water meniscus

${\displaystyle P={\gamma }_L\left({\frac{1}{r}}_1+{\frac{1}{r}}_0\right)\simeq \frac{{\gamma }_L}{r_{eff}}}$

where γ_L, is the surface energy and r₀ and r₁ are defined in the figure.

The pressure is applied on an area of

${\displaystyle A\simeq 2\pi R\simeq [r_{eff}(1+\cos \theta )+h]}$

where θ is the angle between the tip's surface and the liquid's surface while h is the height difference between the surounding liquid and the top of the miniscus.

The force that pulls together the two surfaces is

${\displaystyle F=2\pi R{\gamma }_L\left(1+\cos \theta +\frac{h}{r_{eff}}\right)}$

The same formula could also be calculated as a function of relative humidity.

Gao calculated formulas for different tip geometries. As an example, the force decreases by 20% for a conical tip with respect to a spherical tip.

When these forces are calculated, a difference must be made between the wet on dry situation and the wet on wet situation.

For a spherical tip, the force is:

${\displaystyle f_m=-2\pi R{\gamma }_L(\cos \theta +\cos \varphi )\left(1-\frac{dh}{dD}\right)}$ for dry on wet,

${\displaystyle f_m=-2\pi R{\gamma }_L\frac{d{r}_0}{dD}}$for wet on wet,

where θ is the contact angle of the dry sphere and φ is the immersed angle, as shown in the figure.

For a conical tip, the formula becomes:

${\displaystyle f_m=-2\pi R{\gamma }_L\frac{\tan \delta }{\cos \delta }(\cos \theta +\sin \delta )(hD)\left(1-\frac{dh}{dD}\right)}$ for dry on wet

${\displaystyle f_m=-2\pi R{\gamma }_L\left(\frac{1}{\cos \delta }+\sin \delta \right)(r_0)\left(\frac{d{r}_0}{dD}\right)}$ for wet on wet

where δ is the half cone angle and r₀ and h are parameters of the meniscus profile.

AFM cantilever-deflection measurement

Beam-deflection measurement

AFM beam-deflection detection

The most common method for cantilever-deflection measurements is the beam-deflection method. In this method, laser light from a solid-state diode is reflected off the back of the cantilever and collected by a position-sensitive detector (PSD) consisting of two closely spaced photodiodes, whose output signal is collected by a differential amplifier. Angular displacement of the cantilever results in one photodiode collecting more light than the other photodiode, producing an output signal (the difference between the photodiode signals normalized by their sum), which is proportional to the deflection of the cantilever. The sensitivity of the beam-deflection method is very high, and a noise floor on the order of 10 fm Hz^−1⁄2 can be obtained routinely in a well-designed system. Although this method is sometimes called the "optical lever" method, the signal is not amplified if the beam path is made longer. A longer beam path increases the motion of the reflected spot on the photodiodes, but also widens the spot by the same amount due to diffraction, so that the same amount of optical power is moved from one photodiode to the other. The "optical leverage" (output signal of the detector divided by deflection of the cantilever) is inversely proportional to the numerical aperture of the beam focusing optics, as long as the focused laser spot is small enough to fall completely on the cantilever. It is also inversely proportional to the length of the cantilever.

The relative popularity of the beam-deflection method can be explained by its high sensitivity and simple operation, and by the fact that cantilevers do not require electrical contacts or other special treatments, and can therefore be fabricated relatively cheaply with sharp integrated tips.

Other deflection-measurement methods

Many other methods for beam-deflection measurements exist.

• Piezoelectric detection – Cantilevers made from quartz (such as the qPlus configuration), or other piezoelectric materials can directly detect deflection as an electrical signal. Cantilever oscillations down to 10pm have been detected with this method.
• Laser Doppler vibrometry – A laser Doppler vibrometer can be used to produce very accurate deflection measurements for an oscillating cantilever (thus is only used in non-contact mode). This method is expensive and is only used by relatively few groups.
• Scanning tunneling microscope (STM) — The first atomic microscope used an STM complete with its own feedback mechanism to measure deflection. This method is very difficult to implement, and is slow to react to deflection changes compared to modern methods.
• Optical interferometry – Optical interferometry can be used to measure cantilever deflection. Due to the nanometre scale deflections measured in AFM, the interferometer is running in the sub-fringe regime, thus, any drift in laser power or wavelength has strong effects on the measurement. For these reasons optical interferometer measurements must be done with great care (for example using index matching fluids between optical fibre junctions), with very stable lasers. For these reasons optical interferometry is rarely used.
• Capacitive detection – Metal coated cantilevers can form a capacitor with another contact located behind the cantilever. Deflection changes the distance between the contacts and can be measured as a change in capacitance.
• Piezoresistive detection – Cantilevers can be fabricated with piezoresistive elements that act as a strain gauge. Using a Wheatstone bridge, strain in the AFM cantilever due to deflection can be measured. This is not commonly used in vacuum applications, as the piezoresistive detection dissipates energy from the system affecting Q of the resonance.

Piezoelectric scanners

AFM scanners are made from piezoelectric material, which expands and contracts proportionally to an applied voltage. Whether they elongate or contract depends upon the polarity of the voltage applied. Traditionally the tip or sample is mounted on a "tripod" of three piezo crystals, with each responsible for scanning in the x,y and z directions. In 1986, the same year as the AFM was invented, a new piezoelectric scanner, the tube scanner, was developed for use in STM. Later tube scanners were incorporated into AFMs. The tube scanner can move the sample in the x, y, and z directions using a single tube piezo with a single interior contact and four external contacts. An advantage of the tube scanner compared to the original tripod design, is better vibrational isolation, resulting from the higher resonant frequency of the single element construction, in combination with a low resonant frequency isolation stage. A disadvantage is that the x-y motion can cause unwanted z motion resulting in distortion. Another popular design for AFM scanners is the flexure stage, which uses separate piezos for each axis, and couples them through a flexure mechanism.

Scanners are characterized by their sensitivity, which is the ratio of piezo movement to piezo voltage, i.e., by how much the piezo material extends or contracts per applied volt. Due to the differences in material or size, the sensitivity varies from scanner to scanner. Sensitivity varies non-linearly with respect to scan size. Piezo scanners exhibit more sensitivity at the end than at the beginning of a scan. This causes the forward and reverse scans to behave differently and display hysteresis between the two scan directions. This can be corrected by applying a non-linear voltage to the piezo electrodes to cause linear scanner movement and calibrating the scanner accordingly. One disadvantage of this approach is that it requires re-calibration because the precise non-linear voltage needed to correct non-linear movement will change as the piezo ages (see below). This problem can be circumvented by adding a linear sensor to the sample stage or piezo stage to detect the true movement of the piezo. Deviations from ideal movement can be detected by the sensor and corrections applied to the piezo drive signal to correct for non-linear piezo movement. This design is known as a "closed loop" AFM. Non-sensored piezo AFMs are referred to as "open loop" AFMs.

The sensitivity of piezoelectric materials decreases exponentially with time. This causes most of the change in sensitivity to occur in the initial stages of the scanner's life. Piezoelectric scanners are run for approximately 48 hours before they are shipped from the factory so that they are past the point where they may have large changes in sensitivity. As the scanner ages, the sensitivity will change less with time and the scanner would seldom require recalibration, though various manufacturer manuals recommend monthly to semi-monthly calibration of open loop AFMs.

Advantages and disadvantages

The first atomic force microscope

Advantages

AFM has several advantages over the scanning electron microscope (SEM). Unlike the electron microscope, which provides a two-dimensional projection or a two-dimensional image of a sample, the AFM provides a three-dimensional surface profile. In addition, samples viewed by AFM do not require any special treatments (such as metal/carbon coatings) that would irreversibly change or damage the sample, and does not typically suffer from charging artifacts in the final image. While an electron microscope needs an expensive vacuum environment for proper operation, most AFM modes can work perfectly well in ambient air or even a liquid environment. This makes it possible to study biological macromolecules and even living organisms. In principle, AFM can provide higher resolution than SEM. It has been shown to give true atomic resolution in ultra-high vacuum (UHV) and, more recently, in liquid environments. High resolution AFM is comparable in resolution to scanning tunneling microscopy and transmission electron microscopy. AFM can also be combined with a variety of optical microscopy and spectroscopy techniques such as fluorescent microscopy of infrared spectroscopy, giving rise to scanning near-field optical microscopy, nano-FTIR and further expanding its applicability. Combined AFM-optical instruments have been applied primarily in the biological sciences but have recently attracted strong interest in photovoltaics and energy-storage research, polymer sciences, nanotechnology and even medical research.

Disadvantages

A disadvantage of AFM compared with the scanning electron microscope (SEM) is the single scan image size. In one pass, the SEM can image an area on the order of square millimeters with a depth of field on the order of millimeters, whereas the AFM can only image a maximum scanning area of about 150×150 micrometers and a maximum height on the order of 10–20 micrometers. One method of improving the scanned area size for AFM is by using parallel probes in a fashion similar to that of millipede data storage.

The scanning speed of an AFM is also a limitation. Traditionally, an AFM cannot scan images as fast as an SEM, requiring several minutes for a typical scan, while an SEM is capable of scanning at near real-time, although at relatively low quality. The relatively slow rate of scanning during AFM imaging often leads to thermal drift in the image making the AFM less suited for measuring accurate distances between topographical features on the image. However, several fast-acting designs were suggested to increase microscope scanning productivity including what is being termed videoAFM (reasonable quality images are being obtained with videoAFM at video rate: faster than the average SEM). To eliminate image distortions induced by thermal drift, several methods have been introduced.

Showing an AFM artifact arising from a tip with a high radius of curvature with respect to the feature that is to be visualized

AFM artifact, steep sample topography

AFM images can also be affected by nonlinearity, hysteresis, and creep of the piezoelectric material and cross-talk between the x, y, z axes that may require software enhancement and filtering. Such filtering could "flatten" out real topographical features. However, newer AFMs utilize real-time correction software (for example, feature-oriented scanning) or closed-loop scanners, which practically eliminate these problems. Some AFMs also use separated orthogonal scanners (as opposed to a single tube), which also serve to eliminate part of the cross-talk problems.

As with any other imaging technique, there is the possibility of image artifacts, which could be induced by an unsuitable tip, a poor operating environment, or even by the sample itself, as depicted on the right. These image artifacts are unavoidable; however, their occurrence and effect on results can be reduced through various methods. Artifacts resulting from a too-coarse tip can be caused for example by inappropriate handling or de facto collisions with the sample by either scanning too fast or having an unreasonably rough surface, causing actual wearing of the tip.

Due to the nature of AFM probes, they cannot normally measure steep walls or overhangs. Specially made cantilevers and AFMs can be used to modulate the probe sideways as well as up and down (as with dynamic contact and non-contact modes) to measure sidewalls, at the cost of more expensive cantilevers, lower lateral resolution and additional artifacts.

Other applications in various fields of study

AFM image of part of a Golgi apparatus isolated from HeLa cells

The latest efforts in integrating nanotechnology and biological research have been successful and show much promise for the future, including in fields such as nanobiomechanics. Since nanoparticles are a potential vehicle of drug delivery, the biological responses of cells to these nanoparticles are continuously being explored to optimize their efficacy and how their design could be improved. Pyrgiotakis et al. were able to study the interaction between CeO₂ and Fe₂O₃ engineered nanoparticles and cells by attaching the engineered nanoparticles to the AFM tip. Studies have taken advantage of AFM to obtain further information on the behavior of live cells in biological media. Real-time atomic force spectroscopy (or nanoscopy) and dynamic atomic force spectroscopy have been used to study live cells and membrane proteins and their dynamic behavior at high resolution, on the nanoscale. Imaging and obtaining information on the topography and the properties of the cells has also given insight into chemical processes and mechanisms that occur through cell-cell interaction and interactions with other signaling molecules (ex. ligands). Evans and Calderwood used single cell force microscopy to study cell adhesion forces, bond kinetics/dynamic bond strength and its role in chemical processes such as cell signaling. Scheuring, Lévy, and Rigaud reviewed studies in which AFM to explore the crystal structure of membrane proteins of photosynthetic bacteria. Alsteen et al. have used AFM-based nanoscopy to perform a real-time analysis of the interaction between live mycobacteria and antimycobacterial drugs (specifically isoniazid, ethionamide, ethambutol, and streptomycine), which serves as an example of the more in-depth analysis of pathogen-drug interactions that can be done through AFM.

Genetic algorithm

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Genetic_algorithm

The 2006 NASA ST5 spacecraft antenna. This complicated shape was found by an evolutionary computer design program to create the best radiation pattern. It is known as an evolved antenna.

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection. Some examples of GA applications include optimizing decision trees for better performance, solving sudoku puzzles,^[2] hyperparameter optimization, causal inference, etc.

Methodology

Optimization problems

In a genetic algorithm, a population of candidate solutions (called individuals, creatures, organisms, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotype) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.

The evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated; the fitness is usually the value of the objective function in the optimization problem being solved. The more fit individuals are stochastically selected from the current population, and each individual's genome is modified (recombined and possibly randomly mutated) to form a new generation. The new generation of candidate solutions is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.

A typical genetic algorithm requires:

1. a genetic representation of the solution domain,
2. a fitness function to evaluate the solution domain.

A standard representation of each candidate solution is as an array of bits (also called bit set or bit string). Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple crossover operations. Variable length representations may also be used, but crossover implementation is more complex in this case. Tree-like representations are explored in genetic programming and graph-form representations are explored in evolutionary programming; a mix of both linear chromosomes and trees is explored in gene expression programming.

Once the genetic representation and the fitness function are defined, a GA proceeds to initialize a population of solutions and then to improve it through repetitive application of the mutation, crossover, inversion and selection operators.

Initialization

The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Often, the initial population is generated randomly, allowing the entire range of possible solutions (the search space). Occasionally, the solutions may be "seeded" in areas where optimal solutions are likely to be found.

Selection

Main article: Selection (genetic algorithm)

During each successive generation, a portion of the existing population is selected to reproduce for a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected. Certain selection methods rate the fitness of each solution and preferentially select the best solutions. Other methods rate only a random sample of the population, as the former process may be very time-consuming.

The fitness function is defined over the genetic representation and measures the quality of the represented solution. The fitness function is always problem dependent. For instance, in the knapsack problem one wants to maximize the total value of objects that can be put in a knapsack of some fixed capacity. A representation of a solution might be an array of bits, where each bit represents a different object, and the value of the bit (0 or 1) represents whether or not the object is in the knapsack. Not every such representation is valid, as the size of objects may exceed the capacity of the knapsack. The fitness of the solution is the sum of values of all objects in the knapsack if the representation is valid, or 0 otherwise.

In some problems, it is hard or even impossible to define the fitness expression; in these cases, a simulation may be used to determine the fitness function value of a phenotype (e.g. computational fluid dynamics is used to determine the air resistance of a vehicle whose shape is encoded as the phenotype), or even interactive genetic algorithms are used.

Genetic operators

Main articles: Crossover (genetic algorithm) and Mutation (genetic algorithm)

The next step is to generate a second generation population of solutions from those selected, through a combination of genetic operators: crossover (also called recombination), and mutation.

For each new solution to be produced, a pair of "parent" solutions is selected for breeding from the pool selected previously. By producing a "child" solution using the above methods of crossover and mutation, a new solution is created which typically shares many of the characteristics of its "parents". New parents are selected for each new child, and the process continues until a new population of solutions of appropriate size is generated. Although reproduction methods that are based on the use of two parents are more "biology inspired", some research suggests that more than two "parents" generate higher quality chromosomes.

These processes ultimately result in the next generation population of chromosomes that is different from the initial generation. Generally, the average fitness will have increased by this procedure for the population, since only the best organisms from the first generation are selected for breeding, along with a small proportion of less fit solutions. These less fit solutions ensure genetic diversity within the genetic pool of the parents and therefore ensure the genetic diversity of the subsequent generation of children.

Opinion is divided over the importance of crossover versus mutation. There are many references in Fogel (2006) that support the importance of mutation-based search.

Although crossover and mutation are known as the main genetic operators, it is possible to use other operators such as regrouping, colonization-extinction, or migration in genetic algorithms.^{[citation needed]}

It is worth tuning parameters such as the mutation probability, crossover probability and population size to find reasonable settings for the problem class being worked on. A very small mutation rate may lead to genetic drift (which is non-ergodic in nature). A recombination rate that is too high may lead to premature convergence of the genetic algorithm. A mutation rate that is too high may lead to loss of good solutions, unless elitist selection is employed. An adequate population size ensures sufficient genetic diversity for the problem at hand, but can lead to a waste of computational resources if set to a value larger than required.

Heuristics

In addition to the main operators above, other heuristics may be employed to make the calculation faster or more robust. The speciation heuristic penalizes crossover between candidate solutions that are too similar; this encourages population diversity and helps prevent premature convergence to a less optimal solution.

Termination

This generational process is repeated until a termination condition has been reached. Common terminating conditions are:

• A solution is found that satisfies minimum criteria
• Fixed number of generations reached
• Allocated budget (computation time/money) reached
• The highest ranking solution's fitness is reaching or has reached a plateau such that successive iterations no longer produce better results
• Manual inspection
• Combinations of the above

The building block hypothesis

Genetic algorithms are simple to implement, but their behavior is difficult to understand. In particular, it is difficult to understand why these algorithms frequently succeed at generating solutions of high fitness when applied to practical problems. The building block hypothesis (BBH) consists of:

1. A description of a heuristic that performs adaptation by identifying and recombining "building blocks", i.e. low order, low defining-length schemata with above average fitness.
2. A hypothesis that a genetic algorithm performs adaptation by implicitly and efficiently implementing this heuristic.

Goldberg describes the heuristic as follows:

"Short, low order, and highly fit schemata are sampled, recombined [crossed over], and resampled to form strings of potentially higher fitness. In a way, by working with these particular schemata [the building blocks], we have reduced the complexity of our problem; instead of building high-performance strings by trying every conceivable combination, we construct better and better strings from the best partial solutions of past samplings.

"Because highly fit schemata of low defining length and low order play such an important role in the action of genetic algorithms, we have already given them a special name: building blocks. Just as a child creates magnificent fortresses through the arrangement of simple blocks of wood, so does a genetic algorithm seek near optimal performance through the juxtaposition of short, low-order, high-performance schemata, or building blocks."

Despite the lack of consensus regarding the validity of the building-block hypothesis, it has been consistently evaluated and used as reference throughout the years. Many estimation of distribution algorithms, for example, have been proposed in an attempt to provide an environment in which the hypothesis would hold. Although good results have been reported for some classes of problems, skepticism concerning the generality and/or practicality of the building-block hypothesis as an explanation for GAs' efficiency still remains. Indeed, there is a reasonable amount of work that attempts to understand its limitations from the perspective of estimation of distribution algorithms.

Limitations

There are limitations of the use of a genetic algorithm compared to alternative optimization algorithms:

• Repeated fitness function evaluation for complex problems is often the most prohibitive and limiting segment of artificial evolutionary algorithms. Finding the optimal solution to complex high-dimensional, multimodal problems often requires very expensive fitness function evaluations. In real world problems such as structural optimization problems, a single function evaluation may require several hours to several days of complete simulation. Typical optimization methods cannot deal with such types of problem. In this case, it may be necessary to forgo an exact evaluation and use an approximated fitness that is computationally efficient. It is apparent that amalgamation of approximate models may be one of the most promising approaches to convincingly use GA to solve complex real life problems.
• Genetic algorithms do not scale well with complexity. That is, where the number of elements which are exposed to mutation is large there is often an exponential increase in search space size. This makes it extremely difficult to use the technique on problems such as designing an engine, a house or a plane. In order to make such problems tractable to evolutionary search, they must be broken down into the simplest representation possible. Hence we typically see evolutionary algorithms encoding designs for fan blades instead of engines, building shapes instead of detailed construction plans, and airfoils instead of whole aircraft designs. The second problem of complexity is the issue of how to protect parts that have evolved to represent good solutions from further destructive mutation, particularly when their fitness assessment requires them to combine well with other parts.
• The "better" solution is only in comparison to other solutions. As a result, the stopping criterion is not clear in every problem.
• In many problems, GAs have a tendency to converge towards local optima or even arbitrary points rather than the global optimum of the problem. This means that it does not "know how" to sacrifice short-term fitness to gain longer-term fitness. The likelihood of this occurring depends on the shape of the fitness landscape: certain problems may provide an easy ascent towards a global optimum, others may make it easier for the function to find the local optima. This problem may be alleviated by using a different fitness function, increasing the rate of mutation, or by using selection techniques that maintain a diverse population of solutions, although the No Free Lunch theorem proves that there is no general solution to this problem. A common technique to maintain diversity is to impose a "niche penalty", wherein, any group of individuals of sufficient similarity (niche radius) have a penalty added, which will reduce the representation of that group in subsequent generations, permitting other (less similar) individuals to be maintained in the population. This trick, however, may not be effective, depending on the landscape of the problem. Another possible technique would be to simply replace part of the population with randomly generated individuals, when most of the population is too similar to each other. Diversity is important in genetic algorithms (and genetic programming) because crossing over a homogeneous population does not yield new solutions. In evolution strategies and evolutionary programming, diversity is not essential because of a greater reliance on mutation.
• Operating on dynamic data sets is difficult, as genomes begin to converge early on towards solutions which may no longer be valid for later data. Several methods have been proposed to remedy this by increasing genetic diversity somehow and preventing early convergence, either by increasing the probability of mutation when the solution quality drops (called triggered hypermutation), or by occasionally introducing entirely new, randomly generated elements into the gene pool (called random immigrants). Again, evolution strategies and evolutionary programming can be implemented with a so-called "comma strategy" in which parents are not maintained and new parents are selected only from offspring. This can be more effective on dynamic problems.
• GAs cannot effectively solve problems in which the only fitness measure is a single right/wrong measure (like decision problems), as there is no way to converge on the solution (no hill to climb). In these cases, a random search may find a solution as quickly as a GA. However, if the situation allows the success/failure trial to be repeated giving (possibly) different results, then the ratio of successes to failures provides a suitable fitness measure.
• For specific optimization problems and problem instances, other optimization algorithms may be more efficient than genetic algorithms in terms of speed of convergence. Alternative and complementary algorithms include evolution strategies, evolutionary programming, simulated annealing, Gaussian adaptation, hill climbing, and swarm intelligence (e.g.: ant colony optimization, particle swarm optimization) and methods based on integer linear programming. The suitability of genetic algorithms is dependent on the amount of knowledge of the problem; well known problems often have better, more specialized approaches.

Variants

Chromosome representation

Main article: genetic representation

The simplest algorithm represents each chromosome as a bit string. Typically, numeric parameters can be represented by integers, though it is possible to use floating point representations. The floating point representation is natural to evolution strategies and evolutionary programming. The notion of real-valued genetic algorithms has been offered but is really a misnomer because it does not really represent the building block theory that was proposed by John Henry Holland in the 1970s. This theory is not without support though, based on theoretical and experimental results (see below). The basic algorithm performs crossover and mutation at the bit level. Other variants treat the chromosome as a list of numbers which are indexes into an instruction table, nodes in a linked list, hashes, objects, or any other imaginable data structure. Crossover and mutation are performed so as to respect data element boundaries. For most data types, specific variation operators can be designed. Different chromosomal data types seem to work better or worse for different specific problem domains.

When bit-string representations of integers are used, Gray coding is often employed. In this way, small changes in the integer can be readily affected through mutations or crossovers. This has been found to help prevent premature convergence at so-called Hamming walls, in which too many simultaneous mutations (or crossover events) must occur in order to change the chromosome to a better solution.

Other approaches involve using arrays of real-valued numbers instead of bit strings to represent chromosomes. Results from the theory of schemata suggest that in general the smaller the alphabet, the better the performance, but it was initially surprising to researchers that good results were obtained from using real-valued chromosomes. This was explained as the set of real values in a finite population of chromosomes as forming a virtual alphabet (when selection and recombination are dominant) with a much lower cardinality than would be expected from a floating point representation.

An expansion of the Genetic Algorithm accessible problem domain can be obtained through more complex encoding of the solution pools by concatenating several types of heterogenously encoded genes into one chromosome. This particular approach allows for solving optimization problems that require vastly disparate definition domains for the problem parameters. For instance, in problems of cascaded controller tuning, the internal loop controller structure can belong to a conventional regulator of three parameters, whereas the external loop could implement a linguistic controller (such as a fuzzy system) which has an inherently different description. This particular form of encoding requires a specialized crossover mechanism that recombines the chromosome by section, and it is a useful tool for the modelling and simulation of complex adaptive systems, especially evolution processes.

Elitism

A practical variant of the general process of constructing a new population is to allow the best organism(s) from the current generation to carry over to the next, unaltered. This strategy is known as elitist selection and guarantees that the solution quality obtained by the GA will not decrease from one generation to the next.

Parallel implementations

Parallel implementations of genetic algorithms come in two flavors. Coarse-grained parallel genetic algorithms assume a population on each of the computer nodes and migration of individuals among the nodes. Fine-grained parallel genetic algorithms assume an individual on each processor node which acts with neighboring individuals for selection and reproduction. Other variants, like genetic algorithms for online optimization problems, introduce time-dependence or noise in the fitness function.

Adaptive GAs

Genetic algorithms with adaptive parameters (adaptive genetic algorithms, AGAs) is another significant and promising variant of genetic algorithms. The probabilities of crossover (pc) and mutation (pm) greatly determine the degree of solution accuracy and the convergence speed that genetic algorithms can obtain. Researchers have analyzed GA convergence analytically.

Instead of using fixed values of pc and pm, AGAs utilize the population information in each generation and adaptively adjust the pc and pm in order to maintain the population diversity as well as to sustain the convergence capacity. In AGA (adaptive genetic algorithm), the adjustment of pc and pm depends on the fitness values of the solutions. There are more examples of AGA variants: Successive zooming method is an early example of improving convergence. In CAGA (clustering-based adaptive genetic algorithm), through the use of clustering analysis to judge the optimization states of the population, the adjustment of pc and pm depends on these optimization states. Recent approaches use more abstract variables for deciding pc and pm. Examples are dominance & co-dominance principles and LIGA (levelized interpolative genetic algorithm), which combines a flexible GA with modified A* search to tackle search space anisotropicity.

It can be quite effective to combine GA with other optimization methods. A GA tends to be quite good at finding generally good global solutions, but quite inefficient at finding the last few mutations to find the absolute optimum. Other techniques (such as simple hill climbing) are quite efficient at finding absolute optimum in a limited region. Alternating GA and hill climbing can improve the efficiency of GA while overcoming the lack of robustness of hill climbing.

This means that the rules of genetic variation may have a different meaning in the natural case. For instance – provided that steps are stored in consecutive order – crossing over may sum a number of steps from maternal DNA adding a number of steps from paternal DNA and so on. This is like adding vectors that more probably may follow a ridge in the phenotypic landscape. Thus, the efficiency of the process may be increased by many orders of magnitude. Moreover, the inversion operator has the opportunity to place steps in consecutive order or any other suitable order in favour of survival or efficiency.

A variation, where the population as a whole is evolved rather than its individual members, is known as gene pool recombination.

A number of variations have been developed to attempt to improve performance of GAs on problems with a high degree of fitness epistasis, i.e. where the fitness of a solution consists of interacting subsets of its variables. Such algorithms aim to learn (before exploiting) these beneficial phenotypic interactions. As such, they are aligned with the Building Block Hypothesis in adaptively reducing disruptive recombination. Prominent examples of this approach include the mGA, GEMGA and LLGA.

Problem domains

Problems which appear to be particularly appropriate for solution by genetic algorithms include timetabling and scheduling problems, and many scheduling software packages are based on GAs. GAs have also been applied to engineering. Genetic algorithms are often applied as an approach to solve global optimization problems.

As a general rule of thumb genetic algorithms might be useful in problem domains that have a complex fitness landscape as mixing, i.e., mutation in combination with crossover, is designed to move the population away from local optima that a traditional hill climbing algorithm might get stuck in. Observe that commonly used crossover operators cannot change any uniform population. Mutation alone can provide ergodicity of the overall genetic algorithm process (seen as a Markov chain).

Examples of problems solved by genetic algorithms include: mirrors designed to funnel sunlight to a solar collector, antennae designed to pick up radio signals in space, walking methods for computer figures, optimal design of aerodynamic bodies in complex flowfields

In his Algorithm Design Manual, Skiena advises against genetic algorithms for any task:

[I]t is quite unnatural to model applications in terms of genetic operators like mutation and crossover on bit strings. The pseudobiology adds another level of complexity between you and your problem. Second, genetic algorithms take a very long time on nontrivial problems. [...] [T]he analogy with evolution—where significant progress require [sic] millions of years—can be quite appropriate.

[...]

I have never encountered any problem where genetic algorithms seemed to me the right way to attack it. Further, I have never seen any computational results reported using genetic algorithms that have favorably impressed me. Stick to simulated annealing for your heuristic search voodoo needs.

— Steven Skiena

History

In 1950, Alan Turing proposed a "learning machine" which would parallel the principles of evolution. Computer simulation of evolution started as early as in 1954 with the work of Nils Aall Barricelli, who was using the computer at the Institute for Advanced Study in Princeton, New Jersey. His 1954 publication was not widely noticed. Starting in 1957, the Australian quantitative geneticist Alex Fraser published a series of papers on simulation of artificial selection of organisms with multiple loci controlling a measurable trait. From these beginnings, computer simulation of evolution by biologists became more common in the early 1960s, and the methods were described in books by Fraser and Burnell (1970) and Crosby (1973). Fraser's simulations included all of the essential elements of modern genetic algorithms. In addition, Hans-Joachim Bremermann published a series of papers in the 1960s that also adopted a population of solution to optimization problems, undergoing recombination, mutation, and selection. Bremermann's research also included the elements of modern genetic algorithms. Other noteworthy early pioneers include Richard Friedberg, George Friedman, and Michael Conrad. Many early papers are reprinted by Fogel (1998).

Although Barricelli, in work he reported in 1963, had simulated the evolution of ability to play a simple game, artificial evolution only became a widely recognized optimization method as a result of the work of Ingo Rechenberg and Hans-Paul Schwefel in the 1960s and early 1970s – Rechenberg's group was able to solve complex engineering problems through evolution strategies. Another approach was the evolutionary programming technique of Lawrence J. Fogel, which was proposed for generating artificial intelligence. Evolutionary programming originally used finite state machines for predicting environments, and used variation and selection to optimize the predictive logics. Genetic algorithms in particular became popular through the work of John Holland in the early 1970s, and particularly his book Adaptation in Natural and Artificial Systems (1975). His work originated with studies of cellular automata, conducted by Holland and his students at the University of Michigan. Holland introduced a formalized framework for predicting the quality of the next generation, known as Holland's Schema Theorem. Research in GAs remained largely theoretical until the mid-1980s, when The First International Conference on Genetic Algorithms was held in Pittsburgh, Pennsylvania.

Commercial products

In the late 1980s, General Electric started selling the world's first genetic algorithm product, a mainframe-based toolkit designed for industrial processes. In 1989, Axcelis, Inc. released Evolver, the world's first commercial GA product for desktop computers. The New York Times technology writer John Markoff wrote about Evolver in 1990, and it remained the only interactive commercial genetic algorithm until 1995. Evolver was sold to Palisade in 1997, translated into several languages, and is currently in its 6th version. Since the 1990s, MATLAB has built in three derivative-free optimization heuristic algorithms (simulated annealing, particle swarm optimization, genetic algorithm) and two direct search algorithms (simplex search, pattern search).

Related techniques

See also: List of genetic algorithm applications

Parent fields

Genetic algorithms are a sub-field:

• Evolutionary algorithms
• Evolutionary computing
• Metaheuristics
• Stochastic optimization
• Optimization

Related fields

Evolutionary algorithms

Main article: Evolutionary algorithm

Evolutionary algorithms is a sub-field of evolutionary computing.

• Evolution strategies (ES, see Rechenberg, 1994) evolve individuals by means of mutation and intermediate or discrete recombination. ES algorithms are designed particularly to solve problems in the real-value domain. They use self-adaptation to adjust control parameters of the search. De-randomization of self-adaptation has led to the contemporary Covariance Matrix Adaptation Evolution Strategy (CMA-ES).
• Evolutionary programming (EP) involves populations of solutions with primarily mutation and selection and arbitrary representations. They use self-adaptation to adjust parameters, and can include other variation operations such as combining information from multiple parents.
• Estimation of Distribution Algorithm (EDA) substitutes traditional reproduction operators by model-guided operators. Such models are learned from the population by employing machine learning techniques and represented as Probabilistic Graphical Models, from which new solutions can be sampled or generated from guided-crossover.
• Genetic programming (GP) is a related technique popularized by John Koza in which computer programs, rather than function parameters, are optimized. Genetic programming often uses tree-based internal data structures to represent the computer programs for adaptation instead of the list structures typical of genetic algorithms. There are many variants of Genetic Programming, including Cartesian genetic programming, Gene expression programming, grammatical evolution, Linear genetic programming, Multi expression programming etc.
• Grouping genetic algorithm (GGA) is an evolution of the GA where the focus is shifted from individual items, like in classical GAs, to groups or subset of items. The idea behind this GA evolution proposed by Emanuel Falkenauer is that solving some complex problems, a.k.a. clustering or partitioning problems where a set of items must be split into disjoint group of items in an optimal way, would better be achieved by making characteristics of the groups of items equivalent to genes. These kind of problems include bin packing, line balancing, clustering with respect to a distance measure, equal piles, etc., on which classic GAs proved to perform poorly. Making genes equivalent to groups implies chromosomes that are in general of variable length, and special genetic operators that manipulate whole groups of items. For bin packing in particular, a GGA hybridized with the Dominance Criterion of Martello and Toth, is arguably the best technique to date.
• Interactive evolutionary algorithms are evolutionary algorithms that use human evaluation. They are usually applied to domains where it is hard to design a computational fitness function, for example, evolving images, music, artistic designs and forms to fit users' aesthetic preference.

Swarm intelligence

Main article: Swarm intelligence

Swarm intelligence is a sub-field of evolutionary computing.

• Ant colony optimization (ACO) uses many ants (or agents) equipped with a pheromone model to traverse the solution space and find locally productive areas.
• Although considered an Estimation of distribution algorithm, Particle swarm optimization (PSO) is a computational method for multi-parameter optimization which also uses population-based approach. A population (swarm) of candidate solutions (particles) moves in the search space, and the movement of the particles is influenced both by their own best known position and swarm's global best known position. Like genetic algorithms, the PSO method depends on information sharing among population members. In some problems the PSO is often more computationally efficient than the GAs, especially in unconstrained problems with continuous variables.

Other evolutionary computing algorithms

Evolutionary computation is a sub-field of the metaheuristic methods.

• Memetic algorithm (MA), often called hybrid genetic algorithm among others, is a population-based method in which solutions are also subject to local improvement phases. The idea of memetic algorithms comes from memes, which unlike genes, can adapt themselves. In some problem areas they are shown to be more efficient than traditional evolutionary algorithms.
• Bacteriologic algorithms (BA) inspired by evolutionary ecology and, more particularly, bacteriologic adaptation. Evolutionary ecology is the study of living organisms in the context of their environment, with the aim of discovering how they adapt. Its basic concept is that in a heterogeneous environment, there is not one individual that fits the whole environment. So, one needs to reason at the population level. It is also believed BAs could be successfully applied to complex positioning problems (antennas for cell phones, urban planning, and so on) or data mining.
• Cultural algorithm (CA) consists of the population component almost identical to that of the genetic algorithm and, in addition, a knowledge component called the belief space.
• Differential evolution (DE) inspired by migration of superorganisms.
• Gaussian adaptation (normal or natural adaptation, abbreviated NA to avoid confusion with GA) is intended for the maximisation of manufacturing yield of signal processing systems. It may also be used for ordinary parametric optimisation. It relies on a certain theorem valid for all regions of acceptability and all Gaussian distributions. The efficiency of NA relies on information theory and a certain theorem of efficiency. Its efficiency is defined as information divided by the work needed to get the information. Because NA maximises mean fitness rather than the fitness of the individual, the landscape is smoothed such that valleys between peaks may disappear. Therefore it has a certain "ambition" to avoid local peaks in the fitness landscape. NA is also good at climbing sharp crests by adaptation of the moment matrix, because NA may maximise the disorder (average information) of the Gaussian simultaneously keeping the mean fitness constant.

Other metaheuristic methods

Metaheuristic methods broadly fall within stochastic optimisation methods.

• Simulated annealing (SA) is a related global optimization technique that traverses the search space by testing random mutations on an individual solution. A mutation that increases fitness is always accepted. A mutation that lowers fitness is accepted probabilistically based on the difference in fitness and a decreasing temperature parameter. In SA parlance, one speaks of seeking the lowest energy instead of the maximum fitness. SA can also be used within a standard GA algorithm by starting with a relatively high rate of mutation and decreasing it over time along a given schedule.
• Tabu search (TS) is similar to simulated annealing in that both traverse the solution space by testing mutations of an individual solution. While simulated annealing generates only one mutated solution, tabu search generates many mutated solutions and moves to the solution with the lowest energy of those generated. In order to prevent cycling and encourage greater movement through the solution space, a tabu list is maintained of partial or complete solutions. It is forbidden to move to a solution that contains elements of the tabu list, which is updated as the solution traverses the solution space.
• Extremal optimization (EO) Unlike GAs, which work with a population of candidate solutions, EO evolves a single solution and makes local modifications to the worst components. This requires that a suitable representation be selected which permits individual solution components to be assigned a quality measure ("fitness"). The governing principle behind this algorithm is that of emergent improvement through selectively removing low-quality components and replacing them with a randomly selected component. This is decidedly at odds with a GA that selects good solutions in an attempt to make better solutions.

Other stochastic optimisation methods

• The cross-entropy (CE) method generates candidate solutions via a parameterized probability distribution. The parameters are updated via cross-entropy minimization, so as to generate better samples in the next iteration.
• Reactive search optimization (RSO) advocates the integration of sub-symbolic machine learning techniques into search heuristics for solving complex optimization problems. The word reactive hints at a ready response to events during the search through an internal online feedback loop for the self-tuning of critical parameters. Methodologies of interest for Reactive Search include machine learning and statistics, in particular reinforcement learning, active or query learning, neural networks, and metaheuristics.