WEKO3
AND
アイテム
{"_buckets": {"deposit": "45168408-e605-4c18-9b8e-a6124fddc439"}, "_deposit": {"id": "17837", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "17837"}, "status": "published"}, "_oai": {"id": "oai:soar-ir.repo.nii.ac.jp:00017837", "sets": ["1221:1222"]}, "author_link": ["49819", "49820", "49821"], "item_1628147817048": {"attribute_name": "\u51fa\u7248\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_ab4af688f83e57aa", "subitem_version_type": "AM"}]}, "item_6_biblio_info_6": {"attribute_name": "\u66f8\u8a8c\u60c5\u5831", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2015-11-15", "bibliographicIssueDateType": "Issued"}, "bibliographicPageEnd": "50", "bibliographicPageStart": "42", "bibliographicVolumeNumber": "605", "bibliographic_titles": [{"bibliographic_title": "THEORETICAL COMPUTER SCIENCE"}]}]}, "item_6_description_20": {"attribute_name": "\u6284\u9332", "attribute_value_mlt": [{"subitem_description": "We consider in this work the application of optimization algorithms to problems over discrete codomains corrupted by additive unbiased noise. We propose a modification of the algorithms by repeating the fitness evaluation of the noisy function sufficiently so that, with a fix probability, the function evaluation on the noisy case is identical to the true value. If the runtime of the algorithms on the noise-free case is known, the number of resampling is chosen accordingly. If not, the number of resampling is chosen regarding to the number of fitness evaluations, in an anytime manner. We conclude that if the additive noise is Gaussian, then the runtime on the noisy case, for an adapted algorithm using resamplings, is similar to the runtime on the noise-free case: we incur only an extra logarithmic factor. If the noise is non-Gaussian but with finite variance, then the total runtime of the noisy case is quadratic in function of the runtime on the noise-free case. (C) 2015 Elsevier B.V. All rights reserved.", "subitem_description_type": "Abstract"}]}, "item_6_description_30": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7\uff08\u30b3\u30f3\u30c6\u30f3\u30c4\u306e\u7a2e\u985e\uff09", "attribute_value_mlt": [{"subitem_description": "Article", "subitem_description_type": "Other"}]}, "item_6_description_5": {"attribute_name": "\u5f15\u7528", "attribute_value_mlt": [{"subitem_description": "THEORETICAL COMPUTER SCIENCE. 605:42-50 (2015)", "subitem_description_type": "Other"}]}, "item_6_link_3": {"attribute_name": "\u4fe1\u5dde\u5927\u5b66\u7814\u7a76\u8005\u7dcf\u89a7\u3078\u306e\u30ea\u30f3\u30af", "attribute_value_mlt": [{"subitem_link_text": "Akimoto, Youhei", "subitem_link_url": "http://soar-rd.shinshu-u.ac.jp/profile/ja.OeypbUkh.html"}]}, "item_6_link_67": {"attribute_name": "WoS", "attribute_value_mlt": [{"subitem_link_text": "Web of Science", "subitem_link_url": "http://gateway.isiknowledge.com/gateway/Gateway.cgi?\u0026GWVersion=2\u0026SrcAuth=ShinshuUniv\u0026SrcApp=ShinshuUniv\u0026DestLinkType=FullRecord\u0026DestApp=WOS\u0026KeyUT=000365059800003"}]}, "item_6_publisher_4": {"attribute_name": "\u51fa\u7248\u8005", "attribute_value_mlt": [{"subitem_publisher": "ELSEVIER SCIENCE BV"}]}, "item_6_relation_48": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_name": [{"subitem_relation_name_text": "10.1016/j.tcs.2015.04.008"}], "subitem_relation_type_id": {"subitem_relation_type_id_text": "https://doi.org/10.1016/j.tcs.2015.04.008", "subitem_relation_type_select": "DOI"}}]}, "item_6_rights_62": {"attribute_name": "\u6a29\u5229", "attribute_value_mlt": [{"subitem_rights": "\u00a9 2015. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ "}]}, "item_6_select_64": {"attribute_name": "\u8457\u8005\u7248\u30d5\u30e9\u30b0", "attribute_value_mlt": [{"subitem_select_item": "author"}]}, "item_6_source_id_35": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "0304-3975", "subitem_source_identifier_type": "ISSN"}]}, "item_6_source_id_39": {"attribute_name": "NII ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "0304-3975", "subitem_source_identifier_type": "ISSN"}]}, "item_6_source_id_40": {"attribute_name": "\u66f8\u8a8c\u30ec\u30b3\u30fc\u30c9ID", "attribute_value_mlt": [{"subitem_source_identifier": "AA00862688", "subitem_source_identifier_type": "NCID"}]}, "item_6_text_69": {"attribute_name": "wosonly authkey", "attribute_value_mlt": [{"subitem_text_value": "Discrete optimization; Additive noise; Runtime analysis"}]}, "item_6_text_70": {"attribute_name": "wosonly keywords", "attribute_value_mlt": [{"subitem_text_value": "EVOLUTIONARY ALGORITHM; LOWER BOUNDS; MODEL"}]}, "item_6_textarea_68": {"attribute_name": "wosonly abstract", "attribute_value_mlt": [{"subitem_textarea_value": "We consider in this work the application of optimization algorithms to problems over discrete codomains corrupted by additive unbiased noise. We propose a modification of the algorithms by repeating the fitness evaluation of the noisy function sufficiently so that, with a fix probability, the function evaluation on the noisy case is identical to the true value. If the runtime of the algorithms on the noise-free case is known, the number of resampling is chosen accordingly. If not, the number of resampling is chosen regarding to the number of fitness evaluations, in an anytime manner. We conclude that if the additive noise is Gaussian, then the runtime on the noisy case, for an adapted algorithm using resamplings, is similar to the runtime on the noise-free case: we incur only an extra logarithmic factor. If the noise is non-Gaussian but with finite variance, then the total runtime of the noisy case is quadratic in function of the runtime on the noise-free case. (C) 2015 Elsevier B.V. All rights reserved."}]}, "item_creator": {"attribute_name": "\u8457\u8005", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Akimoto, Youhei"}], "nameIdentifiers": [{"nameIdentifier": "49819", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Astete-Morales, Sandra"}], "nameIdentifiers": [{"nameIdentifier": "49820", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Teytaud, Olivier"}], "nameIdentifiers": [{"nameIdentifier": "49821", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "\u30d5\u30a1\u30a4\u30eb\u60c5\u5831", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2017-11-15"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "Analysis_runtime_optimization_algorithms_noisy_functions.pdf", "filesize": [{"value": "506.8 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensefree": "\u00a9 2015. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/", "licensetype": "license_note", "mimetype": "application/pdf", "size": 506800.0, "url": {"label": "Analysis_runtime_optimization_algorithms_noisy_functions.pdf", "url": "https://soar-ir.repo.nii.ac.jp/record/17837/files/Analysis_runtime_optimization_algorithms_noisy_functions.pdf"}, "version_id": "d5a56577-2f81-4cce-9128-57cba3b6354e"}]}, "item_keyword": {"attribute_name": "\u30ad\u30fc\u30ef\u30fc\u30c9", "attribute_value_mlt": [{"subitem_subject": "Discrete optimization", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Additive noise", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Runtime analysis", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "\u8a00\u8a9e", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"resourcetype": "journal article", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "Analysis of runtime of optimization algorithms for noisy functions over discrete codomains", "item_titles": {"attribute_name": "\u30bf\u30a4\u30c8\u30eb", "attribute_value_mlt": [{"subitem_title": "Analysis of runtime of optimization algorithms for noisy functions over discrete codomains", "subitem_title_language": "en"}]}, "item_type_id": "6", "owner": "1", "path": ["1221/1222"], "permalink_uri": "http://hdl.handle.net/10091/00018606", "pubdate": {"attribute_name": "PubDate", "attribute_value": "2016-02-03"}, "publish_date": "2016-02-03", "publish_status": "0", "recid": "17837", "relation": {}, "relation_version_is_last": true, "title": ["Analysis of runtime of optimization algorithms for noisy functions over discrete codomains"], "weko_shared_id": -1}
Analysis of runtime of optimization algorithms for noisy functions over discrete codomains
http://hdl.handle.net/10091/00018606
93474bf7-ef2f-4869-adcb-64db932cc106
名前 / ファイル | ライセンス | アクション | |
---|---|---|---|
![]() |
|
Item type | 学術雑誌論文 / Journal Article(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2016-02-03 | |||||
タイトル | ||||||
言語 | en | |||||
タイトル | Analysis of runtime of optimization algorithms for noisy functions over discrete codomains | |||||
言語 | ||||||
言語 | eng | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Discrete optimization | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Additive noise | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Runtime analysis | |||||
資源タイプ | ||||||
資源 | http://purl.org/coar/resource_type/c_6501 | |||||
タイプ | journal article | |||||
著者 |
Akimoto, Youhei
× Akimoto, Youhei× Astete-Morales, Sandra× Teytaud, Olivier |
|||||
信州大学研究者総覧へのリンク | ||||||
氏名 | Akimoto, Youhei | |||||
URL | http://soar-rd.shinshu-u.ac.jp/profile/ja.OeypbUkh.html | |||||
出版者 | ||||||
出版者 | ELSEVIER SCIENCE BV | |||||
引用 | ||||||
内容記述タイプ | Other | |||||
内容記述 | THEORETICAL COMPUTER SCIENCE. 605:42-50 (2015) | |||||
書誌情報 |
THEORETICAL COMPUTER SCIENCE 巻 605, p. 42-50, 発行日 2015-11-15 |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | We consider in this work the application of optimization algorithms to problems over discrete codomains corrupted by additive unbiased noise. We propose a modification of the algorithms by repeating the fitness evaluation of the noisy function sufficiently so that, with a fix probability, the function evaluation on the noisy case is identical to the true value. If the runtime of the algorithms on the noise-free case is known, the number of resampling is chosen accordingly. If not, the number of resampling is chosen regarding to the number of fitness evaluations, in an anytime manner. We conclude that if the additive noise is Gaussian, then the runtime on the noisy case, for an adapted algorithm using resamplings, is similar to the runtime on the noise-free case: we incur only an extra logarithmic factor. If the noise is non-Gaussian but with finite variance, then the total runtime of the noisy case is quadratic in function of the runtime on the noise-free case. (C) 2015 Elsevier B.V. All rights reserved. | |||||
資源タイプ(コンテンツの種類) | ||||||
内容記述タイプ | Other | |||||
内容記述 | Article | |||||
ISSN | ||||||
収録物識別子タイプ | ISSN | |||||
収録物識別子 | 0304-3975 | |||||
書誌レコードID | ||||||
収録物識別子タイプ | NCID | |||||
収録物識別子 | AA00862688 | |||||
DOI | ||||||
関連識別子 | ||||||
識別子タイプ | DOI | |||||
関連識別子 | https://doi.org/10.1016/j.tcs.2015.04.008 | |||||
関連名称 | ||||||
関連名称 | 10.1016/j.tcs.2015.04.008 | |||||
権利 | ||||||
権利情報 | © 2015. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ | |||||
出版タイプ | ||||||
出版タイプ | AM | |||||
出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||
WoS | ||||||
表示名 | Web of Science | |||||
URL | http://gateway.isiknowledge.com/gateway/Gateway.cgi?&GWVersion=2&SrcAuth=ShinshuUniv&SrcApp=ShinshuUniv&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000365059800003 |