遗传算法如何工作
Outline of the Algorithm
以下大纲总结了遗传算法的工作方式：
The algorithm begins by creating a random initial population.
The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population. To create the new population, the algorithm performs the following steps:
Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
根据他们的期望，选择成员，称为父母。
Some of the individuals in the current population that have lower fitness are chosen aselite。这些精英个人被传给了下一个人口。
从父母那里养育孩子。儿童是通过向单亲进行随机更改而产生的 -突变- 或结合一对父母的矢量条目crossover。
Replaces the current population with the children to form the next generation.
The algorithm stops when one of the stopping criteria is met. SeeStopping Conditions for the Algorithm。
该算法采取了线性和整数约束的修改步骤。看整数和线性约束。
The algorithm is further modified for nonlinear constraints. SeeNonlinear Constraint Solver Algorithms。
Initial Population
The algorithm begins by creating a random initial population, as shown in the following figure.
In this example, the initial population contains20在dividuals. Note that all the individuals in the initial population lie in the upper-right quadrant of the picture, that is, their coordinates lie between 0 and 1. For this example, the初始人群option is[0;1]。
If you know approximately where the minimal point for a function lies, you should set初始人群so that the point lies near the middle of that range. For example, if you believe that the minimal point for Rastrigin's function is near the point[0 0], you could set初始人群成为[-1;1]。但是，如本示例所示，遗传算法甚至可以找到最低限度初始人群。
Creating the Next Generation
在每个步骤中，遗传算法使用当前的人群来创建组成下一代的孩子。该算法选择当前人口中的一组个人，称为parents, who contribute their基因s—the entries of their vectors—to their children. The algorithm usually selects individuals that have better fitness values as parents. You can specify the function that the algorithm uses to select the parents in theSelectionFCNoption. See选择选项。
遗传算法为下一代创造了三种类型的孩子：
Eliteare the individuals in the current generation with the best fitness values. These individuals automatically survive to the next generation.
Crossoverare created by combining the vectors of a pair of parents.
Mutation孩子们通过向单亲父母引入随机更改或突变来创建。
以下示意图说明了三种类型的儿童。
突变和跨界explains how to specify the number of children of each type that the algorithm generates and the functions it uses to perform crossover and mutation.
以下各节解释了算法如何创建交叉和突变儿童。
跨越儿童
该算法通过将成对的父母在当前的人群中结合在一起来创建跨越儿童。在子矢量的每个坐标处，默认交叉函数随机选择条目，或基因, at the same coordinate from one of the two parents and assigns it to the child. For problems with linear constraints, the default crossover function creates the child as a random weighted average of the parents.
Mutation Children
The algorithm creates mutation children by randomly changing the genes of individual parents. By default, for unconstrained problems the algorithm adds a random vector from a Gaussian distribution to the parent. For bounded or linearly constrained problems, the child remains feasible.
The following figure shows the children of the initial population, that is, the population at the second generation, and indicates whether they are elite, crossover, or mutation children.
后代的图
下图显示了在迭代60、80、95和100处的种群。
|
|
|
|
|
|
As the number of generations increases, the individuals in the population get closer together and approach the minimum point[0 0]。
Stopping Conditions for the Algorithm
The genetic algorithm uses the following options to determine when to stop. See the default values for each option by runningopts = optimoptions（'ga'）。
最大化— The algorithm stops when the number of generations reaches最大化。MaxTime— The algorithm stops after running for an amount of time in seconds equal toMaxTime。FitnessLimit— The algorithm stops when the value of the fitness function for the best point in the current population is less than or equal toFitnessLimit。MaxStallGenerations- 当健身函数值的平均相对变化以上时，算法停止MaxStallGenerations是less than功能公差。MaxStallTime— The algorithm stops if there is no improvement in the objective function during an interval of time in seconds equal toMaxStallTime。函数授体— The algorithm runs until the average relative change in the fitness function value overMaxStallGenerations是less than功能公差。ConstraintTolerance— TheConstraintTolerance不用用作停止标准。它用于确定相对于非线性约束的可行性。还，max(sqrt(eps),ConstraintTolerance)determines feasibility with respect to linear constraints.
The algorithm stops as soon as any one of these conditions is met.
Selection
The selection function chooses parents for the next generation based on their scaled values from the fitness scaling function. The scaled fitness values are called the expectation values. An individual can be selected more than once as a parent, in which case it contributes its genes to more than one child. The default selection option,@selectionstochunif, lays out a line in which each parent corresponds to a section of the line of length proportional to its scaled value. The algorithm moves along the line in steps of equal size. At each step, the algorithm allocates a parent from the section it lands on.
更确定的选择选择ion is@SelectionRemainder, which performs two steps:
In the first step, the function selects parents deterministically according to the integer part of the scaled value for each individual. For example, if an individual's scaled value is 2.3, the function selects that individual twice as a parent.
在第二步中，选择函数使用缩放值的分数部分选择了其他父母，如随机均匀的选择。该函数在各节中列出了一条线，其长度与个人缩放值的分数部分成正比，并以相等的步骤沿线移动以选择父母。
请注意，如果缩放值的分数零件均等于0，则可以使用
最佳缩放，选择完全是确定性的。
有关详细信息和更多选择选项，请参阅选择选项。
Reproduction Options
繁殖选项控制遗传算法如何创建下一代。选项是
EliteCount— The number of individuals with the best fitness values in the current generation that are guaranteed to survive to the next generation. These individuals are calledelite children。When
EliteCount是at least 1, the best fitness value can only decrease from one generation to the next. This is what you want to happen, since the genetic algorithm minimizes the fitness function. SettingEliteCountto a high value causes the fittest individuals to dominate the population, which can make the search less effective.CrossoverFraction— The fraction of individuals in the next generation, other than elite children, that are created by crossover.Setting the Crossover Fractiondescribes how the value ofCrossoverFractionaffects the performance of the genetic algorithm.
Because elite individuals have already been evaluated,GAdoes not reevaluate the fitness function of elite individuals during reproduction. This behavior assumes that the fitness function of an individual is not random, but is a deterministic function. To change this behavior, use an output function. See评估人员在The State Structure。
突变和跨界
The genetic algorithm uses the individuals in the current generation to create the children that make up the next generation. Besides elite children, which correspond to the individuals in the current generation with the best fitness values, the algorithm creates
Crossover children by selecting vector entries, or genes, from a pair of individuals in the current generation and combines them to form a child
Mutation children by applying random changes to a single individual in the current generation to create a child
这两个过程对于遗传算法至关重要。交叉使算法能够从不同个体中提取最佳基因，并将其重新组合到潜在的优质儿童中。突变增加了人口的多样性，从而增加了算法会产生具有更好适合度值的个体的可能性。
看Creating the Next Generationfor an example of how the genetic algorithm applies mutation and crossover.
您可以指定算法创建的每种类型的儿童中有多少种类型的孩子：
EliteCountspecifies the number of elite children.CrossoverFractionspecifies the fraction of the population, other than elite children, that are crossover children.
例如，如果PopulationSize是20,EliteCount是2，和CrossoverFraction是0.8,numbers of each type of children in the next generation are as follows:
There are two elite children.
除精英儿童以外，还有18个人，因此算法回合0.8*18 = 14.4至14，以获取跨界儿童的数量。
其余四个人，除精英儿童以外，是突变儿童。
整数和线性约束
When a problem has integer or linear constraints (including bounds), the algorithm modifies the evolution of the population.
When the problem has both integer and linear constraints, the software modifies all generated individuals to be feasible with respect to those constraints. You can use any creation, mutation, or crossover function, and the entire population remains feasible with respect to integer and linear constraints.
When the problem has only linear constraints, the software does not modify the individuals to be feasible with respect to those constraints. You must use creation, mutation, and crossover functions that maintain feasibility with respect to linear constraints. Otherwise, the population can become infeasible, and the result can be infeasible. The default operators maintain linear feasibility:
GAcreationlinearfeasibleorGAcreationnonlinearfeasiblefor creation,突变抗原用于突变和交叉区用于跨界。
The internal algorithms for integer and linear feasibility are similar to those for代理。When a problem has integer and linear constraints, the algorithm first creates linearly feasible points. Then the algorithm tries to satisfy integer constraints by rounding linearly feasible points to integers using a heuristic that attempts to keep the points linearly feasible. When this process is unsuccessful in obtaining enough feasible points for constructing a population, the algorithm callsintlinprogto try to find more points that are feasible with respect to bounds, linear constraints, and integer constraints.
后来，当突变或跨界创建新的人群成员时，算法确保新成员通过采取类似步骤来确保整数和线性可行。如有必要，将修改每个新成员，以尽可能接近其原始值，同时满足整数和线性约束和边界。
Related Topics
You can also select a web site from the following list:
美洲
- América Latina(Español)
- 加拿大（英语）
- 美国（英语）