講演抄録/キーワード |
講演名 |
2007-06-09 13:10
128bit固定小数点(FPGA)によるロジスティック写像の高速符号生成(II) ~ 順列加速器を用いた16都市TSPへの応用 ~ ○浜 淳・庄野克房(長野県工技総合センター) NLP2007-30 |
抄録 |
(和) |
初期値から生成した1本のカオス軌道が,16都市TSP問題の最短距離ルートを発見する.ロジスティック写像の固定小数点演算(計算精度128bit,出力256bit)を,擬似乱数生成のために用いる.そのカオス状態の長さが2^64写像回数を越すことは無い.擬似乱数256bitから0~15の順列を効果的に取り出し,さらに順列加速器を0~15の順列生成に用いている.5台のシミュレーションシステムを並列に動作させることによって,最大16!~2.09×10^13本中から約10^10回程度の順列生成で最短距離ルートを見出した. |
(英) |
One chaos stream starting at an initial value gives us the shortest distance root of 16 cities TSP (traveling salesman problem). Fixed point calculation (precision is 128 bits, output is 256 bits) of the logistic map was employed for providing quasi random numbers, whose length is very close to but less than 2^64 (mapping period). 0~15 permutations are taken out from quasi random number 256 bits effectively, and permutation accelerators were employed to generate additional 0~15 permutations. By the five parallel operations of the simulation system the shortest distance root was found at around 10^10 trials within the maximum numbers of 16!~2.09×10^13 ones. |
キーワード |
(和) |
固定小数点演算 / FPGA / ロジスティック写像 / カオス状態 / TSP / 順列加速器 / / |
(英) |
Fixed Point Calculation / FPGA / Logistic Map / Chaotic States / TSP / Permutation Accelerator / / |
文献情報 |
信学技報, vol. 107, no. 87, NLP2007-30, pp. 43-46, 2007年6月. |
資料番号 |
NLP2007-30 |
発行日 |
2007-06-02 (NLP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
NLP2007-30 |