AN EFFICIENT P-D ALGORITHM FOR SHORTEST PATH PROBLEM

ThisresearchissupportedbytheNationalNaturalScienceFoundationofChinaunderGrant19271023.Therearenumerousproblemsincombinatorialoptimization.Theirsolutionsaredifferentfromoneanother.Ithasnotbeenfoundanunifiedapproachthatcanbeusedtoailproblemsincombinatorialoptimization.However,therestillexistsanunifiedapproachthatcanbeusedtosolveaclassofproblemsincombinatorialoptimizationrelatingtographs,thisapproachisprimal-dualalgorithm.(WesimplycallPDalgorithm).Inlinearprogram,wesolveDRPtogetanoptimalsol…     

具有有界变量的瓶颈分配问题的一个并行算法(英文)

本文提出一并行算法求解具有优个约束以及n个非负有界变量的瓶颈资源分配问题,若有m台处理机,在一定条件下该并行算法的复杂度为O(n(n+logm))。     

红外光谱的不同产地黑果腺肋花楸果实鉴别

黑果腺肋花楸是已被列入新食品原料名单中的小浆果,富含花青素等成分,在酒类、饮料、功能食品、化妆品等领域广泛应用,具有较高的经济价值。因受不同产地气候等环境因素及种植条件的影响,黑果腺肋花楸果实品质差异明显。为规范黑果腺肋花楸果品市场管理,以中红外光谱技术结合化学计量学方法对不同产地黑果腺肋花楸果实进行鉴别。采集15个产区共750份黑果腺肋花楸果实红外光谱数据,采用K-S样本划分法,按4∶1比例将样本划分为训练集和测试集,并进行多元散射校正(MSC)、标准正态化(SNV)、移动平滑(SG)、一阶导数(FD)、二阶导数(SD)等光谱预处理,与原始光谱进行支持向量机(SVM)建模识别效果对比,确定最佳光谱预处理方法,同时对最佳光谱数据进行归一化处理。采用竞争性自适应重加权算法(CARS)和连续投影算法(SPA)提取光谱特征信息,并结合随机森林(RF)、极限学习机(ELM)、支持向量机(SVM)、偏最小二乘-判别分析(PLA-DA)进行建模对比,确定最佳模型。结果表明,MSC为最佳光谱预处理方法,MSC-SVM训练集识别率为93.33%,测试集识别率为92.67%,能有效减少光谱采集时产生的随...     

FTIR结合ELM对黑果腺肋花楸黄酮、多糖含量快速预测

黑果腺肋花楸是继蓝莓后的又一小浆果,因其黄酮含量高于蓝莓受到关注,已获进入新资源食品名单,并在饮料行业中使用。黑果腺肋花楸黄酮、多糖是其果汁及果渣中的主要生物活性成分,也是影响其品质的重要因素。以中红外光谱技术结合化学计量学方法对黑果腺肋花楸黄酮、多糖含量进行预测,为建立简便、快捷的黑果腺肋花楸产品质量检测方法提供基础。采集15个产区共750份黑果腺肋花楸红外光谱数据,测量每份样品黄酮、多糖含量,采用K-S样本划分法按4∶1的比例将样本划分为校正集和验证集,并对分组后的光谱信息进行多元散射校正(MSC)、标准正态化(SNV)、平滑(SG)、一阶导数(FD)、二阶导数(SD)等光谱预处理,与原始光谱进行极限学习机(ELM)建模预测效果对比,确定最佳光谱预处理方法。采用竞争性自适应重加权算法(CARS)和连续投影算法(SPA)进行黑果腺肋花楸黄酮、多糖特征光谱波段选取,将2种方法选取的光谱数据结合偏最小二乘回归法(PLS)、极限学习机(ELM)、支持向量机(SVM)进行建模对比,选出预测效果最佳的算法模型。结果表明,7种光谱预处理方法中,MSC对原始光谱的处理效果最佳,在此处理下黄酮含量预...     

一类特殊的仓库配置问题

本文研究一类特殊的仓库配置问题.求解这类问题等价于在边e_(ij)的权为w_(ij)=p_id_j的一个加权完备二部分图K_(n,n)中找最小加权完美匹配,而p_i、d_j均为非负(i,j=1,2,…,n).本文没有用复杂性为O(n~3)的匈牙利算法来解这类问题,而是提出了一个更为简单的、复杂性几乎为O(nlogn)的新算法,同时还讨论了在铁路系统中的某些应用.§1.引言铁路车站、大型汽车站以及码头、仓库等会遇到如何配置货位,以达到经济、方便的目的.所谓经济,一般是指货物搬运的运输量“吨公里”最小.例如在铁路零担中转站,停放货     

