组合推荐算法（精选7篇）
组合推荐算法 篇1
摘要：协同过滤算法是电子商务系统中一种重要的个性化推荐技术之一。但是随着电子商务规模的扩大,评分矩阵的稀疏性问题严重的影响了协同过滤算法的推荐效果。该文通过分析并研究了传统的协同过滤算法的不足,提出了一种新的基于用户和项目组合的协同过滤算法,在对稀疏矩阵进行填充时,不仅考虑到了项目之间的相关性,还考虑到了用户之间的相关性,然后在此基础上,构造虚拟的评分矩阵,最后再进行综合推荐。实验结果表明,在评分矩阵极其稀疏的情况下,该算法能有效的提高预测精度。
关键词：协同过滤,数据稀疏性,个性化推荐
随着互联网技术的迅速发展,个性化推荐技术日益成为目前的研究热点之一。个性化推荐技术主要包括基于规则的技术,基于内容过滤技术,协同过滤技术,混合推荐技术和基于用户-产品二部图网络结构的推荐技术[1]等,其中协同过滤技术是当前应用在电子商务网站(如Amazon.com)中最成功且最广泛的推荐技术。但是,随着业务规模的不断扩大,稀疏性问题严重的影响了推荐效果[2]。本文通过分析了传统的协同过滤算法[3,4],提出了一种基于用户和项目组合预测评分的协同过滤推荐算法。实验表明,相比于传统的协同过滤算法,本文的算法进一步的提高了算法的推荐精确度。
1 相关工作的分析
1.1 协同过滤算法的概述
协同过滤又称之为社会过滤,它是基于这样的假设:如果用户对一些项目的评分比较相似,则他们对其他项目的评分也比较相似。目前主要分为两大类[5]:基于内存的算法和基于模型的算法。
1.2 协同过滤算法的步骤
协同过滤算法大致可以分为以下三个步骤[3]:收集可以代表用户兴趣的信息,最近邻居搜索,产生推荐集。
1)收集可以代表用户兴趣的信息。收集用户兴趣的方式通常有显式和隐式两种:显式的方式主要有用户打分或者评价等形式,通过用户直接参与的方式;隐式的方式主要是根据用户的行为由系统代替评价,如购买商品记录和页面浏览记录等。然后根据收集的信息形成一个用户项目评分矩阵。一般评分越高,说明用户对其兴趣越大。
2)最近邻居搜索。所谓最近邻居,就是指与目标用户兴趣相似的一组用户。搜索最近邻居主要是计算目标用户与各个用户的相似度,寻找相似度较高的作为最近邻居。目前比较常用的相似度计算方法有余弦相似性(式1)、相关相似性(式2)以及修正的余弦相似性(式3)。在式中,sim(i,j)代表i,j之间的相似度,在基于项目的算法中搜索最近邻时,指的是项目之间的相似度,本文主要是研究的基于用户的算法的改进,因此在本文指的是用户之间的相似度。Ri,c表示用户i对项目c的评分,表示用户i对项目的平均评分,Ii,j表示用户i与用户j共同评分过的项目集。其中式3与式1的区别是,式3考虑了不同用户的评分尺度问题,修正了部分用户夸大评分值的情况。
3)产生推荐集。根据最近邻居集合,采用公式(4)计算用户对任意项的预测评分,生成推荐结果。其中Pa,i表示目标用户a对项目i的预测值,分别表示目标用户a和用户u对项目的平均评分。k为最近邻个数,可以直接给定或通过阈值确定,也可以将二者结合,取相似性大于阈值的用户中的前k个用户。
1.3 协同过滤算法分析
传统的协同过滤算法是直接通过给定的评分矩阵进行计算的,实际上,这个评分矩阵是极其稀疏的。因此,仅依靠用户共同评分的项目来计算相似度,无疑是有一定误差的。针对稀疏性问题,常见的解决方式进行评分矩阵补缺或者结合其他现有的语义分析方法[6]等,常见的补缺方法有一下几种[2,5,7]:
1)均值填补:是将未评分的值设为一个固定的缺省值,一般设为评分制的均值(如5分制,则均值为3,或者是用户的平均评分,或者是项目的平均评分。
2)众数填补:是将用户对项目评分次数最多的评分作为未评分项的评分。
3)聚心填补:是用聚类的质心替代用户没有评价过的项目的评分。
4)组合填补:当相似性大于指定阈值的最近邻S(a)(a为目标用户)与最近邻项目S(i)(i为当前项目)不为空时,将用户的与评分与基于项目的预测评分进行线性组合预测评分,否则将用户a与项目i的平均评分进行线性组合得到预测评分。
尽管上述方法相比与传统的算法,在精度上都有所提高,但是均值填补,众数填补及聚心填补都没有充分考虑到用户和项目之间的关联性,组合填补虽然有了很大的改进,但是算法中的实际阈值,需要经过大量的训练才能在实际系统中使用,因此可扩展性仍然有待于提高。
2 基于用户和项目组合的推荐算法
2.1 推荐策略及原理
针对评分矩阵的稀疏性问题,文献[8]提出了一种虚拟的预测评分模型,然而,虚拟的预测评分模型却忽略了未知用户对于项目的评分,因此本文通过用户和项目组合预测未知评分的方式,填补稀疏矩阵中的所有未评分的项目评分,此过程不但考虑到了项目之间的关联性,也充分考虑了用户之间的关联性,然后对所有评分在进行虚拟预测,此时便考虑到了那些没有评分的用户对项目的评分,使得推荐的精度进一步的有所提高。
2.2 改进的推荐算法
根据上节的分析,改进的推荐算法主要可分为三个步骤,即组合加权的矩阵补缺,虚拟预测评分和综合预测。
1)组合的矩阵补缺组合评分由用户和项目评分两部分构成,考虑到对不同项目评分的用户数不同和不同用户对同一项目的评分值的差异,这里使用平均加权计算评分。具体计算方式如下:
其中,分别表示用户u和项目i的平均评分,Ru,i为组合之后用户u对项目i的评分。
2)虚拟预测评分经过上述矩阵补缺之后,已经得到一个稠密的评分矩阵了,但是此矩阵并不能体现出目标用户与各用户的相似度关系,因此采用文献[8]中的公式(6)继续修正,最终得到一个虚拟的预测评分矩阵。
其中,u∈N,N为最近邻居集,Rau,i表示目标客户a的最近邻居集内的用户u对项目i的预测值,分别表示目标用户a和最近邻居集内用户u的平均评分,sim(u,a)表示目标用户a和邻居集内用户u的相似度。
3)综合预测通过修正的预测评分矩阵,再结合1.2节的公式(4)便可得出推荐集,具体预测公式如下:
3 实验结果及分析
3.1 实验数据集
本实验采用的数据集是协同过滤推荐算法常用的m1标准测试数据集:Movie Lens(http://www.grouplens.org)。其中包括了943位用户对1682部电影的10万条评分记录以及电影所属类别等详细信息。在此数据集中,其稀疏度为1-10000/(1682*943)=0.936953,每个用户至少有20条评分记录,评分值均为1-5的整数,数值越高,表明用户对电影的偏爱度越高。实验数据集进一步的划分为训练集和测试集,在本实验中取80%的评分数据位训练集,即80000条数据,测试集为20000条数据。
3.2 评价标准
评价推荐系统推荐质量的度量标准主要包括统计精度度量方法和决策支持精度度量方法两大类[3,9,10,11]。本文采用的是前者度量方法中的平均误差MAE(Mean Absolute Error)方法,易于理解并能直观的反映推荐质量。MAE越小,则表明算法的评分预测越精确,即推荐质量越好。设推荐集中的项目评分预测值为{p1,p2,…,p N},对应的实际用户评分集合为{q1,q2,…,q N},则MAE定义为:
3.3 实验结果及分析
本文将传统的基于用户的协同过滤推荐算法及文献[8]提出的改进算法和本文提出的算法进行了实验比较。实验采用All bu one协议[12,13,14]的方案,在实验中,计算用户相似度时采用的是1.2节的公式(2),最近邻居个数依次为5,10,15,20,25,30,35,实验结果如图1所示。
实验结果表明,改进的组合预测评分的算法,通过修正评分矩阵之后,预测质量要高于文献[8]提出的算法的预测质量,同时,预测质量也会随着最近邻居的个数变化而变化。但是总的来说,相对于其他两种方法,本文算法随邻居个数变化而变化的趋势不是太大,这主要是因为对矩阵填补后,再进行预测时不会有太大的影响。当最近邻居个数达到20时,与其余两种算法的预测精度接近一致。因此,当评分矩阵极度稀疏时,本文算法在考虑到用户之间的关联性和项目之间的关联性之后,对评分矩阵再次修正得出了较好的推荐结果。
4 结束语
在分析传统的协同过滤算法的基础上,本文提出了一种基于用户和项目组合的协同过滤推荐算法,然后通过修正组合后的预测评分矩阵,得到一个修正的评分矩阵,充分考虑了评分稀疏性因素,使得推荐质量得到了提高。实验结果显示,该算法较传统的协同过滤算法和文献[8]提出的改进算法,提高了预测评分的精确度。未来的工作主要是研究如何能够进一步的减少算法的复杂度,因为在组合计算时,计算量比较大,所以有待于提高,此外,在考虑到计算项目相似度时,还应该考虑到项目的多层次关系,进一步的提高推荐精度。
全部组合算法 篇2
最近认真学习了王建德教授的“基因繁衍”题, 题目的数据量很大, 王教授采用乘法原理来计算, 看起来很是完美, 不过后来手工列出所有组合数据, 验算了一下, 竟然发现结果不吻合。于是去掉了原来的%10000操作, 为的是和手工验算的数据进行对比。当数据量小时, 运算结果则是正确的, 当数据量很大时, 则是错误的。
1.1 原始题目
某种基因按照下述规律繁衍, 即第1秒, 产生基因1号, 该基因可以繁衍其他基因, 之后每隔一秒, 基因1号都可以繁衍出一个新的基因。第m秒繁衍出的基因编号为m, 称它为m号基因 (m>=2) 。m号基因诞生后继续繁衍, 但每隔m秒会休息一次。比如3号基因, 会在第6、9、12, ...秒休息, 而其他时间都处于繁衍期。
基因休息时, 它的记忆会被移植到当时出生的基因中。比如6号基因诞生时, 2号和3号基因正在休息, 因此, 6号基因会收到2号和3号基因的记忆副本。称2号和3号基因是6号基因的父基因。显然, m号基因的父基因是它的质因子。如果两个基因没有父子关系, 且没有共同的父基因, 则成为这两个基因的编号是互质的。注意:1号基因与其他所有基因的编号是互质的 (因为只有1号才会繁衍基因) , 它也不是任何基因的父基因。
一个基因的独立数是指所有编号比它小且与它互质的不同基因的个数。比如1号基因的独立数为0, 2号基因的独立数为1 (1号基因与它互质) , 6号基因的独立数为2. (1号和5号基因与它互质, 2号和3号基因都是它的父基因, 而4号基因与它有共同的父基因---2号基因。)
新繁衍出来的基因有3种不同的类型。对于编号为m的基因, 如果能把m分解成偶数个不同奇素数的积, 则它是第一类基因。例如15号基因 (3*5) ;否则, 如果m本身就是奇素数或者能把m分解成奇数个不同奇素数的积, 则它是第二类基因, 例如3号基因, 165号基因 (3*5*11) 。其他编号的基因都是第三类基因, 例如2号基因、6号基因和9号基因。
第m秒诞生了基因m号, 我们想知道它和它的父基因中, 所有第一类基因的独立数之和, 所有第二类基因的独立数之和, 以及所有第三类基因的独立数之和。能够解决这个问题吗?
为了方便计算, 已经做了m的素因子分解。为了方便输出, 只要求输出总和除以10000的余数。例如, M有3个不同的素因子:第1个素因子为2, 指数为1;第2个素因子为3, 指数为2;第3个素因子为5, 指数为1。显然m=2*3^2*5=90。90号基因有10个父基因, 加上它自己共11个。其中第一类基因只有15号;第二类基因有3号和5号;第三类基因有8个, 它们的编号分别是2、6、9、10、18、30、45和90, 即基因90号和它的父基因中, 所有第一类基因的独立数之和除以10000的余数为8, 所有第二类基因的独立数之和除以10000的余数为6, 所有第三类基因的独立数之和除以10000的余数为75。
输入:第1行是一个正整数k (1<=k<=1000) , k是m的不同的素因子个数。以下k行, 每行两个整数, pi和ei分别表示m的第i个素因子和它的指数 (i=1, 2, ..., k) 。p1, p2, ..., pk是不同的素数, m=p1^e1*p2^e2*...pk^ek。所有素因子按照从小到大排列, 即p1
输出:包括3行, 第1行是基因m号和它的父基因中, 所有第一类基因的独立数之和除以10000的余数;第2行是基因m号和它的父基因中, 所有第二类基因的独立数之和除以10000的余数;第3行市基因m号和它的父基因中, 所有第三类基因的独立数之和除以10000的余数。
1.2 解题思路
用组合数学的方法解此题。
(1) n的独立数是欧拉函数f (n) 的一个特例
一个数n的欧拉函数f (n) 指小于n且与n互质的数的个数。将n分解成素数的乘积n=p1^e1*p2^e2...*pk^ek。f (n) = (p1-1) *p1^ (e1-1) * (p2-1) *p2^ (e2-1) ...* (pk-1) *pk^ (ek-1) 。所谓一个数n的独立数是欧拉函数f (n) 的一个特例, 指小于n且与n互质的不同数的个数。
将n分解成不同素数的乘积n=p1p2...pk, 即欧拉函数f (n) 中e1=e2=...=ek=1, p1!=p2...!=pk, 因此f (n) = (p1-1) (p2-1) ... (pk-1) 。
(2) 计算具有i个不同的奇素因子 (即i个素因子都大于2) 的独立数之和
将m分解成k个不同素数的乘积m=p1p2...pk。m的欧拉函数 (小于m且与m互质的数的个数) f (m) = (p1-1) (p2-1) ... (pk-1) 即为m号基因的独立数。例如6号基因的独立数为f (6) = (2-1) * (3-1) =2。由于试题要求计算基因编号所含的不同奇素因子的个数k', 因此p1=2时, k'=k-1;p1!=2时, k'=k。设s[i]=具有i个不同的奇素因子 (即i个素因子都大于2) 的独立数之和。显然s[0]=1。依次枚举奇素因子pt, pt+1, ..., pk (p1=2时, t=2;p1!=2时, t=1) , 每枚举一个pi, 则根据乘法原理将s[j-1][pi-1]计入s[j]。例如, k=3, p1=2, e1=1;p2=3, e2=2;p3=5, e3=1。由于p1=2, 因此依次枚举p2和p3。
枚举p2:s[3]=s[3]+s[2] (p2-1) =0, s[2]=s[2]+s[1] (p2-1) =0, s[1]=s[1]+s[0] (p2-1) =0+1*2=2。
枚举p3:s[3]=s[3]+s[2] (p3-1) =0, s[2]=s[2]+s[1] (p3-1) =0+2*4=8, s[1]=s[1]+s[0] (p3-1) =2+4=6
由此得出s[0]=1, s[1]=6, s[2]=8。S序列的计算过程如下:
(3) 计算所有第二类基因的独立数之和与所有第一类基因的独立数之和
对于编号为m的基因, 如果能把m分解成偶数个不同奇素数的积, 则它是第一类基因;如果m本身就是奇素数或者能把m分解成奇数个不用奇素数的积, 则它是第二类基因。试题要求计算基因m号和它的父基因中, 所有第一类基因的独立数之和与所有第二类基因的独立数之和。设tot1为所有第二类基因的独立数之和, tot1=∑ (s[i]|i为奇数) mod 10000;tot2为所有第一类基因的独立数之和, tot2=∑ (s[i]|i为偶数) mod 10000例如, k=3, p1=2, e1=1;p2=3, e2=2;p3=5, e3=1。按照上述方法得出s[0]=1, s[1]=6, s[2]=8。显然, 所有第二类基因的独立数之和tot1=s[1]=6;所有第一类基因的独立数之和tot2=s[2]=8。按照下述方法计算tot1和tot2:
(4) 计算所有第三类基因的独立数之和
对于第三类基因的独立数之和, 无法正面求解, 但可以通过求解n的所有约数的独立数之和来求第三类基因的独立数之和。记n的所有约数的独立数之和为tot3, 由乘法原理可得:
根据“第三类基因是除第一、第二类基因外的其他编号的基因”的题意, 所有第三类基因的独立数之和应该等于m-tot1-tot2-1。例如, k=3, p1=2, e1=1;p2=3, e2=2;p3=5, e3=1。按照上述方法得出m=2*3^2*5=90, tot1=s[1]=6, tot2=s[2]=8, tot3=m-tot1-tot2-1=90-6-8-1=75。
由于输出格式是所有第三类基因的独立数之和除以10000的余数, 因此应该计算 (m mod 10000+30000-tot1-tot2-1) mod 10000 (加30000是为了保证被除数是正整数) 。
1.3 原始算法代码
1.4 重建的算法代码
1.5 原题运算结果及验算结果
(1) 原题运算结果
所有第一类基因的独立数之和是510;
所有第二类基因的独立数之和是644;
所有第三类基因的独立数之和是16007145。
(2) 验算结果
第一类独立数之和是644;
第二类独立数之和是390;
第三类独立数之和是16008047。
2 全部组合算法
2.1 问题引入
题目的实质就是求出全部长度的组合, 然后计算独立数之和。网上见过了很多排列的算法, 包括全排列算法。组合算法也就是根据公式来计算, 只有结果, 也不实用。以前编写过一个最新组合程序, 但是算法太过复杂, 不实用。有没有既简单又实用的算法呢?于是又进一步分析。
2.2 算法思路
设置输出长度从1到n, 依次输出各种组合, 使用一个逻辑数组B[], 设置输出状态。在输出过程中要判断是否有重复输出, 使用判重函数判断单个位置是否重复输出, 使用栈保存起始位置到倒数第二个位置, 然后输出完后恢复栈中存储的位置, 设置为未输出状态。比如:1 2 3 4 5 6, 当要输出1 2 3 45 7时, 首先要保存1 2 3 4 5的位置, 输出1 2 3 4 5 6后, 恢复1 2 3 4 5位置为未输出状态 (B[i]=false) , 然后再次输出12 3 4 5, 当到6位置时, 因为前面已经输出, 所以输出1 2 34 5 7, 到n位置输出后, 起始位置start+1, 并设置从start位置到最后位置n的输出状态全部为false (B[i]=false) 。直到全部长度的组合输出完毕。
2.3 算法代码
2.4 输出结果
共有670个组合序列。
2.5 100个数 (n=100) 的输出结果
共有4416325个组合序列。
3 结语
全部组合算法简洁明了, 功能特别强大, 而且很实用。为了完善此代码, 经过多天的日夜构思算法, 调试代码, 而调试时的繁杂和艰辛 (连续6个小时) 更是要坚强的毅力才能够完成的。坚定的信念加百分的努力一定会有理想的结果。
试想一下, 这只是100个位置的全组合输出, 如果是1000个, 10000个, 100000000个呢?只要有足够的时间, 本程序都可以全部输出, 而且不会造成数据溢出。
摘要：最近认真学习了王建德教授的“基因繁衍”, 题目的数据量很大, 采用乘法原理来计算, 看起来很是完美, 不过后来手工列出所有组合数据, 验算一下, 可以发现与结果不符。采用全部组合算法, 简洁明了, 功能强大实用。
施工机械组合优化计算程序算法 篇3
1 对土方路堤填筑施工过程分析
对于大多数情况,尤其是流水作业时,施工机械都是循环利用。所以,只需选取一个施工周期作为分析对象。考虑到作业方式均为流水作业,即假定当机械完成某施工段作业后马上进入下一施工段的作业。其间发生的等待时间计入下一施工段(相当于在本施工段开始)。这样,只需要考虑计算机械在作业前和作业中的等待时间以及作业时间,有利于计算机械的工作时间,使得程序开发得到简化。
2 程序的主要功能
机械施工仿真程序的主要功能包括:施工过程的仿真计算分析,单位工作量直接成本(元/m3),各种施工机械的利用率分析,单位工作量施工时间(h/m3)。并采用流水作业的方法来分析路堤填筑的施工过程。根据程序分析结果来确定施工机械组合的优化,还可以根据分析结果来确定流水作业的最佳单位作业单元大小。
3 程序数据结构及算法
3.1 程序的输入输出
输入数据包括机械数据和作业数据两种。机械数据是已有的机械数据库中选取各工艺使用的机械及数量;作业数据指和工程仿真计算有关的工程数据。数据输入可采用人机交互的方式按照提示输入,也可以建立Excel文件直接导入程序。
程序输出数据采用两种方式:一种是通过程序的交互界面直接显示在屏幕上;另外一种是把数据导出到Excel。输出数据包括各机械的利用率、总的工作时间、直接成本。
3.2 数据结构
对每一类机械如自卸汽车建立一个数组,数组属性为MachClass。数组的第一个元素记录本组的整体信息,包括机械数量总功率、总的工作能力、总的工作时间、平均工作效率等。由于在某一个作业点,作业进行是按工艺的顺序来完成的,对机械类数组建立一个链。为了避免程序逆序访问数组,链只能单向读取。
3.3 程序的仿真计算算法
3.3.1 程序流程
机械化施工仿真计算程序流程按照工艺顺序分成若干个作业步骤,每个作业步骤都有与之对应的施工机械。在这里不考虑相邻步骤的施工机械在同一工作面同时工作的影响(实际上,合理划分作业单元时,可以减小甚至消除由此带来的误差)。也就是对任何非起始作业的工作,只有它的紧前工作完全结束时,才能开始工作。在程序中,按照不同的施工步骤建立独立的工作模块。具体的流程图见图1。
3.3.2 程序的数学模型
程序采用机械组合的总利用率、机械利用率及单位工作量费的直接成本来评价机械组合的有效性。在机械发生作业等时,费用发生只计算不变费用部分。计算式为:
3.3.3 程序实现过程中遇到的问题的处理
由于在施工的过程中,象压路机、平地机等机械有一部分叠的工作量,这部分工作量处理方法有两种:1)根据机械的重宽度将作业量乘当量系数,得到当量工作量。2)对机械的工作度进行折减,得到有效工作宽度。本程序采用第二种方法。
各作业间的数据传递采用自定义机械类MachClass的属性的修改来完成。同时用机械类的属性值来记录机械所处工作状态、工作/等待的时间及机械的性能参数。
程序通过修改机械类属性MachClass.Machstate=工作/等来确定机械所处的状态。通过上一施工过程生产的工作量与一个施工过程机械的剩余生产能力(处于等待状态机械的生产力)的差值来确定作业的进行程度和机械所处的状态。并根据机械运行的时间来修改属性MachClass.Worktime和MachClass.Attime来记录机械的运行和等待的时间。由此可以计算出各机械利用率MachClass.Effeciency和各机械耗费的直接成本MachClass.Cost。
程序采用使用时间因子的方法来模拟施工过程中消耗的间。在施工开始时,随机产生一时间因子,所有机械的起始时都采用这一因子。机械所消耗的时间在起始时间因子的基础延迟。在延迟时间段内,表示机械处于使用中,否则处于闲置中并采用一计数器记录任何时刻与起始时刻的时间差。为了使录时间单位与机械台班价格相对应,每一个时间因数表示实际工时间为1 h。
4 实践运用
重庆市政道路设计等级为城市快速路,总长5.2 km。文中取了其中的一层作为仿真计算对象,长度为500 m。仿真分析的任务是得到直接成本达到最小的机械组合。取土场离施工现场的平均运距为2 km,路基宽度为15 m(分析层实际施工宽度),松铺厚度40 cm。选配的施工机械及配套方案:2台Cat950B装载机,10 t的自卸汽车若干,1台140推土机,1台PY160平地机,1台12 t的光轮压路机稳压1遍,CA-25 t振动压路机两台各振压2遍,1台179SE压路机作封层碾压。
分析时选用自卸汽车作为分析对象,即在不同的机械组合里选用不同数量的自卸汽车。组合一:选用5台自卸汽车;组合二:选用6台自卸汽车;组合三:选用7台自卸汽车;组合四:选用8台自卸汽车。分析的结果如表1所示。
由分析可知,机械组合经优化后,组合三直接成本节约率高达21%(相对组合一)。机械组合三的直接成本最低,为优化后组合。把组合三运用到工程实践,实际耗费的工程直接成本单价为2.899元/m3。
5 结语
实践证明,通过对工艺的分析和施工过程模拟的简化,采用仿真计算的方法可以对机械组合进行优化。把这种方法在浙江某公司进行推广,现场施工技术人员能较快的掌握并应用这种方法来指导施工,甚至把它推广至隧道的开挖,产生了较好的经济效益。由于机械原始工作参数(如自卸汽车的速度,每车的装运量)是随机的,但是从统计角度来看,它们的平均值是稳定的。这就要求现场施工技术人员对现场机械的作业性能比较熟悉,这是有效使用仿真计算分析方法的关键所在。
摘要：通过对机械施工过程的分析,建立了一个比较简单的数学模型和模拟算法,降低了仿真分析程序的难度,分析解决了程序模拟工程中遇到的一些难题,并把这个优化计算方法运用到具体工程中,指出仿真计算程序可以对机械组合进行优化,并且指导现场施工管理。
关键词：机械化施工,机械组合优化,仿真计算
参考文献
[1]巫世晶,贺小明,何小新,等.大坝碾压混凝土浇筑及施工机械配套的仿真研究[J].红水河,1999(2):35-38.
[2]钟登华,李景茹,刘奎建,等.全过程动态仿真技术及其在大型工程施工管理中的应用[J].天津大学学报,2003,36(3):347-352.
组合优化问题的人工鱼群算法应用 篇4
1 人工鱼群算法
1.1 人工鱼群算法的定义
人工鱼群算法是2003年邵之江、李晓磊等人首次提出来的。它表示在一片水中,鱼一般能自行或者跟随其他鱼群找到营养物质较多的地方,所以,鱼存在数量最多的地方一般就是本片水域中物质营养最多的地方,人工鱼群算法就是利用这一特征,通过组建构造人工鱼来模拟鱼群的寻找吃食、聚集鱼群及相互追尾行为,从而实现寻优目标化。
1.2 人工鱼群算法的几大特点
简单性:在算法中仅能使用目标问题的函数值;
并行性:许多AF并行进行搜索;
快速性:算法中虽然也存在一定的随机因素,但整体是在逐步向最优搜索的;
全局性:算法具有跳出部分极值的功能,使不受局部极值的限制和影响;
跟踪性:随着工作状况或其他因素的改变而造成极值的变化,人工鱼群算法具有迅速跟踪变化的能力。
2 人工鱼的几种典型行为
1)觅食行为:一般正常情况下鱼往往在水中自由自在游动,当发现食物后,就会向食物逐步增多的方向飞速游去。
2)聚群行为:鱼在水中游动的过程,为了保证自身的生存条件,躲避外界危害,会自然而然地聚集成群,鱼聚群所遵守的原则有3条:分隔原则:尽可能避免过度与临近鱼群伙伴造成拥挤;对准原则:尽可能与附近伙伴的游动方向保持一致;内聚原则:尽可能朝附近鱼群伙伴的中心游动。
3)追尾行为:当鱼群中有鱼发现食物的地点并且快速朝食物移动时,其临近的鱼群会尾随此鱼快速来到食物点。
4)随机行为:单独的一条鱼在水中通常都是无规则游动的,这就是为了更大范围面积地寻找食物点以及身边的鱼群伙伴。
5)行为选择:根据所需要解决问题的性质,对人工鱼所生活的环境进行评价,从而选择一种行为方式。较常用的评价方法就是选择能使组合最优化的行为,亦是各个行为中使得人工鱼接下来是一个最优状态的行为,如果没能使接下来的状态最优,则采取随机行为。
3 具体人工鱼算法
综合以上的人工鱼的行为,各个人工鱼探究它目前所处的环境状况和鱼群状况,从而来选择一种适合的行为来实际执行,最终人工鱼聚集在几个极值的周围。一般情况下,在讨论求极大值时,拥有较大的适应值的人工鱼一般处于值较大的极值周围,这利于获取整体极值区域,而且较大的极值区周围一般也能集结许多的人工鱼,这有助于判断并且获取整体极值。具体的人工鱼算法步骤如下:
步骤1:确定种群规模数量结构为N,在变量可行域内生成N个个体,设定人工鱼的可视区域,步长为Step,拥挤度因子为&,尝试次数为try_number。
步骤2:计算初始鱼群各个体适应值,取最优人工鱼状态以及它的值赋在公告板。
步骤3:个体通过寻找食物,鱼群聚集,追尾行为更新自己,生成新鲜的鱼群。
步骤4:评价所有个体。如果某个个体有鱼公告板,则将公告板更新为该个体。
步骤5:当公告板上最优解达到满意的误差范围内,算法到此结束,不然,回到步骤3。
4 人工鱼群算法的实例应用
4.1 求解旅行商问题
对人工鱼群算法在组合优化问题中的应用研究,现将它应用的具体事例,通过对TSP的研究对这整个研究具有重大的实践性和理论基础。TSP问题是一个具有背景和重要理论价值的组合优化难题,许多关于TSP的工作并不是直接推动的,而是因TPS为其他算法提供平台,使得这些算法应用于离散优化的问题,再者,TSP的大量直接应用给研究分析领域带来了勃勃生机,并指引未来工作。
旅行商问题也被称作“旅行推销员问题”,就是指1名推销员要访问许多个地点时,怎样寻找在拜访每个地点一次后再回到最初起点的最短路线。原则虽然简单易懂,可是在地点数目剧增后求解就非常复杂难办。以五十二个地点为例子,要列举所有路线以后再确定最佳行径,那么总路线数目惊人,几乎不可计算。多年来全世界许多有名数学家挖空心思试图找到一个高效简单的算法。TSP问题在物流中的阐述是对应一个物流配送公司来说的,想要将N个客户的订货沿最短路线全部及时送到。
4.2 求解车间作业调度问题
车间作业调度是一个典型的NP—hard问题,亦是组合优化问题领域中研究的重要选题。对JPS的研究具有举足轻重的现实意义和理论基础。车间作业调度问题是最最普遍,最复杂和最具难度的生产调整问题。目前对车间作业调度问题的研究多采取群智能算法和启发式算法,比如例粒子群算法、蚊群算法、遗传算法等等。但采用新型的人工鱼群算发直接解决JPS。
车间作业调度问题描述:
已知:有n个工件{J1,J2,…,Jn}在m台机器{M1,M2,…,Mm}上加工,每个工件以一定的次序在所有的机器上轮流加工,每个工件分成m个工序,而每个工序对应相应的加工机器。其中,工序的加工时间是给定。工件上的约束条件为:每个工件上的工序只能在上一个工序执行结束后,才能开始执行下一个工序。
5 结语
人工鱼群算法的提出者李晓磊等人对参数算法的影响进行了探讨,总体来说,整个算法对各参数的取值范围的容纳度还是非常大的。算法采用自上而下的设计方式,每个个体的行为都具有相对的独立和互补,使得整个算法的收敛性比较稳定,注重研究组合优化问题的人工鱼群算法应用的意义非凡。
摘要：优化组合问题在现实生活中应用普遍,而且工程代表性强,可是想要实现最优化求解不容易,当今组合优化求解的主要方式采用启发式算法。人工鱼群算法是新型的群智能优化的算法,它的原理简单易懂,收敛速度快捷,求解精度颇高。最近几年得到了重视和广泛应用。
关键词：组合优化问题,人工鱼群算法,旅行商问题,车间作业调度
参考文献
[1]李晓磊,路飞,田国会,钱积新.组合优化问题的人工鱼群算法应用[J].山东大学学报(工学版),2014,05:64-67.
[2]雷娟.人工鱼群算法在组合优化问题上的应用研究[D].西安理工大学,2012.
[3]郑晓鸣.人工鱼群算法的改进及应用[D].上海海事大学,2015.
[4]张汉强.人工鱼群混合智能优化算法及其应用研究[D].浙江大学,2013.
一种组合导航系统故障检测算法 篇5
目前在组合导航系统中常用的故障检测方法主要包括残差χ2检验法和状态χ2检验法两种方法这两种方法需要了解系统的数学模型[1,2]。文献[3—5]等还给出了数据变化率检验法、模糊识别判断法、神经网络法等故障检测方法。其中, 数据变化率检验法在故障发生的时间超过了一定期限的情况下可能做出错误的判断;而模糊识别判断法神经网络判断法等虽然不依赖于系统的数学模型, 但具体到实际应用仍有待发展。
支持向量机的思想最初于20世纪70年代提出, 近年来已经成为机器学习领域的一个研究热点。作为一种分类算法, 它能够较好地解决小样本、非线性和高维数的数学问题, 其应用领域也从最初的二类分类问题扩展到复杂系统的建模、优化控制等问题, 不仅在传统的模式识别和工业过程领域得到应用, 而且在新兴的生物信息、金融证券、药物分析、辅助医疗等诸多领域受到研究者的青睐[6,7]。
现将两种χ2检验法的检验量相结合, 应用二叉树多类支持向量机理论, 提出了一种面向组合导航系统的故障检测与处理方法, 同时进行了相关仿真研究。仿真结果表明, 该方法能够较好的应用于组合导航系统。
1χ2检验法
χ2检验法是一种通过检验所构造的n维高斯分布随机向量的均值和方差阵是否与假设值相符, 判断是否发生故障的统计假设检验法。根据所构造的随机向量的不同而有不同的χ2检验法, 其故障检测性能也有所不同。
其中, 状态χ2检验法主要是通过检验两个状态估计的差异来判断是否有故障:一个是经量测更新的Kalman滤波器提供的状态估计x k, 会受到系统故障的影响;另一个是状态估值x sk, 其不接受量测更新, 由所谓“状态递推器”或“影子滤波器”利用先验信息递推计算得到, 与测量信息无关, 因而不受故障影响;残差χ2检验法则主要是通过检验卡尔曼滤波器的残差εk分布来检测系统是否发生故障。
2面向组合导航系统故障检测的二叉树模糊支持向量机模型
2.1模糊支持向量机[8,9]
设存在任意训练样本 (xi, yi) , 其对应模糊因子si, σ≤si≤1, σ为任意小正数, si表示样本xi属于正常的模糊隶属度。由此可得模糊支持向量机的训练数据集合
求解模糊支持向量机最优超平面的问题可以转化为下面的优化问题。
目标函数
约束条件
式中, c为惩罚因子。
引入Lagrange因子αi, 得到如下Lagrange函数
对该Lagrange函数求偏导, 令偏导数为零, 经过推导可以得到如下对偶二次优化问题, 即
目标函数
约束条件
对于非线性问题, 同样考虑从输入空间到特征空间的映射φ, 引进核函数k (xi, xj) , 得到类似的优化问题, 即
目标函数
约束条件
由于惩罚因子c为常量, 因此模糊因子si成为决定模糊支持向量机工作性能好坏的关键因素。当样本xi为噪声样本时, si应较小, 这样将大大降低了噪声样本对模糊支持向量机的训练结果的影响。而当样本xi为非噪声样本时, 则应令si=1, 这可与标准支持向量机相一致。由此可见, 模糊支持向量机通过模糊因子si的引入, 有效地减弱了噪声样本数据对支持向量机训练结果的影响, 从而得到了可靠的分类超平面。
针对模糊因子si的确定, 文献[9]提出的基于样本密度法的模糊支持向量机在性能上远远优于其他模糊支持向量机方法, 取得了较好的应用效果。为此, 采用该方法求解模糊因子。
样本xi的模糊因子计算公式
根据式 (10) 可以得到所有样本的模糊因子, 随后即可训练该模糊支持向量机。
其中, 样本周围同类样本的密度定义为样本正密度, 记为ρ+i;样本周围异类样本的密度定义为样本负密度, 记为ρ-i;所有样本正密度的算术平均称为平均正密度, 记为ρ+。
2二叉树多类模糊支持向量机
针对故障多类问题, 本文采用二叉树多类支持向量机[10,11], 其结构如图1所示, 即每次分割只分割出一个类。具体故障分类时, 从二叉树的根节点SVM 1开始计算分类决策函数, 根据函数值的正负 (+1或-1) 决定下一节点, 如此下去, 直至选定某一叶节点, 此叶节点所代表的子类即为样本的所属类别。
为简化算法, 不再深入定位各导航子系统内的各种故障, 其中子类1表示样本无故障, 子类2表示导航子系统1故障, 子类n表示导航子系统n-1的各种故障。
由于支持向量机对训练样本内的噪声或孤立点特别敏感, 在噪声存在的情况下其分类性能将大大下降。考虑到组合导航系统的传感器精度较低, 易受外部环境干扰, 现采用模糊支持向量机作为二叉树多类支持向量机各节点的支持向量机类型, 即将SVM_1、SVM_2、…、SVM_n均设计为模糊支持向量机。
2.3组合导航系统故障检测原理
组合导航系统的种类非常多, 包括有惯性组合系统、无线电组合系统、雷达组合系统等。以MINS/GPS组合导航系统为实例, 研究了它的故障检测方案。
为提高对系统故障的敏感性, 现利用故障检测量状态χ2检测量ζ
fin (k) =[ζ
ϑ
Xf=[VeVnVuL λ h]TMINS
Xg=[VeVnVuL λ h]TGPS
信息融合中心利用Xf和Xg进行系统状态的最优或次优估计。故障诊断中心包括故障向量生成器以及支持向量机。故障向量生成器包含2节所述的状态递推器, 其接受来自信息融合中心的各种输出信息, 生成故障检测向量fin (k) ;支持向量机则负责根据fin (k) 进行实时故障检测, 其输出fout (k) 即为系统故障检测结果。
最初的支持向量机算法是通过构造一个最优超平面, 只能对两类问题进行分割。但本系统中由于采用的是前文所提出的二叉树模糊支持向量机, 其不仅可以及时检测出系统故障, 而且需要识别系统的具体故障位置, 即识别出MINS子系统故障或GPS子系统故障, 以利于导航信息的输出。显然, 这是一个多类分类问题。
3仿真
为检验前述故障检测算法的有效性, 针对MINS/GPS组合导航系统进行了仿真研究。仿真中支持向量机的训练和故障检测均假设系统在任意时刻只有单个传感器发生故障, 而且这里仅讨论传感器阶跃故障。
3.1二叉树模糊支持向量机的训练
在组合系统的静态仿真数据中, 取所有300组数据作为训练样本, 其中100组为无故障样本, 另外200组为传感器故障样本。
对于支持向量机SVM_1, 取所有300组数据作为训练样本。当fin (k) 为无故障样本时, yk=+1;反之, 取yk=-1。这样, {fin (k) , yk}, 即构成SVM_1的训练样本集。
对于支持向量机 SVM_2, 取200组故障样本为训练样本, 这时yk=+1对应MINS故障, yk=-1对应GPS故障。
分别训练支持向量机SVM_1和SVM_2, 这样就得到了由SVM_1和SVM_2构成的二叉树支持向量机。
3.2仿真结果
在MINS/GPS仿真程序中嵌入上述二叉树支持向量机进行故障检测定位, 同时应用如下故障处理方案:①如果系统检测无故障, 认为信息融合中心的输出信息有效, 以此进一步计算导航信息;②如果检测MINS故障, 直接采用GPS输出信息作为导航信息;③如果检测GPS故障, 则采用MINS输出信息作为导航信息;④如果检测均有故障, 系统失效。
下面将分别针对几种故障情况进行仿真, 并给出了部分典型误差曲线。
3.2.1 x轴陀螺仪发生突变故障, 故障发生时间为100 s
如图3 (a) 和图3 (b) 所示为运用上述二叉树支持向量机的东向速度和北向速度误差仿真曲线。如图3 (c) 和图3 (d) 所示为未使用上述二叉树支持向量机的载体的东向速度和北向速度误差仿真曲线。由于MINS故障被隔离, 系统仅依靠GPS导航, 因此误差精度下降。
3.2.2 GPS速度发生突变故障, 故障发生时间为180 s
如图4 (a) 和图4 (b) 所示为运用上述二叉树支持向量机的东向速度和北向速度误差仿真曲线。
如图4 (c) 和图4 (d) 所示为未使用上述二叉树支持向量机的载体的东向速度和北向速度误差曲线仿真曲线。由于GPS故障被及时隔离, 系统仅依靠MINS导航, 因此误差曲线呈发散趋势, 这也证明了MINS系统只能完成短期导航任务。
分析上述仿真结果不难发现, 基于二叉树支持向量机的故障检测处理单元可以及时、有效地检测、定位系统阶跃故障。同时, 由于系统发生故障后切换为惯性导航或GPS导航, 因此, 系统导航精度下降。
5结论
本文在总结以往用于组合导航系统的故障检测方法的基础上, 将2种χ2检验法的检验量相结合, 应用二叉树支持向量机理论, 提出了一种组合导航系统故障检测方法。该二叉树支持向量机综合应用了二叉树、模糊支持向量机等技术。MINS/GPS组合导航系统的仿真结果证明了该方法的有效性。
参考文献
[1]徐力平.组合导航系统故障检测技术的研究:[博士学位论文].上海:上海交通大学, 2001:12—25
[2]陶俊勇.组合导航系统信息融合理论及故障检测与诊断技术研究:[博士学位论文].长沙:国防科技大学, 2000
[3]樊春玲, 金志华, 田蔚凤.基于小波模糊神经网络的陀螺仪故障诊断技术.上海交通大学学报, 2003;37 (1) :141—144
[4]彭蓉, 秦永元.自适应滤波方法在陀螺软故障检测中的应用.中国惯性技术学报, 2005;13 (1) :81—85
[5]翁海娜, 等.基于调频高斯小波变换的导航传感器故障诊断.北京航空航天大学学报, 2002;28 (4) :477—480
[6]张学工.关于统计学习理论与支持向量机.自动化学报, 2000;26 (1) :32—42
[7]薛毅.支持向量机与数学规划:[博士学位论文].北京:北京工业大学.2003
[8] Inoue T, Abe S.Fuzzy support vector machines for pattern classification.In:Proceedings of the International JointConference on Neural Networks.Washington, DC:Institute of Electrical and Electronics Engineers Inc, 2001:1449—1454
[9]安金龙, 王正欧, 马振平.基于密度法的模糊支持向量机.天津大学学报, 2004;37 (6) :544—548
[10]马笑潇, 等.基于SVM的二叉树多类分类算法及其在故障诊断中的应用.控制与决策, 2003;18 (3) :272—276
[11] Sungmoon C, Sang HO, Soo-Young L.Support Vector Machines withBinary Tree Architecture for Multi-Class Classification.Neural Informa-tion Processing-Letters and Reviews, 2004;2 (3) :47—51
基于组合混沌映射的图像加密算法 篇6
随着网络技术和多媒体技术的迅速发展, 数字图像正在成为人们网络信息交流的重要载体, 所以图像的安全性自然成为人们所关心的问题。传统的加密算法并不适合进行图像加密, 如DES, AES, RSA, 因为用它们加密之后的图象相邻像素点的相关性很大, 不适合保密。应用混沌映射进行图像加密与传统算法相比, 有很多相似但又不同的特性[1,2,3]。例如, 传统加密算法对密钥敏感, 然而混沌映射对初始值和参数值敏感;传统加密算法通过多轮加密来扰乱和扩散数据, 而混沌映射通过迭代把初始区域扩散到整个相空间。传统加密是定义在有限集合, 而混沌映射是定义在实数集。现已有很多的专家学者应用混沌映射进行图像加密, 如YEN J C使用CKBA的加密方法[4];SCHARINGER J使用kolmogorov流的图像加密算法[5];Zhi-Hong Guan使用CAT映射进行图像置换加密[6]等等。
Logistic映射和Chen映射[7]都是典型的混沌映射, 它们都具有初值敏感性和参数敏感性。用Logistic映射产生的混沌序列通过排序来改变图像中各像素点的位置, 达到混淆的目的, 在此基础上, 应用Chen混沌系统对Logistic加密的结果通过改变各点的像素值再进行加密。由于混沌系统所独有的特性, 使得双重加密的结果更加安全。
2 加密算法
2.1 应用Logistic映射进行加密
Logistic映射的表达式如 (1) 所示, 它是一个典型的混沌映射。
其中Xn∈[0, 1], 当参数b取值范围为 (3.569, 4]时, 系统具有混沌特性。
一般用它产生的混沌序列直接对信息进行加密, 但是在计算机有限的精度下, Logistic映射进行迭代的结果会出现重复, 这会给密码分析者带来攻击的机会。如在3位有效数字下, 其有一个13个值的循环, (0.109, 0.338, 0.950, 0.190, 0.610, 0.946, 0.204, 0.650, 0.910, 0.328, 0.882, 0.416, 0.972, 0.109) 。如果把Logistic映射产生的双精度序列进行一下排序, 进而对图像的各像素点位置进行排序, 以此来达到置换像素点位置的目的, 就可以避免重复所带来的不安全性。
用MATLAB进行仿真实验, 其步骤如下:
a.选取一个M×N的灰度图像。
b.给定参数b值和Logistic映射的初值x0, 让系统迭代M×N次, 产生M×N个值, 并对其进行排序。
c.把图像的二维顺序按照先行后列的顺序变成一维顺序, 并根据步骤b最后的顺序相应的对图像进行排序。
d.恢复步骤c为二维图像, 即为加密之后的图像。
经过Logistic映射加密之后的图像已经达到了图像混乱的目的, 但是并没有改变原始图像中各像素点的像素值, 为了增加系统的安全性, 将加密后的图像再送入Chen混沌系统, 改变各像素点的值。
2.2 应用Chen混沌映射进行加密
Chen混沌系统的表达式如 (2) 所示, 它也是一个典型的混沌系统。
其中 (x, y, z) 为系统轨迹; (a, b, c) 为系统参数。当a=35, b=3, c=28时, 系统有一个奇怪吸引子, 处于混沌状态。Chen混沌系统的参数更多, 相对也更安全。用此系统对Logistic映射加密后的图像再进行加密的步骤如下:
a.给定Chen的初值x0, y0, z0, 让系统迭代M×N次。
b.将每次产生的三个序列值按照公式 (3) 进行计算:
其中函数fra是求三个序列平均值的小数部分;计算机的有限精度是15位, 小数最多占用14位, 所以将其放大1014使之变成正整数;图像的灰度值是在 (0-255) 之间, 所以将放大的正整数对256求余, 使结果也在 (0-255) 这个区间。
c.将Ki转化成二进制;将第一次加密产生的图像的各像素点的值也转化成二进制, 并将Ki与其逐个进行异或处理, 共M×N次。
d.将M×N个结果再转化成十进制, 变回二维图像, 完成第二次加密。
这样, 图象中各点的位置和像素点的值都发生了变化, 从而达到了混乱和扩散的要求, 增加了加密的安全性。其安全性主要在于混沌系统对初值的极其敏感性, 系统的初值有一个微小的变化, 其混沌轨道会发生根本的变化, 即所谓的“蝴蝶效应”。为了验证算法的可行性, 我们通过实验来进行仿真分析。
3 仿真实验
选取一幅104×102的灰度图像, 令Logistic映射中的参数b=4, 初值X0=0.7, 则原始图像和第一次加密之后的图像如图1所示。
令Chen混沌系统的初始值x0=-9.036, y0=0.768, z0=29.263, 则第二次加密之后的图像如图2中 (a) 所示;用所有正确的初值进行解密图象如图2 (b) 所示。
从图1和图2中可以看出, 经过Logistic映射后, 已经把图象的各像素点的位置进行了重新的排序;经过Chen混沌系统后, 已经混乱的图象, 通过改变其像素值, 再次进行了加密。
经过大量的实验, 对两个混沌映射选择不同的参数值, 加密之后的图像效果都是“面目全非”的;选择不同的图像, 以及不同大小的图像都能得到同样的加密效果, 这说明用此方法起到了很好的加密作用。
为了验证加密算法的有效性, 可以对该方法进行安全性分析。
4 安全性分析
4.1 密钥量分析
采用Logistic映射和Chen混沌系统进行双重加密的关键技术就是混沌系统本身的初值敏感性。如果我们将Logistic映射的初值x0和Chen混沌系统的初值x0, y0, z0都进行保密, 把他们当作密钥来处理, 按照计算机的双精度来计算, 密钥量可以达到1060, 可见整个系统的密钥空间是很大的。
4.2 敏感性分析
既然混沌加密的安全性就在于它的初始值敏感性, 那么当截获者对得到的密文图像进行破解时, 如果针对两次加密的初始值有一点点偏差的情况下, 也不能还原出原始图像。图3 (a) 是对两次加密的图像图2 (a) 用x0=-9.036, y0=0.768, z0=29.263000001进行解密的图像。我们看到初始值z0仅仅和原来有微小的差异, 可是却没有还原到图1 (b) 的状态;图3 (b) 是针对图1 (b) 用X0=0.700001进行解密的图像, 同样是小的差异, 也没有还原出原始的图像。按照十进制小数双精度为15位来进行穷举攻击, 对4个参数的攻击难度也将达到1060, 所以用穷举法进行攻击显然是不行的。
4.3 统计分析
该加密方法已经改变了图像各点的像素值, 即加密后图像的灰度直方图也发生了变化, 图4是原始图像的灰度直方图, 图5是加密后图像的灰度直方图。从图中可以看出, 原始图像的像素值在某些点出现的频率很高, 比如像素值为100左右和210左右, 而加密后的直方图呈现正态分布。攻击者通过像素值出现频率的大小来破解显然是困难的, 这样就可以有效抵抗用统计方法进行的攻击。
4.4 时间复杂度分析
本算法中, 生成混沌序列主要是通过迭代, 若问题的规模为m, 则生成混沌序列的时间复杂度为O (m) 。为线性阶的时间复杂度, 而且时间复杂度较低。为检测算法的时间开销, 对不同大小的8位和24位BMP位图进行了大量的加解密实验。实验所采用的硬件系统是Pentium42.8G CPU, 512M DDR内存;软件系统为WindowsXP操作系统, MATLAB编程平台。在实验中, 对数据大小为2.25M的1024×768的24位BMP图像加密所用的时间约为0.38s, 解密所用的时间约为0.42s。该速度可以满足要求, 可见算法的效率较高。
4.5 空间复杂度分析
算法主要空间开销是保存混沌序列所使用的4个1维数组, 每个数组大小等于图像像素数。若待加密图像大小为M×N, 采用int型数组, 则总的大小为M×N×4个int型空间。可见空间开销只与图像大小有关, 与图像位数无关。例如, 对一幅1024×768的图像, 其空间开销约为1024×768×4/ (1024×1024) ≈3M。若问题规模为m, 则算法空间复杂度为O (m) 。
4.6 图像处理攻击分析
若加密图像被攻击者进行恶意破坏, 如加噪、滤波、剪切等图像操作, 测试结果表明:对加密图像轻微剪切并不影响图像解密操作。图6 (a) 是对加密图像剪切掉12.5%的图像, 图6 (b) 是相应解密图像;图6 (c) 是对加密图像剪切掉25%的图像, 图6 (d) 是相应解密图像。可见剪切12.5%对图像的恢复没有太大影响, 即便剪切掉25%, 也可清晰的看到原始图像轮廓。所以, 该方法可抵抗一定程度的剪切攻击。实验显示, 对加噪和滤波等图像处理攻击也有一定抗干扰能力。
5 结论
把混沌理论和密码学相结合是最近几年的事情, 但是已经显示出很强的发展趋势。Logistic映射和Chen映射都是典型的混沌映射, 本文利用混沌映射具有的初值敏感性对原始图像进行了双重加密。通过实验分析发现, 加密之后的图像满足了混淆和扩散, 不仅改变了像素点的位置, 还改变了像素点的值;具有密钥量大、抗初值攻击、抗统计和抗图像处理攻击等优点, 从而增加了系统的安全性。当然还有很多需要改进的地方, 如何选择一个好的混沌映射一直是人们所关心的问题。
参考文献
[1]Kocarev L.“Chaos-based cryptography:a brief overview.”IEEE Circ System Magzine, vol.1, no.3, pp.6-21, 2001.
[2]Chen G R, Mao Y B and Chui C K.“A symmetric image encryption scheme based on 3D chaotic cat maps”.Chaos, Solitons and Fractals, vol.21, pp.749-761, 2004.
[3]Kocarev L, Jakimovski G.“Chaos and cryptography:from chaotic maps to encryption algorithms”.IEEE Trans Circ System-I, vol.48, no.2, pp.163-169, 2001.
[4]Yen J C, Guo J I.“A new chaotic key-based design for image encryption anddecryption.”Proc IEEE Int Conference Circuits and Systems, vol.4, pp.49-52, 2000.
[5]Scharinger J.“Fast encryption of image data using chaotic kolmogorov flows.”Electron Imageing, vol.7, no.2, pp.318-325, 1998.
[6]Zhi-Hong Guan, Fangjun Huang and Wenjie Guan.“Chaos-based image encryption algorithm.”Physics Letters A346, pp.153-157, 2005.
排列组合的算法设计与C++实现 篇7
排列和组合是数学和计算机科学中的一项重要内容, 很多问题 (如旅行商问题、工作分配问题) 的求解中都用到了{1, …, n}的全排列。我们知道{1, …, n}的全排列有n!中, 那么该如何设计算法来得到所有的排列, 并用某种语言编程实现呢?下面详细讨论了四种生成{1, …, n}的全排列的算法, 还讨论了一种生成{1, …, n}的字典序r-组合的算法, 5种算法都用C++语言编程具体实现 (由于篇幅问题, 此处没列出C++源程序, 需要源程序的本人可以提供) 。
2 用换位法生成全排列
设已经得到了{1, …, n-1}的 (n-1) !个排列的表, 我们可以把n插入到{1, …, n-1}的每一个排列中的n个可能的位置中去, 从而得到{1, …, n}的n (n-1) !=n!个排列的表。
我们开始从左到右把n插入到12… (n-1) 的n个位置中去, 然后每处理一个{1, …, n-1}的新排列时, 再调转方向。因为这样它满足最小变化要求:仅仅需要交换相邻的两个元素就能得到一个新的排列。
例n=4的情况, 如下:
开始1的排列 1
从右到左将2插入1 12 21
从右到左将3插入12, 再从左到右将3插入21, 得到123 132 312 321 231213
对上面得到的6个{1, 2, 3}的全排列, 从右到左将4插入123中, 再调转方向从左到右将4插入132, 再调转方向依次插入, 如下
为了得到{1, …, n}的所有排列, 就先得生成并保存{1, …, n-1}的所有排列, 而为了生成{1, …, n-1}的所有排列, 又必须先生成{1, …, n-2}的所有排列, 等等, 这样处理和编程都比较困难。
我们可以找到一种方法, 不需要保留所有排列的列表, 从第一个排列1, …, n开始, 每次交换相邻的两个数就得到一个新的排列, 得到与上面相同的顺序。为此, 我们给每个整数k赋予一个方向, 在其上面画一个小箭头来表示:k或k。如果一个整数k的方向指向一个相邻的更小的整数, 我们称这个整数是活动的。例如, 对2 6 3 1 4 5, 346是活动的。
生成{1, …, n}的排列的算法为:
从12…n开始, 重复进行下面3步, 直到不存在活动元素。
1) 求出一个最大的活动元素k
2) 交换k和它指向的相邻元素
3) 把所有大于k的元素的方向调转对n=3应用该算法, 如下所示:
3 用字典序法生成全排列
上面的算法得到的排列的顺序不是非常自然, 我们可以找到一个算法, 按字典序生成{1, …, n}的所有的排列。字典序就是像在字典中单词的排列顺序一样, 所有的排列按照升序排队。
我们先来看看从一个排列来找下字典序的一个排列。例如, 对{1, 2, 3, 4, 5, 6}的一个排列163542, 如何找它的下一个排列。为了按照字典序得到最小的变化, 我们应该尽量去换动右面的数字。我们发现最后三个数字是最大的 (从右到左一个比一个大) , 无法再做任何调整。但3小于右面的5, 3542不是最大的, 故可以换动3。为了使得变化最小, 应该在3的后面找一个比3大的最小的数, 这可以从右到左找到第一个比3大的数。交换这两个数后形成164532, 现在最后三个数依然是从大到小排列的, 为使这三个数最小, 可以把这三个数逆置, 这样便得到163542是下一个排列为164235。
于是, 按字典序生成{1, …, n}的所有的排列的算法如下:
将12…n放置到a数组中, 重复进行以下步骤
1) 从右向左找到第一个减小的元素a[m], 如果不存在这样的元素则结束
2) 再从右向左找到第一个大于a[m]的元素a[k]
3) 交换a[m]和a[k]
4) 将m以后的每个数逆置, 得到一个排列
4 用减治-递归法生成全排列
可以采用减治法, 把n个数的排列, 转化为n-1个数的排列。对{1, …, n}的所有的排列, 我们先把1放在首位, 把{2, …, n}的n-1个数进行全排列, 然后再把2放置在首位, 把剩下的n-1个数进行全排列, ……, 以此类推, 就得到{1, …, n}的所有的排列。为了把某个数 (比如2) 放到首位, 可以交换这个数和第一个数, 但在对剩下的数进行全排列后, 应该再把这两个数交换回来, 以保持原有的顺序不变, 以便可以继续把第一个数和另一个数 (比如3) 进行交换。
5 用回溯-递归法生成全排列
回溯法的一个很好的例子是n皇后问题, 就是在一个n×n的棋盘上放n个皇后, 使得彼此不受攻击。全排列问题可以看作是一个简化的n皇后问题, {1, …, n}的n个元素看做是n个皇后, 放到一个1×n的棋盘上, 每种放法就对应一个排列。
仿照n皇后问题, 得到全排列的回溯算法:先把12…n放置到a数组中, x数组用来记录每个位置所放的是哪个元素, c数组用来记录各个位置是否已经放了数。对于第个元素i, 有n个可能的位置, 先看第一个位置, 如果可以放就放下去, 同时记录该位置已放数据。从第i+1个元素开始将各个元素放到x数组中, 当放好第n个数后就得到一个排列。将已放下去的第i个元素拿起来, 继续看能否放到下一个位置, 放好了第i个元素后继续放置第i+1个元素。
6 组合问题, 按字典顺序生成{1, 2, …, n}的所有r-组合
前面均为{1, 2, …, n}的全排列, 下面来研究一下生成{1, 2, …, n}的所有r-组合的字典排序算法。
例如, {1, 2, …, 8}的字典序的5-组合, 第一个应该是12345, 最后一个是45678。对12478, 我们来找它的下一个组合。和排列一样, 为了得到最小的变化, 我们尽量去改动靠右面的数字。最右面两个数字78已是最大无法再增加, 而数字4还不是这个位置的最大的数, 于是可以把4加1改为5, 最后两位也跟着改为尽可能小的数67。于是得到12478的下一个组合是12567。
于是按字典序生成{1, 2, …, n}的所有r-组合的算法为
从12…r开始, 重复进行进行以下步骤
1) 从右到左找到第一个不是该位置的最大值的元素a[m]
2) 将该元素加1
3) 将该元素以后的元素依次递增, 得到一个组合
摘要：本文讨论了{1, …, n}的全排列的四种不同的算法, 以及按字典顺序列举{1, 2, …, n}的所有r-组合的算法, 并对各个算法用C++语言进行编程加以实现。
关键词：算法,排列,组合,C++程序
参考文献
[1][美]Richard A.Brualdi.组合数学[M].冯舜玺译.北京:机械工业出版社.2002:27-68.
[2][美]Richard Johnsonbaugh.离散数学 (第五版) [M].石纯一译.北京:人民邮电出版社.2003:167-182.