进化计算是基于自然选择和自然遗传等生物进化机制的一种搜索算法。与普通的搜索方法一样，进化计算也是一种迭代算法，不同的是进化计算在最优解的搜索过程中，一般是从原问题的一组解出发改进到另一组较好的解，再从这组改进的解出发进一步改进。而且在进化问题中，要求当原问题的优化模型建立后，还必须对原问题的解进行编码。进化计算在搜索过程中利用结构化和随机性的信息，使最满足目标的决策获得最大的生存可能，是一种概率型的算法。
一般来说，进化计算的求解包括以下几个步骤：给定一组初始解；评价当前这组解的性能；从当前这组解中选择一定数量的解作为迭代后的解的基础；再对其进行 *** 作，得到迭代后的解；若这些解满足要求则停止，否则将这些迭代得到的解作为当前解重新 *** 作。
以遗传算法为例，其工作步骤可概括为：
（1） 对工作对象——字符串用二进制的0/1或其它进制字符编码 。
（2） 根据字符串的长度L，随即产生L个字符组成初始个体。
（3） 计算适应度。适应度是衡量个体优劣的标志，通常是所研究问题的目标函数。
（4） 通过复制，将优良个体插入下一代新群体中，体现“优胜劣汰”的原则。
（5） 交换字符，产生新个体。交换点的位置是随机决定的
（6） 对某个字符进行补运算，将字符1变为0，或将0变为1，这是产生新个体的另一种方法，突变字符的位置也是随机决定的。
（7） 遗传算法是一个反复迭代的过程，每次迭代期间，要执行适应度计算、复制、交换、突变等 *** 作，直至满足终止条件。
将其用形式化语言表达，则为：假设α∈I记为个体，I记为个体空间。适应度函数记为Φ：I→R。在第t代，群体P(t)={a1(t),a2(t)，…，an(t)}经过复制r(reproduction)、交换c(crossover)及突变m(mutation)转换成下一代群体。这里r、c、m均指宏算子，把旧群体变换为新群体。L：I→{True, Flase}记为终止准则。利用上述符号，遗传算法可描述为：
t=0
initialize P(0):={ a1(0),a2(0)，…，an(0)}
while(l(P(t))≠True) do
evaluate P(t):{ Φ(a1(t)), Φ(a2(t))，…，Φ(an(t))}
reproduction: P′(t):=r(P(t))
crossover: P″(t):=c(P′(t))
mutation: P(t+1):= m(P″(t))
t=t+1
end
/************************************************/文件名：Classifier.h
#ifndef CLASSIFIER_H
#define CLASSIFIER_H
#include <iostream>
#include <stdio.h>
#define SELF0
#define NONSELF 1
#define MASKVALUE 2
// detector class
class Detector
{
public:
Detector(const unsigned int length)
Detector::~Detector(void)
unsigned int length
unsigned int *value
double threshold
unsigned int type
void save(FILE *outputStream)
void show(void) { save(stdout)}
}
#endif
/**********************************************/
//文件名：Classifier.cpp
#include "Classifier.h"
// detector class public methods
Detector::Detector(const unsigned int length)
{
this->length = length
threshold = 0.0
value = new unsigned int [length]
type = 0
}
Detector::~Detector(void)
{
delete [] value
}
void Detector::save(FILE *outputStream)
{
register unsigned int i
fprintf(outputStream, \
"%-3d %-.10f %-1d\n", \
length, \
threshold, \
type \
)
for(i = 0i <lengthi++)
fprintf(outputStream, "%-1d ", value[i])
fprintf(outputStream, "\n")
fflush(outputStream)
}
/**********************************************/
//文件名：EvolutionaryAlgorithm.h
#ifndef EVOLUTIONARYALGORITHM_H
#define EVOLUTIONARYALGORITHM_H
#include "Classifier.h"
#include <stdio.h>
// genome class
class Genome
{
public:
Genome(const unsigned int length)
~Genome(void)
unsigned int size
unsigned int *locus
unsigned int type
double mutationProbability
double crossoverProbability
double fitness, scaledFitness
unsigned int thresholdLength, patternLength
double generalityBias
double typeBias
void copyGenome(Genome *genome)
void uniformCrossover(Genome *genome1, Genome *genome2)
void mutateBinary(void)
void randomiseBinary(void)
void setDetector(Detector *detector)
void save(FILE *outputStream)
void show(void) { save(stdout)}
}
// species class
class Species
{
public:
Species(const unsigned int speciesSize, const unsigned int genomeLength)
~Species(void)
unsigned int speciesSize
Genome **genome
unsigned int fittestIndividual
double speciesScaledFitnessSum
double meanSpeciesFitness
Genome *FPSelection(void)
void randomise(void)
void copySpecies(Species *species)
void save(FILE *outputStream)
void show(void) { save(stdout)}
}
#endif
/**********************************************************/
//文件名：EvolutionaryAlgorithm.cpp
#include "EvolutionaryAlgorithm.h"
#include <stdlib.h>
// genome class public methods
Genome::Genome(const unsigned int length)
{
thresholdLength = 8
patternLength = length
size = thresholdLength + 2 * patternLength
locus = new unsigned int [size]
mutationProbability = 2.0 / double(size)
crossoverProbability = 0.6
generalityBias = typeBias = 0.5
fitness = 0.0
type = 0
}
Genome::~Genome(void)
{
delete [] locus
}
void Genome::copyGenome(Genome *genome)
{
register unsigned int i = size
register unsigned int *from = genome->locus
register unsigned int *to = locus
while(i--)
to[i] = from[i]
mutationProbability = genome->mutationProbability
crossoverProbability = genome->crossoverProbability
fitness = genome->fitness
scaledFitness = genome->scaledFitness
generalityBias = genome->generalityBias
size = genome->size
patternLength = genome->patternLength
thresholdLength = genome->thresholdLength
type = genome->type
}
void Genome::uniformCrossover(Genome *genome1, Genome *genome2)
{
register unsigned int i = size
register unsigned int *from1 = genome1->locus
register unsigned int *from2 = genome2->locus
register unsigned int *to = locus
register double cp = crossoverProbability
while(i--)
{
if(drand48() <cp)
to[i] = from1[i]
else
to[i] = from2[i]
}
if(drand48() <cp)
type = genome1->type
else
type = genome2->type
}
void Genome::mutateBinary(void)
{
register unsigned int i = size
register unsigned int *loci = locus
register double mp = mutationProbability
while(i--)
if(drand48() <mp)
loci[i] = 1 - loci[i]
if(drand48() <mp)
type = 1 - type
}
void Genome::randomiseBinary(void)
{
register unsigned int index, i
index = 0
i = thresholdLength
while(i--)
locus[index++] = int((double(rand()) * 2.0) / double(RAND_MAX + 1.0))
i = patternLength
while(i--)
locus[index++] = int((double(rand()) * 2.0) / double(RAND_MAX + 1.0))
i = patternLength
while(i--)
if(drand48() <generalityBias)
locus[index++] = 0
else
locus[index++] = 1
if(drand48() <typeBias)
type = SELF
else
type = NONSELF
}
void Genome::save(FILE *outputStream)
{
register unsigned int i
Detector *detector = new Detector(patternLength)
fprintf(outputStream, \
"%-3d %-3d %-3d %-1d %-10f %-10f %-10f %-10f %-10f %-10f\n", \
size, \
thresholdLength, \
patternLength, \
type, \
fitness, \
scaledFitness, \
mutationProbability, \
crossoverProbability, \
generalityBias, \
typeBias \
)
for(i = 0i <sizei++)
fprintf(outputStream, "%-2d ", locus[i])
fprintf(outputStream, "\n")
setDetector(detector)
detector->save(outputStream)
delete detector
fflush(outputStream)
}
void Genome::setDetector(Detector *detector)
{
register unsigned int i, loci = 0, sum, lastLoci
// set activation threshold
// gray coding for threshold gene
sum = lastLoci = locus[loci++]
while(loci <thresholdLength)
{
sum = (sum <<1) | (lastLoci ^ locus[loci])
lastLoci = locus[loci++]
}
detector->threshold = double(sum) / 255.0// !!!!!!!!!!!!!!!!!!!!
for(i = 0i <patternLengthi++)
detector->value[i] = locus[loci++]
for(i = 0i <patternLengthi++)
if(!locus[loci++])
detector->value[i] = MASKVALUE
detector->type = type
detector->length = patternLength
}
// species class public methods
Species::Species(const unsigned int speciesSize, \
const unsigned int genomeLength)
{
register unsigned int i = speciesSize
this->speciesSize = speciesSize
fittestIndividual = 0
speciesScaledFitnessSum = meanSpeciesFitness = 0.0
genome = new Genome * [speciesSize]
while(i--)
genome[i] = new Genome(genomeLength)
}
Species::~Species(void)
{
register unsigned int i = speciesSize
while(i--)
delete genome[i]
delete genome
}
Genome *Species::FPSelection(void)
{
register unsigned int i = 0
register double dtmp1, dtmp2
dtmp1 = drand48() * speciesScaledFitnessSum
dtmp2 = 0.0
while((i <speciesSize) &&((dtmp2 = dtmp2 + genome[i]->scaledFitness) \
<dtmp1))
i++
return((i <speciesSize) ? genome[i] : genome[i - 1])
}
void Species::randomise(void)
{
register unsigned int i = speciesSize
while(i--)
genome[i]->randomiseBinary()
}
void Species::save(FILE *outputStream)
{
fprintf(outputStream, \
"%-4d %-4d %-5.10f %-.10f\n", \
speciesSize, \
fittestIndividual, \
speciesScaledFitnessSum, \
meanSpeciesFitness \
)
genome[fittestIndividual]->save(outputStream)
fflush(outputStream)
}
void Species::copySpecies(Species *species)
{
register unsigned int i = species->speciesSize
speciesSize = i
while(i--)
genome[i]->copyGenome(species->genome[i])
fittestIndividual = species->fittestIndividual
speciesScaledFitnessSum = species->speciesScaledFitnessSum
meanSpeciesFitness = species->meanSpeciesFitness
}
//补充了下，刚才少了个Classifier.cpp。
进化计算的三大分支包括：遗传算法(Genetic Algorithm ，简称GA)、进化规划(Evolu-tionary Programming，简称EP)和进化策略(Evolution Strategies ，简称ES)。这三个分支在算法实现方面具有一些细微的差别，但它们具有一个共同的特点，即都是借助生物进化的思想和原理来解决实际问题。
遗传算法是一类通过模拟生物界自然选择和自然遗传机制的随机化搜索算法，由美国Holand J教授于1975年首次提出。它是利用某种编码技术作用于称为染色体的二进制数串，其基本思想是模拟由这些串组成的种群的进化过程，通过有组织的、然而是随机的信息交换来重新组合那些适应性好的串。遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并根据适应性来选择染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。遗传算法尤其适用于处理传统搜索方法难于解决的复杂的非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪有关智能计算中的关键技术之一。
1964年，由德国柏林工业大学的RechenbergI等人提出。在求解流体动力学柔性弯曲管的形状优化问题时，用传统的方法很难在优化设计中描述物体形状的参数，然而利用生物变异的思想来随机地改变参数值并获得了较好效果。随后，他们便对这种方法进行了深入的研究和发展，形成了进化计算的另一个分支——进化策略。
进化策略与遗传算法的不同之处在于：进化策略直接在解空间上进行 *** 作，强调进化过程中从父体到后代行为的自适应性和多样性，强调进化过程中搜索步长的自适应性调节而遗传算法是将原问题的解空间映射到位串空间之中，然后再施行遗传 *** 作，它强调个体基因结构的变化对其适应度的影响。
进化策略主要用于求解数值优化问题。
进化规划的方法最初是由美国人Fogel LJ等人在20世纪60年代提出的。他们在人工智能的研究中发现，智能行为要具有能预测其所处环境的状态，并按照给定的目标做出适当的响应的能力。在研究中，他们将模拟环境描述成是由有限字符集中符号组成的序列。
进化算法与传统的算法具有很多不同之处，但其最主要的特点体现在下述两个方面：
进化计算的智能性包括自组织、自适应和自学习性等。应用进化计算求解问题时，在确定了编码方案、适应值函数及遗传算子以后，算法将根据“适者生存、不适应者淘汰"的策略，利用进化过程中获得的信息自行组织搜索，从而不断地向最佳解方向逼近。自然选择消除了传统算法设计过程中的-一个最大障碍：即需要事先描述问题的全部特点，并说明针对问题的不同特点算法应采取的措施。于是，利用进化计算的方法可以解决那些结构尚无人能理解的复杂问题。
进化计算的本质并行性表现在两个方面：
一是进化计算是内在并行的，即进化计算本身非常适合大规模并行。
二是进化计算的内含并行性，由于进化计算采用种群的方式组织搜索，从而它可以同时搜索解空间内的多个区域，并相互交流信息，这种搜索方式使得进化计算能以较少的计算获得较大的收益。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）