平成８年度第４回KSMAP

日時：　平成８年１０月１８日（金）午後４時〜６時

場所：　京都大学工学部８号館３階
　　　  共同６講義室

プログラム：

◆［タイトル］    メタ戦略のロバスト性について

  ［発表者］      柳浦 睦憲

  ［概要］
	多くの組合せ最適化問題について, 厳密な最適解を求めることが極めて困難であるこ
	とが, 計算の複雑さの理論により明らかにされてきた. NP困難問題はその代表例であ
	る. しかし, 現実には, 最適性の保証はなくとも, 十分精度の高い解が求まれば満足
	のいく場合が多い. 近似解法はこのような目的に用いられる. 近似解法の基本戦略と
	して, 欲張り法(greedy method), 局所探索法(local search)などがあるが, 最近では,
	これらを組合わせるなどの方法により, 多少時間はかかっても, より精度の高い解を
	求める枠組を提供しようとする, メタ戦略(metaheuristics)の研究が盛んである. 代
	表的なものとして, ランダム多スタート局所探索法(random multi-start local search)
	遺伝アルゴリズム(genetic algorithm)アニーリング法(simulated annealing)タブー
	探索法(tabu search)などがある. 
	
	メタ戦略の魅力として, その簡単さとロバスト性が挙げられる. これらは, 問題の数
	学的構造などに対するとりわけ深い洞察がなくても, アルゴリズムを簡単に作ること
	ができ, しかも, ある程度良い結果が期待できる. また, 単純な近似解法に比べ, よ
	り高い精度の解が得られる場合が多い. 本研究では, この点に重点を置き, 「できる
	だけ単純な枠組みに従い, アルゴリズム内部のオペレータには複雑なものを用いない」
	ことに留意しつつ, 様々なタイプのメタ戦略について計算実験を行った. 本研究の目
	的は, 特定の問題に対する最良のアルゴリズムを見い出すことではなく, メタ戦略を
	「手軽なツール」として用いることを前提に, 問題固有の性質にできるだけ依存しな
	いような一般的傾向を観察することにある. 現実の場面でメタ戦略のアルゴリズムを
	開発する際には, 開発にあまり時間をかけておれず, アルゴリズムの内部オペレータ
	に複雑なテクニックを取り入れることは出来ない場合が多い. このような場面におい
	て, 本研究で観測されたデータは, アルゴリズム開発者の参考になり, 有用であると
	考えられる. 
	
	具体的な対象としては, 1機械スケジューリング問題を用いた. 
	
	発表では, まず, 代表的なメタ戦略のアイディアを簡単に説明した後, 計算実験の結
	果を報告する. さらに, 実験結果をふまえ, メタ戦略を「手軽なツール」として用い
	る際の設計指針を示す. 

	参考資料:  柳浦睦憲, 茨木俊秀, "メタ戦略のロバスト性について", 第8回RAMPシン
	           ポジウム論文集 (1996) 109-124.




◆［タイトル］    ネットワークフロー、凸性とマトロイド --- M凸関数入門 ---

  ［発表者］      塩浦　昭義
  
  ［概要］
	マトロイド(ポリマトロイド)という概念が、組合せ最適化において 
	基本的な役割を果たしているという事実は、専門家には良く知られ
	ていても、そうでない人にはあまり知られていないかと思います。
	また、マトロイドを勉強しはじめた学生などの意見を聞くと、
	「抽象的でイメージがわかない」「数学的すぎて難しい」などと
	いう悲しい答が帰ってくることもしばしばです。

	一方で、組合せ最適化におけるネットワークフロー理論は、
	比較的なじみやすく、広く理解されている存在です。
	また、非線形最適化(連続最適化)における凸集合、凸関数は、
	この分野において基本的な概念ですが、これらは幾何的にイメージ
	出来ることから、非常にわかりやすい概念となっています。
 
	今回の発表では、これら「ネットワークフロー」「凸性」と「マトロイド」
	を結び付けて、より多くの人にマトロイドをもっと身近に感じて
	もらおう、と思っています。
	具体的には、
	   ・マトロイド(ポリマトロイド)はネットワークフローの一般化
	であるということを再認識して頂くと共に、  
	室田(1996)による論文 "Discrete Convex Analysis" の視点から、
	   ・マトロイド及びM凸関数は離散の世界での凸集合及び凸関数
	と見なせることを理解して頂きたいと思います。