基于禁忌搜索的图染色问题算法Java语言实现

编写一个图染色测序，实现禁忌搜索的基本思想。

程序包括两个文件：GraphColoring.java 和 TabuColoring.java

程序的主方法在 GraphColoring实现,你只需实现TabuColoring类使得程序能够工作并返回指定颜色数的解。GraphColoring.java 实现如下：

/**
 * This is a java implementation of tabu search for
 * graph coloring problem
 * @author JiangHua
 *
 */
import java.util.*;
import java.io.*;
public class GraphColoring {

    public static void main(String[] args) {
        Graph G=readDimacsInstance(args[0]);//读取图文件
        int nbColor=Integer.parseInt(args[1]);//颜色数
        int nbRound=Integer.parseInt(args[2]);//求解次数
        int nbColor=Integer.parseInt("50");//颜色数
        int nbRound=Integer.parseInt("10");//求解次数
        System.out.println(G);
        TabuColoring tabucol=new TabuColoring(G,nbColor);
        for (int r = 1; r <= nbRound; r++) {
            int[] sol=tabucol.search(); //执行搜索，返回解
            System.out.printf("Round %2d ",r);
            G.verifySolution(sol,nbColor); //验证解的正确性
        }
    }
    /**
     * 从文件中读入图
     * @param filename
     * @return Graph 对象
     */
    public static Graph readDimacsInstance(String filename){
        //System.out.println(filename);
        Graph gh=null;
        try {

            Scanner fin=new Scanner(new File(filename));
            while(fin.hasNextLine()) {
                String line =fin.nextLine();
                Scanner sline=new Scanner(line);
                if(line.startsWith("p")) {
                    sline.next();sline.next();
                    int numV=sline.nextInt();
                    int numE=sline.nextInt();
                    gh=new Graph(numV, numE);
                }else if(line.startsWith("e")) {
                    assert(gh!=null);
                    sline.next();
                    gh.addEdge(sline.nextInt(),sline.nextInt());
                }
                sline.close();
            }
            //  System.out.println("File inputed");
            fin.close();
            return gh;
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        return null;
    }
}

class Graph{
    public final int verNum; //顶点数
    public final int edgeNum; //边数
    private byte[][] adjMatrix; // 邻接矩阵
    private Vector<ArrayList<Integer>> adjList; //邻接表

    public Graph(int nbVertex, int nbEdge) {
        this.verNum=nbVertex;
        this.edgeNum=nbEdge;
        adjMatrix=new byte[nbVertex+1][nbVertex+1];
        adjList=new Vector<ArrayList<Integer>>(verNum+1);
        for(int i=0;i<=nbVertex;i++)
            adjList.add(new ArrayList<Integer>());
    }

    //为图添加一条边
    public boolean addEdge(int lnode,int rnode) {
        if(lnode==rnode || lnode > verNum || rnode>verNum || lnode <1  || rnode <1) {
            return false;
        }
        if(adjMatrix[lnode][rnode]==0) {
            adjMatrix[lnode][rnode]=1;
            adjList.get(lnode).add(rnode);
            adjList.get(rnode).add(lnode);
        }
        return true;
    }
    /**
     * return the adjacent list of vertexID
     * @param vertexID
     * @return
     */
    public ArrayList<Integer> getNeighbors(int vertexID){
        return adjList.get(vertexID);
    }

    /**
     * 对解sol的合法性进行验证，如果合法输出"verified!",否则，输出 "failed!"
     * @param sol 解：为一个整型数组，顶点 i 的颜色为 sol[i]
     * @param nbColor 颜色数： 1， 2，3 ，..., nbColor
     */
    public void verifySolution(int[] sol,int nbColor) {
        if(sol.length<=this.verNum){
            System.out.println("failed!");
            return ;
        }
        for(int v=1;v<=this.verNum;v++) {
            int color=sol[v];
            for(int neibor:this.adjList.get(v)) {
                assert(sol[neibor]>=1 && sol[neibor]<=nbColor);
                if(sol[neibor]==color){
                    System.out.println("vertex "+v+" and vertex "+neibor+" have the same color "+color);
                    System.out.println("failed!");
                    return ;
                }
            }
        }
        System.out.println("verified!");
    }
    public String toString() {
        return String.format("Graph with %d vertices %d edges\n", this.verNum,this.edgeNum);
    }
}

核心函数

findMove

该 findMove 方法是禁忌搜索算法中用于寻找最佳移动（即更改颜色的操作）的关键部分。它的目的是在当前解中找到一个顶点，并为其选择一个新颜色，以减少总的冲突数或达到可接受的冲突水平。

步骤解释

1. 初始化变量：

   • delt 被设置为 Integer.MAX_VALUE，作为比较基准，用于找到可能的最佳移动，即能最大程度减少冲突的移动。

2. 遍历所有顶点：

