Particle Swarm Optimization: Fundamental Study and its Application to Optimization and to Jetty Scheduling Problems

Johann Sienz, Mauro Innocente

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

The advantages of evolutionary algorithms with respect to traditional methods have been much discussed in the literature. While particle swarm optimizers share such advantages, they outperform evolutionary algorithms in that they require lower computational cost and easier implementation, involving no operator design and few coefficients to be tuned. However, even marginal variations in the settings of these coefficients greatly influence the dynamics of the swarm.
This paper does not intend to study the tuning of these coefficients. Instead, general-purpose settings are taken from previous studies, and virtually the same algorithm is used to optimize a variety of notably different problems.
Following a short review of optimization, the algorithm is tested on a suite of unconstrained benchmark functions, so that its performance is independent from the constraint-handling techniques. Thus, the settings of the coefficients in the particles' velocity update equation can be evaluated. The results were compared to those of other authors, showing the robustness of our settings.
Once the algorithm has proved itself able to cope with complex, unconstrained functions, it must be tested on a suite of constrained benchmark problems. This is very important because constraints affect the normal dynamics of the swarm. Three different constraint-handling techniques were implemented: the penalization, preserving feasibility, and bisection methods. As much as very good results were obtained, there is room for improvement in each of these techniques. Again, the results were either competitive with, or outperforming those of other authors.
For both suites of constrained and unconstrained benchmark problems, different neighbourhood sizes were considered, always keeping a ring topology. It was concluded that the appropriate balance between exploration and exploitation can be controlled by the neighbourhood sizes, and by the swarm size (for a given number of function evaluations), while keeping the same general-purpose settings for the coefficients in the particles' velocity update equation.
While the use of the binary versions of the method to handle discrete variables is an interesting line for future research, the algorithm was adapted to discrete problems by simply rounding-off the particles' trajectories. Thus, the continuous algorithm was kept virtually unmodified. In turn, the jetty scheduling problem was set as a search problem by generating a discrete search-space where the object variables (i.e. the dimensions of the space) represent shipments, whereas the discrete values that the variables are allowed to take stand for the berths where the shipments are to be served. Every solution returned by the PSO algorithm per se consists of a list of shipments to be served on each berth. Their order is handled deterministically at present, giving priority only according to their estimated time of arrival (ETA).
In summary, our research follows three separate lines: unconstrained PSO algorithm, constrained PSO algorithm, and PSO-based jetty scheduler. The next steps with regard to the first line consist of studying the appropriate setting of the swarm size in relation to the number of dimensions of the search-space (and perhaps to the feasibility ratio and multi-modality of the problem) for a given number of permitted function evaluations. The degree of locality of the method is another aspect that affects the balance between exploration and exploitation, critical for the performance of the algorithm. With regard to the constrained PSO algorithm, further steps will be focused on the development of our current three constraint-handling techniques, as well as on the development of others. For instance, the self-adaptation of penalization coefficients and the development of techniques to delay the loss of particles' momentum and to generate initial feasible solutions other than brute force are promising lines of research for further improvement. Finally, further steps in the development of our PSO-based jetty scheduler consist of designing more developed priority rules, incorporating the demurrage rate to the current rules based on the ETAs only; testing binary versions of the PSO algorithm for the same model of the problem; considering other constraint-handling techniques such as the penalization method; including the minimization of the makespan as a secondary objective; considering embedding an independent optimization algorithm on every berth to optimize the order in which the shipments allocated are to be served; and finally considering solving the jetty scheduling problem as an instance of the general job shop scheduling problem, and therefore using other PSO-based approaches recently published in the literature.
Original languageEnglish
Title of host publicationTrends in Engineering Computational Technology
EditorsM. Papadrakakis, B.H.V. Topping
Place of PublicationStirlingshire
PublisherSaxe-Coburg Publications
Pages103-126
Number of pages24
ISBN (Print) 978-1-874672-40-1
DOIs
Publication statusPublished - 2008
Externally publishedYes

Publication series

NameComputational Science, Engineering & Technology Series
PublisherSaxe-Coburg Publications
Volume20
ISSN (Print)1759-3158

Fingerprint

Particle swarm optimization (PSO)
Scheduling
Function evaluation
Evolutionary algorithms
Momentum
Tuning
Trajectories
Topology

Keywords

  • particle swarms
  • artificial intelligence
  • optimization
  • scheduling

Cite this

