数値実験結果

第6章 数値実験による検証 35

6.2 従来手法と提案手法の比較

1000 bit Tabu Search 20 1000 100 Proposed Method 20 1000 — 48 cities Tabu Search 20 300 20 (att48) Proposed Method 20 300 — TSP 107 cities Tabu Search 20 1000 100

(pr107) Proposed Method 20 1000 — 152 cities Tabu Search 20 2000 200

(pr152) Proposed Method 20 2000 — 20 jobs 5 machines Tabu Search 20 200 4

(ta001) Proposed Method 20 200 — FSSP 50 jobs 5 machines Tabu Search 20 500 10 (ta031) Proposed Method 20 500 — 100 jobs 5 machines Tabu Search 20 500 20 (ta061) Proposed Method 20 500 —

り最適性の高い解を得ることができることが分かる。一方，FSPにおいては探索によって 得られる解はTSに比べてばらつきが大きく，TSよりも良い解が得られない場合も多い。

いずれの問題でも大域的最適解を得ることはできているが，平均値あるいは最悪値がTS に比べて劣っている場合がある。しかしながら，提案手法では計算量の減少はできており，

評価回数が同じになるように探索を行うと，問題によっては提案手法の方が優れた解を発 見できることもある。また，提案手法は任意に設定したT_maxの期間全体を有効に活用する ように多様化・集中化を行って探索をするため，より長期間の探索を行えば，より最適性 の高い解を発見できる可能性もある。

また，評価回数の減少は問題が大規模になるほど顕著となっているため，提案手法は問 題規模が大きいほどより有効になると考えられる。N P困難である組合せ最適化問題を解 く手法としてメタヒューリスティクスに着目した理由が，「大規模問題において現実的な

第6章 数値実験による検証 37 表6.3： 数値実験結果

Problem Tabu Search Proposed Method GOS

Mean 2032.60 (0.99%) 2040.77^∗(0.60%) Best 2049 (0.19%) 2053^∗ (0.00%)

100 bit Worst 2015^∗(1.85%) 2015^∗ (1.85%) 2053

Std 5.75^∗ 6.33

No. of Evaluations 90.4 49.35^∗ Mean 10197.55 (2.79%) 10367.70^∗(1.17%)

Knapsack Best 10256 (2.23%) 10405^∗(0.81%)

Problem 500 bit Worst 10142 (3.32%) 10337^∗(1.46%) 10490

Std 22.31 14.43^∗

No. of Evaluations 452.55 209.14^∗ Mean 20368.60 (2.54%) 20634.66^∗(1.27%)

Best 20452 (2.14%) 20683^∗(1.04%)

1000 bit Worst 20314 (2.80%) 20581^∗(1.53%) 20900

Std 26.32 20.88^∗

No. of Evaluations 980.01 376.80^∗ Mean 33749.04 (0.68%) 33568.23^∗(0.14%)

Best 33522^∗(0.00%) 33522^∗(0.00%)

48 cites Worst 34058 (1.60%) 33783^∗(0.79%) 33522

(att48) Std 135.66 59.45^∗

No. of Evaluations 1008.6 167.57^∗ Mean 44464.17 (0.36%) 44393.86^∗(0.21%)

Traveling Best 44303^∗(0.00%) 44303^∗(0.00%)

Salesman 107 cities Worst 44707 (0.91%) 44617^∗(0.78%) 44303

Problem (pr107) Std 103.53 87.22^∗

No. of Evaluations 5081.8 319.40^∗ Mean 74228.91 (0.74%) 73916.64^∗(0.32%)

Best 73682^∗(0.00%) 73682^∗(0.00%)

152 cities Worst 74686 (1.36%) 74318^∗(0.86%) 73682

(pr152) Std 245.7734 143.17^∗

No. of Evaluations 10791 473.81^∗ Mean 1288.9^∗ (0.85%) 1292.3 (1.12%)

Best 1278^∗(0.00%) 1278^∗ (0.00%)

20 jobs 5 machines Worst 1297^∗(1.49%) 1297^∗ (1.49%) 1278

(ta031) Std 8.67 8.11^∗

No. of Evaluations 184.54 23.64^∗ Mean 2725.9 (0.07%) 2725.7^∗(0.06%)

Flow Shop Best 2724^∗(0.00%) 2724^∗ (0.00%)

Scheduling 50 jobs 5 machines Worst 2729^∗(0.18%) 2735 (0.40%) 2724

Problem (ta031) Std 2.44^∗ 2.64

No. of Evaluations 1189.80 131.20^∗ Mean 5494.9^∗ (0.03%) 5496.5 (0.06%)

Best 5493^∗(0.00%) 5493^∗ (0.00%)

100 jobs 5 machines Worst 5495^∗(0.04%) 5527 (0.62%) 5493

(ta061) Std 0.34^∗ 5.93

No. of Evaluations 4193.30 415.74^∗

7 ^おわりに

本章では，本論文のまとめ及び今後の課題について述べる。

7.1 ^まとめ

大規模・複雑な組合せ最適化問題を解くための手法としてメタヒューリスティクスに着 目し，様々なアナロジーに立脚して開発されてきたこれまでのメタヒューリスティクスに 共通する，最適化手法として本質的に必要な基本構造の解析を行った。そして，その基本 構造の中でも，メタヒューリスティクスが最適性の高い解を得るための最も重要な概念と して，現実の多くの組合せ最適化問題で成立するPOPに着目し，POPを有効に活用する ための研究を行った。本論文では，大きく分けて以下の2点について述べている。

1 POPの定量的な評価

2 ^{定量的に評価した}POPに基づく新たな最適化手法の構築

1では，従来の最適化手法の改良及び新たな最適化手法の開発を行う際に，メタヒューリ スティクスにおける探索戦略の根幹となるPOPをより具体的かつ有効に活用するため，漠 然とした概念であるPOPを探索構造に陽に取り入れる方法を提案した。概念であるPOP を探索構造に取り入れるため，距離および部品の観点からPOPを定量的に評価した。性 質や解表現がそれぞれ異なる組合せ最適化問題であるKP，TSP，FSSPを例として，各問

いた新たな近傍生成方法を提案し，LSにおいて支配的な計算負荷となる近傍の生成・評価 の回数を減少させることに成功した。また，距離の観点によるPOPの評価を用いて多様 化・集中化の観測と制御を行い，近傍の生成回数を減少させつつ高い探索性能を実現した。

提案手法における多様化・集中化の制御では，使用者が任意に設定可能な最大反復回数に 合せて自動的に多様化・集中化のバランスをとるため，設定した探索期間を十分に有効活 用した探索が可能となる。提案手法と同じくLSに立脚した代表的な最適化手法であるTS と比較した結果，TSPとKPでは計算量を減少させつつTS以上の探索性能を得ることが でき，FSSPでは少ない計算量でほぼ同等の性能を発揮することができた。

第7章 おわりに 41