Top

Soft Computing

Published in:

18-02-2017 | Focus

The Problem Aware Local Search algorithm: an efficient technique for permutation-based problems

Authors: Gabriela F. Minetti, Gabriel Luque, Enrique Alba

Published in: Soft Computing | Issue 18/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this article, we will examine whether the Problem Aware Local Search, an efficient method initially proposed for the DNA Fragment Assembly Problem, can also be used in other application domains and with other optimization problems. The main idea is to maintain the key features of PALS and apply it to different permutation-based combinatorial problems. In order to carry out a comprehensive analysis, we use a wide benchmark of well-known problems with different kinds of variation operators and fitness functions, such as the Quadratic Assignment Problem, the Flow Shop Scheduling Problem, and the Multiple Knapsack Problem. We also discuss the main design alternatives for building an efficient and accurate version of PALS for these problems in a competitive manner. In general, the results show that PALS can achieve high-quality solutions for these problems and do it efficiently.

previous article Real-time processing of k-NN queries over moving objects

next article Crowdsourced healthcare knowledge creation using patients’ health experience-ontologies

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Abdelkafi O, Idoumghar L, Lepagnot J (2015) Distributed multistart hybrid iterative tabu search. In: 2015 IEEE international conference on systems, man, and cybernetics, pp 1962–1967. doi:10.1109/SMC.2015.342

Alba E, Dorronsoro B (2008) Cellular genetic algorithms. Operations research/computer science interfaces. Springer, HeidelbergMATH

Alba E, Luque G (2007) A new local search algorithm for the DNA fragment assembly problem. In: Evolutionary computation in combinatorial optimization, EvoCOP’07, Lecture notes in computer science, vol 4446. Springer, Valencia, pp 1–12

Beasley JE (1990) OR-library: distributing test problems by electronic mail. J Oper Res Soc 41(11):1069–1072CrossRef

Benlic U, Hao JK (2015) Memetic search for the quadratic assignment problem. Expert Syst Appl 42(1):584–595. doi:10.1016/j.eswa.2014.08.011 CrossRef

Bhaba RS, Wilbert EW, Gary LH (1998) Locating sets of identical machines in a linear layout. Ann Oper Res 77:183–207CrossRefMATH

Boyer V, Elkihel M, Baz DE (2009) Heuristics for the 0–1 multidimensional knapsack problem. Eur J Oper Res 199(3):658–664MathSciNetCrossRefMATH

Burkard RE, Karisch SE, Rendl F (1997) Qaplib—a quadratic assignment problem library. J Glob Optim 10(4):391–403MathSciNetCrossRefMATH

Chicano F, Luque G, Alba E (2012) Autocorrelation measures for the quadratic assignment problem. Appl Math Lett 25(4):698–705MathSciNetCrossRefMATH

Colombo G, Mumford C (2005) Comparing algorithms, representations and operators for the multi-objective knapsack problem. In: 2005. The 2005 IEEE congress on evolutionary computation, vol 2, pp 1268–1275. doi:10.1109/CEC.2005.1554836

Coy SP, Golden BL, Runger GC, Wasil EA (1998) See the forest before the trees: fine-tuned learning and its application to the traveling salesman problem. IEEE Trans Syst Man Cybern Part A 28:454–464CrossRef

Dorronsoro B, Alba E, Luque G, Bouvry P (2008) A self-adaptive cellular memetic algorithm for the DNA fragment assembly problem. IEEE Congr Evol Comput 2008:2651–2658

Fogel DB (1988) An evolutionary approach to the traveling salesman problem. Biol Cybern 60:139–144MathSciNetCrossRef

Fogel DB, Atmar J (1990) Comparing genetic operators with Gaussian mutations in simulated evolutionary processes using linear systems. Biol Cybern 63:111–114CrossRef

Fukunaga A, Tazoe S (2009) Combining multiple representations in a genetic algorithm for the multiple knapsack problem. In: 2009. CEC ’09. IEEE congress on evolutionary computation, pp 2423–2430

Iturriaga S, Nesmachnow S, Luna F, Alba E (2015) A parallel local search in CPU/GPU for scheduling independent tasks on large heterogeneous computing systems. J Supercomput 71(2):648–672. doi:10.1007/s11227-014-1315-6 CrossRef

James T, Rego C, Glover F (2009) Multistart tabu search and diversification strategies for the quadratic assignment problem. Trans Syst Man Cybern Part A 39(3):579–596. doi:10.1109/TSMCA.2009.2014556 CrossRef

Koopmans T, Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica 25(1):53–76MathSciNetCrossRefMATH

Martello S, Toth P (1981) Heuristic algorithms for the multiple knapsack problem. Computing 27(2):93–112MathSciNetCrossRefMATH

Mason A, Rönnqvist M (1998) Solution methods for the balancing of jet turbines. Comput Oper Res 24:153–167CrossRefMATH

Minetti G, Alba E (2010) Metaheuristic assemblers of DNA strands: noiseless and noisy cases. In: IEEE congress on evolutionary computation. IEEE, pp 1–8

Minetti G, Leguizamón G, Alba E (2012) SAX: a new and efficient assembler for solving DNA fragment assembly problem. In: JAIIO (ed) 13th Argentine symposium on artificial intelligence, ASAI 2012. SADIO, pp 177–188

Minetti G, Leguizamón G, Alba E (2014) An improved trajectory-based hybrid metaheuristic applied to the noisy DNA fragment assembly problem. Inf Sci 277:273–283MathSciNetCrossRef

Mumford C (2003) Comparing representations and recombination operators for the multi-objective 0/1 knapsack problem. In: 2003. CEC ’03. The 2003 congress on evolutionary computation, vol 2, pp 854–861. doi:10.1109/CEC.2003.1299756

Norris M, Lecavalier L (2010) Evaluating the use of exploratory factor analysis in developmental disability psychological research. J Autism Dev Disord 40(1):8–20. doi:10.1007/s10803-009-0816-2 CrossRef

Polak GG (2005) On a special case of the quadratic assignment problem with an application to storage-and-retrieval devices. Ann Oper Res 138:223–233MathSciNetCrossRefMATH

Pop M, Salzberg S, Shumway M (2002) Genome sequence assembly: algorithms and issues. Computer 35(7):47–54CrossRef

Rego C (1998) Relaxed tours and path ejections for the traveling salesman problem. Eur J Oper Res 106(2):522–538CrossRefMATH

Zhang Q, Sun J, Tsang E (2005) An evolutionary algorithm with guided mutation for the maximum clique problem. IEEE Trans Evol Comput 9(2):192–200CrossRef

Title: The Problem Aware Local Search algorithm: an efficient technique for permutation-based problems
Authors: Gabriela F. Minetti
Gabriel Luque
Enrique Alba
Publication date: 18-02-2017
Publisher: Springer Berlin Heidelberg
Published in: Soft Computing / Issue 18/2017
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-017-2515-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 18/2017

Simulated annealing based GRASP for Pareto-optimal dissimilar paths problem

Stock market trend prediction using AHP and weighted kernel LS-SVM

Crowdsourced healthcare knowledge creation using patients’ health experience-ontologies

A genetic-based effective approach to path-planning of autonomous underwater glider with upstream-current avoidance in variable oceans

Real-time processing of k-NN queries over moving objects

A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy

Premium Partner