算法选择问题

① 每天一个知识点：分治算法：选择问题

选择问题的要求是找出含有 N 个元素的表 S 中的第 k 个最小的元素。

基本的算法是简单的递归策略。设 N 大于截止点(cutoff point)，在截止点后元素将进行简单的排序，v 是选出的一个元素，叫做枢纽元(pivot)。其余的元素被放在两个集合 和 中。 含有那些不大于 v 的元素，而 则包含那些不小于 v 的元素。

为了得到一个线性算法，必须保证子问题只是原问题的一部分，而不仅仅只是比原问题少几个元素。这里要解决问题就是如何花费更少的时间来寻找枢纽元。

为得到一个好的最坏情形，关键想法是再用一个间接层。不是从随机元素的样本中找出中项，而是从中项的样本中找出中项。

基本的枢纽元选择算法如下：

上面给出的枢纽元选择法，有一个专业的术语，叫做“五分化中项的中项”。“五分化中项的中项”保证每个递归子问题的大小最多是原问题的大约 70%。对于整个选择算法，枢纽元可以足够快的算出，以确保 的运行时间。

定理：使用“五分化中项的中项”的快速选择算法的运行时间为 。

分治算法还可以用来降低算法预计所需要的比较次数。

设有 N 个数的集合 S 并且要寻找其中第 k 个最小的数 X。我们选择 S 的子集 S‘，令 δ 是某个数，使得计算过程所用的平均比较次数最小化。

找出 S’ 中第 ( ) 个和第 个最小的元素，几乎可以肯定 S 中的第 k 个元素将落在 和 之间，此时，问题变成了 2δ 个元素的选择问题。

经过分析，会发现，若 和 ，则期望的比较次数为 ，除低次项外它是最优的。（如果 k>N/2，那么我们可以考虑查找第(N-k)个最大元素的对称问题。）

最后一项代表进行两次选择以确定 和 的代价。假设采用合理聪明的策略，则划分的平均代价等于 N 加上 在 S 中的期望阶(expected rank)，即 。如果第 k 个元素在 S‘ 中出现，那么代价就是 O(N)。然而，s 和 δ 已经被选取以保证这种情况以非常低的概率 o(1/N) 发生，因此该可能性的期望代价是 o(1)，当它的 N 越来越大时趋向于 0。

这个分析指出，找出中项平均大约需要 1.5N 次比较。当然，该算法为计算 s 需要浮点运算，这在一些机器上可能使该算法减慢速度。不过即使是这样，若能正确实现，则该算法完全能够比得上快速选择实现方法。

② 遗传算法中选择算子的问题

首先介绍sort函数用法：
[B,I]=sort(A,.....),I为返回的排序后元素在原数组中的行位置或列位置.B一般为排序后的数组。举例：
A = 3 4 2
1 5 3
4 7 1
[B,I]=sort(A)
B = 1 4 1
3 5 2
4 7 3
I = 2 1 3
1 2 1
3 3 2
[Oderfi,Indexfi]=sort(fi)，因此这句话中的Oderfi保存了从小到大排列的结果，而Indexfi保存了Oderfi中对应原始数组（fi）的的原始位置。
fi_Size=(Oderfi/fi_sum)*Size 这句话挺难理解的，不过我运行了这个程序后，还是被我发现了
其中Oderf为 适应值 由小到大排列，fi_sum为适应值的总和，Size为总的个数，而fi_sum/size就是平均值，因此。fi_size中所存放的数据是Oderf中数值除以其平均值后的结果。其中必有大于1的，小于1的。我们这里的淘汰规则是淘汰掉 种群中小于平均值的数据，下边的代码是对这个规则的具体化
fi_S只包含0和1，其中0是小于平均值的个体，1是大于平均值的个体。
for j=1:1:fi_S(i) %Select and Reproce
TempE(kk,:)=E(Indexfi(i),:);
kk=kk+1; %kk is used to reproce
end
E中保存的是初始种群，我们每一代种群中都会有80个个体（每一行是一个个体，列数决定了个体范围和精度），当fi_S中某个个体（记为个体A）不是0的时候，就执行了TempE(kk,:)=E(Indexfi(i),:);
这句代码，Indexfi保存了个体A在E中的行数（也就是fi的列数），我们认定这一行（这个个体A）具有优良基因，因此保存在TempE中，进化到下一代。

好久没看遗传算法了，上边的有些术语是我自己编的，看懂就好
还有，你的程序不完全，你能把这个完整的遗传算法代码给我吗，我感觉这个程序写的很简洁，非常好。我的邮箱[email protected]
另外你用这个程序算做什么？一般智能算法解决解决问题具有随机性，因此很难对误差做出评价，这也是应用受到阻碍的主要原因，如果在解决具体问题的时候，还是优先考虑定量算法的。
希望我的回答对你有所帮助。

③ 机器学习算法选择问题

你这个类似故障分类问题了。分以下两种情况给你提供个思路吧：
1.如果你的数据是有标签的，那就可以做有监督的机器学习了。
就是你的数据样本是某时刻各种属性值，标签是此时刻是否有零件有故障以及哪个零件故障。
可以选用的模型有：LogisticRegression、SVM、NaiveBayes、DecisionTree、KNN等，较浅的神经网络也是可以的。
2.如果你的数据没有标签，就不太好办了，可以试试无监督的聚类方法看看有没有什么发现。如Kmeans。
3.我做过的故障分类是有监督的，零件属于某个子系统，子系统又属于某个系统。我先对系统建模，再对子系统建模，再对零件建模，逐步定位到具体问题。
4.如果你的数据真的是无标签的，另外给你提供个线索，可以去研究下自编码网络。

