本書就是一部由國外原版引進的關於算法的數學專著。遺傳算法(GA)是一種啟發式算法,它通過使用由自然進化啟發而來的技術手段(例如交叉、突變和選擇),生成針對優化問題的解決方案。這些解決方案已經成功地被用於數學和工程學的不同領域的連續優化問題中,在本書中,我們選擇了一些圖論中的NP一接近問題,例如優選權重獨立集問題、優選權重控制集問題、p一中心問題等,這些問題都可以使用遺傳算法來解決,帶有捲曲邊權的網路上的最短路徑問題和PERT可以用多項式求解,我們已經證明,邊權不準確的網路上的這些問題的時間複雜度是指數級的,本書還給出了解決這些問題的遺傳算法。
1 Introduction
1.1 Graph Algorithms
1.2 Computational Complexities of Algorithms
1.3 Graph Theoretic Definitions and Notations
1.4 Genetic Algorithms
1.4.1 Components of a GA
1.4.2 General structure of a GA
1.5 Theoretical Foundation of GAs
1.5.1 Schemata and building blocks
1.5.2 GAs and traditional search methods
1.6 Arithmetic of Imprecise Numbers
1.6.1 Interval number and interval arithmetic
1.6.2 Triangular fuzzy number and its arithmetic...
2 Maximum Weight Independent Set of a Graph
2.1 Introduction
2.2 0-1 Integer Programming Formulation
2.3 The GA for the MWIS Problem
2.3.1 Genetic representation
2.3.2 Fitness function
2.3.3 Population initialization
2.3.4 Selection
2.3.5 Crossover
2.3.6 Mutation
2.4 Computational Results
2.5 A summary
3 Minimum Weight Dominating Set of a Graph
3.1 Introduction
3.2 0-1 Integer Programming Formulation
3.3 The GA for the MWDS Problem
3.3.1 Genetic representation
3.3.2 Fitness function
3.3.3 Population initialization
3.3.4 Selection
3.3.5 Crossover
3.3.6 Mutation
3.4 The Proposed GA and its Efficiency
3.5 Computational Results
3.6 A Summary
4 p-center and p-radius of a Graph in Crisp and Fuzzy Environments
4.1 Introduction
4.2 Genetic Representations and Operators
4.2.1 Representations
4.2.2 Initialization
4.2.3 Fitness function
4.2.4 Selection
4.2.5 Crossover
4.2.6 Mutation
4.3 Computational Result
4.4 Fuzzy Network and Different Location Models
4.5 Comparison of Imprecise Numbers