An Introduction to Applied Evolutionary Metaheuristics

Jonathan Anderson

First delivered by me at "Selected Topics on Complex Systems Engineering" an international symposium held at Morelia, Mexico in October 2008. It was subsequently published in the European Journal of Operational Research : Applications of metaheuristics

View slide show

Abstract

This paper introduces some of the main themes in modern evolutionary algorithm research while emphasising their application to problems that exhibit real-world complexity. Evolutionary metaheuristics represent the latest breed of biologically inspired computer algorithms that promise to usefully optimise models that display fuzzy, complex and often conflicting objectives. Until recently, evolutionary algorithms have circumvented much of this complexity by defining a single objective to be optimised. Unfortunately nearly all real-world problems do not compress neatly to a single optimisation objective especially when the problem being modelled is non-linear. Recent research into multi-objective evolutionary metaheuristic algorithms has demonstrated that this single-objective constraint is no longer necessary and so new opportunities have opened up in many fields including environmental health and sustainability.

With their proven ability to simultaneously optimise multiple, conflicting objectives, evolutionary metaheuristics appear well suited to tackle ecological problems. Such algorithms deliver a range of optimal trade-off solutions that allow an appropriate profit / cost balance to be selected according to the decision maker's imperatives. This paper concludes with an examination of a powerful multi-objective evolutionary algorithm called IC-SPEA2 (Martínez-García & Anderson, 2007) and its application to a real world problem namely the maximisation of net revenue for a beef cattle farm running on temperate pastures and fodder crops in Chalco, Mexico State. Some counter-intuitive results and their impact on the farm's overall sustainability are discussed.

What is a Metaheuristic?

A heuristic is a 'rule of thumb', that is a algorithm that provides a solution to a problem without considering whether the solution is formally optimal but which will, nonetheless, tend to be good enough for real-world application.


Figure 1: The law of diminishing returns indicates that perfection is not a realistic goal.

A metaheuristic is an algorithm that synthesises two or more heuristics into a single compound. A metaheuristic algorithm is therefore a heuristic that relies on other heuristics either as sub-components or outsourced to black-box functions.

A metaheuristic example is found in neural-networks. Researchers found that manually training neural networks was inefficient (Alba, Enrique, Marti, Rafael. 2006.). This issue has been solved by employing search heuristics, including evolutionary algorithms, to discover appropriate training regimes for the neural networks (Alba et al). The compound algorithms that results from the synthesis of a neural-networks and evolutionary search heuristics are metaheuristic algorithms.

No Free Lunch

It may seem as though metaheuristics have the potential to create a general or universal search / optimisation mechanism to solve complex problems for which no problem-specific heuristic currently exists. However a theoretical stumbling block stands in the way of this goal.

The No Free Lunch Theorem states that : "any two algorithms are equivalent when their performance is averaged across all possible problems" (Wolpert & Macready 1995)

This implies that for any optimisation algorithm, gaining additional performance over one class of problems is exactly paid for in performance over another class. A universal problem solver is therefore not possible.

Despite this lack of universality metaheuristics remains a vibrant topic of research with many exciting approaches under investigation:

• Simulated annealing
• Ant colony optimization
• Harmony search
• Evolutionary algorithms

What is an Evolutionary Algorithm?

Being alive is a very complex objective, perhaps the most complex there is, and yet solutions to this problem exist in astonishing variety and subtly.
If we cast biology in the role of an optimisation strategy then we can say that biology seeks optimal solutions to the problem of being alive. If, as computer scientists, we could unlock the process by which this most complex of combinatorial-optimisation problems is successfully solved then we would surely have found a powerful heuristic tool.
The process by which biological complexity emerges is Evolution by Natural Selection. In his book “The Blind Watchmaker”, professor Richard Dawkins provides a precise definition of this algorithmic process, precise enough for eventual translation into an computer code:
"Natural Selection is the result of the non-random replication of randomly varying replicators" (Dawkins. 1986)
Natural selection discovers optimal replicators via iterative replication, random variation and environmentally guided selection. If being alive is the problem then, according to Dawkins, the non-random replication of randomly varying replicators is the solution. An evolutionary algorithm is simply this definition converted directly into a computer code.

A General Evolutionary Algorithm

1. InitializationFirst an initial population must be created. This population will contain replicators whose characteristics have been randomly generated.
   
   
   Figure 2: The main loop at the heart of every evolutionary algorithm.
   
2. Fitness assignment
   Each replicator must be evaluated and assigned a fitness value according to a problem-specific definition of fitness.
   