   • 对于图中的每个顶点 i，首先获取其当前颜色 cColor 和与该颜色相关的冲突数 cColorTable（即该顶点当前颜色导致的冲突数）。

3. 检查冲突：

   • 如果顶点 i 当前的颜色冲突数 cColorTable 大于0，说明该顶点存在颜色冲突需要解决。

4. 尝试新颜色：

   • 对于顶点 i 的每个可能的新颜色 j（不等于其当前颜色 cColor）：
     • 计算改变后的冲突差 tmpDelt（将颜色从 cColor 改为 j 后的冲突数变化）。
     • 检查这种颜色变更是否是禁忌的（通过 tabuTenure 数组）。如果不是禁忌或即使是禁忌但可以得到比历史上最好冲突数 bestF 更低的结果，则考虑这种变更。

5. 记录和更新最佳移动：

   • 如果找到的新冲突差 tmpDelt 小于之前记录的 delt，则更新 delt 并重置等价最优解的计数器 equCount。
   • 将这个顶点和新颜色作为一个潜在的最佳移动添加到 equDelt 数组中，用于可能的执行。

6. 随机选择一个最佳移动：

   • 如果有多个等价的最佳移动，通过 rand.nextInt(equCount) 随机选择一个，以引入随机性，帮助算法跳出局部最优。

7. 确定移动：

   • 最终选择的顶点和颜色存储在 selVertex 和 selColor 中，用于后续的 makeMove 方法执行颜色变更。

总结

findMove 方法的核心是通过减少冲突来优化图的颜色配置。它使用了禁忌搜索的机制来避免陷入局部最优，并通过随机选择等价最佳解来增加搜索过程的多样性。这种方法有效地平衡了探索（通过尝试新颜色）和开发（通过选择已知可减少冲突的移动）。

makeMove

方法 makeMove 是禁忌搜索算法中实际执行颜色变更并更新状态的函数。该方法用于将前面通过 findMove 方法确定的最佳移动应用到当前解中，并相应地更新冲突计数和禁忌期。以下是详细的步骤和逻辑解释：

详细步骤解释

1. 更新总冲突数：

   • f 是当前图的总冲突数。delt 是从 findMove 方法得到的冲突变化量，表示这次颜色变更将如何影响总冲突数。通过 f = delt + f 更新总冲突数。

2. 更新历史最小冲突数：

   • 如果新的总冲突数 f 小于历史记录的最低冲突数 bestF，则更新 bestF 为当前的 f。这一步骤是用来跟踪算法运行过程中遇到的最小冲突数。

3. 执行颜色变更：

   • selVertex 是之前 findMove 方法确定要变更颜色的顶点。
   • selColor 是选定的新颜色。
   • 将顶点 selVertex 的颜色从 oldColor（当前颜色）更改为 selColor（新颜色）。

4. 更新禁忌期：

   • 禁忌期是用来暂时阻止某些移动重新发生，以避免算法陷入循环或过早地回到之前的状态。
   • 对于刚刚从 oldColor 变更到 selColor 的顶点 selVertex，设置其从 oldColor 到任何其他颜色的变更为禁忌，禁忌期至少持续到 iter + f + (int) (0.6 * rand.nextInt(10))。这里 iter 是当前的迭代次数，f 是变更后的冲突数，0.6 * rand.nextInt(10) 是添加的随机性，用于动态调整禁忌期的长度。

5. 更新邻接顶点的颜色冲突表：

   • hNbID 是 selVertex 的邻接顶点列表，numEdge 是其邻接顶点的数量。
   • 对于 selVertex 的每个邻接顶点，更新与 oldColor 和 selColor 相关的冲突数：
     • 将与 oldColor 相关的冲突数减一，因为 selVertex 不再使用这个颜色。
     • 将与 selColor 相关的冲突数加一，因为 selVertex 现在使用了这个新颜色。

总结

makeMove 方法直接影响算法的状态，通过实际变更顶点颜色并更新相关的管理信息（如冲突数和禁忌期），来推动解向更优状态发展或维持在较低冲突状态。这一过程是禁忌搜索的核心，通过禁忌机制防止算法回到先前探索过的解，同时允许一定程度的随机性和灵活性，以跳出局部最优解，探索更广泛的解空间。

代码

import java.util.Random;

public class TabuColoring {
    // 类变量声明
    static int N, K; // N: 图的顶点数, K: 可用颜色数
    static int[] sol; // 每个顶点的当前颜色
    static int[][] adjColorTable; // 邻域颜色表，记录每个顶点邻接顶点的颜色分布
    static int[][] tabuTenure; // 禁忌期表，记录变更颜色的禁忌期
    static int f, bestF; // f: 当前冲突数, bestF: 历史最小冲突数
    static int[][] NbID; // 每个顶点的邻接顶点索引数组
    static int[] numAdj; // 每个顶点的邻接顶点数量
    static boolean[][] Adj; // 邻接矩阵，如果两个顶点相邻则为true
    static int[][] equDelt; // 保存相等解的数组
    static Random rand = new Random(); // 全局随机数生成器
    static int delt; // 此次迭代的最优解
    static int equCount = 0; // 记录相等解的个数
    static int iter; // 迭代次数
    static int selVertex, selColor; // move
    private final Graph graph; // 图对象
    private final int numColors; // 使用的颜色数量
    // 构造函数
    public TabuColoring(Graph graph, int numColors) {
        this.graph = graph;
        this.numColors = numColors;
        this.initialize();
    }

