効果的な局所探索制限によるMemetic Algorithmの高速化

永田裕一; 小林重信; 東条敏

文献

J-GLOBAL ID：201002231716235127 整理番号：10A0249033

効果的な局所探索制限によるMemetic Algorithmの高速化

Efficient Local Search Limitation Strategies in Memetic Algorithm

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=10A0249033&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=10A0249033&from=J-GLOBAL&jstjournalNo=U0128A") }}

著者 (3件)： , ,
資料名：
巻： 25 号： 2 ページ： 299-310 (J-STAGE) 発行年： 2010年
JST資料番号： U0128A ISSN： 1346-8030 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：日本語 (JA)

著者らは以前に車両配送問題(VRP)の最も基本的な問題Capacitated VRP(CVRP)の性質を考慮し,交叉法EAX(Edge Assembly Crossover)を考案した。それをGA(Genetic Algorithm)と局所探索を組み合わせたMA(Memetic Algorithm),あるいはGenetic local searchと呼ばれる枠組みと組み合わせたが計算コストが高い。本論文では,交叉後に得られた子個体の状況に応じ,局所探索の探索領域を制限することでMAの効率化を図った。本手法はTSP(Traveling Salesman Problem)でのILK(Iterated Lin-Kergighan)法と同様のアイデアであり,2つの親個体から子個体を生成する場合に一方の親個体からの変化部分に局所探索の探索領域を制限する。7種類の局所探索制限法を実装してCVRPのベンチマークセットで評価したところ,類似している方の親個体との変化部分に局所探索の探索領域を制限すると,探索精度を落とすことなく計算コストを削減できた。一方,CVRPの特徴を考慮しない制限戦略では解の質が悪化したように,問題に応じて適切に探索範囲の制限を設計すべきことが示唆された。

, , , , , , , , , ,
, , , ,

人工知能 , ネットワーク法

引用文献 (25件)：

[Alba 04] E. Alba, B. Dorronsoro: Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms, Proc. of the 4th Int. Conf. on Evolutionary Computation in Combinatorial Optimization, LNCS 3004, pp. 11--20 (2004).
[Bentley 90] J. L. Bentley: Experiments on Traveling Salesman Geuristics, Proc. of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 91--99 (1990).
[Christofides 79] N. Christofides, A. Mingozzi, P. Toth: The vehicle routing problem, Combinatorial optimization, N. Christofides, A. Mingozzi, P. Toth and C. Sandi (eds), Wiley, Chichester, pp. 315--38 (1979).
[Golden 98] B.L. Golden, E.A. Wasil, J.P. Kelly, I.M. Chao: Metaheuristics in vehicle routing, Fleet management and logistics, T.G. Crainic and G. Laporte (eds), Kluwer, Boston, pp. 33--56 (1998).
[Johnson 97] D.S. Johnson, L.A. McGeoch: The traveling salesman problem: a case study, in Local Search in Combinatorial Optimization, E. Aarts and J.K. Lenstra (eds.), Jhon Wiley&Sons, pp. 215--310 (1997).

, ,

前のページに戻る