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).
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].