| 題名 | グラフ点彩色問題に対する厳密解法の上界値の改良による高速化 |
| 著者 | *道後 幸寛 (広島大学工学部第2類情報工学課程), 田岡 智志, 渡邊 敏正 (広島大学大学院工学研究科) |
| Page | pp. 95 - 96 |
| Keyword | 点彩色, VNS, BSC |
| Abstract | グラフの点彩色とは，与えられたグラフGにおいて隣接する(辺で結ばれている)頂点が異なる色となるようにすべての頂点に色を塗ることである．点彩色問題は最小色数及びそのときの点彩色を求めることが目的であるが，一般にNP困難であることが知られている．その解法として必ず最小色数を求められるが，入力によっては計算に長時間かかってしまう厳密解法が存在する．本研究では厳密解法の上界値の改良による高速化を中心に報告する． |
| 題名 | グラフの最大供給分割問題における発見的解法族クラスSIMPLEの辺次数に基づく性能強化 |
| 著者 | *上田 裕之, 田岡 智志, 渡邉 敏正 (広島大学大学院 工学研究科) |
| Page | pp. 97 - 98 |
| Keyword | グラフ, 最大供給分割問題, 近似解法 |
| Abstract | グラフの最大供給分割問題は，グラフが木であってもNP困難であることが知られており，発見的解法がいくつか提案されている．また，グラフが木でありかつ各点の需要量・供給量が全て整数の場合，擬多項式時間で最適解を求めるアルゴリズムが提案されている．本稿では，グラフの最大供給分割問題に対する発見的解法の中で，もっとも計算が早く受給率もよいクラスSIMPLE(およびその派生手法を合わせた手法の族)に注目し，改良手法の提案と計算機実験による性能評価を行った． |
| 題名 | 実験データに基づくシグナル伝達経路ペトリネットモデルの遅延時間推定手法 |
| 著者 | *三輪 良雅, 樋岡 幹司 (山口大学大学院 理工学研究科), Chen Li (東京大学 医科学研究所ヒトゲノム解析センター), Qi-Wei Ge (山口大学 教育学部), 松野 浩嗣 (山口大学大学院 理工学研究科), 宮野 悟 (東京大学 医科学研究所ヒトゲノム解析センター) |
| Page | pp. 99 - 100 |
| Keyword | シグナル伝達経路, ペトリネット, モデル分解, 遅延時間推定, アルゴリズム |
| Abstract | 本稿では，シグナル伝達経路ペトリネットモデルの実験データに基づく遅延時間の推定方法を提案する．我々はまず，李らにより提案されたモデル化手法に基づき，ErbB4レセプタシグナル伝達経路を離散ペトリネットモデルで表現した．さらに，計算時間の短縮のためにモデルの分解を行なった上で，提案するアルゴリズムを用いて実験データに基づく時間ペトリネットモデルを構成した．最後に，提案するアルゴリズムの有効性を確認するために，構成した時間ペトリネットモデルのシミュレーションを行ない，実験データとの比較を行った． |
| 題名 | 時間ペトリネットによるシグナル伝達経路モデルの反応時間決定のアルゴリズムの提案 |
| 著者 | *樋岡 幹司, 三輪 良雅 (山口大学大学院 理工学研究科), 李 晨 (東京大学 医科学研究所 ヒトゲノム解析センター), 葛 崎偉 (山口大学 教育学部), 松野 浩嗣 (山口大学大学院 理工学研究科), 宮野 悟 (東京大学 医科学研究所 ヒトゲノム解析センター) |
| Page | pp. 101 - 102 |
| Keyword | アルゴリズム, ペトリネット, シグナル伝達経路 |
| Abstract | シグナル伝達経路とは，細胞外からリガンド等の物質が細胞膜上の受容体と結合することで細胞内に刺激が伝わり，酵素反応等によりシグナルが下流に伝わる一連の経路である．李らにより，離散ペトリネットを使ってシグナル伝達経路をモデル化する手法が提案されている．さらに，李らの時間ペトリネットを用いたトランジションの発火頻度を決定する手法により，ペトリネットモデルの上流から下流へトークンがプレースに滞留せずに流すことできる．しかし，この手法では発火頻度の決定に対する制約が厳しいという問題点が挙げられる．本稿では，ペトリネットモデルで多く見られるマークグラフを用い，李らの手法に比べ緩い制約の条件式を導出し，アルゴリズムを提案する． |
| 題名 | カンファレンスにおけるセッション編成法の実装 |
| 著者 | *畑 守之 (広島大学大学院 工学研究科 情報工学専攻), 田岡 智志, 渡邉 敏正 (広島大学大学院 工学研究科) |
| Page | pp. 103 - 104 |
| Keyword | 時間割編成 |
| Abstract | 本稿では，カンファレンスにおける時間割編成問題を扱う。カンファレンスとは学術的な研究会や国際会議などのことを指し，実施までに多くのプロセスを経る。その際，数十件から数百件の投稿論文を扱うため，セッションの編成にも多くの労力と時間がかかる。セッション編成は，組合せ的な制約条件（同じ時間帯での教師・クラスの重複の禁止等）を満たしつつ評価値を最適化する組合せ最適化問題の一種であり，一般的な大学等の時間割編成に対してもNP- 完全であることが知られている。 本研究室で実用化されているカンファレンス運営システムでは多くのプロセスを自動化しているが，セッション編成については自動化されていない。この部分を実装し，計算機実験を行いその有用性を示す。 |
| 題名 | 時間付きペトリネットにおけるトランジション選択指標の改良による発火系列探索法の強化 |
| 著者 | *佐々木 浩晶, 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究科) |
| Page | pp. 105 - 106 |
| Keyword | 時間付きペトリネット, 発火スケジューリング問題, increase値, 拡張疑似ボトルネック, 発見的解法 |
| Abstract | 本論分では、時間付きペトリネットの最大発火スケジューリング問題(MAX TPSと略記)に対して、ペトリネットの最大発火系列問題(MAX LFSと略記)の解法で用いられているアルゴリズムを適用させた発見的解法を提案し、その性能を実験的に評価する。新たな解法はDBSR_inc、DBSR_eq、DBSR_eqiの三種類であり、DBSR_incは既存解法DBSR_ra+にincrease値と呼ばれるトランジション選択指標を、DBSR_eqは拡張疑似ボトルネック禁子則を、DBSR_eqiはその両方を組み込んだものである。その結果、いずれの解法も求解率を保ったまま計算時間を最大で約30%減少させることに成功した。 |