“蚁群算法”学习包下载

refla

这是一个控制台程序，你可以用 VC++ Express 打开并且编译运行它。

我还提供了 Unix / Linux 下的 GCC 版本，编译方法如下：
gcc -o mmas mmas.c -lm -static

我已经把这个方法写在源文件 mmas.c 一开始处的注释。

我提供了 3 个 demo 数据，前两个是小规模测试数据，分别是 4 维的对称阵 和 5 维的非对称阵，方便大家跟踪、了解蚁群算法的执行过程；第三个是 12 维的测试数据，已经超出人类的跟踪能力，可以作为调整参数、优化程序的用例。最明显的，就是屏蔽掉 local search 后，求解结果的质量明显低于使用 local search 的情况。

这三个用例都放在 test_mmas() 中，你只要在 test_mmas() 中注释掉代表对应用例的宏，就行了。

例如，我想用第三个用例，那就

//#define  DEMO1
//#define  DEMO2
#define  DEMO3

test_mmas() 会被 read_instance() 调用，所以，如果你想使用自己的用例，可以在 read_instance() 中注释掉 test_mmas()，直接实现自己需要读取的文件即可。

最后放上源代码
mmas.rar (366.85 KB, 下载次数: 1794)

2012-5-5 18:21 上传

点击文件名下载附件

refla

VC++ Express 下载
http://www.microsoft.com/visuals ... /visual-cpp-express

选择适合自己的语言。。。

这是一个免费的开发 .NET 工具，安装一个月后必须注册才能继续使用。

refla

回复 30# acp134

acp134

回复 33# refla


   

refla

分支限界（Branch and Bound）算法是一种带剪枝技巧的搜索算法。当应用在 TSP 时，分支限界法的最大优势是，它一定能找到最优解。

我这代码所带的 3 个算例，还是上次 MMAS 的那 3 个，这可以验证 MMAS 确实有一定概率能找到最优解的。比如，第三个算例的最优解就是 1185485。当然，MMAS 更多时候找到的是次优解 1187399。

注意，分支限界算法处理有向图和无向图的方式是不一样的，这一点我在算例的代码注释中已经说明了！

下面介绍一下分支限界算法的基本概念，以方便大家阅读代码。

行（列）归约 —— 用一行（列）的最小数据减去行（列）中的各个数据。显然，经过归约后，行（列）中最小数据所在的位置必定为零！
行（列）归约数 —— 用来归约一行（列）的数据。显然，行（列）归约数就是该行（列）最小的数据。
归约矩阵 —— 每一行每一列都归约过的矩阵。显然，归约过的矩阵每一行每一列都至少有一个零。

归约矩阵中，那些数值为零的位置，就是那些有可能成为 TSP 的边。那么，我们该如何选择呢？

很简单，我们把那些零逐个挖去，然后重新对这一行和这一列进行归约，则行归约数和列归约数之和，就是不选择这条边的“代价”。显然，我们应该选择代价最高的边。

做出选择后，下一步自然就分裂成选择边和不选择边这两种情况了。在代码中，我把这两种情况分别成为“左节点（left node）”和“右节点（right node）”。

然后，又重复进行归约和选择，直至得到最优解为止！

以下是算法的主体框架：

1. void fuck_tsp()
   
2. {
   
3.   implement_project_branch_bound();
   
4. }
   
5. 
   
6. void implement_project_branch_bound()
   
7. {
   
8.   initialize();
   
9. 
   
10.   struct _node  *node = tsp.next;
    
11.   while( node->order_matrix > 2 )
    
12.   {
    
13.     struct _node  *left = construct_left_node();
    
14.     struct _node  *right = construct_right_node();
    
15. 
    
16.     dequeue();
    
17.     enqueue( left );
    
18.     enqueue( right );
    
19. 
    
20.     node = tsp.next;
    
21.   }
    
22. 
    
23.   output();
    
24.   clear();
    
25. }
    
26. 
    
27. struct _node  *construct_left_node()
    
28. {
    
29.   struct _node  *node = construct_node();
    
30.   struct _node  *backup = tsp.next;
    
31.   tsp.next = node;
    
32. 
    
33.   set_adjacency_list();
    
34.   set_signpost();
    
35.   decrease_order();
    
36.   node->lower_limit += reduce_array();
    
37.   search_candidate();
    
38. 
    
39.   if( 2 == node->order_matrix ) // Well, we find a solution.
    
40.   {
    
41.     if( 0 == node->cost[ 0 ][ 0 ] )
    
42.     {
    
43.       node->potential_edge.row = 0;
    
44.       node->potential_edge.column = 0;
    
45.       set_adjacency_list();
    
46. 
    
47.       node->potential_edge.row = 1;
    
48.       node->potential_edge.column = 1;
    
49.       set_adjacency_list();
    
50.     }
    
51.     else
    
52.     {
    
53.       node->potential_edge.row = 0;
    
54.       node->potential_edge.column = 1;
    
55.       set_adjacency_list();
    
56. 
    
57.       node->potential_edge.row = 1;
    
58.       node->potential_edge.column = 0;
    
59.       set_adjacency_list();
    
60.     }
    
61.   }// if( node->order_matrix )
    
62. 
    
63.   tsp.next = backup;
    
64.   return  node;
    
65. }
    
66. 
    
67. struct _node  *construct_right_node()
    
68. {
    
69.   struct _node  *node = construct_node();
    
70.   struct _edge  *potential_edge = &( node->potential_edge );
    
71.   copy_node( node, tsp.next );
    
72. 
    
73.   struct _node  *backup = tsp.next;
    
74.   tsp.next = node;
    
75. 
    
76.   node->cost[ potential_edge->row ][ potential_edge->column ] = NO_ROUTE;
    
77.   node->lower_limit += reduce_array();
    
78.   search_candidate();
    
79. 
    
80.   tsp.next = backup;
    
81.   return  node;
    
82. }
    

复制代码

Branch and Bound.rar (30.71 KB, 下载次数: 1872)

2012-5-20 19:13 上传

点击文件名下载附件