research-article

Geometric Particle Swarm Optimization for Multi-objective Optimization Using Decomposition

Authors:

Saul Zapotecas-Martinez,

Alberto Moraglio,

Hernan E. Aguirre,

Kiyoshi TanakaAuthors Info & Claims

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Pages 69 - 76

https://doi.org/10.1145/2908812.2908880

Published: 20 July 2016 Publication History

Abstract

Multi-objective evolutionary algorithms (MOEAs) based on decomposition are aggregation-based algorithms which transform a multi-objective optimization problem (MOP) into several single-objective subproblems. Being effective, efficient, and easy to implement, Particle Swarm Optimization (PSO) has become one of the most popular single-objective optimizers for continuous problems, and recently it has been successfully extended to the multi-objective domain. However, no investigation on the application of PSO within a multi-objective decomposition framework exists in the context of combinatorial optimization. This is precisely the focus of the paper. More specifically, we study the incorporation of Geometric Particle Swarm Optimization (GPSO), a discrete generalization of PSO that has proven successful on a number of single-objective combinatorial problems, into a decomposition approach. We conduct experiments on many-objective 1/0 knapsack problems i.e. problems with more than three objectives functions, substantially harder than multi-objective problems with fewer objectives. The results indicate that the proposed multi-objective GPSO based on decomposition is able to outperform two version of the well-know MOEA based on decomposition (MOEA/D) and the most recent version of the non-dominated sorting genetic algorithm (NSGA-III), which are state-of-the-art multi-objec\-tive evolutionary approaches based on decomposition.

References

[1]

D. Agrafiotis and W. Cedeño. Feature selection for structure-activity correlation using binary particle swarms. Journal of Medicinal Chemistry, 45(5):1098--1107, 2002.

[2]

E. Alba, J. Garcıa-Nieto, L. Jourdan, and E.-G. Talbi. Gene selection in cancer classification using pso/svm and ga/svm hybrid algorithms. In CEC'07, pages 284--290. IEEE press, 2007.

[3]

E. Alba, J. Garcıa-Nieto, J. Taheri, and A. Zomaya. New research in nature inspired algorithms for mobility management in gsm networks. In Applications of Evolutionary Computing, pages 1--10. Springer, 2008.

Digital Library

[4]

C. E. Bonferroni. Teoria statistica delle classi e calcolo delle probabilita. Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commerciali di Firenze, 8:3--62, 1936.

[5]

V. J. Bowman Jr. On the relationship of the tchebycheff norm and the efficient frontier of multiple-criteria objectives. In Lecture Notes in Economics and Mathematical System, volume 130, pages 76--86. 1976.

[6]

I. Chaman Garcia, C. Coello Coello, and A. Arias-Montano. Mopsohv: A new hypervolume-based multi-objective particle swarm optimizer. In CEC'14, pages 266--273, July 2014.

[7]

M. Clerc. Discrete particle swarm optimization, illustrated by the traveling salesman problem. In New Optimization Techniques in Engineering, pages 219--239. Springer, 2004.

[8]

C. A. Coello Coello, G. B. Lamont, and D. A. Van Veldhuizen. Evolutionary Algorithms for Solving Multi-Objective Problems. Springer, New York, second edition, September 2007. ISBN 978-0--387--33254--3.

[9]

K. Deb and H. Jain. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints. IEEE TEVC, 18(4):577--601, August 2014.

[10]

M. Ehrgott. Multicriteria Optimization. Springer, Berlin, 2nd edition edition, June 2005.

Digital Library

[11]

J. Garcıa-Nieto and E. Alba. Parallel multi-swarm optimizer for gene selection in dna microarrays. Applied Intelligence, 37(2):255--266, 2012.

Digital Library

[12]

A. Jaszkiewicz. On the Performance of Multiple-Objective Genetic Local Search on the 0/1 Knapsack Problem--A Comparative Experiment. IEEE TEVC, 6(4):402--412, August 2002.

Digital Library

[13]

J. Kennedy and R. C. Eberhart. Particle swarm optimization. In Proceedings of the IEEE International Conference on Neural Networks, pages 1942--1948, 1995.

