SEvoBench用户指南

介绍
基础
API介绍
- 关于问题集的API
- 关于算法的API
示例

介绍

关于SEvoBench

SEvoBench是一个使用C++编写的单目标优化算法测试框架.它的目的是方便单目标进化算法研究工作者快速有效测试算法的优化性能,为此框架不仅为用户提供了优化算法和优化问题的一系列接口,而且还内置了一定数量的state of the art 的优化算法和测试集.

安装

从GitHub上下载源码到用户个人工作文件夹下即可.SEvoBench计算内核位于SEvoBench/include/SEvoBench文件夹下,该文件夹包含了所需要的所有头文件.

系统要求

Compile:支持C++20以上的编译器

编译项目

由于SEvoBench基于C++模版编程实现,无需提前编译成链接库,只需引入项目头文件,指定项目头文件搜索路径即可.

使用CMake进行包管理

SEvoBench支持使用CMake进行包管理

cmake_minimum_required(VERSION 3.15)

cmake -B build  -S . -DBUILD_TESTS=OFF -DBUILD_EXAMPLE=OFF -DCMAKE_INSTALL_PREFIX=/* 用户指定文件夹 */   
cd build &&cmake --build .&& cmake --install .

快速开始

为了演示我们使用内置的DE算法和CEC2020测试集.有关更详细的内容,在文档后面会讲解.

以下代码为DE算法在CEC2020测试集上测试

#include"SEvoBench/parallel_algorithm_benchmark.hpp"
#include<cstdio>
int main() {
    auto data=sevobench::evo_bench<sevobench::DE, sevobench::CEC2020>();
    auto table=data.get_table_data();
    auto alg_name=data.algorithm_name();
    auto pro_name=data.problem_name();
    std::printf("Algorithm:%s Suite:%s,Dim:%d\n",alg_name,pro_name,data.problem_dim());
    for(int i=0;i<data.problem_size();i++) {
        std::printf("F%d mean:%f,std:%f,best:%f,time:%fms,1/4best:%f,middle:%f,3/4best:%f,worst:%f\n",i+1,table[8*i],table[8*i+1],table[8*i+2],table[8*i+3],table[8*i+4],table[8*i+5],table[8*i+6],table[8*i+7]);
    }
    return 0;
}

编译选项

对于GCC Clang编译器,推荐编译命令

-O3 -ffast-math -march=native -std=c++20 -lpthread

对于MSVC编译器,推荐编译命令

/std:c++20 /O2 /fp:fast  /arch:AVX2 /F 8388608

使用CMake

cmake_minimum_required(VERSION 3.15)
project(quickstart LANGUAGES CXX)
set(EXE quickstart)
add_executable(${EXE} quickstart.cpp)
find_package(SEvoBench REQUIRED)
set_target_properties(${EXE} PROPERTIES
        CXX_STANDARD 20
        CXX_STANDARD_REQUIRED ON)
target_link_libraries(${EXE} PUBLIC SEvoBench::SEvoBench)
set(CMAKE_BUILD_TYPE Release)
set(CMAKE_CONFIGURATION_TYPES Release)
target_compile_options(${EXE} PRIVATE
        $<$<CXX_COMPILER_ID:MSVC>:/fp:fast /arch:AVX2 /F 8388608>
        $<$<NOT:$<CXX_COMPILER_ID:MSVC>>:-ffast-math -march=native -Wall -Wextra>
)
target_link_libraries(${EXE} PRIVATE
        $<$<CXX_COMPILER_ID:GNU>:pthread>
)

基础

项目结构

内容	头文件
algorithm基类	single_algorithm.hpp
problem基类	single_problem.hpp
并行计算池	parallel_task.hpp
平台工具函数	tool.hpp
优化算法	pso.hpp de.hpp ...
优化问题	cec2020.hpp cec2022.hpp ...
优化算法测试	parallel_algorithm_benchmark.hpp
约束与概念	common_concept.hpp

