組合せ最適化問題

全文

(1)

5.組合せ計画

(2)

組合せ最適化問題

S x

x f

 s.t.

) (

min

S

:実行可能集合(

feasible set

) ただし,組合せ的構造を持つ

(3)

組合せ的構造とは?

有限個または加算無限個の要素を持つ離散集合

n次元の0-1ベクトルの集合

n次元の整数ベクトルの集合

1nまでの順列の集合

n要素からm要素への写像の全体

n通り 2

n通り m

!通り n

m通り n

(4)

組合せ最適化問題の例

巡回セールスマン問題

traveling salesman problem, TSP

 

序を求める問題.

離が最小となる訪問順

ち,距 と元に戻る巡回路のう

ど一度ずつ訪問したあ

べての都市をちょう が与えられたとき,す

距離

の間の

と,都市 個の都市の集合

) , (

, ,

1 j

i d

j i

n V

n

(5)

4

都市の例

6通りの順路(うち3つは逆向き)

• 1→2→3→4 距離23

• 1→2→4→3 距離24

• 1→3→2→4 距離21

• 1→3→4→2 距離24

• 1→4→2→3 距離21

• 1→4→3→2 距離23

最適解は1→3→2→4 1→4→2→3

(6)

ドイツの15112都市 を巡回する最適な 巡回路

(7)

TSP

は組合せ最適化問題の中で最も有名

この歴史を勉強すれば,組合せ最適化の理 論と解法が効率よく学べる

スケジューリング,配送計画(ロジスティクス)

などの部分問題

山本,久保「巡回セールスマン問題への招 待」朝倉書店,1997

コンビニへの商品の配達

自販機への補充(清涼飲料水,たばこ)

ガソリンスタンドなど

(8)

ナップサック問題(

KNAPSACK problem

める問題.

荷物を選べばよいか決

,どの に荷物を詰め込むには

るようにナップサック

にす で,利得の総和を最大

サイズを超えない範囲

ップサックの が与えられたとき,ナ

サックのサイズ

およびナップ と利得

のサイズ それぞれの荷物

b

c a

i

i i

次ページのように定式化できる

(9)

ナップサック問題(

KNAPSACK problem

i n

x b

x a

x c

i n

i

i i n i

i i

, ,

1 1

or 0

, s.t.

max

1 1

 

 

整数制約(0-1整数制約)

(10)

グラフ彩色問題(

Graph Coloring Problem

与えられた

n

節点からなる無向グラフ

G=(V,E)

に対して,枝の両端点には同じ色を塗らないと いう条件の下で,すべての節点を彩色するとき,

最小の色の数はいくらか?

ネットワークの信頼性,

VLSI

の設計,時間割 作成など応用多数

(11)

例題

実行可能な彩色(彩色数は4)

(12)

例題

実行不可能可能な彩色

(13)

例題

最適な彩色数は3 完全部分グラフの

次数が下限値

(14)

平面グラフ(枝の交差がないグラフ)は四色あ れば彩色可能

世界地図は四色あれば塗り分けられる 四色問題

(15)

ジョブショップスケジューリング

Job Shop Scheduling Problem

作業の集合と,機械の集合が与えられている.

作業間には先行順序があり,各機械は処理で きる作業が決まっている.作業と先行関係を有 向グラフで表したとき,グラフの始点から終点ま での最長路が最短になるように,各機械の処理 順序を決める問題.

(16)

例題

s t

実線の矢印:作業工程の順序

点線の矢印:同じ機械で処理される作業

各工程 一つの仕事

機械1が処理機械2が処理

機械3が処理

(17)

例題

s t

点線の矢印の向きを決めると最長路(クリティカルパス)

が定まる

(18)

組合せ最適化問題は難しい

ごく一部(最短路問題など)を除いて,最適解 を求めるには全列挙(しらみつぶし)が必要

巡回セールスマン問題:すべての都市の順列 ナップサック問題:すべての0or1の割り当て

ジョブショップスケジューリング:鎖線の矢印の向きすべて

クラス

NP

NP

困難

(19)

解法の考え方

厳密解を求める(厳密解法)

結局は全列挙

如何に効率よく列挙するか 分枝限定法(

Branch and Bound method

) 動的計画法(

Dynamic Programming, DP

サイズが大きいと実用的な時間で解けない

(20)

現実的な時間で良質の解を求める

近似解法(

approximate algorithm

) 欲張り法(

greedy method

局所探索法(

local search

)など

発見的解法(

heuristics

メタ戦略

(21)

メタ戦略( metaheuristics )

局所探索を繰り返し行って,良質の解を得る ための一般的な枠組み

ランダム多スタート局所探索,遺伝アルゴリ ズム(

genetic algorithm, GA

),アニーリング 法(

simulated annealing, SA

),タブー探索 法(

tabu search

)など

柳浦,茨木「組合せ最適化ーメタ戦略を中心 としてー」朝倉書店,2001

(22)

近似解法の例

ナップサック問題に対する欲張り法

として

ならば

とする.

ならば,

とする.

ならば,

とする.

とする.

の順に並び替え 個の要素を

k k

n k

x b

a

a b

b x

b a

k b b

a c

a c

a c

a c

n

k k

k k

k

n n

i i

. 1

Step 1

: 1

: 2 Step

0 :

: ,

1 : :

1 Step

1 : , :

: 0 Step

*

*

*

*

* 2 2

1

1

最も効率の良い(単位重さに対する価 値が高い)荷物から入れる

(23)

問題例

1 , , 4

1 0

9 6

5 3

2 s.t.

14 12

5 4

max

4 3

2 1

4 3

2 1

 

i x

x x

x x

x x

x x

i または

となる.

べると

なので,大きい順に並 3,4,1,2

3 / 7 ,

5 / 12 ,

3 / 5 ,

2 :

0

Step c1 a1 c2 a2 c3 a3 c4 a4

(24)

反復 k x 残り容量 目的関数値

0 (0,0,0,0)

1 (0,0,1,0) 9-5=4 12

2 (0,0,1,0)

4-6=-2

12

3 (1,0,1,0) 4-2=2 12+4=16

4 (1,0,1,0) 16

欲張り法の進行の様子

(25)

欲張り法は近似解法

近似解は最適解とは限らない

だが,近似の精度は以外と良い

欲張り法で最適解を見つけられるか?

最小全域木問題に対するクラスカル法(教科 書

153

ページ)は欲張り法の代表例

欲張り法が最適解となる問題のクラス

(26)

演習課題

けちけち法

欲張り法とは逆に,効率の悪い荷物を一つず つ捨ててゆき,容量制約を満たしたら終了す る.

上のナップサック問題例を,けちけち法で解け.

また,全探索をして最適解を求めよ.

Updating...

参照

Updating...

関連した話題 :