[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Use of biased neighborhood structures in multiobjective memetic algorithms

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

Abstract

In this paper, we examine the use of biased neighborhood structures for local search in multiobjective memetic algorithms. Under a biased neighborhood structure, each neighbor of the current solution has a different probability to be sampled in local search. In standard local search, all neighbors of the current solution usually have the same probability because they are randomly sampled. On the other hand, we assign larger probabilities to more promising neighbors in order to improve the search ability of multiobjective memetic algorithms. In this paper, we first explain our multiobjective memetic algorithm, which is a simple hybrid algorithm of NSGA-II and local search. Then we explain its variants with biased neighborhood structures for multiobjective 0/1 knapsack and flowshop scheduling problems. Finally we examine the performance of each variant through computational experiments. Experimental results show that the use of biased neighborhood structures clearly improves the performance of our multiobjective memetic algorithm.

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
£29.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 includes VAT (United Kingdom)

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

  • Caponio A, Cascella GL, Neri F, Salvatore N, Sumner M (2007) A fast adaptive memetic algorithm for online and offline control design of PMSM drives. IEEE Trans Syst Man Cybern B 37: 28–41

    Article  Google Scholar 

  • Coello CAC, Lamont GB (2004) Applications of multi-objective evolutionary algorithms. World Scientific, Singapore

    MATH  Google Scholar 

  • Coello CAC, Van Veldhuizen DA, Lamont GB (2002) Evolutionary algorithms for solving multi-objective problems. Kluwer, Boston

    MATH  Google Scholar 

  • Czyzak P, Jaszkiewicz A (1998) Pareto simulated annealing—a metaheuristic technique for multiple objective combinatorial optimization. J Multi-Criteria Decis Anal 7: 34–47

    Article  MATH  Google Scholar 

  • Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, Chichester

    MATH  Google Scholar 

  • Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6: 182–197

    Article  Google Scholar 

  • Doerner K, Gutjahr WJ, Hartl RF, Strauss C, Stummer C (2004) Pareto ant colony optimization: a metaheuristic approach to multiobjective portfolio selection. Ann Oper Res 131: 79–99

    Article  MATH  MathSciNet  Google Scholar 

  • Fonseca CM, Fleming PJ (1996) On the performance assessment and comparison of stochastic multiobjective optimizers. Lect Notes Comput Sci 1141: 584–593

    Article  Google Scholar 

  • Guo XP, Yang GK, Zhiming W, Huang ZH (2006) A hybrid fine-timed multi-objective memetic algorithm. IEICE Trans Fundam Electron Commun Comput Sci E89A: 790–797

    Google Scholar 

  • Ishibuchi H, Kaige S, Narukawa K (2005) Comparison between Lamarckian and Baldwinian repair on multiobjective 0/1 knapsack problems. Lect Notes Comput Sci 3410: 370–385

    Article  Google Scholar 

  • Ishibuchi H, Murata M (1998) A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Trans Syst Man Cybern C 28: 392–403

    Article  Google Scholar 

  • Ishibuchi H, Narukawa K (2004) Some issues on the implementation of local search in evolutionary multiobjective optimization. Lect Notes Comput Sci 3102: 1246–1258

    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 

  • Jakob W (2006) Towards an adaptive multimeme algorithm for parameter optimisation suiting the engineers’ needs. Lect Notes Comput Sci 4193: 132–141

    Article  Google Scholar 

  • Jaszkiewicz A (2001) Comparison of local search-based meta-heuristics on the multiple objective knapsack problem. Found Comput Decis Sci 26: 99–120

    Google Scholar 

  • Jaszkiewicz A (2002a) Genetic local search for multi-objective combinatorial optimization. Eur J Oper Res 137: 50–71

    Article  MATH  MathSciNet  Google Scholar 

  • Jaszkiewicz A (2002b) On the performance of multiple-objective genetic local search on the 0/1 knapsack problem—a comparative experiment. IEEE Trans Evol Comput 6: 402–412

    Article  Google Scholar 

  • Jaszkiewicz A (2004) On the computational efficiency of multiple objective metaheuristics: the knapsack problem case study. Eur J Oper Res 158: 418–433

    Article  MATH  MathSciNet  Google Scholar 

  • Knowles JD, Corne DW (2000a) M-PAES: a memetic algorithm for multiobjective optimization. In: Proceedings of 2000 congress on evolutionary computation, pp 325–332

  • Knowles JD, Corne DW (2000b) A comparison of diverse approaches to memetic multiobjective combinatorial optimization. In: Proceedings of 2000 genetic and evolutionary computation conference workshop program, pp 103–108

  • Knowles JD, Corne DW (2002) On metrics for comparing non-dominated sets. In: Proceedings of 2002 congress on evolutionary computation, pp 711–716

  • Knowles JD, Corne DW (2005) Memetic algorithms for multi-objective optimization: issues, methods and prospects. In: Hart WE, Krasnogor N, Smith JE(eds) Recent advances in memetic algorithms. Springer, Berlin, pp 313–352

    Chapter  Google Scholar 

  • Krasnogor N, Blackburnem B, Hirst JD, Burke EK (2002) Multimeme algorithms for protein structure prediction. Lect Notes Comput Sci 2439: 769–778

    Article  Google Scholar 

  • Krasnogor N, Smith JE (2005) A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Trans Evol Comput 9: 474–488

    Article  Google Scholar 

  • Moscato P (1999) Memetic algorithms: a short introduction. In: Corne D, Dorigo M, Glover F(eds) New ideas in optimization.. McGraw-Hill, Maidenhead, pp 219–234

    Google Scholar 

  • Murata T, Ishibuchi H, Gen M (2001) Specification of genetic search directions in cellular multi-objective genetic algorithm. Lect Notes Comput Sci 1993: 82–95

    Article  MathSciNet  Google Scholar 

  • Murata T, Ishibuchi H, Tanaka T (1996) Genetic algorithms for flowshop scheduling problems. Comput Ind Eng 30: 1061–1071

    Article  Google Scholar 

  • Murata T, Kaige S, Ishibuchi H (2003) Generalization of dominance relation-based replacement rules for memetic EMO algorithms. Lect Notes Comput Sci 2723: 1233–1244

    Google Scholar 

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

    Article  Google Scholar 

  • Ong YS, Lim MH, Zhu N, Wong KW (2006) Classification of adaptive memetic algorithms: a comparative study. IEEE Trans Syst Man Cybern B 36: 141–152

    Google Scholar 

  • Rahimi-Vahed AR, Mirghorbani SM (2007) A multi-objective particle swarm for a flow shop scheduling problem. J Comb Optim 13: 79–102

    Article  MATH  MathSciNet  Google Scholar 

  • Smith JE (2007) Coevolving memetic algorithms: a review and progress report. IEEE Trans Syst Man Cybern B 37: 6–17

    Article  Google Scholar 

  • Van Veldhuizen DA (1999) Multiobjective evolutionary algorithms: classifications, analyses, and new innovations. PhD dissertation. Air Force Institute of Technology, Dayton, USA

  • Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3: 257–271

    Article  Google Scholar 

  • Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength Pareto evolutionary algorithm. TIK-Report 130, Swiss Federal Institute of Technology (ETH) Zurich, Zurich, Switzerland

  • Zitzler E, Thiele L, Laumanns M, Fonseca CM, da Fonseca VG (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7: 117–132

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Intelligent Systems, Graduate School of Engineering, Osaka Prefecture University, 1-1 Gakuen-cho, Naka-ku, Sakai, Osaka, 599-8531, Japan

    Hisao Ishibuchi, Yasuhiro Hitotsuyanagi, Noritaka Tsukamoto & Yusuke Nojima

Authors
  1. Hisao Ishibuchi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yasuhiro Hitotsuyanagi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Noritaka Tsukamoto
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yusuke Nojima
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hisao Ishibuchi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ishibuchi, H., Hitotsuyanagi, Y., Tsukamoto, N. et al. Use of biased neighborhood structures in multiobjective memetic algorithms. Soft Comput 13, 795–810 (2009). https://doi.org/10.1007/s00500-008-0352-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-008-0352-6

Keywords