グラフ彩色問題に対する定式化とメタヒューリスティクス

準備

ここでは,付録2で準備したグラフに関する基本操作を集めたモジュール graphtools.py を読み込んでいる. 環境によって,モジュールファイルの場所は適宜変更されたい.

定式化

グラフ彩色問題は,以下のように定義される問題である.

点数 $n$ の無向グラフ $G=(V,E)$ の $K$分割($K$ partition)とは,点集合 $V$ の $K$ 個の部分集合への分割 $\Upsilon= \{V_1, V_2, \ldots, V_K\}$ で, $V_i \cap V_j =\emptyset, \forall i \neq j$(共通部分がない),$\bigcup_{j=1}^K V_j =V$(合わせると点集合全体になる) を満たすものを指す.各 $V_i (i=1,2,\ldots,K)$ を色クラス(color class)と呼ぶ.

$K$分割は,すべての色クラス $V_i$ が安定集合(点の間に枝がない)のとき $K$彩色($K$ coloring)と呼ばれる. 与えられた無向グラフ $G=(V,E)$ に対して, 最小の $K$ (これを彩色数と呼ぶ) を導く $K$ 彩色 $\Upsilon=\{ V_1, V_2, \ldots, V_K \}$ を求めよ.

グラフ彩色問題の定式化を行うために,彩色可能な色数の上界 $K_{\max}$ が分かっているものと仮定する. すなわち,最適な $K$彩色は,$1 \leq K \leq K_{\max}$ の整数から選択される.

標準定式化

点 $i$ に塗られた色が $k$ のとき $1$,それ以外のとき $0$ の $0$-$1$ 変数 $x_{ik}$ と, 色クラス $V_{k}$ に含まれる点が $1$つでも あるときに $1$,それ以外の(色クラスが空の)とき $0$ の $0$-$1$ 変数 $y_{k}$ を用いると, グラフ彩色問題は,以下のように定式化できる.

$$ \begin{array}{l l l} minimize & \sum_{k=1}^{K_{\max}} y_{k} & \\ s.t. & \sum_{k=1}^{K_{\max}} x_{ik} = 1 & \forall i \in V \\ & x_{ik} + x_{jk} \leq y_{k} & \forall (i,j) \in E, k=1,2,\ldots,K_{\max} \\ & x_{ik} \in \{0,1\} & \forall i \in V, k =1,2,\ldots,K_{\max} \\ & y_{k} \in \{0,1\} & \forall k =1,2,\ldots,K_{\max} \end{array} $$

Gurobiをはじめとする多くの数理最適化ソルバーは,分枝限定法を利用して求解している. 分枝限定法においては, 上のグラフ彩色問題の定式化における色クラスはすべて無記名で扱われるため,解は対称性をもつ. たとえば,解 $V_1=\{1,2,3\}, V_2=\{4,5\}$ と解 $V_1=\{4,5\}, V_2=\{1,2,3\}$ はまったく同じものであるが, 上の定式化では異なるベクトル $x,y$ で表される.この場合,変数 $x,y$ をもとに分枝しても下界が改良されない現象が発生する. グラフ彩色問題を市販の数理最適化ソルバーで求解する際には,解の対称性を避けるために,添え字の小さい色クラスを優先して用いることを表す,以下の制約を付加することが推奨される.

$$ y_{k} \leq \sum_{i \in V} x_{ik} \ \ \ \forall k=1,2,\ldots,K_{\max} $$$$ y_{k} \geq y_{k+1} \ \ \ \forall k=1,2,\ldots,K_{\max}-1 $$
random.seed(123)
n = 10
K = n
pos = {i: (random.random(), random.random()) for i in range(n)}
G = nx.random_geometric_graph(n, 0.5, pos=pos)

V = G.nodes()
E = G.edges()

model = Model("gcp - standard")
x, y = {}, {}
for i in V:

    for k in range(K):
        x[i, k] = model.addVar(vtype="B", name=f"x({i},{k})")
for k in range(K):
    y[k] = model.addVar(vtype="B", name=f"y({k})")
model.update()

for i in V:
    model.addConstr(quicksum(x[i, k] for k in range(K)) == 1, f"AssignColor({i})")

