Constraint Handling — Representation, Initialisation and Neighbourhood Operators
How to Deal with Constraints in Optimisation Problems?
Most real world problems have constraints.
Copyright By PowCoder代写 加微信 powcoder
Optimisation algorithms themselves usually do not contain Instead, strategies need to be designed for each problem.
strategies to deal with constraints.
Examples of strategies:
Representation, initialisation and neighbourhood operators. Objective function.
How to Deal with Constraints in Optimisation Problems?
Most real world problems have constraints.
Optimisation algorithms themselves usually do not contain Instead, strategies need to be designed for each problem.
strategies to deal with constraints.
Examples of strategies:
Representation, initialisation and neighbourhood operators.
Objective function.
Objective function defines the cost of a solution. (N−1 )
minimise totalDistance(x) = ∑ Dxi,xi+1 + DxN,x1 i=1
where Dj,k is the distance of the path between cities j and k. [Optional] Solutions must satisfy certain constraints.
Traveling Salesman Problem Formulation
Design variables represent a candidate solution.
• The design variable is a sequence x of N cities, where xi ∈ {1,⋯, N}, ∀i ∈ {1,⋯, N}.
The N cities to be visited are represented by values {1,…,N}.
The search space is all possible sequences of N cities, where cities are in {1,…,N}.
1, if xj = i i ∑j=1 j j 0, if xj ≠ i
∀i ∈ {1,⋯, N}, h (x) = N 1(x = i) − 1 = 0 1(x = i) =
Draw cities uniformly at random from {1,…,N} without replacement,
This ensures that there will be no missing or duplicated cities (explicit constraint) and that only cities in {1,…,N} are used (implicit constraint).
__ __ __ __ __
Designing Representation, Initialisation and Neighbourhood Operators to Deal with Constraints
Representation:
1-dimensional array of size N, where N is the number of cities to visit. The fact that the return to the initial city is not in the representation helps to deal with the implicit constraint that we must return to the city of origin.
312453 __ __ __ __ __
Initialisation:
E.g.: for N = 5 132451
__ __ __ __ __
Designing Representation, Initialisation
and Neighbourhood Operators to Deal
with Constraints
Neighbourhood operator:
Reverse the path between two randomly picked cities.
This ensures that there will be no missing or duplicated cities (explicit
constraint) and that only cities in {1,…,N} are used (implicit constraint).
13245 __ __ __ __ __
13245 __ __ __ __ __
This design ensures that the constraints are satisfied.
[Video posted by sarahbau: https://youtu.be/3TrnjUKeFg8 ]
Advantage:
Disadvantage:
May be difficult to design, and the design is problem- dependent.
Sometimes, it could restrict the search space too much, making it difficult to find the optimal solution.
Dealing with Constraints Based on Representation, Initialisation and Neighbourhood Operators
Ensure that no infeasible candidate solutions will be
generated, facilitating the search for optimal solutions.
We need to design strategies to deal with the constraints. Examples of strategies:
Representation, initialisation and neighbourhood operators.
Objective function.
Next Examples of strategies:
Representation, initialisation and neighbourhood operators.
Objective function.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com