Optimization Method based on Genetic Algorithms
| Scientific Paper | |
|---|---|
| Title | Optimization Method based on Genetic Algorithms |
| Read in full | Link to paper |
| Author(s) | Jose Luis Lopez-Bonilla |
| Keywords | Electromagnetic Optimization, Genetic Algorithm. |
| Published | 2005 |
| Journal | Apeiron |
| Volume | 12 |
| Number | 4 |
| No. of pages | 16 |
Read the full paper here
Abstract
The design of electromagnetic systems using methods of optimization have been carried out with deterministic methods. However, these methods are not efficient, because the object functions obtained from electromagnetic optimization problems are often highly non-linear, stiff, multiextreme and non-differential. The lack of a single method available to deal with multidimensional problems, including those with several goals to optimize, has generated the need to use numerical processes for optimization. This paper presents a method of global optimization based on genetic algorithms. The Genetic Algorithms are a versatile tool, which can be applied as a global optimization method to problems of electromagnetic engineering, because they are easy to implement to non-differentiable functions and discrete search spaces. It is also shown how, in some cases, genetic algorithms have been applied with success in electromagnetic problems, such as antenna design, far-field prediction, absorber coatings design, etc.
Overview
This paper, published in Apeiron in October 2005, is unusual among the material archived on this wiki in that it makes no claim about the foundations of physics at all. It is a methodological review, written by A. Rangel-Merino, J. L. López-Bonilla and R. Linares y Miranda of the Instituto Politécnico Nacional in Mexico City, arguing that genetic algorithms are the appropriate global-optimization tool for the design problems that arise in electromagnetic engineering. It is worth noting for the wiki record that López-Bonilla, who appears here as second author, publishes across a very wide range — from Petrov classification and Weyl-tensor invariants to numerical methods of exactly this kind — and this paper belongs firmly to the applied-engineering end of that range.
The argument is a negative one turned positive. Calculus-based optimization, the paper says, is either direct (climbing the local gradient) or indirect (setting the gradient to zero and solving the resulting nonlinear system), and both "lack robustness for two main reasons": they are local, seeking maxima only in the neighbourhood of the analysed point, and they depend on the existence of derivatives. Enumerative schemes avoid the derivative requirement but fail in large or high-dimensional spaces. Since real electromagnetic object functions are "highly non-linear, stiff, multi-extreme and non-differential", and since design variables are typically discrete while most optimization theory is built for continuous ones, the authors argue that a stochastic population-based method is the only general recourse. What departs from routine engineering practice is not the technique — genetic algorithms were already well established by 2005 — but the strength of the claim that deterministic methods are "unsuitable for all but a very limited problem domain."
The method
Provenance and defining features
The authors trace evolutionary methods to Darwin's natural selection and to R. A. Fisher's genetical theory of natural selection, and the genetic algorithm proper to Holland, with Goldberg and Bäck as the standard references. Any recursive population-based approach that uses selection plus random variation to generate new solutions counts as an evolutionary technique. Four properties are given as characteristic of genetic algorithms: they work on a code of the variable group (artificial genetic strings) rather than on the variables themselves; they carry a population of potential solutions rather than improving a single one; they use no information from the object function's derivatives or any auxiliary knowledge; and their transition rules are probabilistic rather than deterministic.
The schema theorem
The paper's one piece of underlying theory is Holland's schema theorem, quoted in Goldberg's form: "short schemata of low order with aptitude above average exponentially increase its number by generations." The inequality given is
m(H, t+1) ≥ m(H, t) · f(H)/favg · [1 − pc δ(H)/(l − 1) − pm O(H)]
where m(H, t) is the number of instances of schema H at generation t, f(H) the average fitness of strings matching H, favg the population average, l the string length, δ(H) the defining length of the schema, O(H) its order, and pc, pm the crossover and mutation probabilities. This is offered as the justification for the algorithm's robust search ability.
Operators
Three operators are described. Reproduction allows the genetic information stored in high-fitness strings to survive into the next generation, each string being assigned a value according to its aptitude in the object function and that value setting its probability of being chosen as a parent. Crossover divides two strings at a randomly chosen point and exchanges the segments — the paper's worked example takes 101001|01 and 111100|00 to 101001|00 and 111100|01 — and is characterised as exploitation of a region of parameter space. Mutation changes an elementary portion (allele) of a single string, taking 10100101 to 11100101, and is characterised as a change of search area in parameter space. The exploitation/exploration contrast between the two is the paper's clearest conceptual point.
Coding, fitness and scaling
Variables are transformed into binary strings, several variables being concatenated. For a required precision Ac on a variable bounded by XU and XL, the number of bits m must satisfy 2m ≥ (XU − XL)/Ac + 1, with the caution that demanding excessive precision lengthens the string and can degrade the search.
Selection may be proportional, Pi = fi/Σfj, or by grouping the population into fitness bands whose members share a reproduction value. For minimization the gross fitness may be taken as the reciprocal of the object function, f = 1/FO. To prevent a single high-fitness individual dominating the first generation, linear scaling f′ = af + b is applied, with the coefficients constrained so that the scaled average fitness stays close to the gross average — which ensures each member contributes on average at least one offspring.
Control parameters
The authors survey work on the interaction of population size, crossover probability, mutation probability and selection, and conclude that the existing studies address simplified problems and do not transfer to practice, so that convergence tests with varied values are unavoidable. Their recommended starting point is a population of 30 to 50 individuals, a crossover probability of about 0.6, and a mutation probability of about 0.01.
Electromagnetic applications
Six applications are surveyed. The first is low-sidelobe optimization of a non-equidistantly spaced long array antenna with quantized excitation and phase, for which the array factor is given as a double sum over elements involving k(dl/2 − Σdm) sin φ cos φ terms; the search space is finite but exhaustive search is impractical. The second is far-field prediction from near-field measurements by fitting an equivalent set of elementary dipoles, at eight parameters per element — four dipoles already give a 28-parameter space — minimizing |F| = |Σ gm(s)(vm − fm(rm, S))| over the vector S of dipole excitations, positions and orientations. Because |F| is highly nonlinear with many local minima, the authors argue only a non-conventional method can find the global optimum.
The third is wide-band microwave absorber coating design, where the layered reflection coefficient is built up by the recursion Ri = (R̃i−1 + Rie−2jki−1ti−1)/(1 + R̃i−1Rie−2jki−1ti−1) with ki = 2πf√(μiεi) and R0 = −1 on a perfect conductor, the goal being to minimize simultaneously 20 log10{max|R(f)|, f ∈ B} and the total thickness Σti. The authors note explicitly that these two goals are opposed, and that the technique found a trade-off rather than a single optimum. The remaining three are: extraction of frequency-dependent permittivity, permeability and conductivity from S-parameter measurements at GHz frequencies; design of electrically small auto-resonant antennas, where the genetic algorithm searches for a wire configuration whose inductive and capacitive reactances cancel at resonance, the difficulty being that radiation resistance falls toward zero and reactance diverges as the antenna shrinks; and recovery of Debye and Lorentzian dispersive-media parameters from transmission-line measurements.
Assessment
Taken for what it is — a compact tutorial and application survey — the paper is sound and useful. The exposition of coding, the three operators, proportional selection and linear fitness scaling is correct and clear, and the recommended starting parameters (population 30–50, pc ≈ 0.6, pm ≈ 0.01) are conventional and reasonable. Two of its judgements are better than routine. The first is the observation that the published studies of parameter interaction address simplified test problems and therefore cannot be transferred to real design work, so that empirical tuning is unavoidable; that remains true. The second is the frank statement in the conclusions that although genetic algorithms demand no derivative information, "it is necessary that one has the sense that a global optimal exists", and that the technique should be checked against another method of the same class such as simulated annealing. Recommending cross-validation against a competing stochastic method is exactly the discipline such papers usually omit. The absorber-coating example is also well chosen, because it makes visible the multi-objective character of real design problems: minimizing reflection and minimizing thickness pull against each other, and what the algorithm returns is a trade-off, not an optimum.
The difficulties are those of scope rather than of error. The paper presents no new algorithm, no benchmark, and no results of its own — every application is reported from the literature by citation, and no convergence data, run time, or comparison against a deterministic baseline is given anywhere. The title's promise of "an optimization method" is therefore not quite met; what is delivered is an argument for an existing method. That matters because the paper's central claim — that deterministic methods are unsuitable for all but a very limited domain — is asserted rather than demonstrated, and it is too strong as stated: gradient methods with multistart, and interior-point or sequential quadratic programming on smooth reformulations, remain competitive on many of the problems named, and the authors offer no case in which a deterministic method was tried and failed.
The theoretical footing is also thinner than the presentation implies. The schema theorem is quoted as the ground of the algorithm's robustness, but it is a lower bound on the expected count of above-average short schemata over one generation, and it does not establish convergence to a global optimum; the paper does not say this, and the standard criticisms of the building-block hypothesis go unmentioned. Similarly, the claim that mutation changes the search area while crossover exploits within it is a useful heuristic, not a result. Finally, the equations are transcribed from their sources with some loss — the array-factor expression in particular is hard to reconstruct unambiguously from the printed form — so the paper functions better as an orientation to the literature than as a working reference.
None of this is a criticism of the method itself, which is well established, and the paper does not overclaim in its conclusions: it ends by naming computation time as the technique's chief inconvenience and calling genetic algorithms "an excellent option" rather than a universal one.