{"created":"2023-05-15T12:20:33.411741+00:00","id":11162,"links":{},"metadata":{"_buckets":{"deposit":"3a711f2a-8d54-4358-b8b1-1b34c81e0801"},"_deposit":{"created_by":1,"id":"11162","owners":[1],"pid":{"revision_id":0,"type":"depid","value":"11162"},"status":"published"},"_oai":{"id":"oai:kansai-u.repo.nii.ac.jp:00011162","sets":["528:1588:1589:1591"]},"author_link":["24372","24373","24370","24371","24366","24368","24367","24369"],"item_9_alternative_title_20":{"attribute_name":"その他のタイトル","attribute_value_mlt":[{"subitem_alternative_title":"Parallel Consultant-Guided Search Algorithm for Traveling Salesman Problem"}]},"item_9_biblio_info_7":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2016-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"1","bibliographicPageEnd":"342","bibliographicPageStart":"331","bibliographicVolumeNumber":"57","bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌"}]}]},"item_9_description_4":{"attribute_name":"概要","attribute_value_mlt":[{"subitem_description":"近年，メタヒューリスティクスは組合せ最適化問題を解く手法として多くの研究が行われている．最近の研究では，コンサルタント誘導型探索（CGS）と呼ばれる新しいメタヒューリスティクスが提案されている．本研究では，CGS を用いた巡回セールスマン問題（TSP）に対する並列アルゴリズムを提案する．アルゴリズムの並列化では，CGS における仮想人間をそれぞれの計算機の各プロセッサコアに割当てることで効率良く解の探索を行う．また，仮想人間の集団を複数のサブ集団に分割し，各サブ集団同士で仮想人間の移住を行う島モデルをCGS に取り入れる．10 台の計算機を用いた性能評価実験を行い，都市数が5000 のTSPLIB のベンチマーク問題例に対して5%未満の誤差率を達成することを示す．Metaheuristic algorithms have been studied as a method for solving combinatorial optimization problems. Recently, the Consultant-Guided Search (CGS) for solving the Traveling Salesman Problem(TSP) has been proposed. In this paper, we propose a parallel method which assigns virtual consultants and virtual clients of the CGS to processes of computers, and calculates  an approximation solution effectively for the TSP. In addition, we introduce the island model to increase the diversity of the solution. We execute computer experiments with the benchmark instances (TSPLIB) by 10 quad-core computers. Our algorithm provides a solution with less than 5% error rate for problem instances of 5,000 cities.","subitem_description_type":"Other"}]},"item_9_full_name_3":{"attribute_name":"著者別名","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"24370","nameIdentifierScheme":"WEKO"}],"names":[{"name":"Ebara, Hiroyuki"}]},{"nameIdentifiers":[{"nameIdentifier":"24371","nameIdentifierScheme":"WEKO"}],"names":[{"name":"Nakayama, Koki"}]},{"nameIdentifiers":[{"nameIdentifier":"24372","nameIdentifierScheme":"WEKO"}],"names":[{"name":"Iida, Shuhei"}]},{"nameIdentifiers":[{"nameIdentifier":"24373","nameIdentifierScheme":"WEKO"}],"names":[{"name":"Nagatsuji, Ryota"}]}]},"item_9_publisher_34":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"一般社団法人 情報処理学会"}]},"item_9_rights_13":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"一般社団法人　情報処理学会（利用は著作権の範囲内に限られる。）"}]},"item_9_source_id_10":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11464803","subitem_source_identifier_type":"NCID"}]},"item_9_source_id_8":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"03875806","subitem_source_identifier_type":"ISSN"}]},"item_9_text_35":{"attribute_name":"出版者（他言語）","attribute_value_mlt":[{"subitem_text_value":"IPSJ Journal"}]},"item_9_version_type_17":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"榎原, 博之"}],"nameIdentifiers":[{},{},{}]},{"creatorNames":[{"creatorName":"中山, 弘基"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"飯田, 修平"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"長辻, 亮太"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2019-05-23"}],"displaytype":"detail","filename":"KU－1100-20160100-01.pdf","filesize":[{"value":"981.1 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"KU－1100-20160100-01.pdf","url":"https://kansai-u.repo.nii.ac.jp/record/11162/files/KU－1100-20160100-01.pdf"},"version_id":"59aa9ac6-678a-439d-a7d9-557e9b9a26d2"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"コンサルタント誘導型探索","subitem_subject_scheme":"Other"},{"subitem_subject":"PC クラスタ","subitem_subject_scheme":"Other"},{"subitem_subject":"並列処理","subitem_subject_scheme":"Other"},{"subitem_subject":"メタヒューリスティクス","subitem_subject_scheme":"Other"},{"subitem_subject":"組合せ最適化問題","subitem_subject_scheme":"Other"},{"subitem_subject":"consultant-guided search","subitem_subject_scheme":"Other"},{"subitem_subject":"PC cluster","subitem_subject_scheme":"Other"},{"subitem_subject":"parallel processing","subitem_subject_scheme":"Other"},{"subitem_subject":"metaheuristics","subitem_subject_scheme":"Other"},{"subitem_subject":"combinatorial potimization problem","subitem_subject_scheme":"Other"},{"subitem_subject":"関西大学（Kansai University）","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"巡回セールスマン問題に対する並列コンサルタント誘導型探索アルゴリズム","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"巡回セールスマン問題に対する並列コンサルタント誘導型探索アルゴリズム"}]},"item_type_id":"9","owner":"1","path":["1591"],"pubdate":{"attribute_name":"公開日","attribute_value":"2016-06-01"},"publish_date":"2016-06-01","publish_status":"0","recid":"11162","relation_version_is_last":true,"title":["巡回セールスマン問題に対する並列コンサルタント誘導型探索アルゴリズム"],"weko_creator_id":"1","weko_shared_id":1},"updated":"2023-05-15T14:13:55.043902+00:00"}