Creating a List of elements from an existing List

Question

I'm creating a genetic algorithm to solve some specific problem. As the problem is hard to describe, i wrote a tiny example that show what I'm doing.

I have a list of Element that should evolve over time.

Each Element has a fitness value that determine how good it is. Here is the Class that represents an Element:

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+"";
    }
}

The best Element is the Element that has a maximum fitness value.

Exemple:

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) 

As we can see the program should take as imput a list of Element and evolve those Elements to create a new List.

The rule is to take the half of the list and merge each two Elment to create a new Element.

For the chosen Element, they should have the maximum fitness value.

For my example above i took the Element(5) + Element(4) to create the Element(9) , and i took Element(3) + Element(2) to create Element(5) and what is left i took Element(5), Element(4), Element(3).

For the iteration 3, i'm doing the same thing and so one.

Here is what i have done for one iteration:

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+"";
    }
}

As I should process List of size(between 2000 and 50000 Element), I need to know the best datastructure to deal with such processing.

I'm looking for the maximum Element every time in an ArryList and it is very bad idea.

The resulting list after each iteration should have the same size as the first List, and unfortunately it is not what I'm getting in my getTheNewList Method.

What I'm looking for too, is the way i should handle this task, should i look for the best Element in the first time, or should i choose theme iteratively...

Answer 1

You can use the Java Streams: Use an IntStream to generate the first half on elements and append the first half of the original list. The following method expects a sorted list and returns a new sorted list of elements:

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());
}

If you use it the following way:

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);

This will print:

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

Answer 2

I would suggest making sure your list is sorted by fitness before passing it into some method like getTheNewList, and instead of making that method return a new list, just have it operate on the same list. For example, if your list is sorted in descending order, you can simply take out the last two elements since size of list/2 is 2 in this case. Then, combine elements in groups of 2 starting from the first element in the list, and insert this list into another list. Then, traverse through this list of combined elements and find out where this new element should be inserted into the list to preserve order. Here's what it would look like,

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));
        }
    }
}