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

SimILS: a simulation-based extension of the iterated local search metaheuristic for stochastic combinatorial optimization

引用

JOURNAL OF SIMULATION 2016年第1期10卷 69-77页

作者： Grasas, Alex Juan, Angel A. Lourenco, Helena R. EADA Business Sch Barcelona 08011 Spain Open Univ Catalonia IN3 Barcelona Spain Univ Pompeu Fabra Barcelona Spain

Iterated Local Search (ILS) is one of the most popular single-solution-based metaheuristics. ILS is recognized by many authors as a relatively simple yet efficient framework able to deal with complex combinatorial optimization problems (COPs). ILS-based algorithms have been successfully applied to provide near-optimal solutions to different COPs in logistics, transportation, production, etc. However, ILS is designed to solve COPs under deterministic scenarios. In some real-life applications where uncertainty is present, the deterministic assumption makes the model less accurate since it does not reflect the real stochastic nature of the system. This paper presents the SimILS framework that extends ILS by integrating simulation to be able to cope with stochastic COPs in a natural way. The paper also describes several tested applications that illustrate the main concepts behind SimILS and give rise to a new brand of ILS-based algorithms.

关键词： iterated local search simulation stochastic combinatorial optimization simheuristics

来源：评论

学校读者我要写书评

暂无评论

A metaheuristic framework for stochastic combinatorial optimization problems based on GPGPU with a case study on the probabilistic traveling salesman problem with deadlines

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2013年第1期73卷 74-85页

作者： Weyland, Dennis Montemanni, Roberto Gambardella, Luca Maria IDSIA Ist Dalle Molle Studi Intelligenza Artificiale CH-6928 Manno Lugano Switzerland

In this work we propose a general metaheuristic framework for solving stochastic combinatorial optimization problems based on general-purpose computing on graphics processing units (GPGPU). This framework is applied to the probabilistic traveling salesman problem with deadlines (PTSPD) as a case study. Computational studies reveal significant improvements over state-of-the-art methods for the PTSPD. Additionally, our results reveal the huge potential of the proposed framework and sampling-based methods for stochastic combinatorial optimization problems. (C) 2012 Elsevier Inc. All rights reserved.

关键词： GPGPU CUDA stochastic combinatorial optimization stochastic vehicle routing Monte Carlo sampling

来源：评论

学校读者我要写书评

暂无评论

A Test Score-Based Approach to stochastic Submodular optimization

引用

MANAGEMENT SCIENCE 2021年第2期67卷 1075-1092页

作者： Sekar, Shreyas Vojnovic, Milan Yun, Se-Young Harvard Univ Harvard Business Sch Boston MA 02163 USA London Sch Econ LSE Dept Stat London WC2A 2AE England Korea Adv Inst Sci & Technol KAIST Grad Sch Artificial Intelligence Daejeon 34141 South Korea

We study the canonical problem of maximizing a stochastic submodular function subject to a cardinality constraint, where the goal is to select a subset from a ground set of items with uncertain individual performances to maximize their expected group value. Although near-optimal algorithms have been proposed for this problem, practical concerns regarding scalability, compatibility with distributed implementation, and expensive oracle queries persist in large-scale applications. Motivated by online platforms that rely on individual item scores for content recommendation and team selection, we study a special class of algorithms that select items based solely on individual performance measures known as test scores. The central contribution of this work is a novel and systematic framework for designing test score-based algorithms for a broad class of naturally occurring utility functions. We introduce a new scoring mechanism that we refer to as replication test scores and prove that as long as the objective function satisfies a diminishing-returns condition, one can leverage these scores to compute solutions that are within a constant factor of the optimum. We then extend these scoring mechanisms to the more general stochastic submodular welfare-maximization problem, where the goal is to partition items into groups to maximize the sum of the expected group values. For this more difficult problem, we show that replication test scores can be used to develop an algorithm that approximates the optimal solution up to a logarithmic factor. The techniques presented in this work bridge the gap between the rigorous theoretical work on submodular optimization and simple, scalable heuristics that are useful in certain domains. In particular, our results establish that in many applications involving the selection and assignment of items, one can design algorithms that are intuitive and practically relevant with only a small loss in performance compared with the state-of-the-art ap

关键词： stochastic combinatorial optimization submodular functions welfare maximization test scores

来源：评论

学校读者我要写书评

暂无评论

The first AI4TSP competition: Learning to solve stochastic routing problems

引用

ARTIFICIAL INTELLIGENCE 2023年 319卷