由于SEvoBench使用模版编程的风格,所以平台中的优化算法使用模版函数风格,如果你对模版函数不了解,请参阅cppreference网站, David Vandevoorde and Nicolai M. Josuttis.所著的《 C++ template: the complete guide》.《C++ Primer Fifth Edition》第十六章内容. C++20引入了约束与概念,本框架也使用约束与概念用于更好的进行模版编程.

SEvoBench中优化算法一般使用如下声明

template<int Dim,int Pop_Size,int Max,bool Memory_Flag=false,typename F,std::floating_point T,typename Parameter_Type=algorithm_parameter<T>>
inline auto algorithm_func(F&& function,T l,T r,const Parameter_Type& pt=Parameter_Type()) noexcept;

如果你不了解auto关键词,请参阅

解释一下函数的模版参数代表的意义

int Dim: 整数类型.指代优化问题函数的维度.
int Pop_Size: 整数类型.对于群智能优化算法来说,指代算法初始种群的大小.用户一般对特定算法设置默认值.
int Max: 指代算法的终止条件.当模版参数Memory_Flag为True时,指代算法最大迭代次数.当模版参数Memory_Flag为False时.指代优化问题的适应度最大计算次数.用户一般对特定算法设置默认值.
bool Memory_Flag: Bool类型.当Memory_Flag为True时,算法计算过程中,会记录收敛过程,用数组来存储数据;当Memory_Flag为False时,不会记录收敛过程.用户一般对特定算法设置默认值.
typename F:指定优化问题类型.不需要用户去声明,会根据函数实参function自动推导.
std::floating_point T:指定计算所需的浮点类型.不需要用户去声明,会根据函数实参自动推导.
typename Parameter_Type:指定封装算法参数的类.算法参数作为算法很重要的一部分,但是不同算法有着各自的参数,为了对参数设置有统一的接口,用户需要提前将算法参数封装成一个类,并为参数设置默认值.比如将封装好的 algorithm_parameter<T> 作为 Parameter_Type 默认类型,当然Parameter_Type也会根据函数实参pt自动推导

对函数实参的说明

F&& function:对于函数实参的F类型function,要求具有以下特性

auto result=function(x);// function的实参x要求为数组类型指针,result为function函数计算返回的结果.

T l,T r:SEvoBench假设问题为Bound constrained optimization problems,所以l,r分别指定问题变量域的下界和上界.
const Parameter_Type& pt=Parameter_Type():用户可以使用内置的类,也可自定义参数类,但确保类成员变量和内置的类保持一致.

由于Modern C++的特性,我们可以根据模版参数的不同,返回不同的函数值类型.当用户自己实现一个algorithm_func函数时,SEvoBench要求用户根据模版参数类型Memory_Flag的不同返回不同的函数值.

template<int Dim,int Pop_Size,int Max,bool Memory_Flag=false,typename F,std::floating_point T,typename Parameter_Type=algorithm_parameter<T>>
inline auto algorithm_func(F&& function,T l,T r,const Parameter_Type& pt=Parameter_Type()) noexcept {
// 中间过程省略
if constexpr(Memory_Flag)
        return std::make_tuple(best_pos, best_fit,convergence_curve);
if constexpr(!Memory_Flag)
    return std::make_pair(best_pos, best_fit);
}

SEvoBench假定算法求解问题的全局最小值
当Memory_Flag为True时,函数返回std::tuple类型,分别存储问题的最优解,最优值,记录收敛过程的数组.
当Memory_Flag为False时,函数返回std::pair类型,分别存储问题的最优解,最优值.

对记录收敛过程的convergence_curve变量,要求其数据结构类型支持适配std::begin() 和std::end()函数.对于convergence_curve变量如何存储收敛数据,要求如下形式存储.

 template<int Dim,int Pop_Size,int Max,bool Memory_Flag=false,typename F,std::floating_point T,typename Parameter_Type=algorithm_parameter<T>>
