Seminar MARA – UP Famnit

V ponedeljek, 13. avgusta 2012, bo ob 16.00 uri v prostorih Fakultete za matematiko, naravoslovje in informacijske tehnologije Univerze na Primorskem, Glagoljaška 8, Koper predavanje v okviru skupnega SEMINARJA ZA MATEMATIČNE IN RAČUNALNIŠKE ZNANOSTI Oddelka za matematiko in Oddelka za Informacijske znanosti in tehnologije UP FAMNIT, Oddelka za matematiko in Oddelka za Informacijske znanosti in tehnologije UP IAM, Oddelka za matematiko in računalništvo UP PEF ter Oddelkov za matematiko in teoretično računalništvo IMFM.

RAČUNALNIŠKI SEMINAR

Prostor: FAMNIT-1-RU1 ob 16:00

Pradavatelj: Milan Djordjevic

Naslov: GRAFTED GENETIC ALGORITHM AND THE TRAVELING VISITOR PROBLEM

Abstract:

In this presentation, two related topics from theoretical computer science are considered.The first one considers Grafted Genetic Algorithms. The presentation analyzes separate, combined and partial performance of local searcher and genetic algorithm. On the Traveling Salesman Problem we examine the impact of hybridization a 2-opt heuristic based local searcher into the genetic algorithm. Genetic algorithm provides a diversification, while 2-opt improves intensification. Results on examples from TSPLIB show that this method combines good qualities from both methods applied and outperform each individual method. In tests we applied hybridization at various percentages of genetic algorithm iterations. On one side the less frequent application of hybridization decreased the average running time of the algorithm from 14.62 sec to 2.78 sec at 100% and 10% hybridization respectively, while on the other side the quality of solution on average deteriorated only from 0.21% till 1.40% worse than the optimal solution. We also studied at which iterations of the genetic algorithm to apply the hybridization. We applied it at random iterations, at the initial iterations, and the ending ones where the later proved to be the best.

The second topic considers the Traveling Visitor Problem. We consider the problem where visitors start from a hotel with desire to visit all interesting sites in a city exactly once and to come back to the hotel. Since, the visitors use streets and pedestrian zones, the goal is to minimize the visitor’s traveling distance. This problem is similar to the Traveling Salesman Problem. The difference is that during visit, traveling visitors cannot fly over buildings in the city. Instead, they have to go around these obstacles. That means that all shortest distances, like those in Euclidean Traveling Salesman Problem, are not valid in this case. The tested benchmarks used come from three real instances made using tourist maps of cities of Venice, Belgrade and Koper and two modified instances from TSPLIB. We introduced and compared two methods for solving the Traveling Visitor Problem. In all tested cases, the Koper Algorithm

outperforms the Naive Algorithm for solving the Traveling Visitor Problem – quality of solutions differs from 6.52% to 354.46%.

Vabljeni!