volume | PIER Journals

Abstract

This is the first of two companion papers on global optimization and antenna analysis and synthesis. In Part I, an analysis of the problems involved in Global Optimization is presented by critically discussing the basic concepts and tools, the performances to be expected, the required computational complexity and the guidelines to select algorithms solving efficiently the problem at hand. The relevance of stochastic techniques is enhanced and the role of double phase algorithms is stressed. The proof of the convergence property of an idealized version of a simplified evolutionary algorithm is provided. In Part II, the selected algorithm, a hybrid evolutionary algorithm, is tested against two real world problems relevant in electromagnetics, the power synthesis of contoured beam hybrid reflector antennas and the reflector antenna diagnosis from only amplitude data. The results of an extensive numerical analysis are presented.

1. Bucci, O. M., G. D'Elia, G. Mazzarella, and G. Panariello, "Antenna pattern synthesis: a new general approach," Proc. IEEE, Vol. 82, No. 3, 358-371, 1994.
doi:10.1109/5.272140

2. Bucci, O. M., G. D'Elia, and G. Romito, "Reflector distortions diagnosis from far-field amplitude pattern," IEEE Trans. Antennas and Propagat., Vol. 43, No. 11, 1217-1225, 1995.

3. Bucci, O. M., G. D'Elia, and G. Romito, "Synthesis technique for scanning and/or reconfigurable beams reflector antennas with phase-only control," IEE Proc. Microw. Antennas Propagat., Vol. 143, 402-412, 1996.
doi:10.1049/ip-map:19960262

4. Bucci, O. M., A. Capozzoli, and G. D'Elia, "New technique for wavefront reconstruction in optical telescopes," J. Opt. Soc. Am. A, Vol. 14, No. 12, 3394-3401, 1997.

5. Bucci, O. M. and G. D'Elia, "Power synthesis of reconfigurable conformal arrays with phase-only control," IEE Proc. Microw. Antennas Propagat., Vol. 1, No. 45, 131-136, 1998.
doi:10.1049/ip-map:19981296

6. Bucci, O. M., A. Capozzoli, and G. D'Elia, "Regularizing strategy for image restoration and wave-front sensing by phase diversity," JOSA A, Vol. 16, No. 7, 1759-1768, 1999.

7. Bucci, O. M., A. Capozzoli, and G. D'Elia, "A method for image restoration and wavefront sensing by using phase diversity," Signal Recovery and Synthesis, Vol. 11, 28-30, 1998.

8. Pierri, R., G. D'Elia, and F. Soldovieri, "A two probes scanning phaseless near-field far-field transformation technique," IEEE Trans. Antennas and Propagat., Vol. 47, No. 5, 792-802, 1999.
doi:10.1109/8.774132

9. McCallum, B. C., "Blind deconvolution by simulated annealing," Opt. Commun., Vol. 75, No. 2, 101-105, 1990.
doi:10.1016/0030-4018(90)90236-M

10. Morris, D., "Simulated annealing applied to the Misell algorithm for phase retrieval," IEE Proceedings, Vol. 143, No. 4, 298-303, 1991.

11. Scales, J. A., M. L. Smith, and T. L. Fischer, "Global optimization methods for multimodal inverse problems," J. Comput. Phys., Vol. 103, 258-268, 1992.
doi:10.1016/0021-9991(92)90400-S

12. Isernia, T., F. Soldovieri, G. Leone, and R. Pierri, "On the local minima in phase reconstruction algorithms," Radio Science, Vol. 31, No. 6, 1887-1999, 1996.
doi:10.1029/96RS02154

13. Pierri, R. and A. Tamburino, "On the local minima problem in conductivity imaging via a quadratic approach," Inverse Problems, Vol. 13, 1547-1568, 1997.
doi:10.1088/0266-5611/13/6/010

14. Zhai, J., Y. Yan, G. Jin, and M. Wu, "Global/local united search algorithm for global optimization," Optik, Vol. 108, 1998.

15. Bucci, O. M., A. Capozzoli, and G. D'Elia, "A hybrid evolutionary algorithm in the diagnosis of reflector distortions," JINA 98, 17-19, 1998.

16. Bucci, O. M., A. Capozzoli, and G. D'Elia, "A hybrid evolutionary algorithm in the diagnosis of reflector distortions from far-field amplitude pattern," Atti della Fondazione Ronchi, Vol. 54, No. 3, 503-519, 1999.

17. Bucci, O. M., A. Capozzoli, and G. D'Elia, "A Lamarckiantype evolutionary algorithm for large reflector diagnosis," XXVI General Assembly of the International Union of Radio Science, 13-21, 1999.