3. Environmental selection
   A subset of the fittest replicators is selected to be used as the breeding stock when breeding a new population of child replicators. The selection process is deterministic and based on the problem specific fitness values assigned previously.
   
4. Termination
   If stopping condition is met then Stop.
   
5. Breeding and Variation
   Breed fittest to create a new population of child replicators. Breeding will mainly involve the mixing of parent characteristics, multiple parents to produce a single child, with the additional chance of a random mutation to slightly alter randomly selected child characteristics.
   
6. Go to Fitness Assignment

Over many generations the population will efficiently search the replicator state-space, the n-dimensional set of possible replicator states where n = the number of mutable replicator characteristics, producing replicators with ever increasing fitness (Goldberg 1989).

Another way of conceiving the evolutionary process is to imagine a complex process deconstructed into a set of rules that together make up a model of that process. The purpose of the evolutionary algorithm is therefore to optimise this model. A model will have many variables that go to define its current state any given point in time. These are usually called the model's decision values. A collection of decision values represents the variability between different instances of a model.

When optimising a model certain characteristics are selected to be the targets of optimisation. These are usually called the objective values. The purpose of the model is to convert decision values into objective values according to the model's internal rules. The objective values are then used by the evolutionary algorithm to calculate a fitness value. Thus a replicator is a set of decision values with an associated set of objective values. The model is the set of environment rules within which the replicator finds its physical expression. The evolutionary algorithm is the set of rules that evaluates, selects and breeds future generations of replicators ready for their brief flicker of life within the model.

Replicators consist of a series of values, analogous to genes, and so can be conveniently encoded as a set of characters, or string, which is analogous to the genome. Often binary is used to encode the replicator values and so the genome will consist of a long string of binary '1' and '0' characters. This makes it relatively easy to manipulate the genome, breaking it into pieces and splicing those pieces back together using standard string handling techniques common to most computer languages. For example during breeding when parental values are mixed together to create a novel child using the mechanism called crossover.

The Crossover Mechanism

During breeding the characteristics of two selected parents are mixed together using a mechanism called crossover to create a novel child. The selection process depends on the fitness values of the parents where the fitter the parent the more likely it is to be selected. This means that the average fitness of the population tends to increase over the generations.

• Select two parents
• Pick a locus somewhere on the parental genome
• Split both the parent's genomes at the selected locus
• Take the first portion of the first parent's genome and join it to the second portion of the second parent's genome to create a new child genome

Figure 3: Illustration of the crossover mechanism that recombines parental characteristics to create novel child combinations.

The mixing of parental values does not affect the values themselves but it does create novel combinations of pre-existing values. This means that short combinations of values which happen to result in higher fitness are preserved between generations. During crossover multiple, high fitness values are moved as a single unit or schema (Goldberg. 1989) between parents and their offspring.

Implicit Parallelism

As a result of selection and crossover fit building blocks or schemata are propagated from generation to generation. Each population member thus provides multiple points at which the state-space is being sampled and tested. Since a population has many members and each member is sampling the state-space with many schemata the resulting search is implicitly parallel.(Goldberg. 1989)

This multiple parallel sampling of the state-space is a unique feature of evolutionary algorithms and it dramatically leverages the efficiency of the search without requiring any special book keeping, processor or memory overheads.

When attempting to solve NP-hard problems, increasing the number of values that define a replicator will exponentially increases the size of the state-space to be searched (NP-hard is a class of problem that cannot be solved in less time than the exponential of the problem size). Evolutionary algorithms display a remarkable insensitivity to the inflation of their target state-space. This insensitivity is due to implicit parallelism. As the number of replicator variables grows then so must the length of the string used to encode them. This simply creates more schemata and so increases the degree of implicit parallelism. In this way an evolutionary algorithm leverages the inflation of the state-space to amplify the effects of implicit parallelism and so mitigates the effects of state-space inflation.

Single Objective Evolutionary Algorithms

Single objective problems are problems whose objectives can be collapsed or aggregated into a single overall objective to be maximised or minimised.A standard NP-hard benchmark single objective problem is the travelling salesperson problem or TSP which states: Given a number of cities and the distance from any city to any other city, what is the shortest round-trip route that visits each city exactly once and then returns to the starting city?Exact, non-heuristic algorithms will give precisely the shortest possible route. For example various branch-and-bound algorithms1 can be used to process TSPs containing 0-60 cities whereas progressive improvement algorithms2 work well for up to 200 cities (Dekker 2008)

