代码 | 自适应大邻域搜索系列之(6) - 判断接受准则SimulatedAnnealing的代码解析

本文主要是介绍代码 | 自适应大邻域搜索系列之(6) - 判断接受准则SimulatedAnnealing的代码解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码 | 自适应大邻域搜索系列之(6) - 判断接受准则SimulatedAnnealing的代码解析

前言

前面三篇文章对大家来说应该很简单吧?不过轻松了这么久,今天再来看点刺激的。关于判断接受准则的代码。其实,判断接受准则有很多种,效果也因代码而异。今天介绍的是模拟退火的判断接受准则。那么,相关的原理之前的推文有讲过,不懂的同学回去翻翻这个文章 复习一下哈,小编也回去看看,咳咳~。好了,废话不多说,开始干活。

01 总体概述

其实这个ALNS的代码库提供了很多的判断接受准则,有最简单的直接根据目标值来判断,也有各种复杂的模拟退火降温冷却等过程来判断。不过,今天挑一个最具代表性的来讲吧,就是模拟退火的判断接受准则。其代码实现是由两个类IAcceptanceModule、SimulatedAnnealing来实现的。它们的关系依旧如下:
1240

其中IAcceptanceModule依旧是抽象类,只提供接口。下面对这两货进行解析。

02 IAcceptanceModule

这个抽象类也很简单,只提供了一个接口transitionAccepted,以用来判断是否要接受新的解,为纯虚函数,需要在后续的代码中重写的。

class IAcceptanceModule
{
public://! Indicate if the new created solution have to be accepted or not//! \param bestSolutionManager a reference to the best solution manager.//! \param currentSolution current solution.//! \param newSolution new solution.//! \param status the status of the current alns iteration.//! \return true if the transition is accepted, false otherwise.virtual bool transitionAccepted(IBestSolutionManager& bestSolutionManager, ISolution& currentSolution, ISolution& newSolution, ALNS_Iteration_Status& status) = 0;//! Some Acceptance modules needs to initialize some variable//! only when the solver actualy starts working. In this case//! you should override this method.virtual void startSignal(){};
};

03 SimulatedAnnealing

SimulatedAnnealing继承于上面的接口类IAcceptanceModule,它利用模拟退火的判断接受准则实现了transitionAccepted的功能。值得注意的是,该类成员变量里面是一个CoolingSchedule,用来获取当前温度。该表有另一个抽象类ICoolingSchedule定义,下面会详细说道。

