java - 蚁群优化问题

Question

我遇到了这个问题: build 一个由 n 个给定边的彩色立方体组成的塔。不能有边小的立方体和边大的立方体，也不能有两个相邻的立方体颜色相同。我正在尝试使用 Ant Colony Optimization 来解决它。我遇到的麻烦是我不知道如何选择下一个立方体来移动 Ant 并在其上留下信息素。

Example: For the following cubes:
C1 - side = 5, Color = Red
C2 - side = 2, Color = Green
C3 - side = 10, Color = Blue
C4 - side = 1, Color = Red
the solution would be: C3, C1, C2, C4

This is what I've done so far:

Ant 类:

     public class Ant {

        private int[] visited;
        private int size;

        public Ant(int size) {
            this.size = size;
            this.visited = new int[size];
        }

        public void clearVisited(){
            for(int i=0; i < size; i++){
                visited[i] = -1;
            }
        }

        public void visit(int index, int cube) {
            visited[index] = cube;
        }

        public int visited(int index){
            return visited[index];
        }

        public boolean contains(int cube){
            for(int i=0; i < size; i++){
                if(visited[i] == cube){
                    return true;
                }
            }

            return false;
        }
    }

立方体类:

    public class Cube {

        private int length;
        private String color;


        public Cube(int length, String color){
            this.length = length;
            this.color = color;
        }

        public Cube(String color){
            this.length = (int)Math.round(Math.random() * 200);
            this.color = color;
        }

        public int getLength(){
            return this.length;
        }

        public String getColor(){
            return this.color;
        }

        public void setLength(int length){
            this.length = length;
        }

        public void setColor(String color){
            this.color = color;
        }

        public String toString(){
            String str = "";
            str += "Cub: l = " + length + ", " + "c = " + color;
            return str;
        }

        public boolean equals(Object o){
            if(o == null){
                return false;
            }

            if(!(o instanceof Cube)){
                return false;
            }

            Cube c = (Cube)o;
            if((c.getColor().equals(this.getColor())) && (c.getLength() == this.getLength())){
                return true;
            }

            return false;
        }
    }

Cube Repository 类:我在这里存储立方体

    public class CubeRepository {

        private static ArrayList<Cube> availableCubes = new ArrayList<Cube>();

        public static void addCube(Cube cube){
            if(!availableCubes.contains(cube)){
                availableCubes.add(cube);
            }
        }

        public static Cube getCube(int index){
            return availableCubes.get(index);
        }

        public static int getSize(){
            return availableCubes.size();
        }
    }

ACO算法:

    public class ACO {

        private int nrAnts;
        private int nrCubes;
        private Ant[] ants;
        private int currentIndex;
        private double[] pheromoneTrail;
        private double ph = 1; //pheromon trace on every cube at start
        private int alpha = 1;
        private int beta = 5;
        private int Q = 500;
        private double q0 = 0.01;

        public ACO(int nrAnts, int nrCubes){
            this.nrAnts = nrAnts;
            this.nrCubes = nrCubes;
            ants = new Ant[nrAnts];
            pheromoneTrail = new double[nrCubes];
        }

        public void createAnts(){//creeaza toate furnicile
            currentIndex = 0;
            for(int i=0; i < nrAnts; i++){
                ants[i] = new Ant(nrCubes);
            }
        }

        public Ant getAnt(int index){//return an ant
            return ants[index];
        }

        public void setupPheromoneTrail(){ //sets pheromone trail for every cube at start
            for(int i=0; i < nrCubes; i++){
                pheromoneTrail[i] = ph;
            }
        }

        public void placeAnts(){ //place every ant on a cube
            for(int i=0; i < nrAnts; i++){
                ants[i].visit(currentIndex, (int)(Math.random() * nrCubes));
            }
            currentIndex++;
        }

        public int selectNextCube(Ant ant){
            if(Math.random() < q0){
                int cube = (int)(Math.random() * nrCubes); //pick a random cube
                while(!ant.contains(cube)){
                    if(CubeRepository.getCube(ant.visited(currentIndex-1)).getColor().equals(CubeRepository.getCube(cube).getColor())){
                        cube = (int)(Math.random() * nrCubes);
                    }
                }

                return cube;
            }

            return 1; //I didn't return a proper value
        }

        public void MoveAnts(){ //move every ant on another cube
            while(currentIndex < nrCubes){
                for(int i=0; i < nrAnts; i++){
                    ants[i].visit(currentIndex, selectNextCube(ants[i]));
                }
                currentIndex++;
            }
        }

    }

Answer 1

在没有理解整个程序的情况下(快速阅读它并找到答案太过分了):您可以使用这样的伪代码选择一个颜色与前一个颜色不同的随机立方体

private static final Random random = new Random(0);
public int selectNextCube(Ant ant)
{
    Cube previousCube = CubeRepository.getCube(ant.visited(currentIndex-1));
    List<Cube> allCubes = obtainAllCubesFromCubeRepository();
    List<Cube> sameColor = obtainAllCubesWithSameColorAs(previousCube); 
    allCubes.removeAll(sameColor);

    // EDIT>>>: You might also need this:
    allCubes.remove(computeAllCubesAlreadyVisitedBy(ant));
    // <<<EDIT: You might also need this:

    int index = random.nextInt(allCubes.size());
    Cube nextCube = allCubes.get(index);
    return indexFor(nextCube);         
}

顺便说一句:我强烈建议不要使用Math.random()。它返回一个不可预测的随机值。调试涉及 Math.random() 的程序非常糟糕。相反，您应该使用 java.lang.Random 的实例，如上面的代码片段所示。您可以调用 random.nextDouble() 以获得 double 值，就像使用 Math.random() 一样。此外，您可以调用 random.nextInt(n) 来获取 [0,n) 范围内的 int 值。最重要的是:当您将此实例创建为 new Random(0) 时，它将始终返回相同的随机数序列。这使得程序具有可预测性，并使真正调试程序成为可能。 (如果你想要一个“不可预测的”随机数序列，你可以将它实例化为 new Random()，没有随机种子)。