Minimization over randomly selected lines

Ismet Sahin


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.


Random Lines; nonlinear optimization; evolutionary optimization; population-based optimization; quadratic interpolation; crossover operator; mutation operator; stopping criterion; Differential Evolution; Particle Swarm

Full Text:

Full Text [PDF]


Torn, A., Global optimization. Springer-Verlag (1989). Crossref

Price, K., Storn, R.M., Lampinen, J.A., Differential evolution: a practical approach to global optimization. Springer-Verlag, Berlin (2005).

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

Luenberger, D.G., Ye, Y., Linear and nonlinear programming. Springer, New York (2008).

Dennis, J.E., Schnabel, R.B., Numerical methods for unconstrained optimization and nonlinear equations. SIAM (1987).

More, J.J., Thuente, D.J., Line search algorithms with guaranteed sufficient decrease. ACM Transactions on Mathematical Software, 20(3), 286–307 (1994). Crossref

Mohan, C., Shanker, K., A controlled random search technique for global optimization using quadratic approximation. Asia-Pacic Journal of Operational Research, 11(1), 93–101 (1994).

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)

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

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

Onwubolu, G., Davendra, D., Scheduling flow shops using differential evolution algorithm. European Journal of Operational Research, 171(2), 674–692 (2006). Crossref

Sahin, I., Random Lines: a novel population set-based evolutionary global optimization algorithm. Genetic Programming vol. 6621, 97-107, Springer-Verlag, Berlin (2011).

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

Rahnamayan, S., Tizhoosh, H.R., Salama, M.M.A., Opposition-based Differential Evolution. IEEE Transactions on Evolutionary Computation, 12(1), 64-79 (2008). Crossref

More, J.J., Garbow, B.S., Hillstrom, K.E., Testing unconstrained optimization software. Acm Transactions on Mathematical Software, 7(1), 17-41 (1981). Crossref

Aluffipentini, F., Parisi, V., Zirilli, F., Global optimization and stochastic differential-equations. Journal of Optimization Theory and Applications, 47(1), 1-16 (1985). Crossref

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

Pierre, D.A., Optimization theory with applications. Courier Dover Publications, Mineola(1987).

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

Ali, M.M., Kaelo, P., Improved particle swarm algorithms for global optimization. Applied Mathematics and Computation, 196(2), 578-593 (2008). Crossref

Ali, M.M., T¨orn, A., Population set-based global optimization algorithms: some modiï¬cations and numerical studies. Computers and Operations Research, 31(10), 1703-1725 (2004). Crossref

Yao, X., Liu, Y., Lin, G., Evolutionary programming made faster. IEEE Transactions on Evolutionary Computation, 3(2), 82 -102 (1999). Crossref



  • There are currently no refbacks.

Copyright (c) 2013 Ismet Sahin

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.


   ithe_170     crossref_284         ind_131_43_x_117_117  Scopus  EBSCO_Host    ULAKBIM    PROQUEST   ZBMATH more...