据我所知,进化算法和遗传算法最大的区别之一就是进化算法采用了突变函数来生成新的种群,而遗传算法则采用了交叉函数。
我找到了一个 演化算法 试图通过这样的突变来生成一个目标字符串。
private static double newMutateRate(){
return (((double)perfectFitness - fitness(parent)) / perfectFitness * (1 - minMutateRate));
}
private static String mutate(String parent, double rate){
String retVal = "";
for(int i = 0;i < parent.length(); i++){
retVal += (rand.nextDouble() <= rate) ?
possibilities[rand.nextInt(possibilities.length)]:
parent.charAt(i);
}
return retVal;
}
我写了这个交叉函数来代替突变函数。
private static String crossOver(String parent)
{
String newChild = "";
for(int i = 0; i < parent.length(); i++)
{
if(parent.charAt(i) != target.charAt(i))
newChild += possibilities[rand.nextInt(possibilities.length)];
else
newChild += parent.charAt(i);
}
return newChild;
}
效果很好 但我想知道它是否是一个有效的交叉函数。. 我觉得,从我对遗传算法的经验来看,交叉函数应该比我所写的产生更多的随机种群,换句话说就是知道具体哪位不要改变,似乎几乎就像作弊一样。
不,你的交叉函数不符合这个词的传统意义。交叉应该把基因从 两种 父母。你现在所拥有的更像是一个突变函数。
统一交叉 是一种常见的两个基因组的交叉实现,其中子代得到每个父代的大约50%的基因。这里我假设基因组的长度是固定的。
private String crossover(String parent1, String parent2){
String child = "";
for(int i = 0; i < parent1.length(); i++){
if (rand.nextFloat() >= 0.5){
child += parent1[i];
}
else {
child += parent2[i];
}
}
}
我认为用目标来构造交叉函数是不合适的,但你应该使用当前种群中的两个最好的字符串进行交叉。
下面是这样一个交叉的伪代码:-。
Crossover(String parent1,String parent2) {
for(i=0;i<parent1.length;i++) {
if(parent1[i]==target[i]) {
child[i] = parent1[i]
}
else if(parent2[i]==target[i]) {
child[i] = parent2[i]
}
}
insert remaining elements into child randomly
}
上面的方法叫做贪婪的交叉
我同意Junuxx的观点,我只想补充一点。恰好遗传算法比其他进化算法更倾向于使用交叉运算符,但并不是繁殖运算符让算法具有遗传性! 我发现,割草机的例子很好地解释了这一点(不用担心实现代码,看解释就可以了)。