Sienz, J., & Innocente, M. (2008). Particle Swarm Optimization: Fundamental Study and its Application to Optimization and to Jetty Scheduling Problems. In M. Papadrakakis, & B. H. V. Topping (Eds.), Trends in Engineering Computational Technology (pp. 103-126). (Computational Science, Engineering & Technology Series; Vol. 20). Stirlingshire: Saxe-Coburg Publications. https://doi.org/10.4203/csets.20.6

Particle Swarm Optimization: Fundamental Study and its Application to Optimization and to Jetty Scheduling Problems. / Sienz, Johann; Innocente, Mauro.

Trends in Engineering Computational Technology. ed. / M. Papadrakakis; B.H.V. Topping. Stirlingshire : Saxe-Coburg Publications, 2008. p. 103-126 (Computational Science, Engineering & Technology Series; Vol. 20).

Research output: Chapter in Book/Report/Conference proceedingChapter

Sienz, J & Innocente, M 2008, Particle Swarm Optimization: Fundamental Study and its Application to Optimization and to Jetty Scheduling Problems. in M Papadrakakis & BHV Topping (eds), Trends in Engineering Computational Technology. Computational Science, Engineering & Technology Series, vol. 20, Saxe-Coburg Publications, Stirlingshire, pp. 103-126. https://doi.org/10.4203/csets.20.6
Sienz J, Innocente M. Particle Swarm Optimization: Fundamental Study and its Application to Optimization and to Jetty Scheduling Problems. In Papadrakakis M, Topping BHV, editors, Trends in Engineering Computational Technology. Stirlingshire: Saxe-Coburg Publications. 2008. p. 103-126. (Computational Science, Engineering & Technology Series). https://doi.org/10.4203/csets.20.6
Sienz, Johann ; Innocente, Mauro. / Particle Swarm Optimization: Fundamental Study and its Application to Optimization and to Jetty Scheduling Problems. Trends in Engineering Computational Technology. editor / M. Papadrakakis ; B.H.V. Topping. Stirlingshire : Saxe-Coburg Publications, 2008. pp. 103-126 (Computational Science, Engineering & Technology Series).
@inbook{2b93b28ca7934fc19772ad90c678873c,
title = "Particle Swarm Optimization: Fundamental Study and its Application to Optimization and to Jetty Scheduling Problems",
abstract = "The advantages of evolutionary algorithms with respect to traditional methods have been much discussed in the literature. While particle swarm optimizers share such advantages, they outperform evolutionary algorithms in that they require lower computational cost and easier implementation, involving no operator design and few coefficients to be tuned. However, even marginal variations in the settings of these coefficients greatly influence the dynamics of the swarm.This paper does not intend to study the tuning of these coefficients. Instead, general-purpose settings are taken from previous studies, and virtually the same algorithm is used to optimize a variety of notably different problems.Following a short review of optimization, the algorithm is tested on a suite of unconstrained benchmark functions, so that its performance is independent from the constraint-handling techniques. Thus, the settings of the coefficients in the particles' velocity update equation can be evaluated. The results were compared to those of other authors, showing the robustness of our settings.Once the algorithm has proved itself able to cope with complex, unconstrained functions, it must be tested on a suite of constrained benchmark problems. This is very important because constraints affect the normal dynamics of the swarm. Three different constraint-handling techniques were implemented: the penalization, preserving feasibility, and bisection methods. As much as very good results were obtained, there is room for improvement in each of these techniques. Again, the results were either competitive with, or outperforming those of other authors.For both suites of constrained and unconstrained benchmark problems, different neighbourhood sizes were considered, always keeping a ring topology. It was concluded that the appropriate balance between exploration and exploitation can be controlled by the neighbourhood sizes, and by the swarm size (for a given number of function evaluations), while keeping the same general-purpose settings for the coefficients in the particles' velocity update equation.While the use of the binary versions of the method to handle discrete variables is an interesting line for future research, the algorithm was adapted to discrete problems by simply rounding-off the particles' trajectories. Thus, the continuous algorithm was kept virtually unmodified. In turn, the jetty scheduling problem was set as a search problem by generating a discrete search-space where the object variables (i.e. the dimensions of the space) represent shipments, whereas the discrete values that the variables are allowed to take stand for the berths where the shipments are to be served. Every solution returned by the PSO algorithm per se consists of a list of shipments to be served on each berth. Their order is handled deterministically at present, giving priority only according to their estimated time of arrival (ETA).In summary, our research follows three separate lines: unconstrained PSO algorithm, constrained PSO algorithm, and PSO-based jetty scheduler. The next steps with regard to the first line consist of studying the appropriate setting of the swarm size in relation to the number of dimensions of the search-space (and perhaps to the feasibility ratio and multi-modality of the problem) for a given number of permitted function evaluations. The degree of locality of the method is another aspect that affects the balance between exploration and exploitation, critical for the performance of the algorithm. With regard to the constrained PSO algorithm, further steps will be focused on the development of our current three constraint-handling techniques, as well as on the development of others. For instance, the self-adaptation of penalization coefficients and the development of techniques to delay the loss of particles' momentum and to generate initial feasible solutions other than brute force are promising lines of research for further improvement. Finally, further steps in the development of our PSO-based jetty scheduler consist of designing more developed priority rules, incorporating the demurrage rate to the current rules based on the ETAs only; testing binary versions of the PSO algorithm for the same model of the problem; considering other constraint-handling techniques such as the penalization method; including the minimization of the makespan as a secondary objective; considering embedding an independent optimization algorithm on every berth to optimize the order in which the shipments allocated are to be served; and finally considering solving the jetty scheduling problem as an instance of the general job shop scheduling problem, and therefore using other PSO-based approaches recently published in the literature.",
keywords = "particle swarms, artificial intelligence, optimization, scheduling",
author = "Johann Sienz and Mauro Innocente",
year = "2008",
doi = "10.4203/csets.20.6",
language = "English",
isbn = "978-1-874672-40-1",
series = "Computational Science, Engineering & Technology Series",
publisher = "Saxe-Coburg Publications",
pages = "103--126",
editor = "M. Papadrakakis and B.H.V. Topping",
booktitle = "Trends in Engineering Computational Technology",

}

