تولید شماره رنگی یک گراف با استفاده از بهینه سازی کلونی مورچه و مقایسه عملکرد آن با آنیل شبیه سازی شده

The problems which are NP-complete in nature are always attracting the computer scientists to develop some heuristic algorithms, generating optimal solution in time-space efficient manner compared to the existing ones. Generating the chromatic number of a graph in reasonable time belongs to the same category, where the algorithm designers are trying to propose some new algorithms for better result. The interesting feature of this problem is that many real world problems like register allocation, matrix partitioning problem, optical network design etc. can be represented in form of a graph. Once we efficiently generate the chromatic number of the graph, the optimal results of the original problem can be achieved automatically. Here, we have applied Ant Colony Optimization (ACO) for optimal vertex coloring of a simple, symmetric and connected graph (GCP). The algorithm has been tested upon a series of benchmarks including large scale test case, specially the graphs derived from the above mentioned problems, and has shown better output than Simulated Annealing(SA) algorithm on the same problem. Our work is still going on for designing better algorithms generating optimal solutions and applies it to solve other real life problems which can be mapped on the same.

A linear graph (or simply a graph) G = (V, E) consists of a set of objects V = {v1, v 2 , ...}called vertices in G, and another set E = {e1,e2,.}, whose elements are called edges in G, such that each edge e kis identified with an unordered pair (v i, vj) of vertices. Proper coloring of a simple, symmetric and connected graph is a classical problem of graph theory. A k-coloring of G is a partition of V into k subsets C i,i=1 .....k, such that no adjacent nodes belong to the same subset. The k colorability optimization problem is to find a k-coloring of G with k as small as possible. This smallest k corresponds to the chromatic number (G) of graph G. A k-vertex coloring of any graph is an assignment of k colors 1, 2, 3,..ktothe vertices of G.The reasons why the graph coloring problem is important are twofold. First, there are several areas of practical interest, in which the ability to color an undirected graph with a small number of colors as possible, has direct influence on how efficiently a certain target problem can be solved. Timetable scheduling [1], examination scheduling [2], register allocation [3], printed circuit testing [4], electronic bandwidth allocation [5], microcode optimization [6], channel routing [7], the design and operation of flexibl e manufacturing systems [8], computation of sparse Jacobian elements by finite differencing in mathematical programming [9], etc are some examples of such areas. The other reason is that, the graph coloring problem has been shown to be computationally hard at a variety of levels: not only its decision problem variant is NP- complete [10], but also its approximate version is NP hard [11].These two reasons are important enough to justify the importance for new heuristics to solve graph coloring problem.In this work, we have focused some real life problems and the benchmarks corresponding to them. One such problem is register allocation.The register allocation was formalized by Chaitin et al. [12][13]as a vertex coloring problem on an interference graph. In that graph, the node represents the live range of a variable, an edge between nodes indicates the interference between the live ranges, and a color corresponds to a physical register. The goal of that graph coloring register allocation is to optimize the total cost by optimizing the number of registers. The problem of Printed Circuit Board Testing[4],involves the problem of testing printed circuit boards PCBs) for unintended short circuits (caused by stray lines of solder). This gives rise to a graph coloring problem in which the vertices correspond to the nets on board and there is an edge between two vertices if there is a potential for a short circuit between the corresponding nets. Chromatic c oloring of the graph corresponds to partitioning the nets into optimal number of supernets", where the nets in each supernet can be simultaneously tested forshorts against all other nets, thereby speeding up the testing process.Another real life problem is Radio frequency assignment for broadcast services in geographic regions(includingcommercial radio stations, taxi dispatch, police and emergency services). The list of all possib le frequencies is fixed by government agencies, but adjacent geographic regions cannot use overlapping frequencies. To reduce frequency assignment to graph coloring, each geographic region needing K frequencies is represented with a K-clique, and all N x K possible bipartite edges are introduced between two geographically adjacent regions needing N and Kfrequencies respectively. Apart from the above real life problems we have considered in this work few other benchmarks generated from some other set of problems, e.g., graphs obtained from a matrix partitioning problem in the segmented columns approach to determine sparse Jacobian matrices, graphs obtained from real-life optical network design problems, where each vertex corresponds to a light path in the ne twork and edges correspond to intersecting paths.A variety of algorithms and approaches have been proposed to produce optimal or near optimal colorings over the years by different researchers

We have presented experimental results on some of the DIMACS benchmark graphs and compared the ACOGCP algorithms performance with the SAGCP. Indeed, our A CO GCP able to find the best known results for most of the tested graphs. But in some instances, A COGCP failed to generate optimal. That may due to the nature of the graph itself. As the results are generated in reasonable time that can be used automatically as a solution of the problem from which it has been derived. To strengthen conclusions made about the power of the algorithm, it is worth to test it on some other classes of large graphs from the benchmark set as well as from the random graphs. The main purpose of this paper is to study Ant Colony Optimization and compare with Simulated Annealing on graph coloring problem and test it on the graphs derived from some real world problems. Here we have tested it in sequential environment. In the future, we intend to refine ACOGCP and try to test it on truly distributed environment which can mimic the multi-agent nature of the algorithm. Also in future, well try to apply this algorithm to optimally color large complex graphs in reasonable time derived from other real world problems