线性优化算法和信赖域优化方法：

系统优化方法与智能优化算法
系统优化方法在各种工程系统、经济系统，乃至社会系统中得到了广泛的应用。最优化理论的研究也一直是一个十分活跃的领域，出版了许多最优化理论、方法和应用的著作和译作。
梯度为基础的传统优化算法具有较高的计算效率、较强的可靠性、比较成熟等优点，是一类最重要的、应用最广泛的优化算法。但是，传统的最优化方法在应用于复杂、困难的优化问题时有较大的局限性。一个优化问题称为是复杂的，通常是指具有下列特征之一：（1）目标函数没有明确解析表达；（2）目标函数虽有明确表达，但不可能恰好估值；（3）目标函数为多峰函数；（4）目标函数有多个，即多目标优化。一个优化问题称为是困难的，通常是指：目标函数或约束条件不连续、不可微、高度非线性，或者问题本身是困难的组合问题。传统优化方法往往要求目标函数是凸的、连续可微的，可行域是凸集等条件，而且处理非确定性信息的能力较差。这些弱点使传统优化方法在解决许多实际问题时受到了限制。
目前由于所研究实际系统的规模越来越大，约束条件增多，系统结构越来越复杂，多准则、非线性、不可微、不确定已成为这些复杂系统的基本特征，致使系统的数学建模难度越来越大，因此，探寻适合大规模计算且具有智能特征的问题求解（或信息处理）方法成为相关学科的研究热点和重要研究方向。计算智能（或软计算）就是在这种情况下出现的一个学科领域，它是由多个学科相互交叉和渗透的结果，得益于运筹学与管理科学、计算数学、人工智能、模式识别、自动控制理论等许多学科，其典型分支主要包括进化计算、神经计算与模糊逻辑等。
作为计算智能的重要研究内容，智能优化算法主要包括进化算法、模拟退火算法、人工神经网络方法、免疫算法、禁忌搜索算法、差分演化算法、蚁群算法、微粒群算法等。这类新的优化算法一般都是建立在生物智能或物理现象基础上的随机搜索算法，目前在理论上还远不如传统优化算法完善，往往也不能确保解的最优性，因而常常被视为只是一些“元启发式方法”（meta-heuristic）。但从实际应用的观点看，这类新算法一般不要求目标函数和约束的连续性与凸性，甚至有时连有没有解析表达式都不要求，对计算中数据的不确定性也有很强的适应能力。由于这些独特的优点和机制，智能优化算法引起了国内外学者的广泛重视并掀起了该领域的研究热潮，且在诸多领域中得到了广泛应用，展示出强劲的发展势头。
参考文献：
1.王凌. 智能优化算法及其应用，清华大学出版社，2001.
2.郭崇慧，唐焕文．演化策略的全局收敛性．计算数学，2001，23（1），105-110
3.唐焕文，秦学志.实用最优化方法（第三版）．大连理工大学出版社，2004．
4.徐宗本. 计算智能（第一册）：模拟进化计算，高等教育出版社，2005.
5.邢文训，谢金星. 现代优化计算方法（第二版），清华大学出版社，2005.
6.汪定伟，王俊伟，王洪峤，张瑞友，郭哲. 智能优化方法，高等教育出版社，2007.
转自:http://www.sciencenet.cn/m/user_content.aspx?id=212836

【优化算法】简述遗传算法（GA）原理
	
【优化算法】简述灰狼优化算法（GWO）原理


前言：

灰狼优化算法（Grey Wolf Optimizer，GWO）由澳大利亚格里菲斯大学学者 Mirjalili 等人于2014年提出来的一种群智能优化算法。该算法受到了灰狼捕食猎物活动的启发而开发的一种优化搜索方法，它具有较强的收敛性能、参数少、易实现等特点。近年来受到了学者的广泛关注，它己被成功地应用到了车间调度、参数优化、图像分类等领域中。

算法原理：

灰狼隶属于群居生活的犬科动物，且处于食物链的顶层。灰狼严格遵守着一个社会支配等级关系。如图：



社会等级第一层：狼群中的头狼记为 ， 狼主要负责对捕食、栖息、作息时间等活动作出决策。由于其它的狼需要服从 狼的命令，所以  狼也被称为支配狼。另外，  狼不一定是狼群中最强的狼，但就管理能力方面来说，  狼一定是最好的。

社会等级第二层： 狼，它服从于  狼，并协助  狼作出决策。在  狼去世或衰老后， 狼将成为  狼的最候选者。虽然  狼服从  狼，但  狼可支配其它社会层级上的狼。

社会等级第三层： 狼，它服从  、 狼，同时支配剩余层级的狼。 狼一般由幼狼、哨兵狼、狩猎狼、老年狼及护理狼组成。

