Table 1 Simulation results of the three algorithms with n = 500, the values in each row are the average of 30 randomly generated interference graphs, each graph is tested by the three algorithms. ToTal CosT Number of spilled Nodes ruNTimes (s) a b oCH Coma Hea oCH Coma Hea oCH Coma Hea 0.10 0.04 96.31 52.90 58.87 16.17 10.57 11.27 4.41 6167.10 4759.69 0.25 0.45 0.60 0.75 0.90 0.08 18.20 0.13 0.63 5.01 0.10 0.23 6.21 4542.11 3979.45 0.10 10.47 0.00 0.00 2.40 0.00 0.00 6.71 4551.87 3911.65 0.15 5.21 0.00 0.00 1.13 0.00 0.00 7.21 4977.58 4331.75 0.20 0.00 0.00 0.00 0.00 0.00 0.00 6.45 3891.28 3282.44 0.04 753.35 642.93 704.97 98.41 84.53 90.13 6.75 21103.36 27225.39 0.08 248.13 185.77 210.40 48.13 36.13 39.47 6.25 6341.77 6286.90 0.10 139.40 79.57 95.10 29.55 18.20 19.13 6.34 2794.91 2283.79 0.15 44.71 12.77 14.00 12.51 2.70 3.00 6.24 1067.02 1748.35 0.20 10.20 1.40 1.73 3.14 0.80 0.80 6.42 1135.89 1184.80 0.04 1816.30 1721.00 1835.63 218.25 201.70 206.43 6.12 44135.36 43551.31 0.08 1002.46 911.43 992.17 152.14 135.43 141.73 5.32 28296.64 29924.65 0.10 724.06 619.87 677.83 124.70 105.90 111.37 5.14 15753.05 21820.81 0.15 247.42 185.60 211.93 57.41 45.73 49.00 5.24 1870.05 5099.23 0.20 56.80 32.20 47.73 19.20 12.43 14.13 5.18 715.70 1424.13 0.04 2487.41 2366.93 2497.57 289.41 273.77 278.20 5.24 50782.55 35383.77 0.08 1647.84 1511.23 1610.00 219.24 207.30 213.77 6.15 43152.85 31154.68 0.10 1294.15 1177.03 1257.00 192.11 176.33 184.23 7.15 33301.04 25504.60 0.15 698.95 588.67 633.70 121.42 109.53 114.37 5.61 4601.47 3018.95 0.20 342.11 262.47 294.77 68.15 56.87 61.90 6.05 2317.68 1266.86 0.04 3246.17 3108.13 3177.50 345.21 329.33 331.17 6.13 34269.39 33119.92 0.08 2531.59 2411.13 2479.37 294.32 279.47 282.47 7.15 29589.07 31651.79 0.10 2245.71 2130.53 2192.07 271.45 258.23 261.37 7.11 25809.97 27296.44 0.15 1655.83 1524.73 1574.70 226.73 208.97 212.57 5.13 22194.34 19966.34 0.20 1168.29 1046.17 1086.77 178.41 164.47 170.13 5.49 16448.77 15685.24 0.04 3968.22 3850.97 3937.37 423.45 393.20 393.43 5.67 30616.90 24114.79 0.08 3338.19 3250.63 3339.00 375.24 352.87 354.13 5.13 27969.15 23537.64 0.10 3145.70 3008.20 3073.47 348.90 336.40 337.70 5.91 26485.76 21956.67 0.15 2612.45 2474.90 2521.13 309.70 299.00 302.60 6.13 23421.52 11245.14 0.20 2152.41 2025.77 2047.87 278.22 266.53 268.67 7.14 18754.54 10283.17 space of the local search is decreased as the moving of nodes. A chromosome better than the offspring is obtained until no node can be moved. The parent with a larger value of fitness calculated by (4) is then replaced by the better chromosome. D. Spilling by Fitness After the end of the algorithm, the individual among the population that has the smallest value of fitness calculated by (4) is the solution of the resource allocation problem. The nodes in SS Ri of R i are spilled and the remaining nodes obtain a resource. The total cost is also calculated by (4). If the total cost is zero, then all the nodes obtain a resource, which means that the graph is k -colorable. So the resource allocation problem studied in this paper is a generalization of the k -coloring problem. As mentioned in Section II, the technique to calculate Fitness (R i) and Fitness (S p) has an evident effect on the result of crossover operator and the local search. The parent which has the larger value of fitness will be replaced by the offspring in the population. In the local search phase, the target resource class of a node is also determined by the Fitness (R i) (see (10)). After a final chromosome (the individual of the population which has the smallest value of fitness) is obtained, the nodes that should be spilled in a resource class R i are also determined by Fitness (R i) . For example, suppose all the nodes in Fig. 4 are in may 2014 | IEEE ComputatIonal IntEllIgEnCE magazInE 63