The best input is OUTPUT.

2017-09-23
遗传算法中适值函数的标定与大变异算法

遗传算法中适值函数的标定与大变异算法

前言

本文尝试对遗传算法中不同适值函数的标定(Scaling)方法进行下总结,并针对常用的线性标定和动态线性标定进行了Python实现,以装饰器的形式添加到遗传算法框架GAFT中,这样在使用GAFT运行遗传算法迭代的时候可以更加Pythonic的给自定义的适值函数进行标定。最后针对能够防止早熟情况的大变异算法进行了相应的实现。

目前(动态)线性标定装饰器以及大变异算子均已添加到GAFT中,gaft项目链接:

Read More

2017-09-19
遗传算法中几种不同选择算子

遗传算法中几种不同选择算子

前言

本文对遗传算法中的几种选择策略进行了总结, 其中包括:

  1. Proportionate Roulette Wheel Selection
  2. Linear Ranking Selection
  3. Exponential Ranking Selection
  4. Tournament Selection

对于每种选择策略我都使用Python进行了相应的实现并以内置插件的形式整合进了本人所写的遗传算法框架GAFT中。对需要使用遗传算法优化问题以及学习遗传算法的童鞋可以作为参考.

项目链接:

Read More

2017-09-10
递归式求解-主方法

递归式求解-主方法

本文对递归式求解中很重要的主方法进行介绍总结。

主方法

主方法为如下形式的递归式提供了一种”菜谱式”的求解方法:
$$T(n) = aT(n/b) + f(n)$$
其中$a \ge 1, b \gt 1$是常数,$f(n)$是渐进正数。

上式描述了这样的一个算法运行时间: 他将原问题的规模为$n$的问题划分为$a$个小的子问题,每个子问题的规模为原来的$\frac{1}{b}$. $a$个子问题递归的进行求解,每个花费时间为$T(n/b)$。子问题合并的代价为$f(n)$

Read More

2017-09-01
机器学习算法实践-SVM中的SMO算法

机器学习算法实践-SVM中的SMO算法

前言

前两篇关于SVM的文章分别总结了SVM基本原理和核函数以及软间隔原理,本文我们就针对前面推导出的SVM对偶问题的一种高效的优化方法-序列最小优化算法(Sequential Minimal Optimization, SMO)的原理进行总结并进行相应的Python实现。

坐标上升算法(Coordiante Ascent)

在SMO算法之前,还是需要总结下坐标上升算法,因为SMO算法的思想与坐标上升算法的思想类似。

坐标上升算法每次通过更新多元函数中的一维,经过多次迭代直到收敛来达到优化函数的目的。简单的讲就是不断地选中一个变量做一维最优化直到函数达到局部最优点。

Read More

2017-08-30
机器学习算法实践-SVM核函数和软间隔

机器学习算法实践-SVM核函数和软间隔

前言

上文中简单总结了对于线性可分数据的SVM的算法原理,本文对于非线性可分以及有噪声存在的时候我们需要对基本SVM算法的改进进行下总结其中包括:

  1. 核函数在SVM算法中的使用
  2. 引入松弛变量和惩罚函数的软间隔分类器

SVM对偶问题

这里稍微回顾下SVM最终的对偶优化问题,因为后面的改进都是在对偶问题的形式上衍生的。

Read More

2017-08-15
机器学习算法实践-支持向量机(SVM)算法原理

机器学习算法实践-支持向量机(SVM)算法原理

前言

关于SVM的算法实践我打算分成多个部分进行总结。本文为第一部分主要介绍SVM的原理以及相关算法的简单推导,其中包括SVM原理,最初表达式,标准形式以及对偶形式(二次规划问题),形式变化过程中涉及到求解有约束优化问题的拉格朗日乘子法以及KKT条件等。

什么是支持向量机

对于线性可分两类数据,支持向量机就是条直线(对于高维数据点就是一个超平面), 两类数据点中的的分割线有无数条,SVM就是这无数条中最完美的一条,怎么样才算最完美呢?就是这条线距离两类数据点越远,则当有新的数据点的时候我们使用这条线将其分类的结果也就越可信。例如下图中的三条直线都可以将A中的数据分类,那条可以有最优的分类能力呢?

  1. 我们需要线找到数据点中距离分割超平面距离最近的点(找最小)
  2. 然后尽量使得距离超平面最近的点的距离的绝对值尽量的(求最大)
Read More