④ 求教：蚁群算法选择最短路径问题

这个例子其实是当初数模比赛时用来完成碎片拼接的，但其所用到原理还是求解最短路径的原理。但这里的最短路径和数据结构中最短路径有一定的区别。在数据结构中，对于最短路径的求解常用的一般有Dijkstra算法与Floyd算法，但对于要求出一条经过所有的点的并且要求路径最短，这些算法还是有一定的局限性的。而蚁群算法则很好地满足了这些条件。话说回来，很想吐槽一下网络流传的一些蚁群算法的例子，当初学习这个时候，身边也没有相关的书籍，只好到网上找例子。网上关于这个算法源代码的常见的有2个版本，都是出自博客，但是在例子都代码是不完整的，缺失了一部分，但就是这样的例子，居然流传甚广，我很好奇那些转载这些源码的人是否真的有去学习过这些，去调试过。当然，我下面的例子也是无法直接编译通过的，因为涉及到图像读取处理等方面的东西，所以就只贴算法代码部分。但是对于这个问题蚁群算法有一个比较大的缺点，就是收敛很慢，不过对于数量小的路径，效果还是很好的。function bestqueue =aco1(nt,nc_max,m ,st, sd ,Alpha ,Beta ,Rho ,Q,gethead,getend)%参数解释：%nt 路径所经过的点的个数；%nc_max 迭代的次数；%m 蚂蚁的个数；%st 起点序号；%sd 终点序号；%Alpha 信息素系数；�ta 启发因子系数；%Rho 蒸发系数；% Q 信息量；%gethead getend 是用来求距离矩阵的，可根据实际情况修改
% nt = 209;%碎片个数full = zeros(nt,nt);tic;%初始化距离矩阵for i =1:nt for t = 1:nt if i ~= t full(i,t) = sum(abs(getend(:,i) - gethead(:,t))); else full(i,t) = inf; end endend% a =full(156,187)eta = 1./full;%启发因子，取距离的倒数% eta% e = eta(4,2)tau = ones(nt,nt);%信息素矩阵% tabu = zeros(nt,nt);%禁忌矩阵，取蚂蚁数量和碎片数量一致，以减少迭代次数nc =1;%初始化迭代次数;rbest=zeros(nc_max,nt);%各代最佳路线rbest(:,1) = (linspace(st,st,nc_max))';rbest(:,nt) =(linspace(sd,sd,nc_max))'; lbest=zeros(nc_max,1);%各代最佳路线的长度pathlen = 0;%临时记录每代最佳路线长度stime = 1;%记录代数进度for i = 1:nc_max % 代数循环 delta_tau=zeros(nt,nt);%初始化改变量 stime for t = 1:m % 对蚂蚁群体的循环， tabu=zeros(1,nt);%禁忌向量，标记已访问的碎片，初试值设为0，访问之后则变为1; viseted = zeros(1,nt);%记录已访问的元素的位置 tabu(st) = 1;%st为起点，在此表示为碎片矩阵的编号，因为已经将蚁群放在起点，故也应将禁忌向量和位置向量的状态进行修改 tabu(sd) =1;%同上 visited(nt) = sd ;%同上； visited(1) = st;%同上； ht = 0; for r = 2:nt-1 %记录了还没访问的图片编号 vp = 1;%visited指示量 pp = [];%置空的概率向量 jc = 0; %获取尚未访问的位置的向量。 wv = zeros( nt -2 - ht ); for k =1 : nt if tabu(k) == 0 jc = jc +1; wv(jc) = k; end end% a =(tau(visited(end),ju(3))^Alpha)*(eta(visited(end),ju(3))^Beta)% visited(end) %计算选择的概率 for k=1:length(wv) pp(k)=(tau(visited(vp),wv(k))^Alpha)*(eta(visited(vp),wv(k))^Beta);%下一张碎片的选择概率计算，p =（信息素^信息素系数）*（启发因子^启发因子系数） end pp=pp./(sum(pp));%归一化 pcum =cumsum(pp); psl = find(pcum >= rand);%轮盘赌法 to_visit= wv(psl(1)) ;%完成选点 tabu(to_visit) =1; visited(r) = to_visit; ht =ht +1;%已访问碎片个数变化 vp =vp+1; end %路径变化信息 %对单个蚂蚁的路径进行统计 sum1 =0; for pr = 1:nt -1 x = visited(pr); y = visited(pr+1) ; sum1 =sum1 + full(x,y); end% vcell{t} =visited;%元胞记录每个蚂蚁的路径，即碎片顺序;% msum(t) = sum1; %信息素变化； for ww=1:(nt-1) delta_tau(visited(ww),visited(ww+1))=delta_tau(visited(ww),visited(ww+1)) + Q/sum1; end% delta_tau(visited(end),visited(1))=delta_tau(visited(end),visited(1))+Q/(sum1/100);% if t == m & i == nc_max % bestqueue = visited% end if t == m bestqueue = visited end end tau=(1-Rho).*tau+delta_tau; %完成信息素的更新，找出现有的最新的最佳路径,即信息素最多的路径； stime =stime +1;end toc;