真實世界中，許多系統，如製造系統、電力系統、電腦系統與運籌系統等，可藉由模擬成由邊(arc)及節點(node)所組成的網路，以分析該系統之績效。其中網路可靠度為許多系統之重要績效指標之一並且可定義為資料可以成功地藉由此網路自發送端傳送至接受端之機率。因此，網路可靠度最佳化為對許多系統管理者所欲達成之目標。近年來如何自現有之資源中，配置一組資源於網路之邊或節點上，使得網路可靠度最佳，為網路可靠度最佳化重要議題之一，其中每一資源具有多種狀態，故網路在任一組資源配置下可視為隨機流量網路(Stochastic-flow Network)。例如以電腦網路而言，每一條傳輸皆由多條實體線路所組成，且因每一條實體線路有提供一負載量及故障之狀態，故此電腦網路之傳輸線具有多種狀態。因此，在任一組傳輸線配置下，電腦網路可視為一隨機流量網路。
近年來的文獻僅有應用基因演算法(Genetic Algorithm)以解決上述網路可靠度之最佳化資源配置問題。因此，本研究提出一混合蟻群與禁忌搜尋為基礎之 (Ant-Tabu algorithm)演算法，同時也針對數個柔性計算包括粒子群最佳化演算法(Particle Swarm Optimization)、蟻群最佳化演算法(Ant Colony Optimization)、禁忌搜尋演算法(Tabu Search)、模擬退火演算法(Simulated Annealing)加以比較，藉以找出解決上述問題之最適方法。所有柔性計算主要用於尋找最佳資源配置，並結合最小路徑(Minimal Paths)與遞回不交和法(Recursive Sum of Disjoint Product)演算法來計算網路可靠度。
本研究以電腦網路為例進行上述所提到6個柔性計算演算法求解效率的比較，並將各個演算法的終止條件設為一固定相同時間。透過10個實際電腦網路之實驗結果發現，在較小網路時，基因演算法所得到的網路可靠度優於其他演算法。但隨著網路的傳輸邊或最小路徑個數增加的情況下，本研究所提出之Ant-Tabu得到的網路可靠度優於其他演算法。

For many real world systems such as manufacturing systems, electric power systems, computer systems, logistics systems can be modeled as networks that composing of arcs and nodes, and analyze system performances. However, network reliability is defined as the probability that the network can transmit a given units of demand from a source node to a sink node. Therefore, network reliability optimization is the goal which most supervisors pursue. Recently, how to determine the best resource assignment from a set of resources to optimize network reliability is a crucial issue. Because each resource has multiple states, these networks should be regarded as stochastic-flow networks. Take computer network for example, each transmission line is combined with several physical lines. Each physical line may provide a capacity or may fail, and thus the transmission line would have several states. That is, a computer network should be regarded as a stochastic-flow network.
In the past decade, the researchers have only applied genetic algorithm to solve resource assignment of network reliability optimization problem. Therefore, this study focus on comparing genetic algorithm with several soft computing algorithms, including particle swarm optimization, ant colony optimization, tabu search, simulated annealing and the hybrid algorithm that combines ant colony system and tabu search. However, the main goal is to apply these soft computing algorithms to obtain the best resource assignment. In addition, we evaluate network reliability using the algorithm that combines MPs and RSDP algorithm.
Furthermore, terminal constraint is set as a period of time in our experiments because we attempt to know computational efficiency among six soft computing algorithms. Several experiments related to ten real computer networks are displayed to show the computational efficiency of both genetic algorithm and Ant-Tabu algorithm yield excellent network reliability as small scale networks. However, the proposed Ant-Tabu algorithm is more effective as the network with more the number of arcs and even more the number of MPs.

REFERENCES

