OptaPlanner内部优化算法

本文内容仅围绕邻域解的接收算法针对move selector的内部算法机制将在另一篇文章中进行阐述

2.启发式算法（Heuristic Algorithm） “探索法”
特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。但由于这种方法具有尝试错误的特点，所以也有失败的可能性。科学家的许多重大发现，常常是利用极为简单的启发式规则。

**群体智能算法(蚂蚁优化，鱼群算法)**就是启发式算法；
通俗的解释就是利用类似仿生学的原理，将自然、动物中的一些现象抽象成为算法处理相应问题。当一个问题是NP难问题时，是无法求解到最优解的，因此，用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的

算法机制
现代启发式算法在优化机制方面存在一定的差异,但在优化流程上却具有较大的相似性,均是一种“邻域搜索”结构。算法都是从一个(一组)初始解出发,在算法的关键参数的控制下通过邻域函数产生若干邻域解,按接受准则(确定性、概率性或混沌方式)更新当前状态,而后按关键参数修改准则调整关键参数。如此重复上述搜索步骤直到满足算法的收敛准则,最终得到问题的优化结果。

番外知识点：Meta-Heuristic和construction Heuristic
启发式算法(Heuristic Algorigthm)是一种基于直观或经验构造的算法,在可接受的花费(指计算时间、计算空间等)给出待解决优化问题的每一实例的一个可行解，该可行解与与最优解的偏离程度一般不可以事先预计。
启发式算法是一种技术,这种算法可以在可接受的计算费用内找到最好的解,但不一定能保证所得到解的可行性及最优性，甚至大多数情况下无法阐述所得解与最优解之间的近似程度。
元启发式算法（MetaHeuristic Algorigthm）是启发式算法的改进，它是随机算法与局部搜索算法相结合的产物。
启发式算法包括遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法及神经网络算法等。
OptaPlanner内部优化算法
优化算法性能对比

3.LocalSearch （Meta-Heuristic 启发算法的一种）
爬山算法禁忌算法模拟退火算法
3-0 思想
大致思想是:https://blog.****.net/ficuep/article/details/5821973
(1). 给定一个数量的初始值状态,也就当前状态
(2). 根据当前状态以一定的规则生成一定数量的相邻状态
(3). 根据一定规则用相邻状态来代替当前状态 (比如相邻状态值优于当前状态)
(4). 重复(2),(3)直到找到一个满意的解或者查找时间用完!

OptaPlanner内部优化算法

3-1 naive Local Search（最基本模型）
A naive Local Search configuration solves the four queens problem in three steps, by evaluating only 37 possible solutions (three steps with 12 moves each + one starting solution), which is only fraction of all 256 possible solutions. It solves 16 queens in 31 steps, by evaluating only 7441 out of 18446744073709551616 possible solutions. By using a Construction Heuristics phase（增加启发阶段） first, it’s even a lot more efficient（更加高效）.
OptaPlanner内部优化算法
3-2 爬山算法（Hill Climbing —>>>Simple Local Search)
Notice that once a queen has moved, it can be moved again later. This is a good thing, because in an NP-complete problem it’s impossible to predict what will be the optimal final value for a planning variable.
OptaPlanner内部优化算法
ATTENTION：Hill Climbing can easily get stuck in a local optimum.

爬山算法缺陷：容易陷入局部最优stuck in local optima
解决方案：不使用爬山算法使用优化版禁忌算法 tabusearch
Improvements upon Hill Climbing (such as Tabu Search, Simulated Annealing and Late Acceptance) address the problem of being stuck in local optima. Therefore, it’s recommend to never use Hill Climbing, unless you’re absolutely sure there are no local optima in your planning problem

3-3禁忌算法（Tabu Search)
核心:爬山算法基础之上添加禁忌表
Tabu Search works like Hill Climbing, but it maintains a tabu list to avoid getting stuck in local optima. The tabu list holds recently used objects that are taboo to use for now. Moves that involve an object in the tabu list, are not accepted. The tabu list objects can be anything related to the move, such as the planning entity, planning value, move, solution, … Here’s an example with entity tabu for four queens, so the queens are put in the tabu list:
OptaPlanner内部优化算法
Attention：If the tabu size is too small, the solver can still get stuck in a local optimum. On the other hand, if the tabu size is too large, the solver can be inefficient by bouncing of the walls. Use the Benchmarker to fine tweak your configuration.