TY - CHAP

T1 - Particle Swarm Optimization: Fundamental Study and its Application to Optimization and to Jetty Scheduling Problems

AU - Sienz, Johann

AU - Innocente, Mauro

PY - 2008

Y1 - 2008

N2 - The advantages of evolutionary algorithms with respect to traditional methods have been much discussed in the literature. While particle swarm optimizers share such advantages, they outperform evolutionary algorithms in that they require lower computational cost and easier implementation, involving no operator design and few coefficients to be tuned. However, even marginal variations in the settings of these coefficients greatly influence the dynamics of the swarm.This paper does not intend to study the tuning of these coefficients. Instead, general-purpose settings are taken from previous studies, and virtually the same algorithm is used to optimize a variety of notably different problems.Following a short review of optimization, the algorithm is tested on a suite of unconstrained benchmark functions, so that its performance is independent from the constraint-handling techniques. Thus, the settings of the coefficients in the particles' velocity update equation can be evaluated. The results were compared to those of other authors, showing the robustness of our settings.Once the algorithm has proved itself able to cope with complex, unconstrained functions, it must be tested on a suite of constrained benchmark problems. This is very important because constraints affect the normal dynamics of the swarm. Three different constraint-handling techniques were implemented: the penalization, preserving feasibility, and bisection methods. As much as very good results were obtained, there is room for improvement in each of these techniques. Again, the results were either competitive with, or outperforming those of other authors.For both suites of constrained and unconstrained benchmark problems, different neighbourhood sizes were considered, always keeping a ring topology. It was concluded that the appropriate balance between exploration and exploitation can be controlled by the neighbourhood sizes, and by the swarm size (for a given number of function evaluations), while keeping the same general-purpose settings for the coefficients in the particles' velocity update equation.While the use of the binary versions of the method to handle discrete variables is an interesting line for future research, the algorithm was adapted to discrete problems by simply rounding-off the particles' trajectories. Thus, the continuous algorithm was kept virtually unmodified. In turn, the jetty scheduling problem was set as a search problem by generating a discrete search-space where the object variables (i.e. the dimensions of the space) represent shipments, whereas the discrete values that the variables are allowed to take stand for the berths where the shipments are to be served. Every solution returned by the PSO algorithm per se consists of a list of shipments to be served on each berth. Their order is handled deterministically at present, giving priority only according to their estimated time of arrival (ETA).In summary, our research follows three separate lines: unconstrained PSO algorithm, constrained PSO algorithm, and PSO-based jetty scheduler. The next steps with regard to the first line consist of studying the appropriate setting of the swarm size in relation to the number of dimensions of the search-space (and perhaps to the feasibility ratio and multi-modality of the problem) for a given number of permitted function evaluations. The degree of locality of the method is another aspect that affects the balance between exploration and exploitation, critical for the performance of the algorithm. With regard to the constrained PSO algorithm, further steps will be focused on the development of our current three constraint-handling techniques, as well as on the development of others. For instance, the self-adaptation of penalization coefficients and the development of techniques to delay the loss of particles' momentum and to generate initial feasible solutions other than brute force are promising lines of research for further improvement. Finally, further steps in the development of our PSO-based jetty scheduler consist of designing more developed priority rules, incorporating the demurrage rate to the current rules based on the ETAs only; testing binary versions of the PSO algorithm for the same model of the problem; considering other constraint-handling techniques such as the penalization method; including the minimization of the makespan as a secondary objective; considering embedding an independent optimization algorithm on every berth to optimize the order in which the shipments allocated are to be served; and finally considering solving the jetty scheduling problem as an instance of the general job shop scheduling problem, and therefore using other PSO-based approaches recently published in the literature.

