IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v247y2016i2d10.1007_s10479-015-1848-y.html
   My bibliography  Save this article

Experimental analysis of crossover and mutation operators on the quadratic assignment problem

Author

Listed:
  • Zakir Hussain Ahmed

    (Al Imam Mohammad Ibn Saud Islamic University (IMSIU))

Abstract

In genetic algorithms crossover is the most important operator where pair of chromosomes and crossover site along their common length are selected randomly. Then the information after the crossover site of the parent chromosomes is swapped. On the other hand, mutation operator randomly alters some genes of a chromosome, and thus diversifies the search space. We consider three crossover and ten mutation operators for the genetic algorithms which are then compared for the quadratic assignment problem on some benchmark QAPLIB instances. The experimental study shows the effectiveness of the sequential constructive crossover and the adaptive mutation operators for the problem.

Suggested Citation

  • Zakir Hussain Ahmed, 2016. "Experimental analysis of crossover and mutation operators on the quadratic assignment problem," Annals of Operations Research, Springer, vol. 247(2), pages 833-851, December.
    • Handle: RePEc:spr:annopr:v:247:y:2016:i:2:d:10.1007_s10479-015-1848-y
    DOI: 10.1007/s10479-015-1848-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-015-1848-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-015-1848-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Patrick Mills & Edward Tsang & John Ford, 2003. "Applying an Extended Guided Local Search to the Quadratic Assignment Problem," Annals of Operations Research, Springer, vol. 118(1), pages 121-135, February.
    2. Heffley, Dennis R., 1980. "Decomposition of the Koopmans-Beckmann Problem," Regional Science and Urban Economics, Elsevier, vol. 10(4), pages 571-580, November.
    3. Zakir Hussain Ahmed, 2014. "Improved genetic algorithms for the travelling salesman problem," International Journal of Process Management and Benchmarking, Inderscience Enterprises Ltd, vol. 4(1), pages 109-124.
    4. Paul, G., 2011. "An efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems," European Journal of Operational Research, Elsevier, vol. 209(3), pages 215-218, March.
    5. Burkard, Rainer E. & Bonniger, Tilman, 1983. "A heuristic for quadratic Boolean programs with applications to quadratic assignment problems," European Journal of Operational Research, Elsevier, vol. 13(4), pages 374-386, August.
    6. Zvi Drezner & Peter Hahn & Éeric Taillard, 2005. "Recent Advances for the Quadratic Assignment Problem with Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods," Annals of Operations Research, Springer, vol. 139(1), pages 65-94, October.
    7. A. M. Geoffrion & G. W. Graves, 1976. "Scheduling Parallel Production Lines with Changeover Costs: Practical Application of a Quadratic Assignment/ LP Approach," Operations Research, INFORMS, vol. 24(4), pages 595-610, August.
    8. Huizhen Zhang & Cesar Beltran-Royo & Liang Ma, 2013. "Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers," Annals of Operations Research, Springer, vol. 207(1), pages 261-278, August.
    9. Zakir Hussain Ahmed, 2011. "Multi-parent extension of sequential constructive crossover for the travelling salesman problem," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 11(3), pages 331-342.
    10. Zvi Drezner, 2003. "A New Genetic Algorithm for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 320-330, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Tammy Drezner & Zvi Drezner & Pawel Kalczynski, 2021. "Directional approach to gradual cover: the continuous case," Computational Management Science, Springer, vol. 18(1), pages 25-47, January.
    2. Zvi Drezner & Taly Dawn Drezner, 2020. "Biologically Inspired Parent Selection in Genetic Algorithms," Annals of Operations Research, Springer, vol. 287(1), pages 161-183, April.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Loiola, Eliane Maria & de Abreu, Nair Maria Maia & Boaventura-Netto, Paulo Oswaldo & Hahn, Peter & Querido, Tania, 2007. "A survey for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 657-690, January.
    2. Zvi Drezner & Jack Brimberg & Nenad Mladenović & Said Salhi, 2015. "Solving the planar p-median problem by variable neighborhood and concentric searches," Journal of Global Optimization, Springer, vol. 63(3), pages 501-514, November.
    3. Peter Hahn & J. MacGregor Smith & Yi-Rong Zhu, 2010. "The Multi-Story Space Assignment Problem," Annals of Operations Research, Springer, vol. 179(1), pages 77-103, September.
    4. Ravindra K. Ahuja & Krishna C. Jha & James B. Orlin & Dushyant Sharma, 2007. "Very Large-Scale Neighborhood Search for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 646-657, November.
    5. Jingyang Zhou & Peter E.D. Love & Kok Lay Teo & Hanbin Luo, 2017. "An exact penalty function method for optimising QAP formulation in facility layout problem," International Journal of Production Research, Taylor & Francis Journals, vol. 55(10), pages 2913-2929, May.
    6. James, Tabitha & Rego, Cesar & Glover, Fred, 2009. "A cooperative parallel tabu search algorithm for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 195(3), pages 810-826, June.
    7. Feizollahi, Mohammad Javad & Feyzollahi, Hadi, 2015. "Robust quadratic assignment problem with budgeted uncertain flows," Operations Research Perspectives, Elsevier, vol. 2(C), pages 114-123.
    8. Naomi Graham & Hao Hu & Jiyoung Im & Xinxin Li & Henry Wolkowicz, 2022. "A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2125-2143, July.
    9. Paul, G., 2011. "An efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems," European Journal of Operational Research, Elsevier, vol. 209(3), pages 215-218, March.
    10. Silva, Allyson & Coelho, Leandro C. & Darvish, Maryam, 2021. "Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search," European Journal of Operational Research, Elsevier, vol. 292(3), pages 1066-1084.
    11. Pawel Kalczynski & Jack Brimberg & Zvi Drezner, 2022. "Less is more: discrete starting solutions in the planar p-median problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 34-59, April.
    12. Pritibhushan Sinha, 2009. "Assignment problems with changeover cost," Annals of Operations Research, Springer, vol. 172(1), pages 447-457, November.
    13. Herrán, Alberto & Manuel Colmenar, J. & Duarte, Abraham, 2021. "An efficient variable neighborhood search for the Space-Free Multi-Row Facility Layout problem," European Journal of Operational Research, Elsevier, vol. 295(3), pages 893-907.
    14. Drezner, Zvi, 2005. "The extended concentric tabu for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 160(2), pages 416-422, January.
    15. Krešimir Mihić & Kevin Ryan & Alan Wood, 2018. "Randomized Decomposition Solver with the Quadratic Assignment Problem as a Case Study," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 295-308, May.
    16. Milind Dawande & Srinagesh Gavirneni & Yinping Mu & Suresh Sethi & Chelliah Sriskandarajah, 2010. "On the Interaction Between Demand Substitution and Production Changeovers," Manufacturing & Service Operations Management, INFORMS, vol. 12(4), pages 682-691, September.
    17. Gerald G. Brown & Robert F. Dell & Ray L. Davis & Richard H. Duff, 2002. "Optimizing Plant-Line Schedules and an Application at Hidden Valley Manufacturing Company," Interfaces, INFORMS, vol. 32(3), pages 1-14, June.
    18. Stutzle, Thomas, 2006. "Iterated local search for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1519-1539, November.
    19. Huizhen Zhang & Cesar Beltran-Royo & Liang Ma, 2013. "Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers," Annals of Operations Research, Springer, vol. 207(1), pages 261-278, August.
    20. A.C. Mahasinghe & L.A. Sarathchandra, 2020. "An Optimization Model for Production Planning in the Synthetic Fertilizer Industry," Advances in Decision Sciences, Asia University, Taiwan, vol. 24(3), pages 28-62, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:247:y:2016:i:2:d:10.1007_s10479-015-1848-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.