随机型流量网络中若干问题的模型及其算法的研究
|
摘要
网络流理论是图论的一个重要分支,是研究网络上相关优化问题的理论和方法。1956年,L.R.福特和D.R.富尔克森等人给出了解决在给定的网络上寻求两点间最大运输量这类问题的算法,从而奠定了网络流理论的基础。网络流理论发展至今,已普遍应用于通讯、运输、电力、工程规划、任务分派等众多领域。为了更好的解决现实中的问题,网络流理论也在不断发展中,先后出现了具有增益的流、分派与匹配、网络优化的拉格朗日松弛法、多商品流、网络流的分解与合并等新的理论和方法。但以上研究都是在网络参数和拓扑结构固定的网络上进行的优化,而实际环境中的网络系统受多种因素影响往往会表现出随机性,所以传统网络流理论在具体应用时与实际情况会有一定的偏差,如果能在随机环境下对网络流进行优化,对提高网络流理论的实用性和针对性均有重要意义,这个问题已越来越引起关注。
目前主要从3个方面将随机因素引入网络流理论:1.令网络的权值为随机变量;2.假设网络的拓扑结构为随机的;3.假设网络中各边的容量为随机变量,提出了随机型流量网络(Stochastic Flow Network)的概念。随机型流量网络上的网络流理论的研究目前处于起步阶段,研究主要集中在:设计算法寻找网络流在网络容量状态X下的最大流V(X)能满足接收端需求d的网络容量状态的临界点d-MCs或d-MPs,并根据这些点计算随机型流量网络的可靠性。但当随机型流量网络的容量处于非临界状态时,对网络流进行分配优化的研究还较少见,论文中将针对不同问题选取特定优化目标,研究网络流不处于最大流状态V(X)时的优化问题。论文主要研究了以下几方面的内容:
1.以目前使用较多的两种随机型流量网络模型(网络节点可靠,单商品流,多发送端,多接收端的网络模型和网络节点不可靠,多商品流,多发送端,多接收端的网络模型)为基础,研究当网络流不处于最大流状态V(X)时如何对网络流流量进行分配优化。选定满足接收端需求的网络流可靠性为目标,建立整数随机规划模型。针对模型的特点,设计相应的算子,采用遗传算法对优化模型进行求解,并与使用Lingo软件方法求解得到的结果进行比较,分析两种求解方法的优缺点及其适用的问题。
2.文中将网络流传输时间和成本从约束条件转化为整体优化目标,并结合网络流可靠性这一主要目标,研究随机型流量网络上网络流的多目标优化问题。为求解建立的多目标优化模型,对NSGA-II方法做出如下改进:改进2-联赛选择算子的比较规则,将模拟2进制交叉算子改进为单点复合交叉算子,改进精英保留策略,使用改进后的算法对模型进行求解,经过测试,得到的结果从多方面优于原NSGA-II算法。
3.已有的随机型流量网络可靠性的算法,由于涉及到最大流最小割原理和Ford-Fulkerson算法等传统网络流理论,故不得不假设随机型流量网络中的所有变量为离散型变量。本文中由于采用了单目标/多目标遗传算法对网络流进行优化,故不受上面的限制。因此文中扩展随机型流量网络的容量为连续型随机变量,各条边上分配的网络流量为连续实数,建立连续型的多目标网络流优化模型,为了处理包含连续型变量的等式约束,对等式约束增加逼近参数,将等式约束分解为两条不等式约束以逼近方式处理。采用改进后的NSGA-II对处理后的优化模型进行求解。通过测试,可快速求出连续型多目标优化模型的Pareto前沿。
4.论文对网络中各节点包含随机需求的网络流多目标优化问题进行了研究。针对这种复杂随机情况下的网络流优化问题建立了机会约束多目标随机规划模型。对建立的随机规划模型进行预处理,将部分以置信度表示的约束条件转化为对应的确定性等价约束。采用随机模拟方法对优化模型的其余部分进行处理。结合前面提到的改进后的多目标遗传算法,提出一个基于随机模拟的多目标遗传算法对机会约束随机规划模型进行求解。通过算例测试,可以求得优化问题的Pareto解集。
Network flow theory is an important branch of Graph Theory, and it is the theory of studying optimization problems upon network. In 1956, L.R. Ford and D.R. Fulkerson propound the algorithm to solve the problem of seeking maximal transportation quantity between two nodes on the network. From then on, network flow theory was founded and developed. Network flow theory now has been widely applied to communication, transportation, power transmission, engineering programming and other fields. In order to solve the practical problem better, some new network flow theory were propounded, such as assignment and matching, LaGrange relaxation of network optimization, multi-commodity flow, network flow’s decomposition and combination and so on. But above research were all based on network whose parameters and topology structure were determinate. Network system in practical circumstance often presents randomicity because of influence of some factors. So it often causes some errors when apply traditional network flow theory to practical problems. It is significant for improving network flow theory’s practicability to optimize network flow in stochastic circumstance. This question has drawn attention.
Presently, stochastic factor has been introduced into network flow theory from three aspects: 1. suppose arcs’weights in network are stochastic variables; 2. suppose network’s topology structure is stochastic; 3. suppose arcs’capacities are stochastic variables, and propound the conception of stochastic flow network. Previous research on network flow theory upon stochastic flow network focused on designing algorithms to seek network’s critical capacity states (d-MCS or d-MPs) and computing network’s reliability according to these states. But when stochastic flow network’s capacity is not critical state, research on network flow optimization is few. So author selected different objectives according to different circumstance and studied optimization problems under the condition that network flow was not maximal flow V(X). The article mainly contains four contents as follows:
1. Basing two frequently used stochastic flow network models (network model with reliable nodes, single-commodity flow, multi-source nodes, multi-sink nodes and network model with unreliable nodes, multi-commodity flow, multi-source nodes, and multi-sink nodes), author studied how to optimize network flow when network flow was not maximal flow V(X).Author selected network flow’s reliability as objective, and constructed integer stochastic programming model. According to model’s characteristics, genetic algorithm was designed to solve constructed model. Author compared genetic algorithm’s result with that obtained by Lingo, and analyzed advantage and disadvantage of these two methods.
2. Author transformed network flow transportation time and transportation cost from constraints to objectives, and studied multi-objective optimization problem upon stochastic flow network. In order to solve constructed model, author improved NSGA-II’s tournament selection operator, simulated binary crossover operator and elitist strategy. Tested by examples, improved algorithm was better than former NSGA-II.
3. Existed algorithms on computing stochastic flow network’s reliability contained maximal flow minimal cut theory, Ford-Fulkerson algorithm and other traditional theory, so the variables in stochastic flow network was restricted to be discrete variables. Because of using genetic algorithm to optimize network flow in paper, above restriction was invalid and variables in model could be continuous. In order to deal with equation constraints containing continuous variables, author added a parameter and decomposed an equation constraint to two inequation constraints. Author solved decomposed model by improved NSGA-II. Tested by an example, algorithm can figure out the Pareto frontier of continuous optimization model.
4. Network flow optimization problem was studied upon network which nodes’demand was stochastic. Author constructed chance constrained programming model and transformed confidence level constraints to corresponding determinate constraints and dealt with other constraints by stochastic simulation method. A multi-objective genetic algorithm based on stochastic simulation was propounded to solve constructed model. Tested by examples, the algorithm can figure out model’s Pareto solutions.
目前主要从3个方面将随机因素引入网络流理论:1.令网络的权值为随机变量;2.假设网络的拓扑结构为随机的;3.假设网络中各边的容量为随机变量,提出了随机型流量网络(Stochastic Flow Network)的概念。随机型流量网络上的网络流理论的研究目前处于起步阶段,研究主要集中在:设计算法寻找网络流在网络容量状态X下的最大流V(X)能满足接收端需求d的网络容量状态的临界点d-MCs或d-MPs,并根据这些点计算随机型流量网络的可靠性。但当随机型流量网络的容量处于非临界状态时,对网络流进行分配优化的研究还较少见,论文中将针对不同问题选取特定优化目标,研究网络流不处于最大流状态V(X)时的优化问题。论文主要研究了以下几方面的内容:
1.以目前使用较多的两种随机型流量网络模型(网络节点可靠,单商品流,多发送端,多接收端的网络模型和网络节点不可靠,多商品流,多发送端,多接收端的网络模型)为基础,研究当网络流不处于最大流状态V(X)时如何对网络流流量进行分配优化。选定满足接收端需求的网络流可靠性为目标,建立整数随机规划模型。针对模型的特点,设计相应的算子,采用遗传算法对优化模型进行求解,并与使用Lingo软件方法求解得到的结果进行比较,分析两种求解方法的优缺点及其适用的问题。
2.文中将网络流传输时间和成本从约束条件转化为整体优化目标,并结合网络流可靠性这一主要目标,研究随机型流量网络上网络流的多目标优化问题。为求解建立的多目标优化模型,对NSGA-II方法做出如下改进:改进2-联赛选择算子的比较规则,将模拟2进制交叉算子改进为单点复合交叉算子,改进精英保留策略,使用改进后的算法对模型进行求解,经过测试,得到的结果从多方面优于原NSGA-II算法。
3.已有的随机型流量网络可靠性的算法,由于涉及到最大流最小割原理和Ford-Fulkerson算法等传统网络流理论,故不得不假设随机型流量网络中的所有变量为离散型变量。本文中由于采用了单目标/多目标遗传算法对网络流进行优化,故不受上面的限制。因此文中扩展随机型流量网络的容量为连续型随机变量,各条边上分配的网络流量为连续实数,建立连续型的多目标网络流优化模型,为了处理包含连续型变量的等式约束,对等式约束增加逼近参数,将等式约束分解为两条不等式约束以逼近方式处理。采用改进后的NSGA-II对处理后的优化模型进行求解。通过测试,可快速求出连续型多目标优化模型的Pareto前沿。
4.论文对网络中各节点包含随机需求的网络流多目标优化问题进行了研究。针对这种复杂随机情况下的网络流优化问题建立了机会约束多目标随机规划模型。对建立的随机规划模型进行预处理,将部分以置信度表示的约束条件转化为对应的确定性等价约束。采用随机模拟方法对优化模型的其余部分进行处理。结合前面提到的改进后的多目标遗传算法,提出一个基于随机模拟的多目标遗传算法对机会约束随机规划模型进行求解。通过算例测试,可以求得优化问题的Pareto解集。
Network flow theory is an important branch of Graph Theory, and it is the theory of studying optimization problems upon network. In 1956, L.R. Ford and D.R. Fulkerson propound the algorithm to solve the problem of seeking maximal transportation quantity between two nodes on the network. From then on, network flow theory was founded and developed. Network flow theory now has been widely applied to communication, transportation, power transmission, engineering programming and other fields. In order to solve the practical problem better, some new network flow theory were propounded, such as assignment and matching, LaGrange relaxation of network optimization, multi-commodity flow, network flow’s decomposition and combination and so on. But above research were all based on network whose parameters and topology structure were determinate. Network system in practical circumstance often presents randomicity because of influence of some factors. So it often causes some errors when apply traditional network flow theory to practical problems. It is significant for improving network flow theory’s practicability to optimize network flow in stochastic circumstance. This question has drawn attention.
Presently, stochastic factor has been introduced into network flow theory from three aspects: 1. suppose arcs’weights in network are stochastic variables; 2. suppose network’s topology structure is stochastic; 3. suppose arcs’capacities are stochastic variables, and propound the conception of stochastic flow network. Previous research on network flow theory upon stochastic flow network focused on designing algorithms to seek network’s critical capacity states (d-MCS or d-MPs) and computing network’s reliability according to these states. But when stochastic flow network’s capacity is not critical state, research on network flow optimization is few. So author selected different objectives according to different circumstance and studied optimization problems under the condition that network flow was not maximal flow V(X). The article mainly contains four contents as follows:
1. Basing two frequently used stochastic flow network models (network model with reliable nodes, single-commodity flow, multi-source nodes, multi-sink nodes and network model with unreliable nodes, multi-commodity flow, multi-source nodes, and multi-sink nodes), author studied how to optimize network flow when network flow was not maximal flow V(X).Author selected network flow’s reliability as objective, and constructed integer stochastic programming model. According to model’s characteristics, genetic algorithm was designed to solve constructed model. Author compared genetic algorithm’s result with that obtained by Lingo, and analyzed advantage and disadvantage of these two methods.
2. Author transformed network flow transportation time and transportation cost from constraints to objectives, and studied multi-objective optimization problem upon stochastic flow network. In order to solve constructed model, author improved NSGA-II’s tournament selection operator, simulated binary crossover operator and elitist strategy. Tested by examples, improved algorithm was better than former NSGA-II.
3. Existed algorithms on computing stochastic flow network’s reliability contained maximal flow minimal cut theory, Ford-Fulkerson algorithm and other traditional theory, so the variables in stochastic flow network was restricted to be discrete variables. Because of using genetic algorithm to optimize network flow in paper, above restriction was invalid and variables in model could be continuous. In order to deal with equation constraints containing continuous variables, author added a parameter and decomposed an equation constraint to two inequation constraints. Author solved decomposed model by improved NSGA-II. Tested by an example, algorithm can figure out the Pareto frontier of continuous optimization model.
4. Network flow optimization problem was studied upon network which nodes’demand was stochastic. Author constructed chance constrained programming model and transformed confidence level constraints to corresponding determinate constraints and dealt with other constraints by stochastic simulation method. A multi-objective genetic algorithm based on stochastic simulation was propounded to solve constructed model. Tested by examples, the algorithm can figure out model’s Pareto solutions.
引文
[1] Hudson JC, Kapur KC. Reliability analysis for multistate systems with multistate components. IIE Transactions 1983;15(2):127–35.
[2] Hudson JC, Kapur KC. Reliability bounds for multistate systems with multistate components. Operations Research 1985;33(1):153–60.
[3] Aven T. Reliability evaluation of multistate systems with multistate components. IEEE Trans Reliab 1985;34(5):473–9.
[4] Doulliez, P. and J. Jamoulle, “Transportation networks with random arc capacities,” Recherche Operationnelle, 1972;3: 45-60 .
[5] Evans, J. R., “Maximal flow in probabilistic graphs - the discrete case,” Networks, 1976;6:161-183 .
[6] Clancy, D. P., G. Gross and F. F. Wu, “Probability flows for reliability evaluation of multiarea power system interconnections,” Electrical Power and Energy System, 1983;5:100-114 .
[7] Abraham, J. A., “An improved algorithm for network reliability,” IEEE Transactions Reliability, 1979;28:58-61.
[8] Aggarwal, K. K., Y. C. Chopra and J. S. Bajwa, “Capacity consideration in reliability analysis of communication systems,” IEEE Transactions Reliability, 1982;31:177-180 .
[9] Lee SH. Reliability evaluation of a flow network. IEEE Trans Reliab 1980;29(1):24–6.
[10] Xue J. On multistate system analysis. IEEE Trans Reliab 1985;34(4):329–37.
[11] Lin JS, Jane CC, Yuan J. On reliability evaluation of a capacitated flow network in terms of minimal pathsets. Networks 1995;3:131–8.
[12] Jane CC, Lin JS, Yuan J. Reliability evaluation of a limited-flow network in terms of minimal cutsets. IEEE Trans Reliab 1993;42(3):354–61.
[13] Al-Ghanim AM. A heuristic technique for generating minimal paths and cutsets of a general network. Computers and Industrial Engineering 1999;36:45–55.
[14] Kobayashi K, Yamamoto H. A new algorithm in enumerating all minimal pathsin a sparse network. Reliability Engineering and System Safety 1999;65:11–15.
[15] Shen Y. A new simple algorithm for enumerating all minimal paths and cuts of a graph. Microelectronics and Reliability 1995;35:973–976.
[16] El-Neweihi, E., F. Proschan and J. Sethuraman, “Multistate coherent systems,” Journal of Applied Probability, 1978;15: 675-688 .
[17] Ball, M. O., “Computational complexity of network reliability analysis: an overview,” IEEE Transactions Reliability, 1986;35(3):230-239 .
[18] Yi-Kuei Lin. On reliability evaluation of a stochastic-flow network in terms of minimal cuts. Journal of the Chinese Institute of Industrial Engineers 2001;18(3): 49-54.
[19] Yi-Kuei Lin. Evaluate the performance of a stochastic-flow network with cost attribute in terms of minimal cuts. Reliability Engineering & System Safety 2006;91(5): 539-45.
[20] Zhou Yan, Meng Qian. Improving efficiency of solving d-MC problem in stochastic-flow network. Reliability Engineering & System Safety Article in Press, www.elsevier.com/locate/ress.
[21] Yi-Kuei Lin. On a multicommodity stochastic-flow network with unreliable nodes subject to budget constraint. European Journal of Operational Research Article in Press, www.elsevier.com/locate/ejor.
[22] Yi-Kuei Lin. Study on the system capacity for a multicommodity stochastic-flow network with node failure. Reliability Engineering & System Safety 2002;78(1):57-62.
[23] Weiwe-Chang Yeh, A simple MC-based algorithm for evaluating reliability of stochastic-flow network with unreliable nodes. Reliability Engineering & System Safety 2004;83(1):47-55.
[24] Yi-Kuei Lin. Using minimal cuts to study the system capacity for a stochastic-flow network in two-commodity case. Computers & Operations Research 2003;30(11):1595-1607.
[25] Chung-Chi Hsieh, Ming-Hsien Lin. Reliability-oriented multi-resource allocation in a stochastic-flow network. Reliability Engineering & System Safety 2003;81(2):155-161.
[26] Yi-Kuei Lin. Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network. Computers & Operations Research 2003;30(4):567-575.
[27] Yi-Kuei Lin. Two-commodity reliability evaluation for a stochastic-flow network with node failure Computers & Operations Research 2002;29(13):1927-1939.
[28] Yi-Kuei Lin. An algorithm to evaluate the system reliability for multicommodity case under cost constraint. Computers & Mathematics with Applications 2004;48(5-6):805-812.
[29] Yi-Kuei Lin. Using minimal cuts to evaluate the system reliability of a stochastic-flow network with failures at nodes and arcs. Reliability Engineering & System Safety 2002;75(1):41-46.
[30] Yi-Kuei Lin. A simple algorithm for reliability evaluation of a stochastic-flow network with node failure. Computers & Operations Research 2001;28(13):1277-1285.
[31] Yeh WC. A simple algorithm to search for all d-MPs with unreliable nodes. Reliab Engng Syst Safety 2001;73(1):49–54.
[32] Lin YK, Yuan J. A new algorithm to generate d-minimal paths in a multistate flow network with non-integer arc capacities. International Journal of Reliability, Quality and Safety Engineering 1998;5:269–85.
[33] Yeh WC. A simple method to verify all d-minimal path candidates of a limited-flow network and its reliability. Int J Adv Manufact Technol 2002;20(1):77–81.
[34] Lin JS. Reliability evaluation of capacitated-flow networks with budget constraints. IIE Transactions 1998;30(12):1175–80.
[35] Yeh WC. A simple approach to search for all d-MCs of a limited-flow network. Reliab Engng Syst Safety 2001;71(1):15–19.
[36] Hikita M, Nakagawa Y, Nakashima K, Narihisa H. Reliability optimization of systems by a surrogate constraints algorithms. IEEE Trans Reliab 1992;41(3):473–80.
[37] Luus R. Optimization of system reliability by a new nonlinear integerprogramming procedure. IEEE Trans Reliab 1975;24(1):14–16.
[38] Misra KB, Ljubojevic MD. Optimization reliability design for a system: a new look. IEEE Trans Reliab 1973;22(5):255–8.
[39] Moskowitz F, Mclean JB. Some reliability aspects of system design, IRE Trans Reliab Qual Control 1956;8:7–35.
[40] Tillman FA, Littschwager JM. Integer programming formulation of constrained reliability problems. Mgmt Sci 1967;13:887–9.
[41] Coit DW, Smith AE. Reliability optimisation of series-parallel systems using a genetic algorithm. IEEE Trans Reliab 1996;45(2):254–60.
[42] Hsieh CC. Optimal task allocation and hardware redundancy policies in distributed computing systems. Eur J Oper Res 2003;147(2):430–77.
[43] Nakagawa Y, Nakashima K. A heuristic method for determining reliability allocation. IEEE Trans Reliab 1977;26(3):156–61.
[44] Painton L, Campbell J. Genetic algorithms in optimization of system reliability. IEEE Trans Reliab 1995;44(2):172–8.
[45] Tillman FA, Hwang CL, Kuo W. Determining component reliability and redundancy for optimal system reliability. IEEE Trans Reliab 1977;26(3):153–7.
[46] 孙伟平,周敬利,余胜生,计算随机流量网络可靠度的算法综述,计算机科学,2004;31(1):25-27.
[47] 王芳,侯朝祯, 一个估计随机流网络可靠性的新方法, 小型微型计算机系统, 2005;26(5)783-787.
[48] 孙伟平, 周敬利, 余胜生, 一类节点与弧的容量均有限制的随机流量网络可靠度的计算,计算机科学, 2004;31(2):29-31.
[49] 孙伟平,周敬利,余胜生, 一类允许节点失效的多信息流随机流量网络的可靠度研究,计算机科学 2003;30(11):88-90.
[50] 王芳, 侯朝桢, 用蒙特卡罗和 Petri 网方法估计随机流网络的可靠性, 北京理工大学学报, 2004; 24(7):604-608.
[51] 王芳, 侯朝桢, 一种计算随机流网络可靠性的新算法, 通信学报, 2004;25(1):70-77.
[52] Daniel Salazar, Claudio M. Rocco , Blas J. Galván. Optimization ofconstrained multiple-objective reliability problems using evolutionary algorithms. Reliability Engineering & System Safety ,2006;91(9):1057-1070.
[53] Zhigang Tiana and Ming J. Zuo. Redundancy allocation for multi-state systems using physical programming and genetic algorithms. Reliability Engineering & System Safety 2006;91(9):1049-1056.
[54] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II . IEEE Transactions on Evolutionary Computation. 2002.6(2):182-197.
[55] N. Srinivas, and K. Deb, Multi-Objective function optimization using non-dominated sorting genetic algorithms," Evolutionary Computation, 1995;2:. 221-248.
[56] Deb K. An efficient constraint handling method for genetic algorithms[J] Computer Methods in Applied Mechanics and Engineering, 2000;186(2-4):311-338.
[57] Iwamura K, Liu B, A genetic algorithm for chance constrained programming. Journal of Information & Optimization Sciences, 1996,17(2):40-47.
[58] 崔晓婷 随机网络中中国邮路算法问题研究 大连理工大学硕士学位论文 2005.12.
[59] 柳亚玲 随机网络的寻径算法及应用 大连理工大学硕士学位论文. 2002.3
[60]Watts D J,Strogatz S H.Colleetive dynamics o‘fsmall world’networks. Nature, 1998;393(6684):440-442.
[61] Barabasi A L,Albert R. Emergence of scaling in random networks. Science, 1999;286(5439):509-512.
[62] P. Erdos, A. Renyi. On random graphs. Publ. Math. Debrecen,1959; 6:290-297.
[63] R. Albert,H. Jeong, A. L. Barabasi. Attack and error tolerance of complex networks. Nature. 2000;406:378-382.
[64] J.Kleinberg. Navigation in a Small World. Nature. 2000;.406:845-850.
[65] J. L. Guilluame,M. Latpay. The Web Grpah: an Overview in: Quatriemes Rencontres Francophones sur les aspects Algortihmliques des Telecommunications (AlgoTel)(in French).2002, May, Meze.
[66] M. E. J. Newman,Scientific collaboration networks. I. Network constructionand fundamental results, Phys. Rev. E64(2001),016131.
[67] M. E. J. Newman,Scientific collaboration networks. II. Network construction and fundamental results, Phys. Rev. E64(2001),016132.
[68] Fonseca C. M, Fleming P. J. An overview of evolutionary algorithms in multiobjective optimization evolutionary computation. IEEE Transactions on Evolutionary Computation, 1995;3(1):1-16.
[69] Horn J. Multi-criterion decision making. In: Back T ed. Handbook of Evolutionary Computation Oxford: Oxford University Press.1997.
[70] William B. The Papers of Benjamin Franklin.Yale University Press, New Haven, 1975;19:299- 300.
[71] Koopmans C. Analysis of Production as an Efficient Combination of Activities. Activity Analysis of Production and Allocation,1951,John Wileyand Sons:33 -97.
[72] Kuhn H.W., Tucker A.W. Nonlinear programming, Proceedings of the second Berkeley Symposium on Mathematical Statistical and Probability, 1951, U. California Press:481-491.
[73] ZadehL.A. Optimality and Nonscalar-Valued Performance Criteria. IEEE Transaction Automatic Control,1963;pp:59-60.
[74] Geofrion A.M. Proper Efficiency and the Theory of Vector Optimization. Journal of Mathematical Analysis and Application,1968;41:491-502.
[75] Charnes A, Cooper and Ferguson W.W.R.O. Optimal Estimation of executive compensation by linear programming. Management Science,1955;1:138-151.
[76] Charnes A., and Cooper. Management Models and Industrial Applications of Linear Programming NewYork, John Wiley& Sons,1961.
[77] Haimes, Lasdon L., and Wismer D. On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization. IEEE Transaction System, Man, and Cybernetics,1971;1:296-297.
[78] Brian J, Ritzel J.,and Ranjithan S. Using Genetic Algorithms to Solve a Multiple Objective Groundwater Pollution Containment Problem. Water Resources Research,1994;30(5):1589 -1603.
[79] Ben-Tal, Aharon. Characterization of Pareto and Lexicographic Optimal Solutions. Multiple Criteria Decision Making Theory and Application 177. LectureNotes in Economics and Ma the matical Systems, Berlin: Springer-Verlag,1980.
[80] Osyczka A., Multicriteria optimization in Engineering with FORTRAN programs. Ellis Horwood Limited,1984.
[81] Tseng C.H., and T.WLu. Minimax Multiobjective Optimization in Structural Design. International Journal for Numerical Methods in Engineering, 1990; 30:1213-1228.
[82] Holland J.H. Outline for a logical theory of adaptive systems. Journal of the Association for Computing Machinery, 1962;3:297-314.
[83] Holland J.H. A new kind of turnpike theorem. Bulletin of the American Mathematical Society, 1969;75:297-314.
[84] Foguel L.J. Artificial Intelligence through simulated evolution. John Wiley & Sons,1966.
[85] Koza J.R. Genetic programming on the programming of computers by means of natural selection. MIT Press, 1992.
[86] Koza J.R. Genetic programming II, automatic discovery of reusable programs. MIT Press, 1994.
[87] 刘勇,康立山,陈屏.非数值并行算法(第二册).北京:科学出版社,2003.
[88] 陈国良等. 遗传算法的理论及其应用. 北京:人民邮电出版社,1996.
[89] Schaffer J.D. Multiobjective optimization with vector evaluated genetic algorithms. In: Proceedings of the first International Conference on Genetic Algorithms. Lawrence Erlbaum Associates, Hillsdale,1985:93-100.
[90] Eckart Zitzler. Evolutionary algorithms for multiobjective optimization: methods and applications. Ph.D dissertation, Computer Engineering and networks Laboratory, Swiss Federal Institute of Technology Zurich, Swiss: 1999.
[91] Zitzler E., Lanumanns M., and Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In K. Giannakoglou et al., editors, Evolutionary Methods for Design, Optimisation, and Control, 2002.
[92] Corne D.W. et al. The Pareto envelope-based selection algorithm for multi- objective optimization[c]. In: M Schoenauered. Lecture Notes in Computer Science, Proc Parallel Problem Solving from Nature–PPSN VI,vol. 1917;2000:839-848.
[93] Knowles J. and Corne D. The Pareto archived evolution strategy: A newbaseline algorithm for multiobjective optimization In: Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway, NJ: IEEE Press, 1999: 98- 105.
[94].Goldberg, D. E, and Deb, K. A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms, Belew, R.K. , and Booker, L. B.(eds), San Mateo, CA: Morgan Kaufmann Pubilshers, 1991:69-93.
[2] Hudson JC, Kapur KC. Reliability bounds for multistate systems with multistate components. Operations Research 1985;33(1):153–60.
[3] Aven T. Reliability evaluation of multistate systems with multistate components. IEEE Trans Reliab 1985;34(5):473–9.
[4] Doulliez, P. and J. Jamoulle, “Transportation networks with random arc capacities,” Recherche Operationnelle, 1972;3: 45-60 .
[5] Evans, J. R., “Maximal flow in probabilistic graphs - the discrete case,” Networks, 1976;6:161-183 .
[6] Clancy, D. P., G. Gross and F. F. Wu, “Probability flows for reliability evaluation of multiarea power system interconnections,” Electrical Power and Energy System, 1983;5:100-114 .
[7] Abraham, J. A., “An improved algorithm for network reliability,” IEEE Transactions Reliability, 1979;28:58-61.
[8] Aggarwal, K. K., Y. C. Chopra and J. S. Bajwa, “Capacity consideration in reliability analysis of communication systems,” IEEE Transactions Reliability, 1982;31:177-180 .
[9] Lee SH. Reliability evaluation of a flow network. IEEE Trans Reliab 1980;29(1):24–6.
[10] Xue J. On multistate system analysis. IEEE Trans Reliab 1985;34(4):329–37.
[11] Lin JS, Jane CC, Yuan J. On reliability evaluation of a capacitated flow network in terms of minimal pathsets. Networks 1995;3:131–8.
[12] Jane CC, Lin JS, Yuan J. Reliability evaluation of a limited-flow network in terms of minimal cutsets. IEEE Trans Reliab 1993;42(3):354–61.
[13] Al-Ghanim AM. A heuristic technique for generating minimal paths and cutsets of a general network. Computers and Industrial Engineering 1999;36:45–55.
[14] Kobayashi K, Yamamoto H. A new algorithm in enumerating all minimal pathsin a sparse network. Reliability Engineering and System Safety 1999;65:11–15.
[15] Shen Y. A new simple algorithm for enumerating all minimal paths and cuts of a graph. Microelectronics and Reliability 1995;35:973–976.
[16] El-Neweihi, E., F. Proschan and J. Sethuraman, “Multistate coherent systems,” Journal of Applied Probability, 1978;15: 675-688 .
[17] Ball, M. O., “Computational complexity of network reliability analysis: an overview,” IEEE Transactions Reliability, 1986;35(3):230-239 .
[18] Yi-Kuei Lin. On reliability evaluation of a stochastic-flow network in terms of minimal cuts. Journal of the Chinese Institute of Industrial Engineers 2001;18(3): 49-54.
[19] Yi-Kuei Lin. Evaluate the performance of a stochastic-flow network with cost attribute in terms of minimal cuts. Reliability Engineering & System Safety 2006;91(5): 539-45.
[20] Zhou Yan, Meng Qian. Improving efficiency of solving d-MC problem in stochastic-flow network. Reliability Engineering & System Safety Article in Press, www.elsevier.com/locate/ress.
[21] Yi-Kuei Lin. On a multicommodity stochastic-flow network with unreliable nodes subject to budget constraint. European Journal of Operational Research Article in Press, www.elsevier.com/locate/ejor.
[22] Yi-Kuei Lin. Study on the system capacity for a multicommodity stochastic-flow network with node failure. Reliability Engineering & System Safety 2002;78(1):57-62.
[23] Weiwe-Chang Yeh, A simple MC-based algorithm for evaluating reliability of stochastic-flow network with unreliable nodes. Reliability Engineering & System Safety 2004;83(1):47-55.
[24] Yi-Kuei Lin. Using minimal cuts to study the system capacity for a stochastic-flow network in two-commodity case. Computers & Operations Research 2003;30(11):1595-1607.
[25] Chung-Chi Hsieh, Ming-Hsien Lin. Reliability-oriented multi-resource allocation in a stochastic-flow network. Reliability Engineering & System Safety 2003;81(2):155-161.
[26] Yi-Kuei Lin. Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network. Computers & Operations Research 2003;30(4):567-575.
[27] Yi-Kuei Lin. Two-commodity reliability evaluation for a stochastic-flow network with node failure Computers & Operations Research 2002;29(13):1927-1939.
[28] Yi-Kuei Lin. An algorithm to evaluate the system reliability for multicommodity case under cost constraint. Computers & Mathematics with Applications 2004;48(5-6):805-812.
[29] Yi-Kuei Lin. Using minimal cuts to evaluate the system reliability of a stochastic-flow network with failures at nodes and arcs. Reliability Engineering & System Safety 2002;75(1):41-46.
[30] Yi-Kuei Lin. A simple algorithm for reliability evaluation of a stochastic-flow network with node failure. Computers & Operations Research 2001;28(13):1277-1285.
[31] Yeh WC. A simple algorithm to search for all d-MPs with unreliable nodes. Reliab Engng Syst Safety 2001;73(1):49–54.
[32] Lin YK, Yuan J. A new algorithm to generate d-minimal paths in a multistate flow network with non-integer arc capacities. International Journal of Reliability, Quality and Safety Engineering 1998;5:269–85.
[33] Yeh WC. A simple method to verify all d-minimal path candidates of a limited-flow network and its reliability. Int J Adv Manufact Technol 2002;20(1):77–81.
[34] Lin JS. Reliability evaluation of capacitated-flow networks with budget constraints. IIE Transactions 1998;30(12):1175–80.
[35] Yeh WC. A simple approach to search for all d-MCs of a limited-flow network. Reliab Engng Syst Safety 2001;71(1):15–19.
[36] Hikita M, Nakagawa Y, Nakashima K, Narihisa H. Reliability optimization of systems by a surrogate constraints algorithms. IEEE Trans Reliab 1992;41(3):473–80.
[37] Luus R. Optimization of system reliability by a new nonlinear integerprogramming procedure. IEEE Trans Reliab 1975;24(1):14–16.
[38] Misra KB, Ljubojevic MD. Optimization reliability design for a system: a new look. IEEE Trans Reliab 1973;22(5):255–8.
[39] Moskowitz F, Mclean JB. Some reliability aspects of system design, IRE Trans Reliab Qual Control 1956;8:7–35.
[40] Tillman FA, Littschwager JM. Integer programming formulation of constrained reliability problems. Mgmt Sci 1967;13:887–9.
[41] Coit DW, Smith AE. Reliability optimisation of series-parallel systems using a genetic algorithm. IEEE Trans Reliab 1996;45(2):254–60.
[42] Hsieh CC. Optimal task allocation and hardware redundancy policies in distributed computing systems. Eur J Oper Res 2003;147(2):430–77.
[43] Nakagawa Y, Nakashima K. A heuristic method for determining reliability allocation. IEEE Trans Reliab 1977;26(3):156–61.
[44] Painton L, Campbell J. Genetic algorithms in optimization of system reliability. IEEE Trans Reliab 1995;44(2):172–8.
[45] Tillman FA, Hwang CL, Kuo W. Determining component reliability and redundancy for optimal system reliability. IEEE Trans Reliab 1977;26(3):153–7.
[46] 孙伟平,周敬利,余胜生,计算随机流量网络可靠度的算法综述,计算机科学,2004;31(1):25-27.
[47] 王芳,侯朝祯, 一个估计随机流网络可靠性的新方法, 小型微型计算机系统, 2005;26(5)783-787.
[48] 孙伟平, 周敬利, 余胜生, 一类节点与弧的容量均有限制的随机流量网络可靠度的计算,计算机科学, 2004;31(2):29-31.
[49] 孙伟平,周敬利,余胜生, 一类允许节点失效的多信息流随机流量网络的可靠度研究,计算机科学 2003;30(11):88-90.
[50] 王芳, 侯朝桢, 用蒙特卡罗和 Petri 网方法估计随机流网络的可靠性, 北京理工大学学报, 2004; 24(7):604-608.
[51] 王芳, 侯朝桢, 一种计算随机流网络可靠性的新算法, 通信学报, 2004;25(1):70-77.
[52] Daniel Salazar, Claudio M. Rocco , Blas J. Galván. Optimization ofconstrained multiple-objective reliability problems using evolutionary algorithms. Reliability Engineering & System Safety ,2006;91(9):1057-1070.
[53] Zhigang Tiana and Ming J. Zuo. Redundancy allocation for multi-state systems using physical programming and genetic algorithms. Reliability Engineering & System Safety 2006;91(9):1049-1056.
[54] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II . IEEE Transactions on Evolutionary Computation. 2002.6(2):182-197.
[55] N. Srinivas, and K. Deb, Multi-Objective function optimization using non-dominated sorting genetic algorithms," Evolutionary Computation, 1995;2:. 221-248.
[56] Deb K. An efficient constraint handling method for genetic algorithms[J] Computer Methods in Applied Mechanics and Engineering, 2000;186(2-4):311-338.
[57] Iwamura K, Liu B, A genetic algorithm for chance constrained programming. Journal of Information & Optimization Sciences, 1996,17(2):40-47.
[58] 崔晓婷 随机网络中中国邮路算法问题研究 大连理工大学硕士学位论文 2005.12.
[59] 柳亚玲 随机网络的寻径算法及应用 大连理工大学硕士学位论文. 2002.3
[60]Watts D J,Strogatz S H.Colleetive dynamics o‘fsmall world’networks. Nature, 1998;393(6684):440-442.
[61] Barabasi A L,Albert R. Emergence of scaling in random networks. Science, 1999;286(5439):509-512.
[62] P. Erdos, A. Renyi. On random graphs. Publ. Math. Debrecen,1959; 6:290-297.
[63] R. Albert,H. Jeong, A. L. Barabasi. Attack and error tolerance of complex networks. Nature. 2000;406:378-382.
[64] J.Kleinberg. Navigation in a Small World. Nature. 2000;.406:845-850.
[65] J. L. Guilluame,M. Latpay. The Web Grpah: an Overview in: Quatriemes Rencontres Francophones sur les aspects Algortihmliques des Telecommunications (AlgoTel)(in French).2002, May, Meze.
[66] M. E. J. Newman,Scientific collaboration networks. I. Network constructionand fundamental results, Phys. Rev. E64(2001),016131.
[67] M. E. J. Newman,Scientific collaboration networks. II. Network construction and fundamental results, Phys. Rev. E64(2001),016132.
[68] Fonseca C. M, Fleming P. J. An overview of evolutionary algorithms in multiobjective optimization evolutionary computation. IEEE Transactions on Evolutionary Computation, 1995;3(1):1-16.
[69] Horn J. Multi-criterion decision making. In: Back T ed. Handbook of Evolutionary Computation Oxford: Oxford University Press.1997.
[70] William B. The Papers of Benjamin Franklin.Yale University Press, New Haven, 1975;19:299- 300.
[71] Koopmans C. Analysis of Production as an Efficient Combination of Activities. Activity Analysis of Production and Allocation,1951,John Wileyand Sons:33 -97.
[72] Kuhn H.W., Tucker A.W. Nonlinear programming, Proceedings of the second Berkeley Symposium on Mathematical Statistical and Probability, 1951, U. California Press:481-491.
[73] ZadehL.A. Optimality and Nonscalar-Valued Performance Criteria. IEEE Transaction Automatic Control,1963;pp:59-60.
[74] Geofrion A.M. Proper Efficiency and the Theory of Vector Optimization. Journal of Mathematical Analysis and Application,1968;41:491-502.
[75] Charnes A, Cooper and Ferguson W.W.R.O. Optimal Estimation of executive compensation by linear programming. Management Science,1955;1:138-151.
[76] Charnes A., and Cooper. Management Models and Industrial Applications of Linear Programming NewYork, John Wiley& Sons,1961.
[77] Haimes, Lasdon L., and Wismer D. On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization. IEEE Transaction System, Man, and Cybernetics,1971;1:296-297.
[78] Brian J, Ritzel J.,and Ranjithan S. Using Genetic Algorithms to Solve a Multiple Objective Groundwater Pollution Containment Problem. Water Resources Research,1994;30(5):1589 -1603.
[79] Ben-Tal, Aharon. Characterization of Pareto and Lexicographic Optimal Solutions. Multiple Criteria Decision Making Theory and Application 177. LectureNotes in Economics and Ma the matical Systems, Berlin: Springer-Verlag,1980.
[80] Osyczka A., Multicriteria optimization in Engineering with FORTRAN programs. Ellis Horwood Limited,1984.
[81] Tseng C.H., and T.WLu. Minimax Multiobjective Optimization in Structural Design. International Journal for Numerical Methods in Engineering, 1990; 30:1213-1228.
[82] Holland J.H. Outline for a logical theory of adaptive systems. Journal of the Association for Computing Machinery, 1962;3:297-314.
[83] Holland J.H. A new kind of turnpike theorem. Bulletin of the American Mathematical Society, 1969;75:297-314.
[84] Foguel L.J. Artificial Intelligence through simulated evolution. John Wiley & Sons,1966.
[85] Koza J.R. Genetic programming on the programming of computers by means of natural selection. MIT Press, 1992.
[86] Koza J.R. Genetic programming II, automatic discovery of reusable programs. MIT Press, 1994.
[87] 刘勇,康立山,陈屏.非数值并行算法(第二册).北京:科学出版社,2003.
[88] 陈国良等. 遗传算法的理论及其应用. 北京:人民邮电出版社,1996.
[89] Schaffer J.D. Multiobjective optimization with vector evaluated genetic algorithms. In: Proceedings of the first International Conference on Genetic Algorithms. Lawrence Erlbaum Associates, Hillsdale,1985:93-100.
[90] Eckart Zitzler. Evolutionary algorithms for multiobjective optimization: methods and applications. Ph.D dissertation, Computer Engineering and networks Laboratory, Swiss Federal Institute of Technology Zurich, Swiss: 1999.
[91] Zitzler E., Lanumanns M., and Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In K. Giannakoglou et al., editors, Evolutionary Methods for Design, Optimisation, and Control, 2002.
[92] Corne D.W. et al. The Pareto envelope-based selection algorithm for multi- objective optimization[c]. In: M Schoenauered. Lecture Notes in Computer Science, Proc Parallel Problem Solving from Nature–PPSN VI,vol. 1917;2000:839-848.
[93] Knowles J. and Corne D. The Pareto archived evolution strategy: A newbaseline algorithm for multiobjective optimization In: Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway, NJ: IEEE Press, 1999: 98- 105.
[94].Goldberg, D. E, and Deb, K. A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms, Belew, R.K. , and Booker, L. B.(eds), San Mateo, CA: Morgan Kaufmann Pubilshers, 1991:69-93.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |