金菊良、丁晶著《水资源系统工程》1 绪论.doc

第1章 绪论1.1 水资源系统工程与遗传算法从系统的组成角度看，系统是由两个或两个以上相互联系的要素组成的、具有整体功能和综合行为的集合1-5。该定义规定了组成任何系统的3个条件：组成系统的要素必须两个或两个以上，它反映了系统的多样性和差异性，是系统不断演化的重要机制；各要素之间必须具有关联性，系统中不存在与其它要素无关的孤立要素，它反映了系统各要素相互作用、相互激励、相互依存、相互制约、相互补充、相互转化的内在相关性，也是系统不断演化的重要机制；系统的整体功能和综合行为必须不是系统各单个要素所具有的，而是由各要素通过相互作用而涌现（emerge）出来的。与系统要素相关联的其它外部要素的集合称之为系统的环境，它是研究对象全空间R中系统集合S与非系统集合F的过渡集合E，它们之间存在如下关系：R=SEF，SF=（空集）。系统的边界把系统与系统的环境区分开来，环境的边界把系统的环境与非系统集合区分开来。系统的边界和环境的边境具有弹性和动态性，是不断变化的，反映了不同的研究时间、研究条件和研究要求，由此决定了系统的层次性，即一个系统既可以向下分解为一系列子系统，又可以向上隶属于更大的系统。 从系统与系统环境的相互作用的角度看，系统是由系统输入、系统转换和系统输出组成的集合。系统输入是环境对系统的作用或激励，系统输出是系统对环境的作用或响应，系统转换是以系统输入为定义域、系统输出为值域的映射。系统输入可以是物质变量、能量变量或者信息变量，相应的系统输出也可以是这三类变量。例如6：可以把到达流域地面的降雨作为系统输入，把流域的下垫面的作用作为系统转换，把水向大气中蒸发、水向深层地下水渗透、水进入河网作为系统输出，这三者组成流域产流系统，而把水在大气中的运动、在深层地下水的运动和在河网中的运动视作流域产流系统的环境；可以把降雨经过下垫面的截留、填洼、下渗和蒸发等损耗后所剩余的“净雨过程”作为系统输入，在流域出口断面的流量过程作为系统输出，把由净雨过程到流量过程的转换过程作为系统转换，这三者组成流域汇流系统，而把水在流域下垫面上的截留、填洼、下渗和蒸发过程等视作流域汇流系统的环境。根据系统与系统环境的相互作用，运用系统输入系统输出不同的关系分析，形成了系统优化、模拟、预测、评价和决策分析等一系列处理系统问题的一般方法。 “工程”的本义是指服务于特定目的的工作程序2，7，因此，系统工程（systems engineering）就是服务于一般系统的开发设计、组织建立或者运行管理的工作程序的一门工程技术学科，它包括运筹学（operations research）、系统分析（systems analysis）、系统研究（systems research）、费用效果分析（cost-effectiveness analysis）和管理科学（management science）等中可用于工程实践的各种定量方法和定性定量集成方法。系统工程的研究对象是任何一种物质系统或任何一种概念系统，包括自然系统、工程技术系统、社会经济系统、管理系统、军事指挥系统等。在现代科学技术的四层次体系结构中2，5，系统工程属于工程技术层次，它的技术科学是运筹学、一般系统论、信息论、控制论等，它的基础科学是尚在建设中的系统学，它的哲学是辨证唯物主义和历史唯物主义。系统工程是介于哲学方法论和专门科学方法论之间的一般科学方法论，它一端与哲学方法相连结，另一端又与其它专门科学方法紧密结合，推动了科学方法论向整体性、深刻性和普适性方面不断发展3。系统工程思考问题的一般方式（系统观点）是，任何研究问题都可作为有关研究对象组成的一个系统，必须从时间上动态长期的、空间上普遍联系的和属性上整体协调的观点来最佳地分析、设计、组织、管理该系统。这种系统观点可以用“白日依山尽（青山依旧在，几度夕阳红：时间上动态长期的），黄河入海流（黄河之水天上来，奔腾到海还复来：空间上普遍联系的），更上一层楼（登高望远：属性上整体协调的），欲穷千里目（把问题看清楚：最佳地处理问题）”来简单概括。系统工程处理问题的一般方法称之为系统工程方法论，目前最有代表性的有两类方法论1，5：一类是以“最优化”为核心的霍尔（A.Hall）系统工程方法论，按照“明确问题目标选取方案设计建立数学模型最优化计算决策分析决策实施”的方式展开，适用于各种复杂的工程技术问题；另一类是以“比较学习”为核心的切克兰德（P. Checkland）系统工程方法论，按照“说明问题现状确定与改善现状有关的因素建立描述问题现状的概念模型改善概念模型模型和现状的比较决策实施”的方式展开，适用于各种复杂的社会经济问题。系统工程和水利工程、电子工程、机械工程等传统工程技术一样，都是从实际问题和条件出发，运用相应的基础科学和技术科学的基本理论和方法，以改造客观世界使其符合人类需要为目的的，但两者有很大的不同，主要表现在1，3，5，8-10：“工程”的内涵不同。传统工程技术的“工程”是指应用自然科学原理和方法于实践，设计和生产出诸如水库、大桥、铁路、建筑物等有形实体（“硬件”）的技术过程。而系统工程中的“工程”概念既包括上述“硬件”的设计与建造，又包括与这些“硬件”紧密相关的概念、思想、规划、计划、方案、程序等（“软件”）活动过程，即为硬件与软件的复合工程，延拓了传统工程技术的“工程”的含义。研究对象不同。传统工程技术的研究对象是各自特定领域内的工程实体对象，着眼于物质运动和能量转换。而系统工程的研究对象是一般系统，既包括各种传统工程技术中的实体对象系统，也包括生态、环境、社会、经济、管理等非实体即概念对象系统，还包括实体对象系统与概念对象系统相结合的复合系统，着眼于研究对象的信息流动。在实际运用系统工程时都把所研究的问题看做一个系统进行研究。这些系统中的各种信息是系统工程的主要研究对象。因此，系统工程不是研究某一类系统的工程技术，而是研究各种系统普遍适用的一门综合性工程技术。在运用系统工程解决实际问题时，系统工程必须与所研究的系统本身所在的学科相结合，从而形成不同的应用系统工程学科，例如水资源系统工程、环境系统工程、资源系统工程、农业系统工程、管理系统工程、军事系统工程和社会系统工程等。学科的任务不同。传统工程技术是着眼于技术的合理性、用来解决某个特定领域中的具体技术问题。而系统工程的任务是解决系统内部各要素之间、各要素与各子系统之间、各子系统之间、系统与环境之间的协调问题，使系统整体最优化和整体协调化。研究的方法和成果不同。传统工程技术所使用的方法是在明确目标后根据条件，采用可能实现目标的方法，提出不同方案进行设计、试制出原型，经试验后最终达到生产和建设的目的，它所使用的方法明显体现出“物理”特征，它所提供的是处理问题的答案。而系统工程的研究方法和结果对传统工程技术而言具有方法论性质，如系统、信息、结构、功能、控制、反馈等范畴，系统观点，以及优化、协调、建模、预测、模拟、评价、决策等各种系统工程方法等，可适用于各种传统工程技术领域，它所使用的方法明显体现出“事理”和“人理”特征，它所提供的是处理问题的过程（行动策略）。系统工程具有多学科综合性的特点，它是综合应用系统科学、自然科学、数学、计算机科学和计算机技术、传统工程技术、管理科学、经济学、社会科学等各种学科知识、组织管理各种复杂系统、横跨众多学科的工程技术学科，只有应用各种学科的广泛知识，才有可能有效地规划设计、管理控制一个复杂系统。水资源系统工程（water resource systems engineering）是应用系统工程方法对水资源系统进行综合考察和分析，并优化水资源工程规划和运行管理的工程技术5，11。从基于研究对象的水资源系统问题分类角度，水资源系统工程的主要研究内容包括河流水资源综合开发利用规划与管理、流域水资源综合开发利用规划与管理12、地下水水资源综合开发利用规划与管理8、农田灌溉系统规划与管理、城市供水系统规划与管理、水力发电工程系统规划与管理、防洪工程系统规划与管理13、抗旱系统规划与管理、航道工程系统规划与管理、水污染控制系统规划与管理、水资源可持续利用与管理等内容14，15。从基于研究过程的处理水资源系统问题的方法论角度，水资源系统工程的主要研究内容包括1，11，13：根据所研究的水资源问题确定水资源系统的目标、功能和边界，从水资源系统整体协调出发，按照系统本身所特有的性质与功能，研究系统与环境之间、系统与各子系统之间、子系统与子系统之间、子系统与各要素之间、各要素之间的相互作用与相互依赖的关系，建立相应的数学模型，并应用系统优化方法、系统建模方法、系统预测方法、系统模拟方法、系统评价方法、决策分析方法以及结合从定性到定量综合集成方法等，定量地或半定量地求解水资源系统规划与管理的优化方案。水资源系统工程处理问题的一般步骤是1，5，8，13：根据所研究的水资源问题的性质、目的，研究问题所包含的要素、要素之间的联系和要素与研究问题外部的联系，确定研究问题的范围，并定义为水资源系统。选择评价系统功能的目标、准则和指标集，建立水资源系统的评价指标体系。目的可用定性方式描述，而目标、指标则一般都需要尽可能用定量方式描述。根据所确定的评价指标体系，通过实验、调查、观察、记录以及引用文献等形式收集有关资料，对照系统目标整理资料，找出影响系统目标和功能的因素集，然后提出实现系统目标的各种替代方案。确定影响系统目标和功能的主要因素及其相互关系，定义系统输入、系统转换、系统输出、系统目标函数和系统约束条件形式，建立系统模型。利用系统模型可以分析影响系统目标和功能的主要因素及其影响程度，确定这些因素的相关程度、总目标和各分目标的实现途径及其约束条件。利用已建立的各种模型对各种替代方案可能产生的结果进行计算、模拟和预测，分析各种指标达到的程度。在上述分析的基础上，再结合各种定性因素，通过相应的系统评价方法，把各种替代方案各指标值综合成单一指标值的形式，以表示各方案达到系统总目标的程度，据此确定各方案的优先顺序，供决策者参考。当研究问题十分复杂、步骤仍未能确定处理所研究问题的最优方案时，需进一步确定反映决策者对研究问题的主观意图和倾向的决策准则，分析各替代方案在未来各种自然状态下的益损值矩阵，通过相应的系统决策分析方法，来求解以替代方案为优化变量、以自然状态为约束条件、以反映决策准则的益损值矩阵的函数为目标函数的特殊的优化问题，最终选择和决定最佳方案。从工程技术角度分析水资源系统工程处理问题的上述步骤，水资源系统工程也可以认为就是由一系列系统优化方法、系统建模方法、系统预测方法、系统模拟方法、系统评价方法、系统决策分析方法组成的方法集，用以最佳地处理所研究的水资源系统问题16。其中，水资源系统优化方法是应用其它水资源系统工程方法的基础。水资源系统工程的主要特征是整体性、关联性、协调性、系统化、模型化、最优化和实践性。 目前，水资源系统工程方法论是以霍尔系统工程方法论为主、兼有切克兰德系统工程方法论，并随着水资源系统工程理论和实践的不断发展，切克兰德系统工程方法论的比重也将不断提高，这是由水资源系统所包含的自然属性、生态环境属性和社会经济属性这三方面的复杂性所决定的。这些复杂性主要有如下几个方面13，17-20：水资源的内涵具有层次性。与人类社会经济和生态环境的生存与发展密切相关的所有淡水（例如大气降水、地表水、地下水、土壤水等），称之为广义水资源；人类社会只有通过对广义水资源的开发利用才能实现从自然资源向实物资源的转变的那部分广义水资源（例如径流性水资源），称之为狭义水资源；根据水资源可持续利用观点，可对狭义水资源进一步划分为生态需水量和国民经济可利用水资源。随着水资源系统工程的理论与实践的不断发展，水资源的内涵也必将进一步展开为自然资源、社会资源与知识资源三中形式21。可见，水资源系统是自然系统、生态系统和社会系统相复合的复杂大系统。水资源的不可替代性与可再生性。水资源对于饮用、卫生、农业、林业、畜牧业、渔业、工业、水力发电、航运、娱乐和许多其它人类活动，以及对于人类社会赖以生存和发展的大自然环境的正常运行而言，都是不可替代的。同时，水资源通过各种水分循环的形式来反映其可再生性。水资源承载能力的多样性、有限性与时空分布的不均衡性。水资源工程系统建设和管理的前期性与长期性。随着社会经济的发展和人民生活水平的不断提高，对狭义水资源的数量需求和质量需求也在不断提高，相应的水资源工程系统的建设和管理的前期性与长期性也日益明显。水资源系统组成要素的层次性和大规模性。水资源复杂系统一般是由天、地、人三大子系统组成，而每个子系统又包括各自的子系统。如此逐层分解，形成了庞大的层次结构，具有很高的维数，系统所覆盖的时间和空间范围大（长期、中期、短期，全球、国家、流域、省市、地县、镇村，大气水、地面水、地下水、泉水和土壤水、生物水），造成计算机的沉重时空负荷，而且难以满足系统在线实时控制的需要。在不同层次上研究所关心的问题是不同的，系统的运行方式和机制也存在着很大差异。实际常遇到的水资源系统，例如河流综合利用系统、大型灌区水资源开发利用系统、城市供水系统、城市下水道系统、农田灌溉系统、防洪工程系统、水旱灾害监测评估系统、水运系统、水污染控制系统、水/火电站群联合优化调度运行系统以及中国西部水资源优化配置与可持续开发利用系统等，都是由天文、气象、下垫面、生态、人文等地球表层众多要素组成的复杂系统。水资源系统各要素之间或各子系统之间的关联形式多种多样，这些关联的复杂性表现在结构上是各种各样的非线性关系，表现在内容上可以是物质、能量或信息的关联。水资源系统的演化特性以适应环境的不断变化。作为开放的系统，水资源系统不断地与其所在的自然环境和人文环境发生着物质、能量和信息方面的交换和作用，由于这些环境的变化和不确定性，引起了水资源系统的输入输出强度与性质不断地变化，并进一步引起水资源系统的结构、功能和目的的变化，从而使水资源系统呈现出显著的演化特性。这种演化，一方面表现为系统趋近并达到均衡（相对平衡状态）并从一个均衡向另一个均衡转移的非均衡过程，另一方面表现为整个系统的结构、功能的变动，以及由此引发的系统均衡格局的变迁。这种演化的行为方式主要有多重均衡（演化问题可能同时存在多个最优解）、路径相依（演化过程与系统的初始状态有关）、分岔、突变、锁定（当系统进入一个均衡态后，若无足够的外界扰动等条件，系统将只能在该均衡态附近波动而无法转移至其它的均衡态）、复杂周期等。例如都江堰水利工程系统中飞沙堰子系统就能根据系统环境中洪水大小变化和泥沙多少变化进行相应的分洪排沙，以保证整个系统能长期安全运行。水资源系统的空间结构特征。受水分循环规律的支配，降水量具有明显的地域分布特征（中国降水量呈由东到西递减的趋势），从而确定了水资源系统空间结构的主要特征；另外，地势、土壤、植被的不同分布和人类活动也在一定程度上影响水资源的空间格局。所有这些因素决定了水资源系统的空间结构经纬交叉、错综复杂。目前研究水资源可持续利用与管理，已从单一河段、单一河流的开发利用研究，转移到全流域、跨流域的水资源统一调配研究、地表水与地下水统一开发利用研究，水资源系统的空间结构特征更为令人关注。水资源系统的社会政治特征。一方面，水是万物生命之源，一个国家或地区经济发展和社会发展越来越受该国家或该地区水资源系统运行状况的约束，水资源短缺危机在世界各地日益暴露，危机程度也在日益加深，导致许多地区冲突；另一方面，水量过多将产生水灾，水量过少又会引起旱灾，水质受到污染还会导致重大环境问题。可见水资源系统问题已成为国家或地区社会经济可持续发展的瓶颈，已成为重大战略性问题。前面9个方面的复杂性往往是相互联系、交织在一起的，随着水资源系统工程理论和实践在深度和广度方面的展开，这些复杂性的程度将越来越高。21世纪中国水利的发展战略将从工程水利向水资源可持续利用方向进行重大转移，研究水资源系统已不能就水论水、就河论河、就工程论工程，而必须把水资源与生态环境、经济结构、人口结构、社会结构组织在同一个复杂大系统（社会经济资源与环境可持续发展系统）下进行综合研究13-19，22，这给水资源系统工程的理论与实践的快速发展带来了难得的机遇和挑战。针对这样的复杂系统，目前普遍认为，采用常规的机理描述和推理难以建立其完整的模型。这是因为复杂系统的行为本质既包含“高维性”又包含“混杂性”23。所谓“高维性”是指复杂系统要素繁多，往往需要做“多目标多要素多层次分析”；所谓“混杂性”是指确定性与不确定性、正态与非正态、定性与定量、静态与动态、宏观与微观、平衡与非平衡等特征的混杂。水资源系统工程的大量实践证明，随着水资源工程实践中所遇到的水资源系统日益大型化、综合化和智能化，研究水资源系统问题已避不开它的复杂性，常规的系统工程方法和手段已难以胜任水资源复杂系统中涉及多因子、多层次的综合分析，只有打破学科、部门、行业界线，把系统科学的其它理论和方法以及计算机、人工智能等现代科学与技术中的最新成果进一步引入水资源系统工程的研究中并进行相应创新，采用多学科交叉渗透和综合集成的研究方法，才能系统地探讨和研究水资源复杂系统的预测、评估与决策等综合性复杂问题，才能为实现人类对水资源复杂系统的有效调控和科学管理提供重要依据。常规的水资源系统工程各种方法在上述水资源系统的复杂性面前遇到了不同程度的挑战。例如，在水资源系统建模方法方面的挑战主要表现在：系统模型结构的不确定性。在客观上，水资源系统要素一般十分庞大而复杂，系统状态具有某种程度的不确定性，受当前科技水平和条件的限制，往往难以用合适结构的数学模型来精确描述；为适应系统环境的不断变化，系统结构和功能也在不断调整、变化。而在主观上，为掌握系统的状态，必要的观测量会很大，同时在高精度下观测又很困难，受建模者的知识、经验和能力的限制，为便于模型求解，提出的模型结构不得不建立在许多假设条件和经验公式之上。系统模型的数值求解的不确定性。由于水资源系统模型具有高维高度非线性，常规方法处理线性、低维模型较为成熟，而对大多数高维高度非线性水资源系统模型往往不能取得满意的结果。系统模型中庞杂信息类型所产生的不确定性。同一水资源系统中往往既含有大量时间、空间和统计等方面的确定性信息，又有众多不确定性信息，如随机性信息、模糊性信息、灰色性信息、混沌性信息、错误信息和主观信息，后者如在水资源缺乏或人类活动影响强烈的地区以及在水资源评价和开发利用、水资源工程经济运行和日常管理中，往往遇到难以用精确数值表示的信息，它们常以经验性语言、知识或规则的形式出现。常规方法已无法妥善求解混杂这些信息类型的系统模型。完全掌握系统模型的这些信息，由于系统的复杂而变得不可能，同时因获得这些信息需要很大成本而变得不可行。所有这些不完备信息和不确定信息将导致系统模型结果的不确定性。系统模型的多目标性。水资源模型的目标既有兴利目标，又有除害目标。前者如农业用水、工业用水、旅游业用水和生活用水等目标，后者如水旱灾害、环境问题和生态问题等目标，这些目标还可向下展开许多子目标，其中有些目标是可定量的，有些是不可定量的，这些目标在系统模型中如何协调、平衡以达到综合最优将会导致模型结果的不确定性。系统模型中自然要素与社会要素的相互关联和相互作用所产生的不确定性。 自古以来，人类的一切活动都是为了能生活得更好些。寻求最佳效果的愿望几乎渗透到各种社会实践活动中，在这类范围广泛的社会实践基础上，在当代通过各门科学技术的不断交叉、渗透和综合，优化已成为系统乃至整个世界发展的趋势和走向，反映到水资源系统工程研究中，优化准则日益成为人们分析系统、评价系统、改造系统和利用系统的一种衡量尺度。水资源系统工程的最终目标就是水资源系统设计和规划的最优化、水资源系统运行和管理的最优化。水资源系统优化方法是应用水资源系统工程其它方法的基础，当前水资源系统工程理论与实践中的重点和难点之一就是如何求解应用水资源系统工程方法过程中的各种复杂的优化问题24。优化问题（optimal problem）就是如何寻找优化变量各分量的某种取值组合，使得目标函数在给定约束条件下达到最优或近似最优这样一类问题，解决这类问题的方法称为（最）优化方法（optimization method）25。优化方法大体可分为3类：第一类是直接利用实验方法（如科学研究中的实验、工程建设中的试点、社会实践中的政策试点）来寻找最优解。第二类是直接利用经验方法（如科技人员的思维、直觉、才能、经历、性格）来寻找最优解。第三类是利用数学方法（图解方法、解析方法和数值方法）来寻找最优解。由于水资源系统的复杂性，在水资源系统工程中常用的是数值优化方法（如运筹学方法），它是通过迭代程序产生问题的最优解。数值优化方法大致可归结为一类搜索方法，也就是构造序列xn，使26 (1.1)当f(x)是连续函数时，有 (1.2)对有约束问题，至少当n充分大时有 xn 在可行域D内。同样有 (1.3)构造序列 xn ，一般用迭代方法(iterative method)(逐步构造法)。其递推公式为 ， ( n=1，2，N) (1.4)式中，Pn为第n步的下降方向，an为第n步的步长。各种非线性优化的算法，大都起源于Pn或an的不同的构造方法。 与初始点有关的优化方法求得的解，常常是找出在初始点附近的一个极值点来，至于它是否为全局极值点，在多数情况下不得而知。在水资源系统工程实际问题中，则常希望找到在给定条件下的全局极值点。求全局极值的方法，本质上是一种试探性搜索方法。由于全局极值点x*在可行域D中的确切位置事先并不知道，是需通过构造序列xn来估计的。因此必然要求xn在D中分布均匀且有一定的密度。蒙特卡罗法（Monte-Carlo Method）在理论上是能满足这种要求的，优化问题的维数、几何形状、是否离散等对它影响也不大，但在实际中则常常失去使用价值。这是因为，在D中分布均匀的前提下，为了提高解的精度，势必在极值点附近加密投点的同时，也在整个可行域D中盲目地加密了投点，导致其运算量十分浩大，该算法的时间复杂性破坏了算法的能行性条件，因而是不合理的。合理的办法是，发展一些启发式策略或引入领域知识，对投点过程给予指导或引导，即：在可能出现全局极值点的地方增加投点密度，而对其它地方只作少量的试探性投点，特别是对已探明无全局极值点出现的区域不投点，从而可大大节省计算量，对该算法的时间复杂性进行了有效压缩，使该算法可行。上述常规的优化方法，可归纳为以下两大类： 确定性优化方法。例如，用得最广泛的梯度法，它通过沿目标函数的负梯度方向函数值下降来逐步寻找最小点。该方法虽然可靠性高，但要求目标函数的一阶或二阶导数存在，且和所选取的初始点关系很大，否则会容易陷入局部最优点。对于优化变量很多的实际问题，特别是当目标函数和约束条件具有复杂的非线性（多峰问题）时，梯度法将变得非常困难和不稳定，以至无效。另外，梯度法在处理离散或离散/连续混合问题时也是十分困难的。又例如，在实际工程计算中用得较多的复合形法（complex method），是单纯形法用于有约束优化问题的推广，它是用于不等式约束条件下直接搜索的一种确定性优化方法。在n维空间中，由不处于同一个超平面（超曲面）上的(n+1)个点构成的凸多面体是该空间中最简单的几何图形，称之为单纯形（simplex），而由k（k(n+1)）个顶点构成的图形称之为复合形（complex）。复合形法不必计算目标函数f(x)的梯度，它不是沿着某一方向进行搜索的，而是对n维空间内的k个顶点（它们构成一个复合形）上的函数值进行比较，丢掉其中最差点，通过反射、延伸、收缩、缩边等算子操作得到一个新点，从而构成一个新的复合形，如此反复迭代，逐步逼近最优点。复合形法程序简单，使用方便，但要求可行域是凸的，这样才能保证各顶点的“重心”也在可行域内部，这就大大限制了复合形法的应用范围。应用复合形法时需对每次求得的“重心点”检验是否满足约束条件，若不满足（可行域是非凸的）则可作某种摄动，使迭代得以继续。复合形法的收敛速度是慢的，特别是对维数较高或约束条件较多时更是如此。上述这些确定性优化方法属单路径寻优，对复杂的非线性优化问题其寻优效率是很低的。另一类确定性优化方法就是枚举法，它包括完全枚举法、隐式枚举法（分枝定界法）、动态规划法等，该类方法的主要缺点是存在“维数灾”问题，搜索效率不高。 随机性优化方法。 又称随机搜索法，它在问题解空间中随机选定一定数量的点，从中选优。设优化问题为 (1.5) （j=1，2，m）随机性优化方法的运行过程如下： 步骤1：令k=0，F=充分大的正数。步骤2：产生n个0，1上的均匀随机数r1，r2， ，rn。令 ，（i=1，2，n） (1.6) 步骤3：若gj (xi(k)0（j=1，2，m），转步骤4；否则令 k+1，转步骤2。 步骤4：计算f(xi(k)。若f(xi(k)F，则令F= f(xi(k)，x*= xi(k)，否则k=k+1，转步骤2。 步骤5：当k=M（给定的自然数）时结束算法的运行，此时，x*即为所求的解。 上述算法中，每一试验点需要求n个随机数。可见，随机性优化方法是通过随机变量的大量抽样，以得到目标函数f(x)的变化特性，然后逐渐得到近优点，这类方法只要求目标函数和约束条件是可计算的，寻优范围大，不会陷入局部最优点，但属“盲目”寻优，计算量很大，其搜索效率也是很低的。由此可见，传统的优化方法尚无法满足许多复杂水资源系统问题的要求。例如，关于水电站的优化运行和管理27，已有的优化方法基本上都出自于数学规划技术，主要有线性规划、动态规划和非线性规划。线性规划由于将非线性问题线性化，误差较大。非线性规划由于缺乏较成熟算法而很少被实际使用。动态规划及其扩展算法广泛用于水库或水电站群的优化调度问题，但随着状态数目的增加，它往往伴随着所谓“维数灾”问题，尤其是当它用于库群联合调度时，“维数灾”问题尤为突出，以至无法在微机上求解。为了克服“维数灾”困难，国内外学者已提出不少方法，比如增量动态规划方法、离散微分动态规划法、逐次逼近增量动态规划方法、逐步优化算法、分解协调技术等，这些扩展方法的共同特点是很难保证收敛到全局最优解。又例如，马斯京根模型参数最优估计问题，目前确定该模型参数x和k的最常用方法是试错法，它需要大量的试算、作图和主观判断，从中选取最优值，而且还受到研究者的经验和判别水准的制约，因此在多组x和k都可接受的情况下，主观判断不能正确地识别拟合最优的x和k。另外，估计x和k的最小二乘法，因为x和k交互作用，使正规方程变为非线性方程组，给参数的求解带来一定的困难。实际中经常遇到的优化问题使人们逐渐认识到，用某种优化方法寻求最优点不是唯一目的，更重要的目标往往是解的不断改进的过程，对于复杂的优化问题更是如此。 1962年美国Michigan大学John H. Holland教授发现28, 29，按照类似活的有机体的自然选择（selection）和杂交（crossover）的自然进化（natural evolution）方式，编制的计算机程序能够解决复杂的优化问题，这类新的优化方法就是遗传算法（genetic algorithm-GA）。本质上，生物进化过程就是生物群体在其生存环境约束下，通过各个体的竞争（competition）、自然选择、杂交、变异（mutation）等方式所进行的“物竟天演，适者生存，不适者淘汰”的一种自然优化过程。因此，生物进化的过程，实际上可以认为是某种优化问题的求解过程。GA正是模拟生物的这种自然选择和群体遗传机理的数值优化方法。具体说来30，31，GA把一族随机生成的可行解作为父代群体，把适应度函数（目标函数或它的一种变换形式）作为父代个体适应环境能力的度量，经选择、杂交生成子代个体，后者再经变异，优胜劣汰，如此反复进化迭代，使个体的适应能力不断提高，优秀个体不断向最优点逼近。 生物进化过程既十分丰富又极为复杂，有许多方面尚未被人类所认识，目前已被认识的生物进化过程中的一些基本特征是：生物个体的染色体（chromosomes）的结构特征，即基因码序列（series of genetic code）决定了该个体对其生存环境的适应能力。自然选择在生物群体（population）进化过程中起着主导作用，它决定了群体中那些适应能力（adaptability）强的个体能够生存下来并传宗接代，体现了“优胜劣汰”的进化规律。个体繁殖（杂交）是通过父代个体间交换基因材料来实现的，生成的子代个体的染色体特征可能与父代的相似，也可能与父代的有显著差异，从而有可能改变个体适应环境的能力。变异使子代个体的染色体有别于其父代个体的染色体，从而也改变了子代个体对其环境的适应能力。生物的进化过程，从微观上看是生物个体的染色体特征不断改善的过程，从宏观上看则是生物个体的适应能力不断提高的过程。 GA就是用下列计算机技术来模拟上述生物进化特征，并逐渐发展成为一类新的优化方法24，28，32-34： 不失一般性，设优化问题为函数极小化问题：min f：RnR，f为目标函数，R为实数集，n为优化变量数目；适应度函数为F：IR，其中I是个体的空间，I=ai|i=1，2，n；ai为个体；x=x1，x2， xn 为Rn上的目标变量集，ui，vi为分量xi的范围；np为父代群体规模，nc为子代群体规模，即在每一代通过杂交、变异产生的个体数目；在第t次进化迭代时，群体为P(t)=a1(t)，a2(t)，anp(t)；C：InpInc 为杂交算子，其控制参数为杂交概率pc；M：IncInc 为变异算子，其控制参数为变异概率pm；S：(IncInp)Inp为选择算子，其控制参数为选择概率ps。这里C，M，S 均为宏算子，即把群体变换为群体，把相应作用在个体上的算子分别记为c，m，s。GA的算法如下： 步骤1：用二进制位串（string）来模拟染色体，用数字串中的某位元模拟基因（gene），用数量极大的数字串表示优化问题可行域内的试探解。这种将优化问题的解表示为数字串的过程称为编码（encoding）。每个串代表一个个体（individual），许多个体的集合称为群体（population）。GA作用于确定长度e的二进制位串上，即I=0，1e。用一段位串(ai1， ai2，aie )通过如下位段解码函数来表示优化变量的第i个分量：xi=i(ai1，ai2，aie )，(i=1，2，n) (1.7)式中，(ai1， ai2，aie )为个体a =(a11，a1e，a21，ane )I e的第i段位串。 遗传算法的操作对象是数字串，而不是优化问题的解形式，这为遗传算法成为一种通用的优化方法奠定了基础。若把所有可行解所对应的二进制串比作某一地区，则那些编码不良答案的串就是该地区的峡谷，而那些编码优良答案的串就对应山峰28。在该地区搜索寻优的常用方法是登山，即从某点开始，若一个小变动能改善解的质量，则沿该方向继续前进，否则取其它方向搜索。但是，复杂问题会使该地区山峰林立，随着解空间维数的增加，该地区的拓扑结构也趋复杂化，此时寻找正确的山峰、甚至判断哪条路径是向上的都会变得越来越困难。另外，这样的搜索空间极大。例如，有一种棋，每步平均有10种走法，每盘棋每方一般走30步，则这种棋共有1060种走法，但是其中大多数走法的效果并不好。 步骤2：用目标函数或其变换作为适应度函数（fitness function）来模拟个体对生存环境的适应性。把上述n个位段解码函数组合成一个个体的解码函数，即=12 n，则个体a的适应度函数可设置为F(a)=g(f (a)，其中g为对目标函数进行变换的函数，其作用是确保适应度值为非负并且好的个体的适应度值也大，常见的g有线性比例函数、幂比例函数和指数比例函数等34。适应度函数用来计算群体中的每个串的适应度值，适应度函数值越大的个体被选择的概率越大，而被淘汰的概率越小，反之亦然。个体ai被选中的概率为 (1.8)并按照上式概率分布选取np个个体作为当代父代群体。GA象一张网，罩在优化问题可行域上。数量极大的位元串组成了一个不断进化的群体，这些串同时在这一地区的很多区域中进行采样，且不同区域中的采样频率正比于该区域的平均适应度值28。 步骤3：父代个体的杂交。设杂交概率为pc，则当代父代群体中有nppc个个体进行杂交。把两个父代数字串配对排列，沿串的长度方向随机选取一点，交换两串的左边部分，产生两个子代个体。其中一个子代个体含第一个串在交换点以左的符号和第二个串在交换点以右的符号，另一个子代个体含第二个串在交换点以左的符号和第一个串在交换点以右的符号。设两父代个体a1=(a111，a112，a1ne )和a2=(a211，a212，a2ne)随机地从群体中配对、杂交，产生两个子代个体 b1=(a111，a112，a1ih，|a2ih+1，a2ih +2，a2ne) (1.9) b2=(a211，a212，a2ih，|a1ih+1，a1ih +2，a1ne) (1.10)式中，杂交点为随机选取。这种杂交算子称为单点杂交算子，参见图1.1。由此扩展，m点杂交算子就是随机选取m个杂交点，并交替地互换配对双亲各杂交点之间的位段而生成两个子代个体。目前尚无明确的理论和可靠的试验证据来判定何种杂交算子是最适宜的，尽管已有一些试图解决此问题的研究成果。 (父代个体1) 10100 (子代个体1)1 0 0 1 1 (父代个体2) 11011 (子代个体2) 1 1 1 0 0 图1.1 单点杂交算子 遗传算法的杂交算子实际上完全模仿了生物模型。所产生的子代个体并不取代适应度值高的父代串，而是取代两个适应度值低的串。每产生新的一代，都将淘汰适应度值低的串，以使整个群体的规模（大小）保持不变。 步骤4：子代数字串变异。在GA中变异算子是一种辅助算子，它作用在子代个体位串上，以小概率pm随机地改变串上的每一位（即相应位上的0变为1，或是1变为0），pm一般取0.001到0.01之间32。变异不依赖于优化变量的维数和位串的总长。设子代个体为ai=(ai11，ai12，aine )，经变异算子m(ai)作用后变为ami=(am11，am12，amne )： (1.11)式中，ujk为0，1上的均匀随机数，参见图1.2。从优化的角度看，单靠变异一般不能在求解的过程中取得显著进展，但是变异能够确保不产生不能继续进化的单一群体。杂交与变异增加了产生新的数字串的可能性，从而使遗传算法有能力搜索那些未被采样的区域。 0 1 1 0 1 1 0 0 图1.2 两点变异算子步骤5：进化迭代。转步骤2，如此反复运行，直至获得满意的解或达到预定进化迭代次数，结束算法的运行，并把适应度值最高的数字串所表示的解作为解优化问题的结果。随着一代代的选择、杂交和变异，GA能在解空间中发掘出期望值高的区域，在这些区域中串的数目在不断增加。表1.1为生物进化过程与GA的对照表24。 表1.1 生物进化过程与遗传算法的对照表24生物进化遗传算法基因(gene)基因值(等位基因)(allele)基因位置(基因座)(locus)基因组(genome)染色体(chromosome)基因总集(基因型)(genotype)表现型(phenotype)个体适应能力(adaptability)选择(selection)杂交(crossover)变异(mutation)生物个体的进化过程(process of evolution)字符(character)字符值(character value)数串位置(string position)模式(schema)数串(string)数串空间(string space)解空间(solution space)适应度函数(fitness function)选择算子(selection operator)杂交算子(crossover operator)变异算子(mutation operator)问题解的优化过程(process of optimization) 可见，遗传算法就是在“优胜劣汰”指导下的一类随机并行自适应优化方法，所编的码串相当于某群体的个体，目标函数及解变量的约束条件相当于个体所处的环境，GA的运行过程就是基于个体与环境的作用进行的24。遗传算法可视为介于确定性优化方法与随机性优化方法之间的一类新的优化方法。其确定性成份表现在，每次选择操作时应用了“优胜劣汰”这一生物进化法则，也即，那些适应度值越高的个体越有可能“遗传”到下一轮进化迭代过程；其随机性成份则表现在选择、杂交、变异操作时都具有一定的随机性，这正如生物进化过程中的基因遗传、变异和突变也具有随机性一样。虽然遗传算法本身也是一类随机优化方法，但它与传统的基于梯度的确定性优化方法相比较，克服了因线性化引起的不稳定性以及依赖于初始点选择而易限于局部极小点等缺点，并且它本身是一类全局寻优方法，不需计算目标函数的偏导数。它与传统的随机优化方法相比较，由于GA的每步搜索都要充分利用已有寻优信息来指导解空间的搜索，它把搜索到的优秀点的信息遗传到下一代，而把劣点予以淘汰，因而它是一类自适应优化方法；而传统的蒙特卡罗方法，搜索完一个点后，不管该点好坏，都不保留任何关于该点的信息，因而降低了搜索效率。此外，GA在运行过程中保持多个当前解，这样不仅使近似解的优化程度有所提高，同时也使得并行计算易行，且可获得近似线性加速的效果。遗传算法与常规优化方法关于寻优稳健性（robustness）的比较参见图1.3。GA就是一类理想的稳健优化方法。归纳起来，与常规的优化方法相比，遗传算法具有如下显著特点24，33-37：适应性强：GA只要求优化问题是可计算的，对搜索空间没有任何特殊要求，可以是离散的、非线性的、多峰值的或高维的、带噪声的。在算法运行中只利用了目标函数值信息，没有利用导数等其它的辅助信息。GA与所求解问题的性质无关。全局优化：GA是多点、多路经搜索寻优，且各路径之间有信息交换，而不是单点、单路径“登山”。它同时从一代个体点群开始并行攀登多峰，并通过杂交算子在各个可行解之间交换信息，这使得它可以有效地在整个解空间寻优，能以很大的概率找到全局最优解或准全局最优 寻 图例 优 遗传算法 效 梯度法 果 枚举法或随机性方法 0 组合问题 单峰问题 多峰问题图1.3 各类优化方法的寻优效果的比较示意图解，即使在所定义的适应度函数是不连续的、非规则的或有噪声的情况下。因此，GA是一类稳健的全局优化方法。编码特征：GA通过编码将优化变量转换成与遗传基因类似的数字编码串结构，遗传信息贮存在其中，可进行各种遗传操作，相应地有解码过程。GA的操作对象就是这些数字编码串，而不是解变量本身，而且编码技术在GA中一般是固定的（常为二进制编码）。基于编码机制的GA用简单的杂交算子、变异算子等模拟了人类探索和发明创造等思维过程中存在的信息交换、渗透和激励机制，从而可以方便地处理离散性问题和连续性问题。概率搜索：GA在选择操作时，用概率规则而不是确定性规则来引导搜索过程向适应度函数值逐步改善的搜索区域方向发展，这就克服了传统的随机性优化方法的盲目性，只需较少的计算量就能找到问题的全局近优解；在杂交、变异操作过程中也是采用随机方式进行的。由于GA使用概率规则指导搜索，因此能搜索离散的、有噪声的或多峰的复杂空间。隐含并行性（implicit parallelism）：GA通过控制群体中n个串，实际上能反映o(n3)阶个模式（schema)，这种性能使GA能利用较少的数字串来搜索可行域中的大量区域，从而只化较少的代价就能找到问题的全局近似解34。GA这种隐含并行性是它优于其它优化算法最主要的因素，因此它特别适合于处理复杂的非线性优化问题。自适应性：GA具有潜在的学习能力，能把注意力集中于解空间中适应度函数期望值最高的部分，发掘出目标区域，因此它适用于具有自适应与学习能力的系统。应用的广泛性：GA兼有确定性优化方法与随机性优化方法的长处，只要求目标函数和约束条件具有可计算性，不要求梯度存在，因此，它的适用范围很广。与常规的非线性优化方法相比，GA利用选择、杂交、变异操作有可能在更加广阔的范围内寻找问题的潜在解，因此GA适于处理