检索结果-内蒙古大学图书馆

stochastic runtime analysis of a Cross-Entropy algorithm for traveling salesman problems

THEORETICAL COMPUTER SCIENCE 2018年 724卷 69-86页

作者： Wu, Zijun Moehring, Rolf H. Lai, Jianhui BISEC Pingle Yuan 100 Beijing Peoples R China Beijing Univ Technol Coll Metropolitan Transportat Pingle Yuan 100 Beijing Peoples R China Beijing Univ Technol Sch Appl Math & Phys Beijing Peoples R China Berlin Univ Technol Math Berlin Germany

This article analyzes the stochastic runtime of a Cross-Entropy algorithm mimicking an Max-MM Ant System with iteration-best reinforcement. It investigates the impact of magnitude of the sample size on the runtime to find optimal solutions for TSP instances. For simple TSP instances that have a {1,n}-valued distance function and a unique optimal solution, we show that sample size N is an element of omega(Inn) results in a stochastically polynomial runtime, and N is an element of O(In n) results in a stochastically exponential runtime, where "stochastically" means with a probability of 1 - n(-omega(1)), and n represents number of cities. In particular, for N is an element of omega(In n), we prove a stochastic runtime of O(N . n(6)) with the vertex-based random solution generation, and a stochastic runtime of O(N . n(3) Inn) with the edge-based random solution generation. These runtimes are very close to the best known expected runtime for variants of Max-Min Ant System with best-so-far reinforcement by choosing a small N is an element of omega(In n). They are obtained for the stronger notion of stochastic runtime, and analyze the runtime in most cases. We also inspect more complex instances with n vertices positioned on an m x m grid. When the n vertices span a convex polygon, we obtain a stochastic runtime of O(n(4)m(3+is an element of)) with the vertex-based random solution generation, and a stochastic runtime of O(n(3)m(3+is an element of)) for the edge-based random solution generation. When there are k is an element of O(1) many vertices inside a convex polygon spanned by the other n k vertices, we obtain a stochastic runtime of O(n(4)m(5+is an element of) + n(6k-1)m(is an element of)) with the vertex-based random solution generation, and a stochastic runtime of O(n(3)m(5+is an element of) + n(3k)m(is an element of)) with the edge-based random solution generation. These runtimes are better than the expected runtime for the so-called (mu+lambda) EA reported in a r

关键词： Probabilistic analysis of algorithms stochastic runtime analysis of evolutionary algorithms Cross Entropy algorithm Max-MM Ant System (mu plus lambda) EA

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：