作者： Zhang, Yingqian Bliek, Laurens da Costa, Paulo Afshar, Reza Refaei Reijnen, Robbert Catshoek, Tom Vos, Daniel Verwer, Sicco Schmitt-Ulms, Fynn Hottung, Andre Shah, Tapan Sellmann, Meinolf Tierney, Kevin Perreault-Lafleur, Carl Leboeuf, Caroline Bobbio, Federico Pepin, Justine Silva, Warley Almeida Gama, Ricardo Fernandes, Hugo L. Zaefferer, Martin Lopez-Ibanez, Manuel Irurozki, Ekhine Eindhoven Univ Technol Eindhoven Netherlands Delft Univ Technol Delft Netherlands McGill Univ Montreal PQ Canada Bielefeld Univ Bielefeld Germany Gen Elect Boston MA USA InsideOpt Dover DE USA Univ Montreal Montreal PQ Canada Polytech Inst Viseu Viseu Portugal Rockets Awesome New York NY USA Univ Manchester Manchester England Telecom Paris Paris France DHBW Ravensburg Ravensburg Germany

This paper reports on the first international competition on AI for the traveling salesman problem (TSP) at the International Joint Conference on Artificial Intelligence 2021 (IJCAI-21). The TSP is one of the classical combinatorial optimization problems, with many variants inspired by real-world applications. This first competition asked the participants to develop algorithms to solve an orienteering problem with stochastic weights and time windows (OPSWTW). It focused on two learning approaches: surrogate-based optimization and deep reinforcement learning. In this paper, we describe the problem, the competition setup, and the winning methods, and give an overview of the results. The winning methods described in this work have advanced the state-of-the-art in using AI for stochastic routing problems. Overall, by organizing this competition we have introduced routing problems as an interesting problem setting for AI researchers. The simulator of the problem has been made open-source and can be used by other researchers as a benchmark for new

关键词： AI for TSP competition Travelling salesman problem Routing problem stochastic combinatorial optimization Surrogate-based optimization Deep reinforcement learning

来源：评论

学校读者我要写书评

暂无评论

Robust university course timetabling problem subject to single and multiple disruptions

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第2期283卷 630-646页

作者： Gulcu, Ayla Akkan, Can Fatih Sultan Mehmet Univ Dept Comp Sci Halic Campus TR-34445 Istanbul Turkey Sabanci Univ Sch Management TR-34956 Istanbul Turkey

University course timetables are often finalized in stages, in between which, changes in the data make the earlier version infeasible. As each version is announced to the community, it is desirable to have a robust initial timetable, i.e. one that can be repaired with limited number of changes and yielding a new solution whose quality is degraded as little as possible. We define two versions of the robust timetabling problem, first one assuming that only one lecture is disrupted (its scheduled period ceasing to be feasible) and the second one assuming multiple lectures are disrupted. The objective of the algorithms is to identify a good Pareto front defined by the solution quality (penalty associated with soft-constraint violations) and the robustness measure. Two versions of a multi-objective simulated annealing (MOSA) algorithm is developed (MOSA-SD and MOSA-SAA, for single and multiple disruptions, respectively), with the difference being in the way robustness of a solution is estimated within the MOSA algorithm. Extensive computational experiments done using the International Timetabling Competition ITC-2007 data set confirm that MOSA-SD outperforms a genetic algorithm from the literature, and MOSA-SAA outperforms MOSA-SD when there are multiple disruptions. For MOSA-SAA an innovative solution network to structure feasible solutions for a set of disruption scenarios has been developed to efficiently perform sample average approximation (SAA) calculations, which can be adopted for other stochastic combinatorial optimization problems. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Timetabling Robustness Bi-criteria optimization Simulated Annealing stochastic combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Designing e-commerce supply chains: a stochastic facility-location approach

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2019年第2期26卷 507-528页

作者： Pages-Bernaus, Adela Ramalhinho, Helena Juan, Angel A. Calvet, Laura Univ Lleida Dept Math Lleida Spain Univ Pompeu Fabra Dept Econ & Business Barcelona Spain Open Univ Catalonia Dept Comp Sci IN3 Barcelona Spain

e-Commerce activity has been increasing during recent years, and this trend is expected to continue in the near future. e-Commerce practices are subject to uncertainty conditions and high variability in customers' demands. Considering these characteristics, we propose two facility-location models that represent alternative distribution policies in e-commerce (one based on outsourcing and another based on in-house distribution). These models take into account stochastic demands as well as more than one regular supplier per customer. Two methodologies are then introduced to solve these stochastic versions of the well-known capacitated facility-location problem. The first is a two-stage stochastic-programming approach that uses an exact solver. However, we show that this approach is not appropriate for tackle large-scale instances due to the computational effort required. Accordingly, we also introduce a "simheuristic" approach that is able to deal with large-scale instances in short computing times. An extensive set of benchmark instances contribute to illustrate the efficiency of our approach, as well as its potential utility in modern e-commerce practices.

关键词： e-commerce supply-chain management capacitated facility-location problem stochastic combinatorial optimization simheuristics stochastic programming

来源：评论

学校读者我要写书评

暂无评论

Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem

引用

JOURNAL OF combinatorial optimization 2018年第3期35卷 794-813页

作者： Levin, Asaf Vainer, Aleksander Technion Fac Ind Engn & Management IL-32000 Haifa Israel

