Method of determining movement sequence, alignment apparatus, method and apparatus of designing optical system, and medium in which program realizing the designing method

Abstract

A determining method of movement sequence and a positioning apparatus of the invention are arranged in such a manner that, in order to measure positions of plural marks as being measurement targets provided on a wafer within a shorter time, a group including executable movement sequences is generated out of a group of movement sequence candidates, each indicating a measurement order of these marks, and a movement sequence that accomplishes a movement operation between the marks within the shortest time is obtained from the group thus generated. For efficiently searching an optical system as a globally optimal solution within a shorter computation time, independently of an initial solution given, a designing method of optical system of the invention obtains the optimal solution of the optical system to be designed, using an evolutionary computation method (genetic algorithm) having a genetic operator for handling continuos values explicitly. Particularly, from a partial space defined by a predetermined continuous occurrence probability distribution of occurrence probabilities set based on parent individuals, child individuals to be candidates in the next generation population are generated according to the occurrence probabilities.

What is claimed is:  
     
         1 . A determining method of movement sequence for determining an order of measurement of a plurality of measurement target areas, which is executed prior to an alignment step in which while the plurality of measurement target areas provided on a substrate are successively moved into a preset measuring area of a measuring system, positions of the respective measurement target areas moved into the measuring area are measured, thereby achieving alignment between a transfer position of a pattern of an original plate and each chip area on the substrate, 
 said determining method of movement sequence comprising an arithmetic step of obtaining a solution of a most preferable movement sequence with respect to an overall movement time between said plurality of measurement target areas, by using a predetermined search technique, said arithmetic step comprising: 
 a first step of generating a group including a plurality of executable movement sequences out of a group of movement sequence candidates, each indicating a measurement order of said plurality of measurement target areas; and  
 a second step of selecting a movement sequence that can accomplish a movement operation between said plurality of target areas in the shortest time, out of said group generated.  
   
     
     
         2 . The method according to  claim 1 , further comprising a pre-step carried out prior to said arithmetic step, said pre-step being a step of producing a movement time management table in which for each of said plurality of measurement target areas, a movement time is recorded as a time necessary for movement of the target area of interest from a position thereof at the time of completion of position measurement of either one of said plurality of measurement target areas into said measuring area of the measuring system.  
     
     
         3 . The method according to  claim 2 , wherein said movement time management table includes such information that for a pair of measurement target areas selected out of said plurality of measurement target areas, after completion of the position measurement of one measurement target area selected, the other measurement target area selected is prohibited from moving from a position thereof at the time of completion of the position measurement of the one measurement target area selected into said measuring area of the measuring system.  
     
     
         4 . The method according to  claim 1 , wherein said search technique includes at least one of a method based on operations-research technique, an evolutionary computation method, and a combination thereof.  
     
     
         5 . The method according to  claim 4 , wherein said method based on operations-research technique includes at least one of a linear programming method, a Lin and Kernighan's approach, and a k-OPT method.  
     
     
         6 . The method according to  claim 5 , wherein said linear programming method is a method arranged in such a manner that when there exist plural near solutions to the best solution of a movement sequence to be obtained, a plurality of good solutions are generated by recomputation with change in a method for selecting one specific solution or with change in a search start point and a most preferable, good solution with respect to the overall movement time between said plurality of measurement target areas is selected out of the plurality of good solutions thus generated.  
     
     
         7 . The method according to  claim 5 , wherein said combination method including said linear programming method is a method arranged in such a manner that, using a plurality of first good solutions obtained by said linear programming method for a movement sequence to be obtained, as initial solutions, a plurality of second good solutions are generated by the Lin and Kernighan's approach or the k-OPT method and a most preferable, second good solution with respect to the overall movement time between said plurality of target areas is selected out of said plurality of second good solutions thus generated.  
     
     
         8 . The method according to  claim 1 , wherein said search technique obtains a solution of a most preferable movement sequence with respect to the overall movement time between said plurality of target areas by use of a genetic algorithm, using constraint satisfying solutions generated at random, as initial solutions.  
     
     
         9 . The method according to  claim 1 , wherein said search technique obtains a solution of a most preferable movement sequence with respect to the overall movement time between said plurality of target areas by use of a genetic algorithm, using solutions obtained by at least one of a linear programming method, a Lin and Kernighan's approach, a k-OPT method, and a combination thereof, as starting solutions.  
     
     
         10 . The method according to  claim 9 , wherein an execution time of said arithmetic step using said genetic algorithm is shortened by improvement in solutions of movement sequences updated on occasion during execution of said genetic algorithm by one of the Lin and Kernighan's approach and the k-OPT method.  
     
     
         11 . The method according to  claim 9 , wherein said genetic algorithm has a mutation operator, said mutation operator having an operator for changing an order of measurement of measurement target areas selected from said plurality of measurement target areas.  
     
     
         12 . A determining method of movement sequence for determining an order of measurement of a plurality of alignment marks as becoming measurement targets provided on a substrate, which is executed prior to an alignment step in which while the plurality of alignment marks are successively moved into a preset measuring area of a measuring system, positions of the respective alignment marks moved into the measuring area are measured, thereby achieving alignment between a transfer position of a pattern of an original plate and each chip area on the substrate, 
 said determining method of movement sequence comprising an arithmetic step of obtaining a solution of a most preferable movement sequence with respect to an overall movement time between said plurality of alignment marks, by use of a predetermined search technique, said arithmetic step comprising: 
 at least a first step of generating a group including a plurality of executable movement sequences out of a group of movement sequence candidates, each indicating a measurement order of said plurality of alignment marks; and  
 a second step of selecting a movement sequence that can accomplish a movement operation between said plurality of alignment marks in the shortest time, out of said group generated.  
   
     
     
         13 . The method according to  claim 12 , further comprising a pre-step carried out prior to said arithmetic step, said pre-step being a step of producing a movement time management table in which for each of said plurality of alignment marks, a movement time is recorded as a time necessary for movement of the alignment mark of interest from a position thereof at the time of completion of position measurement of either one of said plurality of alignment marks into said measuring area of the measuring system.  
     
     
         14 . The method according to  claim 13 , wherein said movement time management table includes such information that for a pair of alignment marks selected out of said plurality of alignment marks, after completion of the position measurement of one alignment mark selected, the other alignment mark selected is prohibited from moving from a position thereof at the time of completion of the position measurement of the one alignment mark selected into said measuring area of the measuring system.  
     
     
         15 . An alignment apparatus for successively measuring positions of a plurality of alignment marks as becoming measurement targets provided on a substrate and performing alignment between a transfer position of a pattern of an original plate and each chip area on the substrate by use of a statistical arithmetic method based on information of the positions of the respective alignment marks obtained, said positioning apparatus comprising: 
 a measuring device for measuring each of the positions of said plurality of alignment marks;    a moving device for effecting relative movement between said plurality of alignment marks and a measuring area of said measuring device;    an arithmetic section for generating a group of a plurality of executable movement sequences out of a group of movement sequence candidates, each indicating a measurement order of said plurality of alignment marks, and selecting a movement sequence that accomplishes a movement operation between said plurality of alignment marks within the shortest time, out of said group generated; and    a control section for controlling said moving device so as to successively move said plurality of alignment marks into the measuring area of said measuring device, according to a solution of the movement sequence obtained by said arithmetic section.    
     
     
         16 . The apparatus according to  claim 15 , further comprising a memory for storing a movement time management table in which for each of said plurality of alignment marks, a movement time is recorded as a time necessary for movement of the alignment mark of interest from a position thereof at the time of completion of position measurement of either one of said plurality of alignment marks into said measuring area of the measuring device.  
     
     
         17 . The apparatus according to  claim 16 , wherein said movement time management table stored in said memory includes such information that for a pair of alignment marks selected out of said plurality of alignment marks, after completion of the position measurement of one alignment mark selected, the other alignment mark selected is prohibited from moving from a position thereof at the time of completion of the position measurement of the one-alignment mark selected into said measuring area of the measuring device.  
     
     
         18 . The apparatus according to  claim 15 , wherein said arithmetic section executes a search technique of at least one of a method based on operations-research technique, an evolutionary computation method, and a combination thereof.  
     
     
         19 . A designing method of optical system comprising: 
 a selection step of selecting at least two parent individuals from a population consisting of a plurality of individuals, said population being an n (≧1) generation population and each individual being a real vector representing a candidate of an optical system to be designed;    a child generation step of newly generating a population of plural child individuals by applying at least one of a crossover operator and a mutation operator as a genetic operator to said parent individuals selected; and    a survival selection step of selecting individuals to be left as individuals in a next generation population from said n generation population and said population of child individuals.    
     
     
         20 . The method according to  claim 19 , wherein said survival selection step is a step of selecting as individuals of the next generation population individuals satisfying at least either of one or two or more evaluation criteria from said n generation population and said population of the child individuals generated.  
     
     
         21 . The method according to  claim 1 , wherein in said child generation step said crossover operator generates, from the inside of a partial space defined by a predetermined continuous occurrence probability distribution of occurrence probabilities set based on components of real vectors of the respective parent individuals selected, a real vector having a component of a value occurring according to the occurrence probabilities, as a child individual.  
     
     
         22 . The method according to  claim 1 , wherein in said child generation step said mutation operator generates, from the inside of a partial space defined by a predetermined continuous occurrence probability distribution of occurrence probabilities increasing with approaching at least one parent individual out of said parent individuals selected, a real vector having a component of a value occurring according to the occurrence probabilities, as a child individual.  
     
     
         23 . The method according to  claim 1 , wherein said selection step, said child generation step, and said survival selection step are carried out in order plural times.  
     
     
         24 . A designing method of optical system for repetitively performing generation of a population consisting of a plurality of individuals, each individual having a plurality of parameters representing a candidate of an optical system to be designed, said optical system including at least one optical element, and selection of individuals to be left as individuals in a next generation population, thereby optimizing the optical system to be designed, 
 wherein optimization of at least one selected parameter out of said plural parameters of the individuals is effected by selecting a plurality of parent individuals out of said individuals generated,    setting a predetermined continuous occurrence probability distribution of occurrence probabilities, based on the selected parameter of each of said plurality of parent individuals, and    newly generating a child individual having as a value of said selected parameter a value occurring according to the occurrence probabilities, from the inside of a partial space defined by said occurrence probability distribution.    
     
     
         25 . The method according to  claim 24 , wherein from a population including at least said parent individuals and said child individual generated, an individual having as a value of said selected parameter a value fitting either of one or two or more evaluation criteria is selected as an individual in the next generation population.  
     
     
         26 . The method according to  claim 24 , wherein said selected parameter of the individual is at least one of a curvature of a boundary surface in said optical element, a distance between boundary surfaces, and a refractive index of a medium placed between the boundary surfaces.  
     
     
         27 . A designing method of optical system comprising: 
 a parent selection step of selecting at least two real vectors to be parents, from a population of plural individuals each representing a candidate of an optical system to be designed, said population being an n (≧1) generation population and each individual being a real vector having a component of one or two or more predetermined parameters featuring the optical system;    a child generation step of executing at least one of a crossover step and a mutation step, said crossover step being a step of generating, from the inside of a partial space defined and expressed by a predetermined continuous occurrence probability distribution of occurrence probabilities set based on components of the respective real vectors of said parent individuals selected, a real vector having a component of a value occurring according to the occurrence probabilities, as a child individual, and said mutation step being a step of generating, from the inside of a partial space defined by a predetermined continuous occurrence probability distribution of occurrence probabilities increasing with approaching at least one parent individual out of said parent individuals selected, a real vector having a component of a value occurring according to the occurrence probabilities, as a child individual; and    a survival selection step of selecting individuals to be left as individuals in a next generation population from said n generation population and said child individual generated.    
     
     
         28 . The method according to  claim 27 , wherein in said survival selection step said individuals selected replace individuals not selected in said n generation population, thereby generating the next generation population.  
     
     
         29 . The method according to  claim 27 , wherein in said survival selection step the individuals to be left as individuals in the next generation population are selected in order from an individual fittest to a predetermined evaluation criterion and in proportion to a fitness value of each individual from the population of said parent individuals and said child individual generated.  
     
     
         30 . The method according to  claim 27 , wherein in said survival selection step an individual satisfying at least either of one or two or more evaluation criteria is selected as an individual in the next generation population from the population of said parent individuals and said child individual generated.  
     
     
         31 . The method according to  claim 27 , wherein said component of real vector of individual is at least one of a radius of curvature of a boundary surface of said optical element, a distance between boundary surfaces, and a refractive index of a medium placed between the boundary surfaces.  
     
     
         32 . A designing apparatus of optical system comprising an arithmetic section for repetitively executing generation of plural parameters each representing a candidate of an optical system to be designed, said optical system including at least one optical element, and selection of parameters to be left out of the plural parameters generated, thereby optimizing the optical system to be designed, and a memory for temporarily storing the parameters generated, 
 wherein said arithmetic section executes at least a parent selection step of selecting at least two real vectors to be parents, from an n (≧1) generation population consisting of a plurality of real vectors given as said plural parameters;    a child generation step of executing at least one of a crossover step and a mutation step, said crossover step being a step of generating, from the inside of a partial space defined by a predetermined continuous occurrence probability distribution of occurrence probabilities set based on components of the respective real vectors of said parent individuals selected, a real vector having a component of a value occurring according to the occurrence probabilities, as a child individual, and said mutation step being a step of generating, from the inside of a partial space defined by a predetermined continuous occurrence probability distribution of occurrence probabilities increasing with approaching at least one parent individual out of said parent individuals selected, a real vector having a component of a value occurring according to the occurrence probabilities, as a child individual; and    a survival selection step of selecting individuals to be left as individuals in a next generation population from said n generation population and said child individual generated.    
     
     
         33 . The apparatus according to  claim 32 , wherein in said survival selection step the arithmetic section replaces individuals not selected in said n generation population by said selected individuals, thereby generating the next generation population.  
     
     
         34 . The apparatus according to  claim 32 , wherein in said survival selection step said arithmetic section selects the individuals to be left as individuals in the next generation population in order from an individual fittest to a predetermined evaluation criterion and in proportion to a fitness value of each individual from the population of said parent individuals and said child individual generated.  
     
     
         35 . The apparatus according to  claim 32 , wherein in said survival selection step said arithmetic section selects an individual satisfying at least either of one or two or more evaluation criteria as an individual in the next generation population from the population of said parent individuals and said child individual generated.  
     
     
         36 . The apparatus according to  claim 32 , wherein said component of real vector of individual handled in said arithmetic section is at least either one of a radius of curvature of a boundary surface of said optical element, a distance between boundary surfaces, and a refractive index of a medium placed between the boundary surfaces.  
     
     
         37 . A medium in which a program is recorded, said program comprising: 
 a parent selection step of selecting at least two real vectors to be parents, from a population of plural individuals each representing a candidate of an optical system to be designed, said population being an n (≧1) generation population and each individual being a real vector having a component of one or two or more predetermined parameters featuring the optical system;    a child generation step of executing at least one of a crossover step and a mutation step, said crossover step being a step of generating, from the inside of a partial space defined by a predetermined continuous occurrence probability distribution of occurrence probabilities set based on components of the respective real vectors of said parent individuals selected, a real vector having a component of a value occurring according to the occurrence probabilities, as a child individual, and said mutation step being a step of generating, from the inside of a partial space defined by a predetermined continuous occurrence probability distribution of occurrence probabilities increasing with approaching at least one parent individual out of said parent individuals selected, a real vector having a component of a value occurring according to the occurrence probabilities, as a child individual; and    a survival selection step of selecting individuals to be left as individuals in a next generation population from said n generation population and said child individual generated.    
     
     
         38 . The medium according to  claim 37 , wherein said program recorded therein is arranged so that in said survival selection step said individuals selected replace individuals not selected in said n generation population, thereby generating the next generation population.  
     
     
         39 . The medium according to  claim 37 , wherein said program recorded is arranged so that in said survival selection step the individuals to be left-as individuals in the next generation population are selected in order from an individual fittest to a predetermined evaluation criterion and in proportion to a fitness value of each individual from the population of said parent individuals and said child individual generated.  
     
     
         40 . The medium according to  claim 37 , wherein said program recorded is arranged so that in said survival selection step an individual satisfying at least either of one or two or more evaluation criteria is selected as an individual in the next generation population from the population of said parent individuals and said child individuals generated.  
     
     
         41 . The medium according to  claim 37 , wherein said program recorded is arranged so that said component of real vector of individual is at least one of a radius of curvature of a boundary surface of said optical element, a distance between boundary surfaces, and a refractive index of a medium placed between the boundary surfaces.