=Paper=
{{Paper
|id=Vol-2310/paper3
|storemode=property
|title=Solving the Quality-based Software-Selection and Hardware-Mapping Problem with ACO
|pdfUrl=https://ceur-ws.org/Vol-2310/paper3.pdf
|volume=Vol-2310
|authors=Samaneh Hoseindoost,Meysam Karimi,Shekoufeh Kolahdouz Rahimi,Bahman Zamani
|dblpUrl=https://dblp.org/rec/conf/staf/HoseindoostKRZ18
}}
==Solving the Quality-based Software-Selection and Hardware-Mapping Problem with ACO==
https://ceur-ws.org/Vol-2310/paper3.pdf
Solving the Quality-based Software-Selection and
Hardware-Mapping Problem with ACO
Samaneh HoseinDoost Meysam Karimi
s.hoseindoost@eng.ui.ac.ir meysam.karimi@eng.ui.ac.ir
Shekoufeh Kolahdouz-Rahimi Bahman Zamani
sh.rahimi@eng.ui.ac.ir zamani@eng.ui.ac.ir
MDSE research group
Department of Software Engineering
Faculty of Computer Engineering
University of Isfahan, Iran
Abstract
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.
1 Introduction
The TTC 2018 case [1] is a Searched Based Optimization Problem (SBSE) to provide an optimal mapping of
software implementation to hardware components for a given set of user requests. In recent years, SBSE has
been applied successfully in the area of model and program transformation [2, 3]. Variety of algorithms exist
to solve optimization problems with large or infinite search spaces. In this paper, the Ant Colony Optimization
(ACO), one of the most successful swarm intelligence algorithms [4], is applied for solving the TTC case.
The remainder of this paper is structured as follows. In section 2, the concept of ACO is overviewed. Section 3
presents the proposed solution to the TTC case. The evaluation of ACO algorithm in terms of performance,
quality and scalability is presented in Section 4. Finally, section 5 concludes the paper.
2 ACO Overview
ACO is one of the most successful swarm intelligence algorithms proposed by M. Dorigo [5]. This algorithm
is inspired by the foraging behavior of real ants in nature. In this algorithm ants communicate indirectly with
each other through modification of environment. When an individual ant modifies the environment, others
will realize and respond to the new modification. Real ants use a chemical trail called pheromone, which left on
the ground during their trips to modify the environment. When another ant choosing their path, they tend to
Copyright c by the paper’s authors.
In: A. Garcia-Dominguez, G. Hinkel and F. Krikava (eds.): Proceedings of the 11th Transformation Tool Contest, Toulouse, France,
29-06-2018, published at http://ceur-ws.org
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.
Figure 1: Optimal route between food and nest by real colony of ants
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.
(τi j )α (ηi j )β
Pi j = P , i ∈ [1, N], j ∈ S (1)
(τi j )α (ηi j )β
After each ant made a feasible solution, pheromone trail, which is the most important concept of ant com-
munication, 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.
τi j = τi j + ∆ (2)
τi j = (1 − ρ)τi j (3)
3 Solution
In order to apply the ACO algorithm to this problem, first a swarm of ants is created by transforming the
problem into an ACO specific solution. Following that each ant is evaluated and then deposited pheromone
according to the result of evaluation. New solutions are then generated from heuristic information and the
amount of pheromone deposited in predecessor iterations. The solutions are evaluated again to make better
results. The algorithm is terminated according to the predefined condition and finally the most optimal result
will be generated. The solution is implemented as two Java files: ACOSolver.java and Ant.java. It is available
as a Github repository1 . Additionally, the implementation is provided in Share virtual machine2 .
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 resources j
1 (τij )α (ηij )β
16 set τij = τ0 , ηij = and Pij = P α β
ob jective o f assignmenti ∀ j (τij ) (ηij )
17 END FOR
18 END IF
19 END FOR
20 Save the solutions // All component mappings of the solutions are valid and their assignments have at least one
possible resource.
21 END FOR
22
23 /* Part 2: Finding the best valid solution */
24 Initialize iteration_size
25 bestSolution is empty
26 FOR each iteration
27 IF time has exceeded from maxSolvingTime THEN
1 https://github.com/Ariyanic/TTC18
2 http://is.ieis.tue.nl/staff/pvgorp/share/?page=MyVirtualDiskImageBanners#XP-TUe_TTC18-ACO.vdi
28 exit
29 END IF
30 FOR each saved solution
31 Create an ant, and pass to current solution, possible resources, τ, η and P into it
32 END FOR
33 Run all ants in parallel
34 Update τ and P to new values
35 IF bestSolution is empty or the objective of antSolution is better than the objective of bestSolution
36 Place antSolution as the bestSolution
37 END IF
38 END FOR
39 OUTPUT: The bestSolution
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 resource j using Rolette Wheel mechanism that has not been used by other assignment
6 Assign resource j to assignmenti
Q
7 Update τij -> τij = τij +
ob jective o f assignmenti
8 Evaporate τij -> τij = (1 − ρ) ∗ τij
(τij )α (ηij )β
9 Calculate Pij = P α β
∀ j (τij ) (ηij )
10 END IF
11 END FOR
12 OUTPUT: The solution
4 Evaluation
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 consid-
ered 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.
Table 1: Evaluation results for the solutions
Execution Time Best objective of
Scalability Level Name (Performance) the valid solution Valid TimeOut
in ms (Quality)
ACO (pop=1, iter=1) 13 226823.7 TRUE FALSE
ILP-direct / external 619 / 445 226823.7 / 226823.7 TRUE / TRUE FALSE / FALSE
trivial
EMFeR 366 226823.7 TRUE FALSE
Simple 1 226823.7 TRUE FALSE
ACO (pop=5, iter=1) 20 34620.2 TRUE FALSE
ILP-direct / external 89 / 311 34620.2 / 34620.2 TRUE / TRUE FALSE / FALSE
small
EMFeR 326 34620.2 TRUE FALSE
Simple 4 34620.2 TRUE FALSE
ACO (pop=8, iter=1) 31 34620.2 TRUE FALSE
ILP-direct / external 73 / 325 34620.2 / 34620.2 TRUE / TRUE FALSE / FALSE
small-many-hw
EMFeR 336 34620.2 TRUE FALSE
Simple 6 34620.2 TRUE FALSE
ACO (pop=80, iter=1) 737 974728.2 TRUE FALSE
ILP-direct / external 1015 / 2298 968744 / 968744 TRUE / TRUE FALSE / FALSE
small-complex-sw
EMFeR 679197 0 FALSE FALSE
Simple 900002 0 FALSE TRUE
ACO (pop=5000, iter=50) 113005 8747556 TRUE FALSE
ILP-direct / external 726894 / 900172 4746869 / 0 TRUE / FALSE FALSE / TRUE
medium
EMFeR GC overhead limit exceeded
Simple Run time error
5 Conclusion
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 population-
based 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 different 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.
References
[1] Sebastian Götz, Johannes Mey, Rene Schöne and Uwe Aßmann, “Quality-based Software-Selection and
Hardware-Mapping as Model Transformation Problem,” in Proceedings of the 11th Transformation Tool Contest,
a part of the Software Technologies: Applications and Foundations (STAF 2018) federation of conferences (A. Garcia-
Dominguez, G. Hinkel, and F. Krikava, eds.), CEUR Workshop Proceedings, CEUR-WS.org, June 2018.
[2] M. Fleck, J. Troya, M. Kessentini, M. Wimmer, and B. Alkhazi, “Model transformation modularization as a
many-objective optimization problem,” IEEE Trans. Softw. Eng, vol. 43, no. 11, pp. 1009–1032, 2017.
[3] G. Kappel, P. Langer, W. Retschitzegger, W. Schwinger, and M. Wimmer, “Model transformation by-example:
a survey of the first wave,” in Conceptual Modelling and Its Theoretical Foundations, pp. 197–215, Springer,
2012.
[4] L. Bianchi, M. Dorigo, L. M. Gambardella, and W. J. Gutjahr, “A survey on metaheuristics for stochastic
combinatorial optimization,” Natural Computing, vol. 8, no. 2, pp. 239–287, 2009.
[5] M. Dorigo, “Optimization, learning and natural algorithms,” PhD Thesis, Politecnico di Milano, 1992.
[6] S. Goss, S. Aron, J.-L. Deneubourg, and J. M. Pasteels, “Self-organized shortcuts in the argentine ant,”
Naturwissenschaften, vol. 76, no. 12, pp. 579–581, 1989.
A Appendix: Details of our solution
A.1 ACOSolver.java
1 package ir.ac.ui.eng;
2
3 import de.tudresden.inf.st.mquat.jastadd.model.*;
4 import de.tudresden.inf.st.mquat.solving.BenchmarkableSolver;
5 import de.tudresden.inf.st.mquat.solving.Solver;
6 import de.tudresden.inf.st.mquat.solving.SolverUtils;
7 import de.tudresden.inf.st.mquat.solving.SolvingException;
8 import de.tudresden.inf.st.mquat.utils.StopWatch;
9 import org.apache.logging.log4j.LogManager;
10 import org.apache.logging.log4j.Logger;
11
12 import java.util.*;
13 import java.util.List;
14 import java.util.concurrent.ThreadLocalRandom;
15 import java.util.concurrent.TimeUnit;
16
17 /**
18 * @author Samaneh Hoseindoost
19 * @author Meysan Karimi
20 * @author Shekoufeh Kolahdouz-Rahimi
21 * @author Bahman Zamani
22 */
23 public class ACOSolver implements BenchmarkableSolver {
24
25 int population_size = 50000;
26 int iteration_size = 50;
27 private static final Logger logger = LogManager.getLogger(ACOSolver.class);
28 private Solution lastSolution;
29 private long lastSolvingTime;
30 private int solutionCounter;
31 private long maxSolvingTime;
32 private StopWatch stopWatch;
33 private boolean timedOut;
34 int numAssignments = 0;
35
36 public ACOSolver() {
37 this(Long.MAX_VALUE);
38 }
39
40 public ACOSolver(long maxSolvingTime) {
41 this.maxSolvingTime = maxSolvingTime;
42 reset();
43 }
44
45 public ACOSolver setPopulation_size(int population_size) {
46 this.population_size = population_size;
47 return this;
48 }
49
50 public ACOSolver setIteration_size(int iteration_size) {
51 this.iteration_size = iteration_size;
52 return this;
53 }
54
55 public Assignment ACOCreateSoftwareAssignment(Request request, Component component, boolean topLevel, int i) {
56 Assignment assignment = new Assignment();
57 assignment.setRequest(request);
58 assignment.setTopLevel(topLevel);
59 Implementation implementation = component.getImplementation(i);
60 assignment.setImplementation(implementation);
61 for (ComponentRequirement requirement : implementation.getComponentRequirementList()) {
62 for (Instance instance : requirement.getInstanceList()) {
63 int rangeMin = 0;
64 int rangeMax = requirement.getComponentRef().getRef().getImplementationList().getNumChild();
65 Assignment ass = null;
66 do{
67 int randomNum = ThreadLocalRandom.current().nextInt(rangeMin, rangeMax);
68 ass = ACOCreateSoftwareAssignment(request, requirement.getComponentRef().getRef(), false, randomNum);
69 }while(!ass.isSoftwareValid());
70 assignment.addComponentMapping(new ComponentMapping(instance, ass));
71 }
72 }
73 for (Instance instance : implementation.getResourceRequirement().getInstanceList()) {
74 assignment.setResourceMapping(new ResourceMapping(instance, null, new de.tudresden.inf.st.mquat.jastadd.model.
List<>()));
75 }
76 return assignment;
77 }
78
79 private static void assignResource(Assignment assignment, Resource resource) {
80 Implementation impl = assignment.getImplementation();
81 ResourceMapping mapping = new ResourceMapping(impl.getResourceRequirement().getInstance(0), resource,
82 new de.tudresden.inf.st.mquat.jastadd.model.List<>());
83 SolverUtils.populateResourceMapping(mapping, impl.getResourceRequirement(), resource);
84 assignment.setResourceMapping(mapping);
85 }
86
87 @Override
88 public Solution solve(Root model) throws SolvingException {
89 reset();
90 if (model.getNumRequest() == 0) {
91 return Solution.emptySolutionOf(model);
92 }
93 int numSoftwareSolutions = 0;
94 int numTotalSoftwareSolutions = 0;
95 stopWatch = StopWatch.start();
96 List solutions = new ArrayList<>();
97 List currentSolutions = new ArrayList<>();
98 List>> currentPossibleResources = new ArrayList<>();
99 List>> currentTau = new ArrayList<>(); // Pheromone for each resources
100 List>> currentEta = new ArrayList<>(); // Objective for each resources
101 List> currentDenominatorP = new ArrayList<>();
102 List>> currentNumeratorP = new ArrayList<>();
103 List>> currentSort = new ArrayList<>();
104
105 /* Part 1: Generating valid software solutions */
106 for (int pop = 0; pop < population_size; pop++) {
107 if (stopWatch.time(TimeUnit.MILLISECONDS) > maxSolvingTime) {
108 timedOut = true;
109 break;
110 }
111 Solution currentSolution = new Solution();
112 currentSolution.setModel(model);
113 de.tudresden.inf.st.mquat.jastadd.model.List requests = model.getRequests();
114 for(Request request: requests){
115 int rangeMin = 0;
116 int rangeMax = request.getTarget().getRef().getImplementationList().getNumChild();
117 Assignment ass = null;
118 do{
119 int randomNum = ThreadLocalRandom.current().nextInt(rangeMin, rangeMax);
120 ass = ACOCreateSoftwareAssignment(request, request.getTarget().getRef(), true, randomNum);
121 }while(!ass.isSoftwareValid());
122 currentSolution.addAssignment(ass);
123 }
124
125 de.tudresden.inf.st.mquat.jastadd.model.List resources = model.getHardwareModel().getResources();
126 numTotalSoftwareSolutions++;
127 List assignments = currentSolution.allAssignments();
128 List> possibleResources = new ArrayList<>(assignments.size());
129 boolean isHardwareValid = true;
130 double tau0 = 1;
131 List> tau = new ArrayList<>(); // Pheromone for each resources
132 List> eta = new ArrayList<>(); // Objective
133 double alpha = 1;
134 double beta = 1;
135 List> numeratorP = new ArrayList<>();
136 List denominatorP = new ArrayList<>();
137 Map> SortIndexByPossibleResource = new HashMap<>();
138 int index = 0;
139
140 for (Assignment assignment : assignments) {
141 Set resourceList = new HashSet<>();
142 List taui = new ArrayList<>();
143 List etai = new ArrayList<>();
144 List numeratorPi = new ArrayList<>();
145 double sum = 0;
146 int i = 0;
147 for (Resource resource : resources) {
148 assignResource(assignment, resource);
149 if (assignment.isValid()) {
150 resourceList.add(resource);
151 taui.add(tau0); // Pheromone on antSolution.allAssignments().allResources;
152 etai.add(1 / assignment.computeObjective());
153 numeratorPi.add((taui.get(i) * alpha) + (etai.get(i) * beta));
154 sum += numeratorPi.get(i);
155 i++;
156 }
157 }
158 if(i == 0){
159 isHardwareValid = false;
160 break;
161 }
162 possibleResources.add(resourceList);
163 tau.add(taui);
164 eta.add(etai);
165 numeratorP.add(numeratorPi);
166 denominatorP.add(sum);
167 SortIndexByPossibleResource.computeIfAbsent(i, k -> new ArrayList<>()).add(index);
168 index++;
169 }
170 if(isHardwareValid == true){
171 numSoftwareSolutions++;
172 Solution clone = currentSolution.deepCopy();
173 currentSolutions.add(clone);
174 currentPossibleResources.add(possibleResources);
175 currentTau.add(tau);
176 currentEta.add(eta);
177 currentNumeratorP.add(numeratorP);
178 currentDenominatorP.add(denominatorP);
179 currentSort.add(SortIndexByPossibleResource);
180 }
181 }
182
183 /* Part 2: Finding the best valid solution */
184 for (int iteration = 0; iteration < iteration_size; iteration++) {
185 if (stopWatch.time(TimeUnit.MILLISECONDS) > maxSolvingTime) {
186 timedOut = true;
187 break;
188 }
189
190 List population = new ArrayList<>();
191 for (int i = 0; i < currentSolutions.size(); i++) {
192 Ant ant = new Ant(i, currentSolutions.get(i), currentPossibleResources.get(i), currentEta.get(i), currentSort.
get(i), numAssignments);
193 population.add(ant);
194 }
195
196 Parallel.ForEach(population, new LoopBody() {
197 @Override
198 public void run(Ant ant) {
199 int ant_Number = ant.id;
200 List> tau = currentTau.get(ant_Number); ///////////// BEFORE RUN
201 List> numeratorP = currentNumeratorP.get(ant_Number);
202 List denominatorP = currentDenominatorP.get(ant_Number);
203
204 Solution antSolution = ant.run(tau, numeratorP, denominatorP); //////////// Tau CHANGE AFTER RUN.
205
206 if (antSolution != null) {
207 currentTau.set(ant_Number, tau); ///////////// AFTER RUN
208 currentNumeratorP.set(ant_Number, numeratorP);
209 currentDenominatorP.set(ant_Number, denominatorP);
210 numAssignments += ant.numAssignments;
211 solutionCounter++;
212 if (solutions.isEmpty() || antSolution.computeObjective() < solutions.get(solutions.size() - 1).
computeObjective()) {
213 Solution clone = antSolution.deepCopy();
214 solutions.add(clone);
215 logger.info("found a better solution with an objective of {}.",antSolution.computeObjective());
216 }
217 }
218 }
219 });
220 }
221
222 logger.info("Number of total software solutions: {}", numTotalSoftwareSolutions);
223 logger.info("Number of iterated software solutions: {}", numSoftwareSolutions);
224 logger.info("Number of iterated solutions: {}", numAssignments);
225 logger.info("Number of correct solutions: {}", solutionCounter);
226
227 if (solutions.size() > 0) {
228 lastSolution = solutions.get(solutions.size() - 1);
229 } else {
230 lastSolution = Solution.emptySolutionOf(model);
231 logger.warn("Found no solution!");
232 }
233
234 lastSolvingTime = stopWatch.time(TimeUnit.MILLISECONDS);
235 return lastSolution;
236 }
237
238 private void reset() {
239 this.lastSolution = null;
240 this.solutionCounter = 0;
241 this.lastSolvingTime = 0;
242 this.timedOut = false;
243 }
244
245 @Override
246 public String getName() {
247 return "aco";
248 }
249
250 @Override
251 public long getLastSolvingTime() {
252 return lastSolvingTime;
253 }
254
255 @Override
256 public double getLastObjective() {
257 if (lastSolution != null) {
258 return lastSolution.computeObjective();
259 } else {
260 // TODO throw exception or do something reasonable
261 return 0d;
262 }
263 }
264
265 @Override
266 public Solver setTimeout(long timeoutValue, TimeUnit timeoutUnit) {
267 this.maxSolvingTime = timeoutUnit.toMillis(timeoutValue);
268 return this;
269 }
270
271 @Override
272 public boolean hadTimeout() {
273 return this.timedOut;
274 }
275 }
A.2 Ant.java
1 package ir.ac.ui.eng;
2
3 import java.util.ArrayList;
4 import java.util.Collections;
5 import java.util.Iterator;
6 import java.util.List;
7 import java.util.Map;
8 import java.util.Random;
9 import java.util.Set;
10 import java.util.Stack;
11
12 import de.tudresden.inf.st.mquat.jastadd.model.Assignment;
13 import de.tudresden.inf.st.mquat.jastadd.model.Implementation;
14 import de.tudresden.inf.st.mquat.jastadd.model.Resource;
15 import de.tudresden.inf.st.mquat.jastadd.model.ResourceMapping;
16 import de.tudresden.inf.st.mquat.jastadd.model.Solution;
17 import de.tudresden.inf.st.mquat.solving.SolverUtils;
18
19 /**
20 * @author Samaneh Hoseindoost
21 * @author Meysan Karimi
22 * @author Shekoufeh Kolahdouz-Rahimi
23 * @author Bahman Zamani
24 */
25 public class Ant {
26
27 int id;
28 Solution currentSolution;
29 List> possibleResources;
30 List> eta;
31 Map> Sort;
32 int numAssignments;
33
34 Ant(int i, Solution solu, List> pr, List> et, Map> sort, int num
) {
35 id = i;
36 currentSolution = solu;
37 possibleResources = pr;
38 eta = et;
39 Sort = sort;
40 numAssignments = num;
41 }
42
43 private static void assignResource(Assignment assignment, Resource resource) {
44 Implementation impl = assignment.getImplementation();
45
46 ResourceMapping mapping = new ResourceMapping(impl.getResourceRequirement().getInstance(0), resource,
47 new de.tudresden.inf.st.mquat.jastadd.model.List<>());
48 SolverUtils.populateResourceMapping(mapping, impl.getResourceRequirement(), resource);
49 assignment.setResourceMapping(mapping);
50 }
51
52 public int RoleteWhileSelection(double[] c) {
53
54 double rangeMin = 0.0f;
55 double rangeMax = c[c.length-1];
56 Random r = new Random();
57 double createdRanNum = rangeMin + (rangeMax - rangeMin) * r.nextDouble();
58 int i;
59 for (i = 0; i < c.length-1; i++) {
60 if (createdRanNum <= c[i + 1])
61 break;
62 }
63 return i;
64 }
65
66 public Solution run(List> tau, List> numeratorP, List denominatorP) {
67
68 List assignments = currentSolution.allAssignments();
69 Stack usedResources = new Stack<>();
70 double alpha = 1;
71 double beta = 1;
72 double rho = 0.1; // Evaporation rate
73 double Q = 2;
74 List keys = new ArrayList(Sort.keySet());
75 Collections.sort(keys); // "keys" are number of possible resources & "values" are index of the assignments
76
77 for (Integer key: keys) {
78
79 int siz = Sort.get(key).size();
80 for (int i = 0; i < siz; i++) {
81 int index = Sort.get(key).get(i);
82 Assignment assignment = assignments.get(index);
83 List resources = new ArrayList(possibleResources.get(index));
84
85 int remove = 0;
86 for (Iterator resIt = resources.iterator(); resIt.hasNext();) {
87 Resource resource = resIt.next();
88 if (usedResources.contains(resource)) {
89 remove++;
90 }
91 }
92 if (resources.size() == remove) {
93 return null;
94 }
95
96 List numerator = numeratorP.get(index);
97 double denominator = denominatorP.get(index);
98 int size = resources.size();
99 double[] p = new double[size];
100 double[] c = new double[size + 1];
101 c[0] = 0;
102 for(int j=0; j taui = tau.get(index);
119
120 // Upadte Pheromone -> tau[index][select] = tau[index][select] + (Q /assignment.computeObjective());
121 taui.set(select, taui.get(select) + (Q / assignment.computeObjective()));
122
123 // Evaporation on Pheromone of antSolution.allAssignments();
124 taui.set(select, (1 - rho) * taui.get(select)); // tau[index][select] = (1 - rho) * tau[index][select];
125 tau.set(index, taui);
126
127 // p[index][select] = (tau[index][select] * alpha) + (eta[index][select] * beta);
128 List sIndex = numeratorP.get(index);
129 sIndex.set(select, (tau.get(index).get(select) * alpha) + (eta.get(index).get(select) * beta));
130 numeratorP.set(index, sIndex);
131 denominatorP.set(index, denominatorP.get(index) + numeratorP.get(index).get(select));
132 }
133 }
134
135 numAssignments++;
136 return currentSolution;
137 }
138 }