本书实用性强，摒弃工具书中难懂的理论讲解，通过使用具体数值实例进行浅显易懂的讲解，保证大学低年级学生凭借现有的数学基础知识也可以完全理解书中介绍的网络数学模型和遗传算法的解法。书中丰富的数值实例能够加深读者对算法的理解，为学习带来便利。

前言

从因特网时代的信息网络系统，到基于GPS进行车辆导航的道路信息系统，以及软件开发的项目进度管理系统，均建立在网络模型的基础之上。目前，网络建模已经被灵活地运用到计算机科学、自然科学、运筹学、金融学、工学等诸多领域。网络建模通过点、弧（连接）以及流量来处理网络问题并搜索到最佳的解决方案。近年来，由于信息通信技术的快速发展，网络技术的飞速进步和普及， 以及产业经济全球化，不仅仅是信息通信业，制造业以及物流业也发生着巨大的变革。优化问题的求解过程，如应用大规模网络系统的最优化通信路径，及网络的开放式最短路径优先（Open Shortest Path First，OSPF）问题，以附加快速信息交互能力的企业资源软件包（Enterprise Resource Package，ERP）为基础的生产信息系统的生产物流调度问题，伴随网络环境下物流系统中顾客和供应商的全球化问题的多阶段供应链管理(Supply Chain Management，SCM)网络问题等，因其结构复杂、多伴有很多制约条件，且常为多目标优化问题，被我们定义为NP-hard组合优化问题。 特别是针对各企业生产物流过程，要求迅速灵活运用准确的信息并给出合理决策，具体指从接受订单到企划，再到生产过程以及密切相关的适时配送计划，即根据供应链管理系统寻求到全局最优化的解。一般地，大规模组合优化问题用旧有方法求解时存在解决不了的问题，所以在启发式算法里最被广泛灵活应用的遗传算法（Genetic Algorithm，GA）受到了关注。遗传算法是进化计算的一种，在业界作为实用技术之一被广泛地使用。例如，在SAP、i2、IBM等世界各地的企业资源软件包中， 均标准化地配备了基于遗传算法的最优化工具。近年来，遗传算法被最广泛地应用于求解难以用数学模型定义的问题或者结构复杂的最优化问题等。并且从SCI级别的国际刊物中基于遗传算法的研究论文数量之多可以看出很多学者也对遗传算法的能力表示肯定。为了灵活运用进化计算之一的遗传算法，本书主要围绕物流配送计划问题、网络的最短路径优先问题、多阶段供应链管理网络问题，以及双目标网络问题中的网络系统的最小费用最大流量问题这几个可用网络模型一般化的NPhard组合优化问题，介绍如何设计不同的染色体来采用遗传算法解决网络设计问题，此外，在数值实验中通过求解实际问题详细地介绍了遗传算法的使用方法。进一步地， 怎样有效地运用遗传算法求解从基本的网络模型，到通信网络、逻辑系统、先进的生产计划（Advanced Planning and Scheduling,APS）等不同的多目标网络模型，将在后面的5章进行说明。在第1章遗传算法中，对背景和作为基础的染色体的编码、评价函数、遗传操作等进行了说明，通过组合优化问题中的典型模型配词问题和背包问题来解释应用基础遗传算法的计算过程，并介绍了模糊逻辑和遗传算法组合的混合型遗传算法。第2章网络模型基础中，介绍了作为网络模型中最基本的最短路径模型、最大流量模型、最小费用流模型和最小生成树模型。第3章物流网络模型中介绍了物流模型、两阶段物流模型、车辆配送模型和工厂配送中心物流模型。第4章多目标遗传算法在简要地说明了多目标最优化模型之后，对多目标遗传算法概要、多目标遗传算法过程、Pareto最优解的评价，以及多目标遗传算法的数值计算实例进行了介绍。在第5章多目标网络模型中，介绍了作为该领域中最新的应用研究用例的最小费用最大流量网络、多目标供应链网络，生产物流系统的网络以及通信系统可靠性网络。本书充分考虑到实用性，摒弃工具书中难懂的理论讲解，通过使用具体数值实例进行浅显易懂的讲解，保证专科学校学生或者大学低年级学生凭借现有的数学基础知识也可以完全理解书中介绍的网络数学模型和遗传算法的解法。书中丰富的数值实例能够加深读者对算法的理解，为学习带来便利。本书从1995年策划开始，已经受到了很多国内外人士的指导和建议。特别是早稻田大学大学院冈本东博士（岩手县立大学）、椋田实博士（日本工业大学）、访问学者 Fulya Altiparmak (Gazi University)，以及软计算研究室的各位博士，特别要感谢刚田几太郎氏、安高真一郎氏，也非常感谢共立出版社（株）的小山透氏、松永智仁氏、国井和郎氏在出版方面给予的帮助。2008年2月玄光男林林

