著者

筒井 茂義 劉力綺

出版者

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

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.86, pp.9-12, 2007-09-03

参考文献数

7

被引用文献数

1

---

筆者らは先にカンニングアントシステム(cAS)と呼ぶ新しいACOアルゴリズムを提案し,TSPを用いて評価を行いその有効性を確認した.本稿は,cASの2次割り当て問題(QAP)への適用に関するものである.QAPはTSPと同様NP困難な問題であるが,順頂序表現問題の中でももっとも困難な問題の一つと考えられている.本稿では,cAS のQAPへの適用方法について述べ,ACOアルゴリズムのなかで最も有効な手法の一つとされているMMASとの比較を行い,cASがQAPにおいても有効なACOアルゴリズムの一つであることを示す.The previously proposed cunning ant system (cAS), a variant of the ACO algorithm, worked well on the TSP and the results showed that the cAS a promising ACO algorithms on TSP. In this paper, we apply cAS to solving QAP. The experimental results showed cAS worked very well on the QAP and it may be one of the most promising ACO algorithms on QAP as well.

著者

藤本 典幸 筒井 茂義

出版者

大阪府立大学

雑誌

基盤研究(C)

巻号頁・発行日

2011

---

様々な選択肢の中から最もよいものを見つける問題を組み合わせ最適化問題と言う.組み合わせ最適化問題を解くための有望な手法のひとつに生物の進化から着想を得た進化計算がある.本研究では,進化計算により様々な組み合わせ最適化問題をパソコンに標準搭載されているGPUという電子部品を用いて高速に解く手法について研究を行った.その結果,2次割当問題,巡回セールスマン問題などの問題に対してCPUの1コアに比べて最大101倍の高速化を実現した.

著者

筒井 茂義

出版者

阪南大学

雑誌

基盤研究(C)

巻号頁・発行日

2007

---

進化計算の新しい流れの一つである確率モデルGAを取り上げ,部分解利用における多様性維持機構について研究した.この方法では,一つの新個体を生成する際,集団の分布推定に基づいて生成する部分は一部分とし,残りの部分は現集団に存在する個体の一部分(部分解)を利用する.これにより,集団の多様性維持が有効に機能する.本研究では,この方法の有効性を組合せ最適化問題を用いて研究した.またその並列化モデルの研究も行った.

著者

劉力綺 筒井 茂義 小島 基伸

出版者

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

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.86, pp.13-16, 2007-09-03

---

筆者らは先にカンニングアントシステム(cAS)と呼ぶ新しいACOアルゴリズムを提案し,TSP を用いて評価を行い,cAS の有効性を確認した.本論文は,cASのQAPへの応用と並列化方式に関するものである並列化の目的は大きく二つに分類できる.一つは,与えられた時間内に よりクオリティーの高い解を得ることである.もう一つは,与えられたクオリティーの基準を満たす解を高速に得ることである本論文では第二の目的,すなわち高速化を達成することを目的に,複数のプロセッサを用いるcASの並列化の一方法と QAP における結果について述べる.The previously proposed cunning ant system (cAS), a variant of the ACO algorithm, worked well on the TSP and the results showed that the cAS could be one of the most promising ACO algorithms. In this paper, we apply cAS to solving QAP focusing our main attention on the parallelization of the cAS. Results show promising speedups of the parallel cAS.