Evolutionary algorithms do not necessarily return the shortest route but they do promise to return a route that is sufficiently short to be useful. The payback for accepting this heuristic uncertainty is the insensitivity to state-space inflation. Evolutionary algorithms can usefully process TSPs up to 100,000 cities and beyond (Dekker 2008).

Single-objective evolutionary algorithms allow single objective problems to be usefully solved. By contrast multi-objective problems do not resolve to a single global optimum but are instead optimise to a potentially large set of trade-off solutions. Finding this set of optimal trade-offs requires a more powerful class of evolutionary algorithm.

What is a Multi-Objective Problem?

A multi-objective problem is characterised by having two or more conflicting objectives. If objectives do not conflict then they can always be aggregated back into a single compound objective. It is the conflict between different objectives that defines a multi-objective problem and creates the additional complexity that defeats the single-objective evolutionary algorithm approach.

Multi-objective problems can be found in various fields:

• Product and process design
• Finance
• Aircraft design
• Oil and gas industry
• Vehicle design

Or wherever decisions are taken where trade-offs exist between two or more conflicting objectives:

• Maximising performance and minimising fuel consumption
• Maximising strength and minimising weight

Figure 4: A real world evolutionary solution to the strength versus weight contradiction.

Multi-objective problems cannot be resolved to a single solution that simultaneously optimises all of the objectives. As soon as two or more conflicting objectives are present then the single global optimum solution disappears to be replaced by a set of non-dominated or Pareto-optimal solutions.

A solution is considered Pareto-optimal if every objective has been optimised to such an extent that attempting to further optimise one of the objectives will result in the degradation of the other objectives. Therefore every Pareto-optimal solution represents an optimal trade-off between the conflicting objectives. Since there are many combinations of objective trade-off there are also many different Pareto-optimal solutions.

The members of a Pareto-optimal set cannot be distinguished in terms of optimality but they can be distinguished in terms of there perceived utility. In order to make a choice between Pareto-optimal solutions external information must be employed. This information can come directly from a human decision maker via a software interface or by encoding the known preferences of a human decision maker as set of post-optimisation rules.

Solving problems with multiple conflicting objectives is challenging. The simplest approach is to construct a single aggregate objective function by assigning each objective a scalar weight which is combined into a single function that can be solved by any single-objective optimisation algorithm (Messac, A., Ismail-Yahaya, A., & Mattson. 2003). The problem with this approach is the globally optimal solution obtained will strongly depend on the values of the arbitrary objective weights. If a higher weight is specified for one objective relative to the others then the optimal solution will be one that favours that objective over the others. Solutions obtained using the weighted sum are always Pareto-optimal, but establishing a meaningful combinations of objective weightings can be very challenging (Messac et al).

Multi-Objective Evolutionary Algorithms

Evolutionary algorithms are well-suited for optimisation problems involving several conflicting objectives. A multi-objective evolutionary algorithm simultaneously optimises multiple conflicting objectives for a given problem resulting a Pareto-optimal set of solutions where each solution represents an optimal trade-off between the conflicting objectives. Although various evolutionary approaches to multi-objective optimisation are capable of searching for multiple solutions concurrently in a single run, in general the discovery of the Pareto-optimal set of solutions involves two implicit goals (Zitzler, Eckart and Laumanns, Marco and Thiele, Lothar. 2001):

1. Minimise the distance from the evolving Pareto front to the undiscovered Pareto-optimal set.
2. Maximise the diversity of the generated solutions.

Minimise the Distance

The set of intermediate solutions generated as the algorithm progresses is called the Pareto front. It is an n-dimensional surface (where n is the number of objectives) whose shape evolves through state-space as the algorithm discovers ever more optimal solutions (Zitzler et al)

Over time the shape of the Pareto front approaches the shape of the Pareto-optimal set or the set of solutions that fully dominates all other possible solutions (Zitzler et al). One solution is said to fully dominate another if each of its objective values is superior (smaller if the objective is being minimised or greater if the objective is being maximised).

To guide the evolving Pareto front, multi-objective algorithms can employ a technique called elitism whereby the best solutions found to date are retained in a secondary population called the archive. An elite solution is replaced in the archive when another solution is discovered that fully dominates it. This avoids the population being dominated by solutions that improve one objective at the expense of another.

Maximise the Diversity

As the algorithm progresses the elite members of the archive tend to converge on a series of points along the non-dominated front creating clusters of solutions. Such clusters indicate a lack of diversity within the emerging Pareto front. Solution diversity is important as rarefied areas of the front will remain poorly investigated with the potential to miss interstitial solutions that may be good enough for application in the real world.