AB - The advantages of evolutionary algorithms with respect to traditional methods have been much discussed in the literature. While particle swarm optimizers share such advantages, they outperform evolutionary algorithms in that they require lower computational cost and easier implementation, involving no operator design and few coefficients to be tuned. However, even marginal variations in the settings of these coefficients greatly influence the dynamics of the swarm.This paper does not intend to study the tuning of these coefficients. Instead, general-purpose settings are taken from previous studies, and virtually the same algorithm is used to optimize a variety of notably different problems.Following a short review of optimization, the algorithm is tested on a suite of unconstrained benchmark functions, so that its performance is independent from the constraint-handling techniques. Thus, the settings of the coefficients in the particles' velocity update equation can be evaluated. The results were compared to those of other authors, showing the robustness of our settings.Once the algorithm has proved itself able to cope with complex, unconstrained functions, it must be tested on a suite of constrained benchmark problems. This is very important because constraints affect the normal dynamics of the swarm. Three different constraint-handling techniques were implemented: the penalization, preserving feasibility, and bisection methods. As much as very good results were obtained, there is room for improvement in each of these techniques. Again, the results were either competitive with, or outperforming those of other authors.For both suites of constrained and unconstrained benchmark problems, different neighbourhood sizes were considered, always keeping a ring topology. It was concluded that the appropriate balance between exploration and exploitation can be controlled by the neighbourhood sizes, and by the swarm size (for a given number of function evaluations), while keeping the same general-purpose settings for the coefficients in the particles' velocity update equation.While the use of the binary versions of the method to handle discrete variables is an interesting line for future research, the algorithm was adapted to discrete problems by simply rounding-off the particles' trajectories. Thus, the continuous algorithm was kept virtually unmodified. In turn, the jetty scheduling problem was set as a search problem by generating a discrete search-space where the object variables (i.e. the dimensions of the space) represent shipments, whereas the discrete values that the variables are allowed to take stand for the berths where the shipments are to be served. Every solution returned by the PSO algorithm per se consists of a list of shipments to be served on each berth. Their order is handled deterministically at present, giving priority only according to their estimated time of arrival (ETA).In summary, our research follows three separate lines: unconstrained PSO algorithm, constrained PSO algorithm, and PSO-based jetty scheduler. The next steps with regard to the first line consist of studying the appropriate setting of the swarm size in relation to the number of dimensions of the search-space (and perhaps to the feasibility ratio and multi-modality of the problem) for a given number of permitted function evaluations. The degree of locality of the method is another aspect that affects the balance between exploration and exploitation, critical for the performance of the algorithm. With regard to the constrained PSO algorithm, further steps will be focused on the development of our current three constraint-handling techniques, as well as on the development of others. For instance, the self-adaptation of penalization coefficients and the development of techniques to delay the loss of particles' momentum and to generate initial feasible solutions other than brute force are promising lines of research for further improvement. Finally, further steps in the development of our PSO-based jetty scheduler consist of designing more developed priority rules, incorporating the demurrage rate to the current rules based on the ETAs only; testing binary versions of the PSO algorithm for the same model of the problem; considering other constraint-handling techniques such as the penalization method; including the minimization of the makespan as a secondary objective; considering embedding an independent optimization algorithm on every berth to optimize the order in which the shipments allocated are to be served; and finally considering solving the jetty scheduling problem as an instance of the general job shop scheduling problem, and therefore using other PSO-based approaches recently published in the literature.

KW - particle swarms

KW - artificial intelligence

KW - optimization

KW - scheduling

U2 - 10.4203/csets.20.6

DO - 10.4203/csets.20.6

M3 - Chapter

SN - 978-1-874672-40-1

T3 - Computational Science, Engineering & Technology Series

SP - 103

EP - 126

BT - Trends in Engineering Computational Technology

A2 - Papadrakakis, M.

A2 - Topping, B.H.V.

PB - Saxe-Coburg Publications

CY - Stirlingshire

ER -