第一篇：最新高维多目标进化算法总结
高维多目标进化算法
二、文献选读内容分析及思考
（一）Borg算法
Borg算法是基于ε-MOEA算法（Deb，2003）的一种全新改进算法[32]，下面将从创新点、原理、算法流程和启发思考四方面进行阐述。1.创新点
1）在ε支配关系的基础上提出ε盒支配的概念，具有能同时保证算法收敛性与多样性的特点。
2）提出了ε归档进程，能提高算法计算效率和防止早熟。3）种群大小的自适应调整。
4）交叉算子的自适应选择。由于处理实际问题时，是不知道目标函数具有什么特性，前沿面如何，在具有多个交叉算子的池子里，根据进程反馈，选择不同的交叉算子，使产生的后代具有更好的特性针对要研究的问题。2.Borg算法原理
1）ε盒支配：通过对目标空间向量的每一维除以一个较小的ε，然后取整后进行pareto支配比较。这样的支配关系达到的效果是把目标空间划分成以ε为边长的网格（2目标时），当点处于不同的网格时，按pareto支配关系比较；当处于同一网格时，比较哪个点距离中心点（网格最左下角）最近。这样一来，网格内都只有一个点。
2）ε归档进程
如图1所示，黑点表示已经归档的，想要添加到档案集的新解用×表示，阴影表示归档解支配的区域。当新解的性能提升量超过阈值ε才属于ε归档进程。比如解
1、解2加入归档集属于ε归档进程，解3加入归档集就不属于ε归档进程。
图1 ε支配网格
在这个过程中设置了一个参数c，表示每一代中加入归档集解得个数，每隔一定迭代次数检测c有没有增加，如果没有增加表明算法停滞，重启机制启动。
3）重启
自适应种群大小：重启后的种群大小是根据归档集的大小设置。γ表示种群大小与归档集大小的比值，这个值也用于第二步中，如果γ值没超过1.25，重启机制也启动。启动后，γ人为设定为固定值，种群被清空，填充归档集的所有个体，不足的个体是随机选取归档集中个体变异所得。与之相匹配的锦标赛比较集大小是归档集大小乘以固定比值τ。
4）交叉算子的自适应选择
摒弃以往采用单一的交叉算子，采用包含各类交叉算子的池子，比如有K种交叉算子，选择概率最开始是相等的，设n表示各类交叉算子产生的后代属于ε归档进程所得个数，个数越多，选取相应交叉算子的概率就越大，逐渐趋于选择解决未知现实问题的交叉算子。3.Borg算法总体流程
通过交叉算子的自适应选择选择一种交叉算子，假设所选交叉算子需要K个父代，1个父代在归档集中按均匀分布选择，K-1个父代从种群中按锦标赛选择（大小按上述第3步中计算），交叉产生一个后代，如果这个后代pareto支配种群中一个或多个个体，则随机的取代一个；如果被种群中的任一个体支配，则不能加入种群；如果互不支配，也是随机的取代种群中的一个。而加入归档集，是按照上述第2步实施的。如此循环一定代数之后，看达没达到第3步重启的条件，达到则重启过程开始，直至满足终止条件。4.思考
1）ε盒支配时，同一网格内的点只是比较离中心点距离最近的，这就有一个不足，最近的不一定是非支配解，离的远的点有可能还支配它，我觉得还需要比较一下哪个解优的目标维数多。
2）设计一种云交叉算子，加入到交叉算子的池子里，或是参数控制云交叉算子替换其中的能达到类似效果的几种算子，便于统一。
（二）基于模糊支配的高维多目标进化算法 1.算法简介
基于模糊支配的高维多目标进化算法[33]是对模糊支配关系的一种改进，2005年M.Farina首次提出的模糊支配，其隶属函数是一条正态分布函数，如图2所示，而此文的隶属函数是一条半正态分布函数，表达的概念更加清晰。
图2 正态隶属函数
对于最小化问题，归一化后的解A（a1,a2,...,aM），B（b1,b2,...,bM）如果目标向量的某一维上的差量（ai-bi）达到-1，则ai好于bi的程度为1，即pareto支配关系下ai支配bi；如果差量（ai-bi）是1，则pareto支配关系下bi支配ai。A模糊支配B程度为每一维差量映射下的隶属度之积，与种群中其他解进行比较，所得隶属度相加即为A解在整个中群众的性能好坏程度，相当于NSGA-II中的非支配排序，只是这里的等级程度更加细分，然后还得设置一个阈值α，即模糊支配隶属度达到多少才能是最优解，也就是NSGA-II中的非支配排序等级为1的解。设定这个值是关键，此文献也对这个值得选取进行了实验说明，针对不同的问题选取不同的值，但是还没能达到根据问题特性自适应调整。2.思考
1）既然隶属度函数不是一成不变的，想用云模型确定隶属度，借鉴张国英《高维云模型及其在多属性评价中的应用》构造一M维云模型，它的作用是输入M维差量映射为一维的模糊支配隶属度u，无需像上文中求出每一维隶属度再相乘。
2）由于阈值α不好确定，可不可以根据归档集的大小取前N个，找到使个体数量大于等于N的u值为α。
（三）基于网格支配的高维多目标进化算法
GrEA[34]也是针对ε-MOEA算法进行改进的，作者认为ε-MOEA算法中的网格划分是基于个体的，如果个体分配不均匀，也就不能得到分布性好的最优前沿，而且网格的大小也不能随着目标空间的特性而自适应调整。1.支配关系创新
grid-dominance，这种支配关系是基于空间区域划分网格，就是在当代种群中找出每一个目标函数上的最大值与最小值（下图上行），然后根据这两个值计算出这个目标函数的网格上下界值（下图下行）。人为设定每一个目标函数需划分的段数div,是一个固定的值，这样就使得收敛性与多样性的要求随着算法进程自适应调整，比如说刚开始时目标空间的个体分布比较广，就需要大的网格来选择个体，随着算法深入，个体更加集中于Pareto前沿区域，就需要小的网格区分个体，更加强调个体的多样性，因此这样动态的网格划分更能体现算法的进程。另外，ε-支配强调个体生死，只有非支配才能加入归档集；而grid dominance不同，它更强调个体的先后，非支配个体只是先于支配个体进入归档集，支配个体还是有机会加入归档集，这在一定程度上保留了边界点，而ε-MOEA算法会丢失边界点。
图3 网格分段示意图
2.适应度值指派创新
本文提出了适应度值指派的三个指标grid ranking(GR)、grid crowding distance(GCD)和grid coordinate point distance(GCPD)，GR和GCPD是收敛性评价指标，GCD是多样性评价指标，网格指标如图4所示。
GR表示个体所处网格各维目标函数坐标之和，相当于将目标向量各维相加，只不过这里是将函数值映射为所处网格坐标值之和。比如下图A点的网格坐标为（0,4），则GR=0+4=4。
GCD是网格拥挤距离，以往的网格拥挤距离都是在一个网格之内的，这样就不能反映分布性了，此处的GCD还考虑临近网格的个体，用网格坐标的差量之和评估，之和越小的GCD值就越大，多样性就越差。如下图C的邻居是B、D，F的邻居是E、G。
GCPD表示的是同一网格内与中心点的距离，这一点与ε-MOEA中相同。比较的先后准则是GR，GR相同比较GCD，GR、GCD都相同则比较GCPD。
图4 网格指标示意图
3.归档策略的改进
以往的归档策略都是基于适应度值的支配关系选择删除，这样会导致解集多样性的缺失，因为相邻的点具有相似的适应度值，会使他们同时被选择或删除，比如上图的E、F、G，这样多样性会得不到保证。本文作者对归档策略进行了改进，就是当一个个体加入归档集时，在归档集中和它相关的个体GR值会受到惩罚，相关的个体包括：1.处于同一网格坐标 2.被网格支配的 3.邻域个体，惩罚力度依次减小。
（四）基于坐标转换的高维多目标进化算法
针对原始的密度评估算子在高维多目标中会出现不能很好的兼顾收敛性与多样性，解集往往会有很好的多样性而收敛性差的缺点，论文设计了一种包含收敛性的密度评估算子shift-based density estimation(SDE)[35]。比如图5中的A点，按照基于pareto支配的多目标优化算法来看，是非支配解切多样性好于B、C、D，但很明显得看出A点收敛性不及BCD。SDE是将各维目标函数上小于A点对应维的值转化为A点那一维的函数值，如下图所示。转换之后A点的密度值较大，而BCD密度值较小，符合所考虑的情况
图5 坐标转换示意图
从图6的四图中可以看出，只有收敛性和多样性都好的个体，其SDE值小，即其值不仅体现密度信息，而且将收敛性信息也包含在内。SDE是一种通用的密度评估算子，可以将其植入NSGA-II，SPEA2和PESA-II中。
图6 拥挤密度示意图
（五）基于角点排序的高维多目标进化算法
本文是在非支配排序上的改进。在高维多目标优化问题中，随着目标维数的增加，非支配解之间的比较次数是非常大的，因此论文提出了角点支配。所谓的角点指的是在M维目标空间中只考虑其中k个目标，在本文中只考虑一个目标函数上的，因为在一个目标函数上最好的点肯定是非支配解。二维、三维角点分别如下图所示。
图7 二维、三维角点示意图
找到角点后，所有被角点支配的点就不用比较了，大大减少评价次数。而且本文还指出非支配解排序的比较次数应该是精确到每一维的目标函数的比较上，因为每两个解之间目标函数的比较次数从2到M，也就是说不同的两个解之间比较所花费的计算量是不同的，只计算一个解与其他解的比较次数是不对的。角点支配排序大致过程如图8所示。
图8 角点非支配排序
图8是2维目标函数的情况，首先得找出每一维目标函数上最好的点，如上图A中的白点，标记他们所支配的点如上图阴影区域，这些点在当前等级中就不考虑排序了，在剩下的点中再寻找两个角点，直到将所有的点都标记，如图B，B中白点表示等级1，等级2、3依次进行。
（六）NSGA-III算法系列文献 1.MO-NSGA-II 为了适合解决高维多目标问题，Kalyanmoy Deb针对NSGA-II的缺点，提出了MO-NSGA-II（many-objective NSGA-II），这是NSGA-III的雏形。MO-NSGA-II的基本框架和NSGA-II差不多，不同之处在于精英选择机制上，因为原有的选择机制对快速增加的非支配解已经没有选择压力。MO-NSGA-II是一种基于参考点的多目标算法，放置分布性好的参考点，使得到的非支配解靠近这些参考点，就能得到分布性好的最优前端。
让我们回顾一下NSGA-II，有一个大小为N的当前种群Pt，由他产生的子代种群Qt，大小也为N，然后对Pt、Qt的合集Rt进行快速非支配排序F1、F2...Fi,将这些点按等级加入下一代种群Pt+1，通过对Fl中个体计算拥挤距离按降序排列，依次加入Pt+1，直到种群大小为N。
参考点的设置就是从这里开始，取代原有的拥挤距离。均匀分布的参考点可以通过一些特定的系统产生。
1）超平面的建立。设F1、F2...Fi的合集为St，在这个集合中找到每一个目标函数值最小的点组成理想点zminminmin(z1min,z2,...,zM)，将目标函数值转化为相对的minf‘i(u)=fi(u)zi，然后种群中的点通过一个聚集函数求最小值（它是相对于在某一维坐标轴上的参考点的）把它当成这一维的端点，通过这M个端点构造超平面，根据这个超平面重新计算参考点，这个超平面在每一代中都不同，所以它是可以根据种群特性自适应调整。
2）选取低拥挤度的解。为了确定解集拥挤度，需要把所有的点投影到超平面上（如图9左图），找到与之距离最近的参考点，这样每个参考点就会有一定数量的解与之相关联（如图9右图）。选择参考点周围个体最少的参考点，选出Fi解集中在这个参考点下ASF最小的点加入Pt+1。再选出个体数次最少的参考点，选出Fi解集中在这个参考点下ASF最小的点加入Pt+1，直到加满Pt+1。
图9 关联操作
3）锦标赛选择。当Pt+1形成，用锦标赛方法产生后代Qt+1，具体操作是从Pt+1任意挑选两个解，比较策略是如果一个解的非支配等级小于另一个解，选择前一个解；如果同处一个非支配等级但是所属参考点的拥挤度不同，选拥挤度小的点；如果非支配等级和所属参考点的拥挤度都相同，则选ASF值小的。然后采用模拟二进制交叉算子，产生后代Qt+1，然后在合并进行第一步，依次循环。2.NSGA-III 本文作者针对上文提出的MO-NSGA-II作了适当改进，提出了NSGA-III。1）超平面的建立。与上文不同的是，本文将超平面进行了归一化处理，找到基于坐标轴上的参考点的每一维端点zmax后，还必须将组成的超平面延伸相交于fi，坐标系，截距为ai，如图10所示。
图10 端点归一化示意图
2）个体与参考点的关联操作。上文中是将个体投影到超平面上，而此文是个体与参考线方向的垂直距离（参考线方向是参考点与理想点的连线方向），如图11所示。
图11 关联操作
3）小生境保留操作。此处本文与上文有个很大不同，本文只计算排除Fi的St，的小生境数，选出围绕参考线个体为0的参考线，如果有多条则任选一条，即0，这样Fi个体就有两种情况。第一，Fi中有一到多个个体与参考点j相j关联，这样就选一个与参考点j垂直距离最短的个体加入下一代种群Pt+1，加
j1。第二，如果，Fi中没有个体与参考点j相关联，则这个参考点在当前代就不用考虑了。如果0，则从Fi中与参考点j相关联的个体集合中任选一个，jj加1。重新调整小生境数，直到加满Pt+1。3.C-NSGA-III 上文提出的NSGA-III是处理无约束的问题，本文为处理约束条件，对NSGA-III进行了改进。1）精英选择操作上的改进，用约束支配取代pareto支配，和NSGA-II为处理约束条件的约束支配原则是一样。此时的种群一般既有可行解，还有不可行解，如果可行解的个数NfN，那么还需要从具有最小约束违反度的不可行解中选取个体加满Pt+1；如果NfN，则按照无约束的NSGA-III精英选择操作进行，接着也要用Pt+1中可行解更新理想点和端点。
2）子代种群生成。锦标赛选取规则是任选两个解，如果一个可行解，一个不可行解，选可行解；如果都是不可行解，选约束违反度小的；如果都是可行解，任选一个；这样选择出一个父代，再进行一次，选出另一个父代，模拟二进制交叉，然后变异。
但是通过实验发现上述算法有个不足，由于约束条件的存在，可行区域可能只是整个区域的一小部分，然而参考点是均匀的分布在目标向量空间，导致不是每个参考方向都能与最有前沿面相交，也就是说有一部分参考点是没用的，而用到的参考点会与多个个体相关联，又不能达到好的分布性，如图12所示。
图12 参考点自适应调整
这就涉及到一个问题：如何使所有的参考点能均匀分布在可行区域上，理想的方法是能分配所有的参考点均匀地分布在最优前沿面，但是对于不同的问题最优前沿面是未知的。于是本文作者提出了自适应的NSGA-III，叫做A-NSGA-III，让它能够自适应鉴别出无用的参考点然后分配他们，希望能找到新的最优解。于是在原有的NSGA-III生成大小为N的Pt+1后，有两个新的操作1.增加新的参考点 2.消除无用的参考点。
1）增加新的参考点。由于参考点个数等于种群规模，理想情况是一个参考点一个个体，当参考点j方向的小生境数j1，则必存在参考点k方向的小生境数，k0。我们针对参考点j，在其周围增加M个参考点的单纯形（单纯形法是一类在小范围内具有更精细搜索效果的优化算法，能提高点的多样性），如下图所示三维空间中具有三个顶点的单纯形扩展。
图13单纯形扩展法
但是扩张的点有两种情况是不接受的：1.不在第一象限 2.在参考点集中已经存在
2）消除无用的参考点。扩张完后的参考点可能存在一些无用的，则消除那些j0的扩展点，而原始的参考点j0是要保留的，有可能下一代就有用了。4.A2-NSGA-III 论文针对A-NSGA-III的四点缺点进行了改进，提出了A2-NSGA-III，四点缺点如下：
1）当问题的最优前沿面很小时，A-NSGA-III扩张操作不能提供足够的参考点使种群分布均匀。
2）扩张操作不适合角点，因为以角点为中心扩张生成的点不在第一象限或出界。
3）由于扩张操作是从第一代开始，种群较分散，离最优前沿面较远，很可能没有足够的时间使种群在各个区域均匀分布而由于额外的扩张点陷入局部最优。
4）只有当所有参考点小生境数为0或1时才开始消除操作，对于高维多目标，由于种群变大，这个条件很难达到。
改进措施：选取参考点为单纯形的一个顶点，而不是中心，且边长减半，而且这样可以有三种外形，如图14所示。
图14 改进单纯形扩展法
当添加一个外形后，还有小生境数大于1的，采用另一个外形，直到所有M个外形都采用，如果还有，则单纯形的边长再取半，直到小生境数为0。在一个外形加入之前，需要进行检查：1.如果外形的点超出边界是不被接受，比如上图Q点，外形1、3是不被接受的。2.如果外形的点在参考点中存在，也是不被接受。
这样的扩张操作引入了更多的单纯形，能缓解第一个缺点；以参考点为顶点半边长的单纯形适用于定点，比如Q点，缓解了第二个缺点；只有当原始的参考点小生境数在过去的10代稳定在一个定值，则扩张的点才被接受，这样能克服第三个缺点；只要参考点总数达到原始参看点个数的10倍，消除操作就开始，这样能克服第四个缺点。
（七）MOEA/D-M2M MOEA/D-M2M是将高维多目标问题分解为多个简单的多目标优化子问题，通过协同方式解决这些子问题，每个子问题对应一个子种群，通过这种方式种群多样性得到维护。它是针对MOEA/D的存在的两个缺点进行的改进。
MOEA/D有两个缺点：
1）一个新个体不该完全根据聚合函数值取代旧个体，因为在有些情况下，这样完全取代会导致种群多样性的丢失。
2）对于不同的问题，MOEA/D总是需要设置合适的聚合方法和权重向量，而这个在解决问题之前是很困难的。
均匀生成K个单位方向向量，将目标空间划分为K个子区间，通过计算N个种群个体所在方向与K个单方方向的夹角，将n个个体划分到k个区域里。这样基于方向向量分解目标空间有两个好处：
1）每个子区域的局部最优前沿面可以组成整个最优前沿面。2）即使整个区域的最优前沿面是非线性几何形状（不规则），经过分解，各个子区域只是整个区域的一小部分，所以最优前沿面在子区域内可以很接近线性形状。而求解线性形状的最优前沿面比非线性几何形状简单得多。
（八）-DEA算法 1.算法简介
近期进化算法上有人基于NSGA3提出一种基于新型支配关系支配的高维多目标优化算法-DEA，它通过引入分解算法MOEA/D中的PBI聚合函数来提高NSGA3的收敛性。出发点是整合NSGA-III 和MOEA/D，达到优势互补。通过分析，文章作者得出：
1）NSGA-III 强调的是个体中靠近参考线的Pareto非支配解，然而目标维数增大时，会导致非支配解个数也急剧增多，基于pareto支配关系的NSGA-III 将缺乏足够的选择压力去促使种群向最优PF面进化，事实上NSGA-III 过多的侧重于多样性而导致收敛性不足。
2）MOEA/D通过基于聚合函数的选择操作能很好地逼近最优PF面，在高维情况下收敛性也很好，而多样性试图通过设置均匀分布的权重向量来维护，低维可以到达目的，但是在高维情况下就不适用了，因为在高维空间中，一个具有很好聚合函数值的解有可能离相应的权重向量很远，那么多样性就会缺失。
综上所诉，NSGA-III收敛性不足，MOEA/D多样性缺失，因此作者通过引入MOEA/D的聚合函数来提高NSGA-III的收敛性，而继承NSGA-III优良的多样性。
2.算法步骤
St1）合并父代种群Pt和子代种群Qt，组成Rt，对Rt进行非支配排序，i1Fi，其中Fi表示第i层pareto前沿，满足i1FiN,i1FiN
2）以N个权重向量为聚类中心，将St中的个体聚类到各个权重向量附近（各个权重向量附近个体数是不一样的），然后通过支配关系对每一个类内个体划分等级。这里所说的支配也就是MOEA/D中的PBI聚合函数，如图15所示。
1图15 PBI聚合函数示意图
其中，d1越小，代表x解的收敛性越好；d2越小说明越靠近权重向量，多样性越好。
综合这两者表示一个解的优劣，可以令Fj(x)dj,1(x)dj,2(x)，如果Fj(x)Fj(y)，我们就说x支配y，其中是惩罚系数，实验仿真取5（对5作解释）
说明一下，这里通过支配关系对每一个类内个体划分等级，其实每一个等级上只有一个解，因为Fj(x)是一个可以比较大小的数值。
3）以此取每一个类里的第一等级，第二等级，以此类推，直到选择最后一个等级，他加入的话大于N，不加入就少于N，然后随机的在这一等级里选取个体满足数量N。3.思考
1）对-DEA的改进，在第三步中，是随机的在最后一等级里选择，而我的想法是定向的选择类内个体数少的那一类的最后等级个体，能够进一步提高多样性。
2）NSGA-III在多样性维护阶段只是依靠d2来选择个体，会导致收敛性不足，而-DEA在考虑多样性d2的同时稍微考虑一点收敛性d1，根据这一点我对自己的多个子种群进化算法做了进一步改进，将子种群中由以前只依靠d2选择个体变为d1+5d2。
3）NSGA-III和-DEA都是先进行非支配排序后聚类，不同的是NSGA-III通过评估每一个类里的小生境数选择小生境数少的类内个体，而-DEA是通过支配循环选择每一类个体，因此我可以将我的子种群的NSGA-III模式改为-DEA模式。参考文献
[1] R.C.Purshouse, P.J.Fleming.On the Evolutionary Optimization of Many Conflicting Objectives.Evolutionary Computation, IEEE Transactions on.2007, 11(6): 770-784 [2] 孔维健, 丁进良, 柴天佑.高维多目标进化算法研究综述.控制与决策.2010(03): 321-326 [3] 巩敦卫, 季新芳, 孙晓燕.基于集合的高维多目标优化问题的进化算法.电子学报.2014(01): 77-83 [4] E.Hughes.Radar Waveform Optimisation as a Many-Objective Application Benchmark.In: Evolutionary Multi-Criterion Optimization--S.Obayashi, K.Deb, C.Poloni, T.Hiroyasu, T.Murata, eds.: Springer Berlin Heidelberg, 2007: 700-714 [5] A.Sülflow, N.Drechsler, R.Drechsler.Robust Multi-Objective Optimization in High Dimensional Spaces.In: Evolutionary multi-criterion optimization: Springer, 2007: 715-726 [6] R.Lygoe, M.Cary, P.Fleming.A Real-World Application of a Many-Objective Optimisation Complexity Reduction Process.In: Evolutionary Multi-Criterion Optimization--R.Purshouse, P.Fleming, C.Fonseca, S.Greco, J.Shaw, eds.: Springer Berlin Heidelberg, 2013: 641-655 [7] K.Deb, A.Pratap, S.Agarwal, T.Meyarivan.A Fast and Elitist Multiobjective Genetic Algorithm: Nsga-Ii.Evolutionary Computation, IEEE Transactions on.2002, 6(2): 182-197 [8] E.Zitzler, M.Laumanns, L.Thiele.Spea2: Improving the Strength Pareto Evolutionary Algorithm.TIK, Swiss Federal Institute of Technology(ETH.2001 [9] D.W.Corne, N.R.Jerram, J.D.Knowles, M.J.Oates, J.Martin.Pesa-Ii: Region-Based Selection in Evolutionary Multiobjective Optimization.In: Proceedings of the Genetic and Evolutionary Computation Conference(GECCO’2001, 2001: 283--290 [10] 陈小红, 李霞, 王娜.高维多目标优化中基于稀疏特征选择的目标降维方法.电子学报.2015(07): 1300-1307 [11] H.Ishibuchi, N.Tsukamoto, Y.Nojima.Evolutionary Many-Objective Optimization: A Short Review.In: Evolutionary Computation, 2008.CEC 2008.(IEEE World Congress on Computational Intelligence).IEEE Congress on, 2008: 2419-2426 [12] K.Deb, M.Mohan, S.Mishra.Evaluating the ϵ-Domination Based Multi-Objective Evolutionary Algorithm for a Quick Computation of Pareto-Optimal Solutions.Evolutionary Computation.2005, 13(4): 501-525 [13] H.Sato, H.Aguirre, K.Tanaka.Controlling Dominance Area of Solutions and Its Impact on the Performance of Moeas.In: Evolutionary Multi-Criterion Optimization--S.Obayashi, K.Deb, C.Poloni, T.Hiroyasu, T.Murata, eds.: Springer Berlin Heidelberg, 2007: 5-20 [14] Y.Shengxiang, L.Miqing, L.Xiaohui, Z.Jinhua.A Grid-Based Evolutionary Algorithm for Many-Objective Optimization.Evolutionary Computation, IEEE Transactions on.2013, 17(5): 721-736 [15] Z.He, G.G.Yen, J.Zhang.Fuzzy-Based Pareto Optimality for Many-Objective Evolutionary Algorithms.Evolutionary Computation, IEEE Transactions on.2014, 18(2): 269-285 [16] 毕晓君, 张永建, 陈春雨.基于模糊支配的高维多目标进化算法mfea.电子学报.2014(08): 1653-1659 [17] A.Jaimes, L.Quintero, C.C.Coello.Ranking Methods in Many-Objective Evolutionary Algorithms.In: Nature-Inspired Algorithms for Optimisation--R.Chiong, ed.: Springer Berlin Heidelberg, 2009: 413-434 [18] Z.Xiufen, C.Yu, L.Minzhong, K.Lishan.A New Evolutionary Algorithm for Solving Many-Objective Optimization Problems.Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on.2008, 38(5): 1402-1412 [19] E.Carreno Jara.Multi-Objective Optimization by Using Evolutionary Algorithms: The Src=“/Images/Tex/387.Gif” Alt=“P”>
第二篇：基于测速雷达的多目标检测算法[推荐]
基于测速雷达的多目标检测算法
（合肥工业大学计算机与信息学院，安徽合肥 20009）
摘要：近些年了来随着科技的进步、人们生活水平的提高，为满足生产和生活的需求各种交通工具应用而生。车型和车速的不断提高给道路交通管制带来了许多的不便和麻烦，因此基于交通测速雷达的多目标分辨领域的研究至关重要，能更好的对道路交通进行管理，在跟踪目标，对超速车辆的查找以及统计各类型车辆数量、缓解交通压力等方面有很大的用途。
本文在多普勒雷达的基础上研究发展而来的基于测速雷达的多目标分辨算法。首先介绍了雷达测速的研究背景及意义，多普勒雷达的测速原理，目前的发展状况以及传统雷达的不足之处。接着介绍了多目标分辨的理论依据，也就是本论文主要讲解的超速雷达的多目标分辨。
关键词:多普勒雷达、多目标分辨、频谱分析、幅度比较
一、研究背景
21世纪以来，人类生产力大解放。科技的蓬勃发展，工业革命的不断推进，无论是生产还是生活人类发生了翻天覆地的变化。其中最明显的便是交通运输工具的变化。随着道路基础设施建设水平的提高，人们生活质量的提高促使家庭小汽车的不断增加，同时为满足生产力发展的需求，各种交通工具应用而生。公路交通运输业是推动国民经济发展，促进经济社会繁荣的主动力。为实现对道路交通的有效管制以及行车速度测量及对超速车辆的实时监测控制对道路上的多目标进行分辨至关重要。
从雷达早期出现用于对空中金属物体的探测，到二战以来出现的雷达对空对地的火力控制等，雷达主要应用于军事领域。随着科技的进步，雷达技术的不断发展，雷达不再是一种单纯的军事雷达，其应用领域不断增加，功能不断增强出现了各种各样的雷达，比如气象雷达，道路交通测速雷达等。雷达测速是利用多普勒效应，通过多普勒频移计算目标的速度。雷达测速因其准确性高，速度快，稳定性好，探测距离远，可移动测速，能更好的抑制地无干扰等优点，得到广泛应用，但是由于雷达波束较宽，在多车并行行驶时，无法分辨出超速车辆，给监测控制带来了困难。国内现有超速测量抓拍系统在多车并行时，由于仅能检测出有车辆超速，无法分辨超速车辆，为避免误判只能放弃抓拍，无形中增加了交通事故隐患，严重影响了现代交通的严格法制化管理进程。因此多目标分辨雷达的研究和制造有着非常重要的作用。同时不仅可应用于超速雷达的探测，在对车型检测，缓解交通压力等方面都发挥很大的作用。
二、交通测速雷达发展状况
目前，美国联邦电讯委员会规定警用测速频道为Xband，Kband，Kaband三种，它们对应的微波频率分别为10.525GHZ，24.150GHZ,33.40-36.00GZH。Xband雷达形状为圆型，无法在车阵中锁定超速车辆只能在车阵中检测第一辆车的速度。K band测速雷达为手持式的雷达，国内警方绝大多数使用这种雷达。Ka band雷达与K band雷达相似，由于其微波频率更高，测速范围更加集中，所以不容易被干扰，目前国内基本局限于一般性测量且测量结果较粗糙，在先进技术方面还有很大差距，因此对多目标分辨的研究至关重要，对提高国内雷达水平，方便道路超速车辆管理有重要的作用。
三、多普勒雷达的作用原理
多普勒雷达，又名脉冲多普勒雷达，是一种利用多普勒效应来探测运动目标的位置和相对运动速度的雷达。1842年,奥地利物理学家J·C·多普勒发现,当波源和观测者有相对运动时,观测者接受到的波的频率和波源发来的频率不同,这种现象被称为多普勒效应。波是由频率和振幅所构成，而无线电波是随着物体而移动的，当无线电波在行进的过程中，碰到物体时，该无线电波会被反弹，而且其反弹回来的波，其频率及振幅都会随着所碰到的物体的移动状态而改变。若无线电波所碰到的物体时是固定不动的，那么所反弹回来的无线电波其频率是不会改变的。然而，若物体朝着无线电线发射的方向前进时，此时所反弹回来的无线电波会被压缩，因此该电波的频率会随之增加；反之，若物体是朝着远离无线电波方向行进时，则反弹回来的无线电波，其频率则会随之减小。
多普勒测速原理图
设雷达与动物体之间的距离为s，则雷达电磁波在到达目标并返回的双层路径中，波长为λ的波数为2s/λ，每个波长对应2π rad的相位变化，双程传播路径总相位变化为φ=4πs/λ。如果目标相对与雷达运动，雷达与运动物体目标的距离s和相位变化都会随时间而变化，对上式求导，可得角频率Wd=dφ/dt=4πv/λ=2πFd。其中v=ds/dt为物体目标径向速度。Fd为多普勒频移。所以Fd=2v/λ=2vf/C，其中f=C/λ是雷达发射电磁波频率。利用多普勒频移产生的拍现象可把运动目标的回波从杂波中分离出来。
四、基于幅度比较的多目标分辨方法
多普勒测速雷达因其测速精度高，速度快，稳定性好，探测距离远，可移动等优点，得到广泛应用，但是由于雷达波束较宽，在多车并行行驶时，无法分辨出超速车辆，给违章抓拍带来了困难，因此可以使用基于幅度比较的多目标分辨方法。
基于幅度比较的多目标分辨方法是通过比较回波幅度分辨并行行驶车辆中的超速车辆的方法。该方法利用雷达天线波束增益和角度的关系，结合雷达作用距离与回波功率的关系，通过对不同车道上雷达接收回波的多普勒频率谱幅度值进行分析比较，从而分辨出多车道上并行车辆中的超速车辆。
雷达测速模型：
如图所示基于幅度比较的多普勒测速雷达的模型图。雷达工作频率 24GHz，λ=1.25cm，天线口径D=5cm，3dB波束宽度θ=λ/D=0.25rad=14.3。雷达有效作用距离大约为30m，此时波束的方位宽度达到d=θ*R=7.5m，单车道宽度大约为3m，此时单个雷达波束可以覆盖2～3个车道，可以同时检测到多个运动目标。但无法分辨每辆车的速度。该方法模型采用同源多天线结构，即天线发射的雷达信号来自同一个源，再由功分器均分形成。测速雷达分别安装在车道中央通过几部天线测出的多普勒频移正的幅度差异来判断超速车辆所处的车道。测速雷达的工作原理是：雷达向目标发射电磁波并接收回波信号，从回波中提取速度对应的多普勒频率，进而求出运动目标的速度。
以雷达发射连续波的情况为例，其发射信号可以表示为： S0(t)=Asin(2πf0t+φ0)式中，A为振幅，fo为雷达的发射频率，φ0为初相。
按照图所示测速模型，雷达1接收到的有：carl反射的雷达1的回波，carl反射的雷达2的回波，car2反射的雷达l的回波和car2反射的雷达2的回波四个信号。由于雷达位置的不同，虽然发射的是相同的信号，但是carl相对与雷达2的径向速度为：V21=V11*cosθ，不同于相对与雷达1的径向速度，因此多普勒频率分量也不相同，car2的情况同理。同样雷达间的位置差异也决定了距离因子和回波衰减系数的不同。
假设左右两车道雷达接收到的由两个运动目标反射的回波信号分别为Sr1(f)和Sr2(f)，建立回波：
式中，αij为雷达波束方向影响因子；rij为目标j相对于雷达i的距离因子；fij=2Vijf0/C，为运动目标的多普勒频移，其中，Vij代表目标j相对于雷达i的运动速度，c代表电磁波的传播速度。
fd11和fd21分别是目标1相对于两个雷达的多普勒频率，fd12和fd22分别是目标2相对于两个雷达的多普勒频率。设△fd1和△fd2为目标1和目标2相对于两个雷达的多普勒频差：
△fd1=fd11-fd21 △fd2=fd12-fd22 将上式化简为如下两式：
回波信号与本振信号进行自混频得到差频信号S1(t)和S2(t):
（k1=r1α为幅度增益系数）
从差频信号中提取多普勒频率，可由多普勒原理计算出目标的运动速度：
v=fd*c/2f0
雷达回波信号信号功率谱分析
当右车道有车辆行驶时，左右两路雷达会分别接收到该车辆的回波信号，由于位置的差异，所接收的多普勒频率分量和能量值均不相同。显而易见，在相对距离较近，且处于主瓣中心位置的能量最大，即对于右车道的车辆而言，右路雷达接收到的右车道行驶车辆的多普勒频率分量的能量就要大于左路雷达所接收到的右车道行驶车辆的多普勒频率分量的能量。如果对两路雷达在该多普勒频率下的能量值做一个差值比较：
P2(fd2)-P1(fd1)=a 当a>0时，多普勒频移为fd2的车在右车道；当a<0时，多普勒频移为fd1的车在左车道。当两车道都有车辆行驶时，两个雷达会分别接收到两车道上行驶车辆的回波信号，由于位置的差异，所接收的多普勒频率分量和其能量值均不相同。此时先判断是否有超速车辆，再判断是否同时超速：如果仅有一辆车超速，对多普勒频率值最大的分量作比较，判断超速车辆所处的位置；如果两辆车同时超速，则直接记录然后进行后续处理。以上就是基于测速雷达的多目标分辨算法。
五、总结
随着中国道路交通的不断发展涌现出各种各样的问题，超速行驶在各种违章中占了很大比例，因此对超速行驶车辆的检测和加大力度的惩罚措施至关重要。而对超速行驶的汽车的鉴定便需要对汽车进行分辨识别，本文便是这个研究方向的一些理论依据。
通过这次的学习，我更加清楚地认识到了多普勒雷达的作用原理，同时基于多普勒原理而衍生出来的超速车辆的分辨研究也有了一定的认识和学习，对雷达在道路交通中的应用更加了解，增强了自己对雷达技术研究的兴趣，收获很多。
参考文献
[1]林仲扬漫谈雷达测速江苏省计量测试技术研究所江苏南京 2006 [2]刘哲交通测速雷达的检测及技术改进分析云南大学2008 [3] 陈卓交通检测雷达的多目标分辨算法研究西安电子科技大 [4] 李艳雷达多目标分辨方法研究国防科技大学 2005 [5] 杨粤湘雷达测速在公安交通管理中的应用广东公安科技
2005 [6]周高杯多运动目标的频谱分析及基于DSP的雷达测速仪的设计湖南大学，2005 [7] 孙超脉冲多普勒雷达测速关键问题研究西安电子科技大学 2014 [8] 孙朝云，阳红，高怀刚 交通测速雷达性能分析与改善《长安大学学报:自然科学版》 2003
第三篇：算法总结
算法分析与设计总结报告
71110415 钱玉明
在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。
下面我将谈谈我对这门课程的心得与体会。
一、数学是算法的基础
经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。
①主定理
本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。
②随机算法中的许多定理的运用
在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。
这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。
二、算法的核心是思想
我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。
①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。
动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。
贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。
周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。
回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。
分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。
②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。
这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。
三、算法与应用紧密相关
我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。
这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。
四、对计算模型和NP问题的理解
由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。
首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。
NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。
最后谈谈对这门课程的建议
①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。
②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。
③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。
第四篇：算法总结
算法分块总结
为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法设计中，时刻都要牢记要减少冗余，要以简洁高效为追求目标。另外当遇到陌生的问题时，要想方设法进行模型简化，转化，转化成我们熟悉的东西。
图论模型的应用
分层图思想的应用：
用此思想可以建立起更简洁、严谨的数学模型，进而很容易得到有效算法。重要的是，新建立的图有一些很好的性质： 由于层是由复制得到的，所以所有层都非常相似，以至于我们只要在逻辑上分出层的概念即可，根本不用在程序中进行新层的存储，甚至几乎不需要花时间去处理。由于层之间的相似性，很多计算结果都是相同的。所以我们只需对这些计算进行一次，把结果存起来，而不需要反复计算。如此看来，虽然看起来图变大了，但实际上问题的规模并没有变大。层之间是拓扑有序的。这也就意味着在层之间可以很容易实现递推等处理，为发现有效算法打下了良好的基础。
这些特点说明这个分层图思想还是很有潜力的，尤其是各层有很多公共计算结果这一点，有可能大大消除冗余计算，进而降低算法时间复杂度。二分图最大及完备匹配的应用： ZOJ place the robots: 二分图最优匹配的应用：
最大网络流算法的应用：典型应用就求图的最小割。最小费用最大流的应用：
容量有上下界的最大流的应用：
欧拉路以及欧拉回路的应用：主要利用求欧拉路的套圈算法。最小生成树：
求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。最小K度限制生成树：
抽象成数学模型就是：
设G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。首先考虑边界情况。先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出 现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中 dT(v0)≥m。也就是说，当k 首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量，分别求最小生成树。接着，对于每个连通分量V’，求一点v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，则该连通分量通过边(v1,v0)与v0相连。于是，我们就得到了一个m度限制生成树，不难证明，这就是最小m度限制生成树。这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树，为了解题的简便，把该树转化成以v0为根的有根树。 假设已经得到了最小p度限制生成树，如何求最小p+1 度限制生成树呢？在原先的树中加入一条与v0相关联的边后，必定形成一个环。若想得到一棵p+1 度限制生成树，需删去一条在环上的且与v0无关联的边。删去的边的权值越大，则所得到的生成树的权值和就越小。动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。 状态共|V|个，状态转移的时间复杂度O(1)，所以总的时间复杂度为O(V)。故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。1 先求出最小m度限制生成树； 2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。 加边和去边过程，利用动态规划优化特别值得注意。 次小生成树： 加边和去边很值得注意。 每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。具体做法： 首先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。 最短路径的应用： Dijkstra 算法应用： Folyed 算法应用： Bellman-Ford 算法的应用： 差分约束系统的应用： 搜索算法 搜索对象和搜索顺序的选取最为重要。一些麻烦题，要注意利用数据有序化，要找一个较优的搜索出发点，凡是能用高效算法的地方尽量争取用高效算法。基本的递归回溯深搜，记忆化搜索，注意剪枝： 广搜（BFS）的应用： 枚举思想的应用： ZOJ 1252 island of logic A*算法的应用： IDA*算法的应用，以及跳跃式搜索探索： 限深搜索，限次： 迭代加深搜索： 部分搜索+高效算法（比如二分匹配，动态规划）： ZOJ milk bottle data: 剪枝优化探索： 可行性剪枝，最优性剪枝，调整搜索顺序是常用的优化手段。 动态规划 动态规划最重要的就是状态的选取，以及状态转移方程，另外还要考虑高效的预处理（以便更好更快的实现状态转移）。最常用的思想就是用枚举最后一次操作。 状态压缩DP，又叫带集合的动态规划：题目特点是有一维的维数特别小。类似TSP问题的DP： 状态划分比较困难的题目： 树形DP： 四边形不等式的应用探索：四边形不等式通常应用是把O(n^3)复杂度O(n^2) 高档数据结构的应用 并查集的应用： 巧用并查集中的路径压缩思想： 堆的利用： 线段树的应用： 总结用线段树解题的方法 根据题目要求将一个区间建成线段树，一般的题目都需要对坐标离散。建树时，不要拘泥于线段树这个名字而只将线段建树，只要是表示区间，而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的，都可以建线段树；不要拘泥于一维，根据题目要求可以建立面积树、体积树等等 树的每个节点根据题目所需，设置变量记录要求的值 用树形结构来维护这些变量：如果是求总数，则是左右儿子总数之和加上本节点的总数，如果要求最值，则是左右儿子的最大值再联系本区间。利用每次插入、删除时，都只对O(logL)个节点修改这个特点，在O(logL)的时间内维护修改后相关节点的变量。 在非规则删除操作和大规模修改数据操作中，要灵活的运用子树的收缩与叶子节点的释放，避免重复操作。 Trie的应用：； Trie图的应用探索： 后缀数组的应用研究： 在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。 树状数组的应用探索：； 计算几何 掌握基本算法的实现。凸包的应用：； 半平面交算法的应用：； 几何+模拟类题目：几何设计好算法，模拟控制好精度。扫描法：； 转化法：ZOJ 1606 将求所围的格子数，巧妙的转化为求多边形的面积。离散法思想的应用：； 经典算法：找平面上的最近点对。 贪心 矩形切割 二分思想应用 活用经典算法 利用归并排序算法思想求数列的逆序对数： 利用快速排序算法思想，查询N个数中的第K小数： 博弈问题 博弈类题目通常用三类解法：第一类推结论； 第二类递推，找N位置，P位置； 第三类SG函数的应用。第四类极大极小法，甚至配合上αβ剪枝。最难掌握的就是第四类极大极小法。 第一类：推结论。典型题目： 第二类：递推。典型题目： 比如有向无环图类型的博弈。在一个有向图中，我们把选手I有必胜策略的初始位置称为N位置(Next player winning)，其余的位置被称为P位置(Previous player winning)。很显然，P位置和N位置应该具有如下性质： 1． 所有的结束位置都是P位置。 2． 对于每一个N位置，至少存在一种移动可以将棋子移动到一个P位置。3． 对于每一个P位置，它的每一种移动都会将棋子移到一个N位置。 这样，获胜的策略就是每次都把棋子移动到一个P位置，因为在一个P位置，你的对手只能将棋子移动到一个N位置，然后你总有一种方法再把棋子移动到一个P位置。一直这样移动，最后你一定会将棋子移动到一个结束位置（结束位置是P位置），这时你的对手将无法在移动棋子，你便赢得了胜利。 与此同时，得到了这些性质，我们便很容易通过倒退的方法求出哪些位置是P位置，哪些位置是N位置，具体的算法为： 1． 将所有的结束位置标为P位置。 2． 将所有能一步到达P位置的点标为N位置。 3． 找出所有只能到达N位置的点，将它们标为P位置。 4． 如果在第三步中没有找到新的被标为P位置的点，则算法结束，否则转到步骤2。这样我们便确定了所有位置，对于题目给出的任一初始位置，我们都能够很快确定出是选手I获胜还是选手II获胜了。第三类：SG函数的应用。 关于SG函数的基本知识：对于一个有向图(X, F)来说，SG函数g是一个在X上的函数，并且它返回一个非负整数值，具体定义为 g(x)min{n0,ng(y)对于所有yF(x)} 1． 对于所有的结束位置x，g(x)= 0。 2． 对于每一个g(x)≠ 0的位置x，在它可以一步到达的位置中至少存在一个位置y使得g(y)= 0。 3．对于每一个g(x)＝ 0的位置x，所有可以由它一步到达的位置y都有g(y)≠ 0。 定理 如果g(xi)是第i个有向图的SG函数值，i = 1,…,n，那么在由这n个有向图组成的状态的SG函数值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四类：极大极小法。 典型题目：ZOJ 1155：Triangle War ZOJ 1993：A Number Game 矩阵妙用 矩阵最基本的妙用就是利用快速乘法O（logn）来求解递推关系（最基本的就是求Fibonacci数列的某项）和各种图形变换，以及利用高斯消元法变成阶梯矩阵。典型题目： 数学模型举例 向量思想的应用： UVA 10089：注意降维和向量的规范化 ； 利用复数思想进行向量旋转。 UVA 10253： 递推 数代集合 数代集合的思想： ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一题：Intuitionistic Logic 用枚举+数代集合思想优化，注意到题中有一句话：“You may assume that the number H = |H| of elements of Hdoesn't exceed 100”，这句话告诉我们H的元素个数不会超过100，因此可以考虑用一个数代替一个集合，首先把所有的运算结果都用预处理算出来，到计算的时候只要用O(1)的复杂度就可以完成一次运算。 组合数学 Polya定理则是解决同构染色计数问题的有力工具。 补集转化思想 ZOJ 单色三角形： 字符串相关 扩展的KMP算法应用：；最长回文串； 最长公共子串； 最长公共前缀； 填充问题 高精度运算 三维空间问题专题 无论什么问题，一旦扩展到三难空间，就变得很有难度了。三维空间的问题，很考代码实现能力。 其它问题的心得 解决一些判断同构问题的方法：同构的关键在于一一对应，而如果枚举一一对应的关系，时间复杂度相当的高，利用最小表示，就能把一个事物的本质表示出来。求最小表示时，我们一定要仔细分析，将一切能区分两个元素的条件都在最小表示中体现，而且又不能主观的加上其他条件。得到最小表示后，我们往往还要寻求适当的、高效的匹配算法（例如KMP字符匹配之类的），来比较最小表示是否相同，这里常常要将我们熟悉的高效算法进行推广 源程序代码： } 一、自然数拆分（递归） } #include 二、快速排序（递归）int a[100];void spilt(int t)#include spilt(j+1);} } int partitions(int a[],int from,int to)void main(){ { int n,i; int value=a[from];printf(“please enter the number:”); while(from a[from]=a[to]; while(from ++from; a[to]=a[from]; } a[from]=value; return from; } void qsort(int a[],int from,int to){ int pivottag;if(from {pivottag=partitions(a,from,to);qsort(a,from,pivottag-1);qsort(a,pivottag+1,to); } scanf(“%d”,&n); for(i=1;i<=n/2;i++){ a[1]=i;a[2]=n-i;spilt(2); 三、删数字（贪心） #include int a[11]={3,0,0,0,9,8,1,4,7,5,1}; int k=0,i=0,j; int m; while(i<11) { printf(“%d ”,a[i]); i++;} printf(“n please input delete number:”); 四、全排列（递归）#include int i;char temp;if(k==n) for(i=0;i<=3;i++) {printf(“%c ”,a[i]);} else { for(i=k;i<=n;i++) { temp=a[i]; a[i]=a[k]; a[k]=temp; A(a,k+1,n); } } } main(){ int n; char a[4]={'a','b','c','d'},temp; A(a,0,3); getch(); return 0;} 五、多段图（动态规划）#include “stdio.h” #define n 12 //图的顶点数 { while(from scanf(“%d”,&m);for(k=0;k { for(i=0;i<=11-k;i++) { if(a[i]>a[i+1]) { for(j=i;j<10;j++) {a[j]=a[j+1];} break;//满足条件就跳转 } } } int quicksort(int a[],int n){ qsort(a,0,n);} } printf(“the change numbers:”); for(i=0;i<11-m;i++) { if(a[i]!=0) { printf(“%d ”,a[i]);} } } #define k 4 //图的段数 #define MAX 23767 int cost[n][n];//成本值数组 int path[k];//存储最短路径的数组 void creatgraph()//创建图的(成本)邻接矩阵 { int i,j; for(i=0;i for(j=0;j scanf(“%d”,&cost[i][j]);//获取成本矩阵数据 } void printgraph()//输出图的成本矩阵 { int i,j; printf(“成本矩阵:n”); for(i=0;i { for(j=0;j printf(“%d ”,cost[i][j]); printf(“n”); } } //使用向前递推算法求多段图的最短路径 void FrontPath(){ int i,j,length,temp,v[n],d[n]; for(i=0;i v[i]=0;for(i=n-2;i>=0;i--){ for(length=MAX,j=i+1;j<=n-1;j++) if(cost[i][j]>0 &&(cost[i][j])+v[j] {length=cost[i][j]+v[j];temp=j;} v[i]=length; d[i]=temp; } path[0]=0;//起点 path[k-1]=n-1;//最后的目标 for(i=1;i<=k-2;i++)(path[i])=d[path[i-1]];//将最短路径存入数组中 } //使用向后递推算法求多段图的最短路径 void BackPath(){ int i,j,length,temp,v[n],d[n]; for(i=0;i for(i=1;i<=n-1;i++) { for(length=MAX,j=i-1;j>=0;j--) if(cost[j][i]>0 &&(cost[j][i])+v[j] {length=cost[j][i]+v[j];temp=j;} v[i]=length; d[i]=temp; } path[0]=0; path[k-1]=n-1; for(i=k-2;i>=1;i--)(path[i])=d[path[i+1]];} //输出最短路径序列 void printpath(){ int i; for(i=0;i printf(“%d ”,path[i]);} main(){ freopen(“E:1input.txt”,“r”,stdin); creatgraph(); printgraph(); FrontPath(); printf(“输出使用向前递推算法所得的最短路径:n”); printpath(); printf(“n输出使用向后递推算法所得的最短路径:n”); BackPath(); printpath();printf(“n”);} 六、背包问题（递归）int knap(int m, int n){ int x; x=m-mn; if x>0 sign=1; else if x==0 sign=0; else sign=-1; switch(sign){ case 0: knap=1;break; case 1: if(n>1) if knap(m-mn,n-1) knap=1; else knap= knap(m,n-1); else knap=0; case-1: if(n>1) knap= knap(m,n-1); else knap=0; } } 七、8皇后（回溯）#include int i; i=1; while(i if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k))) return 0; i++; } return 1;} void Nqueens(int X[N+1]){ int k, i; X[1]=0;k=1; while(k>0){ X[k]=X[k]+1; while((X[k]<=N)&&(!place(k,X))) X[k]=X[k]+1; if(X[k]<=N) if(k==N){ for(i=1;i<=N;i++) printf(“%3d”,X[i]);printf(“n”); } else{ k=k+1; X[k]=0; } else k=k-1; } } void main(){ int n, i; int X[N+1]={0}; clrscr(); Nqueens(X); printf(“The end!”);} 八、图着色（回溯）#include int j,t; while(1){ nextValue(k); if(X[k]==0) return 0; if(k==(N-1)){ for(t=0;t printf(“%3d”,X[t]); printf(“n”); count++; } else mcoloring(k+1); } } int nextValue(int k){ int j; while(1){ X[k]=(X[k]+1)%(M+1); if(X[k]==0) return 0; for(j=0;j if((GRAPH[k][j]==1)&&(X[k]==X[j])) break; } if(j==N){ return 0; } } } void main(){ int k; clrscr(); k=0; mcoloring(k); printf(“ncount=%dn”,count);} 矩阵链乘法（动态规划） 符号S[i, j]的意义： 符号S(i, j)表示，使得下列公式右边取最小值的那个k值 public static void matrixChain(int [ ] p, int [ ][ ] m, int [ ][ ] s) { int n=p.length-1; for(int i = 1;i <= n;i++)m[i][i] = 0; for(int r = 2;r <= n;r++) for(int i = 1;i <= n-r+1;i++){ int j=i+r-1; m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; s[i][j] = i; for(int k = i+1;k < j;k++){ int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if(t < m[i][j]){ m[i][j] = t; s[i][j] = k;} } } } O的定义： 如果存在两个正常数c和n0，对于所有的n≥n0时，有： |f(n)|≤c|g(n)|，称函数f(n)当n充分大时的阶比g(n)低，记为 f(n)=O(g(n))。计算时间f(n)的一个上界函数 Ω的定义： 如果存在正常数c和n0，对于所有n≥n0时，有： |f(n)|≥c|g(n)|，则称函数f(n)当n充分大时下有界，且g(n)是它的一个下界，即f(n)的阶不低于g(n)的阶。记为： f(n)=Ω(g(n))。Θ的定义： 如果存在正常数c1，c2和n0，对于所有的n>n0，有： c1|g(n)|≤f(n)≤c2|g(n)|，则记f(n)=Θ(g(n))意味着该算法在最好和最坏的情况下计算时间就一个常因子范围内而言是相同的。(1)多项式时间算法： O(1) (2)指数时间算法： O(2n) Move(n,n+1)(2n+1,2n+2)move(2n-1,2n)(n,n+1)call chess(n-1) 贪心方法基本思想： 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择 所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 多段图： COST[j]=c(j,r)+COST[r]; 回溯法： (假定集合Si的大小是mi)不断地用修改过的规范函数Pi(x1,…,xi)去测试正在构造中的n-元组的部分向量(x1,…,xi)，看其是否可能导致最优解。如果判定(x1,…,xi)不可能导致最优解，那么就将可能要测试的mi+1…mn个向量略去。约束条件： (1)显式约束：限定每一个xi只能从给定的集合Si上取值。 (2)解 空 间：对于问题的一个实例，解向量满足显式 约束条件的所有多元组，构成了该实例 的一个解空间。 (3)隐式约束：规定解空间中实际上满足规范函数的元 组，描述了xi必须彼此相关的情况。基本做法： 在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 8皇后问题 约束条件 限界函数： 子集和数问题： 约束条件 限界函数： 回溯法－－术语： 活结点：已生成一个结点而它的所有儿子结点还没有 全部生成的结点称为活结点。 E-结点：当前正在生成其儿子结点的活结点叫E-结点。 死结点：不再进一步扩展或其儿子结点已全部生成的结点称为死结点。 使用限界函数的深度优先节点生成的方法成为回溯法；E-结点一直保持到死为止的状态生成的方法 称之为分支限界方法 且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。区别： 分支限界法本质上就是含有剪枝的回溯法，根据递归的条件不同，是有不同的时间复杂度的。 回溯法深度优先搜索堆栈或节点的所有子节点被遍历后才被从栈中弹出找出满足约束条件的所有解 分支限界法广度优先或最小消耗优先搜索队列，优先队列每个结点只有一次成为活结点的机会找出满足约束条件下的一个解或特定意义下的最优解 一般如果只考虑时间复杂度二者都是指数级别的 可是因为分支限界法存在着各种剪枝，用起来时间还是很快的int M, W[10],X[10];void sumofsub(int s, int k, int r){ int j; X[k]=1; if(s+W[k]==M){ for(j=1;j<=k;j++) printf(“%d ”,X[j]); printf(“n”); } else if((s+W[k]+W[k+1])<=M){ sumofsub(s+W[k],k+1,r-W[k]); } if((s+r-W[k]>=M)&&(s+W[k+1]<=M)){ X[k]=0; sumofsub(s,k+1,r-W[k]); } } void main(){ M=30; W[1]=15; W[2]=9; W[3]=8; W[4]=7; W[5]=6; W[6]=5; W[7]=4; W[8]=3; W[9]=2; W[10]=1; sumofsub(0,1,60);} P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合 如果可满足星月化为一个问题L，则此问题L是NP-难度的。如果L是NP难度的且L NP，则此问题是NP-完全的第五篇：算法总结材料
点击咨询 