inline auto algorithm_func(F&& function,T l,T r,const Parameter_Type& pt=Parameter_Type()) noexcept {

/*
 声明过程省略
 */

  /*
  Max_Itreation取决于模版变量Max,Max是最大迭代次数还是适应度最大计算次数则取决于模版变量B
  */
 for (int iteration=0; iteration < Max_Itreation; iteration++) {
    /*
    中间过程省略
    */
    if constexpr (Memory_Flag) {
            convergence_curve[2*iteration] =Current_FES;//记录当前迭代之后的问题适应度计算次数
            convergence_curve[2*iteration+1] = Current_Best_Fit;//记录当前迭代之后的最佳适应度值
        }
 }


if constexpr(Memory_Flag)
        return std::make_tuple(best_pos, best_fit,convergence_curve);
if constexpr(!Memory_Flag)
    return std::make_pair(best_pos, best_fit);
}

对于每一次迭代,存储每一次迭代之后的当前适应度计算次数和当前最佳适应度值.

算法主模版类

为了使得不同的算法有统一的算法类去表示,SEvoBench使用模版偏特化技术

对不同的优化算法函数,用一个主模版类去表示.

在single_algorithm.hpp头文件中namespace sevobench下定义了single_algorithm作为主模版类

namespace sevobench {

template<std::uint64_t Alg_HashName,int Dim,int Pop_Size,int Max,bool Memory_Flag>
struct single_algorithm ;

}

同理,对不同的优化算法参数,也用一个主模版类去表示.在single_algorithm.hpp头文件中在namespace sevobench下定义了single_algorithm_parameter作为主模版类

namespace sevobench {


template<std::uint64_t Alg_HashName,std::floating_point T>
struct single_algorithm_parameter;

}

模版类的第一个参数std::uint64_t Alg_HashName代表着算法函数的Hash值,因此每个算法函数都有一个唯一的Alg_HashName值,而且不同算法函数之间Alg_HashName值不同,从而偏特化single_algorithm类,从而实现不同算法由主模版single_algorithm类去表达.这样设计的目的是方便将不同的算法在测试集上测试.
其余模版参数的意义与优化算法的模版函数参数意义相同.

在single_algorithm.hpp头文件中也定义了 REGISTER_ALGORITHM(func_name,func,parameter) 宏表达式

REGISTER_ALGORITHM(func_name,func,parameter) 让算法函数func成为偏特化的single_algorithm类,并生成 func_name变量,指代算法函数func的Hash值,偏特化之后的single_algorithm类具有一个静态成员字符串数组变量name(用于指代算法名字为func_name)和一个运算符重载函数 inline auto operator()(F &&f, T l, T r),偏特化之后的single_algorithm类可以看成一个函数对象.同理让parameter生成一个偏特化之后single_algorithm_parameter类,并且继承parameter类,详细细节请参考single_algorithm.hpp中关于宏表达式的实现代码.

下面给出示例,展示用户如何实现一个算法,并进行注册

首先包含必要的头文件

#include"single_algorithm.hpp"


/*
其余实现算法所需要的头文件
*/

用户实现算法函数Alogorithm

template<std::floating_point T>
struct Algorithm_Paramater {
    /*定义算法所需要的参数*/
};

template<int Dim,int Pop_Size,int Max,bool Memory_Flag,typename F,std::floating_point T,typename Parameter_Type=Algorithm_Paramater<T>>
inline auto Algorithm(F&& function,T l,T r,const Parameter_Type& pt=Parameter_Type()) noexcept  {

/*
 声明过程省略
 */

/*
  Max_Itreation取决于模版变量Max,Max是最大迭代次数还是适应度最大计算次数则取决于模版变量B
  */
 for (int iteration=0; iteration < Max_Itreation; iteration++) {
    /*
    中间过程省略
    */
    if constexpr (Memory_Flag) {
            convergence_curve[2*iteration] =Current_FES;//记录当前迭代之后的问题适应度计算次数
            convergence_curve[2*iteration+1] = Current_Best_Fit;//记录当前迭代之后的最佳适应度值
        }
 }


if constexpr(Memory_Flag)
        return std::make_tuple(best_pos, best_fit,convergence_curve);
if constexpr(!Memory_Flag)
    return std::make_pair(best_pos, best_fit);
}

