Keywords: particle swarms, artificial intelligence, optimization, scheduling.

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 (Innocente [1]), 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 (e.g. Sha et al. [2]).

[1]

M.S. Innocente, "Population-Based Methods: Particle Swarm Optimization - Development of a General-Purpose Optimizer and Applications", Master's thesis, Universitat Politècnica de Catalunya - CIMNE, Barcelona, Spain, 2006.

[2]

D.Y. Sha, C.-Y. Hsu, "A hybrid particle swarm optimization for job-shop scheduling problem", Computers & Industrial Engineering 51, 791-808, 2006. doi:10.1016/j.cie.2006.09.002

purchase the full-text of this chapter (price £20)

go to the previous chapter
go to the next chapter
return to the table of contents
return to the book description
purchase this book (price £92 +P&P)