Configuration Checking

CC也许在组合问题中可以大展拳脚，但是在CNP这个问题中，应该无法与MACNP结合，因为MACNP在local search本地提高时，add to solution与remove from solution的效率相当高。
而且，由于每次local search提高，只允许stuck 1000步，每次add a vertex to solution其他点的weight都会++，所以重复选取同样的点的概率相当低，所以使用CC避免cycling没有必要。

1.for Satisfiability

Variables = {x1, x2, , , xn}, xi = 0 / 1
literal: x, 非x
clause: 几个literal的析取/或
CNF: 几个clause的合取/并
CL(x): x有出现的所有clause的集合
N(x): 有与x出现在任一clause的variable的集合
w(c): 每个clause的权重
score(x): 翻转x的值，使得总权重的增量，< 0表示总权重减小
δ-satisfied: a clause is δ-satisfied if exactly δ literals in that clause are true
subscore(x): submake(x) - subbreak(x)，其中subscore(x)为翻转x能使1-satisfied的clause变成2-satisfied的数量，subbreak(x)为翻转x使得2-satisfied的clause变成1-satisfied的数量
age(x): 距离x上次翻转经过了多少个步骤

1.NVCC

NVChanged(x) = 1 自x的上次翻转以来，x的邻居N(x)中有任意一个变量翻转了
NVDvars: score(x) > 0, NVChanged(x) = 1
SDvars: score(x) > mean(w)大于所有clause的平均权重值
CCA：
if(!NVDvars.empty()) picks a variable in NVDvars with the greatest score
else picks a variable in SDvars with greatest score

2.CSCC

CSChanged(x) = 1 自x的上次翻转以来，CL(x)中有至少一个clause状态改变/satisfied<->unsatisfied
CSDvars: score(x) > 0, CSChanged(x) = 1

3.DCCA

1.CSDvars为NVDvars的子集
2.The DCCA Heuristic
if(!CSDvars.empty()) return variable in CSDvars with greatest score
else if(!NVDvars.empty()) return variable in NVDvars with greatest score
else if(!SDvars.empty()) return variable in SDvars with greatest score

neibor_removed
neibor_added
2087 2085 2113 2089 2098 2085 2145 2097 2149 2072
SP0 = 50
f_best 2072
f_avg 2102.0
succeed_times 1
t_avg 272.0
init_cost_time 40.4
func_time 1111.2
iter 36604429

MA

WS500

MA

2089 2098 2085 2081 2085 2085 2085 2085 2085 2085
f_best 2081
f_avg 2086.3
succ 1
t_avg 286.1
init_cost_time 12.6
func_time 580.5
iter 90744488

MA_SP0

2072 2085 2085 2072 2081 2085 2072 2085 2072 2085
f_best 2072
f_avg 2079.4
succ 4
t_avg 1906.9
init_cost_time 9.4
func_time 3501.9
iter 717133611
939681

MA_weight

2098 2089 2098 2098 2120 2085 2105 2085 2098 2108 2108
f_best 2085
f_avg 2098.4
succ 2
t_avg 174.2
init_cost_time 9.0
func_time 581.7
iter 113388279

MA_SP0_weight

f_best 2081
f_avg 2089.6
succ 2
t_avg 51.6
init_cost_time 8.5
func_time 1739.0
iter 409768347

ER2500

MA

f_best 926953
f_avg 953125.2
succ 1
t_avg 3381.2
init_cost_time 86.7
func_time 3580.9
iter 73046283

MA_SP0

921720 947717 944143 957465 946453 931462 987189 929706 934888 932595
f_best 921720
f_avg 943333.8
succ 1
t_avg 3209.5
init_cost_time 84.6
func_time 3581.8
iter 75881194

MA_weight

f_best 924121
f_avg 952785.9
succ 1
t_avg 2016.6
init_cost_time 80.2
func_time 3577.7
iter 72959417

MA_SP0_weight

powergrid

MA

15951 15943 15924 15946 15915 15925 16012 15957 15932 15943
f_best 15915
f_avg 15944.8
succ 1
t_avg 1183.7
init_cost_time 20.6
func_time 3520.3
iter 163906811

MA_SP0

15855 15854 15859 15860 15854 15864 15864 15857 15858 15857
f_best 15854
f_avg 15858.2
succ 2
t_avg 3197.4
init_cost_time 21.0
func_time 3567.6
iter 206015104

MA_weight

MA_SP0_weight

Hamilton5000

MA

8409845 8418716 8344683 8507340 8399376 8474275 8421614 8337870 8404270 8387036
f_best 8337870
f_avg 8410502.5
succ 1
t_avg 3578.8
init_cost_time 372.5
func_time 3509.9
iter 16691082

MA_SP0

8444992 8362194 8388417 8262830 8287705 8365535 8414964 8357734 8372868
f_best 8262830
f_avg 8361915.4
succ 1
t_avg 3604.1
init_cost_time 252.7
func_time 3127.5
iter 22318866

MA_weight

MA_SP0_weight

MA
f_best 2102
f_avg 2102.0
succ 1
t_avg 30.1
init_cost_time 9.0
func_time 1746.7
iter 31036697

f_best 2191
f_avg 2191.0
succ 1
t_avg 24.0
init_cost_time 8.6
func_time 568.4
iter 8020417

f_best 2150
f_avg 2150.0
succ 1
t_avg 37.6
init_cost_time 11.6
func_time 567.1
iter 7947582

modified_update
f_best 2096
f_avg 2096.0
succ 1
t_avg 307.9
init_cost_time 8.4
func_time 574.8
iter 9854834

f_best 2085
f_avg 2085.0
succ 1
t_avg 410.5
init_cost_time 9.5
func_time 577.4
iter 10134649

f_best 2085
f_avg 2085.0
succ 1
t_avg 492.4
init_cost_time 9.4
func_time 573.4
iter 11702445

f_best 2085
f_avg 2085.0
succ 1
t_avg 151.5
init_cost_time 9.9
func_time 574.3
iter 11689858

SP
f_best 2087
f_avg 2087.0
succ 1
t_avg 424.1
init_cost_time 13.6
func_time 575.8
iter 9141083

Hamilton5000
f_best = 920040

MACNP
SP0 = 85
f_best 2087
f_avg 2087.0
succeed_times 1
t_avg 168.5
init_cost_time 25.0
func_time 612.0
iter 2836696

include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

define maxn 30100
#define BETA 0.6
#define SP0 85
#define MaxIdleIters 1000
#define parent_num 20

struct solution_struct{
vector solution;
int connectivity;
int total_distance;
};

struct scomp{
vector list;
int size, key_vertex;
};

int vertex_num, K, visited_vertex_num, run_times;
vector adjlist[maxn];
int visited_vertex[maxn];
int weight[maxn], vertex_cpn_id[maxn];
int int_array[maxn];
bool deleted[maxn];
scomp component[maxn];
solution_struct parent[parent_num + 10];
vector solution_operating, S0, S_best, local_best_solution;
stack unused_cpn_id;
set< pair > used_cpn_id;
int f_best, f_avg, succ;
double t_avg, init_cost_time, func_time;
clock_t start_time;
long long iter;
double time_out;

int rank_cnty[parent_num + 10];
int rank_dis[parent_num + 10];
int indexs[parent_num + 10];
stack to_visit;
ofstream out;
vector min_cnty;
int dis;
int cnty_operating;

inline double time_cost() {
return (double)(clock() - start_time) / CLOCKS_PER_SEC;
}

inline bool timeout() {
return time_cost() > time_out;
}

void read_graph(string file_name) {
ifstream in;
in.open(file_name);
string s;
getline(in, s);
istringstream iss(s);
iss >> vertex_num;
int num;
char c;
for (int i = 0; i adjlist[i].clear();
getline(in, s);
istringstream iss(s);
iss >> num >> c;
while (iss >> num) adjlist[i].push_back(num);
}
}

