分波多工網路（wavelength division multiplexing networks, WDM networks）中，任意網路節點或線路的破壞，都可能造成整個網路傳輸的困難。為了能維持網路的正常運作，找到最佳的修復路徑，以解決節點或線路破壞而產生的問題更顯重要。因此，分波多工網路之修復成為一個很重要的課題。而預設路徑式修復為用來保護或修復網路最常見的方法之一。
在本篇論文中，我們提出利用基因演算法（Genetic algorithms）搜尋最佳備用路徑。我們也比較了基因演算法四種不同的交配方式 (SPC, TPC, FPC, EPC) 以及四種不同的突變方式 (SPM, TPM, FPM, EPM)。模擬的結果顯示交配機率、突變機率的設定是非常的重要，適當的參數設定將可獲得更好的結果。我們同時提出了改良式的基因演算法（Modified Genetic algorithms）來解決基因演算法收斂的問題。在改良式的基因演算法中，我們利用最大向下搜尋法則（most-decent search）來產生原始族群，如此可以有效的避免收斂的問題。

Any failure of optical node or link in a Wavelength Division Multiplexing (WDM) network may cause it difficultly to transmit data. For maintaining the normal operation of the network, it is important to find the optimal backup restoration path that can solve the problems of the optical node or link failure. Therefore, restoration of WDM network becomes an essential work. The preplanned restoration is one of the common methods we considered to protect or restore the network failures.
In this paper, a genetic algorithm is proposed to finding optimal backup lightpath. Simulation results indicate that GA is robust for this problem. Four types of crossover operators (SPC, TPC, FPC, EPC) and four types of mutation operators (SPM, TPM, FPM, EPM) are employed in our genetic algorithm. We also show that parameter setting of Pc and Pm are very important. It will have better performance by suitable parameter setting. We proposed MGA to solve the convergence problem. In MGA, we generate initial populations of GA using most-decent search algorithm. It may have higher probability to avoid convergence.

REFERENCES

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

[2] I. Chlamtac, A. Ganz, and G. Karmi, “Lightpath communications: An approach to high bandwidth opticalWANs,” IEEE Trans. Commun., vol. 40, pp. 1171–1182, July 1992.

[3] R. Ramaswami and K. N. Sivarajan, “Routing and wavelength assignment in all-optical networks,” IEEE/ACM Trans. Networking, vol. 3, pp. 489-500, Oct. 1995.

[4] D. Banerjee and B. Mukherjee, “A practical approach for routing and wavelength assignment in large wavelength-routed optical networks,” Selected Areas in Communications, IEEE Journal on, vol. 14, pp. 903-908, June 1996.

[5] A. Mokhtar and M. Azizoglu, “Adaptive wavelength routing in all-optical networks,” IEEE/ACM Trans. Networking, vol. 6, pp. 197–206, Apr. 1998.

[6] S. Subramaniam, M. Azizoglu, and A. K. Somani, “All-optical networks with sparsewavelength conversion,” IEEE/ACMTrans. Networking, vol. 4, pp. 544–557, Aug. 1996.

[7] H. Harai, M. Murata, and H. Miyahara, “Performance of alternate routing methods in all-optical switching networks,” in Proc. IEEE INFOCOM, vol. 2, 1997, pp. 516–524.

[8] B. T. Doshi, S. Dravida, P. Harshavardhana, O. Hauser, and Y. Wang, “Optical network design and restoration,” Bell Labs. Tech. J., pp. 58–84, Jan.–Mar. 1999.

[9] E. Karasan and E. Ayanoglu, “Performance of WDM transport networks,” IEEE J. Select. Areas Commun., vol. 16, pp. 1081–1096, Sept. 1998.

[10] J. Anderson, J. S. Manchester, A. Rodriguez-Moral, and M. Veeraraghavan, “Protocols and architectures for IP optical networking,” Bell Labs Tech. J., pp. 105–124, Jan.–Mar. 1999.

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

[12] 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.

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

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

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

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

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

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

[19] B. Ramamurthy and B. Mukherjee, “Wavelength conversion in DWDM networking,” Selected Areas in Communications, IEEE Journal on, vol. 16, pp. 1061-1073, Sept. 1998.

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

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

[22] ITU-T Rec. G.872, “Architecture of Optical Transport Networks,” Feb. 1999.

[23] N. Nagatsu, S. Okamoto, and K. Sata, “Optical Path Cross-Connect System Scale Evaluation Ssing Path Accommodation Design for Restricted Wavelength Multiplexing,” IEEE JSAC, vol. 14, no. 5, June 1996, pp. 893-902.

[24] M. Alanyali and E. Ayanoglu, “Provisioning Algorithms for WDM Optical Networks,” IEEE/ACM Trans. Net., vol. 7, no. 5, Oct. 1999, pp. 767-78.

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

[26] 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.