    // 寻找最佳移动
    public static void findMove() {
        delt = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            int cColor = sol[i]; // 当前顶点的颜色
            int[] hColor = adjColorTable[i]; // 当前顶点的颜色冲突表
            int cColorTable = hColor[cColor]; // 当前顶点的颜色冲突数
            if (cColorTable > 0) { // 如果当前顶点有冲突
                int[] hTabu = tabuTenure[i];
                for (int j = 0; j < K; j++) {
                    if (cColor != j) { // 如果当前颜色不等于新颜色
                        int tmpDelt = hColor[j] - cColorTable;
                        if (tmpDelt <= delt && (iter > hTabu[j] || (tmpDelt + f) < bestF)) {
                            if (tmpDelt < delt) { // 当前解小于本次迭代最优解,则重新开始保存解
                                equCount = 0;
                                delt = tmpDelt;
                            }
                            equDelt[equCount][0] = i;
                            equDelt[equCount][1] = j;
                            equCount++;
                        }
                    }
                }
            }
        }

        int tmp = rand.nextInt(equCount);  // 有多个解时，随机选择
        selVertex = equDelt[tmp][0];
        selColor = equDelt[tmp][1];
    }

    // 执行移动，更新颜色和禁忌表
    public static void makeMove() {
        f = delt + f;
        if (f < bestF) bestF = f;
        int oldColor = sol[selVertex];
        sol[selVertex] = selColor; // 更新顶点颜色
        tabuTenure[selVertex][oldColor] = iter + f + (int) (0.6 * rand.nextInt(10)); // 更新禁忌表
        int[] hNbID = NbID[selVertex]; // 当前顶点的邻接顶点列表
        int numEdge = numAdj[selVertex]; // 当前顶点的邻接顶点数量
        for (int i = 0; i < numEdge; i++) { // 更新邻接顶点的颜色冲突表
            int tmp = hNbID[i]; // 当前邻接顶点
            adjColorTable[tmp][oldColor]--; // 旧颜色冲突数减一
            adjColorTable[tmp][selColor]++; // 新颜色冲突数加一
        }
    }

    // 初始化方法，用于设置初始颜色和计算邻接关系
    public void initialize() {
        N = graph.verNum;
        K = numColors;
        Adj = new boolean[N][N];
        f = 0;
        Random rand = new Random();
        sol = new int[N];
        // 随机为每个顶点分配颜色，并建立邻接矩阵
        for (int i = 0; i < N; i++) {
            sol[i] = rand.nextInt(K);
            for (int j : graph.getNeighbors(i)) {
                Adj[i - 1][j - 1] = true;
                Adj[j - 1][i - 1] = true;
            }
        }
        // 初始化equDelt数组，用于存储等价的最优解
        // 开辟equDelt,最多有N*(K-1)个解.即每个顶点可以产生K-1个delt
        // equDelt[i][0]存第i个解的顶点，equDelt[i][2]存第i个解的newcolor
        equDelt = new int[N * (K - 1)][2];
        adjColorTable = new int[N][K];
        // 初始化颜色冲突表
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (Adj[i][j]) { // 如果两个顶点相邻
                    adjColorTable[i][sol[j]]++;
                    adjColorTable[j][sol[i]]++;
                    if (sol[i] == sol[j]) {
                        f++; // 两点颜色相等，则冲突数加一
                    }
                }
            }
        }
        bestF = f;  // 初始化最优f

        tabuTenure = new int[N][K];
        numAdj = new int[N];
        NbID = new int[N][N - 1];
        for (int i = 0; i < N; i++) {   // 从邻接矩阵 Adj 提取每个顶点的邻接顶点列表
            int count = 0;
            for (int j = 0; j < N; j++) {
                if (Adj[i][j]) {
                    NbID[i][count++] = j;
                }
            }
            numAdj[i] = count;
        }
    }

    // 搜索方法，执行直到找到无冲突解
    public int[] search() {
        this.initialize();
        while (f != 0) {
            findMove();
            makeMove();
            iter++;
        }
        // 将解中的每个颜色编号增加1，并在数组前加0
        int[] original = sol;
        sol = new int[original.length + 1]; // 创建一个新的数组，长度比原数组多1
        sol[0] = 0; // 在新数组的最前面加上0
        for (int i = 0; i < original.length; i++) {
            sol[i + 1] = original[i] + 1;
        }
        return sol;
    }
}