（模式识别与智能系统专业论文）船舶作业调度的数学模型及其算法研究.pdf

摘要 摘要 本文着重研究的是船舶作业调度问题的数学模型及其算法。这是来自于上海港 的一个实际的组合最优化问题。有一队作业船为抵达或离开上海港的大型运输船舶 提供港口作业服务，问如何安排这些作业船的服务对象、航行路线及作业时间，在 确保准时服务的前提下，使总航行费用最小。 本文从各个方面对船舶作业调度问题作了详尽的分祈，并将它与几个相关的经 典组合最优化问题作了全面的比较。在此基础上，建立了船舶作业调度问题的数学 模型，以简洁的数学语言正确地描述一个复杂的实际阔题，失闯题的求解奠定了基 础。随后对该问题的算法复杂性从理论上作了分析，结论是，本论文提出的船舶作 业调度问题属于脬很难类，没有有效算法。 本文提出了求解船舶作业调度问题的启发式算法。算法的整个过程分为三个步 骤。首先按航行费用最小的原则，生成初始子路径。然后尽可能地将子路径合并以 减少子路径数量，由此生成可行子路径。最后，采用路径改进启发式算法，进行局 部搜索，以提高解的质量。 本文对与船舶作业调度闻题的有密切关系的旅行商问题( t s p ) 提出了两种独 特的算法。 第一种方法是基于二叉树的t s p 描述及其求解的启发式算法。其基本特征是从 大处着眼、从小处着手。以此法求解著名的中国3 1 城市t s p 问题获得了目前已知 的最好解，而且对大规模t s p 也有优异的效果。在这一启发式算法的基础上，本文 还提出了培养算子的概念和方法，以进一步改善解的质量。 第二种方法是种群性状保持的遗传算法。这一算法基于一种假说：在同一种群 中的个体具有相近的性状，由其中的母代个体通过交叉生成的两个子代个体，应具 有与它们的母代个体相近的性状。根据这一假说设计的遗传算法，产生低质量子代 个体机会显著下降，从而提高遗传算法的效率。 另外，将本文提出的基于二叉树描述的启发式算法与种群形状保持的遗传算法 相结合，构成混合遗传算法，解的质量可进一步提高。 关键词组合最优化；船舶作业调度问题；旅行商问题；启发式算法；遗传算法 同济大学博士学位论文 a b s t ra c t a b s t r a c t 1 1 1 em a t h e m a t i cm o d e la n da l g o r i t h m so ft h et u g b o a tr o u t i n ga n ds c h e d u l i n gp r o b l e ma r em a i n l y r e s e a r c h e di nt h i sd i s s e r t a t i o n t h i sp r a c t i c a lo p t i m i z a t i o np r o b l e mc o m e sf r o mt h es h a n 曲a i h a r b o r af l e e to ft u g b o a t sp r o v i d e ss e v e r a lk i n d so fo p e r a t i n gs e r v i c e sf o rt i l o s eh u g et r a n s p o r t i n g s h i p st h a ta r eg o i n gt oa r r i v ea to r1 e a v ef r o mt h es h a n g h a ih a r b o r a n da s kh o wt oa s s i g nt h e s e r v i c e st oe a c ht u g b o a ta n dh o wt oa r r a n g et h e i rr o u t e sa n do p e r a t i n gt i m e s ，s ot h a tt h et o t a l s h i p p i n gc o s tc a l lb em i n i m u m , a t 也ep r e c o n d i t i o nt h a ta l lc l i e n ts h i p sc a l lb es e r v i c e do i lt i m e t h et u g b o a tr o u t i n ga n ds c h e d u l i n gp r o b l e mi sa n a l y z e df r o ma l j a s p e c t sa n dc o m p a r e dw i t h s e v e r a lc o r r e l a t i v ec l a s s i cc o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m s b a s e de l lt h ea n a l y s i sa n dt h e c o m p a r i s o n s ，t h em a t h e m a t i cm o d e lo ft u g b o a tr o u t i n ga n ds c h e d u l i n gp r o b l e mi sb u i l t ，w h i c h d e s c r i b e st h ec o m p l i c a t e dp r a c t i c a lp r o b l e mc o m p a c t l ya n da c c u r a t e l y , a n de s t a b l i s h e d 也eb a s e f o rs o l v i n 空也ep r o b l e m t h e n ，t h ec o m p u t a t i o n a lc o m p l e x i t yo ft h ep r o b l e mi sa n a l y z e d t h e o r e t i c a u ya n dt h er e s u l ti so b t a i n e dt h a tt h et u g b o a tr o u t i n ga n ds c h e d u l i n gp r o b l e mp r o p o s e d i i l 也i sd i s s e r t a t i o nb e l o n g st ot l l e 尸h a r dc l a s s a n dh a sn oe 伍c i e n ta l g o r i t h m ak i n do fh e u r i s t i ca l g o r i t h mt os o l v et h et u g b o a tr o u t i n ga n ds e h e d u l i n gp r o b l e mi sp r o p o s e di n 也i sd i s s e r t a t i o n t h i s a l g o r i t h mi n c l u d e st h r e ep h a s e s f i r s t , a c c o r d i n gt o 吐l ec r i t e n o no f m i n i m u ms h i p p i n gc o s t , t h ei n i t i a lr o u t ei sc o n s t r u c t e d t h o n s o m es u b r o u t e sa r ec o m b i n e dt o d e c r e a s et h en u m b e ro fs u b r o u t e ss ot h a tt h ef e a s i b l es o l u t i o ni sp r o d u c e d f i n a l l y , t h er o u t i n g i m p r o v e m e n ti sd o n et or e s e a r c hl o c a l l yt h ep o s s i b l eb e t t e rs o l u t i o n t w ok i n d so fe x c l u s i v ea l g o r i t h m sa r ep r o p o s e di nt h i sd i s s e r t a t i o nf o rs o l v i n gt 1 1 et r a v e l i n g s a l e s m a np r o b l e m ( t s p ) ，w h i c hh a sac l o s er e l a t i o n s h i pw i t ht h et u g b o a tm u t i n ga n ds c h e d u l i n g p r o b l e m t h ef i r s ti sah e u r i s t i cm e t h o df o rd e s c r i b i n ga n ds o l v i n gt h et s pb a s e do l lt h eb i n a r yt r e e ，w h i c h h a st 1 1 ec h a r a c t e r i s t i co fs e e i n gt h ef o r e s tb e f o r et i l et r e e s u s 抽gt h i sh e u r i s t i cm e t h o dt os o l v i n g t h ef a m o u sc h i n e s et s pw i t h3lc i t i e s ，t h eb e s ts o l u t i o n b yf a r , h a sb e e no b t a i n e d a n dt h e a l g o r i t h mi se f f e c t i v ef o rt h el a r g es c a l et s pe s p e c i a l l y b a s e do n 也i sh e u r i s t i cm e t h o d , a c u l t u r i n go p e r a t o ri sp r o p o s e da n dd e s i g n e d , t oi m p r o v et h es o l u t i o n st h a ta r eo b t a i n e di nt h e h e u f i s t i cm e t h o d i 乃es e c o n di sak i n do fg e n e t i ca l g o r i t h mw i t hp o p u l a t i o nc h a r a c t e r i s t i c sh o l d i n gf o rs o l v i n gt s e t h i sa l g o r i t h mi sb a s e do nah y p o t h e s i s t h a ta l li n d i v i d u a l si nt h es a l l l ep o p u l a t i o nh a v et h e s i m i l a rc h a r a c t e r i s t i c s ，a n d 血et w oe h i l di n d i v i d u a l s ，w h i c hp r o d u c e db yt w op a r e n ti n d i v i d u a l s u s i n gc r o s s o v e r ，s h o u l dh a v et i l es i m i l a rc h a r a c t e r i s t i c sw i t ht l l e i rp a r e n t s t h eg e n e t i ca l g o r i t h m b a s e do l lt h eh y p o t h e s i sd e c r e a s e st h ep r o b a b i l i t yo fp r o d u c i n gt h es o l u t i o n sw i t hl o wq u a l i t y , s o t h a tt h ec o m p u t a t i o n a le f f i c i e n c yi si n c r e a s e d i na d d i t i o n c o m b i n i n gt h eh e u r i s t i cm e t h o db a s e d0 1 1t h eb i n a r yt r e ea n dt h eg e n e t i ca l g o r i t h m w i t hp o p u l a t i o nc h a r a c t e r i s t i c sh o l d i n gc o n s t r u c t sak i n do fh y b r i dg e n e t i ca l g o r i t h m , w h i c hc a n i m p r o v et h es o l u t i o na g a i n k e y w o r d s c o m b i n a t o r i a lo p r i m i z a # o n ；t u g b o a tr o u a n ga n ds c h e d u l i n gp r o b l e m ；t r a v e l i n g s a l e s m e np r o b l e m ；h e u n s t w ；g e n e t i ca l g o r i t h m s 同济大学博士学位论文 第一章引言 第一章引言 1 1 问题的提出 许多理论和实际应用研究都会涉及到如何选取一组参数以达到一个最佳的目 标。本文研究的对象一一船舶作业调度问题( t u g b o a tr o u t i n ga n ds c h e d u l i n g p r o b l e m ，简称t r s p ) 就是这样一个实际问题，它是关于上海港口作业船如何最有 效地进行船舶作业的问题。由于上海港的船舶作业量非常大，即使作业效率只提高 百分之一，每年的收益就能增加数千万元人民币。提高作业效率将使作业船的航程 减少，这对降低黄浦江水域和空气污染也会带来益处。而且，寻求问题的最优解在 理论上也颇有价值。有如此好的经济效益、环境效益和理论价值，这样的问题是值 得花力气去研究的。 1 1 1 上海港简介 上海港作为我国目前最大的港口是最重要的水陆交通枢纽之一，也是世界闻名 的最大的国际性港口之一。目前，上海港的年吞吐量已达数亿吨，与世界上许多国 家的港口建立了良好的通商、通航关系。 在中华人民共和国成立之初，为了建设好、管理好当时就举世闻名的上海港， 根据中央政府的指示，上海市政府随即就成立了上海港务局。港务局根据港口作业 和港口管理的特点，迅速建立起了比较完整、系统的港口管理机制。 解放初期的上海港务局主要由若干港区和若干个作业船队组成。 各港区的主要任务是为到离岸的货船装卸货物，为客船接送旅客，并且为这些 客货轮提供淡水、能源、食品及其他各种服务。 各作业船队的主要任务是完成各种不同的作业，如驳船队的任务是为大型散装 货船接驳货物，带缆船队的任务是为停靠黄浦江上浮筒旁的船舶系缆绳、解缆绳， 交通船队的任务是接送尚未靠岸的船舶上的船员上下船，环保船队的任务是清理黄 浦江水面上的各类垃圾、污物，而拖轮船队的任务是帮助大型客货轮靠岸、离岸、 移泊位等。 上海港作业结构如图1 1 所示。 同济大学博士学位论文 第一章引言 图i i 上海港作业结构 上个世纪八十年代初，上海港年吞吐量突破一亿吨，这是上海港发展史上的一 个重要里程碑。这一时期也正是我国改革开放的起步阶段。上海港在改革进程中发 生了许多巨大的变化。其中，原来集管理与经营于一体的旧港务局模式被管理与经 营分离的新港务局模式所取代。各港区根据其装卸货物的类别和形式逐步演变成了 各港务公司，如集装箱装卸公司、粮油食品装卸公司、煤炭石油装卸公司、散货装 卸公司等。而原来各种船队也根据港口作业的性质组建了各种船务公司。 上海复兴船务公司就是由前港务局的几个船队改建重组后的一个专业从事上海 港港口作业的船舶服务公司。该公司是以原来的拖轮船队为基础建成的，因而其港 口作业的主要经营项目是为大型客货轮提供靠岸、离岸和移位服务，仅该项业务量 金额占公司总额百分之九十以上。 本文的研究内容就是以拖轮作业为背景，着重探讨拖轮作业的规律，以及如何 提高船舶作业的效率和质量。 1 1 2 船舶作业调度的历史与现状 每天有许多大型的客货轮频繁进出上海港，它们或靠岸，或离岸，或从一个泊 位移至另一个泊位。上海港非常繁忙，它给需要停靠上海港的每艘船舶提供的泊位 空间非常有限；另外，上海黄浦江的航道比较狭窄，而这些巨轮的体积又非常的庞 大。因此，这些大型客货轮光靠自身的能力是无法迅速、安全地完成靠岸、离岸、 调头、移泊位、停泊浮筒等作业。按照港口作业的惯例，这些大型客货轮在需要时 可以申请租用一到两艘拖轮，帮助其完成这些作业。上海复兴船务公司的一项主要 业务就是为这些大型船舶提供拖轮作业服务。 公司设有船舶作业调度室，其主要任务是：接受需要拖轮服务的大型船舶的港 口作业申请，合理安排公司内各作业船的工作，为各船舶提供及时、安全、高效的 服务。 同济大学博士学位论文 2 第一章引言 船务公司在完成船舶作业的同时，要充分考虑公司为此所付出的代价。代价主 要包括两个方面：一是作业船从当前位置驶往作业点所需花费的船用作业燃料，二 是作业船的机械损耗。这两方面的代价均与作业船行驶的航程成正比。在己实现市 场经济的今天，船务公司自然把公司在完成客户所要求的各种作业服务的同时将各 种成本降到最低作为公司追求尽可能高的经济经济效益的一项主要目标。 为了降低成本、提高经济效益，除了各作业船需要保持良好的工作状态，以及 各作业船掌握熟练的作业技能，最重要的就是作业调度的水平。这项重要的工作由 公司的作业调度室承担。为此，作业调度室一是要及时、准确掌握公司各作业船动 态，即作业船的位置、航向、航速及工作状况。二是要根据船舶动态和客户需求确 定最佳的船舶作业方案，即船舶调度。作业调度系统如图1 2 所示。 作业船舶动态 客户需求 作业调度 作业指令 客户需求确认 图1 2 作业调度系统 要做到及时、准确地掌握的各船舶的动态，并在此基础上做出最佳的调度安排， 必须依靠一定科学技术手段。该公司在这方面的技术水平随着国家科学技术的进步 而在同步地发展。在过去的半个多世纪里，这一发展大致经历了以下三个发展阶段： 第一代为1 9 4 9 年至1 9 7 9 年，即建国初期到中国共产党的十一届三中全会。这 一阶段的主要技术特征是有线电话加人工调度。每一艘作业船在完成一项作业后， 就近停靠某个码头泊位，然后利用岸上的有线电话向作业调度室报告本船的方位和 船舶的工作状况，并接收调度室的作业指令。由于作业船停靠的码头泊位一般与岸 上电话所在位置相距较远，而且作业船总是停靠在码头的最外档，作业船与岸之间 隔了几艘大船，船员从船上下到岸上要翻越好几艘大船，所以调度室很难及时掌握 各作业船的当前状态，各作业船也同样很难及时接收调度室的指令。这一阶段的作 业调度水平是非常落后的，作业调度的效率也是低下的。 第二代为1 9 8 0 年至1 9 9 5 年，这是我国实行改革开放政策的初级阶段。这一阶 段的主要技术特征是无线电话加人工调度。1 9 8 0 年，随着中国实行改革开放政策的 开始，发达国家的一些新技术、新产品开始进入我国。该公司从1 9 8 0 年开始，逐步 从日本、瑞典等国引进了一些适用于港口作业的无线电通信设备和器材，为每一艘 作业船配备了专用的无线电话，并建立了无线电话通信网。各作业船与作业调度室 之间、各作业船之间都能通过船上的无线通信设备和公司的无线通信网络实现相互 之间及时快速的信息交换。于是，调度室通过无线电话便可以及时了解各作业船的 动态，也可以将作业调度指令及时地发送给各作业船。调度室和各作业船之间的信 息交换效率的大大提高，使得作业调度的水平和效率有了显著的提高。 同济大学博士学位论文 第一章引言 第三代为1 9 9 6 年至2 0 0 2 年，这是我国改革开放政策进一步深化完善的阶段。 这一阶段的主要技术特征是全球定位系统( g l o b a lp o s i t i o n i n gs y s t e m ，简称g p s ) 加人工调度。到1 9 9 9 年底，公司为每艘作业船装备了一套g p s 以及相配套的无线 数据通信设备。作业调度室也相应地配备了无线数据通信设备和电子海图。现在每 艘作业船不再需要通过无线电话向调度室报告自身的方位，而是通过g p s 获得作业 船自身的经纬度坐标数据，并自动地通过无线数据通信设备将这些数据送往作业调 度室。调度室通过无线数据通信系统和电子海图能够及时准确地掌握每一艘作业船 的精确位置、航向和航速，即作业船的动态。由于采用了g p s 和无线数据通信设备， 不仅提高了调度室掌握各作业船动态的效率，而且也极大地提高了确定船舶动态的 精度，这为高效率作业调度提供了必要的技术手段。 船舶作业调度发展的三个阶段中，船舶动态获取、作业指令发送、客户需求申 请、客户需求确认和作业调度的技术手段列于表1 1 中。 表1 1 作业调度技术发展的三个阶段 第一代 第二代 第三代 1 9 4 9 年一1 9 7 9 年1 9 8 0 年一1 9 9 5 年1 9 9 6 年- - 2 0 0 2 年 船舶动态获取有线电话 无线电话 g p s 客户需求申请有线电话 有线电话有线电话 + 作业调度人工调度 人工调度人工调度 客户申请确认有线电话 有线电话 有线电话 作业指令发送有线电话 无线电话无线电话 由表1 1 可以看出，尽管在过去的几十年中上海复兴船务公司船舶作业调度的 技术手段有了本质上的提高，作业调度的效率和质量也有了显著的改进，但是作业 调度的工作方式依旧未变，至今还是依靠手工完成。调度室的工作人员根据作业船 的动态、申请港口作业服务船舶的方位和作业时间，对公司的作业船做出调度安排， 最后通过无线电话将调度指令发送给各艘作业船。整个调度工作都是靠手工完成的。 其结果是调度工作费时费力，而且结果也不尽如人意，这直接影响了调度效率和公 司的效益。所以，公司下一步技术改进的目标是：建立计算机辅助作业调度系统， 以提高船舶作业调度的效率和效益；二是建立新的数据通信系统，调度室不仅通过 该系统获取各作业船的动态，而且还可以将调度指令以数据的形式送达各作业船。 同济大学博士学位论文4 第章引言 1 1 3 新一代作业调度系统的总体结构 上海市是我国经济发展的重要城市，上海港是中国经济走向世界的一个重要的 海上枢纽，上海港的年吞吐量连续多年以两位数增长。为了适应上海港发展的需要， 船务公司正着手对目前使用的第三代船舶作业调度系统进行全面的技术上的升级改 造，建立新一代的作业调度系统。新一代的作业调度系统的系统结构保持不变，如 图1 2 所示，但是，组成系统的五个部分在技术上将发生根本性的变化。新一代的 作业调度系统中，各个环节的手工操作将被全部取消，充分利用当今计算机技术、 通信技术、网络技术，初步实现全自动、数字化的作业调度。这五方面技术改造内 容如下： 1 作业船舶动态获取。船舶动态信息主要包括：船舶位置、航向、航速、船舶 设备状况以及船舶人员状况。这些信息分为两类，第一类是船舶的位置、航向、航 速。这一类信息在第三代系统中由g p s 采集，并通过无线数据通信设备发送到作业 调度室。在新一代的作业调度系统中，这类信息继续由g p s 采集，并送入船上的数 据信息终端通过无线数据网络发送到作业调度室。第二类是船舶的设备状况和人员 状况。这一类信息在第三代系统中由作业船上的相关责任人通过无线电话报告给作 业调度室。在新一代的作业调度系统中，这类信息将由船上的数据信息终端通过无 线数据网络传给作业调度室。 2 客户服务需求的信息获取。客户需求信息主要包括：船舶信息( 船名、吨位、 类型、国籍、注册公司、代理公司，等等) 、日期、时间、地点( 码头、泊位) 。这 部分信息来源比较复杂。在第三代系统中，主要采用接收电话预约和专门递送的预 约单。这些预约申请不是由被服务的船舶递交的，而是由船舶的所属公司或代理公 司递交。在新一代系统中，这些服务申请将通过计算机网络实现。预约申请方在填 妥电子申请单后发送给船务公司的作业调度室，后者在完成作业调度后将计划安排 通知给客户。 3 作业调度。这是作业调度系统的核一t l , 部分，它根据作业船的动态和客户需求 的信息，合理安排作业船的作业，以尽可能地满足客户的需求，同时使船舶作业的 成本降至最低。这部分工作过去一直是由调度人员手工完成的。在新一代系统中， 这部分工作将借助计算机完成。 4 客户需求确认。作业调度有两种可能的结果：一是客户需求得到满足，于是 提出的服务申请得到确认，这样申请过程结束；二是船务公司无法完全满足客户的 需求，这时双方将通过电话洽谈寻求一种解决方案。在第三代系统中，船务公司是 通过电话将确认信息通知给客户的。在新一代的系统中，客户需求确认的信息也将 通过计算机网络传送给客户。 5 作业调度指令发送。作业调度室将作业调度的计划安排通知各作业船。在第 三代系统中，作业调度室使用无线电话将作业调度指令传达给各作业船。在新代 同济大学博士学位论文 第一章引言 作业调度系统中，作业调度指令将用作业调度室的数据信息终端通过无线网络传送 到各作业船。 新一代船舶作业调度系统如图1 3 所示。 在系统的具体实旌过程中，部分硬件设备、软件系统以及通信网络将选用成 熟的、适用的现成产品，另一部分设备和软件必须进行专门设计和开发。 本文就是研究如何设计作业调度的方案及其如何实现。 船舶船舶 r l 刈 ，】i , - t 二，、 i- o，二，、 i 指令状况 l g p s l 指令状况 l g p s 十00伽、，觚千上0 l 无线数据终端 【f 业盯口 无线数据终端 l 无线数据网络 l l 一r 一一t j _ - l 作业计划指令l上船舶动态 无线数据终端 ： 作业调度作业调度室 3 客户管理 伞 服务申请l、r 申请确认，r t 计算机网络。 t 计算机 计算机 囊争白 服务 申请 申请 确认 服务 申请 申请 确认 图1 3 新一代船舶作业调度系统组成框图 同济大学博士学位论文6 第一章引言 1 2 组合最优化问题 本文研究的对象船舶作业调度问题是如何寻求一个实际问题的最优解。根 据客户、作业船、环境等大量数据，对所有作业船从空间和时间上进行合理安排， 目标是为客户提供的服务最好，而服务所需要的费用最低。这是一个最优化问题。 1 2 1 关于组合最优化问题的一些定义 最优化问题可分为两类，一类是连续变量的问题，另一类是离散变量的问题。 离散变量的问题也称为组合问题。连续问题的解，通常是一组实数或一个函数。组 合问题的解，通常是可数无限集的一组整数，或一个集合，或一个排列，或一个图， 等等。 最优化问题种类繁多，但是它们都有三个基本的要素：判决变量、约束条件和 目标函数。在问题的求解过程中，被选定的基本变量称为判决变量，对这些判决变 量的种种取值上的限制称为约束条件，衡量问题可行解的函数称为目标函数。 组合最优化问题就是在给定的约束条件下，求目标函数的最大值或最小值，即 最优值。 定义( 最优化问题实例) 个最优化问题的一个实例是一对元素( s ，) ，其 中解空间s 是可行解集；目标函数厂是一个映射，定义为 厂：s 寸r “ r 8 是疗维实向量空间。 求目标函数最小值的问题称为最小化问题， r a i n ( x ) ，x s 求目标函数最大值的问题称为最大化问题， m a x 厂( 力，z s 即求一个x s ，使得 即求一个x s ，使得 显然，最小化问题和最大化问题没有本质的差别， 最小化问题和最大化问题就可以等价转换。 一 只要改变目标函数的符号， 定义( 全局最优解) 设( s ，) 是组合最优化问题的一个实例，s 。若 ( 墨删) ( 功，x s 则称为最小化问题 r a i n ( x ) ，z s 的全局最优解。一 定义( 最优化问题) 一个最优化问题，就是一些实例的集合。 一个最优化问题和一个最优化问题实例是两个不同的概念。例如，旅行销售商 问题( t s p ) 是一个组合最优化问题。t s p 问题属于n p 类问题，所以不存在有效算 法。然而，一个t s p 实例有可能存在有效算法，比如当一个t s p 实例的所有城市之 同济大学博士学位论文 7 第一章引言 间的距离都相等时，有效算法存在，其可行解空间里的所有可行解都是该实例的最 优解。 定义( 邻域) 给定一个诸实例为( s ，) 的最优化问题，且其可行解x s ，把 某种意义上靠近x 的可行解之集合定义为n ( x ) 。一个邻域就是对每一个实例确定 的映射 n ：so 2 j 2 s 表示空间s 的所有子集的总体。 一 邻域的含义是，对于每一个可行解x ，有一个关于x 的解的集合鼠s ，内 的解在某种意义上与x 是邻近的。 如果s = f ，则一个欧几里得距离内的点集就是一个自然的邻域。在许多组合 问题里，邻域的选取主要依赖于s 的结构。 定义( 局部最优解) 给定一个最优化问题的实例p ，厂) 和一个邻域，一个可 行解x s 。如果对一切夕过有 f ( x ) f 0 ) 则称x 为最小化问题 n f m 厂( x ) ，x s 的关于的局部最优解。 定义( 恰当的邻域)给定一个可行解集为s 、邻域为的最优化问题。若x s 是关于的局部最优解，有x 也是问题的全局最优解，则称邻域是恰当的。 1 2 2 关于组合最优化问题的算法 最优化问题的解集s 通常由一组等式和不等式隐含地表示，并充满可行解。给 定最优化问题，不同的目标函数、不同的决策变量、不同的解空间，数学描述方法 也不同。同一个问题，采用不同的数学描述方法，求解的算法也会不同，最后的计 算效果也就不同。组合最优化问题的可行解集通常是有限空间，但是却与判决变量 的个数呈指数关系。所以，当决策变量的个数较大时，其解空间庞大得几乎可以认 为是无穷的。有些组合最优化问题存在有效算法，而很多问题的求解都需要指数时 间。寻找有效算法求解组合最优化的解一直是一个难题。 求解最优化问题的算法很多，它们可以分为两大类，一类是精确算法( e x a c t a l g o r i t h m s ) ，另一类是近似算法( a p p r o x i m a t i o na l g o r i t h m s ) 。 1 2 2 1 最优化问题的精确算法1 8 5 l 当目标函数和约束条件均为线性表达式时，最优化问题称为线性规划问题 ( 1 i n e a rp r o g r a m m i n gp r o b l e m ) ；否则称为非线性规划问题( n o n l i n e a rp r o g r a m m i n g p r o b l e m ) 。求解线性规划问题最著名的方法是单纯形法( s i m p l e xm e t h o d ) ，这是由丹 捷格( gbd a n t z i g ) 于1 9 4 7 年提出的f 1 8 l 。另外还有对偶性定理。当目标函数为 同济大学博士学位论文 8 第一章引言 二次函数、约束条件全部为线性表达式时，最优化问题称为二次规划问题( q u a d r a t i c p r o g r a m m i n g ) ，这类问题有类似于线性规划问题那样的求解方法。当目标函数为凸 函数、可行域为凸空间时，最优化问题称为凸规划( c o n v e xp r o g r a m m i n g ) 问题。对 于凸规划问题，根据连续性和可微性的假设，求解方法有：最小平方和法，最迅速 下降法，以及牛顿法等经典无约束法。对于非凸规划问题( n o n c o n v e xp r o g r a m m i n g ) ， 有互补转轴理论( c o m p l e m e n t a r yp i v o tt h e o r y ) 的推广。 当判决变量取离散值时，即解空间s 是离散时，最优化问题习惯上称为组合最 优化问题( c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ) 。当目标函数和约束条件均为线性表 达式时，这类问题也称为整数规划( i n t e g e rp r o g r a m m i n g ) 问题。整数规划中若所有 判决变量都为非负整数时，就称为纯整数规划( p u r ei n t e g e rp r o g r a m m i n g ) ，或称为 全整数规划( a l li n t e g e rp r o g r a m m i n g ) 。若判决变量一部分是整数、另一部分是实数， 则称为混合整数规划( m i x e di n t e g e rp r o g r a m m i n g ) 。整数规划中的一种特殊情况是 所有判决变量的仅为0 或1 ，这样的整数规划称为o 一1 规划( 0 1p r o g r a m m i n g ) 。整 数规划问题中，最为著名的求解方法是分枝定晃法( b r a n c h a n d b o u n d ) f 5 ，其他 还有g o m o r y 的割平面法( c u tp l a n e ) t 3 2 1 。运筹学领域中还有一种求解最优化问题的 方法，即动态规划( d y n a m i cp r o g r a m m i n g ) r 7 ，引。 1 2 2 2 近似算法 启发式方法( h e u r i s t i c ) ：依据问题本身的结构等有关知识实现对解空间的搜索。 启发式算法模仿人的大脑求解问题的方法，建立一套搜索策略，并运用这套规则达 到对问题的求解。启发式算法具有很高的计算效率，若算法设计得当，解的质量也 很不错。但是，针对某一种问题的启发式算法对其他不同的问题不适用。应当说， 启发式算法并不是很好的算法。由于其他方法并不具备压倒性的优势，所以启发式 算法至今还活跃在求解组合最优化问题的舞台上。 遗传算法( g e n e t i ca l g o r i t h m s ) 【9 1 j ：是一种建立在模仿生物进化过程基础上的 随机搜索技术。遗传算法把所要求解的问题当作对某个目标函数的全局优化，将问 题的解表示成基因，通过选择、交叉和变异等运算，搜索最优解。 模拟退火( s i m u l a t e da n n e a l i n g ) i s 4 ：1 9 8 2 年k i r k p a t r i c k 等人将物理领域中的退 火思想引入组合最优化问题的求解，提出了模拟退火算法。它源于对固体退火过程 的模拟，采用m e t r o p o l i s 接收准则，并用一组称为冷却进度表的参数控制算法的进 程，使算法在多项式时间内输出一个近似最优解。 神经网络( n e u r a ln e t w o r k s ) p7 趼l ：基于对生物神经网络的模仿，建立一种由大 量、简单、相互连结的人工神经元构成的人工神经网络。人工神经网络经过训练可 以完成许多有意义的工作。人工神经网络的应用领域非常广泛，甚至触及文学艺术 领域。人工神经网络在求解组合最优化问题方面具有独特的视角，在求解路径问题、 时间安排问题等方面都有成功的应用。 禁忌搜索( t a b us e a r c h ) 【2 刎：是一种智能的搜索技术，它与登山非常类似，登 同济大学博士学位论文 9 第章引言 山者必须有选择地记住巡游路径的关键部分，还必须能够沿途做出决策。这是一种 自适应的搜索过程，能够结合使用其他搜索算法，比如，启发式方法，以克服解陷 入局部最优。禁忌搜索算法可以用来求解许多组合最优化问题，具有广泛的应用领 域。 1 3 遗传算法发展与现状 1 3 1 遗传算法的起源 几乎从电子计算机诞生那天起，生物模拟就一直是计算科学的一个重要组成部 分，如自动机理论、机器思维、专家系统、神经网络、人工生命等等无不基于对自 然生物领域某些现象、或特征、或机理的模拟。但所有这些模拟都不及遗传算法所 取得的成功。 达尔文( c h a r l e sd a r w i n ) 提出的适者生存的自然选择原理和孟德尔( g r e g o r j o h a n nm e n d e l ) 基因学说不仅对生物学领域产生了巨大的影响，也对计算机科学和 工程领域产生了同样巨大的影响。遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 就是受 这些理论和学说的启发、基于对生物系统的某些机理的模仿的一种适应性搜索和最 优化算法。1 9 6 5 年美国密执安大学j o h r lh o l l a n d 教授首先提出了遗传算法的基本方 法，对此进行了广泛的研究，并将遗传算法应用于许多工程领域。在这之后，1 9 6 6 年l j f o g e l 等人在研究有限态自动机时提出了进化规划算法( e v o l u t i o n a r y p r o g r a m m i n g ，简称e p ) 1 2 7 1 。1 9 7 2 年i r e c h e n g b e r g 和1 9 7 7 年h p s c h w e f e l 提出 了进化策略算法( e v o l u t i o ns t r a t e g i e s ，简称e s ) 【6 7 7 4 1 。1 9 9 2 年j r k o z a 提出了遗 传程序设计方法( g e n e t i cp r o g r a m m i n g ，简称g p ) 4 s j 。这几类算法也同样基于对自 然进化过程的模仿，它们与遗传算法一起构成了进化计算( e v o l u t i o n a r y c o m p u t a t i o n ，简称e c ) 或称进化算法( e v o l u t i o n a r ya l g o r i t h m s ，简称e a ) 【2 6 2 】的 四大分支，如图1 4 所示。 进化计算 i遗传算法 进化规划算法进化策略算法遗传程序设计 图1 4 进化计算的四大分支 同济大学博士学位论文 1 0 第一章引言 h o l l a n d 教授设计了基本遗传算法( c a n o n i c a lg e n e t i ca l g o r i t h m s ，简称c g a ) 的模型，并运用统计决策理论对遗传算法的搜索机理进行了理论分析，建立了著名 的模式定理( s c h e m at h e o r e m ) 和隐含并行性( i m p l i c i tp a r a l l e l i s m ) 原理，为遗传 算法奠定了基础。1 9 7 5 年，h o l l a n d 教授所著的遗传算法的开创性著作“自然与人 工系统中的适应性( a d a p t a t i o n 加n a t u r a l a n d a r t i f i c m l s y s t e m s ) 3 9 l 一书出版，它标 志了遗传算法的诞生。他的学生们在各自的博士论文中对遗传算法的一系列基础理 论问题和应用问题进行了分析和研究【6 ，屹9 2 1 ，3 m 。其中，d ej o n g 将遗传算法用于函 数优化问题，设计了一系列遗传算法的执行决策和性能评价指标，对遗传算法的性 能作了大量的分析。他的研究成果成为了遗传算法发展史上的重要的里程碑。随着 许多研究者对遗传算法的兴趣逐渐增加，遗传算法在上个世纪八十年代迎来了第一 个发展高潮。1 9 8 5 年举行了第一届“遗传算法及其应用”国际学术研讨会，以后每 两年举行一次。1 9 8 9 年，g o l d b e r g 出版了著名的“搜索、优化和机器学习中的遗传 算法 ( g e n e t i ca l g o r i t h m si ns e a r c h , o p t i m i z a t i o n , a n d m a c h i n el e a r n i n g ) i j l j 一书， 为遗传算法这一领域奠定了坚实的基础。表1 2 列出了遗传算法理论研究的重要成 果。 人们对遗传算法兴趣不断增长的原因主要有两个方面。第一个是遗传算法的应 用方面：许多科学和工程应用领域，尤其是人工智能和自动控制领域，存在许多大 规模的非线性系统，这些系统中的许多优化问题用传统经典优化算法难以求解或不 能有效求解。而遗传算法给众多研究者和设计者提供了一种全新的思想和工具，并 且实践已证明遗传算法在初步的应用中已经取得了许多不错的效果。第二个是遗传 算法的理论研究方面：算法本身的工作机理、算法的性能以及遗传算法的发展潜力 等一些理论问题对许多研究者有着巨大的吸引力。对遗传算法理论上的深入研究， 有助于其自身的不断成熟与完善。 1 3 2 遗传算法的应用 遗传算法与工程设计问题中所使用的传统搜索和最优化方法有非常大的差别。 由于简单、易操作、要求低以及全局搜索能力强等特点，遗传算法己被成功地应用 于各种问题的求解p 引。 1 函数优化问题1 2 。函数优化是遗传算法最早的应用研究领域，同时也是对遗 传算法进行性能评价的常用算例。许多研究者构造出了各种形式复杂的测试函数， 有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确 定函数也有随机函数，有单峰值函数也有多峰值函数等。这些几何特性各具特色的 函数被用来评价遗传算法的性能，从而能更有效地反映遗传算法的本质效果。对许 多非线性、多模型、多