Amiri, A. and Pirkul, H., “Routing and capacity assignment in backbone communication networks”, Computers and Operations Research, Vol. 24, pp. 275-287 (1997).
Aven, T., “Reliability evaluation of multistate systems with multistate components”, IEEE Transactions on Reliability, Vol. 34, pp. 473-479 (1985).
Aydin, M.E. and Fogarty, T.C., “A distributed evolutionary simulated annealing algorithm for combinatorial optimization problems”, Journal of Heuristics, Vol. 10, no. 3, pp. 269-292 (2004).
Ayob, M. and Jaradat, G., “Hybrid Ant Colony Systems for course timetabling problems”, 2009 2nd Conference on Data Mining and Optimization, DMO 2009, pp. 120-126 (2009).
Ball, M. O., “Computing network reliability”, Operation Research, Vol. 27, pp. 823-838 (1979).
Ball, M. O., Hagstrom, J., and Provan, J. S., “Threshold reliability of networks with small failure sets”, Networks, Vol. 25, pp. 101-115 (1995).
Bilgin, S. and Azizoǧlu, M., “Operation assignment and capacity allocation problem in automated manufacturing systems”, Computers and Industrial Engineering, Vol. 56, no. 2, pp. 662-676 (2009).
Bullnheimer, B., Hartl, R.F. and Strauss, C., “An improved Ant System algorithm for the Vehicle Routing Problem”, Annals of Operations Research, Vol. 89, pp. 319-328 (1999).
Candalino Jr., T.J., Kobza, J.E. and Jacobson, S.H., “Designing optimal aviation baggage screening strategies using simulated annealing”, Computers and Operations Research, Vol. 31, no. 10, pp. 1753-1767 (2004).
Chen, D. J., Hol, W. C., Chen, R. S., and Chen, D. T. K. “A heuristic algorithm for the reliability-oriented file assignment in a distributed computing system”, Computers and Mathematics with Applications, Vol. 29, pp. 85-104 (1995).
Cheng, S. T. “Topological optimization of a reliable communication network”, IEEE Transactions on Reliability, Vol. 47, pp. 225-233 (1998).
Cheng, H. and Yang, S., “Joint multicast routing and channel assignment in multiradio multichannel wireless mesh networks using tabu search”, 5th International Conference on Natural Computation, ICNC 2009, pp. 325-330 (2009).
Cheng, H. and Yang, S., “Joint QoS multicast routing and channel assignment in multiradio multichannel wireless mesh networks using intelligent computational methods”, Applied Soft Computing Journal, Vol. 11, no. 2, pp. 1953-1964 (2011).
Chwif, L., Pereira Barretto, M.R. and Moscato, L.A., “A solution to the facility layout problem using simulated annealing”, Computers in Industry, Vol. 36, no. 1-2, pp. 125-132 (1998).
Colbourn, C. J., The Combinatorics of Network Reliability, Oxford University, New York (1987).
Demirel, N.C. and Toksari, M.D., “Optimization of the quadratic assignment problem using an ant colony algorithm”, Applied Mathematics and Computation, Vol. 183, no. 1, pp. 427-435 (2006).
Dorigo, M., Maniezzo, V. and Colorni, A., “Ant system: Optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 26, no. 1, pp. 29-41 (1996).
Dorigo, M. and Gambardella, L.M., “Ant colony system: A cooperative learning approach to the traveling salesman problem”, IEEE Transactions on Evolutionary Computation, Vol. 1, no. 1, pp. 53-66 (1997).
Ford, L. R. and Fulkerson, D. R., Flows in networks, Princeton University, NJ (1962).
Framinan, J.M. and Schuster, C., “An enhanced timetabling procedure for the no-wait job shop problem: A complete local search approach”, Computers and Operations Research, Vol. 33, no. 5, pp. 1200-1213 (2006).
Gambardella, L.M. and Dorigo, M., “Solving symmetric and asymmetric TSPs by ant colonies”, Proceedings of the IEEE Conference on Evolutionary Computation, pp. 622-627 (1996).
Glover, F., “Future paths for integer programming and links to artificial intelligence”, Computers and Operations Research, Vol. 13, no. 5, pp. 533-549 (1986).
Holthatis, O. and Rajendran, C., “A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs”, Journal of the Operational Research Society, Vol. 56, no. 8, pp. 947-953 (2005).
Hsieh, C. C. and Chen, Y. T., “Reliable and economic resource allocation in an unreliable flow network”, Computer and Operations Research, Vol. 32, pp. 613-628 (2005a).
Hsieh, C. C. and Chen, Y. T., “Resource allocation decisions under various demands and cost requirements in an unreliable flow network”, Computer and Operations Research, Vol. 32, pp. 2771-2784 (2005b).
Hsieh, C. C. and Lin, M. H., “Reliability-oriented multi-resource allocation in a stochastic-flow network”, Reliability Engineering and System Safety, Vol. 81, pp. 155-161 (2003).
Hsieh, C. C. and Lin, M. H., “Simple algorithms for updating multi-resource allocations in an unreliable flow network”, Computers and Industrial Engineering, Vol. 50, pp. 120-129 (2006).
Hyppolite, J. M., Galinier, P. and Pierre, S., “A tabu search heuristic for the routing and wavelength assignment problem in multigranular optical networks”, Photonic Network Communications, Vol. 15, no. 2, pp. 123-130 (2008).
Jain, S. P. and Gopal, K., “A heuristic method of link reliability assignment for maximal reliability”, Microelectronics Reliability, Vol. 30, pp. 673-679 (1990).
Jane, C. C. and Laih, Y. W., “Algorithms to determine the threshold reliability of flow networks”, IIE Transactions, Vol. 36, pp. 469-479 (2004).
Jane, C. C. and Yuan, J., “A sum of disjoint products algorithm for reliability evaluation of flow networks”, European Journal of Operational Research, Vol. 131, pp. 664-675 (2001).
Jayaraman, V. and Ross, A., “A simulated annealing methodology to distribution network design and management”, European Journal of Operational Research, Vol. 144, no. 3, pp. 629-645 (2003).
Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P. and Werner, F., “A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria”, Computers and Operations Research, Vol. 36, no. 2, pp. 358-378 (2009).
Kashan, A.H. and Karimi, B., “A discrete particle swarm optimization algorithm for scheduling parallel machines”, Computers and Industrial Engineering, Vol. 56, no. 1, pp. 216-223 (2009).
Kennedy, J. and Eberhart, R., “Particle swarm optimization”, IEEE International Conference on Neural Networks - Conference Proceedings, pp. 1942 (1995).
Kim, K.H. and Moon, K.C., “Berth scheduling by simulated annealing”, Transportation Research Part B: Methodological, Vol. 37, no. 6, pp. 541-560 (2003).
Kirkpatrick, S., Gelatt Jr., C.D. and Vecchi, M.P., “Optimization by simulated annealing”, Science, Vol. 220, no. 4598, pp. 671-680 (1983).
Kumar, A., Pathak, R. M., and Gupta, Y. P., “Genetic-algorithm-based reliability optimization for computer network expansion”, IEEE Transactions on Reliability, Vol. 41, pp. 63-72 (1995a).
Kumar, A., Pathak, R. M., Gupta, Y. P., and Parsaei, H. R., “A genetic algorithm for distributed system topology design”, Computers and Industrial Engineering, Vol. 28, pp. 659-670 (1995b).
Kuo, S., Lu, S., and Yeh, F., “Determining terminal pair reliability based on edge expansion diagrams using OBDD”, IEEE Transactions on Reliability, Vol. 48, pp. 234-246 (1999).
Lee, D. H., Cao, Z. and Meng, Q., “Scheduling of two-transtainer systems for loading outbound containers in port container terminals with simulated annealing algorithm”, International Journal of Production Economics, Vol. 107, no. 1, pp. 115-124 (2007).
Levitin, G. and Lisnianski, A., “A new approach to solving problems of multi-state system reliability optimization”, Quality Reliability Engineering International, Vol. 17, pp. 93-104 (2001).
Lin, Y. K., “A simple algorithm for reliability evaluation of a stochastic-flow network with node failure”, Computer and Operations Research, Vol. 28, pp. 1277-1285 (2001a).
Lin, Y. K., “Study on the multicommodity reliability of a capacitated-flow network”, Computers and Mathematics with Applications, Vol. 42, pp. 255-264 (2001b).
Lin, Y. K., “Using minimal cuts to evaluate the system reliability of a stochastic-flow network with failures at nodes and arcs”, Reliability Engineering and System Safety, Vol. 75, pp. 41-46 (2002).
Lin, Y. K., “Reliability of a stochastic-flow network with unreliable branches and nodes under budget constraints”, IEEE Transactions on Reliability, Vol. 53, pp. 381-387 (2004).
Lin, Y. K., “Reliability evaluation for an information network with node failure under cost constraint”, IEEE Transactions on Systems, Man and Cybernetics – Part A: Systems and Humans, Vol. 37, pp. 180-188 (2007a).
Lin, Y. K., “On a multicommodity stochastic-flow network with unreliable nodes subject to budget constraint”, European Journal of Operational Research, Vol. 176, pp. 347-360 (2007b).
Lin, Y. K. and Yeh, C. T., “Optimal resource assignment to maximize multistate network reliability for a computer network”, Computers and Operations Research, Vol. 37, no. 12, pp. 2229-2238 (2010).
Lin, S. W., Chou, S. Y. and Chen, S. C., “Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date”, Journal of Heuristics, Vol. 13, no. 2, pp. 151-165 (2007).
Lin, S. W., Yu, V. F. and Chou, S. Y., “Solving the truck and trailer routing problem based on a simulated annealing heuristic”, Computers and Operations Research, Vol. 36, no. 5, pp. 1683-1692 (2009).
Lisnianski, A. and Levitin, G., Multi-state system reliability: assessment, optimization and application, Vol. 6, World Scientific, Singapore (2003).
Liu, Q., Zhang, H., Ma, X., and Zhao, Q., “Genetic algorithm-based study on flow allocation in a multi-commodity stochastic-flow network with unreliable nodes”, Proceedings of The 8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, Tsinan, pp. 576-581 (2007).
Liu, Q., Zhao, Q., and Zang, W., “Study on multi-objective optimization of flow allocation in a multi-commodity stochastic-flow network with unreliable nodes”, Journal of Applied Mathematics and Computing, Vol. 28, pp. 185-198 (2008).
Locatelli, M., “Convergence of a Simulated Annealing Algorithm for Continuous Global Optimization”, Journal of Global Optimization, Vol. 18, no. 3, pp. 219-234 (2000).
Lv, H. and Lu, C., “A discrete particle swarm optimization algorithm for assembly sequence planning”, Proceedings of 2009 8th International Conference on Reliability, Maintainability and Safety, ICRMS 2009, pp. 1119 (2009).
McKendall Jr., A.R., Shang, J. and Kuppusamy, S., “Simulated annealing heuristics for the dynamic facility layout problem”, Computers and Operations Research, Vol. 33, no. 8, pp. 2431-2444 (2006).
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H. and Teller, E., “Equation of state calculations by fast computing machines”, The Journal of chemical physics, Vol. 21, no. 6, pp. 1087-1092 (1953).
Misevicius, A., “A tabu search algorithm for the quadratic assignment problem”, Computational Optimization and Applications, Vol. 30, no. 1, pp. 95-111 (2005).
Montemanni, R., Moon, J.N.J. and Smith, D.H., “An improved tabu search algorithm for the fixed-spectrum frequency-assignment problem”, IEEE Transactions on Vehicular Technology, Vol. 52, no. 4, pp. 891-901 (2003).
Paik, C. H. and Soni, S., “A simulated annealing based solution approach for the two-layered location registration and paging areas partitioning problem in cellular mobile networks”, European Journal of Operational Research, Vol. 178, no. 2, pp. 579-594 (2007).
Painton, L. and Campbell, J., “Genetic algorithms in optimization of system reliability”, IEEE Transactions on Reliability, Vol. 44, pp. 172-178 (1995).
Pierre, S. and Legault, G., “A genetic algorithm for designing distributed computer network topologies”, IEEE Transactions on Systems, Man, and Cybernetics – Part B: Cybernetics, Vol. 28, pp. 249-258 (1998).
Provan, J. S. and Ball, M. O., “Computing network reliability in time polynomial in the number of cuts”, Operations Research, Vol. 32, pp. 516-526 (1984).
Ramirez-Marquez, J. E. and Rocco S., C. M., “Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery”, Reliability Engineering and System Safety, Vol. 94, pp. 913-921 (2009).
Ramirez-Marquez, J. E., Rocco S., C. M., and Levitin, G., “Optimal protection of general source-sink networks via evolutionary techniques”, Reliability Engineering and System Safety, Vol. 94, pp. 1676-1684 (2009).
Rameshkumar, K., Suresh, R.K. and Mohanasundaram, K.M., “Discrete particle swarm optimization (DPSO) algorithm for permutation flowshop scheduling to minimize makespan”, Lecture Notes in Computer Science, pp. 572 (2005).
Rueger, W. J., “Reliability analysis of networks with capacity constraints and failure at branches and nodes, IEEE Transactions on Reliability, Vol. 35, pp. 523-528 (1986).
Salcedo-Sanz, S., Santiago-Mozos, R. and Bousoño-Calzón, C., “A Hybrid Hopfield Network-Simulated Annealing Approach for Frequency Assignment in Satellite Communications Systems”, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 34, no. 2, pp. 1108-1116 (2004).
Shuang, B., Chen, J. and Li, Z., “Microrobot based micro-assembly sequence planning with hybrid ant colony algorithm”, International Journal of Advanced Manufacturing Technology, Vol. 38, no. 11-12, pp. 1227-1235 (2008).
Soh, S. and Rai, S., “An efficient cutset approach for evaluating communication-network reliability with heterogeneous link-capacities”, IEEE Transactions on Reliability, Vol. 54, pp. 133-144 (2005).
Spinellis, D.D. and Papadopoulos, C.T., “A simulated annealing approach for buffer allocation in reliable production lines”, Annals of Operations Research, Vol. 93, no. 1-4, pp. 373-384 (2000).
T'kindt, V., Monmarché, N., Tercinet, F. and Laügt, D., “An Ant Colony Optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem”, European Journal of Operational Research, Vol. 142, no. 2, pp. 250-257 (2002).
Van Breedam, A., “Improvement heuristics for the Vehicle Routing Problem based on simulated annealing”, European Journal of Operational Research, Vol. 86, no. 3, pp. 480-490 (1995).
Wang, X., Cao, J., Cheng, H. and Huang, M., “QoS multicast routing for multimedia group communications using intelligent computational methods”, Computer Communications, Vol. 29, no. 12, pp. 2217-2229 (2006).
Wang, S., Shi, R., Wang, L. and Ge, M., “Study on improved ant colony optimization for bin-packing problem”, 2010 International Conference on Computer Design and Applications, ICCDA 2010, pp. V4489-V4491 (2010).
Xia, M., “An ant colony algorithm hybridized with iterated local search for the QAP”, PACIIA 2009 - 2009 2nd Asia-Pacific Conference on Computational Intelligence and Industrial Applications, pp. 80-83 (2009).
Xin, B., Chen, J., Zhang, J., Dou, L. and Peng, Z., “Efficient decision makings for dynamic weapon-target assignment by virtual permutation and tabu search heuristics”, IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, Vol. 40, no. 6, pp. 649-662 (2010).
Xu, W., He, S., Song, R., and Li, J., “Reliability based assignment in stochastic-flow freight network”, Applied Mathematics and Computation, Vol. 211, pp. 85-94 (2009).
Xue, J., “On multistate system analysis”, IEEE Transactions on Reliability, Vol. 34, pp. 329-337 (1985).
Yang, Q., Zhang, C. and Wang, C., “An efficient discrete particle swarm algorithm for task assignment problems”, 2009 IEEE International Conference on Granular Computing, GRC 2009, pp. 686 (2009).
Ying, K. C. and Liao, C. J., “An ant colony system for permutation flow-shop sequencing”, Computers and Operations Research, Vol. 31, no. 5, pp. 791-801 (2004).
Yongling, F. and Wanqin, L., “Optimal task assignment for serial-parallel hybrid robots cooperation via ant colony optimization”, ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments, pp. 3795-3800 (2009).
Youssef, H., Al-Mulhem, A., Sait, S.M. and Tahir, M.A., “QoS-driven multicast tree generation using Tabu search”, Computer Communications, Vol. 25, no. 11-12, pp. 1140-1149 (2002).
Zhan, Z. H. and Zhang, J., “Discrete particle swarm optimization for multiple destination routing problems” (2009).
Zhang, Y. B., Zhao, Y. C. and Xiong, H., “A tabu search algorithm for frequency assignment problem in wireless communication networks”, Proceedings - 5th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2009 (2009).
Zuo, M. J., Tian, Z., and Huang, H. Z., “An efficient method for reliability evaluation of multistate networks given all minimal path vectors”, IIE Transactions, Vol. 39, pp. 811-817 (2007).