A review of representation issues and modeling challenges with influence diagrams

Since their introduction in the mid 1970s, influence diagrams have become a de facto standard for representing Bayesian decision problems. The need to represent complex problems has led to extensions of the influence diagram methodology designed to increase the ability to represent complex problems. In this paper, we review the representation issues and modeling challenges associated with influence diagrams. In particular, we look at the representation of asymmetric decision problems including conditional distribution trees, sequential decision diagrams, and sequential valuation networks. We also examine the issue of representing the sequence of decision and chance variables, and how it is done in unconstrained influence diagrams, sequential valuation networks, and sequential influence diagrams. We also discuss the use of continuous chance and decision variables, including continuous conditionally deterministic variables. Finally, we discuss some of the modeling challenges faced in representing decision problems in practice and some software that is currently available.     

Node deletion sequences in influence diagrams using genetic algorithms

Influence diagrams are powerful tools for representing and solving complex inference and decision-making problems under uncertainty. They are directed acyclic graphs with nodes and arcs that have a precise meaning. The algorithm for evaluating an influence diagram deletes nodes from the graph in a particular order given by the position of each node and its arcs with respect to the value node. In many cases, however, there is more than one possible node deletion sequence. They all lead to the optimal solution of the problem, but may involve different computational efforts, which is a primary issue when facing real-size models. Finding the optimal deletion sequence is a NP-hard problem. The proposals given in the literature have proven to require complex transformations of the influence diagram. In this paper, we present a genetic algorithm-based approach, which merely has to be added to the influence diagram evaluation algorithm we use, and whose codification is straightforward. The experiments, varying parameters like crossover and mutation operators, population sizes and mutation rates, are analysed statistically, showing favourable results over existing heuristics.     

Estimation of distribution algorithms using Gaussian Bayesian networks to solve industrial optimization problems constrained by environment variables

Many real-world optimization problems involve two different subsets of variables: decision variables, and those variables which are not present in the cost function but constrain the solutions, and thus, must be considered during optimization. Thus, dependencies between and within both subsets of variables must be considered. In this paper, an estimation of distribution algorithm (EDA) is implemented to solve this type of complex optimization problems. A Gaussian Bayesian network is used to build an abstraction model of the search space in each iteration to identify patterns among the variables. As the algorithm is initialized from data, we introduce a new hyper-parameter to control the influence of the initial data in the decisions made during the EDA execution. The results show that our algorithm improves the cost function more than the expert knowledge does.