模拟退火实验报告(共6页).docx

精选优质文档-----倾情为你奉上算法报告一、课题名称 一种用于生物网络中最多公共边子图检测的模拟退火算法二、实验目的 介绍了一种用于多重最多公共边子图问题的启发式算法，它能够有效地检测出在多个真实世界大小的网络上共享的大型公共子结构三、实验环境· 现代C ++编译器支持C ++ 11和OpenMP· make· CMake> = 2.8· Boost标题· help2man（可选，用于手册页生成）四、实验主要步骤 安装所有以上环境后，运行以下命令：git clone --recursive cd sailmcscmake . && make 或者，您可以安装二进制文件和文档：sudo make install 要对齐三个图表，运行600秒：sailmcs -t 600 -g mcs.gw -o alignment.txt graph1.gw graph2.gw graph3.gw 最大公共子图将被写入文件mcs.gw，顶点对齐表将被写入alignment.txt五、实验核心代码#include #include #include #include namespace ublas = boost::numeric::ublas;namespace sailmcs {namespace ls { void Best::localSearch( const std::vector &graphs, Solution &solution ) { size_t m = solution.alignment.size1(); size_t n = solution.alignment.size2(); // Create reverse alignment mapping std::vector> map; create_map(graphs, solution, map); // Count number of graphs each edge is covered in edge_count_matrix edges; count_edges(graphs, map, solution, edges); // Build neighbor lists std::vector neighbors; create_neighbor_lists(graphs, map, solution, neighbors); // Active index map std::vector active(m, 0); std::random_device rd; std::minstd_rand rand_gen(rd()); int iteration = 0; bool repeat; do { repeat = false; for(size_t g = 0; g < n-1; ++g) { int best_delta = 0; size_t best_i = 0; size_t best_j = 0; #pragma omp parallel { int prv_best_delta = 0; size_t prv_best_i = 0; size_t prv_best_j = 0; #pragma omp for schedule(static, 1) for(size_t i = 0; i < m; ++i) { for(size_t j = i+1; j < m; ++j) { if(active[i] < iteration && active[j] < iteration) continue; int delta = get_delta(i, j, g, neighbors, edges); if(delta > 0) { active[i] = iteration+1; active[j] = iteration+1; } if(delta > prv_best_delta) { prv_best_delta = delta; prv_best_i = i; prv_best_j = j; } } } #pragma omp critical { if(prv_best_delta > best_delta) { best_delta = prv_best_delta; best_i = prv_best_i; best_j = prv_best_j; } } } if(best_delta > 0) { repeat = true; swap(best_i, best_j, g, iteration, neighbors, edges, solution, active); } } iteration++; } while(repeat); // Extract LCS and solution quality finalize(edges, solution); }}}六、实验数据部分数据如下：50个顶点的数据LEDA.GRAPHstringstring-250|{0}||{1}||{2}||{3}||{36}||{37}||{6}||{33}||{41}||{10}||{7}||{12}||{16}||{22}||{29}||{30}||{31}||{48}||{4}||{5}||{40}||{43}||{34}||{19}||{23}||{24}||{26}||{27}||{25}||{11}||{44}||{14}||{15}||{17}||{46}||{47}||{32}||{8}||{9}||{42}||{13}||{18}||{20}||{35}||{38}||{21}||{28}||{45}||{49}||{39}|701 2 0 |{?}|1 3 0 |{?}|1 4 0 |{?}|1 5 0 |{?}|1 6 0 |{?}|1 7 0 |{?}|1 8 0 |{?}|1 9 0 |{?}|1 10 0 |{?}|1 11 0 |{?}|1 12 0 |{?}|1 13 0 |{?}|1 14 0 |{?}|1 15 0 |{?}|1 16 0 |{?}|1 17 0 |{?}|2 3 0 |{?}|2 4 0 |{?}|2 12 0 |{?}|2 13 0 |{?}|2 18 0 |{?}|2 19 0 |{?}|2 20 0 |{?}|2 21 0 |{?}|2 22 0 |{?}|2 23 0 |{?}|2 24 0 |{?}|2 25 0 |{?}|2 26 0 |{?}|2 27 0 |{?}|2 28 0 |{?}|3 29 0 |{?}|4 19 0 |{?}|4 20 0 |{?}|7 19 0 |{?}|7 42 0 |{?}|8 19 0 |{?}|10 44 0 |{?}|11 20 0 |{?}|11 26 0 |{?}|13 14 0 |{?}|13 19 0 |{?}|13 20 0 |{?}|14 20 0 |{?}|15 41 0 |{?}|19 20 0 |{?}|19 25 0 |{?}|19 30 0 |{?}|19 31 0 |{?}|19 32 0 |{?}|19 33 0 |{?}|19 34 0 |{?}|19 35 0 |{?}|19 36 0 |{?}|20 24 0 |{?}|20 26 0 |{?}|20 37 0 |{?}|20 38 0 |{?}|20 39 0 |{?}|20 40 0 |{?}|20 41 0 |{?}|20 42 0 |{?}|20 43 0 |{?}|24 26 0 |{?}|26 47 0 |{?}|27 48 0 |{?}|28 49 0 |{?}|28 50 0 |{?}|32 45 0 |{?}|42 46 0 |{?}|七、实验结果 实验部分数据输出如下：（含截图）八、实验中的问题专心---专注---专业。