从现有列表创建元素列表

Question

我正在创建一个遗传算法来解决一些特定问题。由于问题很难描述，我写了一个小例子来展示我在做什么。

我有一个应随时间演变的元素列表。

每个元素都有一个适合度值，决定了它有多好。这是代表元素的 Class：

class Element implements Comparable<Element>{
    private int fitness;
    Element( int _fitness){
        this.fitness=_fitness;
    }

    public int getFitness() {
        return fitness;
    }

    @Override
    public int compareTo( Element o ) {
        return this.fitness-o.getFitness();
    }

    @Override
    public String toString() {
        return this.fitness+"";
    }
}

最好的元素是具有最大适应值的元素。

示例：

list_Iteration_One | list_Iteration_Two| list_Iteration_Three
Element(5)         | Element(9)        | Element(14) 

Element(4)         |Element(5)         | Element(9) 

Element(3)         |Element(5)         | Element(9) 

Element(2)         |Element(4)         | Element(5) 

Element(1)         |Element(3)         | Element(5)

正如我们所见，该程序应将元素列表作为输入，并演化这些元素以创建新列表。

规则是取列表的一半，将每两个Elment合并为一个新的Element。

对于所选元素，它们应该具有最大适应值。

对于我上面的例子，我用 Element(5) + Element(4) 创建了 Element(9) ，我用 Element(3) + Element(2) 创建了 Element(5) 剩下的我用了 Element(5), Element(4), Element(3).

对于第 3 次迭代，我正在做同样的事情。

这是我对一次迭代所做的：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class BestDataStructure {

    public static void main( String[] args ) {
        List<Element> list = Stream.of(new Element(5),
                new Element(4),
                new Element(3),
                new Element(2),
                new Element(1)).collect(Collectors.toCollection(ArrayList::new));
        List<Element> theNewList = getTheNewList(list);
        System.out.println(theNewList);
    }

    private static List<Element> getTheNewList( List<Element> list ) {
        List<Element> theNewList = new ArrayList<>();

        int numberOfTimes = list.size()/2;
        Element bestElement=null;
        Element secondBestElement=null;
        for (int i =0; i<numberOfTimes; i++){
            bestElement= Collections.max(list);
            list.remove(bestElement);

            secondBestElement= Collections.max(list);
            list.remove(secondBestElement);

            Element child = new Element(bestElement.getFitness()+secondBestElement.getFitness());
            theNewList.add(child);

            theNewList.add(bestElement);
            theNewList.add(secondBestElement);
        }
        return theNewList;
    }


}

class Element implements Comparable<Element>{
    private int fitness;
    Element( int _fitness){
        this.fitness=_fitness;
    }

    public int getFitness() {
        return fitness;
    }

    @Override
    public int compareTo( Element o ) {
        return this.fitness-o.getFitness();
    }

    @Override
    public String toString() {
        return this.fitness+"";
    }
}

因为我应该处理 List 的大小（在 2000 到 50000 元素之间），我需要知道处理这种处理的最佳数据结构。

我每次都在寻找 ArryList 中的最大元素，这是一个非常糟糕的主意。

每次迭代后的结果列表应该与第一个列表具有相同的大小，不幸的是，这不是我在 getTheNewList 方法中得到的。

我也在寻找的是我应该如何处理这个任务，我应该第一时间寻找最好的元素，还是我应该迭代选择主题...

Answer 1

我建议在将列表传递给 getTheNewList 之类的方法之前确保您的列表已按适应度排序，而不是使该方法 return 成为一个新列表，只需让它在相同的列表。例如，如果您的列表按降序排序，您可以简单地取出最后两个元素，因为在这种情况下 size of list/2 是 2。然后，从列表中的第一个元素开始以 2 为一组组合元素，并将此列表插入另一个列表。然后，遍历这个组合元素的列表，找出这个新元素应该插入到列表中的什么位置以保持顺序。这是它的样子，

private void getTheNewList( List<Element> list ) {
    List<Element> theNewList = new ArrayList<>();
    int numberOfTimes = list.size()/2;
    Element bestElement=null;
    Element secondBestElement=null;
    for (int i = 0 ; i < numberOfTimes; i++) {
        //remove last element of the list
        list.remove(list.size() - 1);
        bestElement= list.get(numberOfTimes * 2 - 2);

        secondBestElement= Collections.max(numberOfTimes * 2 - 1);

        Element child = new Element(bestElement.getFitness()+secondBestElement.getFitness());
        theNewList.add(child);
    }
    //insert combined elements into original list
    for (int i = 0; i < numberOfTimes; i++) {
        for (int j = 0; j < list.size(); j++) {
            if (list.get(j) <= theNewList.get(i)) {
                list.insert(j, theNewList.get(i));
                break;
            }
            list.insert(j, theNewList.get(i));
        }
    }
}

Answer 2

您可以使用 Java 流：使用 IntStream 生成元素的前半部分并附加原始列表的前半部分。以下方法需要一个排序列表和 returns 一个新的排序元素列表：

private static List<Element> getTheNewList(List<Element> elements) {
    int halfElements = elements.size() / 2;
    return Stream.concat(
            IntStream.range(0, halfElements)
                    .mapToObj(index -> new Element(elements.get(index * 2).getFitness() + elements.get(index * 2 + 1).getFitness())),
            elements.stream().limit(halfElements + 1)
    )
            .sorted(Comparator.reverseOrder())
            .collect(Collectors.toList());
}

如果您按照以下方式使用它：

List<Element> iteration1 = Arrays.asList(
        new Element(5),
        new Element(4),
        new Element(3),
        new Element(2),
        new Element(1)
);
System.out.println(iteration1);
List<Element> iteration2 = getTheNewList(iteration1);
System.out.println(iteration2);
List<Element> iteration3 = getTheNewList(iteration2);
System.out.println(iteration3);

这将打印：

[5, 4, 3, 2, 1]
[9, 5, 5, 4, 3]
[14, 9, 9, 5, 5]

从现有列表创建元素列表

Creating a List of elements from an existing List

java

collections

genetic-algorithm

data-structures

java-stream