メタ戦略のロバスト性について
柳浦 睦憲, 茨木 俊秀
アブストラクト
One of the attractive features of recent metaheuristics
is in its robustness and simplicity.
To investigate this direction,
we solved the single machine scheduling problem by
various metaheuristics,
such as random multi-start local search (MLS),
genetic algorithm (GA),
simulated annealing (SA) and
tabu search (TS),
using rather simple inside operators.
The results indicate that:
(1) MLS is usually good enough for practical purposes,
considering its simplicity,
(2) a variant of MLS, called GRASP
(greedy randomized adaptive search procedure),
is effective; however,
its performance is sensitive to greedy methods used to generate
initial solutions,
(3) a variant of MLS, called iterated local search,
is quite effective,
(4) GA combined with local search is also competitive
if longer computational time is allowed, and its
performance is not sensitive
to crossovers,
(5) SA (and its variants called the threshold accepting
and the great deluge algorithm)
is another competitive method assuming that
longer computational time is allowed,
and its performance is not much dependent on inside parameter values,
(6) there are cases in which TS is more effective than MLS;
however, its performance depends on how to define
the tabu list and parameter values, and
(7) the definition of neighborhood is very important
for all of the tested algorithms except GA.
Key Words: combinatorial optimization, metaheuristics,
local search, GRASP, genetic algorithm, simulated annealing,
tabu search, single machine scheduling.
第8回RAMPシンポジウム論文集(1996) 109-124.
PSファイル
論文リストへ