Artificial
Intelligence 2E
foundations of computational agents
The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).
4.9 Optimization
Instead of just having possible worlds satisfy constraints or not, we often have a preference relation over possible worlds, and we want a best possible world according to the preference.
An optimization problem is given
-
•
a set of variables, each with an associated domain
-
•
an objective function that maps total assignments to real numbers, and
-
•
an optimality criterion, which is typically to find a total assignment that minimizes or maximizes the objective function.
The aim is to find a total assignment that is optimal according to the optimality criterion. For concreteness, we assume that the optimality criterion is to minimize the objective function.
A constrained optimization problem is an optimization problem that also has hard constraints specifying which variable assignments are possible. The aim is to find an optimal assignment that satisfies the hard constraints.
A huge literature exists on optimization. There are many techniques for particular forms of constrained optimization problems. For example, linear programming is the class of constrained optimization where the variables are real valued, the objective function is a linear function of the variables, and the hard constraints are linear inequalities. If the problem you are interested in solving falls into one of the classes for which there are more specific algorithms, or can be transformed into one, it is generally better to use those techniques than the more general algorithms presented here.
In a constraint optimization problem, the objective function is factored into a set of soft constraints. A soft constraint has a scope that is a set of variables. The soft constraint is a function from the domains of the variables in its scope into a real number, a cost. A typical optimality criterion is to choose a total assignment that minimizes the sum of the costs of the soft constraints.
Example 4.27.
Suppose a number of delivery activities must be scheduled, similar to Example 4.9, but, instead of hard constraints, there are preferences on times for the activities. The soft constraints are costs associated with combinations of times. The aim is to find a schedule with the minimum total sum of the costs.
Suppose variables , , , and have domain , and variable
has domain .
The soft constraints are
:
Cost
1
1
5
1
2
2
1
3
2
2
1
0
2
2
4
2
3
3
:
Cost
1
1
5
1
2
2
2
1
0
2
2
4
3
1
2
3
2
0
:
Cost
1
1
3
1
2
0
2
1
2
2
2
2
3
1
2
3
2
4
Thus, the scope of is , the scope of is , and the scope of is . Suppose there are also constraints and .
Soft constraints can be added pointwise. The sum of two soft constraints is a soft constraint with scope that is the union of their scopes. The cost of any assignment to variables in the scope is the sum of the costs of the constraints being added on that assignment.
Example 4.28.
Consider functions and in the previous example.
is a function with scope , given by
:
Cost
1
1
1
10
1
1
2
7
1
2
1
2
…
…
…
…
The second value is computed as follows:
Hard constraints can be modeled as having a cost of infinity for violating a constraint. As long as the cost of an assignment is finite, it does not violate a hard constraint. An alternative is to use a large number – larger than the sum of the soft constraints could be – as the cost of violating a hard constraint. Then optimization can be used to find a solution with the fewest number of violated hard constraints and, among those, one with the lowest cost.
Optimization problems have one difficulty that goes beyond constraint satisfaction problems. It is difficult to know whether an assignment is optimal. Whereas, for a CSP, an algorithm can check whether an assignment is a solution by just considering the assignment and the constraints, in optimization problems an algorithm can only determine whether an assignment is optimal by comparing it to other assignments.
Many of the methods for solving hard constraints can be extended to optimization problems, as outlined in the following sections.