Minimization over randomly selected lines

This paper presents a population-based evolutionary optimization method for minimizinga given cost function. The mutation operator of this method selects randomly oriented lines in thecost function domain, constructs quadratic functions interpolating the cost function at three differentpoints over each line, and uses extrema of the quadratics as mutated points. The crossover operatormodiŞes each mutated point based on components of two points in population, instead of one point asis usually performed in other evolutionary algorithms. The stopping criterion of this method dependson the number of almost degenerate quadratics. We demonstrate that the proposed method with thesemutation and crossover operations achieves faster and more robust convergence than the well-knownDifferential Evolution and Particle Swarm algorithms.

PDF

___

[1] T¨orn, A., Global optimization. SpringerVerlag (1989).
[2] Price, K., Storn, R.M., Lampinen, J.A., Differential evolution: a practical approach to global optimization. Springer-Verlag, Berlin (2005).
[3] Tu, T.V., Sano, K., Genetic algorithm for optimization in adaptive bus signal priority control. An International Journal of Optimization and Control: Theories and Applications (IJOCTA), 3(1), 35-43 (2012).
[4] Luenberger, D.G., Ye, Y., Linear and nonlinear programming. Springer, New York (2008).
[5] Dennis, J.E., Schnabel, R.B., Numerical methods for unconstrained optimization and nonlinear equations. SIAM (1987).
[6] More, J.J., Thuente, D.J., Line se arch algorithms with guaranteed sufficient decrease. ACM Transactions on Mathematical Software, 20(3), 286-307 (1994).
[7] Mohan, C., Shanker, K., A controlled random search technique for global optimization using quadratic approximation. Asia-Pacific Journal of Operational Research, 11(1), 93- 101 (1994).
[8] Pant, M., Thangaraj, R., Singh, V.P., A new differential evolution algorithm for solving global optimization problems. International Conference on Advanced Computer Control (ICACC'09), 388-392 (2009)
[9] Storn, R., Price, K., Differential evolution a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), 341-359 (1997).
[10] Montgomery, J., Chen, S., An analysis of the operation of differential evolution at high and low crossover rates. IEEE Congress on Evolutionary Computation (CEC'2010), 1-8 (2010).
[11] Onwubolu, G., Davendra, D., Scheduling flow shops using differential evolution algorithm. European Journal of Operational Research, 171(2), 674-692 (2006).
[12] S¸ahin, ?I., Random Lines: a novel population set-based evolutionary global optimization algorithm. Genetic Programming vol. 6621, 97-107, Springer-Verlag, Berlin (2011). [13] Zielinski, K., Weitkemper, P., Laur, R.,
Kammeyer, K.-D., Examination of stopping criteria for differential evolution based on a power allocation problem. 10th International Conference on Optimization of Electrical and Electronic Equipment, Brasov, Romania (2006).
[14] Rahnamayan, S., Tizhoosh, H.R., Salama, M.M.A., Opposition-based Differential Evolution. IEEE Transactions on Evolutionary Computation, 12(1), 64-79 (2008) . [15] More, J.J., Garbow, B.S., Hillstrom, K.E., Testing unconstrained optimization software. Acm Transactions on Mathematical Software, 7(1), 17-41 (1981).
[16] Aluffipentini, F., Parisi, V., Zirilli, F., Global optimization and stochastic differential-equations. Journal of Optimization Theory and Applications, 47(1), 1-16 (1985).
[17] Ali, M.M., Khompatraporn, C., Zabinsky, Z.B., A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems. Journal of Global Optimization, 31(4), 635-672 (2005).
[18] Pierre, D.A., Optimization theory with applications. Courier Dover Publications, Mineola(1987). [19] Clerc, M., Kennedy, J., The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), 58-73 (2002).
[20] Ali, M.M., Kaelo, P., Improved particle swarm algorithms for global optimization. Applied Mathematics and Computation, 196(2), 578-593 (2008).
[21] Ali, M.M., T¨orn, A., Population set-based global optimization algorithms: some modifications and numerical studies. Computers and Operations Research, 31(10), 1703-1725 (2004).
[22] Yao, X., Liu, Y., Lin, G., Evolutionary programming made faster. IEEE Transactions on Evolutionary Computation, 3(2), 82 -102 (1999).