網路模型與多目標遺傳算法

《網路模型與多目標遺傳算法》是2017年清華大學出版社出版的書籍，作者是[日]玄光男、林林。

基本介紹

• 書名：網路模型與多目標遺傳算法
• 作者：[日]玄光男、林 林 著 梁承姬
• 譯者：於歆傑 譯
• ISBN：9787302456148
• 定價：49
• 出版社：清華大學出版社
• 出版時間：2017.03.01

內容簡介

本書首先圍繞物流配送計畫問題、網路的開放式最短路徑優先問題、多階段供應鏈管理的網路問題以及雙目標網路問題中的網路系統的最小費用最大流量問題這幾個可用網路模型一般化的NPhard組合最佳化問題，介紹如何設計不同的染色體來採用遺傳算法解決網路設計問題；然後，在數值實驗中通過求解實際問題詳細地介紹了遺傳算法的使用方法；最後，介紹怎樣有效地運用遺傳算法求解從基本的網路模型，到通信網路、邏輯系統、先進的生產計畫等不同的多目標網路模型。

本書通過使用具體數值實例進行淺顯易懂的講解，而沒有涉及難懂的理論講解，大學低年級學生憑藉其現有的數學基礎知識就可以完全理解書中介紹的網路數學模型和遺傳算法的解法。書中豐富的數值實例能夠加深讀者對算法的理解，為學習帶來便利。

前言

從網際網路時代的信息網路系統，到基於GPS進行車輛導航的道路信息系統，以及軟體開發的項目進度管理系統，均建立在網路模型的基礎之上。目前，網路建模已經被靈活地運用到計算機科學、自然科學、運籌學、金融學、工學等諸多領域。網路建模通過點、弧（連線）以及流量來處理網路問題並搜尋到最佳的解決方案。

近年來，由於信息通信技術的快速發展，網路技術的飛速進步和普及，以及產業經濟全球化，不僅僅是信息通信業，製造業以及物流業也發生著巨大的變革。最佳化問題的求解過程，如套用大規模網路系統的最最佳化通信路徑，及網路的開放式最短路徑優先（OpenShortestPathFirst，OSPF）問題，以附加快速信息互動能力的企業資源軟體包（EnterpriseResourcePackage，ERP）為基礎的生產信息系統的生產物流調度問題，伴隨網路環境下物流系統中顧客和供應商的全球化問題的多階段供應鏈管理(SupplyChainManagement，SCM)網路問題等，因其結構複雜、多伴有很多制約條件，且常為多目標最佳化問題，被我們定義為NP-hard組合最佳化問題。特別是針對各企業生產物流過程，要求迅速靈活運用準確的信息並給出合理決策，具體指從接受訂單到企劃，再到生產過程以及密切相關的適時配送計畫，即根據供應鏈管理系統尋求到全局最最佳化的解。

一般地，大規模組合最佳化問題用舊有方法求解時存在解決不了的問題，所以在啟發式算法里最被廣泛靈活套用的遺傳算法（GeneticAlgorithm，GA）受到了關注。遺傳算法是進化計算的一種，在業界作為實用技術之一被廣泛地使用。例如，在SAP、i2、IBM等世界各地的企業資源軟體包中，均標準化地配備了基於遺傳算法的最最佳化工具。近年來，遺傳算法被最廣泛地套用於求解難以用數學模型定義的問題或者結構複雜的最最佳化問題等。並且從SCI級別的國際刊物中基於遺傳算法的研究論文數量之多可以看出很多學者也對遺傳算法的能力表示肯定。

為了靈活運用進化計算之一的遺傳算法，本書主要圍繞物流配送計畫問題、網路的最短路徑優先問題、多階段供應鏈管理網路問題，以及雙目標網路問題中的網路系統的最小費用最大流量問題這幾個可用網路模型一般化的NPhard組合最佳化問題，介紹如何設計不同的染色體來採用遺傳算法解決網路設計問題，此外，在數值實驗中通過求解實際問題詳細地介紹了遺傳算法的使用方法。進一步地，怎樣有效地運用遺傳算法求解從基本的網路模型，到通信網路、邏輯系統、先進的生產計畫（AdvancedPlanningandScheduling,APS）等不同的多目標網路模型，將在後面的5章進行說明。

在第1章遺傳算法中，對背景和作為基礎的染色體的編碼、評價函式、遺傳操作等進行了說明，通過組合最佳化問題中的典型模型——配詞問題和背包問題來解釋套用基礎遺傳算法的計算過程，並介紹了模糊邏輯和遺傳算法組合的混合型遺傳算法。第2章網路模型基礎中，介紹了作為網路模型中最基本的最短路徑模型、最大流量模型、最小費用流模型和最小生成樹模型。第3章物流網路模型中介紹了物流模型、兩階段物流模型、車輛配送模型和工廠—配送中心物流模型。第4章多目標遺傳算法在簡要地說明了多目標最最佳化模型之後，對多目標遺傳算法概要、多目標遺傳算法過程、Pareto最優解的評價，以及多目標遺傳算法的數值計算實例進行了介紹。在第5章多目標網路模型中，介紹了作為該領域中最新的套用研究用例的最小費用最大流量網路、多目標供應鏈網路，生產物流系統的網路以及通信系統可靠性網路。

本書充分考慮到實用性，摒棄工具書中難懂的理論講解，通過使用具體數值實例進行淺顯易懂的講解，保證專科學校學生或者大學低年級學生憑藉現有的數學基礎知識也可以完全理解書中介紹的網路數學模型和遺傳算法的解法。書中豐富的數值實例能夠加深讀者對算法的理解，為學習帶來便利。

本書從1995年策劃開始，已經受到了很多國內外人士的指導和建議。特別是早稻田大學大學院岡本東博士（岩手縣立大學）、椋田實博士（日本工業大學）、訪問學者FulyaAltiparmak(GaziUniversity)，以及軟計算研究室的各位博士，特別要感謝剛田幾太郎氏、安高真一郎氏，也非常感謝共立出版社（株）的小山透氏、松永智仁氏、國井和郎氏在出版方面給予的幫助。

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參考文獻