lecture.txt

模拟退火算法求解TSP问题.求解TSP问题的模拟退火算法

Good afternoon, everyone here.
I'm glad to stay here to give a lecture.
Let's see my introduction and some key words in the lecture.

I'm Hu Botao in Fuzhou No.1 middle school.
My interest is extensive. /iks'densiv/
I often do some researches of infor'matics /and mathematic model.
Let's turn to my topic.

My subject /a/ /e/ is "The applications of simulated annealing/ for logistics".

This is the index /e/ of my lecture.

In the economy /iconemi/, the logistics have an important state.
Because the problems in logistics usually have so many conditions, they are very complex to solve.

In logistics, there are many problems of the combination optimization /optimaizeition/.
Traveling salesman problem is a typical/i/ and useful problem in them.
We call it TSP for short.

Look at this flash. 
This is the map of the USA /rigen/. The capital letters in the map means the cities.
There is one way between any two cities.

A salesman transports the products /to all the cities in this map.
The salesman visits each city once and only once, and returns to the starting city.
Of course, he wants to find the shortest route to transport /in order to reduce the cost.
This is a route to transport.
It's A to C to D to G to B to F to E /and back to A , with the total distance about 30 length units.
but it's not the shortest.
This is another route which is better than the one before.
It's A to C to D to G to F to E to B /and back to A , with the total distance about 20 length units.
In fact /it's the shortest route for this map.

Abstracting the problem /in mathematic model, the problem is to get the minimum /of the route cost function.
There are huge /hjug/ amounts of routes to choose. But which one is the shortest? Namely, how to minimize the function /in a quick way?
The traditional way is to search all the cases, but it's too slow.
I design an algorithm called Simulate Annealing /to minimize the function. 
SA is the short name for it. 
Notice the function of the problem is so complex.

The thought of SA comes from a nature rule that /"the substance always closes to the lowest energy."

SA simulates cooling the solid /which is a behavior of physical process.
At first /the solid is at a high temperature, namely has a high energy.
With the solid cooling, its energy is getting lower and lower.
At last, the solid reaches the lowest energy / at the normal temperature.
The process of cooling is known as annealing.

Attention to the lowest energy state that ./has certain similarity to the minimum of the function!
It's an important discovery, which is just my creation point.
That's why SA can get the near minimum of the function.

Because of the time limit, I jump over introducing the detail of SA.

I wrote this program to solve TSP using SA.

At first the route is very bad. We can see the route is getting better and better using SA
Now I change some value, and try again. See this time the length of the route is much shorter than that before.

SA have some excellences: /'ekselensis/
First, efficiency: /i'fishenci/
The rate of the value of the solution and the used time / is quite higher than /getting the real minimum in traditional way.
Time is money.
I think SA satisfies this rule for the modern market.
Second, expandability:
It's a general algorithm to solve the problems in logistics, not only TSP.
It can be also combined with the other algorithm /for concrete problems.

At last/let's review my creation point: 
First, SA simulates the natrue to get the minimum of the function.
Second, SA is very efficient/ifishen/ for logistics in modern markets.


Thank you.


Question:
Q1:Please tell me some other problems in logistcs, which we can solve them, using SA.

Q2:You mentioned a nature rules. I want to know what it is.
It's "The substance always closes to the lowest energy."
For example:
The river always goes to the lower height.
The thing at a high temperature always goes to the lower temperature.

Q3:Why you 
For making the lecture simple, I jumped over it.

For example, the river always goes to the lower height, namely the lower energy state.
The lowest energy state is similar to the minimum of the function.
It's just my creation point.

Q2:I want to know how your method works.

Thank you for your question.
Here it is the detail of the algorithm.
Because of the time limit, I jump over the pager to show how SA works.
The thought of SA mainly is to do loop 
/containing generating the new solution and determining if accept it 
/by certain decreasing probability 
until the temperature closes to 0.
I'm sorry it's hard to explain the detail to you in little time.
If you want to know more, you can see my article.

Q3:Is TSP the application of the fact? 

Yes. TSP is only an example to show how SA works.
the TSP is 
For example:
Dynamic TSP. 
Namely the ways between the cites is not static.
In other words, maybe the traffic in the way between certain two cities is very busy and so on.