メタ戦略のロバスト性について

柳浦睦憲, 茨木俊秀

アブストラクト
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ファイル

論文リストへ