社会等级第四层： 狼，它通常需要服从其它社会层次上的狼。虽然看上去  狼在狼群中的作用不大，但是如果没有  狼的存在，狼群会出现内部问题如自相残杀。

GWO 优化过程包含了灰狼的社会等级分层、跟踪、包围和攻击猎物等步骤，其步骤具体情况如下所示。

１）社会等级分层（Social Hierarchy）当设计 GWO 时，首先需构建灰狼社会等级层次模型。计算种群每个个体的适应度，将狼群中适应度最好的三匹灰狼依次标记为 、 、 ，而剩下的灰狼标记为 。也就是说，灰狼群体中的社会等级从高往低排列依次为； 、 、  及 。GWO 的优化过程主要由每代种群中的最好三个解（即  、 、 ）来指导完成。

２）包围猎物（ Encircling Prey ）灰狼捜索猎物时会逐渐地接近猎物并包围它，该行为的数学模型如下：



式中：t 为当前迭代次数：。表示 hadamard 乘积操作；A 和 C 是协同系数向量；Xp 表示猎物的位置向量； X(t) 表示当前灰狼的位置向量；在整个迭代过程中 a 由2 线性降到 0； r1 和 r2 是 [0，1] 中的随机向量。

３）狩猎（ Hunring）

灰狼具有识别潜在猎物（最优解）位置的能力，搜索过程主要靠 、 、 灰狼的指引来完成。但是很多问题的解空间特征是未知的，灰狼是无法确定猎物（最优解）的精确位置。为了模拟灰狼（候选解）的搜索行为，假设 、 、 具有较强识别潜在猎物位置的能力。因此，在每次迭代过程中，保留当前种群中的最好三只灰狼（ 、 、 ），然后根据它们的位置信息来更新其它搜索代理（包括 ）的位置。该行为的数学模型可表示如下：



式中：、、 分别表示当前种群中 、 、 的位置向量；Ｘ表示灰狼的位置向量；、、  分别表示当前候选灰狼与最优三条狼之间的距离；当｜A｜＞１时，灰狼之间尽量分散在各区域并搜寻猎物。当｜A｜＜１时，灰狼将集中捜索某个或某些区域的猎物。



从图中可看出，候选解的位置最终落在被 、 、 定义的随机圆位置内。总的来说， 、 、 需首先预测出猎物（潜

在最优解）的大致位置，然后其它候选狼在当前最优兰只狼的指引下在猎物附近随机地更新它们的位置。

４）攻击猎物（Attacking Prey）构建攻击猎物模型的过程中，根据2)中的公式，ａ值的减少会引起 A 的值也随之波动。换句话说，A 是一个在区间［-a，a］（备注：原作者的第一篇论文里这里是[-2a,2a]，后面论文里纠正为[-a,a]）上的随机向量，其中ａ在迭代过程中呈线性下降。当 A 在［-1，１］区间上时，则捜索代理（Search Agent）的下一时刻位置可以在当前灰狼与猎物之间的任何位置上。

５）寻找猎物（Search for Prey）灰狼主要依赖 、 、 的信息来寻找猎物。它们开始分散地去搜索猎物位置信息，然后集中起来攻击猎物。对于分散模型的建立，通过｜A｜＞１使其捜索代理远离猎物，这种搜索方式使 GWO 能进行全局搜索。GWO 算法中的另一个搜索系数是Ｃ。从2)中的公式可知，Ｃ向量是在区间范围［０，２］上的随机值构成的向量，此系数为猎物提供了随机权重，以便増加（｜Ｃ｜＞１）或减少（｜Ｃ｜＜１）。这有助于 GWO 在优化过程中展示出随机搜索行为，以避免算法陷入局部最优。值得注意的是，Ｃ并不是线性下降的，Ｃ在迭代过程中是随机值，该系数有利于算法跳出局部，特别是算法在迭代的后期显得尤为重要。

参考文献：

加工时间可控的多目标车间调度问题研究

Grey Wolf Optimizer

 

 

一、粒子群算法的概念

  粒子群优化算法(PSO：Particle swarm optimization) 是一种进化计算技术（evolutionary computation）。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想：是通过群体中个体之间的协作和信息共享来寻找最优解． 

  PSO的优势：在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。  



二、粒子群算法分析