class SimulatedAnnealing: public IAcceptanceModule {
private://! The cooling schedule to be use to compute the temperature each time it//! is needed.ICoolingSchedule* coolingSchedule;
public://! Constructor.//! \param cs the cooling schedule to be used by the simulated annealing.SimulatedAnnealing(ICoolingSchedule& cs);//! Destructor.virtual ~SimulatedAnnealing();//! Compute if the newly created solution have to be accepted or notbool transitionAccepted(IBestSolutionManager& bestSolutionManager, ISolution& currentSolution, ISolution& newSolution, ALNS_Iteration_Status& status);virtual void startSignal();};

其成员函数的实现也非常的简单,不过多说两句。先利用CoolingSchedule获取当前冷却过程的温度。如果新解目标值<当前解的,那么直接接受就行了。如果>,那么按照一定的概率接受。具体公式解释嘛,小编截个图过来吧,因为在以前的文章已经讲过了:
1240

不过这里的能量差计算用的是解的目标惩罚值算的,不是目标值。

bool SimulatedAnnealing::transitionAccepted(IBestSolutionManager& bestSolutionManager, ISolution& currentSolution, ISolution& newSolution, ALNS_Iteration_Status& status)
{double temperature = coolingSchedule->getCurrentTemperature();if(newSolution < currentSolution){return true;}else{double difference = newSolution.getPenalizedObjectiveValue() - currentSolution.getPenalizedObjectiveValue();double randomVal = static_cast<double>(rand())/static_cast<double>(RAND_MAX);return (exp(-1*difference/temperature)>randomVal);}
}void SimulatedAnnealing::startSignal()
{coolingSchedule->startSignal();
}

04 ICoolingSchedule

4.1 ICoolingSchedule

这货是一个抽象类,CoolingSchedule有很多种类型,根据不同需要由这个类可以派生出下面类型的CoolingSchedule:
1240

ICoolingSchedule只提供了两个接口,其中getCurrentTemperature是纯虚函数,用以获取当前的退火温度,需要重写。

class ICoolingSchedule
{
public://! \return the current temperature.virtual double getCurrentTemperature()=0;//! This method should be called when the optimization//! process start. The cooling schedules that actually need//! this should override this method.virtual void startSignal(){};
};

4.2 LinearCoolingSchedule

由于CoolingSchedule有很多类型,小编挑一个LinearCoolingSchedule给大家讲解吧。LinearCoolingSchedule主要的根据是迭代的次数来工作的。成员函数getCurrentTemperature是核心,用以获取当前的温度,便于上面的判断接受准则计算概率。

class LinearCoolingSchedule: public ICoolingSchedule {
private://! The current temperature.double currentTemperature;//! The amount to remove at each temperature recomputation.double amountRemove;
public://! Constructor.//! \param initSol the initial solution.//! \param csParam the cooling schedule parameters.//! \param nbIterations the number of iterations to be performed.LinearCoolingSchedule(ISolution& initSol, CoolingSchedule_Parameters& csParam, size_t nbIterations);//! Constructor.//! \param startingTemperature the initial temperature.//! \param nbIterations the number of iterations to be performed.LinearCoolingSchedule(double startingTemperature, size_t nbIterations);//! Destructor.virtual ~LinearCoolingSchedule();//! Compute and return the current temperature.//! \return the current temperature.double getCurrentTemperature();void startSignal(){};
};

然后现在来看看其具体方法是怎么实现的吧。其实也很简单,没有那么复杂。每次获取currentTemperature的时候呢,先让currentTemperature降降温,再返回。降温的幅度是利用currentTemperature 减去 amountRemove实现的。那么amountRemove又是怎么得出来的呢?LinearCoolingSchedule提供了两个构造函数,对应不同的计算方法:

  1. currentTemperature = (csParam.setupPercentage*initSol.getPenalizedObjectiveValue())/(-log(0.5));
    amountRemove = currentTemperature/static_cast(nbIterations);
    其中,setupPercentage为参数,nbIterations为总的迭代次数。
  2. amountRemove = startingTemperature/static_cast(nbIterations);
    其中,startingTemperature为传入参数。
LinearCoolingSchedule::LinearCoolingSchedule(ISolution& initSol, CoolingSchedule_Parameters& csParam, size_t nbIterations) {currentTemperature = (csParam.setupPercentage*initSol.getPenalizedObjectiveValue())/(-log(0.5));amountRemove = currentTemperature/static_cast<double>(nbIterations);}LinearCoolingSchedule::LinearCoolingSchedule(double startingTemperature, size_t nbIterations) {assert(nbIterations>0);assert(startingTemperature>=0);currentTemperature = startingTemperature;amountRemove = startingTemperature/static_cast<double>(nbIterations);}LinearCoolingSchedule::~LinearCoolingSchedule() {// Nothing to be done.
}double LinearCoolingSchedule::getCurrentTemperature()
{currentTemperature-= amountRemove;if(currentTemperature < 0){currentTemperature = 0;}assert(currentTemperature>=0);return currentTemperature;
}

05 小结

今天讲的总体也不是很难,相信之前模拟退火学得好的小伙伴一眼就能看懂了,如果其他小伙伴还不是很理解的话,回去看看之前的文章,看看模拟退火的判断接受准则再多加理解,相信对大家不是什么问题。

至此,代码已经讲得差不多了,估摸着还能再做几篇文章,依然感谢大家一路过来的支持。谢谢!咱们下期再见。

代码及相关内容可关注公众号。更多精彩尽在微信公众号【程序猿声】
微信公众号

posted @ 2019-05-10 20:25 短短的路走走停停 阅读( ...) 评论( ...) 编辑 收藏

这篇关于代码 | 自适应大邻域搜索系列之(6) - 判断接受准则SimulatedAnnealing的代码解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/161494

相关文章

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

java解析jwt中的payload的用法

《java解析jwt中的payload的用法》:本文主要介绍java解析jwt中的payload的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解析jwt中的payload1. 使用 jjwt 库步骤 1:添加依赖步骤 2:解析 JWT2. 使用 N

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa