Lazinica A. (ed.) Particle Swarm Optimization
Подождите немного. Документ загружается.
Searching for the best Points of interpolation using swarm intelligence techniques
151
Chebyshev Points generated with PSO
-5.0000 -5.0000
-4.2900 -4.7553
-4.0251 -4.0451
-2.6500 -2.9389
-1.4000 -1.5451
0.0000 -0.0000
1.4000 1.5451
2.6500 2.9389
4.0451 4.0451
4.2900 4.7553
5.0000 5.0000
Table 3. Polynomial of degree 10
5. Comparison of interpolation methods
How big an effect can the selection of points have? Fig. 4 and Fig. 5 shows Runge's "bell"
function interpolated over [-5, 5] using equidistant points, points selected from the
Chebyshev distribution, and a new method called PSO. The polynomial interpolation using
Chebyshev points does a much better job than the interpolation using equidistant points,
but neither does as well as the PSO method.
-5 0 5
0
0.2
0.4
0.6
0.8
1
f(x) = 1/(1+x
2
)
P
5, equidistant
P
5, chebyshev
exact
-5 0 5
0
0.5
1
1.5
f(x) = 1/(1+x
2
)
P
10, equidistant
P
10, chebyshev
exact
-5 0 5
0.1
0.2
0.3
0.4
0.5
Error Plot
absolute error
-5 0 5
0.5
1
1.5
Error Plot
absolute error
Figure 4. Comparison of interpolation polynomials for equidistant and Chebyshev sample
points
Particle Swarm Optimization
152
Comparing Fig. 4, we see that the maximum deviation of the Chebyshev polynomial from
the true function is considerably less than that of Lagrange polynomial with equidistant
nodes. It can also be seen that increasing the number of the Chebyshev nodes—or,
equivalently, increasing the degree of Chebyshev polynomial—makes a substantial
contribution towards reducing the approximation error.
Comparing Fig. 5, we see that the maximum deviation of the PSO polynomial from the true
function is considerably less than that of Chebyshev polynomial nodes. It can also be seen
that increasing the number of the PSO nodes—or, equivalently, increasing the degree of PSO
polynomial—makes a substantial contribution towards reducing the approximation error.
-5 0 5
0
0.2
0.4
0.6
0.8
1
f(x) = 1/(1+x
2
)
P
5, PSO
P
5, Chebyshev
exact
-5 0 5
0.2
0.4
0.6
0.8
1
f(x) = 1/(1+x
2
)
P
10, PSO
P
10, Chebyshev
exact
-5 0 5
0.1
0.2
0.3
0.4
0.5
0.6
Error Plot
absolute error
-5 0 5
0
0.05
0.1
Error Plot
absolute error
Figure 5. Comparison of interpolation polynomials for PSO and Chebyshev sample points
In this study we take as measure of the error of approximation the greatest vertical distance
between the graph of the function and that of the interpolating polynomial over the entire
interval under consideration (Fig. 4 and Fig. 5).
The calculation of error gives
Degree
Error points
equidistant
Error points
Chebychev
Error points
PSO
5 0.4327 0.6386 0.5025
10 1.9156 0.1320 0.1076
15 2.0990 0.0993 0.0704
20 58.5855 0.0177 0.0131
Table 2. The error
Searching for the best Points of interpolation using swarm intelligence techniques
153
6. Conclusion
The particle swarm optimization is used to investigate the best interpolating points. Some
good results are obtained by using the specific PSO approach. It is now known that the PSO
scheme is powerful, and easier to apply specially for this type of problems. Also, the PSO
method can be used directly and in a straightforward manner. The performance of the
scheme shows that the method is reliable and effective.
7. References
Clerc, M. (1999). The swarm and the queen: towards a deterministic and adaptive particle
swarm optimization, Proceedings of the 1999 IEEE Congress on Evolutionary
Computation, pp.1951—1957, Washington DC.
Cristian, T.I. (2003). The particle swarm optimization algorithm: convergence analysis and
parameter selection, Information Processing Letters, Vol. 85, No. 6, pp.317--325.
David Kincaid and Ward Cheney, (2002). Numerical Analysis: Mathematics of Scientific
Computing. Brooks/Cole.
Eberhart, R.C. and Kennedy, J. (1995). A new optimizer using particles swarm theory', Sixth
International Symposium on Micro Machine and Human Science, pp.39--43, Nagoya,
Japan.
Eberhart, R.C. and Shi, Y. (1998). Parameter selection in particle swarm optimization, in
Porto, V.W.,
Eberhart, R.C. et al (1996). Computational Intelligence PC Tools, Academic Press Professional,
Boston.
Fourie, P.C. and Groenwold, A.A. (2000). Particle swarms in size and shape optimization',
Proceedings of the International Workshop on Multi-disciplinary Design Optimization,
August 7--10, pp.97—106, Pretoria, South Africa.
Fourie, P.C. and Groenwold, A.A. (2001). Particle swarms in topology optimization',
Extended Abstracts of the Fourth World Congress of Structural and Multidisciplinary
Optimization, June 4--8, pp.52, 53, Dalian, China.
Hammer, R. Et al (1995). Numerical Toolbox for Verified Computing I, Springer Verlag,
Berlin.
Kennedy, J. 1998. The behavior of particles, Evol. Progr., Vol. VII, pp.581-587.
Kennedy J. and Eberhart, R.C, (1995). Particle swarm optimization, Proc. IEEE Int. Conf.
Neural Networks, Piscataway, NJ, pp.1942--1948, USA.
Kennedy, J. and Eberhart, R.C. (2001). Swarm Intelligence, Morgan Kaufmann Publishers, San
Francisco.
Kennedy, J. and Spears, W.M. (1998). Matching algorithms to problems: an experimental test
of the particle swarm and some genetic algorithms on the multimodal problem
generator, Proceedings of the (1998) IEEE International Conference on Evolutionary
Computation, Anchorage, May 4--9, Alaska.
Kulisch, U. and Miranker, W.L. (1983). A New Approach to Scientific Computation,
Academic Press, New York.
L. N. Trefethen. Spectral Methods in Matlab. SIAM, (2000). 9, Philadelphia
L. Djerou, M. Batouche, N. Khelil and A.Zerarka, (2007). Towards the best points of
interpolation using Particles swarm optimization approach, in proceedings of IEEE
Congress of Evolutionary Computing, CEC 2007, pp. 3211-3214, Singapore.
Particle Swarm Optimization
154
Maron, M. and Lopez, R. (1991). Numerical Analysis, Wadsworth Publishing Company,
Belmont, California.
Parsopoulos, K.E. and Vrahatis, M.N. (2001). `Modification of the particle swarm optimizer
for locating all the global minima', in Kurkova, V. et al. (Eds.): Artificial Neural
Networks and Genetic Algorithms, Springer, pp.324--327, New York.
Parsopoulos, K.E. et al, (2001a). Objective function stretching to alleviate convergence to
local minima, Nonlinear Analysis TMA, Vol. 47, pp.3419--3424.
Parsopoulos, K.E.et al (2001b). Stretching technique for obtaining global minimizers through
particle swarm optimization, Proceedings of the PSO Workshop, pp.22--29,
Indianapolis, USA.
Roland E. Larson, Robert P. Hostetler, Bruch H. Edwards and David E. Heyd, (1994).,
Calculus with Analytic Geometry. D. C. Heath and Company.
Saravanan, N., Waagen, D. and Eiben, A.E. (Eds.): Lecture Notes in Computer Science-
Evolutionary Programming VII, Springer, Vol. 1447, pp.591--600.
Shi, Y. and Eberhart, R.C. (1998a). A modified particle swarm optimizer, Proceedings of the
1998 IEEE International Conference on Evolutionary Computation, May 4—9,
Anchorage, Alaska.
Shi, Y.H. and Eberhart, R.C. (1998b). Parameter selection in particle swarm optimization,
Evolutionary Programming VII, Lecture Notes in Computer Science, pp.591--600.
Shi, Y.H. and Eberhart, R.C. (2001). Fuzzy adaptive particle swarm optimization', IEEE Int.
Conf. on Evolutionary Computation, pp.101--106.
Zerarka, A., Khelil, N. (2006). A generalized integral quadratic method: improvement of the
solution for one dimensional Volterra integral equation using particle swarm
optimization, Int. J. Simulation and Process Modeling, Vol. 2, Nos. 1/2, pp.152-163.
9
Particle Swarm Optimization and Other
Metaheuristic Methods in Hybrid Flow Shop
Scheduling Problem
M. Fikret Ercan
Singapore Polytechnic School of Electrical and Electronic Engineering
Singapore
1. Introduction
Multiprocessor task scheduling is a generalized form of classical machine scheduling where
a task is processed by more than one processor. It is a challenging problem encountered in
wide range of applications and it is vastly studied in the scheduling literature (see for
instance (Chan & Lee, 1999 and Drozdowski, 1996) for a comprehensive introduction on this
topic). However, Drozdowski (1996) shows that multiprocessor task scheduling is difficult
to solve even in its simplest form. Hence, many heuristic algorithms are presented in
literature to tackle multiprocessor task scheduling problem. Jin et al. (2008) present a
performance study of such algorithms. However, most of these studies primarily concerned
with a single stage setting of the processor environment. There are many practical problems
where multiprocessor environment is a flow-shop that is it is made of multiple stages and
tasks have to go through one stage to another.
Flow-shop scheduling problem is also vastly studied in scheduling context though most of
these studies concerned with single processor at each stage (see for instance Linn & Zhang,
1999, Dauzère-Pérès & Paulli, 1997). With the advances made in technology, in many
practical applications, we encounter parallel processors at each stage instead of single
processors such as parallel computing, power system simulations, operating system design
for parallel computers, traffic control in restricted areas, manufacturing and many others
(see for instance (Krawczyk & Kubale, 1985, Lee & Cai, 1999, Ercan & Fung, 2000, Caraffa et.
al.,2001)). This particular problem is defined as hybrid flow-show with multiprocessor tasks
in scheduling terminology and minimizing the schedule length (makespan) is the typical
scheduling problem addressed. However, Brucker & Kramer (1995) show that
multiprocessor flow-shop problem to minimize makespan is also NP-hard. Gupta (1988)
showed that hybrid flow-shop even with two stages is NP-hard. Furthermore, the
complexity of the problem increases with the increasing number of stages.
Multiprocessor task scheduling in a hybrid flow-shop environment has recently gained the
attention of the research community. To the best of our knowledge, one of the earliest
papers that deal with this problem in the scheduling literature is by Oğuz and Ercan, 1997.
However, due to the complexity of the problem, in the early studies (such as (Lee & Cai,
1999, Oğuz et. al., 2003)) researchers targeted two layer flow-shops with multiprocessors.
Simple list based heuristics as well as meta-heuristics were introduced for the solution
Particle Swarm Optimization
156
(Oğuz et al.,2003, Jdrzęjowicz & Jdrzęjowicz,2003, Oğuz et al.,2004). Apparently, a broader
form of the problem will have arbitrary number of stages in the flow-shop environment.
This is also studied recently and typically metaheuristic algorithms applied to minimize the
makespan such as population learning algorithm (Jdrzęjowicz & Jdrzęjowicz, 2003), tabu
search (Oğuz et al.,2004), genetic algorithm (Oğuz & Ercan,2005) and ant colony system
(Ying & Lin,2006). Minimizing the makespan is not the only scheduling problem tackled;
recently Shiau et al. (2008) focused on minimizing the weighted completion time in
proportional flow shops.
These metaheuristic algorithms produce impressive results though they are sophisticated
and require laborious programming effort. However, of late particle swarm optimization
(PSO) is gaining popularity within the research community due to its simplicity. The
algorithm is applied to various scheduling problems with notable performance. For
instance, Sivanandam et al. (2007) applied PSO to typical task allocation problem in
multiprocessor scheduling. Chiang et al. (2006) and Tu et al. (2006) demonstrate application
of PSO to well known job shop scheduling problem.
PSO, introduced by Kennedy & Eberhart (1995), is another evolutionary algorithm which
mimics the behaviour of flying birds and their communication mechanism to solve
optimization problems. It is based on a constructive cooperation between particles instead of
survival of the fittest approach used in other evolutionary methods. PSO has many
advantages therefore it is worth to study its performance for the scheduling problem
presented here. The algorithm is simple, fast and very easy to code. It is not computationally
intensive in terms of memory requirements and time. Furthermore, it has a few parameters
to tune.
This chapter will present the hybrid flow-shop with multiprocessor tasks scheduling
problem and particle swarm optimization algorithm proposed for the solution in details. It
will also introduce other well known heuristics which are reported in literature for the
solution of this problem. Finally, a performance comparison of these algorithms will be
given.
2. Problem definition
The problem considered in this paper is formulated as follows: There is a set J of n
independent and simultaneously available jobs where each job is made of Multi-Processor
Tasks (MPT) to be processed in a multi-stage flow-shop environment, where stage j
consists
of m
j
identical parallel processors (j=1,2,...,k). Each MPT
i
∈
J should be processed on p
i,j
identical processors simultaneously at stage j without interruption for a period of t
i,j
(
i=1,2,...,n and j=1,2,...,k). Hence, each MPT
i
∈
J is characterized by its processing time, t
i,j
,
and its processor requirement, p
i,j
. The scheduling problem is basically finding a sequence of
jobs that can be processed on the system in the shortest possible time. The following
assumptions are made when modeling the problem:
• All the processors are continuously available from time 0 onwards.
• Each processor can handle no more than one task at a time.
• The processing time and the number of processors required at each stage are known in
advance.
• Set-up times and inter-processor communication time are all included in the processing
time and it is independent of the job sequence.
Particle Swarm Optimization and Other Metaheuristic Methods
in Hybrid Flow Shop Scheduling Problem
157
3. Algorithms
3.1 The basic PSO algorithm
PSO is initialized with a population of random solutions which is similar in all the
evolutionary algorithms. Each individual solution flies in the problem space with a velocity
which is adjusted depending on the experiences of the individual and the population. As
mentioned earlier, PSO and its hybrids are gaining popularity in solving scheduling
problems. A few of these works tackle the flow shop problem (Liu et al.,2005) though
application to hybrid flow-shops with multiprocessor tasks is relatively new (Ercan & Fung,
2007, Tseng & Liao, 2008).
In this study, we first employed the global model of the PSO (Ercan & Fung, 2007). In the
basic PSO algorithm, particle velocity and position are calculated as follows:
V
id
=W V
id
+ C
1
R
1
(P
id
-X
id
)+C
2
R
2
(P
gd
-X
id
) (1)
X
id
=X
id
+V
id
(2)
In the above equations, V
id
is the velocity of particle i and it represents the distance traveled
from the current position. W is inertia weight. X
id
represents particle position. P
id
is the local
best solution (also called as “pbest”) and P
gd
is global best solution (also called as
“qutgbest”). C
1
and C
2
are acceleration constants which drive particles towards local and
global best positions. R
1
and R
2
are two random numbers within the range of [0, 1]. This is
the basic form of the PSO algorithm which follows the following steps:
Algorithm 1: The basic PSO
Initialize swarm with random positions and velocities;
begin
repeat
For each particle evaluate the fitness i.e. makespan of the schedule;
if current fitness of particle is better than Pid then set Pid to current value;
if Pid is better than global best then set Pgd to current particle fitness value;
Change the velocity and position of the particle;
until termination = True
end.
The initial swarm and particle velocity are generated randomly. A key issue is to establish a
suitable way to encode a shedule (or solution) to PSO particle. We employed the method
shown by Xia et al.(2006). Each particle consists of a sequence of job numbers representing
the n number of jobs on a machine with k number of stages where each stage has m
j
identical processors (j=1,2,...,k). The fitness of a particle is then measured with the maximum
completion time of all jobs. In our earlier work (Oğuz & Ercan,2005), a list scheduling
algorithm is developed to map a given job sequence to the machine environment and to
compute the maximum completion time (makespan). A particle with the lowest completion
time is a good solution.
Figure 1 shows an example to scheduling done by the list scheduling algorithm. In this
example, number of jobs is n= 5 and a machine is made of two stages k=2 where each stage
contains four identical processors. Table 1 depicts the list of jobs and their processing times
and processor requirements at each stage for this example.
Particle Swarm Optimization
158
Job # Stage 1 (j=1) Stage 2 (j=2)
i p
i,1
t
i,1
p
i,2
t
i,2
1 1 1 2 2
2 3 3 4 2
3 3 3 3 2
4 2 1 2 1
5 1 1 1 1
Table 1. Example jobs and their processing time and processor requirements at each stage
For the schedule shown in Figure 1, it is assumed that a job sequence is given as S
1
={2,3,1,4,5}. At stage 1, jobs are iteratively allocated to processors from the list starting from
time 0 onwards. As job 2 is the first in the list, it is scheduled at time 0. It is important to note
that although there are enough available processors to schedule job 1 at time 0 this will
violate the precedence relationship established in the list. Therefore, job 1 is scheduled to
time instance 3 together with job 3 and this does not violate the precedence relationship
given in S
1
. Once all the jobs are scheduled at first stage, a new list is produced for the
succeeding stage based on the completion of jobs at previous stage and the precedence
relationships given in S
1
. In the new list for stage 2, S
2
={2,1,3,4,5} , job 1 is scheduled before
job 3 since it is available earlier than job 3. At time instance 7, jobs 3, 4 and 5 are all available
to be processed. Job 3 is scheduled first since its completion time is earlier at stage 1.
Although, there is enough processor to schedule job 5 at time 8 this will again violate the
order given in list S
1
, hence it is scheduled together with job 4. In this particular example,
jobs 4 and 5 will be the last to be mapped to stage 2 and the over all completion time of tasks
will be 10 units.
The parameters of PSO are set based on our empirical study as well as referring to the
experiences of other researchers. The acceleration constants C
1
and C
2
are set to 2.0 and
initial population of swarm is set to 100. Inertia weight, W, determines the search behavior
of the algorithm. Large values for W facilitate searching new locations whereas small values
provide a finer search in the current area. A balance can be established between global and
local exploration by decreasing the inertia weight during the execution of the algorithm.
This way PSO tends to have more global search ability at the beginning and more local
search ability towards the end of the execution. In our PSO algorithm, an exponential
function is used to set the inertia weight and it is defined as:
max
)(
x
x
endstartend
eWWWW
α
−
−+=
(3)
where, W
start
is the starting, W
end
is the ending inertia values. W
start
are W
end
are set as 1.5
and 0.3 respectively. In addition, x shows the current iteration number and x
max
shows the
maximum iteration number which is set to 10000. An integer constant
α
is used to
manipulate the gradient of the exponentially decreasing W value and it is set to 4.
In this application, X
id
and V
id
are used to generate and modify solutions therefore they are
rounded off to the nearest integer and limited to a maximum value of n which is the
maximum number of jobs. That is position coordinates are translated into job sequence in
our algorithm and a move in search space is obtained by modifying the job sequence.
Particle Swarm Optimization and Other Metaheuristic Methods
in Hybrid Flow Shop Scheduling Problem
159
Figure 1. The schedule of job sequence [2, 3, 1, 4, 5] after being allocated to processors of the
multilayer system using the list scheduling algorithm. Idle periods of the processors are
labeled as idle
3.2 Hybrid PSO algorithms
Although, PSO is very robust and has a well global exploration capability, it has the
tendency of being trapped in local minima and slow convergence. In order to improve its
performance, many researchers experimented with hybrid PSO algorithms. Poli et al. (2007)
give a review on the varations and the hybrids of particle swarm optimisation. Similarly, in
scheduling problems, performance of PSO can be improved further by employing hybrid
techniques. For instance, Xia & Wu (2006) applied PSO-simulated annealing (SA) hybrid to
job shop scheduling problem and test its performance with benchmark problems. Authors
conclude that PSO-SA hybrid delivered equal solution quality as compared to other
metaheuristic algorithms though PSO-SA offered easier modeling, simplicity and ease of
implementation. These findings motivated us to apply PSO and its hybrids to this particular
scheduling problem and study its performance.
The basic idea of the hybrid algorithms presented here is simply based on runnign PSO
algorithm first and then improving the result by employing a simulated annealing (SA) or
tabu search (TS) heuristics. SA and TS introduce a probability to avoid becoming trapped in
a local minimum. In addition, by introducing a neighborhood formation and tuning the
Particle Swarm Optimization
160
parameters, it is also possible to enhance the search process. The initial findings of this study
are briefly presented in (Ercan,2008). The following pseudo codes show the hybrid
algorithms:
Algorithm 2: Hybrid PSO with SA
Initialize swarm with random positions and velocities;
begin
initialize PSO and SA;
while (termination !=true)
do{
generate swarm;
compute and find best Pgd;
}
set particle that gives best Pgd as initial solution to SA;
while (Tcurrent>Temp_end)
do{
generate neighborhood;
evaluate and update best solution and temperature;
}
end.
Algorithm 3: Hybrid PSO with TS
Initialize swarm with random positions and velocities;
begin
initialize PSO and TS;
while (termination !=true)
do{
generate swarm;
compute and find best Pgd;
}
set particle that gives best Pgd as initial solution to TS;
while (termination!=true)
do{
generate sub set of neighborhoods;
evaluate and update the best solution;
update the tabu list;
}
end.
The initial temperature for PSO-SA hybrid is estimated after 50 randomly permuted
neighborhood solutions of the initial solution. A ratio of average increase in the cost to
acceptance ratio is used as initial temperature. Temperature is decreased using a simple
cooling strategy T
current
= λT
current
-1 . The best value for lambda is experimentally found and
set as 0.998. The end temperature is set to 0.01.
A neighbor of the current solution is obtained in various ways.
• Interchange neighborhood: Two randomly chosen jobs from the job list are
exchanged.