1、基本思想

  粒子群算法通过设计一种无质量的粒子来模拟鸟群中的鸟，粒子仅具有两个属性：速度和位置，速度代表移动的快慢，位置代表移动的方向。每个粒子在搜索空间中单独的搜寻最优解，并将其记为当前个体极值，并将个体极值与整个粒子群里的其他粒子共享，找到最优的那个个体极值作为整个粒子群的当前全局最优解，粒子群中的所有粒子根据自己找到的当前个体极值和整个粒子群共享的当前全局最优解来调整自己的速度和位置。下面的动图很形象地展示了PSO算法的过程： 



2、更新规则

  PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest，gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。 

 

公式(1)的第一部分称为【记忆项】，表示上次速度大小和方向的影响；公式(1)的第二部分称为【自身认知项】，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；公式(1)的第三部分称为【群体认知项】，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。以上面两个公式为基础，形成了PSO的标准形式。 

 

公式(2)和 公式(3)被视为标准PSO算法。

3、PSO算法的流程和伪代码



4、PSO算法举例

 



5、PSO算法的demo



#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <random>
#include <ctime>
#include <Eigen/Dense>
using namespace Eigen;
using namespace std;

const int dim = 1;//维数
const int p_num = 10;//粒子数量
const int iters = 100;//迭代次数
const int inf = 999999;//极大值
const double pi = 3.1415;
//定义粒子的位置和速度的范围
const double v_max = 4;
const double v_min = -2;
const double pos_max = 2;
const double pos_min = -1;
//定义位置向量和速度向量
vector<double> pos;
vector<double> spd;
//定义粒子的历史最优位置和全局最优位置
vector<double> p_best;
double g_best;
//使用eigen库定义函数值矩阵和位置矩阵
Matrix<double, iters, p_num> f_test;
Matrix<double, iters, p_num> pos_mat;

//定义适应度函数
double fun_test(double x)
{
    double res = x * x + 1;
    return res;
}

//初始化粒子群的位置和速度
void init()
{
    //矩阵中所有元素初始化为极大值
    f_test.fill(inf);
    pos_mat.fill(inf);
    //生成范围随机数
    static std::mt19937 rng;
    static std::uniform_real_distribution<double> distribution1(-1, 2);
    static std::uniform_real_distribution<double> distribution2(-2, 4);
    for (int i = 0; i < p_num; ++i)
    {
        pos.push_back(distribution1(rng));
        spd.push_back(distribution2(rng));
    }
    vector<double> vec;
    for (int i = 0; i < p_num; ++i)
    {
        auto temp = fun_test(pos[i]);//计算函数值
        //初始化函数值矩阵和位置矩阵
        f_test(0, i) = temp;
        pos_mat(0, i) = pos[i];
        p_best.push_back(pos[i]);//初始化粒子的历史最优位置
    }
    std::ptrdiff_t minRow, minCol;
    f_test.row(0).minCoeff(&minRow, &minCol);//返回函数值矩阵第一行中极小值对应的位置
    g_best = pos_mat(minRow, minCol);//初始化全局最优位置
}

void PSO()
{
    static std::mt19937 rng;
    static std::uniform_real_distribution<double> distribution(0, 1);
    for (int step = 1; step < iters; ++step)
    {
        for (int i = 0; i < p_num; ++i)
        {
            //更新速度向量和位置向量
            spd[i] = 0.5 * spd[i] + 2 * distribution(rng) * (p_best[i] - pos[i]) +
                2 * distribution(rng) * (g_best - pos[i]);
            pos[i] = pos[i] + spd[i];
            //如果越界则取边界值
            if (spd[i] < -2 || spd[i] > 4)
                spd[i] = 4;
            if (pos[i] < -1 || pos[i] > 2)
                pos[i] = -1;
            //更新位置矩阵
            pos_mat(step, i) = pos[i];
        }
        //更新函数值矩阵
        for (int i = 0; i < p_num; ++i)
        {
            auto temp = fun_test(pos[i]);
            f_test(step, i) = temp;
        }
        for (int i = 0; i < p_num; ++i)
        {
            MatrixXd temp_test;
            temp_test = f_test.col(i);//取函数值矩阵的每一列
            std::ptrdiff_t minRow, minCol;
            temp_test.minCoeff(&minRow, &minCol);//获取每一列的极小值对应的位置
            p_best[i] = pos_mat(minRow, i);//获取每一列的极小值，即每个粒子的历史最优位置
        }
        g_best = *min_element(p_best.begin(), p_best.end());//获取全局最优位置
    }
    cout << fun_test(g_best);
}

int main()
{
    init();
    PSO();
    system("pause");
    return 0;
}

参考：https://blog.csdn.net/myarrow/article/details/51507671 

https://blog.csdn.net/google19890102/article/details/30044945 

https://wenku.baidu.com/view/65c600b9294ac850ad02de80d4d8d15abe230048.html 

https://blog.csdn.net/darin1997/article/details/80675933