Warin (Yong) Wattanapornprom  |  Research Portfolio
Technical Note

Applying Alignment Techniques in EC for Permutation Representation

1

Preserving Both Absolute and Relative Order Schemas by
Applying Sequence Alignment Techniques for
Recombination and Mutation in Permutation Representation

Warin Wattanapornprom
ISL Report No 2010-02-002
Intelligence System Lab, Chulalongkorn University

Abstract — Most optimization algorithms

Index Terms—Multi-Objective Combinatorial Optimization, Permutation, Building Blocks, Sequence Alignment, Ordering Schemas

INTRODUCTION

"Multi-objective combinatorial optimization problem is ubiquitous in various applications including

Similarity in permutation representation

Fig 1. Shared common substructure of the candidates in the pareto front.

Similarity in BBs

Moreover

Similarity in MO

Encoding and Similarity

The new proposed recombination techniques are expected to be suitable with the encoding in which there are ordering constraint in the solution string for example the work station with precedence of the production line.

Order Schema

Linkage and Building Block Identification

Crossover Operation for a Permutation Representation

Since 198x many recombination operations have been proposed including Cycle Crossover (CX) [],

Partially Match Crossover (PMX) [],

Order Crossover (OX) [],

,Edge Recombination (ER) [] ข้อจำกัดของ Edge Recombination คือการที่ ER ไม่สามารถ Support Relative Order Schema (Goldberg 1992)

Non Wrapping Order Crossover (NWOX) []

Sequence Alignment Techniques

Alignment Crossover

Fig 2. ….

unfortunately, they use some indirect approaches of mapping permutation problems to fixed-length vectors of discrete or continuous variables [7][8].

Inherit absolute order from parent A, Inherit both absolute and relative order from parent B.

Suite for problem with both absolute and relative order.

References

  1. M.DellAmico,F.Maffioli and S.Martello. Annotated bibliographies in Combinatorial optimization,Wiley-interscience, Chichester,1997.

  2. EJOP Editorial, Recent advances in theory and practice of combinatorial optimization (ECCO X), European Journal of Operational Research, vol.123, pp.227-228, 2000.

  3. R.E. Steuer,Gardiner LR,Gray J (1996) “A bibliographic survey of the activities and international nature of multiple criteria decision making”. Journal of Multi-Criteria Decision Analysis 5:195–217.

  4. D.J. White (1990) “A bibliography on the application of mathematical programming multiple-objective methods”. Journal of the Operational Research Society 41(8):669–691.

  5. M. Pelikan, D. E. Goldberg, and F. Lobo, “A survey of optimization by building and using probabilistic models”, Computational Optimization and Applications, 2002, Vol. 21, No. 1, pp. 5-20. Also IlliGAL Report No. 99018.