Introduction to L. Minku
Optimisation Problems
Optimisation problems: to find a solution that minimises/ Maximisation / minimisation problems.
Copyright By PowCoder代写 加微信 powcoder
maximises one or more pre-defined objective functions.
There may be some constraints that must or should be
satisfied for a given solution to be feasible.
Optimisation Algorithms from Artificial Intelligence
Solutions do not correspond to paths built step by step from
an initial to a goal state.
Instead, the algorithms typically maintain whole candidate Candidate solutions may be feasible or infeasible.
solutions from the beginning.
Routing Problem
118 Timisoara
99 Fagaras
80 Rimnicu
211 Bucharest
Example of infeasible candidate solution:
[Oradea, Zerind, Arad, Timisoara] (does not reach the destination)
Example of infeasible candidate solution:
[Oradea, Rimnicu, Mehadia, Bucharest] (moves to non-neighbouring cities)
Example of feasible candidate solution:
[Oradea, Sibiu, Fagaras, Bucharest]
(non-optimal solution that takes the agent from the origin to the destination)
Optimal solution:
[Oradea, Sibiu, Rimnicu, Pitesti, Bucharest]
Routing Problem
146 Mehadia
Routing problem:
Examples of Optimisation Problems
Given a motorway map
containing N cities.
Zerind • The map shows the 75
distance between Arad connected cities. 118 We have a city of origin Timisoara and a city of destination.
Problem: find a path from the origin to the destination that minimises the distance travelled, while ensuring that direct paths between non- neighbouring cities are not used.
Search and Optimisation
In search, we are interested in searching for a goal state.
In optimisation, we are interested in searching for an optimal solution.
As many search problems have a cost associated to actions, they can also be formulated as optimisation problems.
Similarly, optimisation problems can frequently be formulated as
search problems associated to a cost function.
Many search algorithms will “search” for optimal solutions (see A* as
an example).
Optimisation algorithms may also be used to solve search problems
if they can be associated to an appropriate function to be optimised.
Advantages:
They do not maintain alternative paths to solutions.
Can potentially be more time efficient, depending on the algorithm. Do not necessarily require problem-specific heuristics.
Artificial Intelligence Optimisation Algorithms
Usually more space efficient, frequently requiring the same amount of space
from the beginning to the end of the optimisation process.
Frequently able to find reasonable solutions for problems with large state
spaces, for which the tree-based search algorithms are unsuitable.
Weaknesses:
Not guaranteed to retrieve the optimal solution in a reasonable amount of time.
Applicability:
Can be used for any problem that can be formulated as an optimisation problem.
Depending on the problem formulation and operators, not guaranteed to be
complete either.
Photo from: http://maritime-connector.com/images/container-ship-16-wiki-19057.jpg
Examples of Optimisation Problems
Bin packing problem:
Given bins with maximum volume V, which cannot be exceeded.
We have n items to pack, each with a volume v.
We must pack all items.
Problem: find an assignment of items to bins that minimises the number of bins used, ensuring that all items are packed and the volume of the bins is not exceeded.
Photo from: http://www.tscargo.ca/images/cargo1.jpg
Examples of Software Engineering Optimisation Problems
Software Project Scheduling:
Given E employees and T tasks.
Each task requires an effort in hours and certain skills. Each employee has a salary, a set of skills and can work a maximum number of hours. Tasks have precedence relationships.
Problem: find an allocation of employees to tasks that minimises the cost and the duration of the software project, while ensuring that employees are only assigned to tasks for which they have the required skills, that they work only up to a maximum number of hours, and that the task precedences are respected.
Examples of Optimisation Problems
Hyperparameter optimisation:
algorithm.
Some hyperparameters may be continuous, e.g., learning rate.
Some hyperparameters may be categorical or ordinal, e.g., activation function.
Consider the hyperparameters
of a machine learning
Problem: find the hyperparameter values that minimise the error on the validation set.
Examples of Optimisation Problems
Some machine learning algorithms have models that take the form of functions of a pre-defined form.
These functions are described by parameters, e.g., the weights of a neural networks.
Problem: find the parameter values that minimise the loss calculated based on the training set.
Learning vs Optimisation
From an algorithmic perspective, learning can be seen as We can compute the loss based on the training set.
finding parameters that minimise a loss function.
Learning vs Optimisation
From a problem perspective, the goal of machine learning is to create
models able to generalise to unseen data.
In supervised learning, we want to minimise the expected loss, i.e.,
the loss considering all possible examples, including those that we have not observed yet.
We cannot calculate the loss based on unseen data during training
So, learning can be essentially seen as trying to optimise a function
that cannot be computed.
Therefore, our algorithms may calculate the loss based on the
training set, and design a loss function that includes, e.g., a regularisation term, in an attempt to generalise well to unseen data.
Learning vs Optimisation
From a problem perspective, optimisation usually really wants to minimise (or maximise) the value of a given (known) objective function.
In that sense, learning and optimisation are different.
However, there will be some optimisation problems where we can’t compute the exact function to be optimised, causing the distinction between learning and optimisation to become more blurry.
Optimisation problems are problems where we want to minimise (or maximise) one or more objective functions, possibly subject to certain constraints.
Optimisation algorithms can often find good solutions in a reasonable amount of time, but are typically not guaranteed to find optimal solutions in a reasonable amount of time.
Next How to formulate optimisation problems.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com