一类排序问题及其求解

我们研究如下的排序问题:有 n 批“顾客”(零件、原料、…),它们的批号为1,2,…,n.分别进入 m 个“服务台”(机器,仓库,…)接受服务(加工,处理,…).只要 m 个服务台有一个空闲,那么一批顾客便同时到达,排队等侯服务.设每个顾客所需的服务时间是相同的,而第 i 个服务台需要接纳第 j 批顾客的数量为 q_(ij),试确定 n 批顾客的输入顺序σ,使最大队长总和 f_1(σ)最小.     

中红外光谱和支持向量机的梅花鹿角帽粉假冒与掺假识别模型

梅花鹿角帽具有较高的药用和经济价值,因其质地坚硬,故一般选择打成粉末使用。消费者很难从外观上去判别梅花鹿角帽粉是否为正品,导致其假冒与掺假事件层出不穷。因此,提出利用中红外光谱（FTIR）结合机器学习探索一种识别梅花鹿角帽粉假冒与掺假的方法,以解决用马鹿角帽粉、梅花鹿骨粉假冒梅花鹿角帽粉和牛骨粉掺假梅花鹿角帽粉的问题。从黑龙江、吉林、辽宁3省共5个地区采集梅花鹿角帽、马鹿角帽、梅花鹿骨各120份,共360份样品;牛骨采购于长春市南关区农贸市场,使用牛骨粉掺假梅花鹿角帽粉,掺假比例分别为5%,10%,20%,30%,40%,50%,每种比例各20份,共120份。采集样品中红外光谱数据,多元散射校正（MSC）对光谱进行预处理,经K-S法抽样,按3∶1的比例划分训练集和测试集后,对光谱数据进行归一化（normalization）和主成分（PCA）分析降维处理。根据主成分个数累积贡献率≥85%,主成分特征值≥1原则,选择前7个主成分构成降维后的光谱数据;分别将全光谱（FS）数据与PCA降维后的光谱数据作为模型输入,建立支持向量机(SVM)、随机森林(RF)、极限学习机(ELM)识别模型。结果表明,梅花鹿角帽粉正品与假冒伪品、掺假次品的波谱在波段1 300～1 800和2 800～3 600 cm-1处存在差异,尤其是掺假比例≥10%以上的梅花鹿角帽粉与纯梅花鹿角帽粉差异明显。在识别梅花鹿角帽粉假冒与掺假模型中,FS-SVM,PCA-SVM,FS-RF模型均有很好的识别效果,其训练集与测试集识别率均为100%,其他模型识别率均低于98%。从简化模型的角度上比较,FS-SVM,FS-RF建模时间分别为4 859.36和1 818.96 s,而PCA-SVM建模时间仅为19.91 s。因此,PCA-SVM在6种识别模型中整体效果最佳。研究表明,中红外光谱结合支持向量机建模可以作为一种快速、准确、无损鉴别梅花鹿角帽粉假冒与掺假的有效识别方法。     

中红外光谱结合机器学习对不同产地平菇鉴别

平菇味道鲜美、营养丰富，深受消费者喜爱。平菇在我国的栽培范围较广，产地分散，每个产地的气候条件、栽培基质、栽培方式的差异，使不同产地生产的平菇在口感、营养价值方面会有不同。为规范平菇产品的市场管理，更为打造区域内特色平菇品牌，借助中红外光谱技术无污染、高效、低成本等特点，突破目前化学分析、生物学鉴别方法的限制，提出一种中红外光谱结合机器学习鉴别不同产地平菇的方法。对10个不同产地的平菇子实体进行红外光谱数据采集，每个地区各60份共600份样本。光谱数据经分析表明，在波段530～1 660 cm^-1范围内红外光谱的相关性表现出较明显的差异。同时，基于K-S法按照训练集和测试集比例为7∶3对样品划分，得训练集为420份，测试集为180份。采用多元散射校正(MSC),标准正态变量变换(SNV),平滑(SG),一阶导数(FD),二阶导数(SD)等预处理方法进行光谱优化，去除噪声，并结合支持向量机(SVM)进行初步建模对比，得出MSC预处理后光谱数据差异性最大，预测集识别效果最好为84.44%。将MSC光谱数据进行0～1区间的归一化处理，并采用主成分分析(PCA)对其进行降...