遗传算法——我需要什么数据结构?
Genetic Algorithm - what data structure do I need?
我希望在这里允许这样一个开放式的问题。我正在研究一个简单的 GA,它将进化一个字符串输出以匹配给定的目标字符串。因此,每一代都将创建 N 个字符串的群体,每个字符串都将根据其与目标字符串的汉明距离分配一个适应度。然后我需要一些方法来存储和分类这些信息。我在 Processing 工作,但 Java 中的解决方案几乎总是可以通过导入在这种语言中使用。
由于我所追求的是一个模糊的键值结构,我的直觉是我想要某种字典,但我在使用这些方面的经验很少。还有一些复杂情况使我们偏离了我对字典工作原理的理解。我想执行以下操作:
存储每个字符串及其相关的适应度。 这两个必须可以重复。
按值对结构进行排序,即按适合度的降序列出种群。
Trim 人口的底部 50%。可能最简单的方法就是直接用适合种群的后代替换不适合种群
访问时间/计算效率不是特别关心的问题。
昨晚我试图用HashMap解决这个问题,但我一直运行陷入这种结构下不允许重复键等问题,我找不到一种简单的方法来遍历HashMap 并按值仅更改底部 X% 的条目。
总而言之,我需要一个结构,其中每个条目都由一个字符串和一个整数组成,可以存储每个副本,该结构可以按整数值降序排列,因此可以对顶部或底部 X% 的条目进行操作,而不影响休息。
非常感谢您抽出宝贵时间,我们将不胜感激。
有很多方法可以解决这个问题。就个人而言,我会尝试最简单的解决方案。我不知道你的项目的整个背景及其愿景,但是,根据你提供给我们的信息,我发布了我会选择的解决方案。
注意:以下class可能不完整。您可能必须添加更多方法才能更轻松地使用它们。这只是一个解决方案的想法,以代码形式提出,可能对您有用。
Pair
class 建模一对字符串及其适应度值。 Population
class 模拟特定世代的人口。它将其成员保存在列表中并提供操作列表的方法。它还允许重复对。您可以选择总体中的顶部或底部 X
成员并对它们进行操作。
public class Pair implements Comparable<Pair>{
private final String value;
private final int fitness;
public Pair(String value, int fitness) {
this.value = value;
this.fitness = fitness;
}
public String getValue() {
return value;
}
public int getFitness() {
return fitness;
}
@Override
public int compareTo(Pair pair) {
return -Integer.compare(this.fitness, pair.fitness);
}
@Override
public String toString() {
return "Pair{" + "value='" + value + '\'' + ", fitness=" + fitness + '}';
}
}
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
public class Population {
private final List<Pair> members = new ArrayList<>();
public void addMember(Pair pair) {
members.add(pair);
}
public List<Pair> getTop(int x) {
return members.stream().sorted().limit(x).collect(Collectors.toList());
}
public List<Pair> getBottom(int x) {
return members.stream().sorted(Comparator.reverseOrder()).limit(x).collect(Collectors.toList());
}
}
这是一个非综合测试class:
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.List;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
class PopulationTest {
Population population = new Population();
@BeforeEach
void populate() {
population.addMember(new Pair("test", 5));
population.addMember(new Pair("abc", 13));
population.addMember(new Pair("xyz", 8));
population.addMember(new Pair("abc", 20));
}
@Test
void testSortDescending() {
List<Pair> members = population.getTop(4);
for (int i = 0; i < members.size() - 1; i++) {
assertTrue(members.get(i).getFitness() >= members.get(i + 1).getFitness());
}
}
@Test
void testGetTop() {
List<Pair> top = population.getTop(2);
assertEquals(20, top.get(0).getFitness());
assertEquals(13, top.get(1).getFitness());
}
@Test
void testGetBottom() {
List<Pair> bottom = population.getBottom(2);
assertEquals(5, bottom.get(0).getFitness());
assertEquals(8, bottom.get(1).getFitness());
}
}
我希望在这里允许这样一个开放式的问题。我正在研究一个简单的 GA,它将进化一个字符串输出以匹配给定的目标字符串。因此,每一代都将创建 N 个字符串的群体,每个字符串都将根据其与目标字符串的汉明距离分配一个适应度。然后我需要一些方法来存储和分类这些信息。我在 Processing 工作,但 Java 中的解决方案几乎总是可以通过导入在这种语言中使用。
由于我所追求的是一个模糊的键值结构,我的直觉是我想要某种字典,但我在使用这些方面的经验很少。还有一些复杂情况使我们偏离了我对字典工作原理的理解。我想执行以下操作:
存储每个字符串及其相关的适应度。 这两个必须可以重复。
按值对结构进行排序,即按适合度的降序列出种群。
Trim 人口的底部 50%。可能最简单的方法就是直接用适合种群的后代替换不适合种群
访问时间/计算效率不是特别关心的问题。
昨晚我试图用HashMap解决这个问题,但我一直运行陷入这种结构下不允许重复键等问题,我找不到一种简单的方法来遍历HashMap 并按值仅更改底部 X% 的条目。
总而言之,我需要一个结构,其中每个条目都由一个字符串和一个整数组成,可以存储每个副本,该结构可以按整数值降序排列,因此可以对顶部或底部 X% 的条目进行操作,而不影响休息。
非常感谢您抽出宝贵时间,我们将不胜感激。
有很多方法可以解决这个问题。就个人而言,我会尝试最简单的解决方案。我不知道你的项目的整个背景及其愿景,但是,根据你提供给我们的信息,我发布了我会选择的解决方案。
注意:以下class可能不完整。您可能必须添加更多方法才能更轻松地使用它们。这只是一个解决方案的想法,以代码形式提出,可能对您有用。
Pair
class 建模一对字符串及其适应度值。 Population
class 模拟特定世代的人口。它将其成员保存在列表中并提供操作列表的方法。它还允许重复对。您可以选择总体中的顶部或底部 X
成员并对它们进行操作。
public class Pair implements Comparable<Pair>{
private final String value;
private final int fitness;
public Pair(String value, int fitness) {
this.value = value;
this.fitness = fitness;
}
public String getValue() {
return value;
}
public int getFitness() {
return fitness;
}
@Override
public int compareTo(Pair pair) {
return -Integer.compare(this.fitness, pair.fitness);
}
@Override
public String toString() {
return "Pair{" + "value='" + value + '\'' + ", fitness=" + fitness + '}';
}
}
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
public class Population {
private final List<Pair> members = new ArrayList<>();
public void addMember(Pair pair) {
members.add(pair);
}
public List<Pair> getTop(int x) {
return members.stream().sorted().limit(x).collect(Collectors.toList());
}
public List<Pair> getBottom(int x) {
return members.stream().sorted(Comparator.reverseOrder()).limit(x).collect(Collectors.toList());
}
}
这是一个非综合测试class:
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.List;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
class PopulationTest {
Population population = new Population();
@BeforeEach
void populate() {
population.addMember(new Pair("test", 5));
population.addMember(new Pair("abc", 13));
population.addMember(new Pair("xyz", 8));
population.addMember(new Pair("abc", 20));
}
@Test
void testSortDescending() {
List<Pair> members = population.getTop(4);
for (int i = 0; i < members.size() - 1; i++) {
assertTrue(members.get(i).getFitness() >= members.get(i + 1).getFitness());
}
}
@Test
void testGetTop() {
List<Pair> top = population.getTop(2);
assertEquals(20, top.get(0).getFitness());
assertEquals(13, top.get(1).getFitness());
}
@Test
void testGetBottom() {
List<Pair> bottom = population.getBottom(2);
assertEquals(5, bottom.get(0).getFitness());
assertEquals(8, bottom.get(1).getFitness());
}
}