Why optimize? In design, construction and maintenance of engineering systems, engineers take decisions relating to technology and management at several stages, with an aim to either minimize effort required or maximize benefit from the given resources. Since the effort required or the benefit in any practical situation can be expressed as a function of certain decision variables, optimization can be defined as finding the conditions that give the maximum or minimum (optimum) of the function. The existence of optimization methods existed since the times of Newton and Cauchy who used gradient methods for finding optima. However certain problems are of multi-dimensional nature, and some where optima are hard to find due to a variety of reasons. There may be situations in which conventional methods fail, (such as local optima or non-existence of derivatives) or just become too cumbersome to compute. In such situations we are forced to adopt a different strategy such as Evolutionary Programming to find optima.

The world around us is filled with a staggering diversity of life. All of the plants and creatures have their own unique behavior patterns and characteristics and each species has and continues to evolve (presumably from some primordial life), constantly adapting to a changing environment to survive. The weaker members of a species tend to die away, leaving the stronger and fitter to mate, create offspring and ensure the continuing survival of the species (and genes). This is often termed as the "survivalist" or the "survival of the fittest" theory based on the laws of natural selection proposed by Darwin.

Evolutionary Programming (EP) is a software concept which searches a given space dictated by the mechanics of natural selection and natural genetics, aiming to arrive at a final optimum. In the development of the algorithm it is assumed that the sole purpose of "evolution" is to improve, and at the end of a given interval of time the resulting population of a species will be fitter as compared to their ancestors.

In the modeling of the software, the individuals of a population at any given time are represented by their genetic makeup. In nature several thousand genes represent each individual. However, in line with our purpose to find the optimum solution to a problem, we "tailor" our species to carry only those traits, which are essential to meet our end. The traits of an individual in the real world may represent characters such as short or tall, green or yellow, but in our model these contain co-ordinates of the individual (a possible solution) in hyperspace. Each individual is expressed a specific genetic sequence, and the population is a collection of such genetic sequences. In formulating the model we lay down rules to convert the coordinates into a genetic sequence. The genes may have restrictions based on our knowledge of the search space (it is the part of the hyperspace in which we are looking for the optimal solution, which may be restricted due to constraints).

In our model each individual, at any time represents a potential solution, however depending on objective function (the function we want to optimize) different individuals give a different results. The objective function is a judge of the fitness of an individual, and imposes a selection pressure on the population. We observe that not every individual (solution) is equally fit: some are stronger and some not so strong. Thus the objective function also serves to differentiate between individuals of a population.

Starting with an initial set of individuals with random traits (co-ordinates in hyperspace), the weaker individuals are progressively replaced by offspring of the fitter individuals. Thus this model pushes the population towards individuals towards a better average fitness, improving the chances of striking the optimum, with each iteration.

In the evolution paradigm, the right to mate and produce offspring is given only to the successful individuals, success as measure by the force of selection (in our case, the objective function). Only the successful few are permitted to hand-down their superior genes to the next generation, thus generating a better offspring (hopefully, but not always). In the mating process there is a shuffle of genetic material between a pair of parents (crossover) which is then passed down to the offspring. The exact mechanism of this shuffle varies according to the exact model we adopt. In this shuffle we are intuitively generating an offspring which lie on the hyperline joining the parents, (which has a strong chance of having a superior fitness, as it is situated in the vicinity of other superior solutions). As in nature, freaks do happen – mutations – one or more genes are randomly altered, giving rise to exotic offspring. In nature and in the model this has an important function: to prevent the stagnation of the gene pool and to introduce newer variations with which the model’s population can experiment with any possibly improve by shuffling during the mating process.

There are essential differences in the time concept between our software model and the real world. There are two aspects to this argument. Firstly, time in the real world is continuous with interactions (births, mating and deaths) taking place continuously. In "our world" time is disjoint, with events taking place at discrete times only, with no activity in between. Secondly, in the real world we have a finite age to every individual after which no matter how fit he is – dies. This could work against our end in optimization in which we could lose a potential "best" solution. So we substitute the concept of death by age and introduce a scheme in which the weaker individuals are replaced by offspring of fitter individuals only – such that our population definitely improves over time (iterations).

EP differs from Genetic Algorithms (GA) in the way the traits are coded. GA codes individuals of a population (as represented by their co-ordinates) in terms of strings of 1s and 0s by sequentially breaking down each co-ordinate and storing in a concatenated form. These strings form the gene of the individual. These bear more resemblance to the real world genetics (in the binary form). These genes can be broken and crossed at any arbitrary locus, thus producing an offspring having mixed characters of both parents (just as in the real world!). Mutation is carried out by flipping (converting 1 to 0 and vice-versa) a random number of loci.

In EP, the representation follows from the problem. For example, if one were trying to find the shortest path in a Traveling Salesman Problem, each solution would be a path. The length of the path expressed as a number would be the solution's fitness. The fitness landscape for this problem could be characterized as a hypersurface proportional to the path lengths in a space of possible paths. The goal would be to find the globally shortest path in that space. The methods for crossover and mutation are modified to match the representation and taking into account the discrete nature of the hyperspace.

As EP are modeled close to biological systems in evolution, do have similar advantages – that of robustness and flexibility. They score over other artificial intelligence systems as they demonstrate qualities such as self-guidance, self-repair and reproduction. EP algorithms have been proven to be robust, flexible and efficient in vast complex spaces. These advantages are conferred due to the judicious use the idea of randomness when performing a search.

However, EP is not a simple random search algorithm. Random search algorithms can be inherently inefficient due to the directionless nature of their search. An EP is not directionless. It utilizes knowledge from previous generations of individual in order to construct a new generation that will approach the optimal solution. In other words, they use past knowledge to direct the search. Many search techniques need a variety of information to guide themselves. Hill climbing methods require derivatives, for example. The only information an EP needs is some measure of fitness about a point in the space (given by the objective function value).

EP algorithms use a set, or population, of points to conduct a search, not just a single point on the problem space. This gives EP the power to search noisy spaces littered with local optimum points. Instead of relying on a single point to search through the space, the EP looks at many different areas of the problem space at once (hence inherently parallel), and uses all of this information to guide it.

With the rise in the computation power available today – evolutionary programming strategies are advancing at a rapid pace. They are increasingly being used to solve complex problems posed by today’s engineering in the fields of aircraft design, protein selection and earthquake epicenter detection. Their inherent simplicity, adaptability and ability to solve problems without modification, from only the fitness values, has made them a versatile and indispensable tool in analysis.

-Ronak Vakil

B.E Chemical