Simulated annealing for optimization
显示 更早的评论
Hello everyone,
i have a question to simulated annealing. I want to use it to solve a quadratic asignment problem (QAP) because it is very large and it takes to long to solve it with an exact algorithm. Is it possible to solve a QAP with simulated annealing ?
And how can I solve it with constraints like 
or 
. I can just give the algorithm a start value and a lower bound / upper bound.
or . I can just give the algorithm a start value and a lower bound / upper bound. Can please someone help me ?
Best regards !
回答（1 个）
Walter Roberson
2019-5-22
1 个投票
Generally speaking, simulated annealing can be used to solve QAP, but it would likely be much much slower than a routine designed for solving QAP.
simulannealbnd supports bounds constraints, but no other kinds of constraints, and it does not support anything like event functions that might provide constraints. You would therefore need to code the constraints as a penalty, which is always risky because the routines do not know to avoid penalty areas.
Simulated Annealing is a slow process. You would probably be better off with patternsearch()
4 个评论
Kernel7364
2019-5-22
Walter Roberson
2019-5-23
simmulannealbnd might not be bad for finding an approximate solution, but it is likely to take a long time to find the global minima.
The theory of simmulated annealing says that it is the only minimizer that can find the global minima of arbitrarily hard problems, provided it is given enough time and a slow enough temperature schedule. I have my doubts though: I suspect it might be more like the situation with random walks, which in 3 or more dimensions are not certain to reach any given point (indeed, random walk theory says that the probability that any given point will be reached in infinite time decreases rapidly as the number of dimensions increases.)
WIth the problem as described, it is not clear why you do not simply use Round Robin scheduling -- or if the trains have variable dwell time, then LRU (Least Recently Used).
Kernel7364
2019-5-23
Thank you so much for your quick response again.
Your advices are really helpful for me. I will try different heuristic algorithm to find a good solution. After that I will compare the results and the times what they needed to find a solution.
Since I read in so many papers that Simmulated annealing is the best to find an approximate solution to my problem, I focused my study on that algorithm but I will definately try out the other ones too.
But I have one more question to the function simmulannealbnd.
how is it possible to set constraints like 
in that algorithm ?
in that algorithm ?In the link you gave me are just constraints for the upper bound and lower bound but since I have a QAP I also have constraints that for example 
.
.That basicly means that every train has to be assigned to exactly one platform. And furthermore I have to give that algorithm the arrival and departure time that Matlab knows when a platform is available again after one train left the trainstation.
How is it possible to set this constraints. I could not find it in the link you gave me.
Sorry if some of my questions are silly, I am just a beginner with Matlab.
Thanks for your help !
Walter Roberson
2019-5-23
I already told you that it is not possible to set constraints with simmulannealbnd . All you can do is add a penalty when the constraint is violated. However when you use penalties, you have to plan them carefully. For example if you return 1000000 when the constraint is violated, then SA would be happy to try to search for a location that returned only 999999.99999 instead of understanding that the area is to be denied.
类别
在 帮助中心 和 File Exchange 中查找有关 Simulated Annealing 的更多信息
产品
2019-5-22
2019-5-23
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
