Warin (Yong) Wattanapornprom  |  Research Portfolio
Technical Note

Incremental Edge/Node Histogram Based Sampling Algorithms for Permutation Problems

1

Incremental Edge Histogram Based Sampling Algorithm and
Incremental Node Histogram Based Sampling Algorithm for Permutation Problems

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

Abstract — Most optimization algorithms that use probabilistic models focus on extracting the information from good solutions found in the population. A selection method discards the below-average solutions assuming that they do not contribute any information to be used to update the models. This work proposes a new algorithm, Combinatorial Optimization with Coincidence (COIN) that utilization the substructures in both good and not-good solutions. A Generator represents a probabilistic model of the required solution. The Generator is used to sample candidate solutions. The substructure collected from both good and bad populations are use to update the generator as reward and punishment schemes. It has been observed that the not-good solutions contribute to avoid producing the bad solutions. The proposed algorithm has been tested with sequencing problems on mixed-model U-line in JIT production system. The result shows that it is better than NSGA II in most performance measurement.

Index Terms—Multi-Objective Combinatorial Optimization, Permutation, Negative Knowledge, Ordering Schemas

INTRODUCTION

"Failure is simply the opportunity to begin again, this time more intelligently – Henry Ford.

combinatorial optimization problem is ubiquitous in various applications including

adjacency matrix

Order Schema

Linkage and Building Block Identification

Sequence Alignment Techniques

Edit Distance

Global and Local

Alignment Crossover

The main idea is to find which position should be a cut point for crossover

Fig 1. Masking obtained from an alignment process

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

Preserving both relative and absolute order schemas.

Can be used as a template for EHBSAs, NHBSAs and COINs or apply to crossover techniques or random fill mutation.

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.