We consider stochastic variants of the NP-hard 0/1 knapsack problem in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. The goal is to compute a policy for insertion of the items, that maximizes the expected value of the set of items placed in the knapsack. These variants that we study differ only in the formula for computing the value of the final solution obtained by the policy. We consider both nonadaptive policies (that designate a priori a fixed subset or permutation of items to insert) and adaptive policies (that can make dynamic decisions based on the instantiated sizes of the items placed in the knapsack thus far). Our work characterizes the benefit of adaptivity. For this purpose we use a measure called the adaptivity gap: the supremum over instances of the ratio between the expected value obtained by an optimal adaptive policy and the expected value obtained by an optimal non-adaptive policy. We show that while for the variants considered in the literature this quantity is bounded by a constant there are other variants where it is unbounded.

关键词： Knapsack Benefit of adaptivity stochastic combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

A simheuristic approach for evolving agent behaviour in the exploration for novel combat tactics

引用

OPERATIONS RESEARCH PERSPECTIVES 2019年 6卷

作者： Lam, Chiou-Peng Masek, Martin Kelly, Luke Papasimeon, Michael Benke, Lyndon Edith Cowan Univ Sch Sci 270 Joondalup Dr Joondalup WA 6027 Australia Def Sci Technol Grp Dept Def Joint & Operat Anal Div 506 Lorimer St Fishermans Bend Vic 3207 Australia

The automatic generation of behavioural models for intelligent agents in military simulation and experimentation remains a challenge. Genetic Algorithms are a global optimization approach which is suitable for addressing complex problems where locating the global optimum is a difficult task. Unlike traditional optimisation techniques such as hill-climbing or derivatives-based methods, Genetic Algorithms are robust for ad- on dressing highly multi-modal and discontinuous search landscapes. In this paper, we outline a simheuristic GA-based approach for automatic generation of finite state machine based behavioural models of intelligent agents, where the aim is the identification of novel combat tactics. Rather than evolving states, the proposed approach evolves a sequence of transitions. We also discuss workable starting points for the use of Genetic Algorithms for such scenarios, shedding some light on the associated design and implementation difficulties.

关键词： Simheuristics Genetic algorithms Multiagent simulations stochastic combinatorial optimization Finite state machines

来源：评论

学校读者我要写书评

暂无评论

Low-autocorrelation binary sequences: On improved merit factors and runtime predictions to achieve them

引用

APPLIED SOFT COMPUTING 2017年 56卷 262-285页

作者： Boskovic, Borko Brglez, Franc Brest, Janez Univ Maribor Fac Elect Engn & Comp Sci SI-2000 Maribor Slovenia NC State Univ Comp Sci Raleigh NC 27695 USA

The search for binary sequences with a high figure of merit, known as the low autocorrelation binary sequence (labs) problem, represents a formidable computational challenge. To mitigate the computational constraints of the problem, we consider solvers that accept odd values of sequence length L and return solutions for skew- symmetric binary sequences only - with the consequence that not all best solutions under this constraint will be optimal for each L. In order to improve both, the search for best merit factor and the asymptotic runtime performance, we instrumented three stochastic solvers, the first two are state-of-the-art solvers that rely on variants of memetic and tabu search (lssMAts and lssRRts), the third solver (lssOrel) organizes the search as a sequence of independent contiguous self-avoiding walk segments. By adapting a rigorous statistical methodology to performance testing of all three combinatorial solvers, experiments show that the solver with the best asymptotic average-case performance, lssOrel_8 = 0.000032 * 1.1504(I), has the best chance of finding solutions that improve, as L increases, figures of merit reported to date. The same methodology can be applied to engineering new labs solvers that may return merit factors even closer to the conjectured asymptotic value of 12.3248. (c) 2017 Elsevier B.V. All rights reserved.

关键词： Low-autocorrelation binary sequences Self-avoiding walk stochastic combinatorial optimization Asymptotic average-case performance

来源：评论

学校读者我要写书评

暂无评论

Metaheuristics and Cloud Computing: A Case Study on the Probabilistic Traveling Salesman Problem with Deadlines 1

引用

15th International Conference on Computer Aided Systems Theory

作者： Weyland, Dennis Univ Svizzera Italiana Lugano Switzerland Univ Brescia Dept Econ & Management Brescia Italy

ISBN: (数字)9783319273402

ISBN: (纸本)9783319273402;9783319273396

In this work we study the potential of cloud computing in the context of optimization. For this purpose we perform a case study on the Probabilistic Traveling Salesman Problem with Deadlines, an extremely difficult stochastic combinatorial optimization problem. By using a large amount of computational resources in parallel, it is possible to obtain significantly better solutions for the Probabilistic Traveling Salesman Problem with Deadlines in the same amount of time. For many different applications this advantage clearly outweighs the requirement for additional computational resources, in particular considering the convenience of modern cloud infrastructures.

关键词： stochastic combinatorial optimization Cloud computing Probabilistic traveling salesman problem with deadlines

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：