ABAP算法模拟退火

模拟退火算法

算法原理及概念本文仅结合实现过程做简述

模拟退火算法是一种解决优化问题的算法。通过模拟固体退火过程中的原子热运动来寻找全局最优解。在求解复杂问题时，模拟退火算法可以跳出局部最优解获取全局最优解。

模拟退火算法包含退火过程和Metropolis算法两个部分，体现在外循环和内循环中，外循环就是退火过程，将固体从较高的温度按照降温系数k使温度按照一定的比例下降，当达到终止温度tn时，退火过程结束。内循环为在固定温度下，不断迭代寻求当前温度下能量的最低值，Metropolis 算法可以使得结果跳出局部最优值。

模拟退火基本参数：

T：初始温度，较大值

K：降温系数

TN：终止温度

L：内循环迭代次数

概述图

算法求解过程中主要的两个重要数据，扰动量的多少以及新解接受概率，由于这两个参数依托于实际计算场景，因此使用两个参数控制

FLOAT：用来控制扰动量的范围，最大为1

R：新解保留概率，R值越大，新解保留概率越大，主要目的是平衡能量差过大或过小导致的概率失衡

处理方法及属性

代码地址：https://download.csdn.net/download/xiefireworks/88576481

示例

Demo代码



CLASS lcl_obj DEFINITION FINAL  .

  PUBLIC SECTION.

    INTERFACES zif_annealing_c .
  PROTECTED SECTION.
  PRIVATE SECTION.
ENDCLASS.

CLASS lcl_obj IMPLEMENTATION.

  METHOD zif_annealing_c~check_valid.

    DATA: lv_sum TYPE i.

  ENDMETHOD.

  METHOD zif_annealing_c~calcu_target_value.

    DATA: lv_sum TYPE i.
    DATA: lv_x1 TYPE ftvv_part_default_probability.
    DATA: lv_x2 TYPE ftvv_part_default_probability.

    LOOP AT units INTO DATA(ls_unit).
      CASE ls_unit-name.
        WHEN 'X1'.
          lv_x1 = ls_unit-value / 10000 - 5.
          lv_sum = lv_sum + 20 * ls_unit-value.
        WHEN 'X2'.
          lv_x2 = ls_unit-value / 10000 - 5.
          lv_sum = lv_sum + 30 * ls_unit-value.
        WHEN 'X3'.
          lv_sum = lv_sum + 50 * ls_unit-value.
        WHEN OTHERS.
      ENDCASE.
    ENDLOOP.

*    target_value = 4000 - lv_sum.
    target_value = 4 * lv_x1 * lv_x1 - 21 / 10 * ipow( base = lv_x1 exp = 4 ) + ipow( base = lv_x1 exp = 6 ) / 3
                   + lv_x1 * lv_x2 - 4 * ipow( base = lv_x2 exp = 2 ) + 4 * ipow( base = lv_x2 exp = 4 ).

  ENDMETHOD.

ENDCLASS.

DATA: lo_g    TYPE REF TO zcl_annealing,
      lo_gc   TYPE REF TO lcl_obj,
      lt_recs TYPE zcl_annealing=>tt_allgroups.

START-OF-SELECTION.

  CREATE OBJECT lo_g TYPE zcl_annealing.
  CREATE OBJECT lo_gc.

  lo_g->init( EXPORTING iv_k          = '0.998'
                        iv_l          = '1000'
                        iv_t          = '1000'
                        iv_tn         = '10'
                        iv_random_up  = '100'
                        iv_r          = '0.00005'
                        iv_float      = '0.2'
                        io_annealing  = lo_gc
   ).

  lo_g->add_var( name = 'X1' low = 0 high = 100000 ).
  lo_g->add_var( name = 'X2' low = 0 high = 100000 ).

  DATA(lt_unit) = lo_g->get_result( ).
  lo_g->get_record( IMPORTING et_rec = lt_recs ).

  WRITE:/ '最优解'.
  LOOP AT lt_unit INTO DATA(ls_unit).
    DATA value TYPE ftvv_part_default_probability.
    value = ls_unit-value / 10000 - '5.0000'.
    WRITE:/ ls_unit-name, ':' ,value.
  ENDLOOP.

  WRITE:/ '迭代过程'.
  SORT lt_recs BY target DESCENDING t.
  LOOP AT lt_recs INTO DATA(ls_rec).
    WRITE:/ '温度:',ls_rec-t,'  目标值:' ,ls_rec-target, '  值：'.
    LOOP AT ls_rec-units INTO ls_unit.
      WRITE:ls_unit-name, '-' ,ls_unit-value , ';'.
    ENDLOOP.
  ENDLOOP.