PROTOTYPE OPTIMIZATION WITH EVOLVED IMPROVEMENT STEPS



Introduction
Typically,
   - evolutionary optimization framework considers an evolution of a population of candidate solutions to the problem at hand,
   - candidate solution encodes a complete solution (a complete set of problem control parameters, a complete schedule in JSP, a complete tour for TSP, etc.),
   - the optimal or at least well-fit solution is hard to find for large problem instances.

Here,
   - EA does not handle the solved problem as a whole,
   - EA is employed within the iterative optimisation framework,
   - its role is to evolve the best modification of the current solution prototype in each iteration.

Prototype Optimisation with Evolved Improvement Steps (POEMS)
The main idea behind POEMS is that some initial prototype1 solution is further improved in an iterative process, where the most suitable modification of the current prototype is sought for using an evolutionary algorithm (EA) in each iteration. The modifications are represented as a sequence of primitive actions/operations, defined specifically for the problem at hand. The evaluation of action sequences is based on how good/bad they modify the current prototype, which is an input parameter of the EA. Sequences that do not change the prototype at all are penalized in order to eliminate generating trivial solutions. After the EA finishes, it is checked whether the best evolved sequence improves the current prototype or not. If an improvement is found, then the sequence is applied to the current prototype and the resulting solution becomes the new prototype. Otherwise the current prototype remains unchanged for the next iteration.

POEMS outline


Representation
The EA evolves linear chromosomes of fixed length, where each gene represents an instance of certain action chosen from the set of elementary actions defined for the given problem. Each action is represented by a record, with an attribute action type followed by parameters of the action. Besides actions that truly modify the prototype there is also a special type of action called nop (no operation). Actions with action type=nop are interpreted as void actions with no effect on the prototype, regardless of the values of their parameters. A chromosome can contain one or more instances of the nop operation. In this way the variable effective length of chromosomes is implemented. An important aspect of this implementation is that any temporarily inactivated action can be activated again later on (with its formerly evolved parameters) just by switching its action type on.

Operators
The representation allows to use a variety of recombination and mutation operators.
As a crossover a generalized uniform operator can be used, that forms a valid offspring as an arbitrary combination of parental genes. Both parents have the same probability of contributing its genes to the generated child, and each gene can be used only once.
As a mutation a simple gene-modifying operator that changes either the action type (activates or inactivates the action) or the parameters of the action can be used.

Fragment of an execution on 10D real-valued optimization problem.

The process in the figure above starts with a randomly generated prototype of really poor fitness. For each iteration the following parameters are presented
   - original prototype ... the current prototype,
   - action type ... the type of the action xi,
   - parameter ... the parameter of the respective action,
   - modified prototype ... the new prototype obtained by application of the evolved action sequence to the Prototype.

We can observe that the size of the improvement steps tends to decrease during the course of the run. Also the number of active actions in the evolved action sequences decreases as the optimzation proceeds. The reason is that in early iterations the prototype is rather of bad fitness so it is easier to evolve some "innovative" action sequence that dramatically modifies the prototype. On the other hand, in latter stages of the run the prototype is already well-fit, so the EA tends to produce action sequences that do not modify the prototype much. In other words, POEMS starts with a global exploration mode at the beginning of the run and converts to the local refinement mode at the latter stages of the run.
Note, that not in every iteration an improving action sequence is evolved, see iteration nr. 9.

Traveling Salesman Problem with 2000 cities
The proposed approach has been tested on different optimisation problem domains. Here is an example of solving the well-known TSP with 2000 cities. Results show this the concept can be used to solve hard problems of big size reliably achieving comparably good or better results than classical evolutionary algorithms.

TSP data.


a) b)
a) Original prototype generated using the neighborhood heuristics and b) final solution found by POEMS.


Conclusions
   + General optimisation approach for combinatorial, discrete, and real-valued optimisation problems
   - Local (point-to-point) search approach - prone to get stuck in a local optimum

Scope of possible applications
Refinement/modification of an initial existing solution
   - Job schop re-scheduling problems - insert a new order into the current schedule
   - Local improvement heuristic for the Travelling Salesperson Problem and the Physical Travelling Salesperson Problem
   - SAT problem - dependencies among variables are necessary for effective searching for the optimum solution (but not known a priori)

Publications:
  1) Kubalik, J.: Real-Parameter Optimization by Iterative Prototype Optimization with Evolved Improvement Steps. In 2006 IEEE Congress on Evolutionary Computation [CD-ROM]. Los Alamitos: IEEE Computer Society, 2006, p. 6823-6829. ISBN 0-7803-9489-5.
  2) Kubalik, J., Faigl, J.: Iterative Prototype Optimisation with Evolved Improvement Steps. In Genetic Programming, Proceedings of 9th European Conference, EuroGP 2006. Heidelberg: Springer, 2006, p. 154-165. ISBN 3-540-33143-3.

   top


back to my research page