Bit-flip Heuristic Algorithm¶

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.lines import Line2D
plt.style.use('seaborn-darkgrid')

plt.rcParams['axes.labelsize'] = 16
plt.rcParams['legend.framealpha'] = 0.0
plt.rcParams['legend.fontsize'] = 14
plt.rcParams['mathtext.fontset'] = 'stix'
plt.rcParams['xtick.labelsize'] = 14
plt.rcParams['ytick.labelsize'] = 14

markers = Line2D.filled_markers
linestyles = [k for k, v in Line2D.lineStyles.items() if 'nothing' not in v]

def calc_vios(state):
    N = len(state)
    sum_col = np.sum(state, axis=0)
    sum_row = np.sum(state, axis=1)

    vios = np.zeros((N, N))
    for k in range(N):
        for l in range(N):
            vios[k, l] = sum_col[l] + sum_row[k] - 2

    return vios


def bfh_algo(init_state):
    state = np.array(init_state)
    N = len(state)
    vios = calc_vios(state)
    while np.any(vios != 0):
        if np.any(vios >= 1):
            mult_max = np.argwhere(vios * state == np.max(vios * state))
#             if len(mult_max) != 0:
#                 print('mult_max:', mult_max)
#             max_idx = np.argmax(vios * state)
#             k, l = max_idx // N, max_idx % N
            max_idx = mult_max[np.random.choice(len(mult_max))]
            k, l = max_idx
#             print('max:', k, l)
            state[k, l] = 0
        else:
            mult_min = np.argwhere(vios * (1 - state) == np.min(vios * (1 - state)))
#             if len(mult_min) != 0:
#                 print('mult_min:', mult_min)
#             min_idx = np.argmin(vios * (1 - state))
#             k, l = min_idx // N, min_idx % N
            min_idx = mult_min[np.random.choice(len(mult_min))]
            k, l = min_idx
#             print('min:', k, l)
            state[k, l] = 1
        vios = calc_vios(state)

    return state


def bfh_algo_r(init_state):
    state = np.array(init_state)
    N = len(state)
    vios = calc_vios(state)
    while np.any(vios != 0):
        if np.any(vios <= -1):
            min_idx = np.argmin(vios * (1 - state))
            k, l = min_idx // N, min_idx % N
            print('min:', k, l)
            print(vios)
            state[k, l] = 1
        else:
            max_idx = np.argmax(vios * state)
            k, l = max_idx // N, max_idx % N
            print('max:', k, l)
            print(vios)
            state[k, l] = 0
        vios = calc_vios(state)

    return state

N = 20
init_state = np.random.choice([0, 1], size=(N, N), p=[0.7, 0.3])
print(init_state)

[[0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1]
 [1 1 0 0 0 1 0 0 1 1 1 0 0 0 0 1 0 1 0 0]
 [1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0]
 [0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 0]
 [0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0]
 [1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0]
 [0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 0 1 0 0 1]
 [0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0]
 [0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0]
 [0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1]
 [0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0]
 [0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 0 0 1 0]
 [1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0]
 [0 1 1 0 1 1 1 0 1 0 0 0 1 0 1 1 0 0 0 0]
 [1 1 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 1]
 [0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0 1 0 0]
 [1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0]
 [0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 1 1 1]
 [0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0]]

%%time
states = []
for _ in range(100):
    updated_state = bfh_algo(init_state)
    if updated_state.tolist() not in states:
        print(np.sum(init_state != updated_state))
        states.append(updated_state.tolist())

117
117
113
115
115
113
113
117
115
115
113
115
115
115
111
115
113
115
117
111
115
115
119
113
113
115
115
111
117
117
115
117
117
115
115
115
115
117
115
119
117
117
111
115
113
117
113
113
117
115
115
113
115
115
113
119
115
115
113
113
115
113
117
117
113
115
113
115
115
115
113
115
117
115
115
113
115
113
119
113
113
115
115
113
113
113
111
117
119
111
113
113
117
115
117
113
113
113
117
113
CPU times: user 4.72 s, sys: 197 ms, total: 4.91 s
Wall time: 4.81 s

len(states)

states[0]

[[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
 [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
 [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

N = 4
init_state = np.random.choice([0, 1], size=(N, N), p=[0.7, 0.3])
print(init_state)

# print(calc_vios(init_state))

# updated_state = bfh_algo(init_state)
# print(updated_state)

updated_state = bfh_algo_r(init_state)
print(updated_state)

[[0 1 0 0]
 [0 0 0 1]
 [1 0 1 1]
 [0 0 0 1]]
max: 2 3
[[0. 0. 0. 2.]
 [0. 0. 0. 2.]
 [2. 2. 2. 4.]
 [0. 0. 0. 2.]]
max: 1 3
[[0. 0. 0. 1.]
 [0. 0. 0. 1.]
 [1. 1. 1. 2.]
 [0. 0. 0. 1.]]
min: 1 0
[[ 0.  0.  0.  0.]
 [-1. -1. -1. -1.]
 [ 1.  1.  1.  1.]
 [ 0.  0.  0.  0.]]
max: 2 0
[[1. 0. 0. 0.]
 [1. 0. 0. 0.]
 [2. 1. 1. 1.]
 [1. 0. 0. 0.]]
[[0 1 0 0]
 [1 0 0 0]
 [0 0 1 0]
 [0 0 0 1]]

mullzhang's notes

Bit-flip Heuristic Algorithm

Bit-flip Heuristic Algorithm¶

Bit-flip Heuristic Algorithm¶