著者

柳浦 睦憲 野々部 宏司

出版者

一般社団法人 システム制御情報学会

雑誌

システム/制御/情報 (ISSN:09161600)

巻号頁・発行日

vol.50, no.9, pp.350-356, 2006-09-15 (Released:2017-04-15)

参考文献数

28

著者

柳浦 睦憲 茨木 俊秀

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:09151915)

巻号頁・発行日

vol.J83-D1, no.1, pp.3-25, 2000-01-25

---

組合せ最適化問題に対する効率的な近似解法の一般的枠組みとして,近年,遺伝アルゴリズム,アニーリング法,タブー探索法やそれらの変形版など,様々なアルゴリズムが提案されてきた.これらを総称してメタ戦略あるいはメタヒューリスティクスと呼んでいる.本論文では,これらメタ戦略に現れる様々なアイデアを,近似解法の基本戦略である局所探索法の一般化ととらえることで,体系的にまとめる.メタ戦略の一つの魅力は,その手軽さとロバスト性にある.この観点から,次に,メタ戦略の基本的なアイデアのみで構成したシンプルなアルゴリズムを,計算実験により比較した結果を述べる.これをもとに,手軽なツールとしてのメタ戦略の設計指針を与える.そのあと,より多くの手間をかけても,更に性能の高いアルゴリズムを構成したい場合に有効となる,やや複雑なアイデアについても簡単に紹介する.最後に,メタ戦略の理論的解析の話題にも言及する.

著者

柳浦 睦憲 茨木 俊秀

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 (ISSN:09151915)

巻号頁・発行日

vol.83, no.1, pp.3-25, 2000-01-25

被引用文献数

35

---

組合せ最適化問題に対する効率的な近似解法の一般的枠組みとして, 近年, 遺伝アルゴリズム, アニーリング法, タブー探索法やそれらの変形版など, 様々なアルゴリズムが提案されてきた.これらを総称してメタ戦略あるいはメタヒューリスティクスと呼んでいる.本論文では, これらメタ戦略に現れる様々なアイデアを, 近似解法の基本戦略である局所探索法の一般化ととらえることで, 体系的にまとめる.メタ戦略の一つの魅力は, その手軽さとロバスト性にある.この観点から, 次に, メタ戦略の基本的なアイデアのみで構成したシンプルなアルゴリズムを, 計算実験により比較した結果を述べる.これをもとに, 手軽なツールとしてのメタ戦略の設計指針を与える.そのあと, より多くの手間をかけても, 更に性能の高いアルゴリズムを構成したい場合に有効となる, やや複雑なアイデアについても簡単に紹介する.最後に, メタ戦略の理論的解析の話題にも言及する.

著者

柳浦 睦憲 茨木 俊秀

出版者

The Institute of Electrical Engineers of Japan

雑誌

電気学会論文誌C(電子・情報・システム部門誌) (ISSN:03854221)

巻号頁・発行日

vol.121, no.6, pp.986-991, 2001-06-01 (Released:2008-12-19)

参考文献数

7

著者

山崎 洋祐 スキアボーニ リッカルド イオリ マヌエル 柳浦 睦憲 マルテッロ シルバノ

出版者

京都大学

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

vol.1726, pp.139-154, 2011-02

著者

櫻庭 セルソ 智 柳浦 睦憲

出版者

公益社団法人日本オペレーションズ・リサーチ学会

雑誌

オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch (ISSN:00303674)

巻号頁・発行日

vol.57, no.6, pp.327-334, 2012-06-01

参考文献数

38

---

線形順序付け問題は,正方行列の行と列を同じ順列で並べ替え,下三角部分の値の合計を最小化する問題であり,古くから研究されている.この問題は,辺に重みのついた有向グラフから一部の辺を取り除いてすべての有向閉路を除去するとき,取り除いた辺の重みの合計を最小化するフィードバック辺集合問題と等価である.本稿では,この問題に対するさまざまな解法を,実用的解法を中心に紹介する.

著者

岩崎 慎司 柳浦 睦憲 茨木 俊秀

出版者

公益社団法人日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集

巻号頁・発行日

vol.2000, pp.192-193, 2000-09-27

著者

謝旭珍 柳浦睦憲 小野 孝夫 平田 富夫

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.66, pp.31-38, 2007-07-03

---

グラフの均等辺彩色とは,多重無向グラフと色数が与えれたとき,任意の頂点と任意の2色に対して,その頂点に接続する辺のうちそれぞれの色で塗られているものの本数の差が高々2であるような辺彩色である.与えられたグラフの頂点数を$n$,辺数を$m$とし,色数を$k$とする.謝らは,任意の多重グラフを$O(m2/k)$時間で均等辺彩色するアルゴリズムを提案した.本論文では,彼らのアルゴリズムに変更を加え,初期辺彩色をランダムに与える場合の実行時間を解析する.そして,任意の定数$\varepsilon >0$に対し,実行時間が高い確率で$O(n^{1/2} m^{3/2+\varepsilon })$となることを示す.それは,グラフが密で$k$が小さいときには,既存のアルゴリズムよりも速くグラフを均等辺彩色できることを示す結果である.Given a multigraph $G=(V,E)$ with $n$ vertices and $m$ edges and a color set${\cal C}=\{1,2,\ldots,k\}$, the nearly equitable edge coloring is an assignment of given colors to edges in $G$ such that, among the edges incident to each vertex, the numbers of edges colored with any two colors differ by at most two. Xie~et~al. presented an algorithm to solve this problem in $O(m2/k)$ time. In this paper, we investigate the running time of a modified version of their algorithm in which the initial edge coloring is generated randomly. The new time complexity is proved to be $O(n^{1/2} m^{3/2+\varepsilon })$for arbitrarily small constant $\varepsilon >0$with high probability for sufficiently large $n$,which is better than Xie at al.'s original algorithm when the graph is dense and $k$ is small.