GSL中的模拟退火

模拟退火

    当一个空间的结构不能很好地被理解或不光滑时,常常使用随机搜索技术,因此不能使用像牛顿法(需要计算雅可比矩阵的导数)这样的技术。特别是,这些技术经常被用于解决组合优化问题,如旅行推销员问题。

    模拟退回的目的是在空间中找到一个点,这个点上的实值能量函数(或成本函数)是最小的。模拟退火是一种极小化技术,在避免局部极小化方面取得了良好的效果;它是基于在连续较低的温度下在空间中进行随机行走的想法,其中玻尔兹曼分布给出迭代一步的概率。

    本章描述的函数声明在头文件gsl_siman.h中。

28.1 模拟退火算法

    模拟退火算法随机遍历问题空间,寻找低能量点;在这些随机走动中,走一步的概率由玻尔兹曼分布决定,

GSL中的模拟退火

     换句话说,如果新能量较低,就会出现一个台阶。如果新能量较高,相变仍可发生,且其可能性与温度T成正比,与能量差Ei+1−Ei成反比。

    温度T初始设置为一个较高的值,并在该温度下进行随机走动。然后根据冷却程序,将温度略微降低,例如:TT /µT,其中µT略大于1。

    采取能提供更高能量的步骤的可能性很小,这使得模拟退火经常能够摆脱局部最小值。

28.2 模拟退火函数

void gsl_siman_solve(const gsl_rng * r, void * x0_p, gsl_siman_Efunc_t Ef,

gsl_siman_step_t take_step, gsl_siman_metric_t distance,

gsl_siman_print_t print_position, gsl_siman_copy_t copyfunc,

gsl_siman_copy_construct_t copy_constructor,

gsl_siman_destroy_t destructor, size_t element_size,

gsl_siman_params_t params)

    本函数通过给定的空间执行模拟退火搜索。通过提供函数Ef和distance来指定空间。模拟退火步骤使用随机数生成器r和函数take_step生成。

系统的启动配置应该由x0_p给出。函数提供了两种更新配置的模式,固定大小模式和可变大小模式。在固定大小模式下,配置被存储为一个大小为element_size的内存块。使用标准库函数malloc()、memcpy()和free()在内部创建、复制和销毁该配置的副本。函数指针copyfunc、copy_constructor和destructor应该是固定大小模式下的空指针。在可变大小模式下,copyfunc、

copy_constructor和析构函数用于在内部创建、复制和销毁配置。变量element_size在可变大小模式下应该为零。

params结构(如下所述)通过向算法提供温度调度和其他可调参数来控制运行。

在退出时,搜索过程中获得的最佳结果被放在x0_p中。如果退火过程成功,这应该是空间中最优点的一个很好的近似值。

    如果函数指针print_position不为空,调试日志将打印到stdout,显示如下列:

#-iter  #-evals  temperature  position  energy  best_energy

     以及print_position函数本身的输出。如果print_position为空,则不输出任何信息。

    模拟退火程序需要几个用户指定的函数来定义配置空间和能量函数。下面给出了这些函数的原型。

gsl_siman_Efunc_t

    本类型函数将返回配置xp的能量:

double  (*gsl_siman_Efunc_t)  (void *xp)

上一篇:接口测试执行工具Postman:模拟请求、用例执行、断言、批量运行用例、简单持续集成


下一篇:list tuple