运筹学发展概况 (四)

组合优化

组合优化是20 世纪60 年代逐渐发展起来的一个交叉学科分支,它的研究对象是有限集合上的极值问题。一个组合优化问题由3 部分构成:已知条件的输入,可行解的描述,目标函数的定义。经典的组合优化问题包括网络流、旅行商、排序、装箱、着色、覆盖、最短网络等等。组合优化的一个理论基础是计算复杂性理论,据此组合优化可以分为两类:P-问题类和NP-难问题类;属于前者的问题有多项式时间算法,属于后者的问题一般认为不存在多项式时间算法,通常采用穷举法、启发式算法和近似算法等方法求解。

组合优化与图论、组合学、数理逻辑等有密切关系,在计算机科学、信息科学、管理科学和生命科学等学科有广泛的应用。

图论及算法

1736 年欧拉解决了哥尼斯堡的七桥问题,这被公认为图论的第一个结果。此后的200 多年里,图论并不被视为是数学的一个分支,图论的问题通常被看作一类智力游戏。然而,自上个世纪30 年代始,图论通过其广泛的应用以及与数学其他分支的紧密联系日显其重要性。尤其是,图论作为计算机科学的基础之一,在运筹学中扮演着不可或缺的角色,很多非常难解的组合优化问题都属于NP-完全的图论问题。在图论近几十年的研究中,学者们在取得一系列重要成果的同时,提出了包括整数流、子图覆盖和经典拉姆齐函数的估值在内的许多猜想或未解的难题。

未来受人关注的一些课题包括:

(1)图论中大多数结果都可以推广到超图中(通常推广方式不止一种),相应的超图问题有很多没有解决。对超图的相应性质和问题的研究不仅仅可以发现新的有意义的研究课题,而且还有助于解决图论中的一些已有问题。

(2)对随机图的一些特殊性质的刻画,特别是随机图在生成的过程中,其结构有时会发生突变,这种变化常常与日常的某种物理现象相关,对这种相变现象的研究是非常具有挑战性的课题。

(3)对超大图或者无限网络的研究将是图论的一个新热点方向。它有广泛的应用背景,其中包括实实在在的计算机通讯网络,无形而无处不在的万维网,基于因特网的社交网络,人脑的神经网络等等。对这些超大图性质的研究,需要新的数学工具;引入连续化方法,让这些超大图趋于“无穷”,然后研究其“极限图”的性质,是一个探索方向。这一方向同目前受到物理学界、控制论界重视的“复杂网络”研究相重合。

近似算法设计与分析

近似算法是求解组合优化问题的一类多项式时间算法,它们尽管不能确保对问题的每一个实例都可以求得最优解,但是可以保证求得的解的目标值与最优解的目标值相差不多。

自上世纪60 年代末格雷厄姆在研究排序问题时提出第一个近似算法以后,特别是70 年代初库克首次证明了存在NP-完全问题以来,为各种各样的组合优化问题设计近似算法就一直是组合优化领域的一个重要研究方向。它主要包括3 个方面:设计近似比越来越小的近似算法、设计运行时间越来越短的近似算法、证明近似比的下界或者不可近似性。已有的大量研究主要都集中在第一个方面,人们先后提出了对偶、半定规划、随机算法、平面划分和次模函数等技巧。第二方面的工作主要是针对存在多项式时间近似方案的NP-难问题,而第三方面的工作主要是利用上个世纪90 年代阿罗拉等人提出的概率可验证明系统。这一方向中有很多问题有待解决。

组合多面体

给定一个线性系统,判定其是否定义了一个整数多面体、是否为全对偶整数系统、是否为盒式对偶整数系统,这3 个判定问题是整数规划的核心问题,也构成了组合多面体理论的基本内容;这是因为当一个整数规划实例是由一个整数多面体所定义的,那么它可以在多项式时间内求解(一般的整数规划是NP-难解的)。包括罗瓦兹、施瓦维尔和埃德蒙兹在内的许多著名数学家都研究过组合多面体的结构刻画、计算复杂性等相关问题。另外,由于很多组合优化问题都可以非常容易地表示为整数规划问题,因而这些问题也是组合优化的重要研究课题。比如,组合优化中的一大类问题都可以用超图中的装填问题和覆盖问题来描述;装填问题是求含有边数最多的装填,而覆盖问题是求一个顶点覆盖其中所有顶点的权值之和最小。已经知道装填问题和覆盖问题都是NP-难解的,因此除非P=NP,它们都不存在多项式时间的算法。这两个组合优化问题都可以通过组合多面体的理论和方法研究,特别是:有向图和无向图上的圈装填和覆盖对偶关系以及有向图上的装填和反馈集覆盖对偶关系。

生物分子网络

生物分子网络是系统生物学的基本出发点和主要研究对象,因为从系统的观点看,生命系统是通过基因之间、蛋白之间、代谢物之间以及基因、蛋白质、代谢物、环境与功能和表象之间的相互作用来运行的,正是这些相互作用确定了细胞、组织、器官和生物个体的动态行为。所以系统生物学的根本挑战在于建立完整的、细致的生物分子间联系的描述,并籍此在分子水平及系统的观点来探索生命机理,解释复杂生命现象。最优化理论包括连续优化、组合优化和网络优化等运筹学方法和理论在生物分子网络的研究中都起到了重要作用。

典型的研究内容和问题包括,基因调控网络和蛋白质相互作用网络的数学建模,从生物进化角度出发的生物分子网络进化模型和算法,从高通量生物实验数据出发的网络重构算法,着眼于功能预测与标注的基因蛋白功能联系网络的构建和分析,以及生物分子网络的功能模块探测、网络比对等系统生物学和生物信息学算法。这些研究可以用于蛋白质功能预测和注释,以及进一步地为研究某些与特殊疾病相关的蛋白质功能注释提供有效的工具。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: