实现 AI 进化二元分布算法来解决数值逼近问题
4.92/5 (80投票s)
本文演示了用于查找数组 N 个元素中给定值 x 的“最近”邻近值的 AI 二进制分布进化算法的 C++ 代码。
引言
“进化不断创新，但在每个层面上，它都保留了用于产生创新的要素。”-约翰·H·霍兰德
“进化不断创新，但在每个层面上，它都保留了用于产生创新的要素。”-约翰·H·霍兰德
有时，在模拟建模、模仿现实世界模型，如流程时间线和资源调度、在统计编程中解决搜索优化和分类问题、在数字信号编码/解码（电信）中提供过滤、设计图形图像识别应用程序，甚至开发游戏时，我们通常需要使用“灵活”计算的范式，由进化计算策略提供，以实现寻找问题各种变体的非线性启发式算法，而不是使用保证找到单个平凡问题解决方案的经典线性方法，而后者在大多数情况下可能无法满足优化标准。在本文中，我们将讨论一种实现元启发式非线性 AI 进化搜索算法 (EA) 的最常见场景，该算法旨在解决微积分拓扑近似问题，即找到给定值 x 的“最近”局部邻近值 
在大多数情况下，寻找最近邻值的微积分拓扑近似问题通过使用公式 (1, 2) 进行适当计算即可轻松解决，但遗憾的是，在某些情况下，局部邻近值 
在编程中，我们通常将向量 
-
经典非启发式算法通常通过对所有可能的问题解进行线性遍历，找到近似问题的唯一一个平凡计算解决方案。通常，使用经典的线性算法，我们会将遇到的第一个满足搜索条件的解视为上述优化问题最可行的解决方案；
-
经典非启发式遍历算法在大多数情况下是“固定的”。这意味着我们无法在不修改算法的情况下找到
和
。我们通常需要多次遍历解的数组来找到
作为现有线性遍历算法的替代方案，本文后续章节中描述的算法实现主要基于进化编程 (EP) 概念，并通过提供通过灵活计算获得的优化问题解决方案的多样性来实现更有效的解决方案。此外，它提高了整体性能和生产力，但有时需要额外的资源来进行复杂的数据处理。
背景
所设计的进化算法的主要目标是找到优化后的端点值 
x = 0000 1110 = 14，
通常，如果一个染色体代表一个区间，并且该区间是 x 值所在区间的子集 
上述算法中最关键的阶段是选择最适合的染色体，使其能够在模拟进化过程的每个连续代繁殖新种群。让我们回顾一下，经典的遗传算法 (GA) 为了选择最适合的染色体，通常使用各种方法，例如随机锦标赛或适应度比例选择 (SCX)，其中决定哪些染色体被视为最适合的，是基于计算整个种群中每个染色体的适应度函数。为此，通常使用随机概率或比例因子适应度函数。同样，现有的进化算法会对两个或更多选定的最适合的染色体执行交叉和变异，以繁殖下一代进化过程的新“后代”种群，为线性近似问题提供新的解决方案多样性。在遗传编程 (GP) 中，当我们需要优化某个具有参数向量和多个优化标准的线性函数 
作为现有遗传编程方法的替代方案，本文将讨论进化二进制分布选择算法，该算法为寻找给定参数值 x 的最近邻值问题提供了更有效的解决方案。该算法不使用随机的随机选择方法以及执行经典的交叉和变异，而是实现二进制分布选择过程和二进制重组（交叉）来繁殖问题的后代解候选的新种群。使用二进制分布选择算法确保在有限数量的代数中找到 x 的最近邻值，与现有的选择和重组方法相比，这在模拟进化过程的整体成本效益和性能方面具有优势。与通常在交叉和选择之前执行选择过程的经典遗传算法不同，在下面讨论的算法中，我们将这两个过程合并为一个过程，以找到线性近似问题的优化解决方案。根据提出的算法的总体思想，二进制选择过程的结果是将每个“父代”染色体种群重组为两个新的后代种群，方法是将最适合和最不适合的染色体分配给这两个种群。与通常为一对或多对随机选择的染色体执行交叉和变异的经典遗传算法不同，二进制分布选择通常对属于某个进化代的所有染色体种群执行，并且主要基于使用施加到每个染色体上的“基因”的标准对特定染色体进行分类。最适合的染色体种群代表优化问题的多个条件，而最不适合的染色体种群将其基因传递给种群，这些种群随后也可以在模拟进化过程的下一代中被确定为最适合的。
现在，让我们仔细看看下面讨论的算法实现的二进制选择过程。在选择过程中，我们遍历种群数组，检索每个种群。对于数组中的每个种群，我们最初会检查当前种群是否是最终的后代种群，由一个最适合的“精英”染色体组成，该染色体在其条件编码基因位设置为 1，其位置与参数值 x 的最高有效数字 (MSD) 的位置完全匹配。如果是，我们将该染色体附加到最终的后代目标种群，我们将进一步在该种群中执行线性搜索 x 的最近邻值。否则，我们将继续对每个染色体种群执行二进制分布选择。在二进制分布选择期间，我们实际上执行当前种群的线性遍历，对于每个表示位序列的染色体，我们验证其条件编码位在当前世代的当前基因座位置是否设置为“1”。我们通常通过使用以下按位运算来完成
#define digit(r,n) (r & (1 << n)) ? 1 : 0
如果是，则该染色体被认为是最适合的，我们将它附加到最适合染色体种群。否则，如果基因编码位设置为“0”，我们将该染色体附加到最不适合染色体种群。实际上，以下选择过程是将特定染色体进行二进制分布重组以繁殖进化过程下一代的后代种群的过程。图 3a、b 说明了该算法实现的选择过程。
在二进制重组过程中，每个选定的染色体将其基因传递给属于下一进化代的两个新后代种群的染色体。因此，最不适合的染色体在下一代进化过程中成为最适合的，反之亦然。实现的重组过程实际上是在最适合或最不适合的后代种群之间进行的二进制分布，这是基于确定哪些染色体编码当前进化代施加的问题条件，因此是最适合的。在二进制重组过程之后，我们得到了两个新的最适合或最不适合染色体的后代种群，我们计算下一代的新的基因座位置，并将其与两个新的后代种群相关联。最后，我们将这两个新种群附加到种群数组。在此之后，我们递归地从种群数组中获取下一个种群，并执行上述类似任务。实际上，我们递归地执行选择，直到我们达到种群数组中的最后一个种群。执行二进制分布选择和重组的结果是，我们得到一个“精英”染色体种群，它们实际上是可行的问题解决方案候选。二进制分布选择过程的框图如图 3c 所示。
上面讨论的进化算法的最后阶段是寻找参数值 x 的最近邻值 
使用代码
以下代码部分执行进化二进制分布选择操作，通过生成属于下一代的新的“子代”染色体种群并将它们附加到染色体数组中。此操作对每个种群执行，直到生成最终的后代种群。
template <typename Ty = int>
void gene_selection(_GENE_POPULATION*& _population, Ty val)
{
// Initializing the _lsd and _msd variables
int _lsd = 0, _msd = _lsd;
get_gene_locuses(val, _lsd, _msd);
// Extracting the phenotype value
int _gene_phenotype =
get_gene_phenotype(val, _lsd, _msd);
// Initializing the chromosome population index variable
unsigned long _pop_index = 0;
// Initializing the new breed chromosome population n_pop_index variable
unsigned long n_pop_index = _pop_index + 1;
// We're iterating through the array of chromosome populations and retrieving
// each population, belonging to a certain epoch, from the array of populations.
// To generate the new offspring populations, we're performing binary distribution
// selection for each particular population in the array of populations.
// The iteration proceeds until we've retrieved the last population in the array
while (_population[_pop_index].m_pop_size > 0)
{
int _gene_index = 0; //
int _w_pop_index = 0; //
int _s_pop_index = 0; //
int _gene_pos = _population[_pop_index].m_gene_pos;
int _gene_s[_GENE_POOL_SIZE] = { 0 },
_gene_w[_GENE_POOL_SIZE] = { 0 };
// For each chromosome population from the array of populations we're performing
// the binary distribution selection by fetching each chromosome from the current
// population and testing if a particular chromosome has its condition "gene"
// encoding bit is set to "1" at the current position of locus.
while (_gene_index < _population[_pop_index].m_pop_size && _gene_pos >= 0)
{
// For each particular chromosome represented as a sequence of bits,
// we're performing check if its encoding bit is set to "1" at the
// current locus position for a certain epoch.
if (digit(_population[_pop_index].m_gene_ptr[_gene_index].m_val, _gene_pos))
// if so, we're appending the current chromosome's value, that
// to the array of the most fittest chromosomes _gene_s
_gene_s[_s_pop_index++] =
_population[_pop_index].m_gene_ptr[_gene_index].m_val;
// Otherwise, we're appending the current chromosome array of
// the least fittest chromosomes _gene_w
else _gene_w[_w_pop_index++] =
_population[_pop_index].m_gene_ptr[_gene_index].m_val;
_gene_index++; // Fetching the next chromosome
}
// if the size value of the _gene_s array is greater than zero
// (e.g. the array is not empty), we're appending the most
// fittest population to the array of populations.
if (_s_pop_index > 0)
{
// assigning the value of fitness
_population[n_pop_index].m_gene_fit = 1;
// assigning the value of population size
_population[n_pop_index].m_pop_size = _s_pop_index;
// Obtaining the position value of the condition encoding bit for the next epoch
// and assigning it to the m_gene_pos variable for the new chromosome population
_population[n_pop_index].m_gene_pos = _population[_pop_index].m_gene_pos - 1;
// appending new offspring the most fittest chromosomes population
// to the array of populations
gene_copy(_population[n_pop_index].m_gene_ptr, _gene_s, _s_pop_index);
n_pop_index++;
}
// if the size value of the _gene_s array is greater than zero
// (e.g. the array is not empty), we're appending the least fittest
// population to the array of populations.
if (_w_pop_index > 0)
{
// assigning the value of fitness
_population[n_pop_index].m_gene_fit = 0;
// assigning the value of population size
_population[n_pop_index].m_pop_size = _w_pop_index;
// Obtaining the position value of the condition encoding bit for the next epoch
// and assigning it to the m_gene_pos variable for the new chromosome population
_population[n_pop_index].m_gene_pos = _population[_pop_index].m_gene_pos - 1;
// appending new offspring the least fittest chromosomes population
// to the array of populations
gene_copy(_population[n_pop_index].m_gene_ptr, _gene_w, _w_pop_index);
n_pop_index++;
}
_pop_index++; // Proceed with the next population
}
}
此函数执行线性搜索以查找由单个染色体组成的特定种群。它将找到的染色体附加到最终后代染色体群的整数目标数组中。
int gene_quantum_population(const _GENE_POPULATION* _population,
_GENE_POPULATION*& _population_target, int msd)
{
// Initialize the array of the final offspring population
if (_population_target == NULL)
{
_population_target =
new _GENE_POPULATION[_GENE_POPULATION_SIZE];
memset((void*)_population_target, 0x00,
sizeof(_GENE_POPULATION)* _GENE_POPULATION_SIZE);
}
int nindex = 0; // Assign the value to the populations index variable
// Iterating through the array of populations and performing the check
// if the position of the current population's condition encoding bit exactly
// matches the most significant digit (MSD) position of the parameter value of x
for (int index = 0; _population[index].m_pop_size > 0; index++)
// If the current population contains the only one chromosome and its
// condition encoding bit is set to 1 at the position of MSD of the parameter
// value of x, we are appending the current chromosome to the target
// array of the "elite" chromosomes.
if (_population[index].m_gene_pos == -1 &&
_population[index].m_gene_ptr[0].m_msd == msd)
{
_population_target[nindex].m_gene_fit = _population[index].m_gene_fit;
_population_target[nindex].m_gene_pos = _population[index].m_gene_pos;
_population_target[nindex].m_pop_size = _population[index].m_pop_size;
_population_target[nindex++].m_gene_ptr = &_population[index].m_gene_ptr[0];
}
return nindex;
}
这两个 C++ 例程使用基于显型匹配标准以及 x 值条件的线性搜索，对最终后代染色体的结果目标数组进行线性搜索。
template <typename Ty = int>
Ty gene_find_minimum(Ty val, const _GENE_POPULATION* _population)
{
int _lsd = get_gene_lsd(val); // Get the least significant digit value of x
int _msd = get_gene_msd(val); // Get the most significant digit value of x
// Retrieving the phenotype value for the given value of x
int _gene_phenotype =
get_gene_phenotype(val, _lsd, _msd);
// For each successive condition encoding gene locus position, we're performing
// the linear search of the minumum x_min nearest neighbor value for the given
// parameter value of x.
for (int _gene_msd = _msd; _gene_msd >= 0; _gene_msd--)
{
_GENE_POPULATION* _population_target = NULL;
// Retrieving the target array of chromosomes values that
// belong to the final offspring population
int size = gene_quantum_population(_population, _population_target, _gene_msd);
// Iterating through the target array of the most fittest chromosomes starting
// from the first chromosome in the target population.
for (int index = 0; index < size; index++)
{
// Retrieving the phenotype value for the current chromosome
int _schema = get_gene_phenotype(_population_target[index].m_gene_ptr[0].m_val, _lsd, _gene_msd);
// Test if the value of phenotype for the current chromosome is less than the
// value of phenotype for the parameter value of x.If so, the current chromosome's
// value is the minimum x_min nearest neighbor value for given parameter value of x.
if (_schema < _gene_phenotype && val != _population_target[index].m_gene_ptr[0].m_val)
// Now, we return this value to the calling routine.
return _population_target[index].m_gene_ptr[0].m_val;
}
// If no neighbor value is found, than will proceed of finding the minimum nearest
// neighbor x_min of the parameter value of x for the next encoding gene's locus position.
}
return -1;
}
template <typename Ty = int>
Ty gene_find_maximum(Ty val, const _GENE_POPULATION* _population)
{
int _lsd = get_gene_lsd(val); // Get the least significant digit value of x
int _msd = get_gene_msd(val); // Get the most significant digit value of x
// Retrieving the phonome value for the given value of x
int _gene_phenotype =
get_gene_phenotype(val, _lsd, _msd);
int _gene_msd = _msd;
// For each successive condition encoding gene locus position, we're performing
// the linear search of the maximum x_max nearest neighbor value for the given
// parameter value of x.
while (_gene_msd <= _gene_population[0].m_gene_pos)
{
_GENE_POPULATION* _population_target = NULL
// Retrieving the target array of chromosomes values that
// belong to the final offspring population
int size = gene_quantum_population(_population, _population_target, _gene_msd);
// Iterating through the target array of the most fittest chromosomes starting
// from the first chromosome in the target population.
for (int index = size - 1; index >= 0; index--)
{
// Retrieving the phenome value of the current chromosome
int _schema = get_gene_phenotype(_population_target[index].m_gene_ptr[0].m_val, _lsd, _gene_msd);
// Test if the value of phenotype for the current chromosome is greater or equal to
// the value of phenotype for the parameter value of x.If so, the current chromosome's
// value is the maximum x_max nearest neighbor value for given parameter value of x.
if (_schema >= _gene_phenotype && val != _population_target[index].m_gene_ptr[0].m_val)
// Now, we return this value to the calling routine.
return _population_target[index].m_gene_ptr[0].m_val;
}
// If no neighbor value is found, than will proceed of finding the maximum nearest
// neighbor x_max of the parameter value of x for the next encoding gene's locus position.
_gene_msd++;
}
return -1;
}
输出
这是本文附带的 C++ 代码提供的调试输出。
{ 6 16 5 44 8 12 3 15 2 76 9 18 } val = 11
{ 6 16 5 44 8 12 3 15 2 76 9 18 } pop = 0 fit = 1 pos = 6 size = 12
6 = ( 0000 0110 ) lsd = 1 msd = 2
16 = ( 0001 0000 ) lsd = 4 msd = 4
5 = ( 0000 0101 ) lsd = 0 msd = 2
44 = ( 0010 1100 ) lsd = 2 msd = 5
8 = ( 0000 1000 ) lsd = 3 msd = 3
12 = ( 0000 1100 ) lsd = 2 msd = 3
3 = ( 0000 0011 ) lsd = 0 msd = 1
15 = ( 0000 1111 ) lsd = 0 msd = 3
2 = ( 0000 0010 ) lsd = 1 msd = 1
76 = ( 0100 1100 ) lsd = 2 msd = 6
9 = ( 0000 1001 ) lsd = 0 msd = 3
18 = ( 0001 0010 ) lsd = 1 msd = 4
{ 76 } pop = 1 fit = 1 pos = 5 size = 1
76 = ( 0100 1100 ) lsd = 2 msd = 6
{ 6 16 5 44 8 12 3 15 2 9 18 } pop = 2 fit = 0 pos = 5 size = 11
6 = ( 0000 0110 ) lsd = 1 msd = 2
16 = ( 0001 0000 ) lsd = 4 msd = 4
5 = ( 0000 0101 ) lsd = 0 msd = 2
44 = ( 0010 1100 ) lsd = 2 msd = 5
8 = ( 0000 1000 ) lsd = 3 msd = 3
12 = ( 0000 1100 ) lsd = 2 msd = 3
3 = ( 0000 0011 ) lsd = 0 msd = 1
15 = ( 0000 1111 ) lsd = 0 msd = 3
2 = ( 0000 0010 ) lsd = 1 msd = 1
9 = ( 0000 1001 ) lsd = 0 msd = 3
18 = ( 0001 0010 ) lsd = 1 msd = 4
{ 76 } pop = 3 fit = 0 pos = 4 size = 1
76 = ( 0100 1100 ) lsd = 2 msd = 6
{ 44 } pop = 4 fit = 1 pos = 4 size = 1
44 = ( 0010 1100 ) lsd = 2 msd = 5
{ 6 16 5 8 12 3 15 2 9 18 } pop = 5 fit = 0 pos = 4 size = 10
6 = ( 0000 0110 ) lsd = 1 msd = 2
16 = ( 0001 0000 ) lsd = 4 msd = 4
5 = ( 0000 0101 ) lsd = 0 msd = 2
8 = ( 0000 1000 ) lsd = 3 msd = 3
12 = ( 0000 1100 ) lsd = 2 msd = 3
3 = ( 0000 0011 ) lsd = 0 msd = 1
15 = ( 0000 1111 ) lsd = 0 msd = 3
2 = ( 0000 0010 ) lsd = 1 msd = 1
9 = ( 0000 1001 ) lsd = 0 msd = 3
18 = ( 0001 0010 ) lsd = 1 msd = 4
{ 76 } pop = 6 fit = 0 pos = 3 size = 1
76 = ( 0100 1100 ) lsd = 2 msd = 6
{ 44 } pop = 7 fit = 0 pos = 3 size = 1
44 = ( 0010 1100 ) lsd = 2 msd = 5
{ 16 18 } pop = 8 fit = 1 pos = 3 size = 2
16 = ( 0001 0000 ) lsd = 4 msd = 4
18 = ( 0001 0010 ) lsd = 1 msd = 4
{ 6 5 8 12 3 15 2 9 } pop = 9 fit = 0 pos = 3 size = 8
6 = ( 0000 0110 ) lsd = 1 msd = 2
5 = ( 0000 0101 ) lsd = 0 msd = 2
8 = ( 0000 1000 ) lsd = 3 msd = 3
12 = ( 0000 1100 ) lsd = 2 msd = 3
3 = ( 0000 0011 ) lsd = 0 msd = 1
15 = ( 0000 1111 ) lsd = 0 msd = 3
2 = ( 0000 0010 ) lsd = 1 msd = 1
9 = ( 0000 1001 ) lsd = 0 msd = 3
{ 76 } pop = 10 fit = 1 pos = 2 size = 1
76 = ( 0100 1100 ) lsd = 2 msd = 6
{ 44 } pop = 11 fit = 1 pos = 2 size = 1
44 = ( 0010 1100 ) lsd = 2 msd = 5
{ 16 18 } pop = 12 fit = 0 pos = 2 size = 2
16 = ( 0001 0000 ) lsd = 4 msd = 4
18 = ( 0001 0010 ) lsd = 1 msd = 4
{ 8 12 15 9 } pop = 13 fit = 1 pos = 2 size = 4
8 = ( 0000 1000 ) lsd = 3 msd = 3
12 = ( 0000 1100 ) lsd = 2 msd = 3
15 = ( 0000 1111 ) lsd = 0 msd = 3
9 = ( 0000 1001 ) lsd = 0 msd = 3
{ 6 5 3 2 } pop = 14 fit = 0 pos = 2 size = 4
6 = ( 0000 0110 ) lsd = 1 msd = 2
5 = ( 0000 0101 ) lsd = 0 msd = 2
3 = ( 0000 0011 ) lsd = 0 msd = 1
2 = ( 0000 0010 ) lsd = 1 msd = 1
{ 76 } pop = 15 fit = 1 pos = 1 size = 1
76 = ( 0100 1100 ) lsd = 2 msd = 6
{ 44 } pop = 16 fit = 1 pos = 1 size = 1
44 = ( 0010 1100 ) lsd = 2 msd = 5
{ 16 18 } pop = 17 fit = 0 pos = 1 size = 2
16 = ( 0001 0000 ) lsd = 4 msd = 4
18 = ( 0001 0010 ) lsd = 1 msd = 4
{ 12 15 } pop = 18 fit = 1 pos = 1 size = 2
12 = ( 0000 1100 ) lsd = 2 msd = 3
15 = ( 0000 1111 ) lsd = 0 msd = 3
{ 8 9 } pop = 19 fit = 0 pos = 1 size = 2
8 = ( 0000 1000 ) lsd = 3 msd = 3
9 = ( 0000 1001 ) lsd = 0 msd = 3
{ 6 5 } pop = 20 fit = 1 pos = 1 size = 2
6 = ( 0000 0110 ) lsd = 1 msd = 2
5 = ( 0000 0101 ) lsd = 0 msd = 2
{ 3 2 } pop = 21 fit = 0 pos = 1 size = 2
3 = ( 0000 0011 ) lsd = 0 msd = 1
2 = ( 0000 0010 ) lsd = 1 msd = 1
{ 76 } pop = 22 fit = 0 pos = 0 size = 1
76 = ( 0100 1100 ) lsd = 2 msd = 6
{ 44 } pop = 23 fit = 0 pos = 0 size = 1
44 = ( 0010 1100 ) lsd = 2 msd = 5
{ 18 } pop = 24 fit = 1 pos = 0 size = 1
18 = ( 0001 0010 ) lsd = 1 msd = 4
{ 16 } pop = 25 fit = 0 pos = 0 size = 1
16 = ( 0001 0000 ) lsd = 4 msd = 4
{ 15 } pop = 26 fit = 1 pos = 0 size = 1
15 = ( 0000 1111 ) lsd = 0 msd = 3
{ 12 } pop = 27 fit = 0 pos = 0 size = 1
12 = ( 0000 1100 ) lsd = 2 msd = 3
{ 8 9 } pop = 28 fit = 0 pos = 0 size = 2
8 = ( 0000 1000 ) lsd = 3 msd = 3
9 = ( 0000 1001 ) lsd = 0 msd = 3
{ 6 } pop = 29 fit = 1 pos = 0 size = 1
6 = ( 0000 0110 ) lsd = 1 msd = 2
{ 5 } pop = 30 fit = 0 pos = 0 size = 1
5 = ( 0000 0101 ) lsd = 0 msd = 2
{ 3 2 } pop = 31 fit = 1 pos = 0 size = 2
3 = ( 0000 0011 ) lsd = 0 msd = 1
2 = ( 0000 0010 ) lsd = 1 msd = 1
{ 76 } pop = 32 fit = 0 pos = -1 size = 1
76 = ( 0100 1100 ) lsd = 2 msd = 6
{ 44 } pop = 33 fit = 0 pos = -1 size = 1
44 = ( 0010 1100 ) lsd = 2 msd = 5
{ 18 } pop = 34 fit = 0 pos = -1 size = 1
18 = ( 0001 0010 ) lsd = 1 msd = 4
{ 16 } pop = 35 fit = 0 pos = -1 size = 1
16 = ( 0001 0000 ) lsd = 4 msd = 4
{ 15 } pop = 36 fit = 1 pos = -1 size = 1
15 = ( 0000 1111 ) lsd = 0 msd = 3
{ 12 } pop = 37 fit = 0 pos = -1 size = 1
12 = ( 0000 1100 ) lsd = 2 msd = 3
{ 9 } pop = 38 fit = 1 pos = -1 size = 1
9 = ( 0000 1001 ) lsd = 0 msd = 3
{ 8 } pop = 39 fit = 0 pos = -1 size = 1
8 = ( 0000 1000 ) lsd = 3 msd = 3
{ 6 } pop = 40 fit = 0 pos = -1 size = 1
6 = ( 0000 0110 ) lsd = 1 msd = 2
{ 5 } pop = 41 fit = 1 pos = -1 size = 1
5 = ( 0000 0101 ) lsd = 0 msd = 2
{ 3 } pop = 42 fit = 1 pos = -1 size = 1
3 = ( 0000 0011 ) lsd = 0 msd = 1
{ 2 } pop = 43 fit = 0 pos = -1 size = 1
2 = ( 0000 0010 ) lsd = 1 msd = 1
min val = 9
max val = 12
关注点
基本上，本文所述的进化算法可用于以下目的，例如 AI 反向传播神经网络中使用的归一化函数，它可以避免由于突触权重过小或过大而导致的神经网络瘫痪。此外，该算法可用于微积分，以解决在 0 进化算法 – 基于搜索的启发式算法，通过模仿自然进化过程（如自然选择、交叉和变异等）来寻找特定微积分问题的优化解集。进化算法在编程中通常用作线性搜索算法的替代方案。 染色体 – “基因”的有序序列。在进化编程中，“染色体”是整数值的位特征，通常表示为特定微积分问题编码的优化条件。 基因 – “染色体”的个体粒子，可以编码为“0”或“1”位，代表最不可能和最可能 fitter 的基因。每个染色体包含固定数量的位。 种群 – 属于同一代、能够繁殖新子种群的“染色体”的“池”。“种群”通常代表微积分问题的可能整数解的数组。 池 – 一个整数值数组，代表特定“种群”的“染色体”。 基因座 – “染色体”中特定“基因”的位置。基因座是执行“交叉和变异”繁殖操作的点。每个染色体可能包含一个或多个基因座。基因座通常表示为整数二进制值中的适当位位置。 选择 – 一个过程，用于查找在“基因座”的每个位置具有相似“基因”的“染色体”。在进化算法中，选择作为在线性整数数组中的线性搜索操作执行。 交叉和变异 – 在两个或多个父代“染色体”上执行的基本进化操作，通过交换或转换染色体几个部分中的基因来繁殖新的子代种群。 适应度函数 – 允许确定种群中特定“染色体”执行“交叉和变异”操作的适应度的函数。 按位运算 – 对特定整数值的每个位执行的操作。按位运算包括 AND (&)、OR (|)、XOR (|)、INV(~)、NOT(!) 操作。 最高有效数字 (MSD) – “染色体”位序列中的最高位（例如，最后一个出现的位 - “1”），通常表示最可能 fitter 的解决方案。 最低有效数字 (MSD) – “染色体”位序列中的最低位（例如，第一个出现的位 - “1”），通常表示最不可能 fitter 的解决方案。 Benjamin Doerr, Edda Happ, Christian Klein。交叉在进化计算中可以被证明是有用的。理论计算机科学杂志，第 425 卷，2012 年 3 月。 Borhan Kazimipour, Xiaodong Li, A. K. Qin。进化算法种群初始化技术综述。计算机科学与信息技术学院，皇家墨尔本理工大学，墨尔本，3000，维多利亚，澳大利亚。东南大学自动化学院，中国南京，210096，2015 年 6 月。 Jacqueline A. Jones, Keith Harrow. C语言问题求解 (Problem solving with C). Brooklyn College of the City University of New York. Scott/Jones Inc. Publishers, El Granada, CA, 94018, USA B. W. Kernighan and D. M. Ritchie C语言程序设计 (The C Programming Language) Prentice Hall 1978, ISBN 0-13-110163-3. 附录
参考文献
历史