This paper presents a solution for the Quality-based Software-Selection and Hardware-Mapping problem using the ACO algorithm. ACO is one of the most successful swarm intelligence algorithms for solving discrete optimization problems. The evaluation results show that the proposed approach generates correct results for all evaluated test cases. Also, better results in terms of performance and scalability are given in comparison with the ILP and EMFeR approaches.
choose paths marked by strong pheromone. This helps the ant to choose the best path. After an ant finds food and returns to the nest, it will deposit pheromone again and emphasizes on the correct path. If an ant does not find a food it does not deposit pheromone on the path passed previously. Figure 1 shows an experiment with a real colony of Argentine ants done by Goss et al. [6]. They will choose a shorter route, gradually. When faced with an obstacle, there is an equal chance for an ant to choose a path (the left or right). As the left path is shorter than the right one, the ant eventually deposits a higher level of pheromone. More ants take the left path, when more level of pheromone will be on that path.
Since, the ants may not have chosen very good paths especially in the early stages, it is essential to gradually withdraw these paths from the candidates of new selections. Therefore, there is a need for a concept called evaporation. The evaporation causes the pheromones to evaporate gradually, in order to omit the inappropriate paths.
Listing 1 presents the generic algorithm of ACO. The parameters are set in the initialization phase of this algorithm. Most parameters of ACO are similar to population based metaheuristic algorithms including Genetic and PSO. The most important parameter belonging to ACO is pheromone initialization.
Listing 1: Generic algorithm of ACO 1 Initialize including the pheromone trails and evaporation rate 2 Repeat 3 FOR each ant Do 4 Solution construction using pheromone trails 5 Evaporation 6 Reinforcement 7 Until stopping criteria 8 OUTPUT: Best solution found or a set of solutions
Each artificial ant can be seen as a greedy procedure that constructs a feasible solution in probabilistic fashion. In each step an ant selects a path based on the pheromone and heuristic information. For example in Travel Sales Man (TSP) problem, it can be considered as the distance between cities that each artificial ant cares about to make a better choice. Equation 1 shows the decision transition probabilities. S shows not yet visited solutions in current iteration.
( ij) ( ij)
Pij = P( ij) ( ij) ; i 2 [1; N]; j 2 S
After each ant made a feasible solution, pheromone trail, which is the most important concept of ant communication, will be updated in two phases. Reinforcement phase, where pheromone trails is updated based on the newly constructed solutions by colony in current iteration. Then, an evaporation phase is applied, where pheromone trail will decrease by a fixed proportion called evaporation rate.
Equation 2 shows updating pheromone. is a positive value added by ants in current iteration and ij shows the pheromone trail. Evaporation phase is shown in equation 3, where shows evaporation rate which has been set in the initialization phase.
ij = ij +
ij = (
Listing 2 presents the psudocode of our ACO solver (For more details refer to Appendix A.1). This psudocode has two main parts. In part 1 valid software solutions are generated and in part 2, the solutions are passed to swarm of ants for finding the best valid solutions. The population size and iteration size are predefined parameters that determine the termination of parts 1 and 2, respectively.
In part 1 of the psudocode an empty solution is created and for every requested component of the problem model, a valid software assignment is added to the solution. Each component has an implementation list that one of them should be selected randomly for the assignment. Each implementation has some required components and resources that should be mapped to a valid component and resource aiming at generating better abject values. For mapping required component to a valid component, an implementation is selected randomly and then is checked if a valid assignment for the required component is provided. Another implementation is selected until a valid assignment is produced. Following that it is essential to map valid software assignments to their required resources. To this end, all resources of the model are tested for each valid software assignment. If a resource does not violate the validity of assignment, it will be added to the list of possible resources of assignment. The values of , and are set for each resource of the list and then saved into two dimension matrixes in which columns indicate assignments and rows represent resources. Each cell of the matrixes presents values of , , or p. An invalid hardware solution is recognized, if a solution contains an assignment with no possible resource. Any other solutions are considered as valid software after which possible valid hardware solutions are passed to the ants.
Listing 2: The psudocode of the ACO solver 1 /* Part 1: Generating valid software solutions */ 2 Initialize population_size, 0, , 3 FOR each population 4 IF time has exceeded from maxSolvingTime THEN 5 exit 6 END IF 7 create an empty solution 8 FOR each requested components 9 create an empty assignmenti 10 create a valid component mappings for the assignmenti 11 find the possible resources from all of the available resources //the resources that don't violated the required property clauses and request constraints 12 IF an assignment has no possible resources THEN 13 Ignore the solution 14 ELSE 15 FOR each possible resourcesj 16 1https://github.com/Ariyanic/TTC18 2http://is.ieis.tue.nl/sta /pvgorp/share/?page=MyVirtualDiskImageBanners#XP-TUe_TTC18-ACO.vdi
In part 2, for each saved solution, an ant is created and the solution with its possible resource and the , and matrix are passed to the ant. Following that ants are run for finding the best solution. Additionally, the value of the and matrix is updated for running ants in the next iteration. At the end of each iteration, the best of ant solutions is added to an array. Finally, the algorithm is terminated according to the predefined condition, and the last solution of the array is identified as an optimal solution.
Listing 3 shows the psudocode of the ant.run() method (For more details refer to Appendix A.2). Each ant selects assignments of the received solution one by one with respect to a number of possible resources, such that assignments with the smallest number of possible resources have higher priority than other assignments. This is because the resource cannot be shared between more than one assignment. If an assignment with a small number of possible resources is investigated later, it is possible that all of its possible resources are allocated by other assignments, and therefore the solution becomes invalid. In this paper the map data structure is used for implementing this mechanism. Each map consists of keys and values. The key factors correspond to the number of possible resources and values relate to the index of the assignment. The map is constructed in the first part of the ACO solver after finding possible resources, and then it is passed to the ant with the , , and parameters. In this step, each ant investigates the existence of possible resources for the selected assignment, which have not been used by other assignments. If a resource is found the ant calculates the probability of selecting any possible resources of the assignment. It then selects one of them using a roulette wheel mechanism based on the probability of selecting the resource. If the Roulette Wheel selects an unused resource, the resource is allocated to the assignment, and the and for the selected resource are updated (based on equations 2 and 3). Finally, the updated solution with the best resource mapping is returned by the ant, if the process is terminated successfully for all the assignment of the solution.
Listing 3: The psudocode of the ant.run() method 1 Initialize , , and Q 2 Sort the assignments of the solution based on the number of possible resources 3 FOR each assignments 4 IF there is at least one possible resource that has not been used by other assignment 5 Select a possible resourcej using Rolette Wheel mechanism that has not been used by other assignment 6 Assign resourcej to assignmenti 7 8 9
In order to evaluate our solution in comparison with the other solutions, all of them are run on a standard Windows 7 PC using an Intel R CoreTM i5-2430M with 2.40GHz processor and 4.00 GB RAM. Table 1 shows the results of evaluation w.r.t. their correctness, performance, solution quality and scalability. As explained in the case study description [1]: “Correctness denotes that only solutions not violating the minimum requirements of the users are considered valid”. “The performance of an approach describes how fast a solution can be computed for a given problem”. In order to prevent running the benchmarks very long, the timeout is set on 15 minutes. “The solution quality quantifies how close the computed solution is to the optimal solution”. For this purpose, the objective value of the solutions is measured based on the objective function in the current model. “The objective function is represented as minimization of either a weighted sum or the maximum of all variables”; Therefore the solutions with less objective value are better in terms of quality (except zero points which means the solution has failed in the validity test).
Finally, “scalability is represented by the size of the largest problem”. As shown in Table 1, for each scalability level, the population and iteration size of the ACO algorithm is increased in order to find a better objective for the solution.
The outcome indicates that this approach generates correct results for the evaluated test cases. Also, better results in terms of performance and scalability are given in comparison with the results of the ILP and EMFeR approaches.
In the paper the ACO algorithm is used to solve the Quality-based Software-Selection and Hardware-Mapping problem. ACO is a comprehensive algorithm for solving discrete optimization problems. It is a constructive algorithm that in each step a feasible solution for the next step is constructed. Additionally, ACO is a populationbased algorithm, in which each ant is a candidate solution in a solution space. The population size can be increased according to the problem. Importantly, each ant can run autonomously and this makes an optimal result in terms of performance.
The scalability, performance and quality of the proposed solution are tested on di erent benchmarks. The outcome indicates that this approach generates correct results for the evaluated test cases. Also, better results in terms of performance and scalability are given in comparison with the results of the ILP and EMFeR approaches.
A A.1
ACOSolver.java public ACOSolver setPopulation_size(int population_size) { this.population_size = population_size; return this; int population_size = 50000; int iteration_size = 50; private static final Logger logger = LogManager.getLogger(ACOSolver.class); private Solution lastSolution; private long lastSolvingTime; private int solutionCounter; private long maxSolvingTime; private StopWatch stopWatch; private boolean timedOut; int numAssignments = 0; public Assignment ACOCreateSoftwareAssignment(Request request, Component component, boolean topLevel, int i) { Assignment assignment = new Assignment(); assignment.setRequest(request); assignment.setTopLevel(topLevel); Implementation implementation = component.getImplementation(i); assignment.setImplementation(implementation); for (ComponentRequirement requirement : implementation.getComponentRequirementList()) { for (Instance instance : requirement.getInstanceList()) { int rangeMin = 0; int rangeMax = requirement.getComponentRef().getRef().getImplementationList().getNumChild(); Assignment ass = null; do{ int randomNum = ThreadLocalRandom.current().nextInt(rangeMin, rangeMax); ass = ACOCreateSoftwareAssignment(request, requirement.getComponentRef().getRef(), false, randomNum); }while(!ass.isSoftwareValid()); assignment.addComponentMapping(new ComponentMapping(instance, ass)); } for (Instance instance : implementation.getResourceRequirement().getInstanceList()) { assignment.setResourceMapping(new ResourceMapping(instance, null, new de.tudresden.inf.st.mquat.jastadd.model.
List<>())); private static void assignResource(Assignment assignment, Resource resource) {
Implementation impl = assignment.getImplementation(); ResourceMapping mapping = new ResourceMapping(impl.getResourceRequirement().getInstance(0), resource, new de.tudresden.inf.st.mquat.jastadd.model.List<>()); SolverUtils.populateResourceMapping(mapping, impl.getResourceRequirement(), resource); assignment.setResourceMapping(mapping); } int numSoftwareSolutions = 0; int numTotalSoftwareSolutions = 0; stopWatch = StopWatch.start(); List<Solution> solutions = new ArrayList<>(); List<Solution> currentSolutions = new ArrayList<>(); List<List<Set<Resource>>> currentPossibleResources = new ArrayList<>(); List<List<List<Double>>> currentTau = new ArrayList<>(); // Pheromone for each resources List<List<List<Double>>> currentEta = new ArrayList<>(); // Objective for each resources List<List<Double>> currentDenominatorP = new ArrayList<>();
List<List<List<Double>>> currentNumeratorP = new ArrayList<>(); List<Map<Integer, List<Integer>>> currentSort = new ArrayList<>();
} Solution currentSolution = new Solution(); currentSolution.setModel(model); de.tudresden.inf.st.mquat.jastadd.model.List<Request> requests = model.getRequests(); for(Request request: requests){ int rangeMin = 0; int rangeMax = request.getTarget().getRef().getImplementationList().getNumChild(); Assignment ass = null; do{ int randomNum = ThreadLocalRandom.current().nextInt(rangeMin, rangeMax); ass = ACOCreateSoftwareAssignment(request, request.getTarget().getRef(), true, randomNum); }while(!ass.isSoftwareValid()); currentSolution.addAssignment(ass); de.tudresden.inf.st.mquat.jastadd.model.List<Resource> resources = model.getHardwareModel().getResources(); numTotalSoftwareSolutions++; List<Assignment> assignments = currentSolution.allAssignments(); List<Set<Resource>> possibleResources = new ArrayList<>(assignments.size()); boolean isHardwareValid = true; double tau0 = 1; List<List<Double>> tau = new ArrayList<>(); // Pheromone for each resources List<List<Double>> eta = new ArrayList<>(); // Objective double alpha = 1; double beta = 1; List<List<Double>> numeratorP = new ArrayList<>(); List<Double> denominatorP = new ArrayList<>(); Map<Integer, List<Integer>> SortIndexByPossibleResource = new HashMap<>(); int index = 0; Parallel.ForEach(population, new LoopBody<Ant>() { @Override public void run(Ant ant) { int ant_Number = ant.id; List<List<Double>> tau = currentTau.get(ant_Number); ///////////// BEFORE RUN List<List<Double>> numeratorP = currentNumeratorP.get(ant_Number); List<Double> denominatorP = currentDenominatorP.get(ant_Number); if (antSolution != null) { currentTau.set(ant_Number, tau); ///////////// AFTER RUN currentNumeratorP.set(ant_Number, numeratorP); currentDenominatorP.set(ant_Number, denominatorP); numAssignments += ant.numAssignments; solutionCounter++; if (solutions.isEmpty() || antSolution.computeObjective() < solutions.get(solutions.size() - 1).
computeObjective()) { Solution clone = antSolution.deepCopy(); solutions.add(clone); logger.info("found a better solution with an objective of {}.",antSolution.computeObjective()); } }); } }
} logger.info("Number of total software solutions: {}", numTotalSoftwareSolutions); logger.info("Number of iterated software solutions: {}", numSoftwareSolutions); logger.info("Number of iterated solutions: {}", numAssignments); logger.info("Number of correct solutions: {}", solutionCounter); if (solutions.size() > 0) {
lastSolution = solutions.get(solutions.size() - 1); } else { lastSolution = Solution.emptySolutionOf(model); logger.warn("Found no solution!"); } lastSolvingTime = stopWatch.time(TimeUnit.MILLISECONDS); return lastSolution; } } } private void reset() { this.lastSolution = null; this.solutionCounter = 0; this.lastSolvingTime = 0; this.timedOut = false; @Override public long getLastSolvingTime() {
return lastSolvingTime; A.2
Ant.java import de.tudresden.inf.st.mquat.jastadd.model.Assignment; import de.tudresden.inf.st.mquat.jastadd.model.Implementation; import de.tudresden.inf.st.mquat.jastadd.model.Resource; import de.tudresden.inf.st.mquat.jastadd.model.ResourceMapping; import de.tudresden.inf.st.mquat.jastadd.model.Solution; import de.tudresden.inf.st.mquat.solving.SolverUtils;
Ant(int i, Solution solu, List<Set<Resource>> pr, List<List<Double>> et, Map<Integer, List<Integer>> sort, int num ) { id = i; currentSolution = solu; possibleResources = pr; eta = et; Sort = sort; numAssignments = num; List<Assignment> assignments = currentSolution.allAssignments(); Stack<Resource> usedResources = new Stack<>(); double alpha = 1; double beta = 1; double rho = 0.1; // Evaporation rate double Q = 2; List<Integer> keys = new ArrayList<Integer>(Sort.keySet());
Collections.sort(keys); // "keys" are number of possible resources & "values" are index of the assignments assignResource(assignment, resource); usedResources.push(resource); denominatorP.set(index, denominatorP.get(index) - numeratorP.get(index).get(select)); List<Double> taui = tau.get(index); // Upadte Pheromone -> tau[index][select] = tau[index][select] + (Q /assignment.computeObjective()); taui.set(select, taui.get(select) + (Q / assignment.computeObjective())); // Evaporation on Pheromone of antSolution.allAssignments(); taui.set(select, (1 - rho) * taui.get(select)); // tau[index][select] = (1 - rho) * tau[index][select]; tau.set(index, taui); // p[index][select] = (tau[index][select] * alpha) + (eta[index][select] * beta); List<Double> sIndex = numeratorP.get(index); sIndex.set(select, (tau.get(index).get(select) * alpha) + (eta.get(index).get(select) * beta)); numeratorP.set(index, sIndex); denominatorP.set(index, denominatorP.get(index) + numeratorP.get(index).get(select)); }
} numAssignments++; return currentSolution;