现代优化算法

模拟退火算法

假设材料在状态i之下的能量为\(E(i)\),那么材料在温度\(T\)时从状态\(i\)进入状态\(j\)就遵循如下规律:

1. 如果\(E(j)\leq E(i)\),则接受该状态被转换

2. 如果\(E(j)>E(i)\),则状态一如下概率被接受: \[ e^{\dfrac{E(i)-E(j)}{KT}} \]

材料达到热平衡时,材料处于状态\(i\)的概率满足玻尔兹曼分布 \[ P_T(X=i)=\dfrac{e^{-\dfrac{E(i)}{KT}}}{\sum_{j\in S}e^{-\dfrac{E(j)}{KT}}} \] X为材料当前状态的随机变量,S为状态空间集合

显然: \[ \lim_{T\rightarrow \infty}\dfrac{e^{_\dfrac{E(i)}{KT}}}{\sum_{j\in S}e^{-\dfrac{E(j)}{KT}}}=\dfrac{1}{|S|} \] |S|为集合S中状态的数量

这表明所有状态在高温下具有相同的概率.而当温度下降时,有 \[ \lim_{T\rightarrow 0}\dfrac{e^{\dfrac{K(i)-E_{\min}}{KT}}}{\sum_{j\in S}e^{-\dfrac{E(j)-E_{\min}}{KT}}}=\begin{cases} \dfrac{1}{|S_{\min}|},i\in S_{\min}\\ 0,else \end{cases} \] \(E_{\min}=\min_{j\in S}E(j)且S_{\min}=\{i|E(i)=E_\min\}\)

假定要解决的问题是寻找最小值的优化问题.

考虑一个组合优化问题,优化函数\(f:x\rightarrow R^+\),其中\(x\in S\),表示优化问题的一个可行解,\(R^+=\{y|y\in R,y\geq 0\}\),S表示函数的定义域,\(N(x)\subseteq S\)表示x的一个邻域集合

给定一个初始温度\(T_0\)和该优化问题的一个初始解\(x(0)\),并由\(x(0)\)生成下一个解\(x'\in N[x(0)]\),是否接受\(x'\)作为一个新界\(x(1)\)依赖于如下概率: \[ P(x(0)\rightarrow x')=\begin{cases} 1,&f(x')<f(x(0))\\ e^{-\dfrac{f(x')-f(x(0))}{T_0}}&else\\ \end{cases} \] 在温度\(T_i\)下,经过很多次的转移之后,降低温度\(T_i\),得到\(T_{i+1}<T_i\),在\(T_{i+1}\)下重复上述过程,因此整个优化过程就是不断寻找新解和缓慢降温的交替过程.

在温度\(T_i\)下的平衡态\(x_i\)的分布由下式给出: \[ P_i(T_i)=\dfrac{e^{-\dfrac{f(x_i)}{T_i}}}{\mathop\sum\limits_{j\in S}e^{-\dfrac{f(x_j)}{T_i}}} \] 伪代码如下:

double T = 2000;
double dT = 0.99;
double eps = 1e-14;
while (T < eps) {
    // 退火操作
    T = T * dT;
}

遗传算法

1. 根据具体问题确定可行解域,确定一种编码方式,能用数值串或者字符串表示可行解域的每一解
2. 对每一解应用一个度量好坏的依据,它用一函数表示,叫做适应度函数,一般由目标函数构成
3. 确定进化参数群体规模M,交叉概\(p_e\),变异概率\(p_m\),进化终止条件

求解的遗传算法的参数设定如下:

种群大小M=50,最大代数G=1000;

交叉率\(p_e\)=1,交叉概率为1保证种群的充分进化

变异率\(p_m\)=0.1,一般而言,变异发生的可能性较小.

1. 编码策略

   采用十进制编码,用随机数列\(\omega_1,\omega_2,\cdots,\omega_{102}\)作为染色体,其中\(0\leq \omega_i\leq 1(i=2,3,\cdots ,101),\omega_1=0,\omega_{102}=1\),每一个随机序列都和种群中的一个个体相对应.

2. 初始种群

   改良圈算法

3. 目标函数 \[ \min f(\pi_1,\pi_2,\cdots,\pi_{102})=\sum^{102}_{i=1}d_{\pi_i\pi_{i+1}} \]

4. 交叉操作

   采用单点交叉,对于选定的两个父代个体\(f_1=\omega_1\omega_2\cdots\omega_{102},f_2=\omega_1'\omega_2'\cdots \omega_{102}'\),随机选取第\(t\)个基因处作为交叉点,则经过交叉运算后得到的子代个体为\(s_1\)和\(s_2\),\(s_1.\)基因由\(f_1\)的前\(t\)个基因和\(f_2\)的后\(102-t\)个基因构成,\(s_2\)的基因由\(f_2\)的前\(t\)个基因和\(f_1\)的后\(102-t\)个基因构成

5. 变异操作

   随机地选取三个整数\(u,v,w\),满足\(1<u<v<w<102\),把\(u,v\)之间地基因段插到\(w\)后面

6. 选择

   采用确定性的选择策略,即在父代种群和自带种群中选择目标函数值最小的M个个体进化到下一代,这样可以保证父代的优良特性被保存下来

MATLAB ga参数

MATLAB ga输出