To prevent this gradual loss of diversity modern algorithms tend to incorporate a pruning mechanism whereby solutions that lie too close to their neighbours are removed or pruned to leave room for additional novel solutions. The distance between solutions is calculated in terms of the position in the multi-dimensional state-space with solutions that appear in dense clusters identified and removed (Zitzler et al).


Figure 5: The pruning mechanism. The non-dominated set is shown on the left. The centre indicates those solutions selected for removal. The final, pruned set is shown on the right. This figure has been adapted from Zitler et al (pp8).

The pruning mechanism needs to be carefully designed if good solutions, especially good outrider solutions lying at the edges of the Pareto front, are not to be discarded. The goal is to maintain solution diversity by maximising the spread of solutions across the Pareto front with each solution evenly spaced with respect to its neighbours (Zitzler et al).

Stopping the Algorithm

Due to the intractability of NP-hard, real-world problems the globally optimal Pareto set is typically unknown. This implies that it is impossible to know when the optimisation process should end since there is no metric to determine whether the current Pareto set is the unknown global optimum set. However this is a common feature of heuristic algorithms and is usually resolved by accepting that solutions only need to be good enough and not necessarily optimal in the formal sense.

What is a Constraint?

All real world problems are constrained by physical limits. Solutions that lie outside of these limits are infeasible. Constraints model the physical limits of a problem and therefore a constraint defines a component of solution feasibility. If a solution violates one or more of its constraints then the solution is considered infeasible (Wright J. A., Loosemore H. 2001).


Figure 6: Constraints are the rules that bound the feasible set of solutions. All solutions that do not satisfy the constraints are considered infeasible.

Where advanced knowledge of the problem domain is available it is often possible to define constraints and so confer upon a solution a measure of feasibility. For example the Travelling Salesperson Problem typically does not consider the needs of the salesperson however in real life a salesperson will have a physical limit to the distance they can travel before they must return home. In other words there is an upper limit to the route length and any route that exceeds this length must be considered infeasible. The longer a route is over the upper limit the greater the degree to which the constraint is violated. This allows infeasible routes to be compared and ranked according their degree of infeasibility.

The Problem with Constraints

Since the infeasible solutions will vastly outnumber feasible solutions then throwing away infeasible solutions as they are discovered forces the algorithm to spend most of its time randomly walking through the state-space trying to find a population of feasible solutions to get the ball rolling. The algorithm is being presented with a cliff-face to climb at the outset of any run.

A more effective approach is to provide a mechanism whereby the algorithm can evolve its way from infeasibility to feasibility so converting the cliff-face into a gradual incline. A good way to create a gradual slope is to add an infeasibility objective to the problem(Wright et al). An infeasibility objective is a single measure of a solution's infeasibility. It is treated as an independent objective by a multi-objective evolutionary algorithm. The measure of infeasibility should represent both the number of active constraints and the extent to which each constraint is violated. A measure of infeasibility that has these properties is the sum of the normalised constraint violation values for all violated constraints (Wright et al). The new infeasibility objective is set to be minimised, the smaller the objective value the more feasible the solution is. For feasible solutions the value for the infeasibility objective should equal zero.

With the infeasibility objective in place it is not necessary for a given solution to be feasible in order for it to take part in the ongoing evolutionary process. This allows a population of infeasible solutions to be generated at the start of a run and used to slowly evolve towards a set of feasible solutions.

Applying an Evolutionary Metaheuristic

The hybrid metaheuristic algorithm IC-SPEA2 was first proposed by Martínez-García & Anderson, 2007. It consists of an an infeasibility constrained (IC) version of the Strength Pareto Evolutionary Algorithm 2 (SPEA2) (Zitzler et al).

The core algorithm, SPEA2, is a powerful multi-objective evolutionary metaheuristic that evolves a set of initially infeasible solutions towards the feasible Pareto-optimal set using elitism, a fine-grained fitness assignment strategy and a sophisticated pruning mechanism for maintaining solution diversity without losing outriders.

The state-space is constrained by the addition of an infeasibility objective that forces the algorithm to evolve and maintain a feasible set of solutions. At the end of each optimisation run the non-dominated Pareto-optimal set of solutions is presented to the human decision maker for evaluation and selection.

SPEA2 Main Loop (Zitzler et al)

Input: N population size
N² archive size
T maximum number of generations
Output: ND (non-dominated set)

