Article

Genetic multi-step search in interpolation and extrapolation domain

Authors:

Yoshiko Hanada,

Tomoyuki Hiroyasu,

Mitsunori MikiAuthors Info & Claims

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Pages 1242 - 1249

https://doi.org/10.1145/1276958.1277197

Published: 07 July 2007 Publication History

Abstract

The deterministic Multi-step Crossover Fusion (dMSXF) is an improved crossover method of MSXF which is a promising method of JSP, and it shows high availability in TSP. Both of these crossover methods introduce a neighborhood structure and distance in each permutation problem and perform multi-step searches in the interpolation domain focusing on inheritance of parents' characteristic. They cannot work effectively when parents stand close each other since they search in interpolation domain. Therefore in the case of the MSXF, the Multi-step Mutation Fusion (MSMF), which is the multi-step search in the extrapolation domain, is combined as the supplementary search to improve its search performance. On the other hand, the search mechanism for acquisition of characteristics, such as MSMF, is not applied to dMSXF. In this paper, we introduce a deterministic MSMF (dMSMF) mechanism as complementary multi-step extrapolation search. We apply dMSXF+dMSMF to TSP and JSP, which have structural difference between their landscapes. Through the experiments it was shown that the deterministic multi-step search in interpolation/extrapolation domain performed effectively in combinatorial problems.

References

[1]

Sakuma, J., Kobayashi, S.: Extrapolation-Directed Crossover for Job-shop Scheduling Problems: Complementary Combination with JOX, Proc. of GECCO 2000, pp. 973--980 (2000).

[2]

Kobayashi, S., Ono, I. and Yamamura, M.: An Efficient Genetic Algorithm for Job Shop Scheduling Problems, Proc. of 6th Int. Conf. on Genetic Algorithms, pp. 506--511 (1995).

Digital Library

[3]

Yamamura, M., Ono, I. and Kobayashi, S.: Emergent Search on Double Circle TSPs using Subtour Exchange Crossvoer, Proc. of 1996 IEEE International Conference on Evolutionary Computation, pp. 535--540 (1996).

[4]

Shi, G., Sannomiya, N.: A New Encoding Scheme for Solving Job Shop Problem by Genetic Algorithm, Proc. of 35th IEEE Conf. on Decision and Control, pp. 4395--4400 (1996).

[5]

Ono, I., Kobayashi, S.: A Genetic Algorithm Taking Account of Characteristics Preservation for Job Shop Scheduling Problems, Proc. of the International Conference on Intelligent Autonomous Systems 5, pp. 711--718 (1998).

[6]

Nagata, Y.: New EAX crossover for large TSP instances, Proc. of Parallel Problem Solving fron Nature, PPSN IX, pp. 372--381 (2006).

Digital Library

[7]

Ikeda, K., Kobayashi, S.: Deterministic Multi-step Crossover Fusion: A Handy Crossover for GAs, Proc. of Parallel Problem Solving fron Nature, PPSN VII, pp. 162--171 (2002).

Digital Library

[8]

Yamada, T. and Nakano, R.: Scheduling by Genetic Local Search with Multi-Step Crossover, Proc. of Parallel Problem Solving fron Nature, PPSN IV, pp. 960--969 (1996).

Digital Library

[9]

Boese, K. D.: Cost Versus Distance in the Traveling Salesman Problem, Technical report, TR--950018, UCLA CS Department (1995).

[10]

Ikeda, K., Kobayashi, S.: GA Based on the UV-Structure Hypothesis and Its Application to JSP, Proc. of Parallel Problem Solving fron Nature, PPSN VI, pp. 273--282 (2000).

Digital Library

[11]

Yagiura, M., Ibaraki, T.: Genetic and Local Search Algorithms as Robust and Simple Optimization Tools, Kluwer Academic Publishers, MA, USA (1996).

[12]

Aiex, R. M., Binato, S. and Resende, M. G. C.: Parallel GRASP with path--relinking for job shop scheduling, Parallel Computing, Vol. 29, pp. 393--430 (2003).

Digital Library

[13]

Glover, F.: Genetic algorithms and scatter search: unsuspected potentials, Statistics and Computing 4, pp. 131--140 (1994).

[14]

Marti, R., Laguna, M. and Glover, F.: Principles of Scatter Search, European Journal of Operational Research, Vol. 169 (2), pp. 359--372 (2006).

[15]

Giffler, B., Thompson, G.: Algorithms for Solving Production Scheduling Problems, Operations Research, Vol. 8, pp. 487--503 (1960).

Digital Library

[16]

Aarts, E., van Laarhoven, P., Lenstra, J., Ulder, N: A Computational Study of Local Search Algorithms for Job--shop Scheduling, ORSA J. on Comput, Vol. 6, No. 2, pp. 118--125 (1994).

[17]

Nowicki, E. and Smutnicki, C.: A Fast Taboo Search Algorithm for the Job--shop Scheduling Problem, Management Science, Vol. 42, No. 6, pp. 797--813 (1996).

Digital Library

Cited By

