著者

筒井 茂義 劉力綺

出版者

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

雑誌

情報処理学会研究報告数理モデル化と問題解決(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.

著者

劉力綺 筒井 茂義 小島 基伸

出版者

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

雑誌

情報処理学会研究報告数理モデル化と問題解決(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.