Combining interval branch and bound and stochastic search. (English) Zbl 1474.90526

Summary: This paper presents global optimization algorithms that incorporate the idea of an interval branch and bound and the stochastic search algorithms. Two algorithms for unconstrained problems are proposed, the hybrid interval simulated annealing and the combined interval branch and bound and genetic algorithm. The numerical experiment shows better results compared to Hansen’s algorithm and simulated annealing in terms of the storage, speed, and number of function evaluations. The convergence proof is described. Moreover, the idea of both algorithms suggests a structure for an integrated interval branch and bound and genetic algorithm for constrained problems in which the algorithm is described and tested. The aim is to capture one of the solutions with higher accuracy and lower cost. The results show better quality of the solutions with less number of function evaluations compared with the traditional GA.


90C59 Approximation methods and heuristics in mathematical programming
90C30 Nonlinear programming


Full Text: DOI


[1] Sun, M., A fast memoryless interval-based algorithm for global optimization, Journal of Global Optimization, 47, 2, 247-271 (2010) · Zbl 1190.90147
[2] Ratschek, H.; Rokne, J., New Computer Methods for Global Optimization (1988), New York, NY, USA: Halstad Press, New York, NY, USA · Zbl 0648.65049
[3] Michalewicz, Z., Genetic algorithms + Data Structures = Evolution Programs (1994), New York, NY, USA: Springer, New York, NY, USA · Zbl 0818.68017
[4] Aarts, E.; Korst, J., Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing (1989), New York, NY, USA: John Wiley & Sons, New York, NY, USA · Zbl 0674.90059
[5] Blickle, T.; Thiele, L., A comparison of selection schemes used in genetic algorithms (1995), Zurich, Switzerland: Swiss Federal Institute of Technology (ETH), Computer Engineering and Communications Networks Lab (TIK), Zurich, Switzerland
[6] Goldberg, D. E.; Deb, K., A comparative analysis of selection schemes used in genetic algorithms, Foundations of Genetic Algorithms, 69-93 (1991), Morgan Kaufmann
[7] Razali, N. M.; Geraghty, J., Genetic algorithm performance with different selection strategiesin solving TSP, Proceedings of the World Congress on Engineering, IAENG Publications
[8] Lagouanelle, J.-L.; Soubry, G., Optimal multisections in interval branch-and-bound methods of global optimization, Journal of Global Optimization, 30, 1, 23-38 (2004) · Zbl 1136.90521
[9] Csallner, A. E.; Csendes, T.; Markót, M. C., Multisection in interval branch-and-bound methods for global optimization—I. Theoretical results, Journal of Global Optimization, 16, 4, 371-392 (2000) · Zbl 0997.90104
[10] Markót, M. C.; Csendes, T.; Csallner, A. E., Multisection in interval branch-and-bound methods for global optimization. II. Numerical tests, Journal of Global Optimization, 16, 3, 219-228 (2000) · Zbl 0971.90066
[11] Casado, L. G.; Garcia, I.; Csendes, T., A heuristic rejection criterion in interval global optimization algorithms, BIT. Numerical Mathematics, 41, 4, 683-692 (2001) · Zbl 0992.65068
[12] Sun, M.; Johnson, A. W., Interval branch and bound with local sampling for constrained global optimization, Journal of Global Optimization, 33, 1, 61-82 (2005) · Zbl 1093.90088
[13] Karmakar, S.; Bhunia, A. K., On constrained optimization by interval arithmetic and interval order relations, OPSEARCH, 49, 1, 22-38 (2012) · Zbl 1353.90184
[14] Coello Coello, C. A., A survey of cons traint handling techniques used with evolutionary algorithms (1999), Laboratorio Nacional de Informtica Avanzada
[15] Alander, J. T., Interval arithmetic and genetic algorithms in global optimization, Artificial Neural Nets and Genetic Algorithms, 388-392 (1995), Vienna, Austria: Springer, Vienna, Austria
[16] Sotiropoulos, D. G.; Stavropoulos, E. C.; Vrahatis, M. N., A new hybrid genetic algorithm for global optimization, Nonlinear Analysis: Theory, Methods & Applications, 30, 7, 4529-4538 (1997) · Zbl 0891.68046
[17] Zhang, X.; Liu, S., A new interval-genetic algorithm, Proceedings of the 3rd International Conference on Natural Computation (ICNC ’07)
[18] Shary, S. P., Randomized algorithms in interval global optimization, Numerical Analysis and Applications, 1, 4, 376-389 (2008)
[19] Floudas, C. A.; Pardalos, P. M., A Collection of Test Problems for Constrained Global Optimization Algorithms (1990), New York, NY, USA: Springer, New York, NY, USA · Zbl 0718.90054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.