Transcript Dynamic programming with the ant colony metaheuristic for

optimization of combinatorial problems
with parallel hybrid evolutionary algorithms
Tansel Dökeroğlu, Ph.D.
July, 2015
Content
• Problem definition
• Metahueristics
• Genetic Algorithms and Tabu Search
• Parallel Algorithms and Message Passing Interface
• Proposed Parallel Hybrid Algorithm
• Experimental Setup and Results
• Conclusion and Future Work
Problem Definition
Combinatorial optimization is an area of research at the
intersection of computer science, applied mathematics, and
operations research.
The most widely studied problems of this area are:
•
•
•
•
•
The Traveling Salesman
Bin Packing
Data Allocation
The Facility Layout Problem
Quadratic Assignment Problem
The Quadratic Assignment Problem (QAP)
2
1
Factory 2
Factory 1
3
4
Factory 4
Factory 3
This assignment can be written as a permutation such that p={2,1,4,3}.
The exact solution of the QAP problem for size 35 is peformed with
hundreds of processors by working for months.
Large QAP instances are still optimally unsolvable.
Formal Definition of the QAP
NP-Hard problems and metaheuristics
Genetic Algorithms
Generations
(iterations)
Crossover and Mutation Operators
Generations :
Tabu Search Algorithm
• A neighborhood is constructed to identify adjacent solutions
that can be reached from current solution.
• Classifies a subset of the moves as forbidden (or tabu).
• The classification depends on the history of the search, and
particularly on the frequency that certain move or solution
components, called attributes, have participated in generating
past solutions.
• With an attractive evaluation where it would result in a solution
better than any visited so far, its tabu classification may be
overridden, aspiration criterion.
10
Parameters of Tabu Search
•
•
•
•
•
•
•
Neighborhood structure
Local search procedure
Aspiration conditions
Form of tabu moves
Addition of a tabu move
Maximum size of tabu list
Number of failures
11
Why do we need parallel programs?
(from the perspective of Moore’s law)
the # of transistors in an integrated circuit has doubled every two years
Message Passing Interface
Message Passing Interface (MPI) is a standard and portable messagepassing system designed to function on a wide variety of parallel
computers.
There are several well-tested and efficient implementations of MPI which
are portable and scalable for large-scale parallel applications.
The standard defines the syntax and semantics of a core of library
routines useful to a wide range of users writing portable message-passing
programs in different computer programming languages such as Fortran,
C, C++ and Java.
The communication topology of the proposed algorithm
Proposed Algorithm
Genetic Algorithm Phase
migrate individuals
Global best
Master Node
(at each slave processor)
population
Robust Tabu Engine
(at each slave processor)
best individual
Experimental Setup and Performance Evaluation
QAP Benchmark Instances
http://www.opt.math.tu-graz.ac.at/qaplib/inst.html
There exist problem instances having size 12 ≤ n ≤ 256
136 problem instances and 111 solutions
46 nodes,
each with two CPUs, giving 92 CPUs.
Intel Xeon 5110 Dual-Core CPU
(1.60 GHz, 4 MB L2 Cache, 1066 MHz FSB)
Each CPU has four cores
gıvıng a total number of 368 processors.
Each node has 16 GB of RAM
giving 736 GB of total memory
high-bandwidth communication among the HPC nodes,
Gigabit Ethernet Switches, and Infiniband switch.
Setting parameters for # of individuals and generations
in order to prevent stagnation to local optima
Parameters settings for Tabu Search Algorithm Phase
For small problem instances, the small parameter settings are used,
while the larger parameter settings are used for harder/larger problems
improvement of the solution quality of
as the number of generations, populations, and processors are increased
Comparing the results
with the state-of-the-art parallel algorithms
Conclusion
• A robust algorithm is developed with 0.049 % error deviation
for hard/large problem instances of the QAP.
• A wider fitness landscape analysis is enabled with parallel
computation for the QAP.
• Execution time of the proposed algorithm is reasonable (it can
find (near-) optimal solutions in minutes rather than days or
months).
• The proposed algorithm is reported to be among the best
performing ones in the literature.
• The hybridization of metaheuristics is proved to be an efficient
approach for the solution of the QAP.
Future work
• Enhancing with machine learning techniques such as reinforcement
learning.
• Hyper-heuristics that execute several heuristics on the problem will be
implemented .
• Migrating the existing code to CUDA platform. A more cost-effective
way of solution.
CUDA is a parallel computing platform and programming model that
enables dramatic increases in computing performance by harnessing the
power of the graphics processing unit (GPU).
GeForce GTX 760: A Mid-Range GPU with 1152 CUDA cores
Journal papers
•
Dokeroglu T., (2015) Hybrid teaching-learning-based optimization algorithms for the Quadratic
Assignment Problem, Computers and Industrial Engineering. 85 (2015): 86-101.
•
Dokeroglu T., Bayir M.A., Coşar A., (2015) Robust algorithms for exploiting the common tasks of
relational cloud databases, Applied Soft Computing, Vol 30 : 72-82.
•
Dokeroglu, Tansel, and Ahmet Cosar. (2014) Optimization of one-dimensional Bin Packing
Problem with island parallel grouping genetic algorithms. Computers & Industrial Engineering
75 (2014): 176-186.
•
Dokeroglu, T., Sert, S.A., and Cinar, M.S. (2014) Evolutionary multiobjective query workload
optimization of Cloud data warehouses, The Scientific World Journal.
•
Tosun, U., Dokeroglu, T., & Cosar, A. (2013). A robust island parallel genetic algorithm for the
quadratic assignment problem. International Journal of Production Research, 51(14), 41174133.
•
Dokeroglu, T., Ozal, S., Bayir, M. A., Cinar, M. S., & Cosar, A. (2014). Improving the performance
of Hadoop Hive by sharing scan and computation tasks. Journal of Cloud Computing, 3(1), 1-11.
Proceeding papers
•
•
•
•
•
•
•
Dokeroglu, T., Cosar, A. (2014), "Integer Linear Programming Solution Model for the Multiple
Query Optimization Problem" ISCIS October 27-28th, 2014, Krakow, Poland.
Dokeroglu, T., Sert, S.A., Cinar, M.S., and Cosar, A. (2014). Designing Cloud Data Warehouses
using Multiobjective Evolutionary Algorithms, ACM International Conference on Agents and
Artificial Intelligence (ICAART) Eseo, Angers, Loire Valley, France.
Dokeroglu, T. (supervised by Ahmet Cosar) (2012). Parallel Genetic Algorithms for the
Optimization of Multi-Way Chain Join Queries of Distributed Databases 38th VLDB Ph.D.
Workshop, August 27-31, Istanbul/TURKEY.
Dokeroglu, T., Tosun, U., and Cosar, A. (2012). Particle Swarm Intelligence as a Novel Heuristic
for the Optimization of Distributed Database Queries, The 6th International Conference on
Application of Information and Communication Technologies AICT2012 Georgia, Tbilisi, 17-19 .
Dokeroglu, T and Cosar, A. (2011). Dynamic Programming with Ant Colony Optimization
Metaheuristic for The Optimization of Distributed Database Queries, Proceedings of the 26th
ISCIS, London, UK.
Dokeroglu,T., Tosun, U., and Cosar, A. (2013). Evaluating the Performance of Recombination
Operators with Island Parallel Genetic Algorithms, International Federation of Automatic
Control (IFAC), Saint Petersburg, Russia.
Dokeroglu, T. Tosun, U., and Cosar, A. (2012). Parallel Optimization with Mutation Operator for
the Quadratic Assignment Problem Proceedings of WIVACE, Italian Workshop on Artificial Life
and Evolutionary Computation, Parma/Italy.
Thank You