TSUKAMOTO MHANADA YNAKAO MYAMAMOTO K(2023)Optimization Algorithm with Automatic Adjustment of the Number of Switches in the Order/Radix ProblemIEICE Transactions on Information and Systems10.1587/transinf.2023PAP0004E106.D:12(1979-1987)Online publication date: 1-Dec-2023
https://doi.org/10.1587/transinf.2023PAP0004
Sakai MHanada YOrito Y(2020)Edge Assembly Crossover with Tabu for Traveling Salesman Problem2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185837(1-6)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185837
Kumoyama DHanada YOno K(2019)A New Probabilistic Tree Expression for Probabilistic Model Building Genetic ProgrammingComputational Science/Intelligence and Applied Informatics10.1007/978-3-030-25225-0_9(121-132)Online publication date: 26-Jul-2019
https://doi.org/10.1007/978-3-030-25225-0_9
Show More Cited By

Index Terms

Genetic multi-step search in interpolation and extrapolation domain
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Permutations and combinations

Recommendations

Analysis of the performance of genetic multi-step search in interpolation and extrapolation domain
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

In this paper, we examine overall performances and behaviors of deterministic multi-step search in interpolation / extrapolation domain, dMSXF and dMSMF, using NK model that is one of appropriate models for analyzing fundamental search mechanisms in ...
Two-phase genetic local search algorithm for the multimode resource-constrained project scheduling problem

In this paper, the resource-constrained project scheduling problem with multiple execution modes for each activity is explored. This paper aims to find a schedule of activities such that the makespan of the schedule is minimized subject to the ...
Efficient Local Search with Conflict Minimization: A Case Study of the n-Queens Problem

Backtracking search is frequently applied to solve a constraint-based search problem, but it often suffers from exponential growth of computing time. We present an alternative to backtracking search: local search with conflict minimization. We have ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

July 2007

2313 pages

ISBN:9781595936974

DOI:10.1145/1276958

General Chair:
Hod Lipson
Cornell University, USA

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO07

Sponsor:

GECCO07: Genetic and Evolutionary Computation Conference

July 7 - 11, 2007

London, England

Acceptance Rates

GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
153
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

TSUKAMOTO MHANADA YNAKAO MYAMAMOTO K(2023)Optimization Algorithm with Automatic Adjustment of the Number of Switches in the Order/Radix ProblemIEICE Transactions on Information and Systems10.1587/transinf.2023PAP0004E106.D:12(1979-1987)Online publication date: 1-Dec-2023
https://doi.org/10.1587/transinf.2023PAP0004
Sakai MHanada YOrito Y(2020)Edge Assembly Crossover with Tabu for Traveling Salesman Problem2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185837(1-6)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185837
Kumoyama DHanada YOno K(2019)A New Probabilistic Tree Expression for Probabilistic Model Building Genetic ProgrammingComputational Science/Intelligence and Applied Informatics10.1007/978-3-030-25225-0_9(121-132)Online publication date: 26-Jul-2019
https://doi.org/10.1007/978-3-030-25225-0_9
Kuroda MHanada YOno K(2018)Effectiveness of Multi-step Crossover in Extrapolation Domain for Genetic Programming2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC.2018.00618(3654-3659)Online publication date: Oct-2018
https://doi.org/10.1109/SMC.2018.00618
Sakai MHanada YOrito Y(2018)Edge Assembly Crossover using Multiple Parents for Traveling Salesman Problem2018 Joint 10th International Conference on Soft Computing and Intelligent Systems (SCIS) and 19th International Symposium on Advanced Intelligent Systems (ISIS)10.1109/SCIS-ISIS.2018.00088(474-477)Online publication date: Dec-2018
https://doi.org/10.1109/SCIS-ISIS.2018.00088
Matsumura KHanada YOno K(2017)Probabilistic Model-Based Multistep Crossover Considering Dependency Between Nodes in Tree OptimizationSoftware Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing10.1007/978-3-319-62048-0_13(187-200)Online publication date: 24-Jun-2017
https://doi.org/10.1007/978-3-319-62048-0_13
Matsumura KHanada YOno K(2016)Probabilistic Model-Based Multistep Crossover for Genetic Programming2016 Joint 8th International Conference on Soft Computing and Intelligent Systems (SCIS) and 17th International Symposium on Advanced Intelligent Systems (ISIS)10.1109/SCIS-ISIS.2016.0043(154-159)Online publication date: Aug-2016
https://doi.org/10.1109/SCIS-ISIS.2016.0043
Hanada YMinami KOno KOrito YMuranaka N(2015)A Study on Neighborhood and Temperature in Multi-step Crossover Fusion for Tree StructureProceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems - Volume 210.1007/978-3-319-13356-0_41(519-531)Online publication date: 2015
https://doi.org/10.1007/978-3-319-13356-0_41
Hanada YHosokawa NOno KMuneyasu M(2012)Effectiveness of Multi-step Crossover Fusions in genetic programming2012 IEEE Congress on Evolutionary Computation10.1109/CEC.2012.6256564(1-8)Online publication date: Jun-2012
https://doi.org/10.1109/CEC.2012.6256564
Hanada YTani TLi CMuneyasu M(2011)Effectiveness of genetic multistep searches in interpolation and extrapolation domains on multiobjective optimization2011 IEEE International Conference on Systems, Man, and Cybernetics10.1109/ICSMC.2011.6083716(669-674)Online publication date: Oct-2011
https://doi.org/10.1109/ICSMC.2011.6083716
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents