专栏首页CreateAMind开源ALNS 自适应大邻域搜索(Adaptive Large Neighborhood Search)

开源ALNS 自适应大邻域搜索(Adaptive Large Neighborhood Search)

https://github.com/N-Wouda/ALNS

This package offers a general, well-documented and tested implementation of the adaptive large neighbourhood search (ALNS) meta-heuristic, based on the description given in Pisinger and Ropke (2010). It may be installed in the usual way as,

pip install alns

How to use

The alns package exposes two classes, ALNS and State. The first may be used to run the ALNS algorithm, the second may be subclassed to store a solution state - all it requires is to define an objective member function.

The ALNS algorithm must be supplied with an acceptance criterion, to determine the acceptance of a new solution state at each iteration. An overview of common acceptance criteria is given in Santini et al. (2018). Several have already been implemented for you, in alns.criteria,

  • HillClimbing. The simplest acceptance criterion, hill-climbing solely accepts solutions improving the objective value.
  • RecordToRecordTravel. This criterion only accepts solutions when the improvement meets some updating threshold.
  • SimulatedAnnealing. This criterion accepts solutions when the scaled probability is bigger than some random number, using an updating temperature.

Each acceptance criterion inherits from AcceptanceCriterion, which may be used to write your own.

Examples

The examples/ directory features some example notebooks showcasing how the ALNS library may be used. Of particular interest are,

  • The travelling salesman problem (TSP), here. We solve an instance of 131 cities to within 2.1% of optimality, using simple destroy and repair heuristics with a post-processing step.
  • The cutting-stock problem (CSP), here. We solve an instance with 180 beams over 165 distinct sizes to within 1.35% of optimality in only a very limited number of iterations.

References

  • Pisinger, D., and Ropke, S. (2010). Large Neighborhood Search. In M. Gendreau (Ed.), Handbook of Metaheuristics (2 ed., pp. 399-420). Springer.
  • Santini, A., Ropke, S. & Hvattum, L.M. (2018). A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic. Journal of Heuristics 24 (5): 783-815.

本文分享自微信公众号 - CreateAMind(createamind)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • vae 相关论文 表示学习 1

    05 Nov 2016 (modified: 18 Apr 2017)ICLR 2017 conference submissionReaders: Ever...

    用户1908973
  • 强化学习框架 IMPALA 介绍

    In this work we aim to solve a large collection of tasks using a single reinforc...

    用户1908973
  • deepmind 做通用人工智能的思路

    Automated discovery of early visual concepts from raw image data is a major open...

    用户1908973
  • 【论文推荐】最新6篇图像描述生成相关论文—语言为枢纽、细粒度、生成器、注意力机制、策略梯度优化、判别性目标

    【导读】专知内容组整理了最近六篇图像描述生成(Image Caption)相关文章,为大家进行介绍,欢迎查看! 1. Unpaired Image Captio...

    WZEARW
  • vae 相关论文 表示学习 1

    05 Nov 2016 (modified: 18 Apr 2017)ICLR 2017 conference submissionReaders: Ever...

    用户1908973
  • 袖珍分布式系统(一)

    本文是Distributed systems for fun and profit的第一部分,本文是阅读该文后的一些记录。

    zhuanxu
  • 十大革命性理论(Top 10 revolutionary scientifictheories)中英版(19k字)

    本篇《十大革命性理论》(Top 10 revolutionary scientific theories |Science News)中英文对照版AB,把原文倒...

    秦陇纪
  • UVA 11292 Dragon of Loowater(简单贪心)

    Problem C: The Dragon of Loowater Once upon a time, in the Kingdom of Loowater, ...

    Angel_Kitty
  • uva-----11292 The Dragon of Loowater

    Problem C: The Dragon of Loowater Once upon a time, in the Kingdom of Loowater, ...

    Gxjun
  • 结合人类和机器智能,利用社会媒体图像进行快速损伤评估(CS SI)

    快速损失评估是应对组织在灾害发生时执行的核心任务之一,目的是了解道路、桥梁和建筑物等基础设施的损失程度。 这项工作分析了社会媒体图像内容的有用性,以执行快速损害...

    用户7095611

扫码关注云+社区

领取腾讯云代金券