Step 1. Initialization
Generate an initial population P0 and create the empty archive P²0 → Ø. Set t = 0.

Step 2. Fitness assignment
Calculate fitness values of individuals in Pt and P²(t)

Step 3. Environmental selection
Copy all non-dominated individuals in Pt and P²(t) to P²(t+1). If size of P²(t+1) exceeds N² then reduce P²(t+1) by means of the truncation operator, otherwise if size of P²(t+1) is less than N² then fill P²(t+1) with dominated individuals in Pt and Pt

Step 4. Termination
If t »= T or another stopping condition is satisfied then set ND to the set of decision vectors represented by the non-dominated individuals in P²(t+1). Stop.

Step 5. Mating selection
Perform binary tournament selection with replacement3 on P²(t+1) in order to fill the mating pool.

Step 6. Variation
Apply crossover and mutation operators to the mating pool and set P(t+1) to the resulting population. Increment generation counter (t = t + 1) and go to Step 2.

Testing the Algorithm: The [0/1] Knapsack Problem

The [0-1] knapsack problem is a classic test problem in combinatorial optimisation (Goddard). It seeks the best choice of essential equipment that can fit into one knapsack to be carried on a trip. Given a set of items, each with a weight and a profit value, determine the combination of items to pack into the knapsack so that the total weight is less than or equal to the knapsack's total capacity and the total profit is as large as possible. The problem is called a “[0-1]” problem because each item must be entirely accepted or rejected, that is you cannot sub-divide an item.

Problem Description

Given a knapsack with maximum capacity and a set of items where each item has some weight and profit value, what items should be packed into the knapsack to achieve the maximum profit for the minimum weight?


Figure 7: The knapsack test rig showing a perfect Pareto optimal curving through the 2D state space. Note the lack of clumping. The red dots are infeasible solutions due to a constrained sack size.

Problem Objectives:

• Maximise Profit
• Minimise Weight

Since each item has both a positive profit and weight then adding more items increases the profit, which is desired, but also increases the weight, which is not desired. Conversely removing items decreases the weight, which is desired, but also decreases the profit which is not desired. In other words the objectives are conflict.

Conflicting objectives means that no single knapsack will represents the best possible combination of both weight and profit. Instead a range of non-dominated knapsacks, the Pareto-optimal set, is required to represent the full range of trade-offs between weight and profit leaving the external human decision maker to choose according to their own preferences.

Applying the IC-SPEA2 Algorithm: A Mexican Beef Cattle Farm

A farm is a dynamic system emerging from the imperatives of the environment coupled to the experience of the farmer and the way the available resources are manipulated when trying to achieve multiple and most probably conflicting objectives. A farmer's capacity to act is always bounded by multiple trade-offs, environmental constraints and shifting measures of success (Martínez-García A, Anderson J. 2005).

To explore the problem of farm profitability a model of a Mexican beef cattle farm running on temperate pastures and fodder crops was created. The model served as a black-box objective function taking a set of decision variables and convert these values, via the complex, iterative model rules, into multiple objective values for evaluation by IC-SPEA2, the multi-objective evolutionary algorithm.

Figure 3: An illustration of the relationships between the farm manager, the farm, the farm model and the IC-SPEA2 algorithm used to generate Pareto optimal farming strategies

The purpose of the modelled beef farm is make money by converting food into live animal weight. The farmer can control the rate of weight gain by varying the amount and type of food to be included in the diet formulation for each of the twelve months of the season. The different food types have different nutritional benefit and purchase / production costs which vary throughout the season.

The optimisation objectives for the farm were:

1. Maximise net revenue
2. Minimise the cost of the diet
   This conflicts with maximising net revenue since cheap food tends to have low nutritional value.
3. Maximise average daily weight gain
   This conflicts with minimising diet costs since increasing the weight gain involves using food with the highest nutritional value of the diet resulting in increased diet costs. It may also conflict with maximising net revenue since heavy animals lead to higher variable costs.

The farm manager was asked to suggest an optimal strategy based on his experience and perceived objectives. He suggested the use of as much pasture as possible to feed the herd, supplementing this with alfalfa only when seasonal shortages of pasture occurred, and further only using silage and stubble when both pasture and alfalfa were in short supply.

In other words the farmer suggests feeding his animals in such a way as to maximise the weight gain while minimising the diet costs. If these two objectives are achieved then it seems perfectly reasonable to assume that third objective maximise the net revenue will be achieved since fatter animals should sell for more (Martínez-García et al).

