Zexian Li

智能算法浅析

2020-05-22 · 4 min read
algorithm

迫于期末考试,简要总结课程中介绍过的智能算法。

1.遗传算法

基本思想

遗传算法的基本思想:遗传、变异、适者生存。
遗传:子代总是和亲代有相同或相似的性状。
变异:随机发生,以产生亲代和子代之间、子代的不同个体之间的差异。
适者生存:具有适应性变异的个体被保留下来。

核心步骤

  1. 复制:舍弃旧种群中较差的个体,复制旧种群中生命力强的个体串到新种群以补全个体数。
  2. 交叉:在匹配池中任选两个染色体,随机选择一个或多个交换点,交换并得到新的染色体串。
  3. 变异:以小概率随机改变染色体中的某一位。

算法特性

one-hot编码;多点搜索,隐含并行性;启发式搜索;搜索效率高。

实现考量

个体表现型和问题解空间,染色体编码解码方法,个体适应度评价,遗传算子选择(复制、交叉、变异)
参数:群体大小、终止进化代数、复制替代个体数、交叉概率、变异概率

2.粒子群算法

基本思想

追随当前搜索到的最优值来寻找全局最优解。

核心步骤

类比鸟群,每个解都是搜索空间的一个具有位置和速度的鸟(粒子),每个粒子通过跟踪个体极值(粒子经过的最优解)和全局极值(群体经过的最优解)更新自身的位置。
更新粒子速度的核心公式如下所示:

Vikg+1=w(t)Vikg+c1r1(PikgXikg)+c2r2(BestSikgXikg)V_i^{kg+1} = w(t) * V_i^{kg} + c_1r_1(P_i^{kg} - X_i^{kg}) + c_2r_2(BestS_i^{kg} - X_i^{kg})

算法特性

实数编码;容易实现;精度高,收敛快。

实现考量

问题解空间、个体适应度评价
参数:粒子数、终止条件(最大进化代数/最小误差要求)、最大速度、学习因子(局部学习因子&全局学习因子)、惯性权重、自适应变异参数

3.标准差分进化算法

基本思想

在传统遗传算法上提出基于差分的简单变异、一对一的竞争生存策略。

核心步骤

  1. 变异:将两个个体的向量差加权、缩放并与第三个个体求和,以生成中间体。
  2. 交叉:交叉原始个体x(g)和对应中间体v(g+1),得到新一代候选个体x(g+1)'。
  3. 选择:在x(g)和x(g+1)'中选择更优者作为新个体x(g+1)。

算法特性

实数编码;待定参数少,简单易用;鲁棒性好,不易陷入局部最优,适用多种问题;全局搜索能力强,收敛速度快。

实现考量

问题解空间、个体适应度评价
参数:群体大小、终止进化代数、缩放因子、交叉因子

4.Hopfield神经网络

基本思想

Hopfield网络是对称的二元无向全互联网络,即每个神经元只有两个取值,每个神经元与其他所有神经元连接且该连接具有无向性。
Hopfield网络优化的核心就是使整个网络的能量最小。权值一经计算不再改变,各神经元状态不断更新,当网络演变到稳定时各神经元的状态便是问题的解。

求解TSP问题

详见博客

5.系统辨识

系统辨识是确定系统数学模型及参数的问题,参数辨识是在确定模型结构基础上选用辨识算法估计模型中的未知参数。将辨识误差作为目标函数,可以使上述智能算法在系统辨识中广泛应用。

🤠奶一口考试顺利!

Bad decisions make good stories.