Skip to main content
Search
Search
  • Quick Search anywhere
  • Quick Search fdjslkfh
Advanced search
Cart
Join AIAA Institution Login
Skip main navigation
Close Drawer MenuOpen Drawer Menu
Journal of Aerospace Information Systems logo
No AccessFull-Length Paper

Bayesian Preference Elicitation for Multiobjective Engineering Design Optimization

Published Online:7 Oct 2015https://doi.org/10.2514/1.I010363

Abstract

Many engineering optimization problems have more than one objective. Although there are methods for identifying the Pareto front of a design space, these methods can be computationally prohibitive, and it is still left to the designer to choose which design on the front to build. Consequently, multiobjective optimization often involves specifying a scalar utility function and then optimizing with respect to this utility function. Preference elicitation algorithms can aid the designer in constructing this utility function. In preference elicitation for engineering design optimization, the ideal algorithm would converge to an accurate utility function with as few preference queries to the designer as possible. This paper extends a prior method for preference realization and tailors it for use in engineering design optimization by deriving a less restrictive inference technique and applying an entropy-based method for posing queries that converges faster to the true global utility function than existing algorithms. This method is then applied to optimization of a next-generation aircraft collision-avoidance system. Finally, an implementation of the algorithm is released as an open-source package in the Julia language.

