運用分波多工（Wavelength-Division Multiplexing, WDM）技術的全光纖網路（All-Optical Network），為廣域網路（Wide Area Network, WANs）應用中最被看好的網路技術之一。分波多工網路中，任意網路節點或線路的破壞，都可能造成整個網路傳輸的困難。為了能維持網路的正常運作，找到最佳的備份群播樹，以解決節點或線路破壞而產生的問題更顯重要。因此，分波多工網路之修復成為一個很重要的課題。而預設式修復為用來保護或修復高速網路最常見的方法之一。基於網路存活性的需要, 本篇論文探討分波多工網路中，預設式備份群播樹修復之機制，並針對此問題提出一些有效的解決方法。
為了有更好的修復成果，我們先利用基因演算法(Genetic Algorithm，GA)－一種基於自然選擇過程的一種最佳化搜尋機制，來追求效能的最佳化。基因演算法已經被廣泛應用於解決複雜的最佳化問題。然而，傳統的基因演算法並非毫無缺點；收斂速度慢及不能保證一定可以收斂到最佳解為基因演算法二項主要缺點，現今已有許多改良式基因演算法來加強執行的效能。
同時考慮母體的多樣性(diversity)及演化時間(evolution time)二者間的關係，我們提出可調式突變機率之壓縮映射基因演算法（Contract Mapping Genetic Algorithm with Varying Mutation Probability, CMGAVaPm ）來搜尋最佳備用群播樹。模擬的結果顯示，該演算法不但具有較強的廣域搜索能力，而且能有效避免早熟(premature convergence)的問題。

Optical networks employing wavelength division multiplexing are potential candidates for future wide area networks. Because these networks are prone to component failures and carry a large volume of traffic, maintaining a high level of service availability is an important issue. It is important to find the optimal backup multicast backup tree that can ensure fiber network survivability for maintaining the normal operation of the network.
The preplanned restoration is one of the common methods we considered to protect or restore the network failures. We have presented a new method based upon a GA to find the near optimal preplanned backup multicast trees for the primary multicast trees in WDM network. In this thesis, GA has been employed for solving many complex optimization problems. Although GA is not perfect, i.e., the speed of convergence is slow and it cannot guarantee to converge to globally optimal solution, they are more efficient in attaining near-optimal solutions significantly than conventional point-by-point exhaustive search techniques, especially in large solution spaces.
Taking the relation between diversity of evolution population and evolution times into account, a Contract Mapping Genetic Algorithm with Varying Mutation Probability (CMGAVaPm) is proposed. Not only can the algorithm converge to globally optimal solution, but also it solve premature convergence problem efficiently. Simulation results show that the algorithm CMGAVaPm presented in this thesis performs better contrast with simple genetic algorithm and former contract mapping genetic algorithm.

[1] R. Ramaswami and K. N. Sivarajan, Optical Networks-A Practical Perspective. San Francisco: Morgan Kaufmann, 1998.

[2] G. Keiser, Optical fiber communication. New York: McGraw-Hill, 2000.

[3] B. Mukherjee, “DWDM optical communication networks: progress and challenges,” Selected Areas in Communications, IEEE Journal on, vol. 18, pp. 1810-1824, Oct. 2000.

[4] L. H. Sahasrabuddle and B. Mukherjee, “ Light-Trees: Optical Multicasting for improved performance in Wavelength-Routed Networks,” IEEE Communications
Magazine, Vol. 37, No. 2, pages 67-73, Feb. 1999.

[5] R. Malli, X. Zhang and C. Qiao, “Benefits of Multicasting in All-optical Networks,” Proc. of SPIE, All optical Networking, Vol. 3531, pp. 209-220, Nov. 1998.

[6] B. Mukherjee, Optical Communication Networks. New York: McGraw-Hill, July 1997.

[7] C. A. Brackett et al., “A scalable multiwavelength multihop optical network: A proposal for research on all-optical networks,” J. Lightwave Technol., vol. 11, pp. 736–753, May/June 1993.

[8], G. Mohan, C. S. R. Murthy, and A. K. Somani, “Efficient algorithms for routing dependable connections in DWDM optical networks Networking,” IEEE/ACM Transactions on, Vol. 9, pp.553-566, Oct. 2001.