最后对函数进行注册

REGISTER_ALGORITHM(Algorithm_Name,Algorithm,Algorithm_Paramater)

这样用户通过实现Algorithm函数,得到偏特化的一个single_algorithm类和single_algorithm_parameter类,其中偏特化后的single_algorithm_parameter类继承Algorithm_Paramater,同时得到一个变量Algorithm_Name去指代Algorithm函数的Hash值.

我们可以使用偏特化之后的类去优化Rastrigin问题

#define ALGORITHM(ALG,Dim,F,L,R) single_algorithm<ALG, Dim, 30,1000*Dim, false>()(F,L,R)

int main() {
    std::cout<<ALGORITHM(Algorithm_Name, 30,rastrigin<30>, -100.0f, 100.0f).second<<"\n";
}

测试问题集

想通过算法连续测试一系列问题时,需要构建关于问题集的类.

在SEvoBench中,一般声明一个问题集,使用如下形式去声明

template< int Prob_Index, int Dim,std::floating_point T >
struct  Problem;

Problem类的设计依然使用模版偏特化技术

模版参数 int Prob_Index:代表问题索引
模版参数 int Dim:代表问题维度
std::floating_point T:浮点数类型

使用第一个模版参数int Prob_Index去偏特化Problem类.

template<int Dim,std::floating_point T>
struct Problem<1,Dim,T> {
    static constexpr T L=-100; // 问题下界,使用变量L
    static constexpr T U=100; // 问题上界,使用变量U
   
   /*
   使用运算符重载函数T operator()(T *x)
   */

    T operator()(T *x) noexcept {
       return 10*Dim+std::accumulate(_x, _x+Dim, T(0), [](auto l,auto r){
        return l+r*r-10*std::cos(2*std::numbers::pi_v<T>*r);
    });
    }
};

我们偏特化一个Problem类,它的问题索引为1,问题类型为Rastrigin问题.

问题集主模版类

为了使得不同的问题集有统一的问题集类去表示,SEvoBench使用模版偏特化技术

对不同的问题测试集,用一个主模板类去表示.

在single_problem.hpp头文件中在namespace sevobench下声明了single_problem作为主模版类

namespace sevobench {

template <std::uint64_t Prob_HashName, int Prob_Index, int Dim,
          std::floating_point T>
struct single_problem;

}

对于不同的问题集,有不同的初始化方法,为此也声明一个主模版类用于初始化问题集.

namespace sevobench {

template <std::uint64_t Prob_HashName, int Dim, std::floating_point T>
struct init_single_problem;

}

和算法基类类似,类的第一个模版参数std::uint64_t Prob_HashName为问题集的Hash值,用于偏特化.
其余模版参数和测试问题集的模版参数意义一致

为此提供了两种宏表达式

REGISTER_PROBLEM(problem_name,problem,size)

INIT_PROBLEM(problem,F)

分别用于偏特化问题集和初始化方法.

下面给出示例,展示用户如何实现一个问题集,并进行偏特化

首先包含必要的头文件

#include"single_problem.hpp"


/*
其余实现算法所需要的头文件
*/

声明和定义问题,定义初始化方法

template< int Prob_Index, int Dim,std::floating_point T >
Struct  Problem;



template<int Dim,std::floating_point T>
struct Problem<1,Dim,T> {
    static constexpr T L=-100; // 问题下界,使用变量L
    static constexpr T U=100; // 问题上界,使用变量U
    T operator()(T *x) noexcept {
       return 10*Dim+std::accumulate(_x, _x+Dim, T(0), [](auto l,auto r){
        return l+r*r-10*std::cos(2*std::numbers::pi_v<T>*r);
    });
    }
};

template<std::floating_point T,int Dim>
void init_Problem() {
    /*
    用户定义
    */
}

偏特化问题和初始化方法

REGISTER_PROBLEM(Problem_Name,Problem,1) //最后一个参数代表问题集的问题个数
INIT_PROBLEM(Problem,init_Problem)

