Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

A case study of memetic algorithms for constraint optimization

  • Focus
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

There is a variety of knapsack problems in the literature. Multidimensional 0–1 knapsack problem (MKP) is an NP-hard combinatorial optimization problem having many application areas. Many approaches have been proposed for solving this problem. In this paper, an empirical investigation of memetic algorithms (MAs) that hybridize genetic algorithms (GAs) with hill climbing for solving MKPs is provided. Two distinct sets of experiments are performed. During the initial experiments, MA parameters are tuned. GA and four MAs each using a different hill climbing method based on the same configuration are evaluated. In the second set of experiments, a self-adaptive (co-evolving) multimeme memetic algorithm (MMA) is compared to the best MA from the parameter tuning experiments. MMA utilizes the evolutionary process as a learning mechanism for choosing the appropriate hill climbing method to improve a candidate solution at a given time. Two well-known MKP benchmarks are used during the experiments.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Alkan A, Ozcan E (2003) Memetic algorithms for timetabling. In: Proc of IEEE congress on evo comp, pp 1796–1802

  • Burke E, Cowling P, Causmaecker PD, Berge GV (2001) A memetic approach to the nurse rostering problem. Appl Intell 15(3): 199–214

    Article  MATH  Google Scholar 

  • Burke EK, Kendall G, Newall J, Hart E, Ross P, Schulenburg S (2003) Hyperheuristics: an emerging direction in modern search technology. Handbook of metaheuristics. International Series in OR & Management Science, vol 57. Kluwer, Dordrecht, pp 457–474

  • Burke EK, Smith AJ (2000) Hybrid evolutionary techniques for the maintenance scheduling problem. IEEE Trans PS 15(1): 122–128

    Google Scholar 

  • Chu PC, Beasley JE (1998) A genetic algorithm for the multidimensional knapsack problem. J Heuristics 4(1): 63–86

    Article  MATH  Google Scholar 

  • Cleary R, O’Neill M (2005) An attribute grammar decoder for the 01 multiconstrained knapsack problem. LNCS 3448: 34–45

    Google Scholar 

  • Cotta C, Troya JM (1998) A hybrid genetic algorithm for the 0-1 multiple knapsack problem. In: Artificial NN and GAs, vol 3. Springer, Heidelberg, pp 251–255

  • Cowling P, Kendall G, Soubeiga E (2000) A hyperheuristic approach to scheduling a sales summit. In: Selected papers from 3rd int conf on PATAT. LNCS, vol 2079, pp 176–190

  • Davis L (1991) Bit climbing, representational bias, and test suite design. In: Proc of the 4th int conf on GAs, pp 18–23

  • Ersoy E, Özcan E, Uyar Ş (2007) Memetic algorithms and hyperhill-climbers. In: Proc of the 3rd multidisciplinary int conf on scheduling: theory and applications, pp 159–166

  • Eshelman LJ (1991) The CHC adaptive search algorithm: how to have safe search when engaging in nontraditional genetic recombination. In: Rawlins GJE(eds) Foundations of genetic algorithms. Morgan Kaufmann, Menlo Park, pp 265–283

    Google Scholar 

  • França PM, Mendes A, Moscato P (2001) A memetic algorithm for the total tardiness single machine scheduling problem. EJOR 132(1): 224–242

    Article  MATH  Google Scholar 

  • Freville A (2004) The multidimensional 0–1 knapsack problem: an overview. EJOR 155(1): 1–21

    Article  MATH  MathSciNet  Google Scholar 

  • Freville A, Plateau G (1994) An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem. Discrete Appl Math 49: 189–212

    Article  MATH  MathSciNet  Google Scholar 

  • Garey MR, Johnson DJ (1979) Computers and intractability: a guide to the theory of np-completeness. W.H. Freeman, San Francisco

    MATH  Google Scholar 

  • Gavish B, Pirkul H (1985) Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Math Program 31: 78–105

    Article  MATH  MathSciNet  Google Scholar 

  • Glover F, Kochenberger GA (1996) Critical event tabu search for multidimensional knapsack problems. In: Osman IH, Kelly JP(eds) Meta-heuristics: theory and applications. Kluwer, Dordrecht, pp 407–427

    Google Scholar 

  • Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading

    MATH  Google Scholar 

  • Gottlieb J (1999) Evolutionary algorithms for constraint optimization problems. Dissertation, Institut für Informatik der Technischen Universitat Clausthal

  • Hancock PJB (1999) Selection methods for evolutionary algorithms. In: Chambers L (ed) Practical handbook of genetic algorithms, New Frontiers, vol 2, Chap. 3, pp 67–93

  • Hembecker F, Lopes HS, Godoy JrW (2007) Particle swarm optimization for the multidimensional knapsack problem. LNCS Adapt Nat Comput Algorithms 4431: 358–365

    Article  Google Scholar 

  • Holland JH (1975) Adaptation in natural and artificial systems. Univ. Mich. Press, Ann Arbor

    Google Scholar 

  • Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evol Comput 7: 204–223

    Article  Google Scholar 

  • Khuri S, Back T, Heitkotter J (1994) The zero/one multiple knapsack problem and genetic algorithms. In: Proceedings of the ACM symposium of applied comp, pp 188–193

  • Krasnogor N (2002) Studies on the theory and design space of memetic algorithms. PhD Thesis, University of the West of England, Bristol

  • Krasnogor N, Smith JE (2001) Emergence of profitable search strategies based on a simple inheritance mechanism. In: Proc of the genetic and evolutionary comp. conf., pp 432–439

  • Linqiang P, Martín-Vide C (2005) Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes. J Par Dist Comput (65) 12: 1578–1584

    Google Scholar 

  • Magazine MJ, Oguz O (1984) A heuristic algorithm for the multidimensional zero-one knapsack problem. EJOR 16: 319–326

    Article  MATH  MathSciNet  Google Scholar 

  • Merz P, Freisleben B (2000) Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans Evol Comput 4(4): 337–352

    Article  Google Scholar 

  • Mitchell M, Forrest S (1997) Fitness landscapes: royal road functions. In: Baeck T, Fogel D, Michalewicz Z(eds) Handbook of evolutionary computation, vol B2.7. Institute of Physics Publishing, Philadelphia and Bristol UK, pp 1–25

    Google Scholar 

  • Moscato P, Norman MG (1992) A memetic approach for the traveling salesman problem implementation of a computational ecology for combinatorial optimization on message-passing systems. In: Valero M, Onate E, Jane M, Larriba JL, Suarez B (eds) Parallel computing and transputer applications, IOS Press, pp 177–186

  • Neri F, Toivanen J, Cascella GL, Ong YS (2007) An adaptive multimeme algorithm for designing HIV multidrug therapies. IEEE-ACM Trans Comput Bio Bioinf 4(2): 264–278

    Article  Google Scholar 

  • Ochoa G (2006) Error thresholds in genetic algorithms. Evol Comp J 14(2): 157–182

    Article  MathSciNet  Google Scholar 

  • Ong YS, Keane AJ (2004) Meta-lamarckian learning in memetic algorithms. IEEE Trans Evol Comp 8(2): 99–110

    Article  Google Scholar 

  • Ong YS, Lim MH, Ning Z, Wong KW (2006) Classification of adaptive memetic algorithms: a comparative study. IEEE Trans SMC BC 36(1): 141–152

    Google Scholar 

  • Ozcan E (2006) An empirical investigation on memes, self-generation and nurse rostering. In: Proc of the 6th int conf on the practice and theory of automated timetabling, pp 246–263

  • Ozcan E (2005) Memetic Algorithms for Nurse Rostering, ISCIS 2005. LNCS, vol 3733, pp 482–492

  • Ozcan E, Bilgin B, Korkmaz EE (2008) A comprehensive analysis of hyper-heuristics. Intell Data Anal 12(1): 3–23

    Google Scholar 

  • Ozcan E, Mohan CK (1997) Partial shape matching using genetic algorithms. Pattern Recogn Lett 18: 987–992

    Article  Google Scholar 

  • Ozcan E, Onbasioglu E (2007) Memetic algorithms for parallel code optimization. Int J Parallel Prog 35(1): 33–61

    Article  Google Scholar 

  • Pirkul H (1987) A heuristic solution procedure for the multiconstraint zero-one knapsack problem. Naval Res Logist 34: 161–172

    Article  MATH  Google Scholar 

  • Pisinger D (1995) Algorithms for knapsack problems. PhD thesis, DIKU, University of Copenhagen, Report 95/1

  • Reeves C (1993) Using genetic algorithms with small populations. In: Forrest S (ed) Proc of the 5th int conf on GAs, pp 92–99

  • Radcliffe NJ, Surry PD (1994) Formal memetic algorithms. Evolutionary Computing: AISB Workshop. LNCS, vol 865. Springer, Heidelberg, pp 1–16

  • Smith J, Fogarty TC (1997) Operator and parameter adaptation in genetic algorithms. Soft Comput 1(2): 81–87

    Article  Google Scholar 

  • Syswerda G (1989) Uniform crossover in genetic algorithms. In: Schaffer J(eds) Proc of the 3rd int conf on GAs. Morgan Kaufmann Publishers, Los Altos, pp 2–9

    Google Scholar 

  • Tang J, Lim MH, Ong YS (2007) Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput 11(9): 873–888

    Article  Google Scholar 

  • Tavares J, Francisco BP, Costa E (2006) The role of representation on the multidimensional knapsack problem by means of fitness landscape analysis. In: Proc. of the Congress of Evol Comp, pp 2307–2314

  • Tavares J, Francisco BP, Costa E (2007) Multidimensional knapsack problem: the influence of representation. CISUC Technical Report TR 2007/003. ISSN 0874-338X

  • Volgenant A, Zoon JA (1990) An improved heuristic for multidimensional 0-1 knapsack problems. JORS 41: 963–970

    MATH  Google Scholar 

  • Wolpert D, MacReady WG (1997) No free lunch theorems for optimization. IEEE Trans Evo Comp 1(1): 67–82

    Article  Google Scholar 

  • Zhou Z, Ong YS, Lim MH, Lee BS (2007) Memetic algorithm using multi-surrogates for computationally expensive optimization problems. Soft Comput 11(10): 957–971

    Article  Google Scholar 

  • Zhu Z, Ong YS, Dash M (2007) Wrapper-filter feature selection algorithm using a memetic framework. IEEE Trans SBC BC 37(1): 70–76

    Google Scholar 

  • Zhu Z, Ong YS, Wong KW, Lim MH (2003) Choice of memes in memetic algorithm. In: Proceedings of the 2nd international conference on computational intelligence, robotics and autonomous systems

Download references

Author information

Authors and Affiliations

  1. Department of Computer Engineering, Yeditepe University, Inönü Cad. Kayışdağı Mah., 34755, Kadıköy, Istanbul, Turkey

    Ender Özcan & Can Başaran

Authors
  1. Ender Özcan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Can Başaran
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ender Özcan.

Additional information

E. Özcan is currently on leave of absence and working as a research fellow in the ASAP group at the School of Computer Science, University of Nottingham, exo@cs.nott.ac.uk.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Özcan, E., Başaran, C. A case study of memetic algorithms for constraint optimization. Soft Comput 13, 871–882 (2009). https://doi.org/10.1007/s00500-008-0354-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-008-0354-4

Keywords

Search

Navigation