Computational & Technology Resources
an online resource for computational,
engineering & technology publications 

Computational Science, Engineering & Technology Series
ISSN 17593158 CSETS: 20
TRENDS IN ENGINEERING COMPUTATIONAL TECHNOLOGY Edited by: M. Papadrakakis, B.H.V. Topping
Chapter 6
Particle Swarm Optimization: Fundamental Study and its Application to Optimization and to Jetty Scheduling Problems J. Sienz and M.S. Innocente
ADOPT Research Group, School of Engineering, Swansea University, United Kingdom J. Sienz, M.S. Innocente, "Particle Swarm Optimization: Fundamental Study and its Application to Optimization and to Jetty Scheduling Problems", in M. Papadrakakis, B.H.V. Topping, (Editors), "Trends in Engineering Computational Technology", SaxeCoburg Publications, Stirlingshire, UK, Chapter 6, pp 103126, 2008. doi:10.4203/csets.20.6
Keywords: particle swarms, artificial intelligence, optimization, scheduling.
Summary
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, generalpurpose 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 constrainthandling 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 constrainthandling 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 generalpurpose 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 roundingoff 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 searchspace 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 PSObased 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 searchspace (and perhaps to the feasibility ratio and multimodality 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 constrainthandling techniques, as well as on the development of others. For instance, the selfadaptation 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 PSObased 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 constrainthandling 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 PSObased approaches recently published in the literature (e.g. Sha et al. [2]). References
purchase the fulltext of this chapter (price £20)
go to the previous chapter 