这样用户通过实现Problem问题集,并对其进行偏特化为一个single_problem类,得到一个变量Problem_Name去指代Problem问题集的Hash值.

不过一般来说,用户不需要去添加问题集,SEvoBench平台内置了一系列问题集.

算法测试函数

在parallel_algorithm_benchmark.hpp头文件中namespace sevobench下,我们定义了

namespace sevobench {

template<std::uint64_t Alg_HashName,std::uint64_t Prob_HashName,bool Memory_Flag,int Dim,int Pop_Size,int Max,int Runs,bool parallel,std::floating_point T,typename Parameter_Type=typename single_algorithm_parameter<Alg_HashName, T>::base_type>
inline auto evo_bench(const Parameter_Type & par=Parameter_Type()) noexcept;

}

对于用户来说只需要关注这几个模版参数

std::uint64_t Alg_HashName:算法的Hash变量值指定特定算法
std::uint64_t Prob_HashName:问题集的Hash变量值指定特定问题
bool Memory_Flag:是否记录收敛过程,默认值为false
int Dim:问题集的维度,默认值30
int Pop_Size:进化算法的种群数,默认值30
int Max:问题的适应度最大计算次数或者算法迭代次数,默认为1000*Dim
int Runs:测试重复次数,默认值是30
bool parallel:是否并行计算,默认是true
std::floating_point T:浮点数类型,默认是float
typename Parameter_Type: 指定封装算法参数的类,默认类型为 REGISTER_ALGORITHM(Algorithm_Name,Algorithm,Algorithm_Paramater) 中的 Algorithm_Paramater

测试函数返回类型为benchmark_result<std::floating_point T,typename Algorithm,typename Problem>,该数据结构存储了算法测试结果.

关于benchmark_result<std::floating_point T,typename Algorithm,typename Problem>

定义在parallel_algorithm_benchmark.hpp头文件中namespace sevobench::sevobench_detail
声明如下

namespace sevobench::sevobench_detail {

template<std::floating_point T,typename Algorithm,typename Problem>
class benchmark_result;

}

具有的成员函数

auto get_graph_data() :返回收敛数据graph_data,一维的数组形式存储,数据结构为std::vector<T>.

auto get_table_data() :返回统计数据table_data,一维的数组形式存储,数据结构为std::vector<T>.

constexpr auto problem_dim() :返回测试集问题的维度

constexpr auto problem_size() :返回测试集问题的数目

constexpr auto problem_name() :返回测试集的名字

constexpr auto algorithm_name() :返回测试算法的名字

constexpr auto algorithm_max() : 返回算法的最大迭代次数或者问题适应度值最大计算次数

constexpr auto algorithm_flag() : 返回算法的Memory_Flag标记

void write_table(const char *dir_name) :将统计数据写入dir_name文件夹下,文件以{Algorithm}_{Populations}_{Problem}_{Dim}_table.txt命名

该文件的数据组织形式为


...

Mean
Std
Best
Time
25% quantile
median
75% quantile
Worst
...

文件每一行一个数据,每8个数据作为一组,每一组索引对应着相应问题集的索引.这8个数据分别代表算法测试第I个问题运行N次之后的平均值,方差,最优值,平均时间,较小四分位数,中位数,较大四分位数,最差值.

void write_curve(const char *dir_name) :将收敛数据写入dir_name文件夹下,生成多个文件,每个文件以{Algorithm}_{Populations}_{Problem}_F{index}_{Dim}_curve.txt方式命名

该文件的数据组织形式为

...
FES
Best_Fit
···

文本每一行一个数据,依次为FES(问题适应度计算次数),Best_Fit(当前最优值),依次循环往复.其中{FES,Best_Fit}组成一个点,算法内部的每次迭代会生成一个点,这个点一共有Max(最大迭代次数)个

值得注意的是成员函数auto get_graph_data() 和 auto get_table_data() 返回的数据类型排布方式与文本数据排布方式相同