# CS代考 Constraint Handling — Representation, Initialisation and Neighbourhood Oper – cscodehelp代写

Constraint Handling — Representation, Initialisation and Neighbourhood Operators

How to Deal with Constraints in Optimisation Problems?

Most real world problems have constraints.

Copyright By cscodehelp代写 加微信 cscodehelp

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代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com