EO in practice

As with any other program, evolving objects involves two different phases: the design phase and the programming phase.

• Design: Usually, the object to be evolved is directly given by the application. If what is being approached is the solution to the Travelling Salesperson problem, then a class of TSP paths TSPPath should be designed, in the usual object-oriented way. In many cases, this is not trivial, and guidelines on object oriented design such as the one proposed in Booch et al.'s book [11] should be used. The internal representation can be chosen freely, but in this case, the most adequate is simply an integer array which holds all the cities. A TSPpath factory should also be designed, and it should be able to build new TSPPaths under request. Then, unary and binary operators should be designed to change and combine existing TSP solutions; these operators will take into account the TSP path interface. The unary operators would basically apply permutations to the integer array that represents the path, and the binary operators would combine solutions using any of the current TSP crossover operators (like, for instance, the inver-over operator introduced in [12]). The rest of the design is usually problem-independent: selection, reproduction and elimination procedures, and stopping criteria.
• Programming: The EO algorithm would be programmed much in the same way as any other evolutionary algorithm, that is:

  .

  Create an initial population using the EO factory, or using random default constructors for each object.

  .

  Repeat steps 3 and 4 until a stopping criterium or a logical combination of them is met.

  .

  Evaluate or compare population elements with each other, selecting the best.

  .

  Applying the genetic operators, create new solutions (increase diversity), combine (decrease diversity) or change existing ones, substituting the worst.

  That simple algorithm can be substituted by any other in the evolutionary realm, provided that, on average, the best are kept, the worst are eliminated, and diversity is created (exploration) by applying mutators and decreased (exploitation) by applying selective reproduction and/or crossover. It is even possible to automatically control the exporation/exploitation relation, by using operators with adaptive rate.

There is no theoretical support to prove that this work, or even that this works better that simple random exploration. As it does not use a binary alphabet, neither it can be said that it uses an alphabet, the Schema Theorem does not apply, or any other theoretical results obtained for Evolution Strategies or Evolutionary Programming. However, it should work, at worst, as a random search algorithm, and since it might use solution combination or crossover, the building blocks that make a good solution are being mixed, and thus, it should reach better solutions.

EO takes a bit further the ``building block theory''[1]: as the user is freed from a linear bistring representation, and solutions to problems are coded in natural form, the blocks that form the solution are naturally together, and they are inherited together.

EO also turns some problems that would be considered constrained due to the linear bitstring representation into unconstrained, avoiding the use of penalty functions and repair methods, and thus is better suited than GAs for problems that can't be easily mapped to linear bit strings.