OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 18, Iss. 20 — Sep. 27, 2010
  • pp: 20876–20886
« Show journal navigation

Mutation operators in lens system optimization to jump out of local minima

Lei Li, Qiong-Hua Wang, Xiao-Qing Xu, and Da-Hai Li  »View Author Affiliations


Optics Express, Vol. 18, Issue 20, pp. 20876-20886 (2010)
http://dx.doi.org/10.1364/OE.18.020876


View Full Text Article

Acrobat PDF (1607 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

In lens system design, Damped Least Squares method is a traditionally used local search method. In this paper we apply mutation operators to control damping factor in Damped Least Squares. We study the mutation behavior in this method when the algorithm confronts with local minima. The proposed method can go beyond local minima by taking mutation operators to control damping factor. The proposed method was successfully applied to design problems. The result indicates that the mutation operators provide an effective and rapid way to jump out of poor local minima.

© 2010 OSA

1. Introduction

2. Theory

We first describe briefly the conventional use of Damped Least Squares method [11

11. J. Meiron, “Damped Least-Squares method for automatic lens design,” J. Opt. Soc. Am. 55(9), 1105–1107 (1965). [CrossRef]

]. Damped Least Squares method employs the damping factor to obtain the step size vector ∆X to change the configuration parameter vector X of a lens system as follows:

ΔX=(ATA+PI)1ATF0,
(1)
X=X0+ΔX.
(2)

We note that the system includes the operand space (dimension M) and the variable space (dimension N). A (M × N) is derivative matrix of an optimization problem. I (N × N) is the identity matrix. F0 is the vector of operand values to be reduced to zero or certain target values. X0 is the configuration parameter vector before iteration. P is the damping factor. Usually P is a proper positive real number. The choice of P determines the effectiveness of the algorithm. For more details, see Ref [11

11. J. Meiron, “Damped Least-Squares method for automatic lens design,” J. Opt. Soc. Am. 55(9), 1105–1107 (1965). [CrossRef]

].

In the proposed method, for the purpose of jumping out of local minima we must reset P when the solution is trapped in local minima. From the Eq. (1), we know that if ATA+PI is not a singular matrix, the step size ∆X is to become small and the algorithm is to converge due to basins of attraction [12

12. H. E. Nusse and J. A. Yorke, “Basins of attraction,” Science 271(5254), 1376–1380 (1996). [CrossRef]

]. Then the algorithm can find local minima effectively. However, if ATA+PI is close to a singular matrix, this algorithm shows divergence instead of convergence. We can make ATA+PI singular as follow:

|ATA+PI|=0.
(3)

3. Mutation behavior in Damped Least Squares method

We examine the mutation behavior of the proposed method using a monochromatic doublet optimization problem as an example. The design requirement is that f-number is 3 and the field angle is 1 degree. The optimization parameters are radiuses (r1, r2, r3, r4) and thicknesses (d1, d2, d3, d4) as shown in Fig. 1
Fig. 1 An example of doublet lens.
. The stop is placed at the first surface. The configuration parameter vector X is (r1, r2, r3, r4, d1, d2, d3, d4).

Mutation operations take place only when the algorithm confronts with local minima. In the optimization, we first allow the conventional Damped Least Squares method to iterate until it reaches a local minimum. Then we reset damping factor P as shown in Eq. (5). The algorithm continues to iterate. This procedure is mutation period as we mention in Section 2. Then the mutation period is followed by the former period (using conventional damping factor). These two periods alternate until the final satisfactory result is produced. In the following experiments, Q is set to 0.7.

In the second trial, we reset n to 13. Figure 3
Fig. 3 Optimization route (n = 13). (a) Route of 1200 iterations. (b) Route of 550-750 iterations. (c) Route of 750-950 iterations. (d) Route of 950-1050 iterations.
shows the value of merit function for each iteration in the optimization procedure. In this trial, n becomes larger than that in the first one. We could see that this algorithm iterates less than 1050, but it has produced a satisfactory result which is better than the target. Thus the algorithm ends ahead of 1200 times.

In the third trial, we reset n to 23. The same phenomenon happens as shown in Fig. 4
Fig. 4 Optimization route (n = 23). (a) Route of 1200 iterations. (b) Route of 500-750 iterations. (c) Route of 620-750 iterations.
. We can see that in the first mutation period the value of merit function decreases sharply so as it needn’t more iteration times to produce a satisfactory result.

From three examples, we could make a conclusion that the mutation operation in Eq. (5) takes effect in jumping out of local minima.

In Section 2, we also note that mutation operators can take effect only when the mutated P is neither too near to nor too far from -Pk. Therefore, in the fourth trial, we make mutated P very near to -Pk as follow:

P=Pk{exp[τN(0,1)+τNi(0,1)]}n[QN(0,1)]n.
(8)

Figure 5
Fig. 5 Optimization route when mutated P is near to –Pk. (a) Overview of optimization route. (b) Overview of optimization route with enlarged vertical axis.
shows the value of merit function for each iteration in the optimization procedure. We can see that the mutated solution is very large (bad). In Fig. 5 (a) we could not find the mutated solutions. We enlarge the vertical axis to 3000 as shown in Fig. 5 (b). Then the mutated solutions can be found. Obviously, the result is rather bad. In this trial, P is too near to -Pk, and ATA+PI becomes close to a singular matrix. Then the step size ∆X becomes infinite and out of control. Thus result is very bad.

In the last trial, we make the mutated P far from -Pk as follow:
P=P0{(1+exp[τN(0,1)+τNi(0,1)])}n[1+QN(0,1)]n,
(9)
where P0 is not eigenvalue and is set to 0.2. The value is similar to the value of the common damping factor so as to avoid singular matrix, so the center P0 is quite far from -Pk. We could hardly find the mutation phenomenon during iteration process in Fig. 6
Fig. 6 Optimization route when mutated P is far from –Pk.
.

From the above examples, we can make conclusions that the mutation operators can conduct as an effective way to jump out of poor local minima. However, the mutation operators are not always effective. The mutated P controlled by mutation operators should be set neither too near to nor too far from -Pk. In this paper, we propose a mutation operator shown in Eq. (5). It works fairly well in the optimization.

4. Design examples and result discussions

In Section 3, we analyze the mutation behavior in Damped Least Squares. Now we choose the monochromatic quartet problem to evaluate the capability of the proposed method for automatic lens system design. The statement of the problem is as follows [15

15. D. C. O’Shea, “The monochromatic quartet: a search for the global optimum,” Proc. SPIE 1354, 548–554 (1990). [CrossRef]

]:

Design a 4-elment, f/3, 100 mm effective focal length lens of BK7 glass, illuminated by helium d wavelength. The object is at infinity, the object field covers 30° full field (15° semi-field angle) and the image field is flat. Constraints on the construction include: only spherical surfaces, no aspheric, GRIN elements, Fresnel lenses, binary elements, holographic optical elements, etc. The minimum glass thickness is 2 mm, but there is no upper limit on the size of the lens. The distortion must be less than 1% and there should be no vignetting. The last is intended to assure that vignetting could not be used to improve the edge performance on the lens. No requirement is put on the location of the stop of the system. The merit function consists of the average of the RMS blur spot for three fields: on-axis, 10.5°, and 15°, weighted equally.

The merit function in the experiment is constructed according to the criteria from above.
F=Pdist+Pimg+Pvign+13θ={0,10.5,15}RMS,
(10)
where the variables Pdist, Pimg and Pvign are different penalties computed from a set of physical constraints, as presented in Table 1

Table 1. Physical constraints for the monochromatic quartet.

table-icon
View This Table
| View All Tables
. The initial value of Pdist, Pimg and Pvign is 0. The penalty value is used to make sure the merit function value of unfeasible designs is always worse than that of feasible one. The RMS blur spot size is computed from the variance of the position at the image plane of different exact rays with the same entrance angle.

Besides, we also used evolutionary algorithm to design the same problem. The initial design is also the rough design shown in Table 2. Figure 9
Fig. 9 The design found with evolutionary algorithm.
presents the solution. Table 6

Table 6. Configuration parameters of the design found with evolutionary algorithm.

table-icon
View This Table
| View All Tables
gives the configuration parameters of the design found with evolutionary algorithm. Table 7

Table 7. Comparison of the solutions found with proposed method and the solution found with evolutionary algorithm.

table-icon
View This Table
| View All Tables
is a comparison between solution of the proposed method and the solution of the standard evolutionary algorithm. It is obvious that the proposed method can produce the final solution much faster than the evolutionary algorithm, although these two methods seem to find out the same kind solution finally.

5. Conclusion

In this paper we apply mutation operators to control the damping factor in Damped Least Squares. We study the mutation behavior in this method when the algorithm confronts with local minima. The proposed method can go beyond local minima by taking mutation operators to control the damping factor. The proposed method was successfully applied to design problems. The results indicate that the mutation operators provide an effective and rapid way to jump out of poor local minima. Besides, the proposed method come into use simply by applying the mutation operators to control the damping factor in conventional Damped Least Squares method. So we believe this study can help the existing softwares perform better.

Acknowledgments

The work was supported by Program for New Century Excellent Talents in University in China under Grant No. NCET-07-0582 and the National Natural Science Foundation of China (NNSFC) under Grant No. 60877004.

References and links

1.

K. Levenberg, “A method for the solution of certain non-linear problems in least squares,” Q. Appl. Math. 2, 164–168 (1944).

2.

M. Isshiki, H. Ono, K. Hiraga, J. Ishikawa, and S. Nakadate, “Lens design: global optimization with escape function,” Opt. Rev. 2(6), 463–470 (1995). [CrossRef]

3.

D. Vasiljevic, “Classical and evolutionary algorithms in the optimization of optical systems,” (Wiley, 2001).

4.

V. Yakovlev and G. Tempea, “Optimization of chirped mirrors,” Appl. Opt. 41(30), 6514–6520 (2002). [CrossRef] [PubMed]

5.

C. Gagné, J. Beaulieu, M. Parizeau, and S. Thibault, “Human-competitive lens system design with evolution strategies,” Appl. Soft Comput. 8(4), 1439–1452 (2008). [CrossRef]

6.

I. Ono, S. Kobayashi, and Y. Yoshida, “Optimal lens design by real-coded genetic algorithms using UNDX,” Comput. Methods Appl. Mech. Eng. 186(2-4), 483–497 (2000). [CrossRef]

7.

L. Li, Q. H. Wang, D. H. Li, and H. R. Peng, “Jump method for optical thin film design,” Opt. Express 17(19), 16920–16926 (2009). [CrossRef] [PubMed]

8.

L. Li, Q. H. Wang, X. Q. Xu, and D. H. Li, “Two-step method for lens system design,” Opt. Express 18(12), 13285–13300 (2010). [CrossRef] [PubMed]

9.

D. Shafer, “Global optimization in optical design,” Comput. Phys. 8, 188–195 (1994).

10.

M. van Turnhout and F. Bociort, “Chaotic behavior in an algorithm to escape from poor local minima in lens design,” Opt. Express 17(8), 6436–6450 (2009). [CrossRef] [PubMed]

11.

J. Meiron, “Damped Least-Squares method for automatic lens design,” J. Opt. Soc. Am. 55(9), 1105–1107 (1965). [CrossRef]

12.

H. E. Nusse and J. A. Yorke, “Basins of attraction,” Science 271(5254), 1376–1380 (1996). [CrossRef]

13.

H. P. Schwefel, “Numerical optimization of computer models,” (Wiley, 1981).

14.

J. M. Yang and C. Y. Kao, “A robust evolutionary algorithm for optical thin-film designs,” Evol. Comput. 2, 978–985 (2000).

15.

D. C. O’Shea, “The monochromatic quartet: a search for the global optimum,” Proc. SPIE 1354, 548–554 (1990). [CrossRef]

OCIS Codes
(220.2740) Optical design and fabrication : Geometric optical design
(220.3620) Optical design and fabrication : Lens system design
(080.1753) Geometric optics : Computation methods

ToC Category:
Optical Design and Fabrication

History
Original Manuscript: June 8, 2010
Revised Manuscript: August 13, 2010
Manuscript Accepted: September 15, 2010
Published: September 17, 2010

Citation
Lei Li, Qiong-Hua Wang, Xiao-Qing Xu, and Da-Hai Li, "Mutation operators in lens system optimization to jump out of local minima," Opt. Express 18, 20876-20886 (2010)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-18-20-20876


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. K. Levenberg, “A method for the solution of certain non-linear problems in least squares,” Q. Appl. Math. 2, 164–168 (1944).
  2. M. Isshiki, H. Ono, K. Hiraga, J. Ishikawa, and S. Nakadate, “Lens design: global optimization with escape function,” Opt. Rev. 2(6), 463–470 (1995). [CrossRef]
  3. D. Vasiljevic, “Classical and evolutionary algorithms in the optimization of optical systems,” (Wiley, 2001).
  4. V. Yakovlev and G. Tempea, “Optimization of chirped mirrors,” Appl. Opt. 41(30), 6514–6520 (2002). [CrossRef] [PubMed]
  5. C. Gagné, J. Beaulieu, M. Parizeau, and S. Thibault, “Human-competitive lens system design with evolution strategies,” Appl. Soft Comput. 8(4), 1439–1452 (2008). [CrossRef]
  6. I. Ono, S. Kobayashi, and Y. Yoshida, “Optimal lens design by real-coded genetic algorithms using UNDX,” Comput. Methods Appl. Mech. Eng. 186(2-4), 483–497 (2000). [CrossRef]
  7. L. Li, Q. H. Wang, D. H. Li, and H. R. Peng, “Jump method for optical thin film design,” Opt. Express 17(19), 16920–16926 (2009). [CrossRef] [PubMed]
  8. L. Li, Q. H. Wang, X. Q. Xu, and D. H. Li, “Two-step method for lens system design,” Opt. Express 18(12), 13285–13300 (2010). [CrossRef] [PubMed]
  9. D. Shafer, “Global optimization in optical design,” Comput. Phys. 8, 188–195 (1994).
  10. M. van Turnhout and F. Bociort, “Chaotic behavior in an algorithm to escape from poor local minima in lens design,” Opt. Express 17(8), 6436–6450 (2009). [CrossRef] [PubMed]
  11. J. Meiron, “Damped Least-Squares method for automatic lens design,” J. Opt. Soc. Am. 55(9), 1105–1107 (1965). [CrossRef]
  12. H. E. Nusse and J. A. Yorke, “Basins of attraction,” Science 271(5254), 1376–1380 (1996). [CrossRef]
  13. H. P. Schwefel, “Numerical optimization of computer models,” (Wiley, 1981).
  14. J. M. Yang and C. Y. Kao, “A robust evolutionary algorithm for optical thin-film designs,” Evol. Comput. 2, 978–985 (2000).
  15. D. C. O’Shea, “The monochromatic quartet: a search for the global optimum,” Proc. SPIE 1354, 548–554 (1990). [CrossRef]

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited