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 Google Scholar

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. Google Scholar

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 Google Scholar

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. Google Scholar

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 Google Scholar

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. Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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

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 Google Scholar

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 Google Scholar

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 Google Scholar

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

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. Google Scholar

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. Google Scholar

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. Google Scholar

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 Google Scholar

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. Google Scholar

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, 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, 1995.

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

26. Tuy, H., Convex Analysis and Global Optimization, Kluwer, 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. Google Scholar

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

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

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. Google Scholar

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

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

33. Kantorovic, L. V. and G. P. Akilov, Functional Analysis, MIR, 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. Google Scholar

35. Zemanian, A. H., Distribution Theory and Transform Analysis, Dover, 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 Google Scholar

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 Google Scholar

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 Google Scholar

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. Google Scholar

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

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

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

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 Google Scholar

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

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

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 Google Scholar

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

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

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

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

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

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 Google Scholar

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. Google Scholar

56. Vavasis, S. A., Nonlinear Optimization: Complexity Issues, Oxford Science Publication, 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 Google Scholar

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 Google Scholar

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

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

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. Google Scholar

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. Google Scholar

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 Google Scholar

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 Google Scholar

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

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 Google Scholar

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 Google Scholar

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

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. Google Scholar

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

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

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

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 Google Scholar

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. Google Scholar

77. Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, 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).. Google Scholar

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

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. Google Scholar

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. Google Scholar

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

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 Google Scholar

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

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. Google Scholar

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

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

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. Google Scholar

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

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

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

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

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

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

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

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

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

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 Google Scholar

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

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

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

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

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

Prof. Amedeo Capozzoli

Professor Giuseppe D'Elia