Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Article type: Research Article
Authors: Ishibuchi, Hisao | Kaige, Shiori
Affiliations: Dept. of Industrial Engineering, Osaka Prefecture University, 1-1 Gakuen-cho, Sakai, Osaka 599-8531, Japan. hisaoi@ie.osakafu-u.ac.jp, shiori@ie.osakafu-u.ac.jp
Abstract: The aim of this paper is to propose a simple but powerful multiobjective hybrid genetic algorithm and to examine its search ability through computational experiments on commonly used test problems in the literature. We first propose a new multiobjective hybrid genetic algorithm, which is designed by combining local search with an EMO (evolutionary multiobjective optimization) algorithm. In the design of our algorithm, we try to make its algorithmic complexity as simple as possible so that it can be easily understood, easily implemented and easily executed within short CPU time. At the same time, we try to maximize its search ability. Our algorithm makes use of advantages of both EMO and local search for achieving high search ability without increasing its algorithmic complexity. For example, each solution is evaluated based on Pareto ranking and the concept of crowding as in many EMO algorithms. On the other hand, a weighted scalar fitness function is used for efficiently executing local search. A kind of elitism is also implemented using Pareto ranking in the process of generation update. Through computational experiments on multiobjective 0/1 knapsack problems, we examine the search ability of four variants of our algorithm with various parameter specifications. Those variants are different from each other in the implementation of parent selection and local search. While some variants use the weighted scalar fitness function only for local search, others use it for both local search and parent selection. One variant uses Pareto ranking instead of the weighted scalar fitness function in local search. In addition to the comparison among those four variants, our algorithm is also compared with well-known EMO algorithms (i.e., SPEA of Zitzler & Thiele and NSGA-II of Deb et al.) and memetic EMO algorithms (i.e., M-PAES of Knowles & Corne and MOGLS of Jaszkiewicz). We also examine the effect of the balance between genetic search and local search on the search ability of our algorithm using two parameters: a local search application probability and a local search stopping condition. Moreover we demonstrate the usefulness of a weighted scalar fitness function-based greedy repair procedure in the application of memetic EMO algorithms to multiobjective 0/1 knapsack problems. Our experimental results by various EMO algorithms show that there exists a clear tradeoff between CPU time and the quality of solution sets obtained by each algorithm. Since our algorithm is very simple, it can be efficiently executed. As a result, our algorithm outperforms many EMO and memetic EMO algorithms in terms of CPU time for large test problems while it does not always outperform them in terms of the quality of obtained solution sets.
Keywords: evolutionary multiobjective optimization, memetic algorithms, genetic algorithms, local search
DOI: 10.3233/HIS-2004-11-205
Journal: International Journal of Hybrid Intelligent Systems, vol. 1, no. 1-2, pp. 22-35, 2004
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl