三维装箱问题的模型与改进遗传算法
关于三维装箱算法问题, 一些算法理论, 感觉对这方面的应用有一定帮助144效学的实践与认识40着∑(B,*v)≤VB,B,PD,PWy=0或者1v∈{1,2,…,D},y∈{1,2,…,W},z∈{1,2,…,H},j∈{1,2,…,n}(12目标函数是箱子未装填物品的空间最少(亦即空间浪费最少)条件(2)确保子的1个装填空间单元被装填不超过1次即保证物品间不会互相嵌入;(3)式说明上层物品会有支撑,不会悬空(4),(5),(6)式说明物品装箱位置约束;(7),(8},(9)说明物品的摆放问;(11)是箱子的容积约束2這传算法21遗俊法遗传算法(GAs)是建立在达尔文进化论基础上的搜索算法,它从代表问题潜在解的个种群( population)开始,而一个种群则由经过基因(gene)编码 coding)的一定数目的个体individual)组成遗传算法采用了自然进化模型,如选择,交叉变异等计算开始时,一定数目S个个体(父个体1、父个体2……)即种群随机地初始化,并计算每个个体的适应度函数第一代也即初始代产生如果不满足优化准则,开始产生新一代的计算为了产生新一代按照适应度选择个体,父代通过基因重组(交叉)而产生子代所有的子代按一定的概率变异然后重新计算子代的适应度,将子代插入到种群中取代父代构成新的一代循环执行这一过程,直到满足优化准则22算法设计2.21编码方法采用矩阵编码方法,用多维数组(二维矩阵表示染色体结构,数组元素表示染色体基因,编码清晰,易于理解,遗传算子操作方便染色体S=(L,P,Px,Py,T)来表示问题的一个解其中:向量L=(Li,L1,…,Ln)为待装箱物品的一个排列;向量P=(Bn,B1,…,B3n)为对应于排列L的B,一个排列向量Px=(PB,PB,…,PB)为对应于排列L的PB一个排列向量Py=(PB,PB},…,PB为对应于排列L的PBx一个排列矩阵T=(x2=欢面为对应于排列L的装箱物品坐标22适值函数问题的目标是最小化箱子的浪费空间,适应度函数可定义为空间利用率函数(S代表染色体C1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net2期陈德良,等:三维装箱问题的模型与改进遗传算法Fitness(s)(∑B3*v/若∑(B;*v)≤V否则23解的不可行性,罚函数与评估函数由于对染色体作遗传运算时可能获得不可行的子代,惩罚技术是用遗传算法解约束优化问题中最常用的技术,本质上它是通过惩罚不可行解将约束优化问题转化为无约爽问题就本文讨论的问题而言,惩罚项包括:1)物品在装箱时不交叠,即满足约束条件{2},有着∑By≤1g:(S)1,否则2)物品装箱时不能出现悬空即满足约束条件(3),有0若∑B-B+)>0g2(S)=(151,否则3)物品装箱不能超出箱子边界,即满足约束条件(4,(5)和(6),有0若吃+B(Pp++Pwy*吗)≤D1,否则0若+B*(PD*+PWy*m)≤W941,否则(17)95(S)=0,若x+B*h;≤H8)1,否则eat(s=∑9(S)b=1那么,式(14)至(18)任何一个取值为1,都是不可行评估函数eval(S)=Fitness(S)*(5-Genalty (S)24算法步骤)初始化进化代数计数器,随机产生一定数目(大于设定的初始种群规模)的染色体;2)利用式(14)检验初始种群染色体可行性,对不可行解旋转赌轮接受小部分不可行解,与可行解构成初始种群3)对初始种群染色体进行遗传运算;①按照式(14)至(20)计算评估函数:⑩按顺序交叉方法产生子代;④变异算子;4)旋转赌轮选择染色体;)重复3至4)直到完成给定的循环次数;C1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net数学的实践与认识40卷6)确定最好的染色体作为最优解3实验结果我们用C++编程实现了上述算法在配置为CPU24GH/512 Mb ram的微机上,用随机产生的数据进行实验取遗传算法运行参数为:{群体大小进化代数,交叉概率,变异概率}-{100,50,0.85,0.05}用随机产生的数据进行实验,求解20个种类100件物品的装箱问题,得到最好解耗时小于1秒;计算50个种类200件物品的装箱问题,得到最好解耗时小于2秒以下是3类共16件物品的装箱问题.实验数据图2,第!行为箱子尺『;第2至第4行为待装箱物品,每行第1个数据表小序号第2至镌4数据分别为物品尺寸,第5个数据表示物品件数在计算转桌中包含数据依次是:序号,是否装载,物品长,物品宽,物品高,纵向坐标横向坐标,垂向坐标纵向长度,横向长度,垂向长度(图4).从图4可知第12号物品未能装箱,物品装箱的顺序可以从“序号列中得出.绘制的物品装箱示意图见图31421,2,乙2,2,图2实验数据图3装箱示意图文件((格式(Q帮助新 s REPORT耗时:.1 most g sec次数:01615积:7580001016每a0库:92.875989名寸:=280;y=1210;2=300NO: P st Din 1 Din 2 in 3 C xC YPu y Pu 2202002002002001002812B20020012010010020012鲁2020012010020020020020012B100100212021201215024015824815015561111111111115152每000ao00015150240202020055020200201002001215502D0200120100100201205s012020028012015024075000015024815015024075015015024a152002009o002002001002012090020012日未装相物品121501502年图1计算结果o1994-2010ChinaAcademicJournalElectronicPublishingHousealLrightsreservedhttp://www.cnki.net2期陈德良,等:三维装箱问题的模型与改进遗传算法1474结束语装箱问题是一常见而难解的优化问题,利用遗传算法求解时,随机产生的初始解会出现大量的不可行解(装箱物品占用空间出现大量交叠),本文将箱子内部空间划分为一个个立方体单元:算法的第2)步对标准遗传算法做了修改通过剔除大量不可行解提高算法的收敛速度,实验结果表明此算法运算过程及绪果稳定,具有较强的实际应用价值能有效解决复杂的三维装箱何题,今后将继续研究将该方法运用到其它不同的有关装箱问题或组合优化问题中参考文献[1] John J, et al. An improved algctithra for the ncn-guillctine-constraincd cutting-stock problem(JIOperational Resee ch Society, 19 /0,+1: 141-149[2] Coffmau E. G, et al. ver age-case analysis of cutting and packing in two dimensions [J]. Euro. Jof Operatic al Reseaich, 1990, 44: 134-14413) Fabien C, et al. A Two-phase heuristic for the two-dinensional cutting-stock problem [J. Opera-tional Research Society, 1991, 42: 39-744 Martello Silvano, Pisinger, David, and Vigo, Daniele. The Three-Dimensional Bin Packing ProblemJ. Operations Research, 2000 Informs. Vol. 48: 256-267]何大勇,査建中,姜义东遗传算法求解复杂集装箱装载问题方法研究向]软件学报,201,12(9):13801385阿]张德富魏丽军陈青山陈火旺等.三维装箱问题的组合启发式算法软件学报,2007,18(9):20832089A Mixed Integer Programming Model ofThree-Dimensional Bin-Packing Problem and ImprovedGenetic AlgorithmsCHEN De-liang, 2, CHEN Zhi-yaSchool of Traffc &z transportation Engineering, Central South University, Changsha 41076, China)(2. Logistics School, Central South University of Forestry Technology, Changsha 410004, ChinaAbstracts The three-dimensional bin-packing problem is complicated but a high level ofinterest in developing effective way to solve this kinds of NP-hard problem. First a MixedInteger Programming model was worked out in this paper, which resorted to dividing box spaceinto unit cube. Then an improved genetic algorithm was mainly developed. Tests on hundredsof problems show that this algorithm makes the most of volume utilization in minimal timeKeywords: three-dimensional bin-packing problem; space division; mixed integer program-ming model; improved genetic algorithmso01994-2010ChinaAcademicJournalElectronicPublishinghOuse.Allrightsreservedhttp://www.cnki.net
- 2020-12-05下载
- 积分：1
多核学习综述
特征融合，多核学习，核方法是机器学习的一种重要思想8期汪洪桥等:多核学习方法10391.2容许核的构造数据的基因功能分类问题,其中就讨论了前期、中期利用核函数可以大大简化计算,但如何针对具和后期三种集成方式.早期集成是指数据的集成,后体的问题设计出最适当的核函数却是一个难点实期集成是指分类器结果的集成,而中期集成就是核际上,经常采用的方法是直接定义核函数,从而隐矩库的组合,它通过对多个基本核矩阵进行合成得含地定义了特征空间. Mercer条件是检验核函数到,基于这种多核矩阵直接求和方式,可以实现异构是否定义了一个特征空间的充分条件,我们称满足数据源的融合,用来训练分类器此后,在蛋白质功能预测56与定位,蛋白质容许楼满是一些闭包性质或条件6,这使得我分子间的交互预测2,蛋白质折叠识别和远端同源们可以从些简单的核函数设计出复杂的核函数性检测2等方向,由于涉及到多特征空间或有效属性质1.容许核的正系数线性组合是容许核性的集合( roups of attributes available)问题,来性质2.容许核的乘积是容许核自异构源的数据具有不同特性,如全局特性、局部特性质3.函数乘积的积分是容许核.性等,这就需要核矩阵在集成时可以评佔这些潜在设s(x,)是一个定义在X×X上的函数,使的异构目标描述子各自的贡献.因此出现了一些加得k(x,x)=/5x,x)(2,x)dx存在则ka,2)板图多核合成方法,这类多核方法都无追过多个核是一个容许核数的线性组合得到的,图1所示的就是其构成的性质4.平移不变核是容许核的充要条件示意图个平移不变核k(x,2)=k(-x)是容许核,类别标号或预测值结果输出)且仅当其傅里叶变换F(u)-(2x)-号xk(x)i(ur)dx是非负的分类或回归(分类器或回归R效性质5.内积型核是容诈核的必要条件.合成核空闫合成核若一个内积型核k(x,2)=k(x·z)是容许核,则它必满足v≥0.k(5)≥0.0k()≥0且k(5)Kernel sKernel h5k()>0核空间(kemC性质6.内积型核是容许核的充要条件.一个内积型核k(x,z)=k(x·z)是容许核,当征空间(C且仅当其幂级数展开式k(t)=∑0ant中所有系数an≥0.对于有限维的空间,条件可以稍微减弱输入数据图1多核函数线性组合合成示意图当前已经仔在较多的满足 Mercer条件的核函rig. 1 Sketch map of composition using multiple kernel数,常见核函数通常可分为两类:局部核和全局核6ar而局部核选择不同的核参数,又可分为大尺度核与小尺度核.在一些复杂情形下.同时考虑核机器分下面呆用公式的形式对上述线性组合合成核进类、回归性能和泛化能力,将不同核组合使用,将是行描述.假定k(x,2)是已知核函数,k(x,2)是它的更合理的选择归一化形式,例如核函数k(x,z)可以采用如下方法进行归一化:√k(x,x)k(z,x).采用以引入的符2基本多核学习:合成核方法号,可以定义以下几种合成核:将不同特性的核函数进行组合,获得多类核函a)直接求和核( Direct summation kernel)数的优点,可以得到更优的映射性能.并且,典型的学习问题经常涉及到多种或者异构的数据,多核方k(,2)=∑k(x,2)法可以提供更佳的灵活性.此外,它可以作为一种巧妙的方法来解释学习结果、使得应用问题可以得到b)加求和核( Weighted summation kernel)更深入的理解.这就是多核学习的一类基本方法,即合成核方法k(x,2)=∑(,2,≥0,∑月=1(6)2.1合成核的构造1)多核线性组合合成方法c)加权多项式扩展核( Weighted polynomial多核学习最早从生物信息学领域得到应用和认extended kernel同.如 Pavlidis等20在2001年就研究了基于异构k(x,z)=ak1(x,2)+(1-a)k2(x,2)(7)1010自动化学报36卷其中.k(x,2)是k(x,x)的多项式扩展是,该合成核矩阵的大小为(s×n)×(s×n),而原近来,这类合成核法又得到一些改进,在图始核矩阵的大小都是n×n,由于合成核矩阵是原始像目标的识别领域得到广泛应用.如在金字塔框架核矩阵规模的§倍,因此样本特征必须被复制,使运对日标形状进行多核表示阿,或釆用多核方法,算量成倍增加自动获得基」决策的一种相应目标类别的稀疏依赖3)其他改进合成核方法图,实现了多类目标联合检测③2].提高了目标的识近年来,针对多核学习中核函数的选取以及杖别率.通过同时考虑多核线性组合的稀疏性和分类值系数的改进,又出现了一些新的多核合成方法,器的强判别力,将多核学习问题转化为不同的优化如:问题58.63,或通过多对象描述子、多特征空间的整a)非平稳多核学习合,并进行快速求解64.此外,合成核方法在特征提前述的多核线性组合方法都是对核函数的平稳取、处理及应用7、分类972-4、图像分割、组合,即对所有输入样本,不同的核对应的权值是系统辨识等方面又得到了一些成功应用不变的.无形中对样本进行了一种平均处理. Lewis2)多核扩展合成方法等吲提出了一种多核的非平稳组合方法,对每个输述合成核方法都是试图通过一种求和“平均入样本配以不同的权值系数.如常规SVM判别函化”的思想42来实现不同核矩阵融合.然而,这里数为存在个丢失原始核矩阵信息的风险.比如,如果数据集的局部分布是多变的.不同的核处理不同的区f(c)=∑0r,m)+b(1域会得到更好的结果,对不同核函数采用平均的方法将丢失刻画这些局部分布的性能.为了实现核矩引入不同的加权系数,典型的合成核SVM的阵的组合而不丢失任何原始信息,可以考虑将多核判别函数可以改写为矩阵进行扩展合成42],新的核矩阵由原核矩阵和其他不同的核矩阵共同构成.在这个更大的核矩阵中原核矩阵仍然存在.因此,原始核函数的性质得以保∫(x)-∑m∑k(x,x)+b(1留.该合成核矩阵的形式为而对于非平稳的合成核SVM,其判别函数改进11K1,2K为2.2K∑a:∑()k(c;,m)(12)K1 K可以看出,原始核矩阵位于新矩阵的对角线上在最大熵判别( Maximum entropy discrimination,其他所有元素是定义为(Kn)3=Fn(m,)的MED)框架下,通过使用一种大间隔隐变量生成两个不同核矩阵的混合,可由如下公式求得(以两个模型,使得隐参数估计问题可以通过变化边界和高斯核为例)一个内点优化过程来表示,并且相应的参数估计可以通过快速的序列最小优化( Sequential minimaloptimization,SMO)算法实现.通过多种数据集的4:4+(9)实验验证,非平稳的多核学习方法具有更好的通用性.很明显,当p=p时,Kp=knb)局部多核学习实验结果显示,当数据集具有变化的局部数据此后,仍旧是针对多核学习在整个输入空间中分布时,这种合成核方法将是更好的选择此外,通对某个核都是分配相同权值的问题,G6nen等0常核组合方法在很大程度上依靠训练数据,并且必利用一种选通模型( Galing nodel)部地选择合须道过学习获取一些权系数,以标识每个核的重要适核函数,提出了一种局部多核学习算法在SVM性.而在护展合成核方法中,这些核函数的重要性可框架下,其判别函数形如以直接从支持向量机的训练过程中导出.由此,分别对应不同核的权系数可以通过一个单独的分类尜优化过程整体得到.并且该优化过程不会像其他加权∑q∑(x)k1(x;xm/r)+b(13)核方法那样,由于在优化权系数和训练分类器过程中两次仗用训练数据而产生训练数据的过拟合.但其中,7z(x)是选通函数,其定义形式为8期汪洪桥等:多核学习方法10117(c)exp((vm, )+Umo)(14)详细阐述了应用于合成核的列生成 Boosting方法并成功推广到分类和回归问题∑ep(,x)+"l2)二次约束型二次规划从数学形式上看,二次约束型二次规划是一类这里的tm和tm是选通模型参数,可以在多核学习目标函数和约束同为二次函数的优化问题过程中通过梯度下降法获得.将局部选通模型和基于核的分类器相结合,优化问题可以用一种联合的方式加以解决.局部多核学习方法获得了与多核学习近似的精度,但只需要存储更少的支持向量.基于st.Px+qx+r;≤0,i=1,2,…,m此, Christoudias等又提出了一种基于 BayesianAr=b的局部权值求取方法,以使学习过稈能适应人规模(1的数据集这里,P,B1,…,Pn是n×n矩阵,优化变量x∈c)非稀疏多核学习R;如果P1,…,Pmn均为0矩阵,则约束变为线性大部分合成核方法都有式(6)的形式,即对多核的,该问题实际变为一个二次规划问题系数的约束是一种1范数的形式,以提高核组合的Bach等针对多核矩阵和分类器系数锥组合稀疏性.稀疏性的提高在一些情况下可以减少冗余,问题的联合优化,提出了Q(QP的-种新对偶肜提高运算效率.但当某个问题多个特征编码间具有式,把它作为一个二阶锥规划,可以利用 Moreau-正交性,稀性可能导致有用信息的丢失和泛化性 Yosida正则化来生成SMO方法的适用形式.实能变弱.Klof等通过对系数引入一种l2范数约验结果显示这种基于SMO的算法比常用工具箱中束,即‖2=1,提出了非稀疏的多核学习方法.虽应用的内点法更有效,广泛应用于支持向量回归问然在此约束下,名核组合形式是非凸的,但通过使用题1二范数‖|2=1边界上的值,可以得到一个紧致的3)半定规划凸近似,这就保证了核矩阵的严格正定性.通过在大通过在一个核矩阵中综合考虑训练数据和测试规模数据集下与C1范数和常用多核学习( Multiple数据, Lanckrict等田通过半定规划技术实现了核kernel learning,MKT)方法进行对比实验,仿真实矩阵的学习问题,也为合成核模型提供了一种功能验结果显示2-MKL在抗噪声和特征集冗余方面具强大的渐进直推式算法,该算法被成功应用并推广有较强的鲁棒性.此后,Klo等刚又将O2范数约到蛋白质功能预测0.其考虑的核矩阵具有如下形束推广到任意C范数,p>1,进步增强了核机器式的通用性和鲁棒性Ktr Ktrt2,2合成核机器的学习方法Kr Kt为了求取合成核的参数,通常是将合戊核与支其中,K一(x)重(x;),1-1,…,mu,m+持向量机方法相结合,然后将目标函数转化成不同1,…,m1+nt:这里nt和m是有标号的训练样的优化问题,如不同的正则化形式或对训练样本本个数和无标号的测试样本个数.我们的目标是的一些约束,通过不同的优化方法进行求解.基于通过优化关于训练数据块Kt的损失函数,学习得此,出现了多种合成核机器的学方法到最优的混合数据块矩阵Kr和测试数据块矩阵1) Boosting方法K1即利用有标号的训练样本米预测测试样本的类早期受集成思想和 Boosting方法的启发,别,也就是说,作者认为在训练的过程中同时考虑训Bennett提出了一种多自适应国归核( Multiple练样本和测试样本,可以找出最佳的核矩阵.但这additive regression kernels,MARK)算法.MARK样产生的问题是,求解核矩阵的搜索空间也相对变定义了一种异构核模型,并考虑一个大规模核知阵大,为了避免过学丬( Overfilling), Lanckriet利用库( Library),这个库由不同的核函数和其参数构成.限制核矩阵的迹为一常数米控制,于是有了约束式通过使用一种梯度 Boosting列生成方法, MARK tr(K)=C构建出异构核矩阵的每一列,然后将其添加到合成半定规划是一种凸优化问题( Convex opti-核中.算法的目标就是在这个核矩阵库的基础上,找 mization problem)∞o,它有一个线性的目标函数到一种构建推广模型的方法.这种方法推广性强,不( Alline objectives lunction)、有限个线性矩阵不等需要存储大量的数据米应对后续的预测,提高了预式约束( Linear matrix inequality constraints)以及测的效率在此基础上,通过与SVM结合,Bi等17有限个线性矩阵等式约束( Affine matrix equality1042自动化学报36卷constraints),其标准形式如下如回归问题、一类分类(奇异检测)问题等.实验结果显示该算法可以有效增强模型的自动选择能力min c u并能提高学习结果的解释性.同时能有效应用于数S.t.Fy()-Fd+uFi+,.+ugFg20十万个样本和数百个核的大规模组合优化问题.这7=1,…,种半无限线性规划相比其他方法明显提高了学习速度,适宜于解决大规模问题.特别是当SVMs与·些Au= b已出现的字符串核( String kernel)相结合, String(17)kernel也是一种有效的核方法,它根据两个字符串其中向量t是最优化目标,FF是n×n的的所有公共子串计算它们的相似度,利用这些核对对称矩阵.F(a)是一个半正定阵,上标j表示特征的稀疏映射,使得我们可以训练一种字符串核可能有1全1个约束式:满足此约束式的所构成sVM,并应用于计算生物学中的千万级样本的数据的集合是一个凸集合.A是一个行数与长度相同,片段24在此基础上,7iem等提出了一种应用于列数与b长度相同的矩阵表示有限个等式约束式联含特征映射的多核学习方法,为多兴分类问题的因此,半定规划是在对称且半正定矩阵的凸子集合多核学习提供了一种史方便和原理化的途径.通过( Convex subsct)卜:求解凸函数的最优化问题针对多核支持向量分类问题,通过定义一种对一种凸Q(QP以及两种 SILPs在数据集上进行比较,实验结果显示 SILPS比QCQP在速度上更能指标( Performance iudex)u(K),基于原始一对有优势终可以转化为一个标准的半定规划形式5)超核( Hypcrkcrncls)对基于核方法的支持向量机而言、如何选择一个合适的核函数实现自动的机器学习是一个很大的min t,t,入,υ,6挑战Ong等3通过定义一种核空间上的再生核t.tr|∑FHilbert空间,即超再生核 Hilbert空间,并引入超核的概念及构造方法,在更广义的层面上实现了这,K;≥0目标定义1(超再生核 Hilbert空间, Hyper reproducing kernel Hilbert space).改Ⅹ为非3.tre-tU8+ xy空集合,Ⅹ:ⅩxX是复合指标集,H为函数f:X→R的 Hilbert空间,该函数可表示为该空间中两(e+-6+入y)1t-26Ce个向量的内积,且其范数f=√f,f,则被0>0称为超雨生 Hilbert空间,如果存在一个超核k:x6>0X→R具有如下性质:(18再生性:对所有∫∈丑,有(k,),/)其中,t是引入的一个替代变量( Auxiliary vari-f(x),特殊地,(k(x),k(,x2)-k(xxablc),v,6,A是引入的 Lagrangian乘子,至此,可b)k张成整个空间H,即H以通过标准的半定规划求解方法得到B及相应的span()(XLagrangian乘子,半定规划具有很高的泛化能力c)对仟一固定的(X,超核k是关于其第线性规划( Linear programming,LP)以及QCQP二个输入的核函数,即对任一固定的x∈X,函数问题都可以转换推广成半定规划门题然后可以很k(x,x)-kx,(x,x),x,x′∈是一个核函数容易地使用内点法( Interior-point method)加以解在超再生核 Hilbert空间上,可以用类似于止则决化品质函数的方法.得到一个从训练数据对核进行4)半无限线性规划学习的推理框架.对超核的学习,可以通过定义Sonnenburg等B7在多核矩阵锥组合的基础上,个被称为品质函数( Quality functional)的量(类似提出了一种通用而更有效的多核学习算法.该方法于风险函数)来实现,这个量可以衡量核函数“非良将Bach等的QCQP对偶形式改写为一种半无限( Badness”的程度线性规划(Semi- infinitite linear program,SILP)形定义2(正则化品质函数, Regularized qual-式,新的规划形式可以在标准的SVM应用问题中, ity functionality).设X,Y分别是训练测试样本利用成熟的线性规划方法进行求解.并且,通过将组合和样本标签,对X的一个半正定核矩阵K,此形式进行推广,算法能有效解决更多类型的问题,其正则化的质函数定义为如下形式:8期汪洪桥等:多核学习方法1013g(,x,Y)=9mp(k,X,Y)+2‖(17)分组LasoLasso回归是目前处理多重共线性的主要方法这里,≥0是一个正则化常数,h表示空间之一,相刘于其他方法,更容易产生稀疏解:在参H中的范数,Qm(k,X,Y)是一种经验品质函数,数估计的同时实现变量选择,因而可以用来解决检它表示核函数k与某一特定数据集X,Y的匹配程验中的多重共线性问题,以提高检验的效率.Laso度,该函数的值常用来调整k以使得gm最优(如:可以推广为分组Laso( Group lasso),从而使得最优核目标度量)模型的解可以保持组稀疏性和层次性.Bach26·关引理1(再生核 Hilbert空间的表示定理,注于分块1范数正则化的最小二乘回归,即分组Representer theorem for hyper-RKHS).设Las0o题,研究了其渐进模型一致性,推导出了分X为非空集合,Qmp是任意经验品质函数,X,Y组Laso-致性在一些实际假设下的充要条件,如分别是训练测试样木组合和样木标签,则每一个最模型误定.当线性预测器和欧氏范数(2范数)用函小化正则化品质函数g(k,X,Y)的k∈Ⅱ具有数和再生核 Hilbert,范数代替,这就是常说的多核学以下的一种表示形式习问题.通过使用函数分析工具和特定的协方差算,将上述一致性结果推广到无限维情形,同时提出k(x)=∑月12(m,m),(m,m1),,x∈x种自适应方法来获得一致性模型的估计,即使2,7在非适应方法必要性条件不满足的情况下也能适用(20)为多核学习间题提供了一条新的途径对每一个1≤i,≤M,这里B;∈R2.3其他合成核参数学习方法根据超再牛核 Hilbert空间的表示理论可知,由超核构造的决策函数不仅由某一个单核构成,而且从最简单的多个核直接求和到上述的各种改进还由多核之间的一个线性组合构成,因此具有更优合成核构造方法,多核学习经历了从经验性选择的性能在分类、回归以及奇异检测等方面的实验证运用多和优化方法求解的过程但针对一些具体间实了该方法的有效性B.8,拓展了多核模型选择与题,对核参数的选取,多核权系数的设定,目前还没合成的研究途径有形成一个合理统一的模式.常用的方法只能是凭6)简单MKL借经验、实验对比、大范围的搜索或通过交叉验证从Bach等的多核学习框架36出发, Sonnen-等进行寻优.在这种情况下,也出现了其他的些方bug等提出了种通用而更有效的多核学习算法,实现了多核学习问题,典型的有法37,该方法通过迭代使用现有的支持向量机代1)基于智能优化方法的多核学习码,从一个新的角度解决了人规模问题的多核学习这类方法主要通过一些比较成熟的智能优化然而,这种迭代算法在收敛到一个合理解之前,需要方法,建立目标函数,寻找该函数极值的过程就是过多的迭代运算. Rakotomanonyy等27用一种自合成核参数寻优的过程如采用多项式核与径向适应的C2范数正则化方法米考虑多核学习问题,每基核的合成核2作为支持向量机的核函数k个核矩阵的权系数被包含在标准SVM的经验风险2-(1-p)km,将其用SVM进行预测过程中最小化问题中,并采用(2约束以提高解的稀疏,的参数向量(d,o,,p)作为粒子,其中d为多项式然后采用了一种基于分块1范数正则化的算法来解核参数,为径向基核尺度参数,y为SVM调整参决这一问题,为多核问题提供了一个新的视角,并且数,p为合成核的权重参数,利用粒了群算法对该合证明了该方法与Bach等的方法是等效的.从上运成核的参数进行优化,最终找到最优的预测结果描述可以看出,除了学习合成核外,该与法解决的是2)基于核目标度量的多核学习个标准的SVM优化问题,这里核的定义形式为核度量434是两个核函数之间或核函数与目多个核的线性组合. Rakotomamonjyl称之为简标函数间的一个相似性度量,在多核矩阵信息融合单多核学习( Simple MKL)在加权的2范数正则方面得到了应用,其概念最早由 Cristianini等提出化形式下,同时对多核权系数进行一个额外的1范考虑一个两类分类数据集S={(x,1)}=1,其中非数约束,为多核学习提供了一种基于混合范数正则∈{+1,-1},则在数据集S下,两个核矩阵之间的化的新思路.简单多核学习可以从两类分类问题向核度量定义为其他方向扩展,如回归、类、一类分类(奇异检测)A(S,K1,K2)(K1,K2)以及多类分类问题,具有很强的通用性,并且与其他(21√k1,K1)F(K2,k2)F多核学习算法相比,该算法收敛速度更快且效率更这里,(K,Ka)F=>1-1Fn(x2:)(x,T)通1044自动化学报36卷过上式,对应于S的核矩阵K的性能可以通过A;-2,t-0,1,2,值米量度,如:A(5,K,G),这里的G是基于特定任务的理想核G=y,其中y=m12…,.基另一种典型多尺度核为小波核函数( Waveletkernel function) 831于对目标核的度量原珥,通过使用不同的核函数,或定理1.令h(m)是一个小波母函数,a和c分者调节不同的参数值,可以产生一组核矩阵.然后,别表示仲缩和转移因子,a,∈R如果x,z∈R对该度量值的最大化执行半定规划或其他学习方法,则内积型小波核函数可表示为以得到一个对不同核矩阵加权组合的最优核3多个尺度的多核学习:多尺度核方法k(2)=江4(合成核方法虽然有了一些成功应用,但都是根据简单核函数的线性组合,生成满足 Mercer条件的转移不变小波核函数为新核函数;核函数参数的选择与组合没有依据可循,对样木的不平坦分布仍无法圆满解决,限制了决策k(a, z)=(函数的表示能力.在此情况下,山现了多核学习的种特殊化情形,即将多个尺度的核进行融合.这种定理2.考虑具有一般性的小波函数方法更具灵活性,并且能比合成核方法提供更完备的尺度选择.此外,随着小波理论、多尺度分析理论h(x)=cos(1.75x)252间使其其有了很好的且论录这类方法目箭也如果x2(R",则小波核函数为得到了很好的利用,烘型的如 Kingsbury等③2将多个尺度大小的核进行分光heng等B到、 Yang k(a,2)=h(x二等834提出了多尺度支持向量回归.分别用于非平坦i=1数的估计和时序列预测.此外,通过进一步将多∏1c015(n-2)C一之尺度核与支持向量机结合.多尺度核方法在基于回归的热点检测48和图像压缩49等方面均得到了应(26用.近来,结合多尺度分析方法,基于 Hilbert空间通过仲缩因子a的变化,即可得到不同尺度的小波中的再生核进行函数重构得到了重视并进行了相关的应用研究;此外,多尺度核方法又逐步推广到核函数了高斯过程的健模与处里-27,这对基于核方法3.2多尺度核的学习方法的机器学习又是一次大的扩展1)多尺度核序列学习方法3.1具有多尺度表示能力的核函数对多尺度核的学习,很直观的思路就是进行多尺度核的序列学习.多尺度核序列合成方法32简单度表示能力的核函数.在被广泛使用的核函数中,高理解就是先用大尺度核拟合对应决策函数平滑区域的样木,然后用小尺度核拟合决策函数变化相对剧斯径向基核烈区域的样本,后面的步骤利用前面步骤的结果,进k(a, a )=cxp(22行逐级优化,最终得到更优的分类结果考虑一个两尺度核k1和k2合成的分类问题是最受欢迎的,因为它们具有通用普遍的近似能力,我们要得到合成的决策函数同时它也是一种典型的可多尺度化核.以此核为例f(x)=f1(x)+f2(x)将其多尺度化(假设其只有半移不变性):k(-22这里22af()=∑ak1(xn,)b2其中.σ1
- 2020-12-07下载
- 积分：1
|
联系客服（QQ：3324461878）
