更改

<!-- Deleted image removed: The ESA/JAXA interplanetary Trajectory recipient of the [http://www.genetic-programming.org/combined.php 2013 gold HUMIES ] award. This complex tour of the Jovian Moons was found with the help of an evolutionary technique based on self-adaptation -->

<!-- Deleted image removed: The ESA/JAXA interplanetary Trajectory recipient of the [http://www.genetic-programming.org/combined.php 2013 gold HUMIES ] award. This complex tour of the Jovian Moons was found with the help of an evolutionary technique based on self-adaptation -->

< ! -- 被删除的图片: ESA/JAXA 行星际轨道奖获得者。这次木星卫星之旅是在一种基于自我适应的进化技术的帮助下发现的

<!-- 被删除的图片: ESA/JAXA 行星际轨道奖获得者。这次木星卫星之旅是在一种基于自我适应的进化技术的帮助下发现的 -->

In [[computer science]] and [[operations research]], a '''genetic algorithm''' ('''GA''') is a [[metaheuristic]] inspired by the process of [[natural selection]] that belongs to the larger class of [[evolutionary algorithm]]s (EA). Genetic algorithms are commonly used to generate high-quality solutions to [[Optimization (mathematics)|optimization]] and [[Search algorithm|search problem]]s by relying on biologically inspired operators such as [[Mutation (genetic algorithm)|mutation]], [[crossover (genetic algorithm)|crossover]] and [[selection (genetic algorithm)|selection]].{{sfn|Mitchell|1996|p=2}}

In [[computer science]] and [[operations research]], a '''genetic algorithm''' ('''GA''') is a [[metaheuristic]] inspired by the process of [[natural selection]] that belongs to the larger class of [[evolutionary algorithm]]s (EA). Genetic algorithms are commonly used to generate high-quality solutions to [[Optimization (mathematics)|optimization]] and [[Search algorithm|search problem]]s by relying on biologically inspired operators such as [[Mutation (genetic algorithm)|mutation]], [[crossover (genetic algorithm)|crossover]] and [[selection (genetic algorithm)|selection]].{{sfn|Mitchell|1996|p=2}}

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection.

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection.

在计算机科学和运筹学研究中，遗传算法(GA)是一种受自然选择过程启发的元启发式算法，属于进化算法(EA)的较大类别。遗传算法通常依赖于生物学上的变异、交叉和选择算子来生成优化和搜索问题的高质量解。

在计算机科学和运筹学研究中，'''<font color="#ff8000">遗传算法 genetic algorithm(GA)</font>'''是一种受自然选择过程启发的元启发式算法，属于[[演化算法]](EA)的较大类别。遗传算法通常依赖于生物学上的'''变异'''、'''交叉'''和'''选择'''算子来生成优化和搜索问题的高质量解。

== Methodology ==

=== 最优化问题 ===

 

 

 

=== Optimization problems ===

In a genetic algorithm, a [[population]] of [[candidate solution]]s (called individuals, creatures, or [[phenotype]]s) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its [[chromosome]]s or [[genotype]]) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.{{sfn|Whitley|1994|p=66}}

In a genetic algorithm, a [[population]] of [[candidate solution]]s (called individuals, creatures, or [[phenotype]]s) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its [[chromosome]]s or [[genotype]]) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.{{sfn|Whitley|1994|p=66}}

In a genetic algorithm, a population of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotype) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.

In a genetic algorithm, a population of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotype) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.

在遗传算法中，最佳化问题的候选解决方案(被称为个体、生物或表型)群体向着更好的解决方案进化。每个候选解决方案都有一组可以变异和改变的属性(染色体或基因型) ; 传统上，解决方案用二进制表示为0和1的字符串，但其他编码也是可能的。

在遗传算法中，最优化问题的候选解(被称为个体、生物或表型)群体会向着更好的方向进化。每个候选解都有一组可以变异和改变的属性(染色体或基因型)，传统上，解会用二进制编码成0和1的字符串，但其他编码也是可能的。

The evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated; the fitness is usually the value of the objective function in the optimization problem being solved. The more fit individuals are stochastically selected from the current population, and each individual's genome is modified (recombined and possibly randomly mutated) to form a new generation. The new generation of candidate solutions is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.

The evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated; the fitness is usually the value of the objective function in the optimization problem being solved. The more fit individuals are stochastically selected from the current population, and each individual's genome is modified (recombined and possibly randomly mutated) to form a new generation. The new generation of candidate solutions is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.

