Minimization over randomly selected lines
This paper presents a population-based evolutionary optimization method for minimizing a given cost function. The mutation operator of this method selects randomly oriented lines in the cost function domain, constructs quadratic functions interpolating the cost function at three different points over each line, and uses extrema of the quadratics as mutated points. The crossover operator modifies each mutated point based on components of two points in population, instead of one point as is usually performed in other evolutionary algorithms. The stopping criterion of this method depends on the number of almost degenerate quadratics. We demonstrate that the proposed method with these mutation and crossover operations achieves faster and more robust convergence than the well-known Differential Evolution and Particle Swarm algorithms.
[1] T¨orn, A., Global optimization. Springer- Verlag (1989).
[2] Price, K., Storn, R.M., Lampinen, J.A., Dif- ferential 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 Opti- mization and Control: Theories and Appli- cations (IJOCTA), 3(1), 35–43 (2012).
[4] Luenberger, D.G., Ye, Y., Linear and non- linear 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 search algo- rithms with guaranteed sufficient decrease. ACM Transactions on Mathematical Soft- ware, 20(3), 286–307 (1994).
[7] Mohan, C., Shanker, K., A controlled ran- dom 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 opti- mization 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 algo- rithm. European Journal of Operational Re- search, 171(2), 674–692 (2006).
[12] S¸ahin, I(˙)., Random Lines: a novel popula-tion set-based evolutionary global optimiza- tion 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 Interna- tional Conference on Optimization of Elec- trical and Electronic Equipment, Brasov, Ro- mania (2006).
[14] Rahnamayan, S., Tizhoosh, H.R., Salama, M.M.A., Opposition-based Differential Evo- lution. 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 Soft- ware, 7(1), 17-41 (1981).
[16] Aluffipentini, F., Parisi, V., Zirilli, F., Global optimization and stochastic differential-equations. Journal of Optimiza- tion Theory and Applications, 47(1), 1-16 (1985).
[17] Ali, M.M., Khompatraporn, C., Zabinsky, Z.B., A numerical evaluation of several sto- chastic algorithms on selected continuous global optimization test problems. Journal of Global Optimization, 31(4), 635-672 (2005).
[18] Pierre, D.A., Optimization theory with ap- plications. Courier Dover Publications, Mi- neola(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 parti- cle swarm algorithms for global optimiza- tion. Applied Mathematics and Computation, 196(2), 578-593 (2008).
[21] Ali, M.M., T¨orn, A., Population set-based global optimization algorithms: some mod- ifications and numerical studies. Computers and Operations Research, 31(10), 1703-1725 (2004).
[22] Yao, X., Liu, Y., Lin, G., Evolutionary pro- gramming made faster. IEEE Transactions on Evolutionary Computation, 3(2), 82 -102 (1999).