（计算机应用技术专业论文）遗传算法研究及在航运船舶配载系统中的应用.pdf

大连理工大学硕七学位论文 摘要 近些年来，人们对遗传算法的关注程度逐渐加深，对它的应用越来越广泛，但有关 它收敛速度上的理论研究并不是很多。本文在杰出个体保存遗传算法的收敛速度方面做 了理论上的分析，并在分析的基础上对传统的遗传算法进行了优化，方法是在进化的各 个代中提高向全局范围最优解靠近的可能性进而使算法的效率得到提高。此外遗传算法 还有早熟问题，本文给出了一种解决早熟收敛的方法，在求解过程中连续运行遗传算法 数次来得到数个局部最优解，然后再从这些备选解中选择最杰出的解。本文还研究了应 用遗传算法学习神经网络的权值的一些问题，给出了一种优化的网络结构，使用几个单 一输出的网络作为多个输出的b p 网络的一种替代方法，该种网络结构更简单，更适合 使用遗传算法优化。此外，可以证明这种优化的网络结构具有更优的可行解。 0 1 规划是最具代表性的整数线性规划模型之一，本文在将遗传算法应用于实际项 目航运船舶配载系统中时，将选取待选船舶建立为o 1 规划的模型。在实际问题中 待选船舶的数量可达数百艘，使用全枚举的方法在这里显然无法胜任。本文首先采取了 分支限界法进行求解，使问题的计算复杂度明显降低，在通常情况下可以立刻求解出问 题的全局最优解。然后本文针对那些使用分支限界法也无法在可接受的时间内计算出全 局最优解的情形，提出了一种改进的遗传算法来解决任务。 其实使用目前所知的任何方法求解这些少部分情况都是困难的，使用遗传算法计算 满意解已经可以满足需要，通过实验也证明了本文给出的方法的是有效的。 关键词：遗传算法；最优保存；收敛速度；神经网络；决策支持 遗传算法研究及在航运船舶配载决策支持系统中的应用 g e n e t i ca l g o r i t hma n di t sa p p l i c a t i o ni ns t o w a g es y s t e mo f s h i p p i n gs h i p s a b s t r a c t i nr e c e n ty e a r sg e n e t i ca l g o r i t h mi sp a i dm o r ea n dm o r ea t t e n t i o n ，a n di t sa p p l i c a t i o ni s g e t t i n gm o r ea n dm o r ee x t e n s i v e ，h o w e v e rt h e r ei sl e s st h e o r e t i c a lr e s e a r c ho ni t sc o n v e r g e n c e s p e e d c o n s e q u e n t l y ，t h et h e o r e t i c a la n a l y s i sf o rt h ec o n v e r g e n c es p e e do fb e s ti n d i v i d u a l p r e s e r v e dg e n e t i ca l g o r i t h mi sc o n d u c t e di nt h i sp a p e r ，a n do nt h eb a s i so ft h ea n a l y s i st h e t r a d i t i o n a la l g o r i t h mi so p t i m i z e d ，w h i c hi st oe n h a n c et h ee f f i c i e n c yo ft h ea l g o r i t h mt h r o u g h e n h a n c i n gt h ea p p e a r i n gp r o b a b i l i t yo fg l o b a lo p t i m a ls o l u t i o n i na d d i t i o nt h e r ei ss t i l la l li s s u e o fp r e m a t u r ec o n v e r g e n c ef o rg e n e t i ca l g o r i t h m , s oam e t h o df o ro v e r c o m i n gp r e m a t u r e c o n v e r g e n c ei sp r o p o s e d t m sm e t h o ds u c c e s s i v e l yr u n sg e n e t i ca l g o r i t h mt oo b t a i nm u l t i p l e d i f f e r e n tl o c a lo p t i m a ls o l u t i o n si nt h ep r o c e s so fs e a r c h i n go p t i m a ls o l u t i o n , t h e no b t a i n s g l o b a lo p t i m a ls o l u t i o nf r o mt h e s es o l u t i o n st ob ec h o s e n i nt h i sp a p e rt h ei s s u eo fu s i n g g e n e t i ca l g o r i t h mt ol e a r nt h ew e i g h to fn e u r a ln e t w o r ki sa l s os t u d i e d ，a n da no p t i m i z e d n e t w o r ka r c h i t e c t u r ei sp r o p o s e d , w h i c hu s e san e t w o r k 、析mm u l t i p l es i n g l eo u t p u t st or e p l a c e ab pn e t w o r kw i t hm u l t i p l eo u t p u t s ，s ot h a tf e a t u r e sa r es i m p l ei ns t r u c t u r e ，a n da r em o r e s u i t a b l et ou s eg e n e t i ca l g o r i t h mo p t i m i z a t i o n i na d d i t i o n , t h i so p t i m i z e dn e t w o r k a r c h i t e c t u r ec a nb ep r o v e dt oh a v em o r es u p e r i o ro p t i m a ls o l u t i o n o - 1p r o g r a m m i n gi so n eo ft h em o s ti m p o r t a n ti n t e g e rl i n e a rp r o g r a m m i n g i nt h ep a p e r w h e ng e n e t i ca l g o r i t h mi sa d o p t e di nap r a c t i c a lp r o j e c to f s t o w a g es y s t e mf o rs h i p p i n g s h i p s ”，a v a i l a b l es h i p sw i l lb ec h o s e nt oe s t a b l i s h0 1p r o g r a m m i n gm o d e l i np r a c t i c a l p r o b l e m st h en u m b e ro fa v a i l a b l es h i p sm a yb eu pt oh u n d r e d s s ot h em e t h o do fa l l e n u m e r a t i o ni so b v i o u s l yn o ts u i t a b l eh e r e t h e r e f o r et h ei d e ao fe m b r a n c h m e n td e l i m i t a t i o ni s i n t r o d u c e df i r s ti nt h ep a p e rs ot h a tt h et i m e so fc a l c u l a t i o na r er e d u c e dd r a m a t i c a l l y 。a n dt h e o p t i m a ls o l u t i o nc a l lb eo b t a i n e di nav e r ys h o r tt i m ei nm o s tc a s e s t h e na ni m p r o v e dg e n e t i c a l g o r i t h mi sp r o p o s e dt os o l v et h eo p t i m a ls o l u t i o na g a i n s tt h es i t u a t i o nt h a te m b r a n c h m e n t d e l i m i t a t i o nm e t h o dc a i ln o to b t a i no p t i m a ls o l u t i o ni nas h o r t e rt i m e i nf a c ti ti sd i f f i c u l tt os o l v es u c hm i n o r i t ys i t u a t i o n su s i n ga n ym e t h o d sn o w k n o w n , a n di t i sab e t t e rc h o i c et ou s eg e n e t i ca l g o r i t h mo b t a i n i n gas a t i s f a c t o r ys o l u t i o n t h ee x p e r i m e n t a l r e s u l th a sp r o v e dt h ee f f e c t i v e n e s so ft h ep r o p o s e dm e t h o d k e yw o r d s ：g e n e t i ca t g o r i t h m s ；b e s ti n d i v i d u a tp r e s e r v e d ；c o n v e r g e n c es p e e d ； n e u r a tn e t w o r k s ；d e c i s i o ns u p p o r ts y s t e m - i i - 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：丝壁簦三圭塑垒墨型型塑皇丝筮墨兰查芏丝望 作者签名：型l 堡墨 日期：掣午生月三l 日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 日期：! 砗生月! 一日 日期：型2 年l 月旦日 l1 大连理工大学硕士学位论文 引言 遗传算法( g e n e t i ca l g o r i t h m ) 是基于生物进化机制的随机搜索算法。自1 9 7 5 年由 h o l l a n d 教授提出【l 】，后经g o l d b e r g 全面系统的论述 2 】，从而奠定了现代遗传算法的理 论和应用基础。它简单、通用、鲁棒性强，易于实现并行处理，因此在过去的2 0 多年 里，遗传算法的应用范围非常广泛，并且取得了巨大的成功。在软件技术、模式识别、 机器学习、神经网络、工程优化控制、图像处理、遗传学、生物学、社会科学等方面， 遗传算法的应用前景都非常广泛。 遗传算法的生物基础虽然很牢固，但它的理论基础无法谈得上雄厚，h o ll a n d 提出 的模式定理是最典型的理论，而其余的一些理论都缺少完整的证明，总体看来遗传算法 的收敛机制并没有完全确定。有学者证明了杰出个体保存的遗传算法可以在全局范围内 找到收敛点【3 】，但是对于在杰出个体保存遗传算法的收敛速度上还没有进行很多的理论 研究，本文将对杰出个体保存遗传算法的收敛速度方面进行一定的理论研究。此外，将 遗传算法应用于实际问题还存在一些其他的缺点，如收敛慢，易早熟( 种群中的个体提 前在一个非全局最优点的周围聚集) 等问题，本文同样给出了一些自己的见解，并将传 统的遗传算法做了适当的优化。 决策支持系统是辅助决策者通过模型、数据和知识，以人机交互方式进行半 结构化或者非结构化决策的计算机系统。它是管理系统向更高一个层次发展而产 生的高级信息管理系统。它为决策者提供分析问题、建立模型、模拟决策过程和 方案的一个平台，通过调用各种信息资源和分析工具，帮助决策者提高决策的水 准和质量。在决策支持系统中存在大量的优化问题，其中大多都是n p 类型的，求 取最优解在现阶段并不现实，实际情况是求得一个较优解或满意解就可以达到要 求，遗传算法正是求较优解或满意解最好的手段之一。 本文在开发航运船舶配载系统的过程中，在选择待选船舶问题上建立了 o 1 线性规划模型，然后通过采用两种不同的方法( 一种优化的隐枚举法和遗传算 法) 做比较，实验的结果均达到满意的程度，本文还分析比对了两种算法的性能， 此外，本系统在实际使用中同样达到了满意的效果。 全文共分为五章，第l 章介绍遗传算法；第2 章是决策支持系统概述；第3 章针对 遗传算法的一些问题进行改进优化：第4 章介绍航运船舶配载系统的概况、背景、 功能以及系统设计；第5 章对选船问题建模并求解。 遗传算法研究及在航运船舶配载决策支持系统中的应用 1 遗传算法综述 遗传算法是h o l l a n d 教授最先提出，并慢慢进化为一种迭代自适应的概率性搜索算 法。它很有创意地引进了生物进化论中的“适者生存 的理论，通过竞争与淘汰的策略 来处理优化问题，因此它的全局搜索能力很强大，它把问题的重点放在了性能更高的地 方。 1 1传统优化算法的缺陷 传统上求解优化问题的方法主要有： ( 1 ) 导数方法：找到目标函数的导数值为零的位置或进行大量的迭代计算来得到 最终的最优解。这种方法在处理多峰问题时容易计算得到局部而非全局最优解，且目标 函数必须有良好的连续性或可导性。在解决具体问题时有时甚至无法得到确切的目标函 数，更不用说使用这种方法进行求解。 ( 2 ) 全局枚举法：在整个求解空间中计算每一个点的目标函数值，通过比较各个 点的值得到最终的解。很明显，当解空间的规模很庞大时该种方法的计算量会大得惊人。 ( 3 ) 随机算法：这类算法主要有完全随机算法、爬山法和模拟退火法。完全随机 法应用了“蒙”的策略，效率很差。传统的爬山法是通过对解空间小范围的尝试来寻找 最优解的，该方法受最初采样空间和单方向搜索的局限，很容易搜索到局部而非全局最 优解。模拟退火是一种基于蒙特卡罗迭代求解的启发式随机性搜索算法，它尝试学习高 温物体退火的一个过程，寻找目标函数的全局解空间中的最优解。它可以避免陷入局部 最优点，但是致命的缺点是收敛速度太慢，运行时间太长。 1 2 遗传算法的基本步骤 遗传算法的基本思想是，对问题的可行解进行二进制的编码从而得到一个串，随机 选择若干可行解，组成原始种群。根据优化目标设计适应度函数，得到种群里每个个体 的适应度函数值，依据适应度函数值的大小确定种群中每个个体的选择概率，让适应性 强( 适应度函数值大) 的个体获得比较多的交叉、遗传机会。通过选择、遗传和变异生 成子代，反复迭代，最终获得问题的满意解h - 9 。 ( 1 ) 编码：遗传算法在搜索之前首先确定变量的编码规则，把一些随机解编码成 一个固定长度的字符串，将这些随机解生成的字符串放在一起就组成了一个解空间( 称 为染色体) 。 ( 2 ) 制造最初种群：随机制造一定数量的初始编码串，一个编码串叫做一个个 大连理工大学硕士学何论文 体，这些个体形成一个种群。遗传算法将这些随机个体定作起点进行迭代。通常原始种 群个体的质量会很差，遗传算法所要做的就是从随机个体开始，模仿生物的进化历程进 行优胜劣汰，最终迭代出非常杰出的种群与个体。 ( 3 ) 适应度函数的选择与计算：适应度函数用来衡量个体的好坏，相当于生物界 中种群个体对大自然适应力的高低，对于不一样的问题适应度函数有着不一样的定义方 法。如果是对函数进行优化操作，通常目标函数就是适应度函数，也有一些问题适应度 函数较难确定。对环境的适应能力是进化论中自然选择的能动力，它决定了一个个体能 够顺利地生存并繁殖下去的可能性；同理看遗传算法，这同样决定了杰出个体成功保留 到下一代的可能性。 ( 4 ) 选择后代t 一个种群由个子个体组成，在种群里选取一定量的个体进行繁 衍便是选择操作要完成的任务。种群中个体是否被选择是通过个体的适应度函数值来确 定的，适应度函数值大的个体被选择繁殖的概率就大。选择操作与进化论中的适者生存 理论相一致。常见的选择方法有轮盘选择法、局部选择法、截断选择法和锦标赛选择法 盘占 弋丁o ( 5 ) 染色体交叉：将种群中被继承的两个个体的染色体随机地确定一个位置f ( 1 f 甩) ，交换两个染色体( 编码串) 第f 个字符前面( 或后面) 的一段，繁殖出一对 新的个体，新的个体继承了上一代个体的一些性质，这种染色体的交叉方法就是单点交 叉法。还有多点交叉、顺序交叉、循环交叉等方法。交叉操作同进化论中基因交换的理 论相一致。 ( 6 ) 基因突变：突变对于每一个繁衍的后代个体以较小的概率进行，对于突变的 染色体以一个较小的概率任意地将编码串中某个编码的值改变。通常使用二进制进行编 码时就将o 和1 互换。遗传算法中突变发生的可能性极低，概率通常在 o 0 0 1 ，0 o u 区间 内。突变在进化中的贡献是有机会为种群产生够优异的基因。 ( 7 ) 终止的条件：传统的方法是确定迭代某一个代数。显然，针对不一样的问题 需要的代数也不相同。文献 1 0 给出的自适应遗传算法能够自动确定遗传代数。 遗传算法的整体流程如图1 1 所示。 1 3 遗传算法的特点 遗传算法是一类可以应用于复杂系统优化的具有鲁棒性的随机搜索算法，它和传统 的优化算法比较，主要有以下特点： ( 1 ) 自组织、自适应和学习性。遗传算法排除了算法设计中的一个最大瓶颈，即 需要事先说明问题的全部特点，并需要描述针对问题的不同特点算法应该运用的应对手 遗传算法研究及在航运船舶配载决策支持系统中的应用 段，因此，它可以用来处理复杂的非结构化问题，且有较强的鲁棒性。 “ - 7 墨慧 匹至习 。终止条件 “ 8 一f 否 囱 r 再孺；礤丽 l 塑重堕鏖鱼塑焦i 图1 1 遗传算法基本流程 f i g 1 1 b a s i cf l o wc h a r to f g a ( 2 ) 遗传算法处理的是决策变量的编码。传统的优化算法常常直接作用于变量自 身的值上，而遗传算法只与决策变量的编码打交道，使得我们可以模仿生物学里的染色 体和基因的概念，可以仿造生物界的遗传和进化论，在处理问题时操作染色体更加便利。 ( 3 ) 遗传算法直接以适应度函数作为优化过程中的指挥棒，不需要求导等其他辅 助手段。 ( 4 ) 具有显著的隐并行性。遗传算法并行地搜索一个种群解空间中的各个点。它 的并行性可以体现为两个方面：一是遗传算法是内在并行的；二是遗传算法是内含并行 的。 ( 5 ) 遗传算法应用了基于概率的搜索策略，而不是确定性的规则，所以每次求解 都有可能得到不同的最终解。 ( 6 ) 遗传算法的一个主要的优点是运算时间主要和种群中的个体数量、适应度函 茎蜜 囱囱 大连理工大学硕+ 学位论文 数的复杂性和迭代代数有关系，并且是线性关系，不会像传统的算法那样，运行时间随 解空间规模的增长成指数性增长。 ( 7 ) 形式上简单明了。 1 4 遗传算法的理论基础 遗传算法所要达到的目标是使用当前种群生成比目前个体更优秀的新个体。遗传算 法的理论和方法的研究也都是为了实现这个目标而展开的。 1 4 1 遗传算法的基础理论研究 研究遗传算法的根本是研究收敛性，即在全局解空间中可以找到最优解的可能性。 总的来说，可以分成基于模式理论的收敛性研究和基于随机过程的收敛性研究。 ( 1 ) 随机模型理论 对于有限的解空间与有限的种群，可以把遗传算法的查找过程看成离散时间的马尔 可夫链模型( m a r k oc h a i nm o d e l ) ，这就能够运用现有的随机过程理论将分析做得更严 谨：j r u d o l p h 1 1 】通过奇次有限马尔科夫链得出了标准遗传算法无全局收敛性这个结 论。 e i b e n 1 2 】等使用马尔科夫链得出了杰出个体保存策略的遗传算法可以概率性地 收敛这个结论。 q i 和p a l m i e r i e l 3 1 使用马尔科夫链得出了可浮点编码的遗传算法有全局收敛性这 个结论，但是这个结论是假设种群规模为无穷大的。 ( 2 ) 进化动力学理论 进化动力学的主要内容是对一些特有的运算形式的遗传算法的迭代繁衍过程进行 理论分析。 f l q h o l l a n d 教授阐述的模式定理【14 】可以看做遗传算法进化动力学的基本理论。 积木块假设1 1 4 】对遗传算法的重组功能进行了说明。 模式定理与积木块假设一起形成了在处理优化问题时令遗传算法拥有搜索全局 能力的充分条件，这同时是研究遗传算法的进化过程的基础理论，统称为模式理论。 模式理论为遗传算法打下了坚实的数学基础，通过隐形并行性可以证明每一代计算 有效模式的下限值是甩3 ( c 1 1 2 ) ，其中玎是种群规模，是编码串的长度，c 是一个小整 数，某些文献将结果简化成了，z 3 ，有学者旧获得了迭代的每一代最少产生o ( 2 加1 ) 数量 级的新模式，也就是每次迭代相当于在，z 的指数次方大小这样的子空间内进行查找，这 可以体现出遗传算法查找效率之高。 遗传算法研究及在航运船舶配载决策支持系统中的应用 1 4 2 模式定理 对于遗传算法迭代机制的研究有几种有差异的理论，都是很多理论都没有完美的证 明。最常见的是h o l l a n d 阐述的模式定理。 h o l l a n d 使用了一个特殊符号( 宰) 将“模式”的概念引入进来。模式表示了相像编 码串的模板：除了奉以外其他字符均完全一致的编码串( 这是解空间的一个子空间，也 叫做“超平面 ) 。如，1 11 与1 11 1 ，11 1 0 对应；1 1 幸牛对应于l1 0 0 ，11 0 1 ，1 l1 0 ，1 11 1 。 每个模式编码串可以匹配矿( 七是字符的规模，是出现木的次数，例如在二进制编码中 k 为2 ) 个个体；此外，长度为的编码串存在2 个模式串与之相对应。例如，0 1 1 1 有2 4 个模式串与之对应：0 1 1 1 ，幸1 1 l ，0 1 1 ，枣木。对于规模为m 的种群，能 够表示的模式数最大是m 2 。 将s 中的确定字符数( “0 和“1 的个数) 定义为模式s 的阶，模式s 的“既定 长度是s 中最左侧与最右侧固定字符的距离，他决定了模式中存在的信息的紧密程度。 研究模式时需要考虑的另外一点是它在一个特有时刻的适应度值。将模式s 在时刻t 的 适应度值b ( s ，f ) 定义为：种群中与模式s 的所有染色体对应的平均适应度函数值。 设在时刻t 中种群里存在p 个个体s ，品与模式s 相对应，则： 上 只( s ，t ) = f ( s ) p ( 1 1 ) ，= 1 模式定理的推导过程参考文献 1 】。 模式定理的具体内容是： 模式定理：短的、低阶的且高出平均适应度函数值的模式，在遗传算法的后续代中 以指数方式增加它们的试验次刿。 因为交叉、突变的原因，并不是比平均适应度函数值杰出的模式都为有效的模式， 但在一个模式规模为的种群中，有o ( 妒) 个模式为有效模式f l 】。即遗传算法在迭代 每一代时在运算个染色体的同时，还可以对矿个模式进行并行处理，而且不使用任 何额外的辅助存储空间，这就是隐并行性。也就是遗传算法在解空间中查找的过程可看 成是隐式地对模式进行样本抽取的过程，然后通过染色体的作用把短的低阶的模式的信 息组成高阶高于平均值的模式，直到形成最终解为止。这表明了遗传算法比传统的优化 算法的查找能力更强大。 1 4 3 欺骗问题 在遗传算法过程中，那些阻碍高适应度函数值的模式生成的问题叫做欺骗问题。算 法在种群的进化过程中总是将具有高适应度函数值、低阶、短定义矩等优良特征的基因 大连理工大学硕士学位论文 片段进行重新组合以整合到一个模式上从而产生更为优秀的模式及其所对应的个体，但 在某一时刻具有这些相对良好基因片段的模式可能不包括最优模式所需具备的遗传信 息，因此遗传算法就可能收敛到一个局部最优解。研究欺骗问题的目的是为了预测给定 问题用遗传算法求解的难易程度。 建筑块假设：短的、低阶、高于平均值的模式( 称为建筑块) 逐渐产生高阶高于平 均值的模式，直到最终生成最优解，如果某个问题的编码规则满足建筑块假设，那么用 遗传算法搜索解空间的效率较高，否则搜索效率比较低。低阶建筑块错误地引导求解过 程，使求解过程无法找到高阶的建筑块，使得算法无法收敛，搜索不到最优解，这种现 象叫做欺骗。 g o l d b e r g 描述了一个最小的欺骗问题刚，目的是尽量让问题的编码规则与建筑块的 假设不符，让高阶建筑块无法生成最优解。通过实验发现，对于包含欺骗的优化问题， 用遗传算法有可能搜索到最优解也有可能搜索不到最优解，这表明了欺骗不是用以决定 遗传算法求解问题是否困难的唯一因素。到现在为止还不能确定一个优化问题包含欺骗 问题的数量对遗传算法搜索最优解产生何种影响，因为对导致遗传算法无法正常工作的 原因还没有完全搞清楚。 为了成功应用于实际问题，人们对算法采取了很多很好的改良措施，主要有： ( 1 ) 对参数值的优化：主要是对种群的个体数量，交叉概率b 以及突变概率 的优化问题。 ( 2 ) 怎样避免早熟现象，即怎样避免种群中的个体提前在解空间中的一个否最优 点附近聚集。 ( 3 ) 在传统的遗传算法的前提下提出新的算子，从而提高算法的迭代效率。 ( 4 ) 在理论层面上研究遗传算法如何在全局范围内收敛到最优解。 以上讨论已经获得了许多有效的成果，进一步的研究有待继续进行。 遗传算法研究及在航运船舶配载决策支持系统中的应用 2 决策支持系统概述 数字计算机应用于管理领域，主要是进行数据处理和编制报表，实现数据库管理办 公的自动化。通常将这类系统所涉及到的技术称为电子数据处理( e d p ) 。e d p 将人们 从繁琐的事务处理中解脱出来，大大地提高了工作的效率，但它存在着对信息交换和资 源共享及其增删改操作等问题。因此有必要对系统的信息进行整体分析和系统设计，进 而使工作更加协调一致。 信息管理系统( i m s ) 是以人为主导，使用计算机软硬件来进行信息的收集、加工、 存储、传输、更新以及维护，以企业战略竞优、提高效益和效率为目的，支持企业高层 决策、中层控制、基层运作的集成化人机系统。i m s 能监测各类运行的状况，使用以前 和现在的数据来预测未来的数据，使用信息对企业行为进行控制，协助企业完成其规划 目标的实现。 运筹学、系统工程和计算机的结合，形成了模型辅助决策系统。由于采取的模型主 要是数学模型，辅助决策的能力主要体现在定量分析上。决策支持系统将管理信息系统 与模型辅助决策系统结合起来，将数值计算和数据处理融为一体，进而提高了辅助决策 的能力。 2 1 决策支持系统的基本含义 决策是人们为实现一定目标而制定的行动方案并准备组织实行的活动过程。决策支 持系统( d s s ，d e c i s i o ns u p p o r ts y s t e m ) 是以管理科学、运筹学、控制论和行为科学为基 础，以计算机技术、人工智能技术和信息技术为手段，智能化地进行决策活动的支持的 计算机系统。决策支持系统通过人机对话进行分析、比较和判断，识别问题，建立或修 改模型，协助决策者明确决策目标，为决策者提供各类方案并对其进行评价和选择，为 正确决策提供有益的帮助【1 7 。1 9 1 。 决策支持系统具备如下的特征： ( 1 ) 辅助决策主体在半结构化或者非结构化的任务中来制定决策。 ( 2 ) 辅助但不是代替用户制定决策。 ( 3 ) 改进决策效能，而非提高决策的效率。 决策支持系统是管理信息系统( m i s ，m a n a g e m e n ti n f o r m a t i o ns y s t e m ) 高级阶段的 一种形式，可以单独作为不同于m i s 的系统而存在。 2 2 决策支持系统的发展历史与现状 大连理工大学硕士学位论文 2 0 世纪7 0 年代末，传统的m i s 对多变的外部及内部管理环境已经力不从心，对管理 人员的辅助作用几乎可以忽略，因此人们希望重新设计一种全新的用于管理的信息系统 能够解决m i s 存在的问题，确实能辅助管理人员做一些事情，这时d s s 应运而生。d s s 最早是由美国麻省理工学院的m i c h a e ls s m o r t o n 和p e t e r g w k e e n 提出的。 1 9 7 8 年至1 j 1 9 8 8 年的十年间，d s s 的发展速度极为迅猛，许多为辅助管理的软件都被 扣上d s s 的名号。在科学技术发展迅速的当今社会，新技术层出不穷，d s s 在技术上已 经不存在绝对的难点，最主要的问题是我们怎样结合具体情况选择适当、有效的新技术， 将理论运用于实际，更有效率地帮助人们解决实际问题。 从辅助个人决策到辅助组织决策，从处理数据的d s s 至u 处理知识的d s s ，从把模型 做为过程处理到模型的产生与管理等，都表明了d s s 的发展的迅速。 d s s 进一步的发展方向是：种群决策支持系统( g d s s ) ，智能决策支持系统( i d s s ) 以及分布式决策支持系统( d d s s ) 。未来决策支持系统发展的方向是高度智能化，通 过多种知识类型表示、自组织协同工作、自动学习知识和白适应能力强等为特点的。 2 3 决策支持系统的理论基础和相关技术 ( 1 ) 信息论 使用信息的理论，将系统定位成是通过抽取、传递、处理信息进而达到目的的应用 方法。d s s 是用来加工信息的，它的基本概念与理论基础要依靠信息论中的分析方法加 以解释与陈述。 ( 2 ) 计算机技术 计算机的软、硬件是d s s 实现目标的基本工具，计算机技术是实现d s s 目标的基础 和重要的约束因素。 ( 3 ) 管理科学和运筹学 管理科学与运筹学一般处理优化、模拟以及建模等相关问题。 ( 4 ) 信息经济学 信息经济学是分析信息的出现、提取、传送、加工处理、输出等方面的成本问题。 信息经济学分析的领域例如规则、语法、满足用户愿望的程度、获得信息便利程度、获 得信息的时间长短等都是d s s 所要考虑的问题领域。 ( 5 ) 行为科学 d s s 可以对社会变化的进行管理，强调过程的动态性、变化中产生的困难以及产生 变化程序的需求。研究行为科学可以抽取出管理人员的共同特点，从而帮助d s s 的分析 和研究。 遗传算法研究及在航运船舶配载决策支持系统中的应用 ( 6 ) 人工智能 d s s 中提出了人工智能这个技术，尤其是专家系统中的知识推理技术，模仿管理者 的思维方式与过程，根据管理者的需要通过提出问题、分析问题、应用有关规则指导管 理者选择正确的模型，从而把d s s 推向一个新的高度。决策支持系统和专家系统虽然归 于不同的学科领域，求解问题的过程有很大差异，但将专家系统引入到解决管理科学中 半结构和非结构化的问题中来，可以为d s s 提供高效的理论和方法的帮助。 ( 7 ) 数据仓库 数据仓库( d w ) 系统从分布的、异构的信息源中抽取、清理和集成数据，用以帮 助管理者更好更快地进行决策分析。 ( 8 ) o l a p o l a p ( o n l i n ea n a l y t i c a lp r o c e s s i n g ，联机分析处理) 是大量多维数据的动态综合、 分析和合并技术，通过上卷、下钻、切片、切块、转轴等操作，能够帮助管理者高效地 得到他们想要得到的信息。 ( 9 ) 数据挖掘 数据挖掘( d m ) 从大量数据中抽取对人们有用的知识，而这些知识是隐藏的、未 定的和潜在有用的，将抽取的知识表示为概念、规则、规律、模式等，帮助管理者高效、 正确地做出决策。 ，( 1 0 ) 知识管理 知识管理包括对知识层次、类别地合理划分，对知识管理流程的规范化、科学化以 及对知识内在规律的深入挖掘。通过使用知识管理中本体分类等方法和手段，从海量的、 异构的信息中进行知识的抽取和整理，从而使知识得到更好的重用、组织和积累，提高 组织的灵活性和反应速度。知识是决策制定的前提与依据。 2 4 决策支持系统的体系结构 决策支持系统在发展的过程中经历了两库系统、三库系统等。两库系统指的是模型 库系统( m b m s ，m o d e lb a s em a n a g e m e n ts y s t e m ) 和数据库系统( d b m s ，d a t a b a s e m a n a g e m e n ts y s t e m ) ，三库系统除了两库系统中的两个系统外还多了一个方法库系统 ( m e b m s ，m e t h o db a s em a n a g e m e n ts y s t e m ) 。交互式系统中一个典型的例子是决策支 持系统，它必须通过大量的人机交互模式才能做出更科学、更合理的决策，因此还应将 人机接口系统( d g m s ，d i a l o g u eg e n e r a t i o nm a n a g e m e n ts y s t e m ) 加入到决策支持系统的 体系结构中来。而包括了推演、翻译等功能的知识库系统( k b m s ，k n o w l e d g eb a s e m a n a g e m e n ts y s t e m ) 也是决策支持系统极为重要的组成部分。综上所述决策支持系统 大连理：1 二大学硕士学位论文 的体系结构如图2 1 所示。 图2 1决策支持系统体系结构图 f i g 2 1 t h eg e n e r a la r c h i t e c t u r eo fd d s 2 5 决策支持系统总结 决策支持系统比管理信息系统的发展高出了一个层次，支持决策的主体在半结构化 或非结构化的任务中产生决策。决策支持系统的产生、快速地发展以及成功地运用都证 明了信息处理技术已经实现了巨大的突破。决策支持系统是可以应用在不同学科不同领 域的崭新的信息系统分支。决策支持系统使得信息管理系统更加强大，决策支持系统如 同为企业移入了大脑。 决策支持系统早先是通过数据和模型来帮助管理人员进行决策，经历了一个长足地 发展以后，决策支持系统吸收和融入了更多领域学科的方法与手段，越来越朝着更智能 化的方向发展着。今后决策支持系统将为社会的进步和企业的管理决策做出越来越巨大 的贡献。 遗传算法研究及在航运船舶配载决策支持系统中的应用 3 遗传算法的进一步改进 3 1对传统遗传算法各步骤的优化 3 1 1 编码方式的优化 编码串最常使用的方式是二进制形式，不过如果遇到解空间是连续型的问题，就会 产生精度缺失现象。并且一般的二进制形式编码串会导致早熟收敛，为了避免这些问题， s c h r a u d o l p h 等人引入了动态变量编码( d y n a m i cp a r a m e t e re n c o d i n g ，简称d p e ) 。d p e 会动态地调整变量的定义域，当采用一个方法确定种群收敛时，那么变量的定义域就会 调整得更小，从而可以进一步锁定搜索范围。s c h r a u d o l p h 等人通过测试d e j o n g 的石石 函数，得出结论应用d p e 后改进效果只有多极值函数居没有得到优化。 3 1 2 对适应度函数的优化 适应度函数的设计是遗传算法能否找到优秀解的关键，针对适应度函数设计准则的 研究也层出不穷。普通的适应度函数容易在早期使个别的杰出的个体后代占满整个群 体，导致早熟收敛。在算法后期适应度函数值不再变动，杰出的个体在生成子代时无法 显现出优越性，最终导致群体无法继续进化。因此有必要对适应度函数做适当的伸展操 作，从而使杰出的个体的优越性更加显著。g o l d b e r g 等使用线性变换方法进行伸展操作， 确保伸展后得到的群体的平均适应度函数值保持不改变，最杰出的个体适应度函数值是 平均值的a 倍，据此确定a 、b 参数。 厂，一j 西+ 6 ，z 0 r 冀1 、 山一l - o ，z o w h7 万是第f 个个体的适应度函数值，通常a 取2 ，它将群体个体的适应度函数值调整为一 个等差数列的形式，进而有效地避免了停滞和早熟的发生。 3 1 3 对交叉操作的优化 传统遗传算法只在染色体上进行单点交叉操作。但是当染色体长度过长或者染色体 代表几个变量的时候，采用单点交叉常常会达不到期望的效果，这时使用多点交叉操作 通常可以更好地提高遗传搜索的效率。常用的多点交叉法为两点交叉法和均匀交叉法。 两点交叉与单点交叉类似，在染色体上任意选择两个点，然后将两点之间的一段编码互 换。均匀交叉是从父代染色体中以适当的概率任意选择等位基因形成两个子代的染色 体。这两种优化方法在通常状况下都好于单点交叉。此外还有顺序交叉和循环交叉等方 法，它们各有自己的优点。文献 2 0 】指出一般情况下均匀交叉比两点交叉要好。 大连理工大学硕士学位论文 3 1 4 对交叉概率和突变概率的优化 标准遗传算法本身存在着早熟即过早收敛于局部值等缺陷，这给遗传算法的应用带 来了很大的不便。 遗传算法的参数中交叉概率只和突变概率p m 的选择是影响遗传算法行为和性能的 关键所在，直接影响算法的收敛性，只越大，新个体产生的速度就越快。然而，尸。过大 时遗传模式被破坏的可能性也越大，使得具有高度适应性的个体结构很快就会被破坏； 但是如果只过小，会使搜索过程很慢，以至停滞不前。对于突变概率如，如果r 过小， 就不易产生新的个体结构；如果 取值过大，那么遗传算法就变成了纯粹的随机概率 搜索算法。针对不同的优化问题，需要反复实验来确定只和厶，这是一个繁琐的工作， 而且很难找到适合每个问题的最佳值。s r i n v i v a s 等提出一种自适应遗传算法( a d a p t i v e g a ，a g a ) ，p c 和厶能够随个体的适应度自动改变。 在自适应遗传算法中，交叉概率以和突变概率厶按如式3 2 、3 3 自适应调整【1 7 1 ： r， ，j 反：卜石m a r 乏一j ，广厶 ( 3 2 ) l 岛，f 厶 lff p 。： t k ，厶j “一- 石j 厂 ( 3 3 ) 【，厂 厶 其中缸为种群里最大的适应度函数值；是每代种群的平均适应度函数值；厂是要交 叉的两个个体中较大的适应度函数值；厂是要突变个体的适应度函数值；k ，恕，岛，乜 在 0 ，1 】取值。 从以上公式可以看出，当适应度值越接近最大适应度值，r 和厶的值就越小；当 等于最大适应度值时，尸c 和厶的值为零。这种调整只和厶的方法对于群体处于进化 后期时比较适合，因为在进化后期，群体中每个个体基本上表现出较优的性能，这时不 宣对个体进行较大的变化以免破坏了个体的优良性能结构；但是这种调整方式在群体处 于进化初期阶段时显得进化过于缓慢，因为在进化初期阶段群体中的较优良个体几乎处 于一种不发生变化的状态，而此时的优良个体不一定是问题的全局最优解，这容易使进 化走向局部最优的可能性增加。 针对以上问题对只和厶做如下改进，使群体中最大适应值的个体的r 和尸m 不为 零，分别提高到尸c 1 和p c 2 。 遗传算法研究及在航运船舶配载决策支持系统中的应用 驴卜与当_ 厶 慨4 ，以：p 一瓦彳2 ( 3 4 ) i 见1 ，哪 胪卜 当p ，厂厶 5 ， l p 。，厶 其中：p 。l = 0 9 ，p c 2 - 0 6 ，p m 尸o 1 ，p 小2 = 0 。0 1 。 这样就相应地提高了群体中表现优良的个体的p c 和尸m ，使得他们不会处于一种近 乎停滞不前的状态。因此，自适应的巴和p 聊能够提供相对某个解的最佳尸c 和尸册。改 进的自适应遗传算法在保证群体多样性的同时，保证遗传算法的收敛性1 2 1 1 。 3 1 5 对生成子代方法的优化 在上面提到的操作中，选择、交叉、突变三种操作是通过父代种群繁衍出子代种群 的。传统遗传算法在产生子代时将父代个体全部抛弃，全部使用繁衍下来的子代个体， 这样在父代中较杰出的个体就损失掉了。子代个体对环境的适应能力不可能全部强于父 代个体，这是显而易见的，因此在进化