这里的启发式算法一般指运筹学中解决大规模负责最优化问题的一类算法。
其实运筹学的历史长于计算机,在没有计算机或者计算机没有大规模民用的年代学者们都是用脑子和笔去解决最优化问题的,所以才有了GoMary的割平面法等运筹学方法。
虽然随着今年计算机应用技术的大力发展,低复杂度和小规模的最优化方法已经相当容易计算,但对于大规模的最优解问题仍然是学界研究的热点。比如一万个点的邮差问题,不可能只依靠计算机的运算速度求得答案。
其实从1945年启发式算法提出以来整个的发展历程十分明显:社会需要什么,学者们就研究什么。需要一套有效求解最优解的算法,于是又了单纯型法;需要解决整数规划,于是有了分支定界法;需要解决大范围内最优解,于是有了局部搜索;范围再大一点,就有了禁忌搜索;范围内分布不均匀,于是模拟退火啊、遗传啊、最速下山啊等等等等算法都冒了出来。
再以后学者对效果还不满意,琢磨怎么模拟人类大脑,于是神经网络就被发明了出来;觉得世界不是那么的统一,于是模糊系统被提了出来;认为以上的研究都太单调,于是把所有的算法仍一起搅一搅,混合系统也被发明…..
人类一思考,上帝就发笑。
上帝笑不笑咱不清楚,不过有意思的是经过如此多的尝试加上近几十年计算机性能的突飞猛进,到目前还是没有一个可靠的、有效的、适用性广泛的算法,来解决日常生活中的大规模最优化问题。
但无疑,启发式算法在这个发展迅速的世界显得越来越重要。
如果对启发式算法的发展历程感兴趣,那么下面的paper应该可以帮到您。
The Growing Importance of Heuristics
Heuristics is a loanword from Greek, means find or discover the solution of the optimal problem. Although this theory has a short of history from its offered (Polya 1945), however, it growing and improved quickly around recent half century. The reason why a new technices could deal large amount of problems is that it was an experienced based on algorithm.
As we known, the real-world problems are difficult to solved for several reasons. For example, the search space is so large to forbid an efficient search , the problem is so complicated that just to facilitate any answer or the evaluation function was noisy with time. Even through, researchers are never giving up trying to find methods to approach the real world.
Some of traditional methods, like enumerating, work well under several of acceptable assumptions in these aspects. However, the search space was larger, exhaustive search will be less effective. Local search will be helpful on that conditions. If the question could be model as linear programming, simplex method could bring complete solutions.
If the problem has both complicated attibute and large search area, the greedy algorithm could get the partial solution. Divide and conquer the search area was a good idea , just like branch and bound method(Madsen & Zertchaninov 1998).
But none of these methods were robust, which means when the problems changed the model must change too. And more importantly, these algorithms sometimes get the local optimal solutions, but not the global optimal solutions we wanted. So, for a real-world problem, we need find other tools.
When we change our focus from global to local optima, simulated annealing and tabu search join into our discuss. Both of them were designed for escaping local optima. Tabu search searching only make uphill moves at local optima but simulated annealing moves any times. By that moving or jumping, we have more opportunity to get a solution better than local optima.
Both of those heuristic methods return the same solution or different solutions based on initial configuration. But the real world was changes continually, a continually changing and similarities across fingerprints methods were necessary.
Evolutionary approach methods, including a series models, was researching as early as 1950s(Fogel 1998). Genetic programming and classifier systems were the represent of earlier methods. The model could adjust themselves by feedback to match the data more accurately. Mathematical model are closing to real world step by step. Additionally, some of real-world problems need lots of solutions but not only one of them. Evolutionary approach can do all that things well.
The effectiveness of an evolutionary approach methods relay on lots of its components and interactions. For example, the methods was lower efficient if the infeasible area was sufficiently large than feasible area. Recently, a series of research shows that self-adaptive methods were useful to improve evolutionary approach results(Angeline et al. 1997; Vavak et al. 1997).
That is not enough, fuzzy systems are developing to let some of heuristic methods more accurately or more close to the real world(GEORGE J. & BO 2008; Yager & Filev 1994). Hybrid systems are used to combine an evolutionary method with a traditional method to make a search process high efficients.
Now we have several of heuristics models could approach the optimal results we want. There are two important propose to evaluate a heuristics searching technique, exploiting the best solutions and exploring the search space at the same time(Michalewicz & Fogel 2004). This balance was researching from as early as the 1950s (Box 1954), and conclusion recent decades as there’s no way to choose a single search method that can serve well in every case (Fogel & Ghozeil 1997; Wolpert & Macready 1997).
Moreover, researcher brings the neural networks theory trying to simulate human brains functions to solve problems. Growing computer technologies are useful on that area. Neural networks offer functions that can be simulate almost any real-world demands. We just training the model and it could find a feasible solution rapidly. However, according to reference, the large the network is ,the more potential error will be contain in that(Haykin 1994).
As we seen above, the real-world problem is usually associated by a large amount of little problems or parameters. And the heuristic methods are growing follow the problem and show its importance. However, the real world full of noise, it is hard to use a simple or even closed-form mathematical procedure to modeling it. The point is to anticipate a problem and adapt our solution so as to best handle the possibilities that we might face (Michalewicz & Fogel 2004).
—
Reference
Angeline, P.J. et al., 1997. Evolutionary Programming VI P. J. Angeline et al., eds., Berlin/Heidelberg: Springer-Verlag. Available at: http://www.springerlink.com/index/10.1007/BFb0014795 [Accessed March 12, 2014].
Box, G.E.P., 1954. The Exploration and Exploitation of Response Surfaces: Some General Considerations and Examples. Biometrics, 10(1), p.16. Available at: http://www.jstor.org/stable/3001663?origin=crossref [Accessed March 11, 2014].
Fogel, D.B., 1998. Evolutionary Computation: The Fossil Record. Available at: http://dl.acm.org/citation.cfm?id=521840 [Accessed March 12, 2014].
Fogel, D.B. & Ghozeil, A., 1997. A note on representations and variation operators. IEEE Transactions on Evolutionary Computation, 1(2), pp.159–161. Available at: http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=687882 [Accessed March 11, 2014].
GEORGE J., K. & BO, Y., 2008. FUZZY SETS AND FUZZY LOGIC, THEORY AND APPLICATIONS. –. Available at: http://digilib.uin-suka.ac.id/7049/1/FUZZY SETS AND FUZZY LOGIC Theory and Applications – GEORGE J. KLIR %2C BO YUAN.pdf [Accessed March 13, 2014].
Haykin, S., 1994. Neural Networks: A Comprehensive Foundation [Hardcover], Macmillan Coll Div. Available at: http://www.amazon.com/Neural-Networks-A-Comprehensive-Foundation/dp/0023527617/ref=sr_1_1?ie=UTF8&qid=1394617536&sr=8-1&keywords=Neural+networks%3A+A+comprehensive+foundation [Accessed March 12, 2014].
Madsen, K. & Zertchaninov, S., 1998. A new branch-and-bound method for global optimization D. of M. Modelling, ed., Technical Universityof Denmark. Available at: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.8197&rep=rep1&type=pdf [Accessed March 12, 2014].
Michalewicz, Z. & Fogel, D.B., 2004. How to solve it: modern heuristics, Springer.
Polya, G., 1945. How to Solve It: A New Aspect of Mathematical Method, Princeton university press.
Vavak, F., Jukes, K. & Fogarty, T.C., 1997. Learning the local search range for genetic optimisation in nonstationary environments. In Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC ’97). IEEE, pp. 355–360. Available at: http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=592335 [Accessed March 12, 2014].
Wolpert, D.H. & Macready, W.G., 1997. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), pp.67–82. Available at: http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=585893 [Accessed January 27, 2014].
Yager, R.R. & Filev, D.P., 1994. Essentials of Fuzzy Modeling and Control. Available at: http://dl.acm.org/citation.cfm?id=561534 [Accessed March 13, 2014].
本文遵守署名-非营利性使用-相同方式共享协议,转载请保留本段:冰丝带雨 » 日益重要的启发式算法