[14]

J. Kennedy and R. C. Eberhart. A discrete binary version of the particle swarm algorithm. IEEE Transactions on Systems, Man, and Cybernetics, 5:4104--4108, 1997.

[15]

F. Li, J. Liu, S. Tan, and X. Yu. R2-mopso: A multi-objective particle swarm optimizer based on r2-indicator and decomposition. In Evolutionary Computation (CEC), 2015 IEEE Congress on, pages 3148--3155, May 2015.

[16]

H. Li and Q. Zhang. Multiobjective Optimization Problems With Complicated Pareto Sets, MOEA/D and NSGA-II. IEEE TEVC, 13(2):284--302, April 2009.

Digital Library

[17]

K. Miettinen. Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, Boston, Massachuisetts, 1999.

[18]

C. Mohan and B. Al-Kazemi. Discrete particle swarm optimization. In workshop on particle swarm optimization, Indianapolis, 2001. Purdue School of Engineering and Technology, IUPUI.

[19]

A. Moraglio, C. D. Chio, and R. Poli. Geometric particle swarm optimization. In European Conference on Genetic Programming, pages 125--136, 2007.

Digital Library

[20]

A. Moraglio and J. Togelius. Geometric pso for the sudoku puzzle. In GECCO'07, pages 118--125, 2007.

Digital Library

[21]

N. A. Moubayed, A. Petrovski, and J. A. W. McCall. A novel smart multi-objective particle swarm optimisation using decomposition. In PPSN (2), pages 1--10, 2010.

Digital Library

[22]

G. Pampara, A. Engelbrecht, and N. Franken. Binary differential evolution. In IEEE Congress on Evolutionary Computation, 2006.

[23]

W. Peng and Q. Zhang. A decomposition-based multi-objective particle swarm optimization algorithm for continuous optimization problems. In GrC'08, pages 534 --537, 2008.

[24]

R. Purshouse and P. Fleming. On the evolutionary optimization of many conflicting objectives. Evolutionary Computation, IEEE Transactions on, 11(6):770--784, Dec 2007.

Digital Library

[25]

J. Qin, Y.-x. Yin, and X.-j. Ban. Hybrid discrete particle swarm algorithm for graph coloring problem. Journal of Computers, 6(6):1175--1182, 2011.

[26]

M. Reyes-Sierra and C. A. Coello Coello. Multi-Objective Particle Swarm Optimizers: A Survey of the State-of-the-Art. International Journal of Computational Intelligence Research, 2(3):287--308, 2006.

[27]

H. Scheffé. Experiments With Mixtures. Journal of the Royal Statistical Society, Series B (Methodological), 20(2):344--360, 1958.

[28]

E.-G. Talbi, L. Jourdan, J. Garcia-Nieto, and E. Alba. Comparison of population based metaheuristics for feature selection: Application to microarray data classification. In Computer Systems and Applications, 2008. AICCSA 2008. IEEE/ACS International Conference on, pages 45--52. IEEE, 2008.

Digital Library

[29]

J. Togelius, R. D. Nardi, and A. Moraglio. Geometric pso+gp = particle swarm programming. In Proceedings of the Congress on Evolutionary Comptutation (CEC), 2008.

[30]

F. Wilcoxon. Individual comparisons by ranking methods. Biometrics Bulletin, 1(6):80--83, 1945.

[31]

Y. yan Tan, Y. chang Jiao, H. Li, and X. kuan Wang. Moea/d+ uniform design: A new version of moea/d for optimization problems with many objectives. Computers & Operations Research, 40(6):1648--1660, 2013.

Digital Library

[32]

S. Zapotecas-Martínez, H. E. Aguirre, K. Tanaka, and C. A. Coello Coello. On the Low-Dyscrepancy Sequences and Their use in MOEA/D for High-Dimensional Objective Spaces. In CEC'15, pages 2835--2842, Sendai, Japan, May 2015.

[33]