3-4 模拟退火算法（Simulated Annealing)
Simulated Annealing evaluates only a few moves per step, so it steps quickly. In the classic implementation, the first accepted move is the winning step. A move is accepted if it doesn’t decrease the score or - in case it does decrease the score - it passes a random check（0.41 0.50 0.88 。。。）. The chance that a decreasing move passes the random check decreases relative to the size of the score decrement and the time the phase has been running (which is represented as the temperature).
OptaPlanner内部优化算法
Simulated Annealing does not always pick the move with the highest score, neither does it evaluate many moves per step. At least at first. Instead, it gives non improving moves also a chance to be picked, depending on its score and the time gradient of the Termination. In the end, it gradually turns into Hill Climbing, only accepting improving moves.

#################以下算法做法禁忌搜段moveselector的辅助算法#################

3-5 延迟接受爬山算法 Late Acceptance（Late Acceptance Hill Climbing)
Late Acceptance (also known as Late Acceptance Hill Climbing) also evaluates only a few moves per step. A move is accepted if it does not decrease the score, or if it leads to a score that is at least the late score (which is the winning score of a fixed number of steps ago).

OptaPlanner内部优化算法
Attention: LA+TS 组合
(1)Late Acceptance should use a low acceptedCountLimit.
(2)Late Acceptance can be combined with a tabu acceptor at the same time. That gives Late Acceptance salted with a bit of Tabu. Use a lower tabu size than in a pure Tabu Search configuration.

3-6 Step Counting Hill Climbing
核心阈值得分机制类似于LA
Step Counting Hill Climbing also evaluates only a few moves per step. For a number of steps, it keeps the step score as a threshold. A move is accepted if it does not decrease the score, or if it leads to a score that is at least the threshold score.

3-7 Strategic Oscillation 策略波动
Strategic Oscillation is an add-on, which works especially well with Tabu Search. Instead of picking the accepted move with the highest score, it employs a different mechanism: If there’s an improving move, it picks it. If there’s no improving move however, it prefers moves which improve a softer score level, over moves which break a harder score level less.

3-8 VND算法 Variable Neighborhood Descent
Variable Neighborhood Descent iteratively tries multiple move selectors in original order (depleting each selector entirely before trying the next one), picking the first improving move (which also resets the iterator back to the first move selector).
Attention：Variable Neighborhood Descent doesn’t scale well, but it is useful in some use cases with a very erratic score landscape.

1.贪心算法和动态规划
贪心算法：是一种在解决问题的过程中追求局部最优的算法，对于一个有多种属性的事物来说，贪心算法会优先满足某种条件，追求局部最优的同时希望达到整体最优的效果。以背包问题为例，可以放在背包中的物体有它的重量和价值两种属性，背包的容量也是有限的，我们希望得到一种价值最大的物品摆放方式，如果我们倾向于重量贪心，那么在摆放物品的时候会优先放重量小的，但这和我们追求的价值最优没有关系，自然不能采用；如果倾向于价值贪心，而忽略了物品的重量，可能会导致摆放物品的数量不多，总价值很小；如果是以价值和重量的比值设计贪心算法求解，便可以实现最优的方案。下面我们举一些例子来说明在实际运用中如何实践贪心算法。贪心算法追求局部最优，拿到问题之后先分析我们需要达到什么目标，是否适合采用贪心算法，并且使得什么最优以及实现的方法。
例子：：VRP最优路线起点开始依次寻找下一个最近点—>>>做种组成最优路线
https://blog.****.net/mayifan_blog/article/details/85063336

package com.algrthim;

import java.util.Arrays;

/**
 * 贪心算法 自顶向下
 * @author JFeng
 * @date 2019/4/9 10:04
 */
public class Greedy {
    public static void main(String[] args) {
        Greedy greedy = new Greedy();
        greedy.greedy1();
    }
    /**
     * 贪心算法1：钱币找零问题
     */
    public void greedy1(){
        //面额
        int[] values = { 1, 2, 5, 10, 20, 50, 100 };
        //数量
        int[] counts = { 3, 3, 2, 1, 1, 3, 3 };
        //获取需要各种面值多少张
        int[] result = getNumber1(100, values, counts);
        System.out.println("各币值的数量："+ Arrays.toString(result));
    }

    /**
     * 贪心算法1：钱币找零问题
     * @param sum
     * @param values
     * @param counts
     * @return
     */
    public int[] getNumber1(int sum , int[] values, int[] counts)
    {
        int[] result = new int[7];
        int add=0; //当前凑的金额
        //从最大面值100开始寻找
        for(int i=values.length-1;i>=0;i--)
        {
            int num = (sum-add)/values[i];
            //按照count最大进行处理
            if(num>counts[i])
            {
                num=counts[i];
            }
            add=add+num*values[i];
            result[i]=num;
        }
        return result;
    }

}

各币值的数量：[0, 0, 0, 0, 0, 0, 1]

动态规划：

OptaPlanner内部优化算法

相关推荐