void depth_first_search_split(int start, vector& visited) {
visited_vertex_num = 0;
while(!to_visit.empty()) to_visit.pop();
to_visit.push(start);
visited[start] = true;
int v;
while(!to_visit.empty()) {
v = to_visit.top();
to_visit.pop();
visited_vertex[visited_vertex_num++] = v;
for(auto &n : adjlist[v])
if(!deleted[n] && !visited[n]) to_visit.push(n), visited[n] = true;
}

int cpn_id = unused_cpn_id.top();<br />    unused_cpn_id.pop();<br />    used_cpn_id.insert(make_pair(visited_vertex_num, cpn_id));<br />    scomp &cur = component[cpn_id];<br />    cur.list.resize(visited_vertex_num);<br />    cur.key_vertex = visited_vertex[0];<br />    cur.size = visited_vertex_num;<br />    for (int j = 0; j < visited_vertex_num; ++j) {//优化为不需要使用这个循环<br />        vertex_cpn_id[visited_vertex[j]] = cpn_id;<br />        cur.list[j] = visited_vertex[j];<br />        if (weight[visited_vertex[j]] > weight[cur.key_vertex])<br />            cur.key_vertex = visited_vertex[j];<br />        //visited[visited_vertex[j]] = false;<br />    }<br />}

int seperate_graph() {
while (!unused_cpn_id.empty()) unused_cpn_id.pop();
for (int i = 0; i <= vertex_num; ++i) unused_cpn_id.push(i); //add one more
used_cpn_id.clear();
cnty_operating = 0;
vector visited(vertex_num, false);
for (int i = 0; i < vertex_num; ++i)
if (!deleted[i] && !visited[i]) {
depth_first_search_split(i, visited);
for (int j = 0; j visited[visited_vertex[j]] = true;//优化为不需要使用这个循环
cnty_operating += (visited_vertex_num - 1) * visited_vertex_num / 2;
}
return cnty_operating;
}

int select_large_component() {
int L = used_cpn_id.begin() -> first, R = used_cpn_id.rbegin() -> first;//使用set记录使用过的id，避免两次遍历
int bound = (L + R) >> 1;
int cnt = 0;
for (auto it = used_cpn_id.rbegin(); it != used_cpn_id.rend() && it -> first >= bound; ++it)//从后往前/从大到小遍历，遇到不够大的终止
int_array[cnt++] = it -> second;
return int_array[rand() % cnt];
}

void add_to_solution(int add_vertex) {
int decrease = 0, cpn_size = 1;
int cpn_id = vertex_cpn_id[add_vertex];
deleted[add_vertex] = true;
vector visited(vertex_num, false);
for (auto &n : adjlist[add_vertex])
if (!deleted[n] && vertex_cpn_id[n] == cpn_id) {//第二个判断条件表示是否已经访问过
depth_first_search_split(n, visited);
cnty_operating += (visited_vertex_num - 1) visited_vertex_num / 2;
cpn_size += visited_vertex_num;
for (int i = 0; i < visited_vertex_num; ++i)
weight[visited_vertex[i]]++;//可以放在深度遍历里面完成
}
cnty_operating -= cpn_size (cpn_size - 1) / 2;
unused_cpn_id.push(cpn_id);
used_cpn_id.erase(make_pair(component[cpn_id].size, cpn_id));
}

void remove_from_solution() {
int increase = maxn maxn, back_vertex = -1;
int idx = -1;
for (auto &v : solution_operating) {//修改为传统迭代
++idx;
int delta = 0, cnt = 0, cpn_id;
int sub_vertex_num = 0;
vector visited(vertex_num, false);
for (auto &n : adjlist[v])
if (!deleted[n])
if (!visited[cpn_id = vertex_cpn_id[n]]) {//写在同一个if
visited[cpn_id] = true;
delta += sub_vertex_num component[cpn_id].size;
sub_vertex_num += component[cpn_id].size;
}
delta += sub_vertex_num;
for (auto &n : adjlist[v])
if (!deleted[n]) visited[vertex_cpn_id[n]] = false;
if (delta <= increase) increase = delta, back_vertex = idx;
}
swap(solution_operating[back_vertex], solution_operating.back());//放到最后再删除，效率较高
back_vertex = solution_operating.back();
solution_operating.pop_back();
deleted[back_vertex] = false;
weight[back_vertex] = 0;
cnty_operating += increase;
int cpn_id;
vector visited(vertex_num, false);
for (auto &adj : adjlist[back_vertex])
if (!deleted[adj])
if (!visited[cpn_id = vertex_cpn_id[adj]]) {
visited[cpn_id] = true;
unused_cpn_id.push(cpn_id);
used_cpn_id.erase(make_pair(component[cpn_id].size, cpn_id));
}
for (auto &adj : adjlist[back_vertex])
if (!deleted[adj]) visited[vertex_cpn_id[adj]] = false;
vector tmp_visited(vertex_num, false);
depth_first_search_split(back_vertex, tmp_visited);
}

void component_based_neiborhood_search() {
clock_t func_start_time = clock();
fill(weight, weight + vertex_num, 0);
local_best_solution = solution_operating;
int local_best_cnty = seperate_graph();//放在initialize和crossover
int idle_iter = 0;
while (idle_iter < MaxIdleIters) {
int add_vertex = component[select_large_component()].key_vertex;
solution_operating.push_back(add_vertex);
add_to_solution(add_vertex);
remove_from_solution();
++iter;
if (cnty_operating < local_best_cnty) {
local_best_solution = solution_operating;
local_best_cnty = cnty_operating;
idle_iter = 0;
}
else idle_iter++;
}
for (auto &v : solution_operating) deleted[v] = false;
solution_operating = local_best_solution;
cnty_operating = local_best_cnty;
for (auto &v : solution_operating) deleted[v] = true;
func_time += (double)(clock() - func_start_time) / CLOCKS_PER_SEC;
}

double get_distance(vector &S1, vector &S2) {
int Sim = 0;
vector visited(vertex_num, false);
for (auto &num : S1) visited[num] = true;
for (auto &num : S2) Sim += visited[num];
for (auto &num : S1) visited[num] = false;
return K - Sim;
}

int deth_first_search(int start, vector& visited) {
stack s;
s.push(start);
visited[start] = true;
int size = 0;
while(!s.empty()) {
int vertex = s.top();
s.pop();
size++;
for(int i = 0; i < adjlist[vertex].size(); ++i) {
int neibor = adjlist[vertex][i];
if(!deleted[neibor] && !visited[neibor]) {
s.push(neibor);
visited[neibor] = true;
}
}
}
return size;
}

int get_connectivity() {//只需要得到连通度，不需要将原图分割、记录子图信息时，使用该函数
int connectivity = 0;
vector visited(vertex_num, false);
for(int i = 0; i < vertex_num; ++i) {
if(!deleted[i] && !visited[i]) {
int size = deth_first_search(i, visited);
connectivity += size * (size - 1) / 2;
}
}
return connectivity;
}

void population_initialization() {
for (int i = 0; i < parent_num; ++i) {
fill(deleted, deleted + vertex_num, false);
solution_operating.resize(K);
for (int j = 0; j < K; ++j) {
solution_operating[j] = rand() % vertex_num;
while (deleted[solution_operating[j]]) solution_operating[j] = rand() % vertex_num;
deleted[solution_operating[j]] = true;
}
component_based_neiborhood_search();
while (true) {
bool differ = true;
for(int j = 0; j < i; ++j) {
bool same = true;
for(auto &v : parent[j].solution)
if(!deleted[v]) {
same = false;
break;
}
if(same) {
differ = false;
break;
}
}
if (differ) break;
int idx = rand() % K;
deleted[solution_operating[idx]] = false;
int v = rand() % vertex_num;
while (deleted[idx]) v = rand() % vertex_num;
deleted[v] = true;
solution_operating[idx] = v;
}
parent[i].solution = solution_operating;
int cnty;
parent[i].connectivity = (cnty = get_connectivity());
cout << i << “ pool initialization cnty : “ << cnty << endl;
parent[i].total_distance = 0;
for(int j = 0; j < i; ++j) {
dis = 0;
for(auto &v : parent[j].solution) dis += deleted[v];
dis = K - dis;
parent[i].total_distance += dis;
parent[j].total_distance += dis;
}
}
}

void double_backbone_based_crossover(vector &S1, vector &S2) {
int cnt = 0;
for (auto &v : solution_operating) deleted[v] = false;
solution_operating.clear();
vector visited(vertex_num, false);
for (auto &v : S1) visited[v] = true;
for (auto &v : S2)
if (visited[v]) {
solution_operating.push_back(v);
deleted[v] = true;
visited[v] = false;
}
else int_array[cnt++] = v;
for (auto &v : S1)
if (visited[v]) int_array[cnt++] = v;//S1独有的点visited没有置为false
for (int i = 0; i < cnt; ++i)
if (rand() % 100 <= SP0) {
solution_operating.push_back(int_array[i]);
deleted[int_array[i]] = true;
}
if (solution_operating.size() == K) return;
seperate_graph();
if (solution_operating.size() < K) {
for (auto &v : S1) visited[v] = true;
for (auto &v : S2) visited[v] = true;//XB里面有些点并没有加入solution_operating，这时visited = true
while (solution_operating.size() < K) {//后面add_to_solution会调用dfs_split，里面会使用visited数组，这会导致误以为这些点被删掉
scomp &cpn = component[select_large_component()];
int idx = rand() % cpn.size;
if (!visited[cpn.list[idx]]) {
solution_operating.push_back(cpn.list[idx]);
add_to_solution(solution_operating.back());
}
}
}
while (solution_operating.size() > K) remove_from_solution();
}

bool cnty_compare(int i, int j) {return parent[i].connectivity < parent[j].connectivity;}
bool distance_compare(int i, int j) {return parent[i].total_distance > parent[j].total_distance;}

void rank_based_pool_updating() {
parent[parent_num] = solution_struct{solution_operating, cnty_operating, 0};
for (int i = 0; i < parent_num; ++i) {
int tmp = get_distance(parent[i].solution, parent[parent_num].solution);
parent[parent_num].total_distance += tmp;
parent[i].total_distance += tmp;
}
stable_sort(indexs, indexs + parent_num + 1, cnty_compare);
for(int i = 0; i < parent_num + 1; ++i) rank_cnty[indexs[i]] = i;
stable_sort(indexs, indexs + parent_num + 1, distance_compare);
for(int i = 0; i < parent_num + 1; ++i) rank_dis[indexs[i]] = i;
int idx = -1, max_score = -1, score;
for(int i = 0; i < parent_num + 1; ++i) {
score = BETA rank_cnty[i] + (1 - BETA) rank_dis[i];
if(score > max_score) idx = i, max_score = score;
}
if (idx != parent_num) swap(parent[idx], parent[parent_num]);
for (int i = 0; i < parent_num; ++i)
parent[i].total_distance -= get_distance(parent[i].solution, parent[parent_num].solution);
}

void critical_node_problem() {
srand(time(0));
int local_best_cnty = maxn * maxn;
S0.clear();
start_time = clock();
population_initialization();
init_cost_time += time_cost();
for (int i = 0; i < parent_num; ++i)//直接在初始化时完成
if (parent[i].connectivity < local_best_cnty){
local_best_cnty = parent[i].connectivity;
S0 = parent[i].solution;
}

//start_time=clock();<br />    double cost_time = 0;
fill(weight, weight + vertex_num, 0);<br />    while (!timeout()) {<br />        int Si = rand() % parent_num, Sj = rand() % parent_num;<br />        while (Si == Sj) Si = rand() % parent_num, Sj = rand() % parent_num;//不用参数，直接用全局变量<br />        double_backbone_based_crossover(parent[Si].solution, parent[Sj].solution);<br />        component_based_neiborhood_search();<br />        cout << "best connectivity once : " << local_best_cnty << " / " << cnty_operating << endl;<br />        cout << "best ever : " << f_best << endl;<br />        //cout << solution_operating[0] << " " << solution_operating[1] << endl;<br />        if (cnty_operating < local_best_cnty) {<br />            S0 = solution_operating;<br />            local_best_cnty = cnty_operating;<br />            cost_time = time_cost();<br />        }<br />        rank_based_pool_updating();//不用参数，直接用全局变量<br />    }
if (local_best_cnty < f_best) {<br />S_best = S0;<br />f_best = local_best_cnty;<br />t_avg = cost_time;<br />succ = 1;<br />}<br />else if (local_best_cnty == f_best) t_avg += cost_time, succ++;<br />min_cnty.push_back(local_best_cnty);<br />f_avg += local_best_cnty;<br />out << local_best_cnty << endl;<br />}

void print(vector &solution_operating) {
sort(solution_operating.begin(), solution_operating.end());
for (auto &vertex : solution_operating) cout << vertex << “ “;
fill(deleted, deleted + vertex_num, false);
for (auto &num : solution_operating) deleted[num] = true;
cout << “\n” << seperate_graph() << endl;
}

int one_benchmark(string file_name, int k) {
min_cnty.clear();
read_graph(file_name);
K = k;
f_best=vertex_num*vertex_num, f_avg=0, succ=0;
t_avg=0; init_cost_time=0; func_time=0; iter=0;
for (int i=0; icout << fixed;
cout << “f_best “ << f_best << “\n”;
cout << “f_avg “ << setprecision(1) << double(f_avg)/run_times << “\n”;
cout << “succ “ << succ << “\n”;
cout << “t_avg “ << setprecision(1) << t_avg/succ << “\n”;
cout << “init_cost_time “ << setprecision(1) << init_cost_time/run_times << “\n”;
cout << “func_time “ << setprecision(1) << func_time/run_times << “\n”;
cout << “iter “ << iter << “\n”;

out << fixed;
for(auto &cnty : min_cnty) out << cnty << “ “;
out << endl;
out << “f_best “ << f_best << “\n”;
out << “f_avg “ << setprecision(1) << double(f_avg)/run_times << “\n”;
out << “succ “ << succ << “\n”;
out << “t_avg “ << setprecision(1) << t_avg/succ << “\n”;
out << “init_cost_time “ << setprecision(1) << init_cost_time/run_times << “\n”;
out << “func_time “ << setprecision(1) << func_time/run_times << “\n”;
out << “iter “ << iter << “\n”;
system(“pause”);
return 0;
}

int main() {
for(int i = 0; i < parent_num + 1; ++i) indexs[i] = i;
vector file_names = {“BenchMarks/cnd/WattsStrogatz_n500.txt”, “BenchMarks/cnd/ErdosRenyi_n2500.txt”,
“BenchMarks/RealInstances/powergrid.txt”, “BenchMarks/RealInstances/Hamilton5000.txt”};
vector Ks = {125, 200, 494, 500};
string result_file_name = “results_MA.txt”;
time_out = 600;
run_times = 1;
out.open(result_file_name);
for(int i = 0; i < 1; ++i) one_benchmark(file_names[i], Ks[i]);
system(“pause”);
return 0;
}

实验数据

WS500

MA
2146 2104 2091 2129 2099 2140 2130 2094 2098 2134
SP0 = 85
f_best 2091
f_avg 2116.5
succeed_times 1
t_avg 115.8
init_cost_time 16.3
func_time 3572.6
iter 330225015

MA_modified_SP0
2087 2085 2072 2085 2087 2081 2085 2085 2072 2085
SP0 = 0
f_best 2072
f_avg 2082.4
succeed_times 2
t_avg 1389.2
init_cost_time 13.8
func_time 3558.4
iter 389873773

MA_modified_SP0_weight
2085 2085 2085 2085 2085 2081 2072 2087 2085 2085
SP0 = 0
f_best 2072
f_avg 2083.5
succeed_times 1
t_avg 327.1
init_cost_time 22.9
func_time 3594.0
iter 194379671

ER2500

MA
980392, 981543, 984477, 1000657, 987069, 1017198, 990911, 939597, 1012281, 977125, 972153, 965371, 981783, 964957, 950740, 999123, 992074, 977793, 974920, 1012557, 984539, 1019918, 980747, 978320, 1002024, 976516, 994421, 990079, 994613, 968584
f_best 939597
f_avg 985082.7
succeed_times 1
t_avg 1478.2
init_cost_time 180.8
func_time 3766.2
iter 99046503

MA_modified_SP0
962774 984733 966273 1006299 961697 976355 961602 987833 991144 991611
SP0 = 85
f_best 961602
f_avg 979032.1
succeed_times 1
t_avg 2730.2
init_cost_time 152.9
func_time 3737.3
iter 37928982

MA_modified_SP0_weight
973101 977709 993228 953430 975270 954026 998845 982875 985245 990812
SP0 = 0
f_best 953430
f_avg 978454.1
succeed_times 1
t_avg 3523.0
init_cost_time 193.0
func_time 3772.8
iter 31154076

powergrid

MA
16071 15999 16072 16048 16059 16067 16050 16071 16051 16018
SP0 = 85
f_best 15999
f_avg 16050.6
succeed_times 1
t_avg 988.2
init_cost_time 82.7
func_time 3661.2
iter 43560215

MA_modified_SP0
15971 15964 15962 15963 15975 15979 15956 15965 15977 15970
SP0 = 0
f_best 15956
f_avg 15968.2
succeed_times 1
t_avg 3259.1
init_cost_time 85.0
func_time 3665.2
iter 44632069

MA_modified_SP0_weight
15985 15949 15962 15938 15943 15933 15982 15929 15946 15949
SP0 = 0
f_best 15929
f_avg 15951.6
succeed_times 1
t_avg 3459.5
init_cost_time 66.1
func_time 3648.4
iter 53554058

Hamilton5000

MA
8454393 8511617 8611049 8441974 8492181 8577711 8451021 8424585 8475915 8630682
SP0 = 85
f_best 8424585
f_avg 8507112.8
succeed_times 1
t_avg 3452.4
init_cost_time 527.7
func_time 4048.4
iter 13283329

MA_modified_SP0
8597868 8602276 8507918 8718366 8638995 8532672 8622902 8589994 8600017 8569039
SP0 = 85
f_best 8507918
f_avg 8598004.7
succeed_times 1
t_avg 3536.2
init_cost_time 526.6
func_time 4048.7
iter 12950153

MA_modified_SP0_weight
8550111 8531751 8539699 8505464 8581063 8553533 8565017 8647540 8532419 8668827
SP0 = 85
f_best 8505464
f_avg 8567542.4
succeed_times 1
t_avg 3544.0
init_cost_time 495.7
func_time 4023.0
iter 13894973

Modified_update

WS500

MA
BenchMarks/cnd/WattsStrogatz_n500.txt
2098 2098 2097 2098 2085 2085 2098 2116 2085 2088
f_best 2085
f_avg 2094.8
succeed_times 3
t_avg 1518.6
init_cost_time 41.4
func_time 3547.4
iter 310654709

MA_SP0
BenchMarks/cnd/WattsStrogatz_n500.txt
2072 2085 2085 2087 2085 2085 2085 2085 2072 2085
f_best 2072
f_avg 2082.6
succeed_times 2
t_avg 873.8
init_cost_time 23.5
func_time 3580.3
iter 183309718

ER2500

MA
BenchMarks/cnd/ErdosRenyi_n2500.txt
972170 945628 964495 938067 958767 938380 982553 972528 981887 965579
f_best 938067
f_avg 962005.4
succeed_times 1
t_avg 3515.3
init_cost_time 163.8
func_time 3740.5
iter 36409946

MA_SP0
BenchMarks/cnd/ErdosRenyi_n2500.txt
983921 966243 976105 1034643 984802 954249 1017295 980751 964533 991790
f_best 954249
f_avg 985433.2
succeed_times 1
t_avg 3452.2
init_cost_time 212.9
func_time 3516.1
iter 26184249

powergrid

MA
BenchMarks/RealInstances/powergrid.txt
16039 16051 15985 15980 15983 16008 15989 16051 16049 15952
f_best 15952
f_avg 16008.7
succeed_times 1
t_avg 1185.3
init_cost_time 69.9
func_time 3637.1
iter 50775042

MA_SP0
BenchMarks/RealInstances/powergrid.txt
15948 15975 15950 15904 15943 15928 15946 15960 15933 15943
f_best 15904
f_avg 15943.0
succeed_times 1
t_avg 2983.9
init_cost_time 78.7
func_time 3649.7
iter 43919136

Hamilton

MA
8614225 8471335 8611867 8573018 8672674 8516540 8660056 8532989 8469067 8678253
SP0 = 85
f_best 8469067
f_avg 8580002.4
succeed_times 1
t_avg 3573.6
init_cost_time 1006.0
func_time 4036.7
iter 12512364

MA_SP0
8627980 8565966 8540259 8797655 8579885 8573333 8594149 8651997 8660058 8560741
SP0 = 85
f_best 8540259
f_avg 8615202.3
succeed_times 1
t_avg 3513.7
init_cost_time 654.1
func_time 4156.1
iter 11571762

叶荣臻的CC

mark_size计算复杂度相当高，可以每次add to solution/remove from solution时更新mark_size
即使使用了启发式更新mark_size的方式，复杂度同样是O(n^2)级别，无法使用
主要原因是为了防止加进去一些不会影响连通度的点，这里可以提前检测，只要检测加进去的这个点不会分裂出来多个（超过2）component，就不要加进去，直接下一轮
conf_times与我的neibor_removed意义接近，都是考察有没有邻居被放回原图

使用提前检测，达到mark_size的效果

初始化时使用前面初始化并提高后的解，概率加入新的解

weight初始化为度，放回原图重置为度，提高度比较高的点被选中的概率

问题出现在选取点的时候，选取了一个点后，加进去，又被放回来，但是如果其他点的度与其相差太大，则会连续选取该点，选取powergrid为对比组测例，因为使用了SP0启发式更新后
2085 2085 2085 2085 2085 2081 2072 2087 2085 2085
SP0 = 0
f_best 2072
f_avg 2083.5
succeed_times 1
t_avg 327.1
init_cost_time 22.9
func_time 3594.0
iter 194379671

15985 15949 15962 15938 15943 15933 15982 15929 15946 15949
SP0 = 0
f_best 15929
f_avg 15951.6
succeed_times 1
t_avg 3459.5
init_cost_time 66.1
func_time 3648.4
iter 53554058

8550111 8531751 8539699 8505464 8581063 8553533 8565017 8647540 8532419 8668827
SP0 = 85
f_best 8505464
f_avg 8567542.4
succeed_times 1
t_avg 3544.0
init_cost_time 495.7
func_time 4023.0
iter 13894973

local search提高

解中每个点将自己放回原图里，然后在它所在的子图里，找到一个更好的点替代自己，迭代会逐渐加快，因为由于解的质量逐步提高，每个点放回原图后，所在的子图的会变小，所以搜索范围变小。搜索范围变小也导致一个问题，无法从全局考虑问题。导致优化有限。

只遍历一次：
2115
2111
2090
2155
2091
2166
2194

到所有的点都无法提高
2167 2108 2111 2162 2152 2105 2148 2095 2203 2175
SP0 = 85
f_best 2095
f_avg 2142.6
succeed_times 1
t_avg 540.7
init_cost_time 410.5
func_time 1001.8
iter 0

SP0启发式更新

还需要powergrid中SP0 = 85，没有修改SP0启发式更新的结果，以证明启发式更新有效

当Si, Sj中相同元素超过RATE K时，只从XA中取RATE K个元素，不从XB中取元素，使得保持一定的探索能力，效果比较好
2085 2087 2133 2085 2072 2145 2085 2072 2087 2085
SP0 = 0
f_best 2072
f_avg 2093.6
succeed_times 2
t_avg 158.0
init_cost_time 30.5
func_time 1070.6
iter 53315184

2087 2085 2072 2085 2087 2081 2085 2085 2072 2085
SP0 = 0
f_best 2072
f_avg 2082.4
succeed_times 2
t_avg 1389.2
init_cost_time 13.8
func_time 3558.4
iter 389873773

powergrid
15971 15964 15962 15963 15975 15979 15956 15965 15977 15970
SP0 = 0
f_best 15956
f_avg 15968.2
succeed_times 1
t_avg 3259.1
init_cost_time 85.0
func_time 3665.2
iter 44632069

Hamilton//大图效果比较差，没有达到原结果，可能是算法效率不够，应该审视如何提高算法效率

8597868 8602276 8507918 8718366 8638995 8532672 8622902 8589994 8600017 8569039
SP0 = 85
f_best 8507918
f_avg 8598004.7
succeed_times 1
t_avg 3536.2
init_cost_time 526.6
func_time 4048.7
iter 12950153

code

//local search时不用每次开始前划分cpn，可以在初始化解之后进行划分，然后产生后代时的本地提高也不需要划分，因为每次加点进解时会更新
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

string filename = “BenchMarks/cnd/WattsStrogatz_n500.txt”;
int K = 125;
double time_out = 3600;//每次运行函数允许使用的最大时间
int run_times = 10;//运行次数
int SP0 = 85;

define rate 0.95
#define maxn 30100
#define BETA 0.6
#define MaxIdleIters 1000//是否太大了
#define parent_num 20

ofstream out;

vector min_cnty;
vector> adjlist;//整个图的邻接矩阵
int vertex_num;//图中顶点总数

int cnty_operating;//当前操作的解的连通度
vector solution_operating;//当前操作的解
vector best_solution_once;//单次最优解
int min_connectivity_once;//单次最优解的连通度
vector best_solution;//所有次数里的最佳解
int f_best;//最优解的连通度
int f_avg;//所有单次最优解的平均连通度
int succeed_times;//达到最优解的次数
int exch;//交换次数

long long weight[maxn];//每个顶点的权重，每次local search时都更新，还是全程只要一次初始化
int vertex_component_id[maxn];//每个顶点所属的子图的id
bool deleted[maxn];//删除的点/在当前操作的解中的顶点

vector components[maxn];//连通子图
vector solutions[parent_num + 10];//解的集合

stack unused_component_id;//未使用的子图id
set used_component_id;//已使用的子图id

double t_avg;//找到最优解所用的平均时间
double init_cost_time;//初始化使用的时间
double func_time;//调用函数解决所用的时间
long long iter;//迭代次数，即交换次数
clock_t start_time;//用于计算时间

vector connectivities(parent_num + 1, 0);//每个解的连通度
int* key_vertexs = new int[maxn];//每个子图中权重最大的顶点
vector tmp_dis(parent_num + 1, 0);
vector total_distances(parent_num + 1, 0);//解与其他解的总距离
vector rank_connectivity(parent_num + 1, 0);//解的连通度排名

vector visited_vertex;//分割出新的component时记录其中的顶点

inline double time_cost() {
return (double)(clock() - start_time) / CLOCKS_PER_SEC;
}

inline bool timeout() {
return time_cost() > time_out;
}

void read_graph(string filename) {
ifstream in;
in.open(filename);
string line;
getline(in, line);
istringstream iss(line);
iss >> vertex_num;
adjlist.resize(vertex_num);
int tmp;
char c;
for (int i = 0; i < vertex_num; ++i) {
getline(in, line);
istringstream iss(line);
iss >> tmp >> c;
while(iss >> tmp) adjlist[i].push_back(tmp);
}
}

int deth_first_search_split(int start, vector& visited, bool add_weight) {//component信息记录
int cpn_id = unused_component_id.top();//新component用的id
visited_vertex.clear();//新component包含的顶点
stack to_visit;
to_visit.push(start);
visited[start] = true;
int key_vertex = start;//权重最大的顶点
int vertex;
while(!to_visit.empty()) {//深度优先遍历，注意每个点在加入stack时就要把visited置为true
vertex = to_visit.top();
to_visit.pop();
visited_vertex.push_back(vertex);
vertex_component_id[vertex] = cpn_id;//每个顶点所属的component的id
if(add_weight) weight[vertex]++;//如果是添加顶点到solution里，则剩余的点的权重要++
if (weight[vertex] > weight[key_vertex]//权重较大或权重相等但是度比较大
|| (weight[vertex] == weight[key_vertex] && adjlist[vertex].size() > adjlist[key_vertex].size()))
key_vertex = vertex;
for(auto &neibor:adjlist[vertex])
if(!deleted[neibor] && !visited[neibor]){
visited[neibor] = true;
to_visit.push(neibor);
}
}
components[cpn_id] = visited_vertex;
unused_component_id.pop();
used_component_id.insert(cpn_id);
key_vertexs[cpn_id] = key_vertex;
return visited_vertex.size();
}

void seperate_graph() {//只要连通度而不用继续提高的话，可以调用get_cnty
while (!unused_component_id.empty()) unused_component_id.pop();//初始化，后面只要将使用的重新push就好
for (int i = 0; i < vertex_num; ++i) unused_component_id.push(i);
used_component_id.clear();
vector visited(vertex_num, false);
cnty_operating = 0;
for (int i=0; i if (!deleted[i] && !visited[i]) {
int size = deth_first_search_split(i, visited, false);
cnty_operating += (size - 1) * size / 2;
}
}

int select_large_component() {//每次都要遍历used_cpn_id来找到最大最小cpn_size，因为每次加点进solution，可能分割了最大的cpn，
int max_component_size = 0;//如果想要不用每次遍历used_cpn_id来找到最大，最小的size，要用set，而且要更改set的排列函数（比较大小的函数）
int min_component_size = vertex_num;//实测使用了set但是实际上并没有维持有序的大小，是因为cpn_size修改时没有相对应更新该set？另起数组记录cpn_size
for (auto it = used_component_id.begin(); it != used_component_id.end(); ++it) {//可以每次都遍历，因为只需要O(n)的复杂度
int cpn_size = components[*it].size();
if(cpn_size > max_component_size) max_component_size = cpn_size;
if(cpn_size < min_component_size) min_component_size = cpn_size;
}
int mean_cpn_size = (max_component_size + min_component_size) / 2;
vector large_component_id;
for(auto &id:used_component_id)
if (components[id].size() >= mean_cpn_size)
large_component_id.push_back(id);
return large_component_id[rand() % large_component_id.size()];
}

void add_to_solution(int add_vertex) {//add vertex to solution_operating
deleted[add_vertex] = true;
int cpn_size = 1;
int sub_cpn_size;
vector visited(vertex_num, false);
for (auto &num:adjlist[add_vertex])
if (!deleted[num] && !visited[num]) {
sub_cpn_size = deth_first_search_split(num, visited, true);//重新分割原来的component
cnty_operating += sub_cpn_size (sub_cpn_size - 1) / 2;
cpn_size += sub_cpn_size;
}
cnty_operating -= (cpn_size - 1) cpn_size / 2;
int cpn_id = vertex_component_id[add_vertex];
components[cpn_id].clear();
unused_component_id.push(cpn_id);
used_component_id.erase(cpn_id);
}

int remove_from_solution() {//remove the optimal node from solution
int min_increase = vertex_num vertex_num;
int remove_vertex = -1;
int idx = -1;
for (int i = 0; i < solution_operating.size(); ++i) {//遍历解内所有成员，找放回后使连通度上升最少的
int cnty_increase = 0;
int cpn_id;
int size;
int cpn_size = 1;
vector visited(vertex_num, false);
for (auto &adj:adjlist[solution_operating[i]])
if (!deleted[adj] && !visited[cpn_id = vertex_component_id[adj]]) {
visited[cpn_id] = true;
cpn_size += (size = components[cpn_id].size());
cnty_increase -= size (size - 1) / 2;
}
cnty_increase += cpn_size * (cpn_size - 1) / 2;
if (cnty_increase <= min_increase) {
min_increase = cnty_increase;
idx = i;
}
}
cnty_operating += min_increase;
remove_vertex = solution_operating[idx];
solution_operating.erase(solution_operating.begin() + idx);
deleted[remove_vertex] = false;
weight[remove_vertex] = adjlist[remove_vertex].size();
int cpn_id;
vector visited(vertex_num, false);
for (auto &neibor:adjlist[remove_vertex])//更新component的id使用情况
if (!deleted[neibor] && !visited[cpn_id = vertex_component_id[neibor]]) {
visited[cpn_id] = true;
components[cpn_id].clear();
unused_component_id.push(cpn_id);
used_component_id.erase(cpn_id);
}
vector tmp_visited(vertex_num, false);
deth_first_search_split(remove_vertex, tmp_visited, false);//更新component
return remove_vertex;
}

int deth_first_search(int start, vector& visited) {
stack s;
s.push(start);
visited[start] = true;
int size = 0;
while(!s.empty()) {
int vertex = s.top();
s.pop();
size++;
for(int i = 0; i < adjlist[vertex].size(); ++i) {
int neibor = adjlist[vertex][i];
if(!deleted[neibor] && !visited[neibor]) {
s.push(neibor);
visited[neibor] = true;
}
}
}
return size;
}

int get_connectivity() {//只需要得到连通度，不需要将原图分割、记录子图信息时，使用该函数
int connectivity = 0;
vector visited(vertex_num, false);
for(int i = 0; i < vertex_num; ++i) {
if(!deleted[i] && !visited[i]) {
int size = deth_first_search(i, visited);
connectivity += size * (size - 1) / 2;
}
}
return connectivity;
}

void component_based_neghborhood_search() {
clock_t func_start_time = clock();
//fill(weight, weight + vertex_num, 0);
for(int i = 0; i < vertex_num; ++i) weight[i] = adjlist[i].size();
vector local_best_solution = solution_operating;
int local_min_connectivity = cnty_operating;
int idle_iter = 0;
int add_vertex, remove_vertex;
while (idle_iter < MaxIdleIters) {//无论新得到的解是否比原来的好，这里都直接更新了
add_vertex = key_vertexs[select_large_component()];
solution_operating.push_back(add_vertex);//增加顶点
add_to_solution(add_vertex);
remove_vertex = remove_from_solution();
++iter;
if (cnty_operating < local_min_connectivity) {//增量式更新连通度使用的地方
local_min_connectivity = cnty_operating;
local_best_solution = solution_operating;
idle_iter = 0;
}
else idle_iter++;
}
for (auto &v:solution_operating) deleted[v] = false;
solution_operating = local_best_solution;
for (auto &v:solution_operating) deleted[v] = true;
seperate_graph();
func_time += (double)(clock() - func_start_time) / CLOCKS_PER_SEC;
}

bool cnty_compare(int i, int j) {return connectivities[i] < connectivities[j];}

void population_initialization() {//初始化的连通度相差较大，可以尝试加大人口，或者加大local search迭代次数，提高初始化连通度
for (int i = 0; i < parent_num; ++i) {
fill(deleted, deleted + vertex_num, false);
//fill(conf_changed, conf_changed + vertex_num, false);
solution_operating.resize(K);
for (int j = 0; j < K; ++j) {
solution_operating[j] = rand() % vertex_num;
while (deleted[solution_operating[j]]) solution_operating[j] = rand() % vertex_num;
deleted[solution_operating[j]] = true;
}//为什么每次初始化得到的解的连通度都一样，而且每次都只剩下一个cpn？运行时间间隔太小导致srand()函数没有发挥作用，而导致得到的解都一样
seperate_graph();
component_based_neghborhood_search();//还是图的关系，初始化得到的解都一样差？
while (true) {
bool differ = true;
vector visited(vertex_num, false);//需要先把在solution_operating中的点置为visited
for(auto &v : solution_operating) visited[v] = true;
for (int j = 0; j < i; ++j) {
int dis = 0;
for(auto &v : solutions[j]) dis += visited[v];
dis = K - dis;
if (dis == 0) {//可以设为小于某个阈值，则进行交换操作？
differ = false;
break;
}
}
if (differ) break;
int idx = rand() % K;
int add_vertex = rand() % vertex_num;
while(deleted[add_vertex]) add_vertex = rand() % vertex_num;
deleted[solution_operating[idx]] = false;
deleted[add_vertex] = true;
solution_operating[idx] = add_vertex;
}
solutions[i] = solution_operating;
int cnty = (connectivities[i] = get_connectivity());
cout << i << “ initialization connectivity : “ << cnty << endl;
if(cnty < min_connectivity_once) {//记录单次最优解
min_connectivity_once = cnty;
best_solution_once = solution_operating;
}
for(int j = 0; j < i; ++j) {//初始化距离矩阵与总距离
int common = 0;
for(int m = 0; m < K; ++m) common += deleted[solutions[j][m]];
int dis = K - common;
total_distances[j] += dis;
total_distances[i] += dis;
}
}
}

void double_backbone_based_crossover(vector &S1, vector &S2) {
vector XB;
vector XA;
fill(deleted, deleted + vertex_num, false);//重置del数组，表示所有点都未放进S
//fill(conf_changed, conf_changed + vertex_num, false);
solution_operating.clear();
vector visited(vertex_num, false);
for (auto &v:S1) visited[v] = true;
for (auto &v:S2)
if (visited[v]) {
//solution_operating.push_back(v);//在s1也在s2的点
XA.push_back(v);
//deleted[v] = true;
visited[v] = false;
}
else XB.push_back(v);//在s2但是不在s1里的点

//更新SP0
SP0 = 85;
if(XA.size() <= rate K) {
for(auto &v : XA) {
solution_operating.push_back(v);
deleted[v] = true;
}
}
else {
SP0 = 0;
for(auto &v : XA)
if(rand() % XA.size() <= rate K) {
solution_operating.push_back(v);
deleted[v] = true;
}
}

for (auto &v:S1)<br />        if (visited[v]) XB.push_back(v);//在s1但是不在s2里的点<br />    for (auto &v : XB)<br />        if (rand() % 100 < SP0) {<br />            solution_operating.push_back(v);<br />            deleted[v] = true;<br />        }<br />    if(solution_operating.size() == K) return;<br />    seperate_graph();//划分cpn<br />    for (auto &v:S1) visited[v] = true;<br />    for (auto &v:S2) visited[v] = true;//记录XC<br />    while (solution_operating.size() < K) {//不够K的话要加顶点到后代<br />        int large_idx = select_large_component();<br />        vector<int>& large_cpn = components[large_idx];<br />        int idx = rand() % large_cpn.size();<br />        int add_vertex = large_cpn[idx];<br />        if (!visited[add_vertex] && !deleted[add_vertex]) {<br />            solution_operating.push_back(add_vertex);<br />            add_to_solution(add_vertex);<br />        }<br />    }<br />    while (solution_operating.size() > K) remove_from_solution();<br />}

bool distance_compare(int i, int j) {return total_distances[i] > total_distances[j];}

void rank_based_pool_updating(int connectivity) {//尝试不要直接加进去再算要不要加，而是根据原本的解，构建一个阈值，不用每次计算这么多
if(connectivity < 2072) {
for(auto &v : solution_operating) out << v << “ “;
out << endl;
}
solutions[parent_num] = solution_operating;
connectivities[parent_num] = connectivity;
vector index(parent_num + 1, -1);
for(int i = 0; i < parent_num + 1; ++i) index[i] = i;
stable_sort(index.begin(), index.end(), cnty_compare);
for(int i = 0; i < parent_num + 1; ++i) rank_connectivity[index[i]] = i;
for(int i = 0; i < parent_num; ++i) {//求总距离
int dis = 0;
for(int j = 0; j < K; ++j) dis += deleted[solutions[i][j]];
dis = K - dis;
total_distances[parent_num] += dis;
total_distances[i] += dis;
}
stable_sort(index.begin(), index.end(), distance_compare);
vector rank_distance(parent_num + 1, -1);
for(int i = 0; i < parent_num + 1; ++i) rank_distance[index[i]] = i;
int idx = -1;
double max_score = -1;
for(int i = 0; i < parent_num + 1; ++i) {//找出加权排名最低的解
double score = BETA rank_connectivity[i] + (1 - BETA) rank_distance[i];//求加权排名
if(score > max_score) {
idx = i;
max_score = score;
}
}
if(idx == parent_num) return;
for(int i = 0; i < parent_num + 1; ++i) {
int dis = 0;
for(auto &v : solutions[i]) dis += deleted[v];
dis = K - dis;
total_distances[i] -= dis;
}
total_distances[idx] = total_distances[parent_num];//total_distances需要更新
total_distances[parent_num] = 0;
swap(solutions[idx], solutions[parent_num]);
int delete_connectivtiy = connectivities[idx];
connectivities[idx] = connectivities[parent_num];//交换connectivity，交换rank
rank_connectivity[idx] = rank_connectivity[parent_num];
for(int i = 0; i < parent_num + 1; ++i) //因为删去了一个解，排名会发生变化
if(connectivities[i] >= delete_connectivtiy) rank_connectivity[i]—;
}

void Critical_Node_Problem() {
srand(time(0));
min_connectivity_once = vertex_num * vertex_num;//该次最小的连通度
best_solution_once.clear();
start_time = clock();
population_initialization();//初始化所有解
init_cost_time += time_cost();
start_time = clock();
double cost_time;
while (!timeout()) {
int Si = rand() % parent_num;
int Sj = rand() % parent_num;
while (Si == Sj) Si = rand() % parent_num, Sj = rand() % parent_num;
double_backbone_based_crossover(solutions[Si], solutions[Sj]);
component_based_neghborhood_search();
if (cnty_operating < min_connectivity_once) {
best_solution_once = solution_operating;
min_connectivity_once = cnty_operating;
cost_time = time_cost();
out << “time cost to get this : “ << cost_time << endl;
}
cout << “min connectivity once : “ << min_connectivity_once << “ / “ << cnty_operating << endl;
cout << “best ever : “ << f_best << endl;
rank_based_pool_updating(cnty_operating);
}
if (min_connectivity_once < f_best) {//更新所有次数最优解
best_solution = best_solution_once;
f_best = min_connectivity_once;
t_avg = cost_time;
succeed_times = 1;
}
else if (min_connectivity_once == f_best) {
t_avg += cost_time;
succeed_times++;
}
min_cnty.push_back(min_connectivity_once);
f_avg += min_connectivity_once;
out << min_connectivity_once << endl;
}

int main() {
read_graph(filename);
f_best = vertex_num * vertex_num;
f_avg = 0;
succeed_times = 0;
t_avg = 0;
init_cost_time = 0;
func_time = 0;
iter = 0;
string results_filename = “results.txt”;
out.open(results_filename);

for (int i = 0; i < run_times; ++i) Critical_Node_Problem();

for (int i = 0; i < run_times; ++i) out << min_cnty[i] << " ";<br />    out << endl;<br />    out << filename << endl;<br />    out << fixed;<br />out << "f_best " << f_best << endl;<br />out << "f_avg " << setprecision(1) << double(f_avg)/run_times << endl;<br />out << "succeed_times " << succeed_times << endl; <br />out << "t_avg " << setprecision(1) << t_avg / succeed_times << endl;<br />out << "init_cost_time " << setprecision(1) << init_cost_time / run_times << endl;<br />out << "func_time " << setprecision(1) << func_time / run_times << endl;<br />out << "iter " << iter << endl;
for (int i = 0; i < run_times; ++i) cout << min_cnty[i] << " ";<br />    cout << endl;<br />cout << fixed;<br />    cout << "SP0 = " << SP0 << endl;<br />cout << "f_best " << f_best << endl;<br />cout << "f_avg " << setprecision(1) << double(f_avg)/run_times << endl;<br />cout << "succeed_times " << succeed_times << endl; <br />cout << "t_avg " << setprecision(1) << t_avg / succeed_times << endl;<br />cout << "init_cost_time " << setprecision(1) << init_cost_time / run_times << endl;<br />cout << "func_time " << setprecision(1) << func_time / run_times << endl;<br />cout << "iter " << iter << endl;<br />    system("pause");<br />return 0;<br />}

1.Done

1. 了解问题背景，阅读理解 MACNP 等论文。
2. 完成开题报告。
3. 完成了 Random Walk 论文的复现工作，并把其结果应用到 CNP 的 bench mark 当中

发现效果并不理想，Random Walk 估计连通度方向暂时存档中。

1. 尝试手写代码复现 MACNP 的结果，目前结果已经在接近论文的结果。更多相关数据仍在进一步调试当中。
2. 了解 SMAC 调参工具，在 Ubuntu 虚拟机上成功安装稳定版本，并成功运行官方测例与自己手写的简单测例。
3. 对 Multi Agent Reinforcement Learning 做了简单的 survey。

2.To Do

1. 2.20 号之前尽量完成 MACNP 的论文复现
2. 2.20 号之后全身心投入到 MACNP+IEM 和 MACNP+CC 与 MACNP 的比较当中
3. 3.20 之前完成论文初稿

修改rank_based_pool_updating函数，关于总距离更新，测试距离计算是否正确，所有解是否最终趋于相同，为什么新得到的解与其他解之间的总距离总是从小到大，从小到大

macnp在所有解变相同后，无法再次被提高，主要问题是当前解通过交换点已经无法再次提高，必须将多个点换出来，将多个点换出去才可能提高，因为后面的local search其实是会遍历所有的点都加进去试的，但是仍然无法获得提高

找出优良基因，比如每次提高后，哪些点被移除，哪些点被加入

复现

1. solutions 中所有解，随着迭代次数的增加，会越来越趋向相同，最终达到所有解完全相同，如何在这种情况发生前，保证能最大限度地保证解的丰富度，保证所有点（有可能的点）都有被访问到？
2. 结合 restart 的的可能性
3. ws500 有在 57s 达到最优解的情况
4. //经常重复分配 visited 数组比较需要比较多时间还是维护 visited 数组需要比较多时间
5. 修改了 compare 函数，可以将 id 按所指向的 component 的大小从大到小排序，为什么修改了 id 的排序方式，会影响初始化的解的质量
6. local search时不以cnty为唯一标准？
7. select_large_component

//每次都要遍历 used_cpn_id 来找到最大最小 cpn_size，因为每次加点进 solution，可能分割了最大的 cpn
//如果想要不用每次遍历 used_cpn_id 来找到最大，最小的 size，要用 set，而且要更改 set 的排列函数（比较大小的函数）
//实测使用了 set 但是实际上并没有维持有序的大小，是因为 cpn_size 修改时没有相对应更新该 set？另起数组记录 cpn_size
//可以每次都遍历，因为只需要 O(n)的复杂度，而且 used_cpn_id 比较小，每次遍历两次，与遍历 0.5 次，差距应该不大

1. 收敛到同一个解之后，所有的大子图large component中的所有点都会被尝试添加到solution_operating中，但是都无法提高。应该不是说把large component中的点放宽到图中所有顶点就能解决问题。
2. cycling问题究竟存不存在——存在

参数调整

由于收敛到一样的解的速度过快，而且收敛到一样的解之后，无法再通过遗传算法提高，所以把SP0参数从0.85改为0.5，收敛速度变慢，解的质量变高

2085 2072 2072 2076 2087 2072 2088 2078 2087 2088
SP0 = 20
f_best 2072
f_avg 2080.5
succeed_times 3
t_avg 893.2
init_cost_time 17.8
func_time 3586.5
iter 239887858
超越了MA的平均值

WS500
SP0 = 0.5
2106
2099
2081
2087
2089
2092
2098
2099
2114
2082

SP0 = 0.3
2098 2096 2098 2087 2087 2124 2113 2078 2093 2082
f_best 2078
f_avg 2095.6
succeed_times 1
t_avg 230.9
init_cost_time 17.6
func_time 1204.1
iter 82298451

2078 2087 2093 2072 2072 2089 2087 2089 2082
SP0 = 30
f_best 2072
f_avg 2083.2
succeed_times 2
t_avg 400.5
init_cost_time 19.0
func_time 3590.0
iter 232633012

2072 2089 2106 2103 2089 2100 2088 2112 2088 2098
SP0 = 40
f_best 2072
f_avg 2094.5
succeed_times 1
t_avg 132.2
init_cost_time 20.9
func_time 318.9
iter 18035580

2093 2108 2100 2087 2082 2088 2119 2081 2095 2087
SP0 = 40
f_best 2081
f_avg 2094.0
succeed_times 1
t_avg 82.1
init_cost_time 14.8
func_time 604.2
iter 62236399

2082 2093 2089 2076 2089 2105 2087 2106 2098 2085
SP0 = 50
f_best 2076
f_avg 2091.0
succeed_times 1
t_avg 72.8
init_cost_time 18.4
func_time 613.7
iter 40760792

2085 2100 2085 2124 2091 2087 2088 2106 2085 2085
SP0 = 50
f_best 2085
f_avg 2093.6
succeed_times 4
t_avg 239.3
init_cost_time 22.6
func_time 617.7
iter 34139534

2097 2102 2089 2092 2089 2085 2072 2082 2089 2124
SP0 = 50
f_best 2072
f_avg 2092.1
succeed_times 1
t_avg 161.4
init_cost_time 24.8
func_time 616.1
iter 52771769

2119 2087 2102 2072 2098 2097 2100 2072 2091 2091
BenchMarks/cnd/WattsStrogatz_n500.txt
SP0 = 50
125 2078
f_best 2072
f_avg 2092.9
succeed_times 2
t_avg 143.7
init_cost_time 16.5
func_time 608.3
iter 56323492

2087 2085 2113 2099 2098 2098 2087 2098 2085 2072
SP0 = 50
f_best 2072
f_avg 2092.2
succeed_times 1
t_avg 173.1
init_cost_time 18.3
func_time 613.1
iter 40078887

2098 2091 2093 2099 2087 2100 2098 2088 2088 2109
f_best 2087
f_avg 2095.1
succeed_times 1
t_avg 70.6
init_cost_time 16.0
func_time 608.1
iter 57285422

powergrid
SP0 = 40
15988
15994
15982
16006
16005
15993
15989
16053
15990
16015
15988 15994 15982 16006 16005 15993 15989 16053 15990 16015
BenchMarks/RealInstances/powergrid.txt
f_best 15982
f_avg 16001.5
succeed_times 1
t_avg 689.2
init_cost_time 65.6
func_time 763.1
iter 11111222

SP0 = 20
15993
15977
16003
15999
15993
16007
15972
16006
15986
16014
15993 15977 16003 15999 15993 16007 15972 16006 15986 16014
BenchMarks/RealInstances/powergrid.txt
f_best 15972
f_avg 15995.0
succeed_times 1
t_avg 756.7
init_cost_time 63.5
func_time 1139.6
iter 16558679

SP0 = 10
16091
16046
16023
16063
16054
16059
16023
16048
16020
16077
16091 16046 16023 16063 16054 16059 16023 16048 16020 16077
BenchMarks/RealInstances/powergrid.txt
f_best 16020
f_avg 16050.4
succeed_times 1
t_avg 1161.7
init_cost_time 63.8
func_time 3653.2
iter 54585782

15995 16042 16005 15987 15965 16017 16052 16007 15984 16045
SP0 = 20
f_best 15965
f_avg 16009.9
succeed_times 1
t_avg 946.1
init_cost_time 63.4
func_time 1139.6
iter 18085464

Icremental Evaluation Mechanism

使用 IEM 与不使用的迭代次数差距巨大，效率提高了一倍
f_best 2118
f_avg 2118.0
succeed_times 1
t_avg 83.9
init_cost_time 17.5
func_time 298.7
iter 1933466

f_best 2129
f_avg 2129.0
succeed_times 1
t_avg 39.8
init_cost_time 19.0
func_time 314.9
iter 2056653

f_best 2098
f_avg 2098.0
succeed_times 1
t_avg 169.7
init_cost_time 25.2
func_time 322.8
iter 801823

f_best 2102
f_avg 2102.0
succeed_times 1
t_avg 134.8
init_cost_time 28.5
func_time 325.9
iter 908613

ER2500测试

最优值为939597，已经超过该macnp出现之前的最优值959500，但macnp的最优值为902498，平均值为922339.5，差距仍有，但是正在接近
980392，981543
984477
1000657
987069
1017198
990911
939597
1012281
977125
972153
965371
981783
964957
950740
999123
992074
977793
974920
1012557
984539
1019918
980747
978320
1002024
976516
994421
990079
994613
968584
980392, 981543, 984477, 1000657, 987069, 1017198, 990911, 939597, 1012281, 977125, 972153, 965371, 981783, 964957, 950740, 999123, 992074, 977793, 974920, 1012557, 984539, 1019918, 980747, 978320, 1002024, 976516, 994421, 990079, 994613, 968584
f_best 939597
f_avg 985082.7
succeed_times 1
t_avg 1478.2
init_cost_time 180.8
func_time 3766.2
iter 99046503

yrz:
986465, 983820, 964073, 973413, 1003598, 990930, 978801, 966987, 1009521, 984036, 979840, 958065, 967903, 1009986, 949501, 969041, 983721, 957687, 1000871, 964434, 961219, 1000144, 987757, 1018151, 1045421, 995995, 982681, 996914, 972658, 941724
f_best 941724
f_avg 982845.2
succ 1
t_avg 1023.5
init_cost_time 154.6
func_time 3735.0
iter 143021771

重读论文

1.population initialization
1.生成随机的解
2.component-based neiborhood search 提高
3.如果与其他解都不同，加入 population；否则进行 exchange 操作，直到与与其他解都不同
未说明 exchange 操作是如何进行的，都是随机？

2.component-based neiborhood search
1.add to solution：把权重最大的点 v 加入结集，复杂度为 O(T + nbr v)，T 为大子图的数量，nbr v 为 v 的邻居的数量
需要分割为新的子图，维护 components 相关信息，这里的复杂度不止 nbr v 吧？
2.remove from solution：把导致连通度上升最少的点 u 从解中删除/放回原图，复杂度为 O(K * nbr u)，K 为解的大小，nbr u 为 u 的邻居的数量
同上
3.node weighting scheme：
1.初始化为 0
何时初始化
2.选择权重最大的点加入解，该 cpn 剩下的点的权重都+1
3.被从解中放回原图的点的权重重置为 0

3.double backbone-based crossover
1.两个解的交集直接加入后代
2.两个解特有的顶点按概率加入后代—sp
3.如果|S| > K，add to solution，从任一大子图里随机选择属于 XC 的顶点加入解；如果|S| < K，贪婪地 remove from solution
如何贪婪地 remove from solution
sp 可以设置为|XA|，|XB|，K 的函数或者为常数，可以影响后代的多样性

4.rank-based pool updating
1.先把新来的解加入人口
2.按照目标函数的值从小到大排序，与其他解的距离从大到小排序
3.计算得分 score，目标函数的排名β+平均距离的排名(1 - β）
4.删除得分最高的解（如果就是新加入的则无需操作）
文章未说 BETA 的取值，引用的文章只是说根据经验设置为 0.6

3.例会

1. 2019.11.18——确定研究问题，大致方向是使用Random Walk估计连通子图的连通度，适用于规模较大的图（目前测例皆侧重于规模较小的图）。指导下一步工作是熟悉当前最前沿的结果VPMS-MACNP。
2. 2019.11.25——讨论Random Walk论文复现过程中遇到的问题。
3. 2019.11.28——新任务：survey Multi Agent Reinforcement Learning。
4. 2019.12.09——总结Random Walk论文复现结果，讨论将其用于CNP的bench mark的效果及可能性。
5. 2019.12.19——确定MACNP复现和MACNP+CC为下一步优先方向。
6. 2020.02.20——交流应该使用什么样的CC策略。
7. 2020.02.26——交流使用CC后的效果与其他调整MA算法的方向。

newest edition code
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

int K;
double time_out = 3600;//每次运行函数允许使用的最大时间
int run_times = 10;//运行次数

define SP0 85
#define maxn 30100
#define BETA 0.6
#define MaxIdleIters 1000//是否太大了
#define parent_num 20

ofstream out;

vector min_cnty;
vector> adjlist;//整个图的邻接矩阵
int vertex_num;//图中顶点总数

int cnty_operating;//当前操作的解的连通度
vector solution_operating;//当前操作的解
vector best_solution_once;//单次最优解
int min_connectivity_once;//单次最优解的连通度
vector best_solution;//所有次数里的最佳解
int f_best;//最优解的连通度
int f_avg;//所有单次最优解的平均连通度
int succeed_times;//达到最优解的次数
int exch;//交换次数

long long weight[maxn];//每个顶点的权重，每次local search时都更新，还是全程只要一次初始化
int vertex_component_id[maxn];//每个顶点所属的子图的id
bool deleted[maxn];//删除的点/在当前操作的解中的顶点

vector components[maxn];//连通子图
vector solutions[parent_num + 10];//解的集合

stack unused_component_id;//未使用的子图id
set used_component_id;//已使用的子图id

double t_avg;//找到最优解所用的平均时间
double init_cost_time;//初始化使用的时间
double func_time;//调用函数解决所用的时间
long long iter;//迭代次数，即交换次数
clock_t start_time;//用于计算时间

vector connectivities(parent_num + 1, 0);//每个解的连通度
int* key_vertexs = new int[maxn];//每个子图中权重最大的顶点
vector tmp_dis(parent_num + 1, 0);
vector total_distances(parent_num + 1, 0);//解与其他解的总距离
vector rank_connectivity(parent_num + 1);//解的连通度排名
vector rank_distance(parent_num + 1);//解的总距离排名

vector visited_vertex;//分割出新的component时记录其中的顶点

inline double time_cost() {
return (double)(clock() - start_time) / CLOCKS_PER_SEC;
}

inline bool timeout() {
return time_cost() > time_out;
}

void read_graph(string filename) {
ifstream in;
in.open(filename);
string line;
getline(in, line);
istringstream iss(line);
iss >> vertex_num;
adjlist.clear();
adjlist.resize(vertex_num);
int tmp;
char c;
for (int i = 0; i < vertex_num; ++i) {
getline(in, line);
istringstream iss(line);
iss >> tmp >> c;
while(iss >> tmp) adjlist[i].push_back(tmp);
}
}

int deth_first_search_split(int start, vector& visited, bool add_weight) {//component信息记录
int cpn_id = unused_component_id.top();//新component用的id
visited_vertex.clear();//新component包含的顶点
stack to_visit;
to_visit.push(start);
visited[start] = true;
int key_vertex = start;//权重最大的顶点
int vertex;
while(!to_visit.empty()) {//深度优先遍历，注意每个点在加入stack时就要把visited置为true
vertex = to_visit.top();
to_visit.pop();
visited_vertex.push_back(vertex);
vertex_component_id[vertex] = cpn_id;//每个顶点所属的component的id
if(add_weight) weight[vertex]++;//如果是添加顶点到solution里，则剩余的点的权重要++
if (weight[vertex] > weight[key_vertex]//权重较大或权重相等但是度比较大
|| (weight[vertex] == weight[key_vertex] && adjlist[vertex].size() > adjlist[key_vertex].size()))
key_vertex = vertex;
for(auto &neibor:adjlist[vertex])
if(!deleted[neibor] && !visited[neibor]){
visited[neibor] = true;
to_visit.push(neibor);
}
}
components[cpn_id] = visited_vertex;
unused_component_id.pop();
used_component_id.insert(cpn_id);
key_vertexs[cpn_id] = key_vertex;
return visited_vertex.size();
}

void seperate_graph() {//只要连通度而不用继续提高的话，可以调用get_cnty
while (!unused_component_id.empty()) unused_component_id.pop();//初始化，后面只要将使用的重新push就好
for (int i = 0; i < vertex_num; ++i) unused_component_id.push(i);
used_component_id.clear();
vector visited(vertex_num, false);
cnty_operating = 0;
for (int i=0; i if (!deleted[i] && !visited[i]) {
int size = deth_first_search_split(i, visited, false);
cnty_operating += (size - 1) * size / 2;
}
}

int select_large_component() {//每次都要遍历used_cpn_id来找到最大最小cpn_size，因为每次加点进solution，可能分割了最大的cpn，
int max_component_size = 0;//如果想要不用每次遍历used_cpn_id来找到最大，最小的size，要用set，而且要更改set的排列函数（比较大小的函数）
int min_component_size = vertex_num;//实测使用了set但是实际上并没有维持有序的大小，是因为cpn_size修改时没有相对应更新该set？另起数组记录cpn_size
for (auto it = used_component_id.begin(); it != used_component_id.end(); ++it) {//可以每次都遍历，因为只需要O(n)的复杂度
int cpn_size = components[*it].size();
if(cpn_size > max_component_size) max_component_size = cpn_size;
if(cpn_size < min_component_size) min_component_size = cpn_size;
}
int mean_cpn_size = (max_component_size + min_component_size) / 2;
vector large_component_id;
for(auto &id:used_component_id)
if (components[id].size() >= mean_cpn_size)
large_component_id.push_back(id);
return large_component_id[rand() % large_component_id.size()];
}

void add_to_solution(int add_vertex) {//add vertex to solution_operating
deleted[add_vertex] = true;
int cpn_size = 1;
int sub_cpn_size;
vector visited(vertex_num, false);
for (auto &num:adjlist[add_vertex])
if (!deleted[num] && !visited[num]) {
sub_cpn_size = deth_first_search_split(num, visited, true);//重新分割原来的component
cnty_operating += sub_cpn_size (sub_cpn_size - 1) / 2;
cpn_size += sub_cpn_size;
}
cnty_operating -= (cpn_size - 1) cpn_size / 2;
int cpn_id = vertex_component_id[add_vertex];
components[cpn_id].clear();
unused_component_id.push(cpn_id);
used_component_id.erase(cpn_id);
}

int remove_from_solution() {//remove the optimal node from solution
int min_increase = vertex_num vertex_num;
int remove_vertex = -1;
int idx = -1;
for (int i = 0; i < solution_operating.size(); ++i) {//遍历解内所有成员，找放回后使连通度上升最少的
int cnty_increase = 0;
int cpn_id;
int size;
int cpn_size = 1;
vector visited(vertex_num, false);
for (auto &adj:adjlist[solution_operating[i]])
if (!deleted[adj] && !visited[cpn_id = vertex_component_id[adj]]) {
visited[cpn_id] = true;
cpn_size += (size = components[cpn_id].size());
cnty_increase -= size (size - 1) / 2;
}
cnty_increase += cpn_size * (cpn_size - 1) / 2;
if (cnty_increase <= min_increase) {
min_increase = cnty_increase;
idx = i;
}
}
cnty_operating += min_increase;
remove_vertex = solution_operating[idx];
solution_operating.erase(solution_operating.begin() + idx);
deleted[remove_vertex] = false;
weight[remove_vertex] = 0;
int cpn_id;
vector visited(vertex_num, false);
for (auto &neibor:adjlist[remove_vertex])//更新component的id使用情况
if (!deleted[neibor] && !visited[cpn_id = vertex_component_id[neibor]]) {
visited[cpn_id] = true;
components[cpn_id].clear();
unused_component_id.push(cpn_id);
used_component_id.erase(cpn_id);
}
vector tmp_visited(vertex_num, false);
deth_first_search_split(remove_vertex, tmp_visited, false);//更新component
return remove_vertex;
}

int deth_first_search(int start, vector& visited) {
stack s;
s.push(start);
visited[start] = true;
int size = 0;
while(!s.empty()) {
int vertex = s.top();
s.pop();
size++;
for(int i = 0; i < adjlist[vertex].size(); ++i) {
int neibor = adjlist[vertex][i];
if(!deleted[neibor] && !visited[neibor]) {
s.push(neibor);
visited[neibor] = true;
}
}
}
return size;
}

//只需要得到连通度，不需要将原图分割、记录子图信息时，使用该函数
int get_connectivity() {
int connectivity = 0;
vector visited(vertex_num, false);
for(int i = 0; i < vertex_num; ++i) {
if(!deleted[i] && !visited[i]) {
int size = deth_first_search(i, visited);
connectivity += size * (size - 1) / 2;
}
}
return connectivity;
}

void component_based_neghborhood_search() {
clock_t func_start_time = clock();
fill(weight, weight + vertex_num, 0);
/
for(int i = 0; i < vertex_num; ++i) {
weight[i] = adjlist[i].size();
}/
vector local_best_solution = solution_operating;
seperate_graph();
int local_min_connectivity = cnty_operating;
int idle_iter = 0;
int add_vertex, remove_vertex;
while (idle_iter < MaxIdleIters) {//无论新得到的解是否比原来的好，这里都直接更新了
add_vertex = key_vertexs[select_large_component()];
solution_operating.push_back(add_vertex);//增加顶点
add_to_solution(add_vertex);
remove_vertex = remove_from_solution();
++iter;
if (cnty_operating < local_min_connectivity) {//增量式更新连通度使用的地方
local_min_connectivity = cnty_operating;
local_best_solution = solution_operating;
idle_iter = 0;
}
else idle_iter++;
}
for (auto &v:solution_operating) deleted[v] = false;
solution_operating = local_best_solution;
for (auto &v:solution_operating) deleted[v] = true;
seperate_graph();
func_time += (double)(clock() - func_start_time) / CLOCKS_PER_SEC;
}

void population_initialization() {//初始化的连通度相差较大，可以尝试加大人口，或者加大local search迭代次数，提高初始化连通度
for (int i = 0; i < parent_num; ++i) {
fill(deleted, deleted + vertex_num, false);
//fill(conf_changed, conf_changed + vertex_num, false);
solution_operating.resize(K);
for (int j = 0; j < K; ++j) {
solution_operating[j] = rand() % vertex_num;
while (deleted[solution_operating[j]]) solution_operating[j] = rand() % vertex_num;
deleted[solution_operating[j]] = true;
}//为什么每次初始化得到的解的连通度都一样，而且每次都只剩下一个cpn？运行时间间隔太小导致srand()函数没有发挥作用，而导致得到的解都一样
component_based_neghborhood_search();//还是图的关系，初始化得到的解都一样差？
while (true) {
bool differ = true;
vector visited(vertex_num, false);
for(auto &v : solution_operating) visited[v] = true;
for (int j = 0; j < i; ++j) {
int dis = 0;
for(auto &v:solutions[j]) dis += visited[v];
dis = K - dis;
if (dis == 0) {//可以设为小于某个阈值，则进行交换操作？
differ = false;
break;
}
}
if (differ) break;
int idx = rand() % K;
int add_vertex = rand() % vertex_num;
while(deleted[add_vertex]) add_vertex = rand() % vertex_num;
deleted[solution_operating[idx]] = false;
deleted[add_vertex] = true;
solution_operating[idx] = add_vertex;
}
solutions[i] = solution_operating;
int cnty = (connectivities[i] = get_connectivity());
cout << i << “ initialization connectivity : “ << cnty << endl;
if(cnty < min_connectivity_once) {//记录单次最优解
min_connectivity_once = cnty;
best_solution_once = solution_operating;
}
for(int j = 0; j < i; ++j) {//初始化距离矩阵与总距离
int common = 0;
for(int m = 0; m < K; ++m) common += deleted[solutions[j][m]];
int dis = K - common;
total_distances[j] += dis;
total_distances[i] += dis;
}
}
}

void double_backbone_based_crossover(vector &S1, vector &S2) {
vector XB;
fill(deleted, deleted + vertex_num, false);//重置del数组，表示所有点都未放进S
//fill(conf_changed, conf_changed + vertex_num, false);
solution_operating.clear();
vector visited(vertex_num, false);
for (auto &v:S1) visited[v] = true;
for (auto &v:S2)
if (visited[v]) {
solution_operating.push_back(v);//在s1也在s2的点
deleted[v] = true;
visited[v] = false;
}
else XB.push_back(v);//在s2但是不在s1里的点
for (auto &v:S1)
if (visited[v]) XB.push_back(v);//在s1但是不在s2里的点
for (auto &v : XB)
if (rand() % 100 <= SP0) {
solution_operating.push_back(v);
deleted[v] = true;
}
if(solution_operating.size() == K) return;
seperate_graph();//划分cpn
for (auto &v:S1) visited[v] = true;
for (auto &v:S2) visited[v] = true;//记录XC
while (solution_operating.size() < K) {//不够K的话要加顶点到后代
int large_idx = select_large_component();
vector& large_cpn = components[large_idx];
int idx = rand() % large_cpn.size();
int add_vertex = large_cpn[idx];
if (!visited[add_vertex] && !deleted[add_vertex]) {
solution_operating.push_back(add_vertex);
add_to_solution(add_vertex);
}
}
while (solution_operating.size() > K) remove_from_solution();
}

bool distance_compare(int i, int j) {return total_distances[i] > total_distances[j];}
bool cnty_compare(int i, int j) {return connectivities[i] < connectivities[j];}

void rank_based_pool_updating(int connectivity) {//尝试不要直接加进去再算要不要加，而是根据原本的解，构建一个阈值，不用每次计算这么多
solutions[parent_num] = solution_operating;
connectivities[parent_num] = connectivity;
vector index(parent_num + 1, -1);
for(int i = 0; i < parent_num + 1; ++i) index[i] = i;
stable_sort(index.begin(), index.end(), cnty_compare);
for(int i = 0; i < parent_num + 1; ++i) rank_connectivity[index[i]] = i;
vector diss(parent_num);//新产生的解与其他解之间的距离
int dis;
//int tmp = 0;
total_distances[parent_num] = 0;
for(int i = 0; i < parent_num; ++i) {//求总距离
dis = 0;
for(auto &v : solutions[i]) dis += deleted[v];
dis = K - dis;
diss[i] = dis;
total_distances[parent_num] += dis;
total_distances[i] += dis;
//cout << total_distances[i] << “ “;
//tmp += total_distances[i];
}
//cout << total_distances[parent_num] << “ “ << (tmp + total_distances[parent_num]) / (parent_num + 1) << endl;
stable_sort(index.begin(), index.end(), distance_compare);
for(int i = 0; i < parent_num + 1; ++i) rank_distance[index[i]] = i;
/
for(auto &r : rank_distance) cout << r << “ “;
cout << endl;
for(auto &cnty : connectivities) cout << cnty << “ “;
cout << endl;
for(auto &r : rank_connectivity) cout << r << “ “;
cout << endl;
/
int idx = -1;
double max_score = -1, score;
for(int i = 0; i < parent_num + 1; ++i) {//找出加权排名最低的解
score = BETA rank_connectivity[i] + (1 - BETA) rank_distance[i];//求加权排名
if(score > max_score) {
idx = i;
max_score = score;
}
}
if(idx == parent_num) {
for(int i = 0; i < parent_num; ++i) total_distances[i] -= diss[i];
return;
}
vector visited(vertex_num, false);
for(auto &v : solutions[idx]) visited[v] = true;
for(int i = 0; i < parent_num + 1; ++i) {
int dis = 0;
for(auto &v : solutions[i]) dis += visited[v];
dis = K - dis;
total_distances[i] -= dis;
}
swap(solutions[idx], solutions[parent_num]);
total_distances[idx] = total_distances[parent_num];//total_distances需要更新
connectivities[idx] = connectivities[parent_num];//交换connectivity，交换rank
}

void Critical_Node_Problem() {
srand(time(0));
min_connectivity_once = vertex_num * vertex_num;//该次最小的连通度
best_solution_once.clear();
start_time = clock();
population_initialization();//初始化所有解
init_cost_time += time_cost();
start_time = clock();
double cost_time;
fill(weight, weight + vertex_num, 0);
while (!timeout()) {
int Si = rand() % parent_num;
int Sj = rand() % parent_num;
while (Si == Sj) Si = rand() % parent_num, Sj = rand() % parent_num;
double_backbone_based_crossover(solutions[Si], solutions[Sj]);
component_based_neghborhood_search();
if (cnty_operating < min_connectivity_once) {
best_solution_once = solution_operating;
min_connectivity_once = cnty_operating;
cost_time = time_cost();
}
cout << “min connectivity once : “ << min_connectivity_once << “ / “ << cnty_operating << endl;
cout << “best ever : “ << f_best << endl;
rank_based_pool_updating(cnty_operating);
}
if (min_connectivity_once < f_best) {//更新所有次数最优解
best_solution = best_solution_once;
f_best = min_connectivity_once;
t_avg = cost_time;
succeed_times = 1;
}
else if (min_connectivity_once == f_best) {
t_avg += cost_time;
succeed_times++;
}
min_cnty.push_back(min_connectivity_once);
f_avg += min_connectivity_once;
out << min_connectivity_once << endl;
}

void one_benchmark(string filename, int k) {
K = k;
read_graph(filename);
f_best = vertex_num * vertex_num;
f_avg = 0;
succeed_times = 0;
t_avg = 0;
init_cost_time = 0;
func_time = 0;
iter = 0;

min_cnty.clear();<br />for (int i = 0; i < run_times; ++i) Critical_Node_Problem();<br />    out << filename << endl;<br />    for (int i = 0; i < run_times; ++i) out << min_cnty[i] << " ";<br />    out << endl;<br />    out << fixed;<br />out << "f_best " << f_best << endl;<br />out << "f_avg " << setprecision(1) << double(f_avg)/run_times << endl;<br />out << "succeed_times " << succeed_times << endl; <br />out << "t_avg " << setprecision(1) << t_avg / succeed_times << endl;<br />out << "init_cost_time " << setprecision(1) << init_cost_time / run_times << endl;<br />out << "func_time " << setprecision(1) << func_time / run_times << endl;<br />out << "iter " << iter << endl << endl << endl;
for (int i = 0; i < run_times; ++i) cout << min_cnty[i] << " ";<br />    cout << endl;<br />cout << fixed;<br />    cout << "SP0 = " << SP0 << endl;<br />cout << "f_best " << f_best << endl;<br />cout << "f_avg " << setprecision(1) << double(f_avg)/run_times << endl;<br />cout << "succeed_times " << succeed_times << endl; <br />cout << "t_avg " << setprecision(1) << t_avg / succeed_times << endl;<br />cout << "init_cost_time " << setprecision(1) << init_cost_time / run_times << endl;<br />cout << "func_time " << setprecision(1) << func_time / run_times << endl;<br />cout << "iter " << iter << endl;<br />}

int main() {
vector file_names = {“BenchMarks/cnd/WattsStrogatz_n500.txt”, “BenchMarks/cnd/ErdosRenyi_n2500.txt”,
“BenchMarks/RealInstances/powergrid.txt”, “BenchMarks/RealInstances/Hamilton5000.txt”};
vector Ks = {125, 200, 494, 500};
string results_filename = “results_MA.txt”;
out.open(results_filename);
for(int i = 0; i < 4; ++i) one_benchmark(file_names[i], Ks[i]);
system(“pause”);
return 0;
}