Interpreting the Results – A Counter Intuitive Strategy is Discovered

Table 9: Martínez-García et al (pp. 647)

IC-SPEA2 returned multiple, distinct Pareto-optimal strategies, of which two were of particular interest:

• Solution 2
  The strategy that gave the highest net revenue.
• Solution 1
  The strategy that gave the highest live weight gain.

These results were counter-intuitive as it was assumed that the strategy that gave the highest live weight gain would be the same strategy that gave the highest net revenue.
Even the farmer assumed that the goal was to make the animals as heavy as possible since heavy animals sell for more money.

Yet IC-SPEA2 found a strategy that gave the highest net revenue while delivering lighter animals. This has potentially profound implications for the sustainable management of the farm.

The Implications for Farm Sustainability

Among the most surprising discoveries resulting from using IC-SPEA2 were the counter-intuitive nature of the solutions, their diversity and the fact that such a set allows for a compromise between the manager's goals and the precautionary principle4.

This point is demonstrated by the fact that for the solution with the highest net revenue the animals eat less allowing for a compromise between the farmer's objectives and the sustainability of the farm. Maintaining net revenue while reducing live weight gain can correspondingly reduces the stress on the available pasture and allows the farmer to meet his profit obligations while operating the farm at below its maximum carrying capacity.

Furthermore, IC-SPEA2 showed the potential usefulness of on demand optimisation displaying an ability to simulate and optimise a large, non-linear model with an intractable state-space using a cheap laptop computer. Martínez-García et al (2005) states that:

... as self-generated, cognitive systems with humans at their core, the main technical problem for achieving sustainable [farming systems] is how to enhance the decision-makers skills for choosing appropriate courses of action, in real time, in response to their own internal, dynamic purposes, while increasing their number of choices to face complex environmental conditions.

This suggests farmers making regular use of real-time evolutionary metaheuristic software may be able to respond to changes in their dynamic farm systems and so perform frequent, incremental, strategic re-evaluations in the field. These small adjustments measured against the backdrop of a shifting reality may well buffer against the over-shoot and performance fluctuations that can prove damaging to the sustainability of a complex, dynamic farm system.

Finally it suggests that the ability of multi-objective evolutionary heuristics to generate a Pareto set of multiple, optimal choices gives the farmer the control and scope to dynamically re-balance the farm's objectives to maintain its sustainability in a measured and controlled manner even as the environmental conditions fluctuate and the farmer's measures of success evolve.

References

Alba, Enrique, Marti, Rafael (Eds). 2006. Metaheuristic Procedures for Training Neural Networks. Operations Research/Computer Science Interfaces Series, Vol.35

Dawkins, R. 1996. The Blind Watchmaker. UK: Penguin Books

Dekker, M.D. 2008. Travelling salesman problem. http://en.wikipedia.org/wiki/Travelling_salesman_problem

Goddard, S. Dynamic programming 0-1 Knapsack problem. CSCE 310J. Data Structures & Algorithms. http://www.cse.unl.edu/goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley.

Martínez-García A, Anderson J. (2005). Cárnico-ICSPEA2 – A metaheurístic co-evolutionary navigator for a complex co-evolutionary farming system. European Journal of Operational Research 179 (2007) 634–655

Messac, A., Ismail-Yahaya, A., and Mattson, C.A. (2003) The Normalized Normal Constraint Method for Generating the Pareto Frontier, Structural and Multidisciplinary Optimization, Vol. 25, No. 2, 2003, pp. 86-98.

Wolpert, D.H., Macready, W.G. (1995), No Free Lunch Theorems for Search, Technical Report SFI-TR-95-02-010 (Santa Fe Institute).
Wright J. A., Loosemore H. (2001). An Infeasibility Objective for Use in Constrained Pareto Optimization. EMO 2001: 256-268

Zitzler, Eckart and Laumanns, Marco and Thiele, Lothar (2001) SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Evolutionary Methods for Design, Optimisation, and Control.

Notes

1 A general optimisation algorithm where all possible solutions are processed and discarded in blocks if they lie outside the estimated minimum and maximum bounds of the quantity being optimized

2 Progressive improvement algorithms follow a direction of improvement until no further optimisation can be made. With luck the global optimum is now located.

3 Two random solutions are selected from the population and the more fit of the two wins the tournament. A clone of the winning solution is made leaving the original in the population so it can continue to take part in future tournaments.

4 A moral and political principle that invokes caution to avoid damaging the environment in ways that cannot be reversed where the scientific evidence is not conclusive.