网站原创2001年全国大学生数学建模竞赛题目(本科组)
全部题目(包括数据)可以从以下下载:
csiam.edu./mcmsciput.163.网易教育频道
A题血管的三维重建·
断面可用于了解生物组织,器官等的形态.例如,将样本染色后切成厚约如m的切片,
在显微镜下观察该横断面的组织形态结构.如果用切片机连续不断地将样本切成数十,成百的平行切片,可依次逐片观察.根据拍照并采样得到的平行切片数字图象,运用计算机可重建组织,器官等准确的三维形态.
检测设某些血管可视为一类特殊的管道,该管道的表面是由球心沿着某一曲线(称为中轴线)的球滚动包络而成.例如圆柱就是这样一种管道,其中轴线为直线,由半径固定的球滚动包络形成.
现有某管道的相继100张平行切片图象,记录了管道与切片的交.图象文件名依次为0.bmp,1.bmp,等,99.bmp,格式均为BMP,宽,高均为512个象素(pixel).为简化起见,检测设:管道中轴线与每张切片有且只有一个交点,球半径固定,切片间距及图象象素的尺寸均为1.
取坐标系的Z轴垂直于切片,第1张切片为平面Z等于0,第100张切片为平面Z等于99.Z等于Z切片图象中象素的坐标依它们在文件中出现的前后次序为
(—256,—256,Z),(—256,—255,Z),等(—256,255,Z)
(—255,—256,Z),(—255,—255,Z),等(—255,255,Z)
等
(255,—256,Z),(255,—255,Z),等(255,255,Z).
试计算管道的中轴线与半径,给出具体的算法,并绘制中轴线在XY,YZ,ZX平面的投影图.下面是100张平行切片图象中的6张,全部图象请从网上下载.
关于BMP图象格式可参考:
1.《VisualC++数字图象处理》第12页2.3.1节.何斌等编着,人民邮电出版社,2001年4月.
2.dcs.ed.ac.uk/home/mxr/gfx/2d/BMP.txt
B题公交车调度
公共交通是城市交通的重要组成部分,作好公交车的调度对于完善城市交通环境,改进市民出行状况,提高公交公司的经济和社会效益,都具有重要意义.下面考虑一条公交线路上公交车的调度问题,其数据来自我国一座特大城市某条公交线路的客流调查和运营资料.
该条公交线路上行方向共14站,下行方向共13站,下面给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计.公交公司配给该线路同一型号的大客车,每辆标准载客100人,据统计客车在该线路上运行的平均速度为20公里/小时.运营调度要求,乘客候车时间一般不要超过10分钟,早高峰时一般不要超过5分钟,车辆满载率不应超过120%,一般也不要低于50%.
试根据这些资料和要求,为该线路设计一个便于操作的全天(工作日)的公交车调度方案,包括两个起点站的发车时刻表,一共需要多少辆车,这个方案以怎样的程度照顾到了乘客和公交公司双方的利益,等等.
如何将这个调度问题抽象成一个明确,完整的数学模型,指出求解模型的方法,根据实际问题的要求,如果要设计更好的调度方案,应如何采集运营数据.
站名A13A12AllA10A9A8A7A6A5A4A3A2A1A0站间距(公里)1.60.510.732.041.262.2911.20.4111.030.535:00—6:00上3716052437690488385264545110下08913204845813218242585576:00—7:00上1990376333256589594315622510176308307680下0991051642395885428004072083002889216157:00—8:00上3626634528447948868523958904259465454990下0205227272461105810971793801469560636187114598:00—9:00上2064322305235477549271486439157275234600下010612316930063462197144024533940811327599:00—10:00上118620516614728130417232426778143162360下0817512018140741155125013618723377448310:00—11:00上92315112010821521411921220175123112260下052558113629928044217810515316753238511:00—12:00上95718115713325426413525326074138117300下054588413132129142019611915915353434012:00—13:00上87314114010821520412923222165103112260下046497111126325638916411113414848833313:00—14:00上779141103841861851032111736610897230下03941701032211972971378511311638426314:00—15:00上6251041088216218090185170497585200下036394778189176339139809712038323915:00—16:00上635124988215218080185150498585200下0363957882091963391298010711035322916:00—17:00上1493299240199396404210428390120208197490
下0808513519445044173133515725525180055717:00—18:00上2016379311230497479296586508140250259610下0110118171257694573957390253293378122879318:00—19:00上69112410789167165108201194539382220下04548801082372313901508913112542833619:00—20,00上3506455469185508889274847110下0222334631161081968348646620413920:00—21:00上304504336727540776022383790下01617243880841435934464716011721:00—22:00上209373226535529475216282760下0141421337863125623040411289222:00—23:00上193325535513210下03358181727127993221站名A0A2A3A4A5A6A7A8A9A10AllA12A13站间距(公里)1.5610.441,20.972.291.320.7310,51,625:00—6:00上22342443331100下02116775342396:00—7:00上795143167841511881091371304553160下070404018420519514793109751082717:00—8:00上2328380427224420455272343331126138450下02941561577107808495453744442653739588:00—9:00上27063744922244045323333453541201534600下026615814975682785652936742823737611679:00—10:00上15562042741252353081622031987699270下01571008041051149833619927613621955610:00—11:00上902147183821552061201501435059180下010359592463463201911471859615443811:00—12:00上847130132671271501081041074148150下09448481992382561751221436812834612:00—13:00上70690118661051449295883440120下07040401742152051271031196598261
13:00—14:00上7709712659102133971021043643130下0754343166210209136901276011530914:00—15:00上839133156691301651011181204249150
DNA序列的分类模型
汤诗杰,周亮,王晓玲
指导老师:孙广中
(中国科技大学,合肥230026)
编者按:本文提出了DNA序列分类的三种模型.其一,基于A,G,T,C四种碱基出现的频率,具二利用了同—等碱基在序列中的间隔.这一信息是单纯考虑频率所不能包含的,在第三种模型中.作者把DNA序列视为一个信息流.考虑每增加一个字符所带来的信息增量.尽管文中信息量的定义方式仍可讨论,但本文思想新颖活跃,有其独特之处.本文最后的分类方法.足以上三种的综合使用.
摘 要:本文针对DNA序列分类这个实际问题,提出了相应的数学模型.为了很好的体现DNA序列的局
部性和全局性的特征.我们给出厂衡量分类方法优劣的标准,即在满足一定限制条件的情况下.是否能充分反映序列的各方面特性.
依据我们提出的判别标准.单一标准的分类是无法满足要求的,我们的方法是侧重点不同的三种方法的综合集成.这三种方法分别体现了序列中元素出现的概率,序列中元素出现的周期性,序列所带有的信息含量.利用这个方法.完成了对未知类型的人工序列及自然序列的分类工作.最后.对分类模型的优缺点进行了分析,并就模型的推广作了讨论.
1问题的提出(略)
2问题的分析
这是一个比较典型的分类问题,为了表述的严格和方便,我们用数学的方法来重述这个问题.已知字母序列其中,有字符序列集合A,B,满足并当时,现要求考虑当与集合A及集合B的关系.
在这里,问题的关键就是要从已知的分好类的20个字母序列中提取用于分类的特征.知道了这些特征,我们就可以比较容易的对那些未标明类型的序列进行分类.下面我们将首先对用于分类的标准问题进行必要的讨论.
3分类的标准及评价
首先,我们提取的特征应该满足以下两个条件:
(1)所取特征必须可以标志A组和B组.也就是说,我们利用这些特征应该可以很好的区分已经标示分类的20个序列.这是比较显然的一个理由.
(2)所取特征必须是有一定的实际意义的.这一点是决不能被忽视的.比如,如果不考虑模型的实际意义,我们就可以以序列的开头字母为分类标准:已知在B类中的十个序列都是以gt开始的,而已知在A类中10个序列没有以z2开始的,甚至以算开始的都没有.显然这是满足上面的第一个条件的.如果仅因此就认为这种特征是主要的,并简单的利用这个特征将所有待分类的序列分成两类,显然是不甚合理的.
对于这样的一个复杂的分类问题,需要考虑的因素很多,也是就说,可供我们使用的分类特征有许多.如何从众多的因素中提取分类的主要因素,是我们处理这个问题的困难之处.上面的第一个条件是我们的分类方法所必须满足的,可以看作是个限制条件,而第二个条件是我们在设计分类方法时必须考虑到的,可以看作是对分类方法优劣的一种衡量,是某种意义下的目标函数.
4模型的建立及分析
由上面的分析可知,由于DNA序列本身的复杂性,我们很难在不知道确切的分类标准的情况下,使用单一的方法来处理这个分类问题.由于,DNA序列同时具有局部性和全局性的特征,我们尝试综合使用几种设计思想不同的方法来处理这个问题,以使该分类方法具有好的分类性能和相当的健壮性.
下面我们先从不同的角度出发,提出三种侧重点不同的分类方法,第一种从频率角度出发,第二种从字母出现的周期性的角度出发,第三种从序列所带的某方面的信息量出发,并给出它们单独使用时的分类结果.我们认为,这三方面综合考虑,可以较好的体现出序列各个方面的特征,最后,从这三种方法出发,得到一个综合系统的分类方法,并利用它得到了最终的182个序列的分类结果.
方法1基于字母出现频率
不同段的DNA中,每个碱基出现的概率并不相同,从生物理论中,我们知道,编码蛋白质的DNA中G,C含量偏高,而非编码蛋白质的DNA中A,T含量偏高.因此,A,G,T,C的频率中会含有很多的信息,下面给出A,B组的频率统计.见表1,表2(略).
由统计的数字可以看出,A组的碱基构成与B组的碱基构成有较大的不同.A组的G含量较高,B组的T含量较高.为做定量化的分析,引入数学中的内积概念,即将A,T,G,C的频率分别作为四维向量的四个分量(),现在我们得到两组向量,然后将未知的序列21～40作为一个新的向量C,要将它归人A组或B组,我们可以尝试在Hilbert空间中将向量归一化后求C与A组和B组的平均距离.记,,为归一化后的向量.为此,我们计算内积和,其中内积定义为欧氏度量引导出的内积(c1,c2,c3,).(a1,a2,a3,a4)等于clal+c2a2+c303+a4.即
内积小的两个序列,我们可以认为它们的相关性小,而内积大的序列,我们就认为其相关性大.因此,如果则认为C应归人A类,否则认为它应归人B类.
由此,我们找到了区分C组的一种方法,这种比较的方法,我们可以归纳为一个目标函数F1(l),即
表3
未知的序号与A组的内积与B组的内积属于的类型未知的序号与A组的内积与B组的内积属于的类型1
2
3
4
5
6
7
8
9
100.815781
0.926922
0.939727
0.788524
0.948194
0.801201
0.953019
.0746071
0.931007
0.8977740.938814
0.803952
0.656827
0.937135
0.772076
0.930121
0.76695
0.968035
0.613193
0.844082B
A
A
B
A
B
A
B
A
A11
12
13
14
15
16
17
18
19
200.852231
0.866976
0.860955
0.961689
0.960322
0.904282
0.944724
0.75862
0.885631
0.755840.920957
0.853967
0917122
0.67678
0.739089
0.747578
0.723664
0.954652
0.811837
0.941B
A
B
A
A
A
A
B
A
B
方法一讨论这种方法是从概率统计的角度分析问题,通过对每个字母出现频率的计算,找出A,B两类DNA链中的频率特性,建立四维向量空间,然后对待求分类的序列统计频率,与已知分类的向量进行内积运算,找出量化的关联性,从而将其分类.但这种方法也有其局限性,在统计字母出现的频率时,忽略了字母所在位置以及各个字母之间的相互关系,造成用这种方法对已知分类的序列进行检验时,个别频率特性不明显的序列不太容易分类.所以,这种方法虽然有其科学性,但还不够完善,不能完全体现序列的所有特征.
方法二基于字母出现周期性
在以上进行了基于字母出现频率的分类之后,我们认为,一个序列所含的信息远不止每个字母出现的频率,还有字母出现和它前后若干个字母的相关联性,字母在序列中出现的规律性等等.前一个问题我们留到下面讨论,现在我们想办法处理后一个问题.
对于某单个字母,以d为例,检测设它在序列中第九,扎.等,扎+,,个位置出现,我们试图找出这些数字之间的关联.首先,可以认识到考查乙的分布及绝对值是意义不大的,因为序列是一大段DNA中的一'个片断,片断的起始段不同会导致乙的不同.于是为了抵消打的线性位移,考虑下面一组值
即字母"出现的间距.
可以看出,序列的大小包含的信息是"的"稠密度",也可看成一个与频率有关的量,前面已经处理过.所以我们可以考虑序列的波动幅度,幅度越小,说明的值越趋于统一,即a的出现周期性越大.而表征波动幅度的量在统计·中是中心矩.现求,,的二阶中心矩,即方差.
同理,可以求出Varg,,Vart,,Varc,
由所得数据知,对Varg与Vart,上述方法对A,B组的区分率很高,就有良好的可分辨性.为了强调这种特征的显着性,我们用F2等于Varg/Vart作为这种方法的目标函数.
由图1可以看出点与原点连线的斜率在A组中和B组中有显着差别,根据这个特征,A组和B组可以很好地区分开来.并且较好地弥补了方法一中的不全面之处.
方法二讨论这种方法是从序列中相邻相同字母之间的距离即字母出现的周期性着手分析的.它统计了每个字母在序列中两次出现的间隔,并且用方差度量这种间隔的波动大小,由此找到了一个能较好区分A,B组的目标函数,综合地考虑了序列全局和局部的性质.
方法3基于序列熵值
我们可以把一串DNA序列看成一个信息流,这与生物学的基础知识是相应的.关于
A,B的分类,可以考虑其单位序列所含信息量(即熵)的多少.从直观上来看,我们可以认
为,重复得越多,信息量越少..这是我们通过观察A,B组的特点而归纳出的方法.
设序列为L等于(a1,a2,a3,等,an),前m个字符所带的信息量为记
即为加上第m个字母之后所增加的信息量.然后,由,得为整个序列所带的信息量.即为单位长度所带的信息量,现在的问题就归结为如何找出一个合适的.
我们有理由认为:g具有以下性质:
性质即任意加上一个字符,它或多或少带有一定信息量,
性质2:第m个字符(或者是以它结尾的较短序列)与前面的序列(信息流)重复得越
多,的值必然越小,
性质3:第m个字符(或者是以它结尾的较短序列)如果和与它靠得越近的重复,
的值越小,和与它离得越远的重复,的值越大,
性质
对此,我们可以构造如下函数:
其中b为防止分母为零而设的一个小正数,
以第m-t个字符结尾的i字串且与以第t个字符结尾的i字串完全相同
否则
a为一个小于1的数,其存在体现了A/的性质3,即如果越近的位置出现重复,认为字串
信息量越少,反之较多.
的表达式中,t表示两个相同字串之间的距离,i表示宇串长度,这个表达式定量的给出距离和信息量之间的关系.
又由于长度不同的字串重复对信息量的影响是不同的,所以必须在前乘上一个权值
,由概率统计的知识可知,这种影响是呈指数上升的,则可选择一适当的常数c>,1,使得ti等于,这个表达式定量的给出长度和信息量之间的关系.
可以认为,宇串长度太大的重复非常少见,则可将户取为某一固定的正数.那么,给出a,b,c,p参数,就可以把严格确定下来.通过反复上机搜索,我们认为,取,即只检查长度为1到6的字串即可.
另外,职可以将A,B组值分得较开,并可以用来处理未知数据.
方法三讨论这种方法从序列的信息量(熵)人手,认为当序列中有大量的重复元素时,信息量就会比重复少的序列所含有的信息少.所以,其侧重点是是序列前后的重复性,也就是序列元素的相关性.从所给的A,B两类中可以很清楚地看到B中序列重复量大,所含的信息明显少于A组,而这个特征就被我们定义的熵函数凸显出来.将DNA序列看成一个信息流的方法由于其在实际问题中的广泛背景,将会是一个很有价值的想法,统计学和信息论的一套非常成熟的强大工具也会在DNA研究中发挥巨大的作用.
综合模型的建立
以上我们分别用三种方法得出了分类方案,这三种方案分别基于三种不同的方面对问题进行分析.第一种方法主要考虑的是单个字母出现的频率,第二种方法主要考虑每个字母的出现是否具有周期性,而第三种方法则考虑的是每条DNA所蕴含的信息量.我们将这三种方法对A,B组自身进行了检验,都得到了较令人满意的结果,但因为每个模型都只突出考虑序列某一方面的特征,所以,总有一些不尽如人意的地方,于是,我们认为应该把三种方法综合起来考虑,使序列各方面的特征都能得到体现,以使分类更加科学.
下面就是我们将几种方法综合考虑得到最后结果.
以上我们用三种方法得到了三个目标函数:,这三个目标函数可以作为分类的判别标准.将它们看成定义在序列空间,作用于实轴上的函数.现在,我们必须找到一个函数F,使得F可以体现序列的各个特征.
由于的值域范围差别很大,为了有效的比较这三个函数,我们必须
将它们归一化,将看成一定义在上空间上的随机变量,A,为L的子集,则将归一化得
(1)
代入(1)即得
现估计投射L的点到实轴上后,的分界点其中
以为例,A的10个样本点和B的10个样本点不能被一个分界点分开,有极大似然估计的思想,分界点应该把尽可能多的点分开,即
由于的分布未知,故只能检测设其满足较均匀的分布,则A,B的分界点的最好估计为而(由g的定义),恰好是分界点的最佳估计.
同理,分界是对应分界点的最佳估计.
令,则其分界点
由F的构造方法知,F作用到A样本上大于零,作用到B样本上小于零,我们确定适当的权值,以此作为A,B的分类法即可.根据不同的实际情况,可以相应调节这三个权值,以体现分类中的不同因素所在的比重,在下面的计算中,我们简单的取a1等于1,a2等于-1,a3等于0.5.得到的结果如表4,表5所示.
表4
序号目标函数值序号目标函数值序号目标函数值序号目标函数值A
组1
2
3
4
51.80288
1.75894
2.5887
0.27582
2.1781A
组6
7
8
9
101.75355
1.25115
1.41371
1.9011
1.97282B
组11
12
13
14
15-1.38528
-1.22372
-0.940004
-0.93612
-2.27462B
组16
17
18
19
20-2.60295
-0.0165438
-1.31022
-2.6043
-3.603表5
序号目标函数值类别序号目标函数值类别21
22
23
24
25
26
27
28
29
30-1.96454
0.873279
2.32887
-1.48005
1.21328
-1.184
1.22569
-3.71616
2.69272
0.550393B
A
A
B
A
B
A
B
A
A31
32
33
34
35
36
37
38
39
40-1.06638
-0.668504
-0.877053
2.60904
1.69535
1.22298
1.83991
-3.01466
0.499763
-2.77993B
B
B
A
A
A
A
B
A
B由以上数据可以看出,我们构造的目标函数具有较好的区分度.对于A组,目标函数值都大于零,而对B组,目标函数值都小于零.也就是说,用这种方法,对A,B组样本的区分率已达到了100%.正如前面所说,这种方法综合了序列中的许多信息.因此,我们完全可以采用这个标准来区分C组.表5是对C组区分的结果.
对20个未标明分类的人工序列的分类结果为:
A类:22,23,25,27,29,30,34,35,36,37,39B类:2l,24,26,28,31,32,33,38,40
同样的,我们利用这种方法对所给的182个自然序列进行了分类,结果如下所示(略).
5模型的评价及推广
在我们的模型基础上提出的分类方法可以很好的验证已知的20个序列,并且很好的完成了对未知类型序列的分类.我们认为这种模型,同时考虑了序列中元素的局部性质和序列的全局性质,具有相当的实际背景.当我们知道分类标准的更多信息时,我们可以很方便的调整模型中的参数,使之符合新的情况,具有很好的自学习性.但这个模型比较复杂,在实际计算中参数选择需要花费大量计算时间进行搜索.
我们在模型中使用的基于信息流的方法中,如果选取更为合适的熵函数,一定可以使它更加符合实际情况,在三种方法综合的时候,所取的权值也是可以采用更为有效的方法选取,如应用层次分析法,还可以选取其他分类方法加入.这些都是本模型可以改进的地方.
;研究,这里的结构指的是在DAN序列中重复出现的有特征的片断,这种重复出现形成丁规律.由于结构的含义是广泛的,担心学生因此而无从下手,我们特别举出三种结构为例,其目的仅仅是为了说明,DNA序列貌似随机地由A,T,C,G四个字符组成,但它之所以有"万能"的功能,正是由于在随机的外衣下隐藏着大量的结构,正是这种结构决定了功能.因此,在生物信息学中,人们普遍相信这样一个信条:序列——结构一一功能.这一信条引导人们成功地在DNA序列中挖掘出许多与生物功能相关的自然规律.在A题中举出的三种结构是十分基础而且在科学界广泛为人们所接受的.一种是四种碱基的丰度,对于DNA序列的不同的片段常常表现出碱基丰度的差别,因此碱基的丰度往往成为区别不同序列片段的特征,第二种是三联子对蛋白质的编码,它首先由发现DNA双螺旋结构的克里克和南非的分子生物学家西德尼·布伦纳确定的,这种不重叠的三联子组成的编码区(Exon)与非编码区的交替出现形成了DNA序列中一个重要的结构.如果读者想了解这一方面的知识只要在互联网上搜索"Exon—IntronStructure",你会得到供选读的大量文献,A题举的第三个例子是所谓DNA序列的长程相关性,这一规律最早由C·K.Peng等人在1992年Nature上报导[3],此后人们研究了各种DNA长序列,分别发现了DNA序列在大尺度的范围内具有统计相关性,然而这种相关性的细节及意义至今还是一个迷.A题中举出这三种结构,也为了说明在DNA序列的结构中既有大尺度全局性的,也有局部性的,研究和发现DNA序列中的这些规律均有重要意义.正由于这种结构的多样性和一般性,为求解A题确定了解法的开放性.虽然事实上许多试卷都把这一结构理解成为编码区与非编码区,但这种局限性的理解并没有比一般性理解结构的试卷更好些.A题定义结构的一般性,有两方面的理由.一方面希望在求解A题时对生物知识的依赖不要太多,除了最基本的DNA序列的背景外,解题中并不需要有更多的基因组结构的知识(例如,是否知道Exon与Intron并无大关系).这样做是为了在"数学建模"这一基本的专业性质下平等.第二个方面就是希望这种开放性,可以使从初等到高等的许多数学模型化方法均能对A题做出一定水平的解答.而且也希望发现一些富有创造性的,十分有效的方法.事实上,本届比赛中也的确涌现出大量富有创意的方法,实在令命题者兴奋不已.
解答方法的开放性,是A题的命题领域本身就决定了的.事实上,仅在编码区预测的文献中就有了许多不同的方法.有通过核苷酸片段差异的区分方法[4],同源比较算法[5],隐马尔可夫模型(HiddenMarkovModel,HMM).这种方法将DNA序列的形成看作随机过程,而HMM可自动找出其隐藏的统计规律性[6].大家熟知的动态规划方法[7],以及傅立叶分析[8],线性判别分析(LinearDiscriminantAnalysis,LDA)[9].此外许多专门的方法用于DNA的结构分析与寻找:法则系统(rule—basedsystem)[10],语言系统(1inguistic)[11],决策树(decisiontree)[12].这些方法对于从DNA序列中找出编码序列均有很好效果,有些准确率
| 有关论文范文主题研究: | 关于序列的论文范文 | 大学生适用: | 大学毕业论文、函授论文 |
|---|---|---|---|
| 相关参考文献下载数量: | 33 | 写作解决问题: | 怎么撰写 |
| 毕业论文开题报告: | 论文提纲、论文目录 | 职称论文适用: | 期刊发表、职称评中级 |
| 所属大学生专业类别: | 怎么撰写 | 论文题目推荐度: | 经典题目 |
高达90%.有兴趣的读者可以在最近出版的《解码生命》[13]一书中查到有关评论.
A题将DNA结构的研究具体化为不同序列的分类,这种分类对于寻找出序列的结构
具有基础的价值.它是寻找结构的一种简化而有效的变形,这种具体化在帮助学生模型化
是有益的.然而这种具体化也给出题带来一定困难,为了方便广大参赛队对这种分类方法
的理解与数值实验,我们设计了两套数据.一套是人工构造的数据,而另——套是来源于自然的DNA数据库.显然这两套数据既有联系又有明显的差别,这种差别使得企图用比较简单的方法而不加区别地处理这两类数据将不会得到好的效果.正如自然界给人类提出的问题不太可能恰好满足我们希望的数学条件一样,A题也要求解题者具有立足于实际,从有限而不完全的已知数据去探索更复杂的数据中的未知规律这样一种研究素质.
4阅卷随想
在评阅试卷时,老师们对年轻学子在A题解法中表现出的热情,智慧,严谨和富予创造性都留下极深刻的印象.作为命题人,更对本科学生能在短短的三天中所做出的成果惊喜,并在许多十分聪明的解法中学习到了新的东西.A题的试卷几乎令所有阅卷老师叹服:中国大学生年轻有为！
学生论文的立意大多在"特征提取一分类方法"这一模式,这显然是最容易想到的,大多数试卷也在这一立意之下,选择好的方法而得到较好的结果.特征的选择,首先易于让人想到的是A,T,C,G四个字符在字符串中出现的频率,这在文献中常称为"单个碱基丰度",单纯使用这一特征,许多学生的文章对人工数据得到好的结果,但对后面182个序列的分类却常常不太理想.在优秀论文中浙江大学的一个队将这种特征提取后形成四维特征向量,然后分别用欧氏距离,马氏距离分类法和Fisher判别模型,对人工数据得到理想的分类,对自然数据(182个)也得到很高的分类正确率,是这一类算法中较突出的卷例.另有一些试卷在这一特征基础上考虑到字符的顺序,将模型做得更复杂些.更多的论文是用4个字符的字符串作为特征,由于这时特征一下子增加了许多,于是需要从其中评判挑选并排出特征的重要性顺序,这种特征的提取往往可以得到较好的效果.特别是对于自然序列,大连理工大学的一个队通过概率统计方法首先对已知的人工序列集进行特征提取,从而形成特征向量较为全面地表达分类特征,当然也出现了高维问题的计算复杂性,他们得到了很好的分类效果.值得指出的是,由于竞赛题一方面源于生物学实际问题,同时又相对地独立于生物而形成适当抽象的"试题",因此试题并不是基因组中某种结构的翻版.有些试卷过多地研究了生物学的来源,而且将A题仅局限于他们所想象的结构(例如Exon结构),于是三联子编码成为分类的唯一特征,而三联码的不重叠性又使他们在阅读框的起始位置前不知所措,以至所产生的结果不理想.
在分类方法上,统计的方法(特别是聚类方法)是最易于想到的,许多试卷从而构造了好的方法.但是简单而不加修正地使用统计方法并不能得到好的结果.这是因为人工已知序列的样本数只有20个,而且都很短,待分类的自然数据样本数182且都长得多,因此从小样本中得到的统计规律在处理大样本时效果显然不佳.这是众多用统计方法所得到结果不理想的一个直接原因.有些学生看到并指出了这一点,而且有的试卷注意到人工数据与自然数据的生物学的差别而在分类自然序列时修改了分类方法而得到较好的结果,显然概念的清楚与思维的灵活得到很好的统一.用各种方式构造判别函数的方法以及神经网络的方法,特别对于非线性系统的识别很有效.因此通过构造各种神经网络来进行分类,更多的队得到很好的效果.例如大连理工大学的一个队,用统计方法提取较好的特征又用BP网络进行分类,方法严谨,考虑细致,对自然序列的分类正确率高达88%.而科技大学的一个队通过对神经网络方法的逐层的改进,又辅以统计方法,产生了比较精细的网络算法,也得到分类自然数据的正确率达65%的好效果.
除了上述大量"正规方法"以外,一些试卷有创意地提出了一些十分新颖的思想,有些还取得了很好的效果.例如中国科技大学的一个队将序列看作信息流,注意到字母出现的特征是熵的改变,是十分新意的,他们最终又将设计好的几个模型形成综合判别的目标函数,也得到好的分类效果,对自然数据分类正确性达58%.而北京大学的一个队将DNA字符串看作一篇文章,而利用了类似文本分类中的特征判别方法定义关 键 词标准,进而使用优选法,找出关 键 词的特征,然后使用层次分类.他们的方法精细,尽管分类最终效果并不十分理想,仍不失为值得一读的好文章.由于篇幅有限,有些文章虽然没有作为优秀论文刊出,但是在其中仍然表现出学生丰富的想象力和创造精神.—篇十分有趣的文章是大连理工大学的另一个队,这些学生既没有拘泥于"特征提取+分类"的模式,也没有局限自己的思维于"概率统计""神经网络""判别函数"等"大路"方法.他们深入地分析了序列问题的生物来源,又观察人工序列的数学结构和数值试验结果,在一些DNA序列几何表达文献的启发下,提出了简捷的几何分类法,得到了出色的分类结果.对自然数据分类的正确率高达94%.而且这种不依赖训练集的方法,属于目前研究基因组结构的令人关注的方向.
应当指出,科研能力的表现是多方面的.在试卷中,我们注意到许多学生十分用心于科学文献的检索,阅读与借鉴.例如一些试卷研究了我国着名学者,中科院院士张春霆教授的Z曲线方法[14],并简化用于A题分类(例如中国科技大学的另一个队),也取得好的结果.此外,特别值得指出的是香港城市大学的论文,该文的思路清晰,表述严谨,图表数据完整,行文流畅,作为本科学生三天完成的科研论文值得赞赏！
综上所述,作为A题的命题人,原先的担心与顾虑被事实扫得干干净净.学生的聪明才智,扎实的数学功底和运用于实际问题的灵活性,创造性证明,中国大学生完全可以适应更贴近科学研究实际,更贴近工程技术实际,更贴近社会经济生活实际的数学建模比赛问题.
中国大学生在数学建模比赛的锻炼中必将大大提高应用数学的能力,在二十
新科技的发展中做出出色的成绩.
指出每一行最小值与最大值之差最大的一行,第i行,找出该行的最小值为②令
③C的第j列的所有数据改为,
④如果,第i个供应点的供应量已达上限,令C的第i行的所有数据为.
对于问题一和问题三,我们用改进的伏格尔法求得方案的总费用分别为1279019万元和1407383万元.
(2)调整优化
调整优化是将一个离最优解很近的初始解调整到在调整算法下无法更优的程度.调整优化分两个部分,第一部分是用试探法对供应点的供应量进行优化.第二部分是用迭代法对供应点进行两两对调优化.
*试探法调整优化实际供应量在500以下的供应点
对每个实际供应量在500以·F的供应点,只存在两种合理的优化方法:一种是将其供应量增加到500,另一种是将其供应量减少到0.试探法将分别试探进行下列两种优化:
其一是先将供应点的供应量强行提升至500,使用改进的伏格尔法的优先顺序,从其它供应点负责供应的需求点抢夺一部分,再用对调法优化至无法更优,得出一个总费用F1,其二是先将该供应点的供应量调整为0,其原供应的需求点由其它钢厂用改进的伏格尔法的优先顺序补充,再用对调法优化至无法更优,得出一个总费用F2那么,就应当采取总费用较小的方法.
例如,对于第一问,按改进的伏格尔法获得的初始方案中,S7的用量仅为245,优化时,试探将其降为0和将其提升为500后的最优结果,分别为1279019万元和1280506万元,则说明应将S,降为0.
*用迭代法进行对调优化
改进的伏格尔法给出的初始值虽然很接近最优值,但仍有不足之处,即可能存在两个需求点,调换供应点能使总费用更小,例如,需求点a和6的供应点是x和y,费用分别是C(x,a)和C(y,b),如果让y供应a,x供应b的话,费用将是C(y,a)和r(c,b),如果:
C(y,a)+r(x,b)<,C(x,a)+C(y,b)
则说明对调后总费用更低.
因此,我们可以采用迭代法对任意两个需求点的供应点两两对调至无法更优.
由于一共只有m等于7个供应点,所以两两对调的可行方案一共有种,因此,两两对调供应点的方法是可行的,具体步骤如下:
Stepl对于任意两个供应点xi和xji等于1,2,等,mj等于1,2,等,m
1)找出所有由xi供应的需求点,构成点集A等于{a1,a2,c}
2)找出所有由xj供应的需求点,构成点集B等于{b1,b2,等}
3)对A中所有点,如果改用xj来供应,将付出的代价构成向量
4)对B中所有点,如果改用xi来供应,将付出的代价构成向量
5)对分别按升序排序.
6)同时对从前向后遍历,如果(表示对调供应者将降低总费用),则对调其供应者,直到出现为止.
Step2统计这轮对调后的总费用是否比原来的总费用F有明显的进步,即.如果有明显的进步,则再回Stepl执行,否则结束优化.
令人振奋的是,采用改进的最小元素法和改进的伏格尔法得到问题一的初始方案分别采用这种优化方案后,竟都达到了相同的最小费用:1279019万元.
(3)结果(略)