for (i, j) in E:
    for k in range(K):
        model.addConstr(x[i, k] + x[j, k] <= y[k], f"BadEdge({i},{j},{k})")
for k in range(K):
    model.addConstr(y[k] <= quicksum(x[i, k] for i in V), f"SymmetryBreak1({k})")

for k in range(K - 1):
    model.addConstr(y[k] >= y[k + 1], f"SymmetryBreak2({k})")

model.setObjective(quicksum(y[k] for k in range(K)), GRB.MINIMIZE)

model.optimize()
color = {}
if model.status == GRB.Status.OPTIMAL:
    for i in V:
        for k in range(K):
            if x[i, k].X > 0.5:
                color[i] = k
                break

print("solution:", color)

nx.draw(
    G,
    pos=pos,
    with_labels=False,
    node_color=[color[i] for i in V],
    node_size=100,
    cmap=plt.cm.Paired,
    edge_color="black",
    width=0.5,
)
Set parameter Username
Academic license - for non-commercial use only - expires 2023-11-07
Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (mac64[x86])
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 379 rows, 110 columns and 1278 nonzeros
Model fingerprint: 0x372ce9d2
Variable types: 0 continuous, 110 integer (110 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+00]
Presolve removed 323 rows and 2 columns
Presolve time: 0.00s
Presolved: 56 rows, 108 columns, 425 nonzeros
Variable types: 0 continuous, 108 integer (108 binary)
Found heuristic solution: objective 10.0000000

Root relaxation: objective 7.000000e+00, 87 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

H    0     0                       7.0000000    2.00000  71.4%     -    0s
     0     0          -    0         7.00000    7.00000  0.00%     -    0s