进化通常从一个随机生成的个体群体开始，是一个迭代过程，每次迭代中的群体称为一代。在每一代人中，每一个人的适合度都会被评估; 适合度通常是解决最佳化问题中目标函数的值。更适合的个体随机地从当前的种群中选出，每个个体的基因组被修改(重组和可能的随机突变) ，形成新一代。然后在算法的下一次迭代中使用新一代候选解。一般情况下，当生成了最大的世代数，或者群体达到了令人满意的适应水平时，算法就会终止。

进化通常从一个随机生成的群体开始，是一个迭代过程，每次迭代中的群体称为一代。在每一代中，每一个个体的适合度都会被评估；'''<font color="#ff8000">适合 fitness</font>'''度通常是解决最佳化问题中目标函数的值。适合度更高的个体会被随机地从当前的种群中选出，每个个体的基因组被修改(重组和可能的随机突变) ，形成新一代。然后在算法的下一次迭代中使用新一代候选解。一般情况下，当迭代次数达到最大的预设值，或者群体达到了令人满意的适应水平时，算法就会终止。

一个典型的遗传算法需要:

一个典型的遗传算法需要:

# a [[genetic representation]] of the solution domain,

# a [[genetic representation]] of the solution domain,

# a [[fitness function]] to evaluate the solution domain.

# a [[fitness function]] to evaluate the solution domain.

 

# 一个适应度函数来评估解域。

一个适应度函数来评估解域。

 

 

A standard representation of each candidate solution is as an [[bit array|array of bits]].{{sfn|Whitley|1994|p=66}} Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple [[Crossover (genetic algorithm)|crossover]] operations. Variable length representations may also be used, but crossover implementation is more complex in this case. Tree-like representations are explored in [[genetic programming]] and graph-form representations are explored in [[evolutionary programming]]; a mix of both linear chromosomes and trees is explored in [[gene expression programming]].

A standard representation of each candidate solution is as an [[bit array|array of bits]].{{sfn|Whitley|1994|p=66}} Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple [[Crossover (genetic algorithm)|crossover]] operations. Variable length representations may also be used, but crossover implementation is more complex in this case. Tree-like representations are explored in [[genetic programming]] and graph-form representations are explored in [[evolutionary programming]]; a mix of both linear chromosomes and trees is explored in [[gene expression programming]].

A standard representation of each candidate solution is as an array of bits. Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple crossover operations. Variable length representations may also be used, but crossover implementation is more complex in this case. Tree-like representations are explored in genetic programming and graph-form representations are explored in evolutionary programming; a mix of both linear chromosomes and trees is explored in gene expression programming.

A standard representation of each candidate solution is as an array of bits. Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple crossover operations. Variable length representations may also be used, but crossover implementation is more complex in this case. Tree-like representations are explored in genetic programming and graph-form representations are explored in evolutionary programming; a mix of both linear chromosomes and trees is explored in gene expression programming.

Once the genetic representation and the fitness function are defined, a GA proceeds to initialize a population of solutions and then to improve it through repetitive application of the mutation, crossover, inversion and selection operators.

Once the genetic representation and the fitness function are defined, a GA proceeds to initialize a population of solutions and then to improve it through repetitive application of the mutation, crossover, inversion and selection operators.

==== Initialization ====

==== 初始化====

The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Often, the initial population is generated randomly, allowing the entire range of possible solutions (the [[Feasible region|search space]]). Occasionally, the solutions may be "seeded" in areas where optimal solutions are likely to be found.

The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Often, the initial population is generated randomly, allowing the entire range of possible solutions (the [[Feasible region|search space]]). Occasionally, the solutions may be "seeded" in areas where optimal solutions are likely to be found.

The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Often, the initial population is generated randomly, allowing the entire range of possible solutions (the search space). Occasionally, the solutions may be "seeded" in areas where optimal solutions are likely to be found.

The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Often, the initial population is generated randomly, allowing the entire range of possible solutions (the search space). Occasionally, the solutions may be "seeded" in areas where optimal solutions are likely to be found.

种群大小取决于问题的性质，但通常包含几百个或几千个可能的解决方案。通常，初始种群是随机生成的，允许所有可能的解(搜索空间)。有时候，解决方案可能会在有可能找到最佳解决方案的地区被“播种”。

种群大小取决于问题的性质，但通常包含几百个或几千个可能的解。通常，初始种群是随机生成的，允许所有可能的解(搜索空间)。有时候，解可能会在有可能找到最佳解决方案的地区被“播种”。

