OPTIMIZATION USING
CONCEPT OF
SIMULATED ANNEALING
Optimisation with Spreadsheet
GROUP 6:
OM SHUBHAM (PGP/26/397)
PAARISHA SAINI (PGP/26/398)
SHRIYA TIWARI (PGP/26/411)
SIMRAN KERNI (PGP/26/412)
INTRODUCTION
Simulated Annealing (SA) is a stochastic
optimization method used for the
optimization of an objective function. The
global extreme of the function with local
minimums can then be determined using
this method. SA is based on an analogy
with statistical mechanics and, in
particular, with solid-state physics
elements.
A practical example can be drawn from
metallurgy: what happens to the atomic
structure of the body when it is rapidly
cooled and its temperature is lowered? A The name of the method is derived from
sudden drop in temperature could result simulations of thermal annealing of critically
in the system having a non-symmetric heated solids.
structure, or, to put it another way, a
non-optimal state.
Imagine you are currently occupying one
of the spots above. You put a ping-pong
ball in the area with the objective of
moving it to the lowest possible position
(as depicted below). Gravity causes the
ball to naturally roll downhill, although it
may occasionally get trapped. When a
ping-pong ball gets stuck, the natural
reaction is to shake the area to dislodge
it and enable it to continue rolling
downhill. Simulated annealing is a
heuristic search technique, which means
that it seeks to discover a solution that is
"near enough."
ALGORITHM
Simulated annealing searching for a maximum. The objective here is to get to the
highest point. In this example, it is not enough to use a simple hill climb algorithm,
as there are many local maxima. By cooling the temperature slowly the global
maximum is found.ear your teammates talk and that they hear you clearly as well.
THE SHORTEST ROUTE DETERMINATION BETWEEN
BELARUSIAN DAIRY COMPANIES
One of the biggest companies is
"Concern Brestmiasomolprom," which
manages State Association Holding. in
the Republic of Belarus's dairy and
meat sectors.
The concern's businesses have
amassed a substantial manufacturing
of meat and dairy products for many
years.
The group consists of 8 dairy
companies as shown in figure 3 with
their corresponding GPS coordinates.
THE SHORTEST ROUTE DETERMINATION BETWEEN
BELARUSIAN DAIRY COMPANIES
A research was done to determine the shortest path
between the specified items for logistical reasons. There
was a need to find the shortest path between 8
Belarusian cities using the SA technique to complete the
TSP-8 job.
The Travelling Salesman problem using simulated
annealing :
Problem : TSP task is to find the minimum route between
N cities - visiting each city only once and in the end
returning to the departure city
THE SHORTEST ROUTE DETERMINATION BETWEEN
BELARUSIAN DAIRY COMPANIES
Steps invlolved in solving the problem using simulated annealing :
Let f(x) be the objective function which denotes the
total length of path we have selected for current set
x (eg for n = 5, x can be {1,2,3,4,5,1} )
Set initial Temperature to the maximum temperature
and set the values for rate of temperature used to
reduce T slowly over consecutive iterations, set value
of number of iterations for inner loop
Generate randomly the initial solution X0 and
compute f(X0) corresponding to that)
For each loop, generate new solution X' (randomly
generated cyclic permutation) and compute f(X')
THE SHORTEST ROUTE DETERMINATION BETWEEN
BELARUSIAN DAIRY COMPANIES
Steps invlolved in solving the problem using simulated annealing :
Calculate difference in objective function values, D = f(X') - f(X0)
If the difference (D) is less than zero, then we will accept the new
solution X0=X' and new minimum value of objective function
becomes f(X')
If above criteria doesn't satisfy we will check another condition
known as the Metropolis rule which state if exp(-D/T) > r, where r is
a random number between 0 and 1, we will accept the X'.
Otherwise we will move to next iteration, after the set number of
iterations we will move to new temperature set according the rate
we decided initially.
If T reached less than minimum temperature we end the process.
Simulated Annealing in action
THE SHORTEST ROUTE DETERMINATION BETWEEN
BELARUSIAN DAIRY COMPANIES
APPLICATION OF SIMULATED ANNEALING IN TEXTILES
Simulated algorithm is used for engineering
design of woven fabrics with minimum
manufacturing cost and requisite quality. In
order to minimize the fabric areal density (GSM)
while meeting the inequality criteria of the fabric
tensile, bending, and shear properties as well as
the equality constraint of crimp balancing, an
optimization problem was developed.
It is solved by finding the optimum values of
yarn counts, crimps and thread spacing for
production of light, medium and heavy weight
cotton fabrics.
APPLICATION OF SIMULATED ANNEALING IN TEXTILES
Here we have design cotton yarn with predefined strength by
optimal selection of raw materials. There was a model of yarn
strength developed by Zurek and Frydrynch used for formulation
of optimization problem.
The following optimization problem was formulated for 20 tex
combed cotton yarn:
APPLICATION OF SIMULATED ANNEALING IN TEXTILES
Simulated annealing was used to solve the
optimization problem in order to obtain the
predefined yarn strength by searching the
optimum values of cotton fiber parameters
such as linear density , breaking strain ,
breaking stress, and mean length, as well as
yarn twist/meter. The values of initial
temperature T, minimum temperature Tmin,
cooling rate CT , and number of iterations at
each temperature n for the simulated
annealing algorithm were set to 1,000; 0.0001;
0.9; and 500, respectively.
APPLICATION OF SIMULATED ANNEALING IN TEXTILES
Table 1 shows the lower
and upper boundaries of
the variables.
Table 2 illustrates the
optimum combination of
fiber properties and
twist/meter for the
production of 20 tex
yarns with target
strength of 20 gf/tex. The
value of yarn strength
with the optimized
parameters was
obtained as 19.97 gf/tex.
CONCLUSION
ADVANTAGES
Simulated annealing is easy to code and use and
is easily applicable to a large number of
problems.
It can deal with noisy data and highly non-linear
models.
The ignorant search algorithm performs searches.
An ordered space tree (depth first, breadth first)
or depth-first iteration) to seek for the answer
In addition, it may provide good outcomes with a
small number of iterations, making it suited for
real-time control.
It does not rely on restrictive properties of the
model and hence is versatile
LIMITATIONS
However, for bigger search spaces there is the
issue of combinatorial explosion that renders
search impossible, the answer generated by
ignorant algorithms Each of these It takes
exponential time for algorithms to solve issues.
A lot of parameters have to be tuned as it is
metaheuristic.
The precision of the numbers used in its
implementation has a significant effect on the
quality of results.
There is a tradeoff between the quality of result
and the time taken for the algorithm to run.
Results are generally not reproducible;another run
can give a different result.
Thank
you!!
