Генетическая эволюция строк в Java
В конечном счете, я пытаюсь создать генетический алгоритм, который будет развивать строку, которая соответствует целевой строке. У меня нет обычного фона кодирования, поэтому мой код будет очень грязным. Вот мой полный код.
public class Main {
public static double similarity(String s1, String s2) {
String longer = s1, shorter = s2;
if (s1.length() < s2.length()) { // longer should always have greater
// length
longer = s2;
shorter = s1;
}
int longerLength = longer.length();
if (longerLength == 0) {
return 1.0;
/* both strings are zero length */ }
/*
* // If you have StringUtils, you can use it to calculate the edit
* distance: return (longerLength -
* StringUtils.getLevenshteinDistance(longer, shorter)) / (double)
* longerLength;
*/
return (longerLength - editDistance(longer, shorter)) / (double) longerLength;
}
public static int editDistance(String s1, String s2) {
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
int[] costs = new int[s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
int lastValue = i;
for (int j = 0; j <= s2.length(); j++) {
if (i == 0)
costs[j] = j;
else {
if (j > 0) {
int newValue = costs[j - 1];
if (s1.charAt(i - 1) != s2.charAt(j - 1))
newValue = Math.min(Math.min(newValue, lastValue), costs[j]) + 1;
costs[j - 1] = lastValue;
lastValue = newValue;
}
}
}
if (i > 0)
costs[s2.length()] = lastValue;
}
return costs[s2.length()];
}
public static void printSimilarity(String s, String t) {
System.out.println(String.format("%.3f is the similarity between \"%s\" and \"%s\"", similarity(s, t), s, t));
}
private static String getCharForNumber(int i) {
char[] alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ".toCharArray();
if (i > 27) {
return null;
}
return Character.toString(alphabet[i]);
}
public static String generateString(int numChar) {
Random random = new Random();
String randomString = "";
for (int i = 0; i < numChar; i++) {
String temp = getCharForNumber(random.nextInt(27));
randomString += temp;
}
return randomString;
}
public static String returnTwoChildren(String s1, String s2, boolean first) {
// chromosomes
// String s1;
// String s2;
// crossovers
String c1;
String c2;
Random r = new Random();
// get a random indices
int ind1 = r.nextInt(s1.length());
// make sure ind2 > ind1... leaving this part out;
// break both strings into parts like in your picture
String s1part1 = s1.substring(0, ind1);
String s1part2 = s1.substring(ind1);
String s2part1 = s2.substring(0, ind1);
String s2part2 = s2.substring(ind1);
// combine the parts
c1 = s1part1 + s2part2;
c2 = s2part1 + s1part2;
if (first)
return c1;
return c2;
}
Random random;
static String[] population;
static String[] childPopulation;
static String target = "Cat";
public static void createPopulation(int size) {
population = new String[size];
for (int i = 0; i < size; i++) {
population[i] = generateString(3);
// System.out.println(population[i]);
// if (similarity(population[i], target) > 0.3)
// printSimilarity(population[i], target);
}
}
public static void fitness(boolean print) {
for (int i = 0; i < population.length; i++) {
for (int j = i + 1; j < population.length; j++) {
if (similarity(population[j], target) > similarity(population[i], target)) {
String temp = population[i];
population[i] = population[j];
population[j] = temp;
}
}
if (print && similarity(population[i], target) > 0)
System.out.println(population[i] + ", " + similarity(population[i], target));
}
}
public static void createChildPopulation(int size) {
childPopulation = new String[size];
for (int i = 0; i < population.length; i += 2) {
population[i] = returnTwoChildren(population[i], population[i + 1], true);
population[i + 1] = returnTwoChildren(population[i], population[i + 1], false);
}
}
public static void mutate() {
Random random = new Random();
int prob;
String sub1, sub2;
for (int i = 0; i < population.length; i++) {
for (int j = 1; j < population[i].length(); j++) {
prob = random.nextInt(100);
if (prob == 0) {
sub1 = population[i].substring(0, j);
sub2 = population[i].substring(j);
population[i] = sub1 + generateString(1) + sub2;
}
}
}
}
public Main() {
// fightGame(random);
//String string1 = "acbdefghijklmnop";
//String string2 = "1234567891234567";
int populationSize = 80;
createPopulation(populationSize);
boolean print = true;
for (int i = 0; i <= 800; i++) {
if (i % 5 == 0) {
print = true;
System.out.println("Generation: " + i);
}
fitness(print);
if (similarity(population[0], target) == 1.0) {
System.out.println("Succeded! Generation: " + i + " String: " + population[0]);
break;
}
createChildPopulation(populationSize);
mutate();
print = false;
}
// returnTwoChildren(string1, string2);
System.out.println("Done!");
}
public static void main(String[] args) {
new Main();
}
}
Когда я запускаю программу, это нормально для нескольких поколений, а затем, кажется, обнаруживает проблему. Я не знаю, почему строки становятся длиннее (чем три символа). Если бы кто-то мог помочь указать мне на проблему и решение, я был бы чрезвычайно благодарен.
1 ответ
Проблемной является эта часть:
public static void mutate() {
Random random = new Random();
int prob;
String sub1, sub2;
for (int i = 0; i < population.length; i++) {
for (int j = 1; j < population[i].length(); j++) {
prob = random.nextInt(100);
if (prob == 0) {
sub1 = population[i].substring(0, j);
sub2 = population[i].substring(j);
population[i] = sub1 + generateString(1) + sub2;
}
}
}
}
Когда вы нажимаете "= 0", то ваша популяция [i] мутирует, но вместо замены одной буквы вы добавляете одну букву.
Я думаю, что это должно быть:
sub1 = population[i].substring(0, j-1);
вместо
sub1 = population[i].substring(0, j);
Тогда ваши строки будут всегда иметь 3 буквы