==== Selection ====

==== 选择 ====

{{Main|Selection (genetic algorithm)}}

{{Main|Selection (genetic algorithm)}}

During each successive generation, a portion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected. Certain selection methods rate the fitness of each solution and preferentially select the best solutions. Other methods rate only a random sample of the population, as the former process may be very time-consuming.

During each successive generation, a portion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected. Certain selection methods rate the fitness of each solution and preferentially select the best solutions. Other methods rate only a random sample of the population, as the former process may be very time-consuming.

在每一个连续的世代中，现有种群的一部分被选中来繁殖新的一代。个人的解决方案是通过基于适应度的过程来选择的，在这个过程中，通常更有可能选择适应度较高的解决方案(用适应度函数来衡量)。某些选择方法评价每个解的适合度，并优先选择最佳解。其他方法只对总体的随机样本进行评分，因为前一个过程可能非常耗时。

在每一个代中，现有种群的一部分 个体被选中来繁殖新的一代。个体的解是通过基于适应度的过程来选择的，在这个过程中，通常更有可能选择适应度较高的解(用适应度函数来衡量)。某些选择方法评价每个解的适合度，并优先选择最佳解。因为这个过程可能非常耗时，所以还有其他方法，只对总体的随机样本进行评分，。

The fitness function is defined over the genetic representation and measures the quality of the represented solution. The fitness function is always problem dependent. For instance, in the knapsack problem one wants to maximize the total value of objects that can be put in a knapsack of some fixed capacity. A representation of a solution might be an array of bits, where each bit represents a different object, and the value of the bit (0 or 1) represents whether or not the object is in the knapsack. Not every such representation is valid, as the size of objects may exceed the capacity of the knapsack. The fitness of the solution is the sum of values of all objects in the knapsack if the representation is valid, or 0 otherwise.

The fitness function is defined over the genetic representation and measures the quality of the represented solution. The fitness function is always problem dependent. For instance, in the knapsack problem one wants to maximize the total value of objects that can be put in a knapsack of some fixed capacity. A representation of a solution might be an array of bits, where each bit represents a different object, and the value of the bit (0 or 1) represents whether or not the object is in the knapsack. Not every such representation is valid, as the size of objects may exceed the capacity of the knapsack. The fitness of the solution is the sum of values of all objects in the knapsack if the representation is valid, or 0 otherwise.

在遗传表示上定义适应度函数，并度量表示解的质量。适应度函数总是依赖于问题。例如，在背包问题中，人们希望最大化可以放入某个固定容量背包的物品的总价值。解决方案的表示形式可以是一个位数组，其中每个位表示一个不同的对象，位(0或1)的值表示对象是否在背包中。并非所有这样的表示都是有效的，因为对象的大小可能超过背包的容量。解的适应性是背包中所有对象的值之和，如果表示是有效的，否则为0。

适应度函数的定义要基于遗传表示的方法，并能够度量解的质量。适应度函数总是依赖于问题。例如，在背包问题中，人们希望最大化可以放入某个固定容量背包的物品的总价值。解决方案的表示形式可以是一个二进制串，其中每个位表示一个不同的对象，位(0或1)的值表示对象是否在背包中。当然并非所有这样的个体都是有效的，因为对象的大小可能超过背包的容量。解的适应性是背包中所有对象的值之和。如果表示无有效（即个体表示的解对应的重量超过了背包最大承载），则为0。

In some problems, it is hard or even impossible to define the fitness expression; in these cases, a simulation may be used to determine the fitness function value of a phenotype (e.g. computational fluid dynamics is used to determine the air resistance of a vehicle whose shape is encoded as the phenotype), or even interactive genetic algorithms are used.

In some problems, it is hard or even impossible to define the fitness expression; in these cases, a simulation may be used to determine the fitness function value of a phenotype (e.g. computational fluid dynamics is used to determine the air resistance of a vehicle whose shape is encoded as the phenotype), or even interactive genetic algorithms are used.

在某些问题中，很难甚至不可能定义适应度表达式; 在这些情况下，模拟可以用来确定表型的适应度函数值(例如:。计算流体力学是用来确定车辆的空气阻力，车辆的形状被编码为显型) ，甚至交互式遗传算法被使用。

在某些问题中，适应度函数很难甚至不可能定义，在这些情况下，可以用模拟来确定个体的适应度(例如，计算流体力学来确定车辆的空气阻力，被编码的是车辆的形状) ，甚至交互式遗传算法也会被用上。