18. Bucci, O. M., A. Capozzoli, and G. D'Elia, "Diagnosis of array faults from far-field amplitude-only data," IEEE Trans. Antennas and Propagat., Vol. 48, No. 5, 647-652, 2000.
doi:10.1109/8.855482

19. Bucci, O. M., A. Capozzoli, and G. D'Elia, "A global optimization technique in the synthesis of reflector antennas," 17th Annual Review of Progress in Applied Computational Electromagnetics, 19-23, 2001.

20. Pardalos, P. M. and J. B. Rosen, Constrained Global Optimization: Algorithms and Applications, Springer-Verlag, 1987.

21. Torn, A. and A. Zilinskas, Global Optimization, Springer-Verlag, 1987.

22. Van Laarhoven, P. J. M. and E. H. L. Aarts, Simulated Annealing: Theory and Applications, Kluwer, Dordrecht, 1987.

23. Horst, R. and H. Tuy, Global Optimization: Deterministic Approaches, Springer, 1992.

24. Horst, R. and P. M. Pardalos (Eds.), Handbook of Global Optimization, Kluwer, Dordrecht, 1995.

25. Back, T., D. B. Fogel, and Z. Michalewicz (Eds.), Handbook of Evolutionary Computation, Institute of Physics Publishing, Oxford University Press, 1997.

26. Tuy, H., Convex Analysis and Global Optimization, Kluwer, Dordrecht, 1998.

27. Gu, J. and X. Huang, "Efficient local search with search space smooting: A case of study of the traveling salesman problem (TSP)," IEEE Trans. On Systems, Vol. 24, No. 5, 728-735, 1994.

28. Zabinsky, Z. B., "Stochastic methods for practical global optimization," J. of Global Optimization, Vol. 13, 433-444, 1998.
doi:10.1023/A:1008350230239

29. Graham, L. C., "Synthetic interference radar for topographic mapping," Proc. IEEE, Vol. 62, 763-768, 1974.

30. Romeijn, H. E. and R. L. Smith, "Simulated annealing and adaptive search in global optimization," Probability in Engineering and Informational Sciences, Vol. 8, 571-590, 1994.

31. Hiriart-Urruty, J. B., "Conditions for global optimality," Handbook of Global Optimization, 1-26, 1995.

32. Giaquinta, M. and S. Hildebrandt, Calculus of Variation, Vols. I- II, Springer, Berlin, 1996.

33. Kantorovic, L. V. and G. P. Akilov, Functional Analysis, MIR, Moscow, 1980.

34. Rinnooy Kan, A. H. G. and G. T. Timmer, "Stochastic methods for global optimization," American Journal of Mathematical and Management Sciences, Vol. 2, 1-2, 1984.

35. Zemanian, A. H., Distribution Theory and Transform Analysis, Dover, New York, 1987.

36. Gergel, V. P., "A global optimization algorithm for multivariate functions with Lipschitzian first derivatives," Journal of Global Optimization, Vol. 10, 257-281, 1997.
doi:10.1023/A:1008290629896

37. Hansen, P., B. Jaumard, and S. Lu, "Global optimization of univariate Lipschitz functions; I. Survey and properties," Mathematical Programming, Vol. 55, 251-272, 1992.
doi:10.1007/BF01581202

38. Hansen, P., B. Jaumard, and S. Lu, "Global optimization of univariate Lipschitz functions; II. New algorithms and computational comparison," Mathematical Programming, Vol. 55, 273-292, 1992.
doi:10.1007/BF01581203

39. Rinnooy Kan, A. H. G. and G. T. Timmer, "Stochastic methods for global optimization," American Journal of Mathematical and Management Sciences, Vol. 2, 1-2, 1984.

40. Hiriart-Urruty, J. B. and C. Lemarechal, Convex Analysis and Minimization Algorithms, Vols. I-II, Springer-Verlag, 1993.

41. Floudas, C. A. and V. Visweswarn, "Quadratic optimization," Handbook of Global Optimization, 217-269, 1995.

42. Hansen, P. and B. Jaumard, "Lipschitz optimization," Handbook of Global Optimization, 407-493, 1995.

43. Bonanno, G., "On a class of functions whose local minima are global," Journal of Global Optimization, Vol. 12, 101-104, 1998.
doi:10.1023/A:1008234910469

44. Benson, H. P., "Concave minimization: Theory, applications and algorithms," Handbook of Global Optimization, 43-148, 1995.

