跳转到内容

排序最佳化

维基百科,自由的百科全书

排序最佳化(ordinal optimization)也称为序最佳化,是最优化中的一种,是针对在偏序集(poset)上取值函数的最佳化[1][2][3][4]。排序最佳化可以应用在等候网络的理论中。

数学基础

[编辑]

偏序是指在集合P内的二元关系 "≤",是自反关系反对称关系传递关系。针对集合P内的所有a, bc,会有以下的关系:

  • a ≤ a(自反关系);
  • a ≤ bb ≤ a ,则 a = b(反对称关系);
  • if a ≤ b and b ≤ c,则 a ≤ c(传递关系).

偏序关系也可以说是预序关系。具有偏序关系的集合称为偏序集(poset)。

针对偏序集P内的两个相异元素a, b,若a ≤ bb ≤ a,则ab 是可比较的,否则是不可比较的。若偏序集中任两个元素都是可比较的,此偏序集称为全序关系或“chain”(也就是依顺序排列的自然数)。若任两个元素都是不可比较的,则称为反链

以下是一些数学中偏序集的例子:

  • 实数的偏序关系是标准的小于等于关系 ≤ ,也是全序集。
  • 特定集合子集形成的集合(幂集),偏序关系是包含
  • 向量空间子空间的集合,偏序关系也是包含。

计算机科学及统计学中的排序最佳化

[编辑]

在许多领域都有排序最佳化的问题。计算机科学中会研究选择算法,这种算法比排序算法要简单[5][6]

决策论会研究选择算法,会要识别出“最佳”的子群体,或是识别出“近乎最佳”的子群体[7][8][9][10][11]

应用

[编辑]

自1960年代起,排序最佳化在其理论及应用上都有许多的扩展。其中的antimatroid英语antimatroidmax-plus代数英语max-plus algebra已应用在网络分析等候理论中,特别是在等候网络中。排序最佳化也应用在离散事件仿真[12][13][14]

相关条目

[编辑]

参考文献

[编辑]
  1. ^ Brenda L. Dietrich; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. IBM J. Res. Dev. 47 (2003), no. 1, 25–30.
  2. ^ Topkis, Donald M. Supermodularity and complementarity. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN 0-691-03244-0
  3. ^ Singer, Ivan Abstract convex analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997. xxii+491 pp. ISBN 0-471-16015-6
  4. ^ Björner, Anders; Ziegler, Günter M. Introduction to greedoids. Matroid applications, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,
  5. ^ Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.3: Minimum-Comparison Selection, pp.207–219.
  6. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 9: Medians and Order Statistics, pp.183–196. Section 14.1: Dynamic order statistics, pp.302–308.
  7. ^ Gibbons, Jean Dickinson; Olkin, Ingram, and Sobel, Milton, Selecting and Ordering of Populations, Wiley, (1977). (Republished as a Classic in Applied Mathematics by SIAM.)
  8. ^ Gupta, Shanti S.; Panchapakesan, S. Multiple decision procedures: Theory and methodology of selecting and ranking populations. Wiley Series in Probability and Mathematical Statistics. New York: John Wiley & Sons. 1979: xxv+573. ISBN 0-471-05177-2. MR 0555416.  (Republished as a Classic in Applied Mathematics by SIAM.)
  9. ^ Santner, Thomas J., and Tamhane, A. C., Design of Experiments: Ranking and Selection, M. Dekker, (1984).
  10. ^ Robert E. Bechhofer, Thomas J. Santner, David M. Goldsman. Design and Analysis of Experiments for Statistical Selection, Screening, and Multiple Comparisons. John Wiley & Sons, 1995.
  11. ^ Friedrich Liese, Klaus-J. Miescke. 2008. Statistical Decision Theory: Estimation, Testing, and Selection. Springer Verlag.
  12. ^ Glasserman, Paul; Yao, David D. Monotone structure in discrete-event systems. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. New York: John Wiley & Sons, Inc. 1994: xiv+297. ISBN 0-471-58041-4. MR 1266839. 
  13. ^ Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre. Synchronization and linearity: An algebra for discrete event systems. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Chichester: John Wiley & Sons, Ltd. 1992: xx+489. ISBN 0-471-93609-X. MR 1204266. 
  14. ^ Heidergott, Bernd; Oldser, Geert Jan; van der Woude, Jacob. Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications. Princeton Series in Applied Mathematics. Princeton, NJ: Princeton University Press. 2006: xii+213. ISBN 978-0-691-11763-8. MR 2188299. 

延伸阅读

[编辑]
  • Fujishige, Satoru Submodular functions and optimization. Second edition. Annals of Discrete Mathematics, 58. Elsevier B. V., Amsterdam, 2005. xiv+395 pp. ISBN 0-444-52086-4
  • Gondran, Michel; Minoux, Michel Graphs, dioids and semirings. New models and algorithms. Operations Research/Computer Science Interfaces Series, 41. Springer, New York, 2008. xx+383 pp. ISBN 978-0-387-75449-9
  • Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. IBM J. Res. Dev. 47 (2003), no. 1, 25–30.
  • Murota, Kazuo Discrete convex analysis. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2003. xxii+389 pp. ISBN 0-89871-540-7
  • Topkis, Donald M. Supermodularity and complementarity. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN 0-691-03244-0
  • Singer, Ivan Abstract convex analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997. xxii+491 pp. ISBN 0-471-16015-6
  • Björner, Anders; Ziegler, Günter M. Introduction to greedoids. Matroid applications, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,
  • Zimmermann, U. Linear and combinatorial optimization in ordered algebraic structures. Ann. Discrete Math. 10 (1981), viii+380 pp.
  • Cuninghame-Green, Raymond Minimax algebra. Lecture Notes in Economics and Mathematical Systems, 166. Springer-Verlag, Berlin-New York, 1979. xi+258 pp. ISBN 3-540-09113-0
  • Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre. Synchronization and linearity: An algebra for discrete event systems. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Chichester: John Wiley & Sons, Ltd. 1992: xx+489. ISBN 0-471-93609-X. MR 1204266. 
  • Glasserman, Paul; Yao, David D. Monotone structure in discrete-event systems. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. New York: John Wiley & Sons, Inc. 1994: xiv+297. ISBN 0-471-58041-4. MR 1266839. 
  • Heidergott, Bernd; Oldser, Geert Jan; van der Woude, Jacob. Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications. Princeton Series in Applied Mathematics. Princeton, NJ: Princeton University Press. 2006: xii+213. ISBN 978-0-691-11763-8. MR 2188299. 
  • Ho, Y.C., Sreenivas, R., Vakili, P.,"Ordinal Optimization of Discrete Event Dynamic Systems", J. of DEDS 2(2), 61-88, (1992).
  • Allen, Eric, and Marija D. Ilic. Price-Based Commitment Decisions in the Electricity Market. Advances in industrial control. London: Springer, 1999. ISBN 978-1-85233-069-9

外部链接

[编辑]