模拟退火
概述 模拟退火的出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。
原理1.加温过程增强粒子的热运动,使其偏离平衡位置,当温度足够高的时候,固体将熔为液体,消除原有的非均匀状态。
2.等温过程对于与周围环境交换热量而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行的,当自由能达到最小时,系统达到平衡状态。
3.冷却过程使粒子热运动减弱,系统能量下降,得到晶体结构。
加温过程相当于对算法设定初值,等温过程对应算法的Metropolis抽样过程,冷却过程对应控制参数的下降。这里能量的变化就是目标函数,我们要得到的最优解就是能量最低态。其中Metropolis准则是SA算法收敛于全局最优解的关键所在,Metropolis准则以一定的概率接受恶化解,这样就使算法跳离局部最优的陷阱。
SA算法的Metropolis准则允许接受一定的恶化解,具体来讲,是以一定概率来接受非最优解。举个例子,相当于保留一些“潜力股”,使解空间里有更多的可能性。对比轮盘赌法,从概率论来讲,它是对非最优解给予概率0,即全部抛弃。
模拟退火本身是求一个最小值问题,但可以转化为求最 ...
粒子群算法(PSO)
概括特点 粒子群算法具有收敛速度快、参数少、算法简单容易实现的优点,但是会有局部最优解的情况发生。
基本思路 粒子群算法主要模拟鸟类觅食的行为,所以我们设想我们的“小鸟”在森林中随机搜索,每一只”小鸟“都向着自己判断的方向搜索,并记录搜索过程中食物最多的位置,同时进行共享,这样“小鸟”们就知道哪个为止的食物最多。在整个搜索过程中每只“小鸟”都会根据鸟群当前的信息来调整自己的搜索策略。
基本原理6个重要参数
粒子位置$X_{id}$
粒子速度$V_{id}$
第i个粒子搜索到的最优位置$P_{i,pbest}$
群体搜索的最优为止$P_{d,gbest}$
第i个例子搜索到的最优位置的优化目标函数值$f_p$
群体搜索的最优位置的优化目标函数值$f_g$
流程图
参数详解粒子群规模:N 没啥好说的,越多越好,但是随着数量的增加,“性价比”会很低。
粒子维度:D 根据优化目标函数的自变量个数进行设置。
迭代次数:K 字面意思,特点和粒子群规模差不多。
(经典取值:60、70、100)
惯性权重:$\omega$ 动态调整惯性权重以平衡收 ...
jupyter疑难杂症
添加anaconda环境首先安装ipykernel:conda install ipykernel
在虚拟环境下创建kernel文件:conda install -n 环境名称 ipykernel
激活conda环境: source activate 环境名称
将环境写入notebook的kernel中
python -m ipykernel install —user —name 环境名称 —display-name “Python (环境名称)”
删除kernel环境:
jupyter kernelspec remove 环境名称
常见还原算法
如果对压缩感知没有概念的同学可以去看看我的上一篇文章:压缩感知基本概念
基追踪算法 我们考虑下面的问题:
Ax=b 其中$x\in R^n,b\in R^m,A\in R^{m\times n},m<<n$,实际上,这个问题是存在无穷多解的,但是对于压缩感知而言,我们需要的是稀疏解,所以我们需要将问题转化成
min||x||_0 \quad s.t.\quad Ax=b 但是我们不难发现,这是一个NP-hard问题,但是在这类问题中,我们可以将$||x||_1与||x||_0$等价看待,由于$||x||_1$是连续的,对于我们来说就可以更好地进行求解。但是,还有一个问题,$l_2$范数比$l_1$范数更好求解,那么我们可以通过求解$min||x||_2$来求解问题嘛,很明显,这是不行的,因为$l_2$范数会破坏数据的稀疏性,所以求解的出来的那个解对于我们来说是没有用的,简单点说就是$l_2$范数的解空间是与球相切的,它的解在坐标轴上是非稀疏的(有点粗略,不明白的可以去各大wiki上学学范数)。
求解线性规划问题 一个比较基础方法 ...
大规模无线传感器网络压缩数据采集
压缩感知主要应用于图像处理等领域,但是如果我们利用其特性,它在物理网领域也是可以得到较好的运用的,这篇博客主要是讲一种Compressive Data Gathering(CDG)方法在物联网数据收集中的应用。
采用压缩感知的优势 在物联网传输信息的过程中,我们单独抽出一条链路传输信息的过程来看.
我们可以看到,在数据向Sink节点传输的过程中,单对传输这个过程来说,他的复杂度是$O(n^2)$的,同时,在传输的过程中,整个能量的消耗是不均匀的,越接近Sink节点的子节点能量消耗越大,这对于整个无线传感器网络的效率与维护是不利的,所以我们采用压缩感知算法来优化这一过程。
如何采用压缩感知算法如下图所示:
图a是一个常见的无线传感器网络,可以看到图中的Sink节点有四个子树(用虚线划分),我们取出其中一个子树作为样例来解释如何进行压缩,我们假设对节点$S_i$收集到的数据标记为$x_i$,那么根据压缩感知的理论我们就可以得到这样一个压缩的结果,如果对压缩感知没有概念的同学可以去看看我的上一篇文章:压缩感知基本概念
y_i=\sum_{j=1}^ ...
压缩感知基本概念
奈奎斯特采样定理 想要让采样之后的数字信号完整保留信号中的信息,采样频率必须大于信号中最高频率的两倍!
为什么? 从下面这张图中可以看到,如果采样率比信号频率的两倍要低,那么在频域中信号会混叠,这个信号就和时域信号中的信号不一样了。
举个例子,对于一个$sin(2\pi x)$的信号,他的周期是$1$,频率就是$1$
我们可以看到在1Hz的采样频率的情况下,图像已经和我们的原函数相差很大了,当2Hz的采样频率下才有点像了,当10Hz就已经十分甚至九分地像了。当然这是对于一个比较标准的三角函数来进行的模拟,感兴趣的读者可以试着自己做一下多个不同周期的正弦波叠加的信号在不同采样频率下的结果。
概念的提出 所以说我们可以粗略地得出一个结论,采样的频率越高,还原出来的原始信号就越符合原始信号!
但是,问题来了,我们一定要在那么高的采样率下进行数据收集嘛?很显然,这是一种资源的浪费,所以,在2004年,三位大牛证明出,如果信号是稀疏的,那么它就可以由远低于上述采样定理要求的采样点重构恢复,并于2007年正式提出了“压缩感知”
为什么 ...