[AIM] Introduction

Day 0

Content

  • Definitions: Decision, Decision Making, Decision Support, Models
  • Decision Making/Modeling Process
  • Combinatorial Optimisation
  • Heuristic Search
  • Search Paradigms
  • Pseudo-random Numbers

Defintion

A decision is defined as the choice of one among a number of alternatives.
Decision Making is the process of choosing among alternative courses of action for the purpose of attaining a goal or goals. Every decision making process produces a final choice. The output can be an action or an opinion of choice.
The term Decision support is used often and in a variety of contexts related to decision making.

System

  • Degree of independence of system
    • Closed systems are totally independent
    • Open systems dependent on their environment
  • Evaluations of systems
    • System effectiveness: the degree to which goals are achieved, i.e. result, output
    • System efficiency: a measure of the use of input(or resources) to achieve outputs, e.g. speed

Models

  • Major characteristic of decision support systems is that it includes at least one model
  • A model is a simplified representation or abstraction of reality
    • Reality is usually too complex
    • Much of complexity is irrelevant to solving the problem

Types of Models

  • Iconic Models
    • Least abstract - a physical replica of a system : e.g., 3D car
  • Analog models
    • More abstract - a symbolic representation of reality
    • Behaves like the real system but does not look like it: e.g., 2D charts
  • Mathematical Models
    • Most abstract - mathematical relationships in the problem
    • Easy to model than manipulating real system
    • Low cost of the analysis
    • Cost of making mistakes is less than mistakes on real system
    • Can model risk and uncertainty
    • A very large number of solutions can be analysed

Global Optimisation

Global optimisation is the task of finding the absolutely best set of admissible conditions to achieve your objective, formulated in mathematical terms.

Heuristic

A heuristic is a rule of thumb method derived from human intuition.
  • A heuristic is a search method which seeks good, i.e. near-optimal solutions, at a reasonable cost without being able to guarantee optimality.
  • Good for solving ill-structured problems, or complex well-structured problems (large-scale combinatorial problems that have many potential solutions to explore)
enter image description here
Systematic: BFS, DFS, IDS, Best-First, A*. Always complete for finite search spaces, some versions complete for infinite spaces.
Local Search: A local search algorithm starts from a candidate solution and then iteratively moves to a neighbor solution.

Search Paradigms

  • Single point based search vs. Multi-point based search
  • Constructive: partial candidate solutions(starts from empty solution)
  • Perturbative: complete solutions
You should be able to understand some simple problems:

Example- Bin Packing Problem

If we apply bin packing using branch and bound algorithms, it will get optimal solution but the time is waste. If we use a heuristic solution, we can use largest item first fit.
It is a systematic/Deterministic/Constructive heuristic.

Classroom Assignment and Graph Colouring

For the classroom assignment problem, there must be some constraints. We represent the problem using a graph:
  • Vertices: meetings/classes
  • Edges: constraints. If there are constraints between two vertices, connect them with edges.
  • Degree of a vertex: number of edges connected to that vertex
  • Saturation degree of a vertex: number of differently coloured vertices already connected to it.
  • enter image description here

Graph colouring heuristic

Step 1: Arrange the vertices in decreasing order of their degree
Step 2: Colour a vertex of maximal degree with colour #1
Step 3: Choose an uncoloured vertex with maximal saturation degree. If there is a tie choose any of it
Step 4: Colour the selected vertex using the colour with lowest possible number(#)
Step 5: If all vertex are coloured then STOP else go to step 3
enter image description here

TSP

Number of configurations to search from is N!, so it is hard to use systematic approach.
  • The nearest neighbourhood (NN) algorithm
    • Constructive (Deterministic and Systematic)
  • Pairwise exchange (2-opt) or LinKernighan heuristics
    • Perturbative (Stochastic and Local Search)
  • There is no guarantee for the optimality of the obtained solutions
  • Usually can be used only for the specific situation for which they are designed
  • Often, heuristics have some parameters
    • Performance of a heuristic could be sensitive to the setting of those parameters
  • May give a poor solution

Pseudo-random numbers

  • Numbers that are produced using a deterministic process but which appear to be random
  • Note that most computers produce pseudo-random numbers

Some problems with pseudo-random numbers

  • Shorter than expected periods for some seed states
  • Lack of uniformity of distribution
  • Correlation of successive values
  • Poor dimensional distribution of the output sequence
One early method is Middle Square Method:
  • Starts with an initial value (seed) (2156)
  • Takes its square (\(2156^2\) = 04\(\underline{6483}\) 36)
  • Middle digits are used as a random number 6483
  • Then this process is repeated: (\(6483^2\) = 42\(\underline{0292}\) 89)
  • Etc…

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t
阅读全文