Explored 1 nodes (127 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 16 (of 16 available processors)

Solution count 2: 7 10 

Optimal solution found (tolerance 1.00e-04)
Best objective 7.000000000000e+00, best bound 7.000000000000e+00, gap 0.0000%
solution: {0: 3, 1: 2, 2: 0, 3: 1, 4: 5, 5: 0, 6: 4, 7: 6, 8: 3, 9: 5}

彩色数固定定式化

上で示したアプローチでは,彩色数 $K$ を最小化することを目的としていた. 以下では,彩色数 $K$ を固定した定式化を用いることによって,より大規模な問題を求解することを考えよう.

枝の両端点が同じ色で彩色されているとき $1$,それ以外のとき $0$ を表す 新しい変数 $z_{ij}$ を導入する.そのような「悪い」枝の数を最小化し, 最適値が $0$ になれば,彩色可能であると判断される.彩色数 $K$ を変えながら, この最適化問題を解くことによって,最小の彩色数を求めることができる.

$$ \begin{array}{l l l} minimize & \sum_{(i,j) \in E} z_{ij} & \\ s.t. & \sum_{k=1}^{K} x_{ik} = 1 & \forall i \in V \\ & x_{ik} + x_{jk} \leq 1+z_{ij} & \forall (i,j) \in E, k=1,2,\ldots,K \\ & x_{ik} \in \{0,1\} & \forall i \in V, k =1,2,\ldots,K \\ & z_{ij} \in \{0,1\} & \forall (i,j) \in E \end{array} $$

ここで目的関数は,悪い枝の数の最小化である. 最初の制約は,各点 $i$ に必ず1つの色が塗られることを表す. 2番目の制約は,枝$(i,j)$ の両端点の点$i$ と点$j$ が,同じ色クラスに割り当てられている場合には, 枝$(i,j)$ が悪い枝と判定されることを表す.

彩色数 $K$ を固定した定式化は,以下のようになる.

def gcp_fixed_k(V, E, K):
    """gcp_fixed_k -- model for minimizing number
    of bad edges in coloring a graph
    Parameters:
        - V: set/list of nodes in the graph
        - E: set/list of edges in the graph
        - K: number of colors to be used
    Returns a model, ready to be solved.
    """
    model = Model("gcp - fixed k")
    x, z = {}, {}
    for i in V:
        for k in range(K):
            x[i, k] = model.addVar(vtype="B", name=f"x({i},{k})")
    for (i, j) in E:
        z[i, j] = model.addVar(vtype="B", name=f"z({i},{j})")
    model.update()

    for i in V:
        model.addConstr(quicksum(x[i, k] for k in range(K)) == 1, f"AssignColor({i})")

    for (i, j) in E:
        for k in range(K):
            model.addConstr(x[i, k] + x[j, k] <= 1 + z[i, j], f"BadEdge({i},{j},{k})")

    model.setObjective(quicksum(z[i, j] for (i, j) in E), GRB.MINIMIZE)

    model.update()
    model.__data = x, z
    return model

上のモデル(彩色数固定定式化)を用いて最適な(色数最小の)グラフ彩色を得るには,2分探索をすればよい. 以下のそのためのコードを示す.

def solve_gcp(V, E):
    """solve_gcp -- solve the graph coloring problem
    with bisection and fixed-k model
    Parameters:
        - V: set/list of nodes in the graph
        - E: set/list of edges in the graph
    Returns tuple with number of colors used,
    and dictionary mapping colors to vertices
    """
    LB = 0
    UB = len(V)
    color = {}
    while UB - LB > 1:
        K = (UB + LB) // 2
        print("trying fixed K=", K)
        gcp = gcp_fixed_k(V, E, K)
        gcp.Params.OutputFlag = 0  # silent mode
        gcp.Params.Cutoff = 0.1
        gcp.optimize()
        if gcp.status == GRB.Status.OPTIMAL:
            x, z = gcp.__data
            for i in V:
                for k in range(K):
                    if x[i, k].X > 0.5:
                        color[i] = k
                        break
                # else:
                #     raise "undefined color for", i
            UB = K
        else:
            LB = K

    return UB, color
K, color = solve_gcp(V, E)
print("minimum number of colors:", K)
print("solution:", color)

AMPLによる求解

AMPLモデル(gcp_fixed_k.mod)

set V;
set E within {V,V};
param K;
set C := {1..K};

var x {V, C} binary;
var z {E} binary;

minimize Z: sum {(i,j) in E} z[i,j];

subject to
Color {i in V}: sum {k in C} x[i,k] = 1;
BadEdge {(i,j) in E, k in C}: x[i,k] + x[j,k] <= 1 + z[i,j];
ampl = AMPL(Environment(AMPL_PATH))
ampl.option['solver'] = 'highs'
ampl.read("../ampl/gcp_fixed_k.mod")
ampl.set['V'] = list(V)
ampl.set['E'] = list(E)

LB = 0
UB = len(V)
while UB - LB > 1:
    K = (UB + LB) // 2
    print("current K:{}\t[LB:{},UB:{}]".format(K,LB,UB))
    ampl.param['K'] = K
    ampl.solve()
    Z = ampl.obj['Z']
    #print("Bad edges:", Z.value())

    if Z.value() > .5:
        LB = K
        z = ampl.var['z']
#         for (i, j) in E:
#             if z[i, j].value() > .5:
#                 print("Bad edge:", (i, j))
    else:
        UB = K
        x = ampl.var['x']
        for k in range(1, K + 1):
            vk = [i for i in V if x[i, k].value() > .5]
            #print("color {} used in {}".format(k, vk))

print()
print("Chromatic number:", UB)
print("color {} used in {}".format(k, vk))
current K:5	[LB:0,UB:10]
HiGHS 1.2.2:HiGHS 1.2.2: optimal solution; objective 2
12 branching nodes
current K:7	[LB:5,UB:10]
HiGHS 1.2.2:HiGHS 1.2.2: optimal solution; objective 0
1 branching nodes
current K:6	[LB:5,UB:7]
HiGHS 1.2.2:HiGHS 1.2.2: optimal solution; objective 1
1 branching nodes

Chromatic number: 7
color 7 used in [0, 8]

半順序定式化

解の対称性を除去するために,同じ色に塗られた点の部分集合に対する半順序を用いた定式化を示す.

点 $i$ に塗られた色が $k$ のとき $1$,それ以外のとき $0$ の $0$-$1$ 変数 $x_{ik}$ の他に, 各点 $i$ に対して色 $k$ に先行する($i \prec k$)か後続する($k \prec i$)かを表す以下の変数を導入する.

  • $y_{ki}$: 点 $i$ が色$k$に後続する($k \prec i$)とき $1$,それ以外のとき $0$ の $0$-$1$ 変数

  • $z_{ik}$: 点 $i$ が色$k$に先行する($i \prec k$)とき $1$,それ以外のとき $0$ の$0$-$1$ 変数

グラフ彩色問題は,以下のように定式化できる.

$$ \begin{array}{l l l} minimize & 1+\sum_{k=1}^{K_{\max}} y_{k0} & \\ s.t. & x_{ik} = 1-(y_{ki}+z_{ik}) & \forall i \in V; k =1,2,\ldots,K_{\max} \\ & z_{i1} = 0 & \forall i \in V \\ & y_{K_{\max},i} = 0 & \forall i \in V \\ & y_{ki} \geq y_{k+1,i} & \forall i \in V, k =1,2,\ldots,K_{\max}-1 \\ & y_{ki} + z_{i,k+1} =1 & \forall i \in V, k =1,2,\ldots,K_{\max}-1 \\ & y_{k0} \geq y_{ki} & \forall i \in V \setminus \{0\}, k =1,2,\ldots,K_{\max} \\ & x_{ik} + x_{jk} \leq 1 & \forall (i,j) \in E \\ & x_{ik} \in \{0,1\} & \forall i \in V, k =1,2,\ldots,K_{\max} \\ & y_{ki} \in \{0,1\} & \forall i \in V, k =1,2,\ldots,K_{\max} \\ & z_{ik} \in \{0,1\} & \forall i \in V, k =1,2,\ldots,K_{\max} \end{array} $$

目的関数は,最初の点 $0$ に先行する色数の最小化であり,点 $0$ が塗られた色クラス $1$ を加えたものが最小の彩色数になる.

最初の制約は,点 $i$ が色 $k$ に後続も先行もされないときは,色 $k$ に塗られていることを表す. 2番目の制約は,色 $1$ に先行する点がないこと,3番目の制約は,最後の色に後続する点がないことを表す. 4番目の制約は,点が色$k+1$に後続するなら色$k$にも後続することを表す. 5番目の制約は,点 $i$ が何れかの色に塗られることを規定する. 6番目の制約は,他の点が色 $k$ に塗られたら,点 $0$ には $k$以上の色で塗ることを表す. 最後の制約は,枝の両端点が異なる色で塗られることを表す.

半順序を用いた定式化は,以下のようになる.

K = n
model = Model("gcp - partial order")
x, y, z = {}, {}, {}
for i in V:
    for k in range(K):
        x[i, k] = model.addVar(vtype="B", name=f"x({i},{k})")
        y[k, i] = model.addVar(vtype="B", name=f"y({k},{i})")
        z[i, k] = model.addVar(vtype="B", name=f"z({i},{k})")
model.update()

for i in V:
    model.addConstr(z[i, 0] == 0, f"FixZ({i})")
    model.addConstr(y[K - 1, i] == 0, f"FixY({i})")

for i in V:
    for k in range(K - 1):
        model.addConstr(y[k, i] >= y[k + 1, i], f"Ordering({i},{k})")
        model.addConstr(y[k, i] + z[i, k + 1] == 1, f"AssignColor({i},{k})")
        model.addConstr(y[k, 0] >= y[k, i], f"FirstNode({i},{k})")

# for i in V:
#    model.addConstr(quicksum(x[i,k] for k in range(K)) == 1,
#                    f"AssignColor({i})")

for i in V:
    for k in range(K):
        model.addConstr(x[i, k] == 1 - (y[k, i] + z[i, k]), f"Connection({i},{k})")

for (i, j) in E:
    for k in range(K):
        model.addConstr(x[i, k] + x[j, k] <= 1, f"BadEdge({i},{j},{k})")

model.setObjective(1 + quicksum(y[k, 0] for k in range(K)), GRB.MINIMIZE)

model.optimize()

for i in V:
    for k in range(K):
        if x[i, k].X > 0.5:
            color[i] = k
            break

print("solution:", color)

代表点定式化

隣接していない2つの点 $i,j$ に対して, 点 $j$ の色を点 $i$ と同じ色にするとき $1$,それ以外のとき $0$ になる $0$-$1$ 変数 $x_{ij}$ を導入する. 変数 $x_{ij}$ が $1$ のとき, 点 $j$ は点 $i$ に割り当てられ,点 $i$ が点 $j$ の代表点になっている また, $0$-$1$ 変数 $x_{ii}$ は,点 $i$ を色 $i$ で彩色するとき$1$,それ以外のとき $0$ になるものとする.

$N_i (A_i)$ を点 $i$ に隣接していない点からなるグラフの点(枝)集合とする.

これらの記号を用いると,グラフ彩色問題は,以下のように定式化できる.

$$ \begin{array}{l l l} minimize & \sum_{i \in V} x_{ii} & \\ s.t. & \sum_{i \in N_j} x_{ij} + x_{jj} \geq 1 & \forall j \in V \\ & x_{ij} + x_{ik} \leq x_{ii} & \forall i \in V, (j,k) \in A_i \\ & x_{ij} \leq x_{ii} & \forall i \in V, j \in N_i \\ & x_{ij} \in \{0,1\} & \forall i \in V, j \in V \end{array} $$

目的関数は色の代表点として選ばれた点数の最小化である.

最初の制約は,点 $j$ は代表点になるか,他の隣接していない点に割り振られるかのいずれかであることを表す. 2番目の制約は,点 $i$ に隣接していないグラフ内の枝 $(j,k)$ の両端点に,点 $i$ に塗られている色を同時に割り振らないことを表す. 3番目の制約は,他の点から割り振られた点は必ず代表点であることを表す.

最後の2本の制約は,点 $i$ に隣接していないグラフ内の極大クリーク(完全部分グラフ)を用いることによって強化できる.

Gbar = nx.complement(G)

model = Model("gcp - representative")
x = {}
for i in V:
    for j in V:
        x[i, j] = model.addVar(vtype="B", name=f"x({i},{j})")
model.update()

for j in V:
    model.addConstr(
        quicksum(x[i, j] for i in Gbar.neighbors(j)) + x[j, j] >= 1, f"Assign({j})"
    )

for i in V:
    for (j, k) in G.subgraph(Gbar.neighbors(i)).edges():
        model.addConstr(x[i, j] + x[i, k] <= x[i, i], f"BadEdge({i},{j},{k})")
    for j in Gbar.neighbors(i):
        model.addConstr(x[i, j] <= x[i, i], f"Connection({i},{j})")

model.setObjective(quicksum(x[i, i] for i in V), GRB.MINIMIZE)
model.optimize()

color = {}
k = 0
for i in V:
    if x[i, i].X > 0.5:
        color[i] = k
        k += 1

for (i, j) in x:
    if i != j and x[i, j].X > 0.5:
        color[j] = color[i]

print("solution:", color)

制約最適化ソルバーによる求解

上では数理最適化ソルバーを用いてグラフ彩色問題を解いたが,制約最適化ソルバー SCOP を用いると,より簡潔に記述できる.

色数 $K$ を固定した問題を考える.点 $i$ に対して,領域 $\{1,2,\ldots,K\}$ をもった変数 $X_i$ を用いる. 枝 $(i,j) \in E$ に対しては,異なる色(値)をとる必要があるので, $X_i$ と $X_j$ に対する相異制約(Alldiff)を定義する. 破っている制約がなければ,$K$色で彩色可能と判定できる.

以下にコードを示す.

from scop import *

m = Model()

K = 20
nodes = [f"node_{i}" for i in V]
varlist = m.addVariables(nodes, range(K))

for (i, j) in E:
    con1 = Alldiff(f"alldiff_{i}_{j}", [varlist[i], varlist[j]], "inf")
    m.addConstraint(con1)

m.Params.TimeLimit = 10
sol, violated = m.optimize()

if m.Status == 0:
    print("solution")
    for x in sol:
        print(x, sol[x])
    print("violated constraint(s)")
    for v in violated:
        print(v, violated[v])

構築法

グラフ彩色問題に対しては,以下の構築法が代表的である.

  • seq_assignment: 与えられた点の番号の順に,彩色可能な最小の番号の色で塗っていく.
  • largest_first: 点の次数(隣接する点の数)が大きいものから順に彩色する.
  • dsatur: 構築法の途中で得た動的な情報をもとに,次に彩色する点を選択する.具体的には,次に彩色する点を, 隣接する点ですでに使われた色数が最大のもの(同点の場合には,彩色されていない隣接点の数が最大のもの)とする.
  • recursive_largest_fit: 同じ色を塗ることができる点の集合(色クラス)は,互いに隣接していてはいけない. これは,安定集合に他ならない. 新しい色で彩色するための安定集合を順次求めることによって解を構築する.

seq_assignment[source]

seq_assignment(nodes, adj)

Sequential color assignment.

Starting with one color, for the graph represented by 'nodes' and 'adj':

  • go through all nodes, and check if a used color can be assigned;
  • if this is not possible, assign it a new color. Returns the solution found and the number of colors used.

largest_first[source]

largest_first(nodes, adj)

Sequencially assign colors, starting with nodes with largest degree.

Firstly sort nodes by decreasing degree, then call sequential assignment, and return the solution it determined.

dsatur[source]

dsatur(nodes, adj)

Dsatur algorithm (Brelaz, 1979).

Dynamically choose the vertex to color next, selecting one that is adjacent to the largest number of distinctly colored vertices. Returns the solution found and the number of colors used.

recursive_largest_fit[source]

recursive_largest_fit(nodes, adj)

Recursive largest fit algorithm (Leighton, 1979).

Color vertices one color class at a time, in a greedy way. Returns the solution found and the number of colors used.

check[source]

check(nodes, adj, color)

Auxiliary function, for checking if a coloring is valid.

print("*** graph coloring problem ***")
print()

print("instance randomly created")
nodes, adj = gts.rnd_adj_fast(100, 0.5)

print("sequential assignment")
color, K = seq_assignment(nodes, adj)
print("solution: z =", K)
print(color)
print()
print("largest fit")
color, K = largest_first(nodes, adj)
print("solution: z =", K)
print(color)
print()
print("dsatur")
color, K = dsatur(nodes, adj)
print("solution: z =", K)
print(color)
print()
print("recursive largest fit")
color, K = recursive_largest_fit(nodes, adj)
print("solution: z =", K)
print(color)
print()

メタヒューリスティクス

タブーサーチ

彩色数 $K$ を固定した問題を考える.枝の両端点が同色で塗られた枝を「悪い枝」とよぶことにする. 点 $i$ に接続する悪い枝の数 $B(i)$ とすると, この問題における目的関数は以下のように定義される.

$$ \sum_{i=1}^{n} B(i)/2 $$

彩色数 $K$ は固定されているので,もし目的関数が $0$ となる解が得られたときは,$K$ 彩色が得られたことになる. 彩色数の上限は点 の数 $n$ であるので,$2$ 分探索法を用いれば 最悪でも $\lceil \log_2 n \rceil$ 回だけ彩色数 $K$ を固定した問題を解けば原問題の最適解が得られる. ちなみに,$\lceil \cdot \rceil$ は天井関数(ceiling function)であり, $\cdot$ 以上の最小の整数を表す.

この問題の目的関数値を減らすためには,接続する悪い枝の数 $B(i)$ が正の値をもつ点の色を変える必要がある. したがって,$B(i)>0$ である点に限定して色を変更する操作を行う方が良いと考えられる. このような近傍の制限は,近傍が広い(近傍に含まれる解の数が多い)ときに有効である.

以下に,彩色数 $K$ を固定した場合に対する制限付きmove近傍を用いたタブーサーチを示す. 禁断リスト $tabu$ には,点と色のペアを保管する.

tabu_search(nodes, adj, K, color, tabulen, max_iter, report=None)

Execute a tabu search for Graph Coloring starting from solution 'color'.

The number of colores allowed is fixed to 'K'. This function will search a coloring such that the number of conflicts (adjacent nodes with the same color) is minimum. If a solution with no conflicts is found, it is returned immediately.

Parameters:

  • nodes, adj - graph definition
  • K - number of colors allowed
  • colors - initial solution
  • tabulen - lenght of the tabu status
  • max_iter - allowed number of iterations
  • report - function used for output of best found solutions

Returns the best solution found and its number of conflicts.

find_move[source]

find_move(nodes, adj, K, color, bad_degree, best_color)

Find a non-tabu color exchange in a node on solution 'color'.

Tabu information is implicit in 'best_color': tabu indices are have value 'None'. The non-tabu neigbor solution (node and respective color) with largest improvement on the 'bad_degree' is selected.

Returns the chosen node (color is implicit in 'best_color'), and the improvement on bad degree to which the movement leads.

move[source]

move(nodes, adj, K, color, bad_degree, best_color, i_star, it, tabu, tabulen)

Execute a movement on solution 'color', and update the tabu information.

Node 'i_star' is changed from its previous color to its 'best_color'.

rsatur[source]

rsatur(nodes, adj, K)

Saturation algorithm adapted to produce K classes.

Dynamically choose the vertex to color next, selecting one that is adjacent to the largest number of distinctly colored vertices. If a non-conflicting color cannot be found, randomly choose a color from the K classes. Returns the solution constructed.

rand_color[source]

rand_color(nodes, K)

Randomly assign a color from K classes to a set of nodes.

Returns the solution constructed.

evaluate[source]

evaluate(nodes, adj, color)

Evaluate the number of conflicts of solution 'color'.

calc_bad_degree[source]

calc_bad_degree(nodes, adj, color, K)

Calculate the number of conflicts for each node switching to each color.

Returns two structures:

  • dictionary 'bad_degree[i,k]', which contains the conflicts that will be obtained if node 'i' switches to color k
  • list 'best_color', holding, for each node, index 'k' of color that will produce the minimum of conflicts is assigned to the node.
nodes, adj = gts.rnd_adj_fast(100, 0.5)
K = 15  # tentative number of colors
print("tabu search, trying coloring with", K, "colors")
color = rsatur(nodes, adj, K)
print("starting solution: z =", evaluate(nodes, adj, color))
print("color:", color)
print()

print("starting tabu search")
tabulen = K
max_iter = 1000
color, sum_bad_degree = tabu_search(nodes, adj, K, color, tabulen, max_iter)
print("final solution: z =", sum_bad_degree)
print("color:", color)

遺伝的アルゴリズムとタブーサーチの融合法

タブーサーチは,広い範囲の問題例に対して,比較的短時間で良好な近似解を算出するので推奨されるが, より長い時間を要してさらに良い解を探索したい場合には,複数の解を保持して, その集団を改良していく方法を用いることができる.ここでは簡単な遺伝的アルゴリズムとの融合を用いる. この融合法は,改善法を遺伝的アルゴリズムに組み込んだ方法(遺伝的近傍探索法)と考えられる.

まず,集団から親を選択する方法について述べる. 集団 $P$ 内に保持された解を目的関数値(この場合には悪い枝の数)の小さい順に $0,1,\cdots,|P|-1$ と並べておく. この順位をランクとよぶ.ランクの小さな解を優先し,かつランダムに親を選択することを考える. $i$ 番目のランクをもつ解が親として選択される確率を $|P|-i$ に比例させるものとする. $m=|P| (|P| +1)/2$ としたとき,選択確率は $$ \frac{|P|-i}{m} $$ となる.

この確率でランダムに選択された相異なる2 つの解(親)に対応する $K$ 分割を, $\Upsilon^1=\{ V_1^1,\ldots,V_K^1 \}$,$\Upsilon^2=\{ V_1^1,\ldots,V_K^2 \}$ とする. 2 つの親の形質をなるべく均等に取り入れ,かつ各色クラスの位数(含まれる点の個数)が大きくなるようにしたいので, 各親から交互になるべく位数の大きな色クラスを選択することにする. これを擬似コードとして記述すると以下のようになる.

$\Upsilon^1=\{ V_1^1,\ldots,V_K^1 \}$,$\Upsilon^2=\{ V_1^1,\ldots,V_K^2 \}$ に対する交叉

  • 生成する子 $\Upsilon :=\emptyset$
  • for all $i = 1, \ldots, K$ do
    • $i$ が奇数のときは親番号 $p=1$,偶数のときは親番号 $p=2$
    • $k^* := argmax_{k} \{ |V_k^p| \}$
    • 色クラス $V_{k^*}^p$ を子 $\Upsilon$ に追加
    • 色クラス $V_{k^*}^p$ 内の点を $\Upsilon^1, \Upsilon^2$ から削除
    • まだ色が塗られていない点に対してランダムに $1,\ldots,K$ を彩色
  • return $\Upsilon$

上の交叉を用いることによって,遺伝的アルゴリズムとタブーサーチの融合法が構築できる.

gcp_ga[source]

gcp_ga(nodes, adj, K, ngen, nelem, TABULEN, TABUITER, report=None)

Evolve a Genetic Algorithm, with crossover and mutation based on Hao 1999.

A population of 'nelem' elements is evolved for 'ngen' generations. The number of colores allowed is fixed to 'K'. This function will search a coloring such that the number of conflicts (adjacent nodes with the same color) is minimum. If a solution with no conflicts is found, it is returned immediately.

Parameters:

  • K - number of colors
  • ngen - number of generations
  • nelem - number of elements to keep in population
  • TABUITER - number of tabu search iterations to do on each newly created solution
  • report - function to call to log best found solutions

Returns the best solution found and its number of conflicts.

crossover[source]

crossover(nodes, s1, s2, K)

Create a solution based on 's1' and 's2', according to Hao 1999.

nodes, adj = gts.rnd_adj_fast(100, 0.5)
K = 15  # tentative number of colors
print(
    "genetic algorithm (intensification with tabu search), trying coloring with",
    K,
    "colors",
)
color = rsatur(nodes, adj, K)
print("starting solution: z =", evaluate(nodes, adj, color))
print("color:", color)
print()

print("starting evolution with genetic algorithm")
nelem = 10
ngen = 100
TABULEN = K
TABUITER = 100
color, sum_bad_degree = gcp_ga(nodes, adj, K, ngen, nelem, TABULEN, TABUITER)
print("final solution: z =", sum_bad_degree)
print("color:", color)
G = gts.to_nx_graph(nodes, adj)
# print(G.edges())
pos = nx.layout.spring_layout(G)
node_color = [color[i] for i in G.nodes()]
nx.draw(
    G,
    pos=pos,
    with_labels=False,
    node_color=node_color,
    node_size=50,
    width=0.1,
    cmap=plt.cm.cool,
    edge_color="black",
)  

枝彩色問題

グラフ彩色問題が点に色を塗るのに対して,枝彩色問題(edge coloring problem)では,枝に色を塗る. グラフ理論では,2つの問題は区別して研究されているが,最適化の観点では(簡単に帰着できるという意味で)ほぼ同値な問題である.

無向グラフ $G=(V,E)$ に対する枝彩色問題は, 枝(点の対)上に点を配置し,端点を共有する枝に対応する点の間に枝をはったグラフ(線グラフ) $L$ に対する(点)彩色に帰着される.

例として完全グラフに対する枝彩色を行う. $8$ 点の完全グラフに対する枝彩色は $7$ になることが知られており,これは $8$ チームの総当りのトーナメントが $7$ 日で完了することを表している.

G = nx.complete_graph(8)
L = nx.line_graph(G)
nx.draw(G)

点彩色問題に変換したグラフ(線グラフ)を描く.

nx.draw(L)

点彩色問題をメタヒューリスティクスで解く.

K = 7
mapping = dict(zip(L.nodes(), list(range(len(L)))))
G2 = nx.relabel_nodes(L, mapping)

nodes = G2.nodes()
adj = [set([]) for i in nodes]
for (i, j) in G2.edges():
    adj[i].add(j)
    adj[j].add(i)

color = rsatur(nodes, adj, K)
print("starting solution: z =", evaluate(nodes, adj, color))
print("color:", color)
print()

print("starting evolution with genetic algorithm")
nelem = 10
ngen = 100
TABULEN = K
TABUITER = 100
color, sum_bad_degree = gcp_ga(nodes, adj, K, ngen, nelem, TABULEN, TABUITER)
print("final solution: z =", sum_bad_degree)
print("color:", color)

以下のような7色の点彩色が得られる.

nx.draw(
    L,
    with_labels=False,
    node_color=color,
    node_size=100,
    cmap=plt.cm.cool,
    edge_color="black",
    width=1,
)

枝彩色に戻して描画する. 色はトーナメントの日を表し,7日でトーナメントが終了することが分かる.

col = {}
for i, (u, v) in enumerate(L.nodes()):
    col[u, v] = color[i]
edge_color = []
for (u, v) in G.edges():
    edge_color.append(col[u, v])
nx.draw(
    G,
    with_labels=False,
    node_color="b",
    node_size=100,
    cmap=plt.cm.afmhot,
    edge_color=edge_color,
    width=5,
)