[9] J. Holland, “Adaptation in Natural and Artificial Systems,” Univ. of Michigan Press (Ann Arbor), 1975.

[10] D. E. Goldberg, “Genetic algorithms in Search, Optimization and Machine learning,” Reading. MA: Addison Wesley, 1989.

[11] M. Mitchell, “An introduction to genetic algorithms,” London, England, 1996.

[12] S. Ramamurthy and B. Mukherjee, “Survivable WDM mesh networks, Part I—Protection,” in Proc. IEEE INFOCOM, 1999, pp. 744–751.

[13] G. Mohan and A. K. Somani, “Routing Dependable Connections With Specified Failure Restoration Guarantees in WDM Networks,” Proc. IEEE INFOCOM 2000, Mar. 2000.

[14] G. Mohan, C. S. R. Murthy, “Routing and wavelength assignment for establishing dependable connections in WDM networks,” Fault-Tolerant Computing, 1999. Digest of Papers. Twenty-Ninth Annual International Symposium on, pp. 94 -101, 1999.

[15] G. Mohan, C. S. R. Murthy, “Lightpath restoration in DWDM optical networks,” IEEE Network, vol. 14, pp.24-32, Nov.-Dec. 2000.

[16] R. Kawamura, I. Tokizawa, “Self-Healing Virtual Path Architecture in ATM Networks”, IEEE Communications Magazine, pp.72-79, Sep. 1995

[17] B. T. Doshi et al., “Optical network Design and Restoration,” Bell Labs Tech. J., Jan.-Mar. 1999, pp. 58-84.

[18] Cheng-Shong Wu and Shi-Wei Lee, “Study of working and backup path routing policies in self-healing ATM networks,” ISCOM’95

[19] R. Kawamura, K. Sato. and I. Tokizawa, “Self-healing ATM networks based on virtual path concept,” IEEE JSAC, vol. 1, no. 1, pp. 120-127, June 1996.

[20] Cheng-Shong Wu and Shi-Wei Lee, Young-tseng Hou, and Yuan-Sun Chu,“A new preplanned self-healing scheme for multicast ATM networks,” Communication Technology Proceedings, vol. 2, no. 5-7, May 1996

[21] B. M. Waxman, “Routing of multipoint connections,” IEEE JSAC, vol. 6, no. 9, pp. 1617-1622, Dec. 1988.

[22] J. K. Shapiro, D. Towsley, and J. Kurose,” Optimization-based congestion control for multicast communications,” IEEE Communications Magazine, vol. 40 Issue: 9, 2002.

[23] E. N. Gilbert and H. O. Pollak, “Steiner minimal trees,” SIAM J. Appl. Math., vol. 16, no. 1, pp. 1-29, 1968.

[24] H. S. M. Coxeter, Introduction to Geometry. New York: Wiley, 1961.

[25] R. E. Miller and J. W. Thatcher, “Reducibility among combinatorial problems,” in Complexity of Computer Computations, R. M. Karp, Ed. New York: Plenum, pp.85-103, 1972.

[26] K. Bharath-Kumar and J. M. Jaffe, “Routing to multiple destinations in computer networks,” IEEE Trans. Commun., vol. COM-31,no. 3, pp. 343-351, Mar. 1983.

[27] A. Szalas and Z. Michalewicz, Contract mapping genetic algorithm and their convergence, Dept. of computer science, University of North Carolina at Charlotte, Technical Report 006-1993.

[28] Z. Michalewicz, Genetic Algorithm + data structure=Evolution Programs. Springer-Verlag, 1994.

[29] S. Banach, Sur les operations dans les ensembles abstraits et leur applications aux equations integrals, Fundamenta Mathematica, vol. 3, pp.133-181, 1922.

[30] Dunwei Gong and Xiaoyan Sun, “A modified contract mapping genetic algorithm,” ISIE 2002, vol. 1, pp. 353-356, 2002.

[31] M. Srinivas and L. M. Patnaik, ”Adaptive probabilities of crossover and mutation in genetic algorithms,” IEEE transactions on systems, Man and Cybernetics, vol. 24, no. 4, Apr. 1994.

[32] K. Murakami and H. S. Kim, “Near-optimal virtual path routing for survivable ATM networks,” INFOCOM '94. Networking for Global Communications. 13th Proceedings IEEE, vol.1, pp. 208 –215, Jun. 1994.