Pagerank算法

思想

在互联网中，如果一个网页被很多其他网页所链接，说明它受到了普遍的承认和信赖，那么它的排名就会比较高，即它的pagerank比较高。

对于每个网页自身而言，它的重要程度由所有链接到它的网页贡献而来。对于一个网页，它的pagerank越大，那么它“说话”的“分量”也会越大，因此如果它链接到了一个其他网页，那么它对这个网页pagerank的贡献也会越大；相对的如果一个网页的pagerank较低，那么它能够给它链接到的网页贡献的pagerank就会比较小。

在整个互联网中会出现悬挂点以及排他水槽，如果不加以解决的话它们就会消耗掉整个网络中的pagerank。因此对于每个节点，都让其有一定的概率跳转到整个网络中任意的一个点中，这样就避免了悬挂点和排他水槽消耗掉整个网络的pagerank。

步骤

1. 根据各个网页之间的链接关系，得到该网络对应图，之后根据图中每个点的出度得到该网络的超链矩阵H；
2. 选择适合的阻尼系数 α \alpha α，通常取 α = 0.85 \alpha = 0.85 α=0.85，将超链矩阵转化为谷歌矩阵，公式为 G = α H + ( 1 − α ) n J G=\alpha H + \frac{(1 - \alpha)}{n} J G=αH+n(1−α)​J，其中j为大小为n的全1矩阵， n n n为图中点的个数；
3. 选择合适的 n n n维向量 I I I，该向量需要满足向量中所有数相加的和为 1 1 1，即 ∑ j = 1 n I [ j ] = 1 \sum _{j=1}^n I[j]=1 ∑j=1n​I[j]=1；
4. 不断进行 I = G I I=GI I=GI的矩阵相乘迭代，直到迭代前后向量 I I I几乎不发生变化，即 M a x j = 1 n { Δ I [ j ] } < ϵ Max_{j=1}^{n}\{\Delta I[j]\}<\epsilon Maxj=1n​{ΔI[j]}<ϵ时停止迭代，其中 ϵ \epsilon ϵ为设置的允许的前后变化的最大值；

Random Walk算法

思想

该算法要实现的是搜索，从起始点s开始找到目的地t。

给定一个图，从起点开始走的每一步都让其有一定的概率 α \alpha α跳转到图中的任意一个点上，还有 1 − α 1-\alpha 1−α的概率会行走到任意一个与该点相连的点上。不断的重复上述过程，直到找到目的地中。

该算法的思想也被应用到了pagerank算法中，pagerank算法中为了解决悬挂点和排他水槽的问题，也使得每个点有一定概率跳转到图中任意一个点中。

步骤

1. 将实际问题抽象为图的形式，并用临接表、邻接矩阵等存图方式将图存储在计算机中；

2. 用一个变量记录当前所处的位置（图中点的标号），每次随机一个[0, 1]之间的数，若其小于等于随机跳跃概率 α \alpha α则随机一个[1, n]的数字并跳转，否则随机一个 x , x ∈ S x,x\in S x,x∈S，其中S为与当前点相连的点的集合；

3. 不断重复第二步并记录路径，直到找到目的地t.

Genetic算法

思想

遗传算法的根本思想就是达尔文的适者生存法则。

使用二进制编码（也就是基因），对要进行优化的问题的某个属性进行编码。对于更适应环境的个体它有更大的概率（选择）能够将自己的基因遗传给下一代（交叉）。

同时遗传算法还允许个体的基因有一定的概率发生突变（突变），这样可以丰富基因库，使得可以跳出局部最优，找到全局最优。

步骤

以找二元函数 f ( x , y ) f(x,y) f(x,y)最大值为例。

1. 确定群体数量n，并随机生成n个个体，对于每个个体都有两个长度为m的二进制串代表他们的DNA链，分别代表x、y.
2. 确定适应度函数，在这个问题中适应度函数就是 f ( x , y ) f(x,y) f(x,y)，函数值越大代表其适应度越高.
3. 将每个个体的基因序列转化为十进制值（二进制转十进制），并按照比例映射到规定的x,y区间中，用适应度函数计算每个个体的适应度.
4. 选择：通过轮盘赌的方式选出n对个体 A i , B i , i ∈ [ 1 , n ] A_i,B_i,i \in [1,n] Ai​,Bi​,i∈[1,n]。
5. 交叉：对于每一对个体 A i , B i A_i,B_i Ai​,Bi​，随机选择两个[1,m]之间的数字 p 1 , p 2 p_1,p_2 p1​,p2​，作为两个个体遗传片段的分割点。例如新个体的x基因是由 A i A_i Ai​的前 p 1 p_1 p1​长的序列和 B i B_i Bi​的后 m − p i m-p_i m−pi​长的序列遗传得到的。
6. 变异：对于每个新产生的个体，随机一个[0,1]的数字，若其小于变异概率，则随机选中新个体中的一个基因中的一个单点，对其进行取反操作.
7. 用新产生的群体取代上一代的群体.
8. 重复3、4、5、6、7步操作T次，T为提前设置好的进化次数。

这样最终群体代表的x、y就是函数 f ( x , y ) f(x,y) f(x,y)的最大值对应坐标位置。