Image from: http://www.kirkk.com/modularity/wp-content/uploads/2009/12/EncapsulatingDesign1.jpg
Example of Hill Climbing Application: Software Module Clustering (Algorithmic Design)
Image from: http://www.turingfinance.com/wp-content/uploads/2015/05/Annealing.jpg
Copyright By PowCoder代写 加微信 powcoder
Design Variable
Design variable: allocation of units into modules.
Consider that we have N units, identified by natural numbers in {1,2,…,N}.
This means that we have at most N modules.
• Our design variable is a list L of N modules, where each module Li, i ∈ {1,2,…,N}, is a set containing a minimum of 0 and a maximum of N units.
L1 = {} L2 = {1}
Module 1 Module 2
L3 = {2,4,5}
unit 2 unit 5
Constraints and Objective Function
Constraints: N/A
Objective function: quality of modularisation (to be maximised).
Quality(L) = X
(maximise)
Quality(Li) i ∈ {1,2,…,N} |
Quality(Li) = (maximise)
#IntraEdgesi #IntraEdgesi + 1/2 * #InterEdgesi
Problem Formulation
Hill-Climbing (assuming maximisation)
1. current_solution = generate initial solution randomly
2. Repeat:
2.1 generate neighbour solutions (differ from current solution by a single element)
2.2 best_neighbour = get highest quality neighbour of current_solution
2.3 If quality(best_neighbour) <= quality(current_solution)
2.3.1 Return current_solution
2.4 current_solution = best_neighbour
Until a maximum number of iterations
Design variable —>
what is a candidate solution for us?
Objective —> what is quality for us?
Are there any constraints that need to be satisfied?
Designing Representation, Initialisation and Neighbourhood Operators
Hill-Climbing (assuming maximisation)
1. current_solution = generate initial solution randomly
2. Repeat:
2.1 generate neighbour solutions (differ from current solution by a single element)
2.2 best_neighbour = get highest quality neighbour of current_solution
2.3 If quality(best_neighbour) <= quality(current_solution)
2.3.1 Return current_solution
2.4 current_solution = best_neighbour
Until a maximum number of iterations
Representation:
• How to store the design variable.
Initialisation:
Neighbourhood operator:
Usually involve
E.g., boolean, integer or
float variable or array.
randomness.
How to generate
neighbour solutions.
Representation
How to represent the design variable internally in the implementation?
E.g., list of N modules, where each module is a list of
integers in {1,2,...,N} identifying the existing units.
Module 1 Module 2 Module 3 Module 4
unit 2 unit 5
E.g., if we have N=5, a possible allocation is L = {{},{1},{2,4,5},{},{3}}.
Representation
How to represent the design variable internally in the implementation?
E.g., matrix ANxN, where Aij = 1 if unit j is in module i, and 0
otherwise.
unit 2 unit 5
0 00 00 1 00 00 0 10 11 0 00 00 0 01 00
Initialisation
E.g.: place each unit into a randomly picked module.
For each unit u ∈ {1,...,N}
Add u to a module Li, where i~U{1,N}
unit 1 unit 3
unit 2 unit 4
Module 1 Module 2 Module 3
L = {{},{1},,},},{3,}{,}{,}{,}2}{,}{}{}2,}{},}{}4}},5} }}
Neighbourhood Operator
A neighbour in the software module clustering problem would be a solution where a single unit moves from one module to another. E.g.:
What would be a possible neighbourhood operator for the
software clustering problem?
L = {{},{1},{2,4,5},{},{3}}
L = {{},{1,5},{2,4},{},{3}}
Module 1 Module 2 Module 3
unit 2 unit 5
Neighbourhood
Real world problems will frequently have more than two
neighbours for each candidate solution.
How many neighbours do we have for the candidate solution
below, if we allow for equivalent neighbours?
Module 1 Module 2 Module 3 Module 4
unit 2 unit 5
5 units * 4 possible modules to move to = 20
Neighbourhood
How many neighbours do we have for the candidate solution
below, if we allow for equivalent neighbours?
1 Module 2
unit 2 unit 5
Some neighbours will be equivalent. Duplicates could be eliminated.
Neighbourhood
How many neighbours do we have for the candidate solution
below, if we allow for equivalent neighbours?
For i ∈ {1,...,N} // module
For j ∈ {1,...,size(Li)} // unit within module
For i’ ∈ {1,...,N} \ i // another module L’ = clone of L
Move unit L’ij to module L’i’ Yield L’ as a neighbour
Hill Climbing
Hill-Climbing (assuming maximisation)
1. current_solution = generate initial solution randomly
2. Repeat:
2.1 generate neighbour solutions (differ from current solution by a single element)
2.2 best_neighbour = get highest quality neighbour of current_solution 2.3 If quality(best_neighbour) <= quality(current_solution)
2.3.1 Return current_solution
2.4 current_solution = best_neighbour
Until a maximum number of iterations
Simulated Annealing would also require a representation, initialisation procedure, and neighbourhood operator to solve a problem.
Software Module Clustering problem formulation. Representation, initialisation and neighbourhood operators.
Next Application of Simulated Annealing.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com