When it comes to solving the controller placement problem with tens of millions placements for which performing the exhaustive evaluation requires a considerable amount of time and memory budget, our proposed heuristic approach is an appropriate choice.
As described before, for such these large-scale instances, it is only possible to calculate an upper bound for evaluated placements and nothing can be expressed about the obtained accuracy of the heuristic algorithm. This is due to not existing the actual Pareto optimal solutions and hence, the absence of reference data to compare. Here, an evaluation including 40 graphs from the Internet Topology Zoo is carried out. For each graph, …show more content…
each triple (IGD,τ,f_min ). In this evaluation, it is supposed to τ=0.008 or 0.005 for the precision threshold and f_min=70 or 80 as the fraction of desired instances as described in the previous section. The height and color of each bar demonstrate the mean value of the relative budget in the evaluations of each category and each precision specification, i.e. as represented by each of four triples, respectively. Taking a glimpse to the graph makes it clear that the search spaces consisting of less than 2 million placements consume a significantly higher degree of relative budget than six other categories with larger search spaces. This trend is followed when comparing each category with the others located on its right-hand side. It can be deduced that for instances whose search spaces are not very large, POCO and MHNSGA evaluate a closer number of placements. By moving to the right of the graph, the falling rate of the heights is becoming considerably more