References

  • [1] Belegundu A. D. and Chandrupatla T. R., Optimization Concepts and Applications in Engineering, 2nd ed., Cambridge Univ. Press, New York, 2011, pp. 339–359. Google Scholar

  • [2] Gandibleux X., Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys, Vol. 52, Springer Science & Business Media, New York, 2002. Google Scholar

  • [3] Deb K., “Multi-Objective Optimization,” Search Methodologies, Springer, New York, 2014, pp. 403–449. CrossrefGoogle Scholar

  • [4] Marler R. and Arora J., “Survey of Multi-Objective Optimization Methods for Engineering,” Structural and Multidisciplinary Optimization, Vol. 26, No. 6, 2004, pp. 369–395. doi:https://doi.org/10.1007/s00158-003-0368-6 SMOTB4 1615-1488 CrossrefGoogle Scholar

  • [5] Zalzala A. M. and Fleming P. J., Genetic Algorithms in Engineering Systems, Vol. 55, Inst. of Engineering and Technology, Stevenage, England, U.K., 1997, pp. 63–76. CrossrefGoogle Scholar

  • [6] Deb K. and Kalyanmoy D., Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, New York, 2001. Google Scholar

  • [7] Deb K., Pratap A., Agarwal S. and Meyarivan T., “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, April 2002, pp. 182–197. doi:https://doi.org/10.1109/4235.996017 ITEVF5 1089-778X CrossrefGoogle Scholar

  • [8] Chica M., Cordón O., Damas S. and Bautista J., “Interactive Preferences in Multiobjective Ant Colony Optimisation for Assembly Line Balancing,” Soft Computing, Vol. 19, No. 10, 2014, pp. 2891–2903. doi:https://doi.org/10.1007/s00500-014-1451-1 CrossrefGoogle Scholar

  • [9] Chica M., Cordón O., Damas S. and Bautista J., “Including Different Kinds of Preferences in a Multi-Objective Ant Algorithm for Time and Space Assembly Line Balancing on Different Nissan Scenarios,” Expert Systems with Applications, Vol. 38, No. 1, 2011, pp. 709–720. doi:https://doi.org/10.1016/j.eswa.2010.07.023 ESAPEH 0957-4174 CrossrefGoogle Scholar

  • [10] Kornbluth J., “A Survey of Goal Programming,” Omega, Vol. 1, No. 2, 1973, pp. 193–205. doi:https://doi.org/10.1016/0305-0483(73)90023-6 CrossrefGoogle Scholar

  • [11] Kuchar J. K., “Methodology for Alerting-System Performance Evaluation,” Journal of Guidance, Control, and Dynamics, Vol. 19, No. 2, 1996, pp. 438–444. doi:https://doi.org/10.2514/3.21637 JGCODS 0731-5090 LinkGoogle Scholar

  • [12] Braziunas D., “Computational Approaches to Preference Elicitation,” Dept. of Computer Science, Univ. of Toronto, TR, Toronto, 2006. Google Scholar

  • [13] Guo S. and Sanner S., “Real-Time Multiattribute Bayesian Preference Elicitation with Pairwise Comparison Queries,” International Conference on Artificial Intelligence and Statistics, Microtome Publ., Brookline, MA, 2010, pp. 289–296. Google Scholar

  • [14] Boutilier C., “A POMDP Formulation of Preference Elicitation Problems,” AAAI Innovative Applications of Artificial Intelligence Conference, Assoc. for the Advancement of Artificial Intelligence Press, Palo Alto, CA, 2002, pp. 239–246. Google Scholar

  • [15] Chajewska U., Koller D. and Parr R., “Making Rational Decisions Using Adaptive Utility Elicitation,” AAAI Innovative Applications of Artificial Intelligence Conference, Assoc. for the Advancement of Artificial Intelligence Press, Palo Alto, CA, 2000, pp. 363–369. Google Scholar

  • [16] Bezanson J., Karpinski S., Shah V. B. and Edelman A., “Julia: A Fast Dynamic Language for Technical Computing,” Computing Research Repository [online database], 2012, http://arxiv.org/abs/1209.5145 [cited 10 Nov. 2014]. Google Scholar

  • [17] Conitzer V., “Eliciting Single-Peaked Preferences Using Comparison Queries,” Journal of Artificial Intelligence Research, Vol. 35, June 2009, pp. 161–191. CrossrefGoogle Scholar

  • [18] Siskos Y. and Yannacopoulos D., “UTASTAR: An Ordinal Regression Method for Building Additive Value Functions,” Investigaçao Operacional, Vol. 5, No. 1, 1985, pp. 39–53. Google Scholar

  • [19] Bishop C. M., Pattern Recognition and Machine Learning, Springer, New York, 2006, pp. 18–24. Google Scholar

  • [20] Herbrich R., Minka T. and Graepel T., “Trueskill: A Bayesian Skill Rating System,” Advances in Neural Information Processing Systems, MIT Press, Cambridge, MA, 2006, pp. 569–576. Google Scholar

  • [21] Minka T. P., “Expectation Propagation for Approximate Bayesian Inference,” Conference on Uncertainty in Artificial Intelligence, Assoc. for Uncertainty in Artificial Intelligence Press, Corvallis, OR, 2001, pp. 362–369. Google Scholar

  • [22] Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H. and Teller E., “Equation of State Calculations by Fast Computing Machines,” Journal of Chemical Physics, Vol. 21, No. 6, 1953, pp. 1087–1092. doi:https://doi.org/10.1063/1.1699114 CrossrefGoogle Scholar

  • [23] Geman S. and Geman D., “Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 6, No. 6, 1984, pp. 721–741. doi:https://doi.org/10.1109/TPAMI.1984.4767596 CrossrefGoogle Scholar

  • [24] Yuan Y., “A Modified BFGS Algorithm for Unconstrained Optimization,” IMA Journal of Numerical Analysis, Vol. 11, No. 3, 1991, pp. 325–332. doi:https://doi.org/10.1093/imanum/11.3.325 IJNADH 0272-4979 CrossrefGoogle Scholar

  • [25] Bertsekas D. P., Nonlinear Programming, Athena Scientific, Belmont, MA, 1999, pp. 4–13. Google Scholar

  • [26] Powell M., “Some Global Convergence Properties of a Variable Metric Algorithm for Minimization Without Exact Line Searches,” Nonlinear Programming, Vol. 9, June 1976, pp. 53–72. Google Scholar

  • [27] Chen W., Wang Z. and Zhou J., “Large-Scale L-BFGS Using MapReduce,” Advances in Neural Information Processing Systems, MIT Press, Cambridge, MA, 2014, pp. 1332–1340. Google Scholar

  • [28] Gerstner T. and Griebel M., “Numerical Integration Using Sparse Grids,” Numerical Algorithms, Vol. 18, Nos. 3–4, 1998, pp. 209–232. doi:https://doi.org/10.1023/A:1019129717644 CrossrefGoogle Scholar

  • [29] Huang D., Allen T. T., Notz W. I. and Zeng N., “Global Optimization of Stochastic Black-Box Systems Via Sequential Kriging Meta-Models,” Journal of Global Optimization, Vol. 34, No. 3, 2006, pp. 441–466. doi:https://doi.org/10.1007/s10898-005-2454-3 JGOPEO 0925-5001 CrossrefGoogle Scholar

  • [30] Forrester A. I., Sóbester A. and Keane A. J., Engineering Design via Surrogate Modelling: A Practical Guide, AIAA, Reston, VA, 2008. CrossrefGoogle Scholar

  • [31] Smith K., Kochenderfer M. J., Olson W. and Vela A., “Collision Avoidance System Optimization for Closely Spaced Parallel Operations Through Surrogate Modeling,” AIAA Guidance, Navigation, and Control Conference, AIAA Paper  2013-4624, 2013. LinkGoogle Scholar

  • [32] Andrieu C. and Roberts G. O., “The Pseudo-Marginal Approach for Efficient Monte Carlo Computations,” Annals of Statistics, Vol. 37, No. 2, 2009, pp. 697–725. doi:https://doi.org/10.1214/07-AOS574 CrossrefGoogle Scholar

  • [33] Shannon C. E., “A Mathematical Theory of Communication,” Bell System Technical Journal, Vol. 27, No. 3, 1948, pp. 379–423, 623–656. doi:https://doi.org/10.1002/bltj.1948.27.issue-3 CrossrefGoogle Scholar

  • [34] Kramer A., Hasenauer J., Allgower F. and Radde N., “Computation of the Posterior Entropy in a Bayesian Framework for Parameter Estimation in Biological Networks,” IEEE Conference on Control Applications, IEEE Publ., Piscataway, NJ, 2010, pp. 493–498. Google Scholar

  • [35] Lindley D., “On a Measure of the Information Provided by an Experiment,” Annals of Mathematical Statistics, Vol. 27, No. 4, 1956, pp. 986–1005. CrossrefGoogle Scholar

  • [36] Houlsby N., Huszar F., Ghahramani Z. and Hernández-Lobato J. M., “Collaborative Gaussian Processes for Preference Learning,” Advances in Neural Information Processing Systems 25, edited by Pereira F., Burges C., Bottou L. and Weinberger K., Curran Associates, Red Hook, NY, 2012, pp. 2096–2104. Google Scholar

  • [37] MacKay D., “Information-Based Objective Functions for Active Data Selection,” Neural Computation, Vol. 4, No. 4, July 1992, pp. 590–604. doi:https://doi.org/10.1162/neco.1992.4.4.590 NEUCEB 0899-7667 CrossrefGoogle Scholar

  • [38] Lawrence N., Seeger M. and Herbrich R., “Fast Sparse Gaussian Process Methods: The Informative Vector Machine,” Proceedings of the 16th Annual Conference on Neural Information Processing Systems, MIT Press, Cambridge, MA, 2003, pp. 609–616. Google Scholar

  • [39] Brand M., “Pattern Discovery via Entropy Minimization,” MERL—A Mitshubishi Electric Research Lab. TR-98-21, Cambridge, MA, 1998. Google Scholar

  • [40] Bertsimas D. and Tsitsiklis J. N., Introduction to Linear Optimization, Vol. 6, Athena Scientific, Belmont, MA, 1997, pp. 65–67. Google Scholar

  • [41] Viappiani P. and Boutilier C., “Optimal Bayesian Recommendation Sets and Myopically Optimal Choice Query Sets,” Advances in Neural Information Processing Systems 23, edited by Lafferty J., Williams C., Shawe-Taylor J., Zemel R. and Culotta A., Curran Associates, Red Hood, NY, 2010, pp. 2352–2360. Google Scholar

  • [42] Rice J., Mathematical Statistics and Data Analysis, Cengage Learning, Boston, 2006, pp. 279–285. Google Scholar

  • [43] Bradley R. A. and Terry M. E., “Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons,” Biometrika, Vol. 39, Nos. 3–4, 1952, pp. 324–345. doi:https://doi.org/10.2307/2334029 CrossrefGoogle Scholar

  • [44] Boutilier C., Patrascu R., Poupart P. and Schuurmans D., “Constraint-Based Optimization and Utility Elicitation Using the Minimax Decision Criterion,” Artificial Intelligence, Vol. 170, No. 8, 2006, pp. 686–713. doi:https://doi.org/10.1016/j.artint.2006.02.003 AINTBB 0004-3702 CrossrefGoogle Scholar

  • [45] Kochenderfer M. J., Holland J. and Chryssanthacopoulos J., “Next-Generation Airborne Collision Avoidance System,” Lincoln Laboratory Journal, Vol. 19, No. 1, 2012, pp. 17–33. Google Scholar

  • [46] Kochenderfer M. J., Chryssanthacopoulos J. P. and Weibel R. E., “A New Approach for Designing Safer Collision Avoidance Systems,” Air Traffic Control Quarterly, Vol. 20, No. 1, 2012, p. 27. LinkGoogle Scholar

  • [47] Kochenderfer M. J. and Chryssanthacopoulos J., “Robust Airborne Collision Avoidance Through Dynamic Programming,” Massachusetts Inst. of Technology Rept.  ATC-371, Lincoln Lab., Lexington, MA, 2011. Google Scholar

  • [48] Bertsekas D. P., Dynamic Programming and Optimal Control, Vol. 1, Athena Scientific, Belmont, MA, 1995. Google Scholar

  • [49] Russell S. and Norvig P., Artificial Intelligence: A Modern Approach, Prentice–Hall, Englewood Cliffs, NJ, 1995, pp. 645–679. Google Scholar

  • [50] Smith K., “Collision Avoidance System Optimization for Closely Spaced Parallel Operations Through Surrogate Modeling,” M.S. Thesis, Massachusetts Inst. of Technology, Cambridge, MA, 2013. LinkGoogle Scholar

  • [51] Regan K. and Boutilier C., “Robust Policy Computation in Reward-Uncertain MDPs Using Nondominated Policies,” Association for the Advancement of Artificial Intelligence, 2010. Google Scholar

  • [52] Chatterjee K., Majumdar R. and Henzinger T. A., “Markov Decision Processes with Multiple Objectives,” Symposium on Theoretical Aspects of Computer Science, Springer, New York, 2006, pp. 325–336. CrossrefGoogle Scholar

  • [53] Roijers D. M., Scharpff J., Spaan M., Oliehoek F. A., De Weerdt M. and Whiteson S., “Bounded Approximations for Linear Multi-Objective Planning Under Uncertainty,” International Conference on Autonomous Planning and Scheduling, Assoc. for the Advancement of Artificial Intelligence Press, Palo Alto, CA, 2014, pp. 262–270. Google Scholar

  • [54] van Laarhoven P. J. and Aarts E. H., “Simulated Annealing,” Simulated Annealing: Theory and Applications of Mathematics and Its Applications, Vol. 37, Springer, New York, 1987, pp. 7–15. CrossrefGoogle Scholar

  • [55] Sivanandam S. and Deepa S., Genetic Algorithm Optimization Problems, Springer, New York, 2008. CrossrefGoogle Scholar

  • [56] Poli R., Kennedy J. and Blackwell T., “Particle Swarm Optimization,” Swarm Intelligence, Vol. 1, No. 1, 2007, pp. 33–57. doi:https://doi.org/10.1007/s11721-007-0002-0 CrossrefGoogle Scholar

  • [57] Bagnoli M. and Bergstrom T., “Log-Concave Probability and Its Applications,” Economic Theory, Vol. 26, No. 2, 2005, pp. 445–469. doi:https://doi.org/10.1007/s00199-004-0514-4 ECTHEA CrossrefGoogle Scholar

  • [58] Prékopa A., “On Logarithmic Concave Measures and Functions,” Acta Scientiarum Mathematicarum, Vol. 34, June 1973, pp. 335–343. Google Scholar

Previous article
Next article