目录

第1章遗传算法

1.1遗传算法基础

1.1.1遗传算法概述

1.1.2编码

1.1.3适值函数

1.1.4遗传操作

1.1.5应用于非线性最优化问题

1.2遗传算法应用于组合优化问题的实例

1.2.1配词问题

1.2.2背包问题

1.3混合遗传算法

1.3.1lshGA

1.3.2flchGA

1.4参考文献

第2章网络模型基础

2.1最短路径模型

2.1.1最短路径问题数学模型

2.1.2基于优先级的遗传算法解法

2.1.3数值计算

2.2最大流量模型

2.2.1最大流量问题的数学模型

2.2.2基于优先级编码的遗传算法

2.2.3数值计算

2.3最小费用流模型

2.3.1最小费用流问题的数学模型

2.3.2基于优先级编码的遗传算法

2.3.3数值计算

2.4最小生成树模型

2.4.1最小生成树问题的数学模型

2.4.2基于PrimPred的遗传算法解法

2.4.3数值计算

2.5参考文献

第3章物流网络模型

3.1物流模型

3.1.1配送计划模型

3.1.2基于矩阵的遗传算法解法

3.1.3基于生成树的遗传算法解法

3.1.4数值计算

3.2两阶段物流模型

3.2.1两阶段物流模型

3.2.2基于优先级的遗传算法解法

3.2.3数值计算

3.3车辆配送模型

3.3.1多配送中心带时间窗的车辆配送模型

3.3.2基于遗传算法的解法

3.3.3数值计算

3.4工厂配送中心物流模型

3.4.1PDC物流网络数学模型

3.4.2基于优先级的遗传算法解法

3.4.3数值计算

3.5参考文献

第4章多目标遗传算法

4.1多目标优化模型概要

4.1.1多目标优化问题

4.1.2Pareto最优解

4.2多目标遗传算法概要

4.2.1多目标遗传算法的处理过程

4.2.2向量评价遗传算法

4.2.3评价值共享

4.3多目标遗传算法过程

4.3.1Pareto排序评价方法

4.3.2多目标函数加权和评价方法

4.3.3多目标函数的加权及保存精英策略的引入

4.4Pareto最优解的评价

4.4.1参照解集S*

4.4.2求得的Pareto最优解数量|Sj|

4.4.3获得Pareto最优解个体数比例RNDS(Sj)

4.4.4Pareto最优解集与参照解集间的距离D1R

4.4.5各目标函数轴的最大值, 最小值, 平均值IMMA

4.5多目标遗传算法的数值计算

4.5.1数值计算实例 1

4.5.2数值计算实例 2

4.6参考文献

第5章多目标网络模型

5.1最小费用最大流量网络模型

5.1.1最小费用最大流量网络的数学模型

5.1.2基于优先级的遗传算法解法

5.1.3数值计算

5.2多目标供应链网络模型

5.2.1多目标供应链网络数学模型

5.2.2基于优先级的遗传算法求解

5.2.3数值计算

5.3生产物流系统网络模型

5.3.1生产物流系统的数学模型

5.3.2基于随机值的多阶段决策遗传算法的解法

5.3.3数值计算

5.4通信系统可靠性网络

5.4.1系统瘫痪率和总成本最小化的数学模型建立

5.4.2基于混合多目标遗传算法的解法

5.4.3数值计算

5.5参考文献