=== Entry for the 2007 Human-Competitive Results Contest (Humies) === Human-Competitive Lens System Design with Evolution Strategies by Christian Gagné Julie Beaulieu Marc Parizeau Simon Thibault ------------------------------------------------ PUBLISHED PAPERS RELEVANT TO THE SUBMITTED ENTRY Main paper backing the human-competitive result claims: 1) Christian Gagné, Julie Beaulieu, Marc Parizeau, and Simon Thibault, "Human-Competitive Lens System Design with Evolution Strategies", Technical report RT-LVSN-2007-01, Laboratoire de Vision et Systèmes Numériques, Université Laval, Québec (Quebec), Canada, May 22, 2007, 25 pages, http://vision.gel.ulaval.ca/Publications/PublDetails.php?Id=674. Abstract: Lens system design provides ideal problems for evolutionary algorithms: a complex non-linear optimization task, often with intricate physical constraints, for which there is no analytical solutions. This paper demonstrates, through the use of two evolution strategies, namely non-isotropic SA-ES and CMA-ES, as well as multiobjective NSGA-II optimization, the human competitiveness of an approach where an evolutionary algorithm is hybridized with a local search algorithm to solve both a classic benchmark problem, and a real-world problem. Comments: This report has also been submitted for publication to the journal "Applied Soft Computing" and is still under evaluation as of May 28th, 2007. It is partly based on the work presented in on Chapter 6 of Christian Gagné's Ph.D. thesis. Other relevant papers: 2) Simon Thibault, Christian Gagné, Julie Beaulieu, and Marc Parizeau, "Evolutionary Algorithms Applied to Lens Design: Case Study and Analysis", Proc. of the SPIE International Symposium on Optical Systems Design (EOD 2005), Jena, Germany, September 12-16, 2005. Abstract: Lens system design makes extensive use of optimization techniques to improve the performance of an optical system. We know that designing a lens system is a complex task currently done by experienced optical designers, using specialized optical design software tools. In order to contribute to this particular field, this paper presents a comparison between lens design done by optical designers and evolutionary algorithms lens based design. Evolutionary algorithms consist in population-based global search methods inspired by natural evolution. They are recognized to be particularly efficient for complex non-linear optimization problems. Given the non-linear nature of lens design as an optimization process, evolutionary algorithms are good candidates for automating this task. The evolutionary algorithms were applied to the monochromatic quartet that was presented to expert participants at the International Lens Design Conference in 1990 (a friendly competition). Comparative results demonstrate that the evolutionary approach is able to find solutions slightly better than those presented at the competition. Then a real-life imaging problem is tackled. Results show that an evolutionary algorithm is again able to discover lens systems comparable to design done after a reasonable effort by experts. This paper presents an analysis of this approach for automatic lens design from a real-life optical design point of view. Comments: This paper is an analysis by Simon Thibault of the results presented in "Human-Competitive Lens System Design with Evolution Strategies" (ref. 8 in the paper) from an optical design point-of-view. This analysis has been published in a peer-reviewed international conference on optical design. 3) Julie Beaulieu, Christian Gagné, and Marc Parizeau, "Lens System Design and Re-Engineering with Evolutionary Algorithms", Proc. of the Genetic and Evolutionary Computation Conference (GECCO 2002), New York (NY), USA, July 9-13, 2002, p. 155-162. Abstract: This paper presents some lens system design and re-engineering experimentations with genetic algorithms and genetic programming. These Evolutionary Algorithms (EA) were successfully applied to a design problem that was previously presented to expert participants of an international lens design conference. Comparative results demonstrate that the use of EA for lens system design is very much human-competitive. Comments: This paper presents preliminary results obtained with GA and GP for automatic optical design. Although published in 2002, the work in this paper has never been proposed to any of the previous Humies. This paper won the best-paper award of the track "Evolvable Hardware" at the GECCO 2002. ------------------------------------------------ WHY THE RESULT SATISFIES THE EVALUATION CRITERIA The first type of results that support our claims are for the monochromatic quartet problem, proposed in a friendly lens design competition between human experts attending the 1990 International Lens Design Conference (ILDC 1990). Best human-generated results were published in the conference proceedings and were then believed to be global optima for this problem. By applying two different evolution strategies hybridized with a local search algorithm available in optical CAD tools, two results of interest have been obtained for the monochromatic problem: one design with a significantly better quality than those presented at ILDC 1990, contradicting the believes that the global optima was found at the conference, and one other design that appears to be a rediscovery of results proposed by human experts at ILDC 1990. A similar approach was also applied to a lens design problem previously tackled by world-class human experts in optical design from the INO (National Optics Institute, www.ino.ca). This real-world problem consists in designing an optical system for an imaging system where mechanical constraints are important. Again, by using classical evolution strategies hybridized with local search algorithms, results obtained through EA are better than those proposed by the INO's experts. Using a multi-objective version of our algorithm, it was also possible to produce lens system design of a given quality, with an estimated relative cost significantly better than the design proposed by the INO's experts. Referring to the eight criteria for establishing that an automatically created result is competitive with a human-produced result, the automatic lens system design with hybridized evolution strategy applied to the monochromatic quartet problem and the INO's imaging problem satisfies the following three of the eight criteria: (D) The result is publishable in its own right as a new scientific result - independent of the fact that the result was mechanically created. (G) The result solves a problem of indisputable difficulty in its field. (H) The result holds its own or wins a regulated competition involving human contestants (in the form of either live human players or human-written computer programs). ------------------------------------------------- WHY THE JUDGES SHOULD CONSIDER THIS ENTRY AS BEST Optical design is an important engineering discipline with a central role in domains such as astronomy, computer vision, remote sensing, or optical telecommunications. Moreover, the importance of this discipline might just continue to grow, with bright farsighted perspectives. Indeed, it is widely believed that current computing devices based on electricity and silicon might be replaced in a not-so-far future by computation with light and optical materials. It is widely known that common optical design problems can be formulated as real-valued optimization problems, and specialized optical CAD tools have been using local search algorithms for a long time. But, these optimization problems are recognized for having a complex search space made of several peaks and non-linearities, making local search insufficient. The modern optical design process thus still involves human experts that are crafting solutions to the tackled problems using their experience and intuition. These rough solutions are then refined with optical CAD tools using local search optimization procedures. Several iterations of human intervention followed by computer optimization are then typically necessary to obtain satisfactory solutions. The proposed method based on EA is an important step toward the automation of optical design. The novelty of this particular work lies is twofold: 1) the hybridization of evolution strategies with specialized local search algorithms, which somehow simulate modern optical design process by replacing human experts by EA, and 2) the successful application of this technique to synthetic and real-world problems, with results equal or better than those obtained by human experts. This is a clear example of human-competitiveness that give high credit to EC for its inclusion in the optical designer's toolbox. Completely replacing optical designers by computer programs may not yet be thinkable, but the work presented in this entry enables at least a semi-automated design that works for real-life situations. This kind of breakthrough should be an incitative for companies making optical CAD tools to improve their software by making use of EC, so that optical experts can design better systems in less time. ----------------------------- COMPLETE ADDRESSES OF AUTHORS 1) Christian Gagné (corresponding author) Preferred mailing addresses: (Private address, removed for privacy reasons) Professional affiliation (not good for physical mail): Informatique WGZ Inc. 819 avenue Monk Québec (Quebec), G1S 3M9 Canada Phone: +1 418 844-4000 ext. 4295 E-mail: cgagne@gmail.com, christian.gagne@wgz.ca 2) Julie Beaulieu Preferred mailing addresses: (Private address, removed for privacy reasons) E-mail: jubeaulieu@gmail.com, julie@juliebeaulieu.com 3) Marc Parizeau Département de Génie Électrique et de Génie Informatique Université Laval, Québec (Quebec), G1K 7P4 Canada Phone: +1 418 656-2131 ext. 7912 E-mail: Marc.Parizeau@gel.ulaval.ca 4) Simon Thibault Preferred mailing addresses: (Private address, removed for privacy reasons) Professional affiliation (not good for physical mail): ImmerVision Inc. 2020 University, suite 2420 Montréal (Quebec), H3A 2A5 Canada Professional phone: +1 514 985-4007 ext. 3018 Cell phone: +1 418 261-0049 E-mail: simon.thibault@immervision.com ------------------------- STATEMENT ABOUT THE PRIZE Any prize money, if any, is to be divided equally among the co-authors.