S. Zapotecas Martínez and C. A. Coello Coello. A Multi-objective Particle Swarm Optimizer Based on Decomposition. In GECCO'11, pages 69--76, Dublin, Ireland, July 2011. ACM Press.

Digital Library

[34]

Q. Zhang and H. Li. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE TEVC, 11(6):712--731, December 2007.

Digital Library

[35]

Q. Zhang, A. Zhou, S. Zhao, P. N. Suganthan, W. Liu, and S. Tiwari. Multiobjective Optimization Test Instances for the CEC 2009 Special Session and Competition. Technical Report CES-487, University of Essex and Nanyang Technological University, 2008.

[36]

E. Zitzler, K. Deb, and L. Thiele. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2):173--195, Summer 2000.

Digital Library

[37]

E. Zitzler and L. Thiele. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE TEVC, 3(4):257--271, November 1999.

Digital Library

Cited By

Zapotecas-Martínez SMenchaca-Méndez A(2020)On the Performance of Generational and Steady-State MOEA/D in the Multi-Objective 0/1 Knapsack Problem2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185715(1-8)Online publication date: 19-Jul-2020
https://dl.acm.org/doi/10.1109/CEC48606.2020.9185715
Omran SEl-Behaidy WYoussif A(2020)Decomposition Based Multi-objectives Evolutionary Algorithms Challenges and CircumventionIntelligent Computing10.1007/978-3-030-52246-9_6(82-93)Online publication date: 4-Jul-2020
https://doi.org/10.1007/978-3-030-52246-9_6
Cai CLiu SWang LYang BChen ZZhou JTakadama K(2018)Optimizing floating centroids method neural network classifier using dynamic multilayer particle swarm optimizationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205573(394-401)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205573

Index Terms

Geometric Particle Swarm Optimization for Multi-objective Optimization Using Decomposition
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Discrete space search

Recommendations

Particle Swarm Optimization Based on Linear Assignment Problem Transformations
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Particle swarm optimization (PSO) algorithms have been widely used to solve a variety of optimization problems. Their success has motivated researchers to extend the use of these techniques to the multi-objective optimization field. However, most of ...
A Novel Particle Swarm Optimization Algorithm for Multi-Objective Combinatorial Optimization Problem

The Combinatorial problems are real world decision making problem with discrete and disjunctive choices. When these decision making problems involve more than one conflicting objective and constraint, it turns the polynomial time problem into NP-hard. ...
Movement Strategies for Multi-Objective Particle Swarm Optimization

Particle Swarm Optimization (PSO) is one of the most effective metaheuristics algorithms, with many successful real-world applications. The reason for the success of PSO is the movement behavior, which allows the swarm to effectively explore the search ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

July 2016

1196 pages

ISBN:9781450342063

DOI:10.1145/2908812

Editor:
Tobias Friedrich
Hasso Plattner Institute
,
General Chair:
Frank Neumann
University of Adelaide
,
Program Chair:
Andrew M. Sutton
Hasso Plattner Institute

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '16

Sponsor:

SIGEVO

GECCO '16: Genetic and Evolutionary Computation Conference

July 20 - 24, 2016

Colorado, Denver, USA

Acceptance Rates

GECCO '16 Paper Acceptance Rate 137 of 381 submissions, 36%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
198
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zapotecas-Martínez SMenchaca-Méndez A(2020)On the Performance of Generational and Steady-State MOEA/D in the Multi-Objective 0/1 Knapsack Problem2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185715(1-8)Online publication date: 19-Jul-2020
https://dl.acm.org/doi/10.1109/CEC48606.2020.9185715
Omran SEl-Behaidy WYoussif A(2020)Decomposition Based Multi-objectives Evolutionary Algorithms Challenges and CircumventionIntelligent Computing10.1007/978-3-030-52246-9_6(82-93)Online publication date: 4-Jul-2020
https://doi.org/10.1007/978-3-030-52246-9_6
Cai CLiu SWang LYang BChen ZZhou JTakadama K(2018)Optimizing floating centroids method neural network classifier using dynamic multilayer particle swarm optimizationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205573(394-401)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205573

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten