5. Optimization & Decision-making Algorithms
Learning Objectives
Tools
Optimization Algorithms in AI
Allocation Problems
Next, you will look at a number of examples each with their own domain specific constraints and objectives.
All of the above applications can be modeled as complex problems with a vast number of possible
The exchaustive nature of the brute-force approach guarantees that it will always find the optimal solution,
Optimal Solution
Heuristic Methods
Constraint Programming
Mathematical Programming
A Working Example: Optimization for the Team-Formation Problem
Now, you will test the above function by creating a problem instance with 10 total skills, 6 workers, 5 required skills, and at most 5 skills per worker.
Given the randomized nature of the function, you will get a different problem instance every time you run this code.
The next step is to create a solver which is an optimization algorithm that can determine the smallest
Decision Making with a Brute-Force Algorithm
The following function can then be created to solve an instance
The brute-force solver is guaranteed to always find
The following code uses this function and the brute-force solver to compute the solutions for 5-worker,
Decision Making with a Greedy Heuristic Algorithm
intersection() returns a new set containing only the skills that are common to worker's worker_skills and uncovered_required_skills.
The greedy solver does not consider all possible teams and does not guarantee finding the optimal
What are the advantages and disadvantages of the brute-force and greedy algorithms for solving optimization problems?
Analyze how greedy heuristic algorithms are used to find optimal solutions in optimization problems.
You want to create a greedy solver for the optimization problem of team formation.
List three different real-world optimization problem. For each problem:
In the brute-force solver, if you increase the number of workers, how does it affect the problem in terms of number of solutions and computational time?