45. H. Tuy, ``D.C. optimization: Theory[#COMMA] methods, "D.C. optimization: Theory, methods and algorithms," Handbook of Global Optimization, 149-216, 1995.

46. Luenberger, D. G., Linear and Nonlinear Programming, Addison- Wesley, 1984.

47. Strekalovsky, A. S., "Global optimality conditions for non convex optimization," Journal of Global Optimization, Vol. 12, 415-534, 1998.
doi:10.1023/A:1008277314050

48. Hiriart-Urruty, J. B., "Conditions for global optimality 2," Journal of Global Optimization, 349-367, 1998.
doi:10.1023/A:1008365206132

49. Levi, A. V. and A. Montalvo, "The tunneling algorithm for the global minimization of functions," Siam J. Sci. Stat. Comput., Vol. 6, 1985.

50. Falk, J. E., "Conditions for global optimality in nonlinear programming," Operation Research, Vol. 21, 337-340, 1973.

51. Pincus, M, "A closed form solution of certain programming problems," Operation Research, Vol. 16, 690-694, 1968.

52. Murty, K. G. and S. N. Kabadi, "Some NP-complete problems in quadratic and nonlinear programming," Mathematical Programming, Vol. 38, 117-129, 1987.

53. Wolpert, D. H. and W. G. Macready, "No free lunch theorems for optimization," IEEE Trans. Evolutionary Comput., Vol. 1, 1997.
doi:10.1109/4235.585893

54. Waldrop, M. M., Complexity: The Emerging Science at the Edge of Order and Chaos, Simon & Schuster, 1992.

55. Ratschek, H. and J. Rokne, "Interval methods," Handbook of Global Optimization, 751-828, 1995.

56. Vavasis, S. A., Nonlinear Optimization: Complexity Issues, Oxford Science Publication, New York, 1991.

57. Nemirovsky, A. S. and D. B. Yudin, Problem Convexity and Method Efficiency in Optimization, John Wiley and Sons, 1983.

58. Vescovo, R., "Constrained and unconstrained synthesis of array factor for circular arrays," IEEE Trans. on Antennas and Peropagat., Vol. 43, No. 12, 1405-1410, 1995.
doi:10.1109/8.475929

59. Anderssen, R. S. and P. Bloominfield, "Properties of the random search in global optimization," Journal of Optimization Theory and Applications, Vol. 16, 383-398, 1975.
doi:10.1007/BF00933849

60. Boender, C. G. E. and H. E. Romeijn, "Stochastic methods," Handbook of Global Optimization, 8299-869.

61. Solis, F. J. and R. J. B. Wets, "Minimization by random search techniques," Math. Operation Res., Vol. 6, 19-30.

62. Rinnooy Kan, A. H. G. and G. T. Timmer, "Stochastic global optimization methods Part I: Clustering methods," Mathematical Programming, Vol. 39, 27-56, 1987.

63. Rinnooy Kan, A. H. G. and G. T. Timmer, "Stochastic global optimization methods Part II: Multi level methods," Mathematical Programming, Vol. 39, 57-78, 1987.

64. Patel, N. R., R. L. Smith, and Z. B. Zabinsky, "Pure adaptive search in Monte Carlo optimization," Mathematical Programming, Vol. 43, 317-328, 1988.
doi:10.1007/BF01582296

65. Zabinsky, Z. B. and R L. Smith, "Pure adaptive search in global optimization," Mathematical Programming, Vol. 53, 323-338, 1992.
doi:10.1007/BF01585710

66. Kirkpatrik, S., C. D. Gelatt, Jr., and M. P. Vecchi, "Optimization by simulated annealing," Science, Vol. 220, No. 4598, 671-680, 1983.

67. Romeijn, H. E. and R. L. Smith, "Simulated annealing for constrained global optimization," Journal of Global Optimization, Vol. 5, 101-126, 1994.
doi:10.1007/BF01100688

68. Byrd, R., C. L. Dert, A. H. G. Rinnooy Kan, and R. B. Schnabel, "Concurrent Stochastic methods for global optimization," Mathematical Programming, Vol. 46, 1-29, 1990.
doi:10.1007/BF01585724

69. Mahfoud, S., "Boltzmann selection," Handbook of Evolutionary Computation, 1997.

70. Back, T., U. Hammel, and H. P. Schwefel, "Evolutionary computation: Comments on the history and current state," IEEE Trans. on Evolutionary Comput., Vol. 1, 1997.

71. Back, T. and H. P. Schwefel, "An overview of evolutionary algorithms for parameter optimization," Evolutionary Computation, Vol. 1, No. 2, 1-20, 1993.

72. Fogel, D. B., "An introduction to simulated evolutionary optimization," IEEE Trans. Neural Networks, Vol. 5, 1994.
doi:10.1109/72.265956

73. Kim, J. H. and H. Myung, "Evolutionary programming techniques for constrained optimization problems," EEE Trans. Evolutionary Comput., Vol. 1, 1997.

74. Tang, K. S., K. F. Man, S. Kwong, and Q. He, "Genetic algorithms and their applications," IEEE Signal Processing Magazine, No. 11, 22-37, 1996.
doi:10.1109/79.543973

75. Holland, J. H., Adaptation in Natural and Artificial Systems, MIT Press, 1995.

76. De Jong, K., D. B. Fogel, and H. P. Schwefel, "A history of evolutionary computation," Handbook of Evolutionary Computation, 1997.

77. Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989.

78. Davis, L., Handbook of Genetic Algorithms, Van Nostrand Reinhold, 1991.

79. Back, T., G. Rudolph, and H. P. Schwefel, "Evolutionary programming and evolution strategies: Similarities and differences," The Evolutionary Computation Repositary Network (ENCORE)..

80. Muhlenbein, H. and D. Schlierkamp-Voosen, "Predictive models for breeder genetic algorithms," Evolutionary Computation, Vol. 1, No. 1, 25-49, 1993.

81. Qi, X. Q. and F. Palmieri, "Theoretical analysis of evolutionary algorithms with an infinite population size in continuous space Part I: Basic properties of selection and mutation," IEEE Trans. Neural Networks, Vol. 5, 1994.

82. Qi, X. Q. and F. Palmieri, "Theoretical analysis of evolutionary algorithms with an infinite population size in continuous space Part II: Analysis of the diversification role of crossover," IEEE Trans. Neural Networks, Vol. 5, 1994.

83. Rudolph, G., "Convergence analysis of canonical genetic algorithms," IEEE Trans. Neural Network, Vol. 5, 1994.
doi:10.1109/72.265964

84. Francois, O., "An evolutionary strategy for global minimization and its Markov chain analysis," IEEE Trans. Evolutionary Computat., Vol. 2, No. 3, 77-90, 1998.
doi:10.1109/4235.735430

85. Naudts, B. and L. Kallel, "A comparison of predictive measures of problem difficulty in evolutionary algorithms," IEEE Trans. Evolutionary Computat., Vol. 4, 2000.

86. Kellel, L., B. Naudts, A. Rogers, and G. Rozenberg, Theoretical Aspects of Evolutionary Computing, Springer Verlag, 2001.

87. Suzuki, J., "A Markov chain analysis on simple genetic algorithms," IEEE Trans. Systems, Vol. 25, 1995.

88. Rudolph, G., "Stochastic processes," Handbook of Evolutionary Computation, 1997.

89. Rudolph, G., "Modes of stochastic convergence," Handbook of Evolutionary Computation, 1997.

90. Goldberg, D. E., "A note on Boltzmann tournament selection for genetic algorithms and population-oriented simulated annealing," Complex Systems, Vol. 4, 445-460, 1990.

91. Fogel, D. B. and A. Ghozeil, "A note on representation and variation operators," IEEE Trans. Evolutionary Computat., Vol. 1, 1997.

92. Radcliffe, N. J, "Schema processing," Handbook of Evolutionary Computation, 1997.

93. Eshelman, L. J. and J. D. Schaffer, "Real-coded genetic algorithms and interval-schemata," Foundation of Genetic Algorithm 2, 1993.

94. Renders, J. M. and S. P. Flasse, "Hybrid methods using genetic algorithms for global optimization," IEEE Trans. Systems, Vol. 26, 1996.

95. Hancock, P. J. B., "A comparison of selection mechanisms," Handbook of Evolutionary Computation, 1997.

96. Grefenstette, J., "Proportional selection and sampling algorithms," Handbook of Evolutionary Computation, 1997.

97. Back, T., D. B. Fogel, D. Whitley, and P. J. Angeline, "Mutation," Handbook of Evolutionary Computation, 1997.

98. Rudolph, G., "Local convergence rates of simple evolutionary algorithms with Cauchy mutation," IEEE Trans. Evolutionary Computat., Vol. 1, 1997.

99. Booker, L. B., D. B. Fogel, D. Whitley, and P. J. Angeline, "Recombination," Handbook of Evolutionary Computation, 1997.

100. Eiben, A. E., R. Hinterding, and Z. Michalewicz, "Parameter control in evolutionary algorithms," IEEE Trans. Evolutionary Computat., Vol. 3, 124-141, 1999.
doi:10.1109/4235.771166

101. Back, T., "Self adaptation in genetic algorithms," Evolutionary Computation, Vol. 1, No. 2, 1-20, 1993.

102. Srinivas, M. and L. M. Patnaik, "Adaptive probabilities of crossover and mutation in genetic algorithms," IEEE Trans. Systems, Vol. 24, 1994.

103. Grefenstette, J. J., "Optimization of control parameter for genetic algorithms," IEEE Trans. Systems, Vol. 16, 1986.

104. Smith, R. E., "Population size," Handbook of Evolutionary Computation, 1997.

105. Ross, S. M., Stochastic Processes, J. Wiley and Sons, New York, 1983.

Prof. Amedeo Capozzoli

Professor Giuseppe D'Elia