Milan Djordjević - doktorat

%%%%%%%%%%%%%%%%%%%% author.tex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%

% sample root file for your "contribution" to a contributed volume

%

% Use this file as a template for your own input.

%

%%%%%%%%%%%%%%%% Springer %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% RECOMMENDED %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass{llncs}

\usepackage{makeidx}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{epsfig}

\usepackage{algorithm}

\usepackage{algpseudocode}

\begin{document}

\frontmatter

\pagestyle{headings}  % switches on printing of running heads

\mainmatter              % start of the contributions

\title{Performance Analysis of Partial Use of Local Optimisation Operator on Genetic Algorithm for TSP}

\titlerunning{Performance Analysis of Partial Use of Local Search and Genetic Algorithm}

% Use \titlerunning{Short Title} for an abbreviated version of

% your contribution title if the original one is too long

\author{Milan Djordjevic \and Andrej Brodnik \and Marko Grgurovic}

% Use \authorrunning{Short Title} for an abbreviated version of

% your contribution title if the original one is too long

\institute{Department of Information Science and Technology\\University of Primorska, Koper, Slovenia\\

\email{milan.djordjevic@student.upr.si}, \email{andrej.brodnik@upr.si}, \email{marko.grgurovic@student.upr.si}}

%

% Use the package "url.sty" to avoid

% problems with special characters

% used in your e-mail or web address

%

\maketitle

\abstract{The paper analyzes separate, combined and partial performance of local searcher and genetic algorithm.

%We propose a strategy to graft a 2-opt local searcher into a genetic algorithm, after recombination, to optimize each offspring`s genomes.

On the well studied Euclidean \textit{Travelling Salesman Problem} we examine the impact of grafting a \textit{2-opt} heuristic based local searcher into the genetic algorithm for solving the Euclidean Travelling Salesman Problem.

%Standard genetic algorithms are known to be rather slow, while 2-opt search applied to the Travelling Salesman Problem quickly gives results that are far from optimal.

Genetic algorithm provides a diversification, while 2-opt improves intensification. Results on examples from \textit{TSPLIB} show that this method combines good qualities from both methods applied and significantly outperforms each individual method. The experiment extension demonstrate a third generation testing on hybrid genetic algorithms where an influence of partial grafting a 2-opt local searcher into genetic algorithm was tested.}

\section{Introduction}

\label{sec:1}

Genetic Algorithms (GA) use some mechanisms inspired by biological evolution \cite{holland75}. They are applied on a finite set of individuals called population. Each individual in a population represents one of the feasible solutions of the search space. Mapping between genetic codes and the search space is called encoding and can be binary or over some alphabet of higher cardinality. Good choice of encoding is a basic condition for successful application of a genetic algorithm. Each individual in the population is assigned a value called fitness. Fitness represents a relative indicator of quality of an individual compared to other individuals in the population. Selection operator chooses individuals from the current population and takes the ones that are transferred to the next generation. Thereby, individuals with better fitness are more likely to survive in the population`s next generation. The recombination operator combines parts of genetic code of the individuals (parents) into codes of new individuals (offsprings).

%Such a mixing of genetic material enables that well-fitted individuals or their relatively good genes give even better offspring. By a successive application of selection and crossover, the diversity of genetic material can be decreased which leads to a premature convergence in a local optimum which may be far from a global one.

The components of the genetic algorithm software system are: Genotype, Fitness function, Recombinator, Selector, Mater, Replacer, Terminator, and in our system a Local searcher which is new extended component.

%The  basic  step  of  2-opt  is  delete  two  edges  from  a  tour  and  reconnect the remaining  fragments of  the  tour by adding  two new edges.

%Once we choose the two edges to delete, we do not have a choice about which edges to add there is only one way to add new edges that results in a valid tour.

%The 2-opt algorithm repeatedly looks for 2-opt moves that decrease the cost of the tour. A 2-opt move decreases the cost of a tour when the sum of the lengths of the two deleted edges is greater than the sum of the lengths of the two new replaced edges. A 2-opt move  is  the  same as  inverting a  subsequence of  cities  in  the  tour.

%\medskip

%\noindent

%{\it Here is a pseudo code for the 2-opt local search algorithm:}

%\begin{verbatim}

%current_tour := create_random_initial_tour()

%repeat

  %  modified_tour := apply_2opt_move(current_tour)

   % if length(modified_tour) < length(current_tour)

%then current_tour := modified_tour

%until no further improvement or a specified number of iterations

%\end{verbatim}

In this paper we study a well defined problem of a Traveling Salesman Problem (TSP). In the TSP a set $ \left\{C_{1}, C_{2}, ... C_{N}\right\}$ of cities is considered and for each pair $\left\{{C_{i},C_{j}}\right\}$ of distinct cities a distance $d(C_{i},C_{j})$ is given. The goal is to find an ordering $\pi$ of the cities that minimizes the quantity

\begin{equation}

  \sum^{N-1}_{i=1}d(C_{\pi(i)} , C_{\pi(i+1)} ) + d(C_{\pi(N)} , C_{\pi(1)}).

\end{equation}

This quantity is referred to as the tour length since it is the length of the tour a salesman would make when visiting the cities in the order specified by the permutation, returning at the end to the initial city. We will concentrate in this paper on the symmetric TSP in which the distances satisfy $d(C_{i}, C_{j})=d(C_{j},C_{i} )$ for $1 \leq i,j \leq N$ and more specificaly to the Euclidean distance. While the TSP is known to be \textit{NP-hard} \cite{garey79} even under substantial restrictions, the case with Euclidean distance is well researched and there are many excellent algorithms which perform well even on very large cases \cite{garey79}.

%Genetic algorithms have been successfully applied to the TSP, but for restricted versions of the TSP, such as one with the Euclidean distance, they are very slow in convergence and more efficient methods are known ~\cite{freisleben96}.

The 2-opt is a simple local search algorithm for the TSP. The main idea behind it is to take a route that crosses itself and reorder it so that it does not cross itself any more. The 2-opt local search will be used to hybridize GA metaheuristic to solve TSP. Although the 2-opt algorithm \cite{engels09} performs well and can be applied to Traveling Salesman Problems with many cities, it finds only a local minimum. The nearest neighbour algorithm \cite{hoos05} is one of the most intuitive heuristic algorithms for the TSP. It's a greedy method for solving the TSP.

The genetic algorithm considered in this paper are hybrid genetic algorithms, incorporating local search which have been referred to as Memetic Algorithms (MA) \cite{merz01}. One example of hybridisation of genetic algorithms is shown in \cite{sels11}

%~\cite{krasnogor05},

\section{Grafted GA for the TSP}

\label{sec:2}

% Always give a unique label

% and use \ref{<label>} for cross-references

% and \cite{<label>} for bibliographic references

% use \sectionmark{}

% to alter or adjust the section heading in the running head

%Grafted genetic algorithm.

Grafting in botanic is when the tissues of one plant are affixed to the tissues of another.

%To speed maturity of hybrids in fruit tree breeding programs, hybrid seedlings may take ten or more years to flower and fruit on their own roots.

Grafting can reduce the time to flowering and shorten the breeding program.

Local Searcher is an extension of the conventional genetic algorithm as it does not need to make use of genetic components. It facilitates the optimization of individual genomes outside the evolution process. There are many implementations of local searchers \cite{freisleben96}, some even in hardware \cite{hoos05}.

In our algorithm, the pseudocode can be seen in Algorithm \ref{alg:gga}, after the recombination has been applied (line 7 in the pseudocode), a Local Searcher is used to optimize every single offspring genome (line 8 in the pseudocode). Because of the usage of such external optimizer the genetic algorithm is no longer $pure$ and therefore we speak of a grafted genetic algorithm \cite{djordjevic08,djordjevic09}. This form of optimization is of a local kind. It alters the genome by heuristically changing the solution. %When approximating a TSP instance, a 2-opt local optimization technique is applied to make modifications to a genome so as to create better genomes at a higher rate. These are much desired because the evolution process can be quite slow with respect to the desired results. Furthermore  it has always been the case in optimization that incorporating problem specific knowledge (not only through local optimizations, but also in defining the evolutionary operators) is required to gain better results.

%A genome represents a potential solution to a problem. How the solution information is coded within a genome is determined by the genotype. TSP Numbered List is a representation of a tour in the TSP by means of a list in which the locations are identified by numbers.

Edge map crossover \cite{freisleben96} is an implementation of the recombination operator (line 7 in the Algorithm \ref{alg:gga}). It makes use of a so called edge map.

%Edge map is a table in which each location is placed. For each location there is a list in which the neighbouring locations are listed with this location. Recombination is then established as follows:

%\medskip

%\noindent

%{\it Here is a pseudcode for the 2-opt local search algorithm:}

%\begin{verbatim}

%1.	Choose the first location of one of both parents

  %          to be the current location.

%2.	Remove the current location from the edge map

  %          lists.

%3.	If the current location still has remaining edges,

 %           go to step 4, otherwise go to step 5.

%4.	Choose the new current location from the edge

%            map lists of the current location as the one with

 %           the shortest edge map list.

%5.	If there are remaining locations, choose the one

%            with the shortest edge map list to be the current

 %           location and return to step 2.

%Example:

%Parents: 1-2-3-4-5-6; 2-4-3-1-5-6

%Edge map: 1) 2 6 3 5;  2) 1 3 4 6;  3) 2 4 1;

         %  4) 3 5 2;     5) 4 6 1;     6) 1 5 2 6

%1.	Random choice: 2.

%2.	Next candidates: 1 3 4 6, choose from 3 4 6

%            (same #edges), choose 3.

%3.	Next candidates: 1 4 (edge list 4 < edge list 1),

 %           choose 4.

%4.	Next candidate: 5, choose 5.

%5.	Next candidate:  1 6 (tie breaking) choose 1

%6.	Next candidate; 6, choose 6.

%Offspring: 2-3-4-5-1-6

%\end{verbatim}

Distance preserving crossover \cite{helsgaun00} is another implementation of the recombination operator (line 7 in the Algorithm \ref{alg:gga}). It attempts to create a new tour with the same distance to both parents.

%In order to establish this, the content of the first parent is copied to the offspring and all edges that do not occur in the second parent are removed. The resulting fragments are reconnected without making use of non-overlapping edges of the parents. If edge $(i, j)$ has been destroyed, the nearest available neighbor $k$ of $i$ from the remaining fragments, is selected and the edge $(i, k)$ is added to the tour

%\medskip

%\noindent

%{\it Here is a pseudcode for the 2-opt local search algorithm:}

%\begin{verbatim}

%Example:  Parents: 5-3-9-1-2-8-0-6-7-4; 1-2-5-3-9-4-8-6-0-7

%Fragments: 5-3-9|1-2|8|0-6|7|4

%Offspring: 6-0-5-3-9-8-7-2-1-4

%\end{verbatim}

%

%Tournament Selector places groups of genomes from the population together, creating the groups from top to bottom with respect to the enumerative ordering of the genomes in the population and selects the best of the genomes within this group. This is repeated until the required amount of genomes is selected. The selection size is 400, and tournament size is 2. The Random Mater is a simple way of mating parents. It mates the parents as enumerated in the population at random using the mating size to create groups until no more groups can be created. The grouping size is 2. The new offspring only replacer is the implementation of the classical replacement strategy that simply only allows the offspring to survive. Thus the genomes from the next generation replace the entire current population. The equality terminator for all equal genomes  implements the termination condition specifying that the genetic algorithm should terminate when all genomes in the population are identical-all equal genomes.

The local learcher is an extension to the conventional genetic algorithm as it needs not make use of genetic operators. It facilitates the optimization of individual genomes outside the evolution process.

%After the Recombination has been applied, a Local Searcher is used to optimize every single offspring genome.

The Local Searcher has no further knowledge on the execution of the genetic algorithm in the larger setting. The system will provide it with the genome it needs to locally optimize when needed.

\medskip

\begin{algorithm}

\caption{Pseudocode}

\label{alg:gga}

\begin{algorithmic}[1]

%\Procedure{Euclid}{$a,b$}\Comment{The g.c.d. of a and b}

\State $t=0$

\State {{initialize} $(P(t))$}

\State {{evaluate} $(P(t))$}

\While{{not terminate} $(P(t))$}

\State{$sel$ = {select} $(P(t))$}

\State{$mat$ = {mate} $(sel)$}

\State{$rec$ = for each mated collection $m \in mat$

                      do recombination$(r)$}

\State{$loc$ = for each genome $g$ in each recombined

               collection $r \in rec$ do local search}

\State{$rep$ = replace($loc$, $P(t)$)}

\State{$P(t+1)$ = select$(rep)$}

\State{evaluate {$(P(t+1))$}}

\State{$t=t+1$}

\EndWhile

%\While{$r\not=0$}\Comment{We have the answer if r is 0}

%\State $a\gets b$

%\State $b\gets r$

%\State $r\gets a\bmod b$

%\EndWhile\label{euclidendwhile}

%\State \textbf{return} $b$\Comment{The gcd is b}

%\EndProcedure

\end{algorithmic}

\end{algorithm}

%\noindent

%{\it Here is a pseudo code for the algorithm:}

%\begin{verbatim}

%t=0

%initialize(P(t))

%evaluate(P(t))

%while(not terminate(P(t))) do

 %  sel = select(P(t))

  % mat = mate(sel)

   %rec = for each mated collection m belongs to mat do

    %     recombination(r)

   %loc = for each genome g in each recombined collection

    %     r belongs to rec do local search(l)

   %rep = replace(loc, P(t))

   %P(t+1) = select(rep)

   %evaluate(P(t+1))

   %t=t+1

%\end{verbatim}

The 2-opt local searcher is a local optimizer for the TSP that has been grafted into the standard genetic algorithm (line 8 in the Algorithm \ref{alg:gga}). This local optimizer performs the 2-opt heuristic that exchanges edges to reduce the length of a tour. An exchange step consists of removing two edges from the current tour and reconnecting the resulting two paths in the best possible way Fig. \ref{fig:example}.

\begin{figure}[b]

\centering

\includegraphics[height=3.6cm]{2opt.eps}

\caption{Exchange step of 2-opt algorithm}

\label{fig:example}

\end{figure}

Following experiments demonstrate a third generation testing on hybrid genetic algorithms.

In the extension of an experiment an influence of partial grafting a 2-opt local searcher into genetic algorithm was tested. In the conducted experiments we will present an influence of grafting GA with local search and we will perform a performance analysis of partial use of local optimisation operator on GA for TSP. Furthermore, we will answer the questions of how often to graft a GA and when.

\section{Experiment}

\label{sec:3}

\begin{table}

%\sidecaption[t]

\centering

\caption{Five techniques for solving Euclidean TSP}

%\vspace{7.8cm}

\includegraphics[height=6.8cm]{tabela}

\label{fig:Table 1}

\end{table}

For testing our strategy and comparing it to other solutions we used the instances of symmetric traveling salesman problem which can be found on TSPLIB. We deliberately used well known problem (TSP) and relatively small instances for which best solutions are known since the goal of this research is not to find a better algorithm for the symmetric TSP, but rather to compare on a controlled environment the impact of grafting a genetic algorithm.  Altogether 20 instances have been tried out, with different complexity and range from 14 to 150 cities per instance, look in Table \ref{fig:Table 1}.

We compared our method (grafted genetic algorithm (GGA)), separately in one case with edge map crossover (GGAemc) and in another case with a distance preserving crossover (GGAdpc) with four other methods. As the upper bound for the quality of solution we used the above mentioned Greedy Heuristic. For the lower bound for the quality of solution we used exact solutions, global minima, obtained by Concorde \cite{applegate01}.  Then we compared our grafted method with a pure 2-opt algorithm and pure genetic algorithm.

For Greedy Heuristic and the pure 2-opt Heuristic the running time is in a range from 0.5 to 1.5 seconds.

%U nastavku eksperimenta smo testirali parcijalni uticaj cepljenja 2 opt algoritma i genetskog algoritma. Odnosno, kada lokalni searcher povremeno implementiramo u 10, 20, 40, 50, 80 i 90 \% od ukupnog broja generacija rada algoritma.

%GGAemc i GGAdpc su algoritmi sa 100 \% korišćenja lokalnog searchera u celokupnom radu algoritma.

%Ovo testiranje je izvršeno na najvećoj instanci sa oznakom ch150.

%Broj generacija rada algoritma sa parcijalnim korišćenjem 2 opt algoritma je ograničen na broj generacija adekvatnog cepljenog genetskog algoritma sa 100 \% učestalosti.

%Što znači da za instancu ch150 termination condition iznosi tačno 88 i 82 generacija respectively for GGAemc and GGAdpc.

%Sa ovim kriterijumom terminacije garantujemo da će vreme rada parcijalnog GGA biti manje nego rad adekvatnog GGA sa 100 \% korišćenja loaklnog searchera.

%U varijantama sa 40, 50, 80 \% učestalosti, smo testirali različite preraspodele generacija rada sa lokalnim searcherom, i to uniformly, na početku i na kraju.

%Sve instance problema su zatim testirane sa 90 \% učestalosti rada lokalnog searchera u adekvatnom Graftovanom genetskom algoritmu.

In experiment extension a local searcher is periodically implemented with  10, 20, 30, 40, 50, 60, 70, 80 and 90\% frequency.

In all cases three different independent distributions of generations with local searcher were used: random, beginning sequence and ending sequence. Random variations means that use of local searcher is with adequate probability distributed in iterations of the algorithm. Begin sequence means that a sequence of iterations with local searcher is used in the first generations of an algorithm. While in the ending it is used on the last generations of the algorithm.

%The pseudocode of the Partial Grafted Genetic Algorithm is given in Algorithm 2. The $W$ stands for a set of iterations with local searcher involved.

The total number of iterations are limited to the number of iterations reached in grafted genetic algorithm with edge map recombination (GGAemc).

The extension of an experiment include testing on a 10 largest instances from the Table \ref{fig:Table 1} plus instance pr439. The results presents average values of 5 runs for each tested method.

All experiments were conducted on a computer with Pentium(R) 2.8 GHz CPU, with Windows 7. Furthemore, a development environment the \textit{EA Visualizer} \cite{bosman99}, an application written in \textit{Java} programming language, was used. The Concorde's code is written in the \textit{AnsiC} programming language. Therefore, in this research absolute times were not of crucial importance, we were only interested in relative performance of tested algorithms.

%\begin{table}

%%\sidecaption[t]

%\centering

%\caption{Three different variations of the algorithm with 50\% frequency of Local Searcher}

%%\vspace{5.8cm}

%\includegraphics[height=5.0cm]{tabela50}

%\label{fig:Table50}

%\end{table}

\section{Results}

\label{sec:4}

The results of an experiment are summarized in Table \ref{fig:Table 1}. Twenty cases from the well known TSPLIB were used for testing. The names of these cases are in the first column and the name always contains the size of the problem, i.e. the number of cities (which are between 14 and 150).

The last two columns are exact solutions (global minima) obtained by Concorde \cite{applegate01}, together with execution times. A well known problem with moderate sized examples and tools to get optimal solutions were selected, recall that a goal of this research is not to improve solutions for difficult problems but to compare and quantitatively examine  the effects of grafting local searches (in this case 2-opt based) to standard genetic algorithm. Such knowledge can be used to fine tune and calibrate a hybrid system which can then be used on large cases. These last two columns are used as a reference for all other tests.

The second column in Table \ref{fig:Table 1} represents lower bound for the quality of solution. It is a simple nearest neighbour heuristic. It is fast, but very unsophisticated and any reasonable algorithm should do better than that. This greedy heuristic gives results that are about 15 \% (except for some very small cases) worse than the optimal solution. The column titled quality shows by how many percent is the solution produced by this algorithm worse than the optimal solution. 0 \% in this column means  algorithm found the best solution. The running times of the algorithm are from 0.2 to 2.3 in seconds.

The third column in the Table \ref{fig:Table 1} corresponds to the pure 2-opt algorithm. As expected, it also gives quick but far from optimal solutions. It quickly finds a local minimum, but it is unable to broaden the search to find another local minimum. However, 2-opt algorithm is superior to greedy algorithm, the quality of the solution, with the similar running times from 0.2 to 2.5 seconds, is on average about 8 \% worse than optimal.

The fourth column in the Table \ref{fig:Table 1} corresponds to the pure Genetic Algorithm. The running time, as expected, is significantly increased. While our GGA algorithm reached optimal solution below one second or few seconds (0.6 to 15.3 seconds), the running time for pure genetic algorithm was from 3.4 seconds to 100 seconds which was time-limit. In 12 out of 20 cases no optimal solution was found within that time limit, but in 8 cases an optimal solution was found and the middle column indicates in which generation that happened. For 12 cases where optimal solution was not found, the quality of found solution is expressed as for previous cases in percents above the optimal solution.

The sixth column in Table \ref{fig:Table 1} describes results obtained by our grafted algorithm, which is programmed with edge map crossover as recombination operator (GGAemc). In 17 out of 20 considered cases an optimal solution was found. Remaining three instances differ from optimal solution in 0.01, 0.10 and 0.22 percent. The solutions were found in relatively few generations and very fast. Execution times were 0.6 to 15.2 seconds.

The seventh column in Table \ref{fig:Table 1} corresponds to our grafted genetic algorithm which contains a distance preserving crossover as recombination operator (GGAdpc). In 11 out of 20 considered cases an optimal solution was found. In remained 9 cases, delivered solutions differ from optimal in range from 0.13 to 0.32 percent. The running time and number of generations of GGAdpc, in comparison with GGAemc, are slightly lesser, particularly in the lowermost part of the table which represents more complex instances. Quantitative results on test cases from \textit{TSPLIB} show that grafted algorithms, GGAemc and GGAdpc, have advantages. Even when their's components have serious drawbacks, their grafted combinations exhibits a very good behaviour. Results on examples from \textit{TSPLIB} show that this grafted method combines good qualities from both methods applied and significantly outperforms each individual method.

%The difference in the quality on the other side is in the hand of GGAemc for the same considered cases.

%Poenta eksperimenta predstavljenog u tabeli 1 je fino izkalibrirati sistem na manjim instancama da bi uspešno rešili veće. U nastavku odnosno nadogradnji eksperimenta u testiranju parcijalnog korišćenja ekstenzije lokalnog serchera na genetski algoritam, sistem kalibriramo upravo na najvećoj instanci iz tabele 1, zbog toga jer je u instanci ch150 najduža evolucija odnosno broj generacija algoritma, zatim najveće je vreme rada algoritma i najveća je razlika u kvalitetu dobijenog rešenja.

%\begin{algorithm}

%\caption{Pseudocode}\label{}

%\begin{algorithmic}[]

%%\Procedure{Euclid}{$a,b$}\Comment{The g.c.d. of a and b}

	%\State $t=0$

	%\State {{initialize} $(P(t))$}

	%\State {{evaluate} $(P(t))$}

	%\While{{not terminate} $(P(t))$}

	%\State{$sel$ = {select} $(P(t))$}

	%\State{$mat$ = {mate} $(sel)$}

	%\State{$rec$ = for each mated collection $m \in mat$

												%do recombination$(r)$}

	%\If {{$t \in W$}}

	%%\State $loc$ = $\bigcup_{g \in rec} LocalSearch(g)$

		%

	%\State{$loc$ = for each genome $g$ in each recombined

								 %collection $r \in rec$ do local search}

	%\EndIf

	%\State{$rep$ = replace($loc$, $P(t)$)}

	%\State{$P(t+1)$ = select$(rep)$}

	%\State{evaluate {$(P(t+1))$}}

	%\State{$t=t+1$}

	%\EndWhile

%%\EndProcedure

%\end{algorithmic}

%\end{algorithm}

\begin{table}

%\sidecaption[t]

\centering

\caption{Partial Grafting of a Genetic Algorithm}

%\vspace{4.8cm}

\includegraphics[height=11.5cm,angle=90]{tabela_partial_gga5}

\label{fig:Tablesve}

\end{table}

The results of experiment extension are summarized in Table \ref{fig:Tablesve} and in Figures \ref{fig:example2}, \ref{fig:example3} and \ref{fig:example4}.

%The Table \ref{fig:Table50} describes results of 50\% frequancy use of local searcher. The results achieved by \textit{uniform} use of an algorithm show us results which vary from 0.0\% to 1.04\% from optimal, while running times vary from 6.1 to 14.6 seconds. In the second setting of an algorithm, named \textit{begin}, a little better results was achieved. The quality of solutions vary from 0.0 to 0.89\% from optimal, while the running times are the same. The best performance, of all three settings with 50\% use of local searcher, was achieved in the \textit{end} configuration. In two cases an optimal solutions was found, remaining instances differ from optimal solution in a range from 0.03 to 0.77\%. The running time vary from 6.1 to 14.6 seconds, which is the same as in \textit{begin} and \textit{uniform} configuration.

%The Table \ref{fig:Tablesve} describe results of pure genetic algorithm (GAemc), variations of algorithms with 10, 20, 30, 40, 50, 60, 70, 80 and 90 percent frequency, and grafted genetic algorithm (GGAemc). The variations with 20, 30, and 40 precent frequency has an uniform distribution of iterations with local search. Furthermore, the variations with 60, 70, 80 and 90 percent frequency has and ending sequence distrubition.

%For the lower bound for the quality of solution we used solutions obtained by GGA with edge map crossover as a recombination operator.

The first column in Table \ref{fig:Tablesve} corresponds to the names of instances and the size of the problem (which are between 76 and 439) which are duplicated for better visualization of the table.

The second column in the Table \ref{fig:Tablesve} presents the result of the pure Genetic Algorithm and grafted Genetic Algorithm, both with edge map crossover as recombination operator (GAemc and GGAemc). This algorithms contain 0\% and 100\% frequency of local search, respectively. The \textit{q} in Table \ref{fig:Tablesve} stands for \textit{quality} differ from optimal solution. The \textit{t} stands for running time.

The third column in Table \ref{fig:Tablesve} represents results for 10\% and 90\% frequency. The subcolumn titles \textit{rnd, begin, end} stands for three variations of partial hybridization, random, begin sequence and end sequence, respectively. The result for 10\% frequency shows that this kind of algorithm settings is fast (the time vary from 0.9 seconds to 11.0 seconds), but the quality of solution (which vary from 0.34\% to 4.92\%), are weak.

The best performance of all tested cases was achieved in the configuration with 90\% frequency, especially in variation with end sequence, with results coloured in red. In 9 out of 11 tested instances the results was the same as for GGAemc. For instance (kroB100) result was better in 0.01\%, and for instance pr439 a result is worse in 0.04\%. Furthermore, the solutions provided by, 90\% end sequnce variations, were found faster then by GGAemc. The running time vary from 3.3 to 78.9 seconds, compared to the time achieved by GGAemc, which vary from 3.6 to 91.8 seconds. This mean, that the {\em same quality} of result was achieved in {\em shorter time}.

The results for instance pr439 can be seen in Figure \ref{fig:example2}.

In 95\% of all tested cases, (look in columns from 3 to 7 in Table \ref{fig:Tablesve}) the best performance was achieved in variation with end sequence.

Additionally, the results of end sequence for all instances can be seen in Figure \ref{fig:example4}.

In all three variations of hybridization (random, begin and end) the running time is the same for particular frequency. For all tested instances the running time grows almost linerly with regard to percent of hybridization, see Figure \ref{fig:example3}.

%The fourth column in Table \ref{fig:Tablesve} presents result for grafted algorithm with 20\% frequency use of local searcher. This kind of settings also gives quick but far from optimal solutions. A running times vary from 5.4 to 12.7 seconds, and a quality of solutions is in the range from 0.46 to 1.98\% diference from optimal solutions.

%Fifth, sixth, seventh, eight and ninth column in Table \ref{fig:Tablesve} represents result of configurations with 30, 40, 60, 70 and 80 percent frequency use of local search, respectively.

\begin{figure}%[b]

\centering

\includegraphics[height=5.8cm]{pr439.eps}

\caption{Results for pr439}

\label{fig:example2}

\end{figure}

\begin{figure}%[b]

\centering

\includegraphics[height=5.6cm]{time.eps}

\caption{Running times}

\label{fig:example3}

\end{figure}

\begin{figure}%[b]

\centering

\includegraphics[height=7.6cm]{end.eps}

\caption{Results for end sequence}

\label{fig:example4}

\end{figure}

\section{Conclusions}

\label{sec:5}

The goal of this paper was to investigate influence of grafting a 2-opt based local searcher into the standard genetic algorithm, for solving the Travelling Salesman Problem with Euclidean distance. It is known that genetic algorithms are very successful when implemented for many NP-hard problems. However, they are much more effective if some specific knowledge about particular problem is utilized.

%The TSP is well researched problem with many such improvements, especially when the restricted version of the problem with Euclidean distance is considered.

In our first experiment we compared two direct techniques, with our grafted genetic algorithms. Solutions from Concorde and greedy algorithm were added for better comparison. Quantitative results on test cases from \textit{TSPLIB} show that grafted algorithms have advantages. Even when both components have serious drawbacks, their grafted combinations exhibits a very good behaviour. Results on examples from \textit{TSPLIB} show that this method combines good qualities from both methods applied and significantly outperforms each individual method.

%The future research will focus on a new heuristic algorithm for making an initial tour of Lin-Kernighan heuristic, which is known to be one of the most successful heuristics for the TSP.

In the second part of an experiment an influence of partial grafting a 2-opt local searcher into genetic algorithm was studied.

The {\em best performance} was achieved in a configuration with 90\% frequency with end sequence. In a comparison with a performance of GGAemc the {\em same quality} of results was achieved in a {\em shorter time}, on average a 7\% of running time was spared.

The cases with 10\% frequency use of local search provides fast and far from optimal solutions but still better then the GAemc, with small increase in time. The configurations with 50\% frequency use of local searcher present a good examples of trade-off between a running time and quality, especcialy in setting with ending sequence of local searcher.

From the results obtained in Table \ref{fig:Tablesve}, we can conclude that the best gain

%results of tested hybrid genetic algorithms for solving an Euclidean Travelling Salesman Problem

is attained when a local searcher is used in an ending sequence of the algorithm and in frequency not less then 50\% and not more than 90\%.

%Further calibration of this system will include measuring the optimal blend of all components for larger test cases.

There are several issues for future research, such as investigating the effects of a different use of the local optimisation and other metaheuristic algorithms, analyzing the individual performance gains provided by the local search, and to look at how to scale up the algorithm for solving large instances of TSP.

%%%%%%%%%%%%%%%%%%%%%%%% reference %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% sample references

% %

% Use this as a template for your own input.

%

%%%%%%%%%%%%%%%%%%%%%%%% Springer-Verlag %%%%%%%%%%%%%%%%%%%%%%%%%%

%

\begin{thebibliography}{99.}%

% and use \bibitem to create references.

%

% Use the following syntax and markup for your references if

% the subject of your book is from the field

% "Mathematics, Physics, Statistics, Computer Science"

%

% Contribution

\bibitem{applegate01}

Applegate, D., Bixby, R., Chv\'{a}tal, V., Cook, W.: {TSP} cuts which do not

  conform to the template paradigm. In: Computational Combinatorial

  Optimization (2001) 261--304

\bibitem{djordjevic08}

Djordjevic, M.: {Influence of Grafting a Hybrid Searcher Into the Evolutionary

  Algorithm}. In: Proceedings of the Seventeenth International Electrotechnical

  and Computer Science Conference. Slovenian Section IEEE (2008) 115--118

\bibitem{djordjevic09}

Djordjevic, M., Tuba, M., Djordjevic, B.: {Impact of Grafting a 2-opt Algorithm

  Based Local Searcher Into the Genetic Algorithm}. In: Proceedings of the 9th

  WSEAS international conference on Applied informatics and communications. World Scientific and Engineering Academy and Society (WSEAS) (2009) 485--490

\bibitem{bosman99}

Bosman, P., Thierens, D.: {On the modelling of evolutionary algorithms}. In: Proceedings of the Eleventh Belgium-Netherlands Conference on Artificial Intelligence BNAIC (1999) 67--74

\bibitem{engels09}

Engels, C., Manthey, B.: Average-case approximation ratio of the 2-opt

  algorithm for the TSP. Operations Research Letters {\bfseries 37} (2009) 83--84

\bibitem{freisleben96}

Freisleben, B., Merz, P.: New genetic local search operators for the traveling

  salesman problem. In: Proceedings of the 4th International Conference on

  Parallel Problem Solving from Nature (1996) 890--899

\bibitem{garey79}

Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of

  NP-completeness. WH Freeman \& Co, New York (1979)

\bibitem{helsgaun00}

Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling

  salesman heuristic. European Journal of Operational Research {\bfseries 126}

  (2000) 106--130

\bibitem{holland75}

Holland, J.: Adaptation in natural and artificial systems. The University of

  Michigan Press, Ann Arbor (1975)

\bibitem{hoos05}

Hoos, H., Stutzle, T.: Stochastic local search: Foundations and applications.

  Morgan Kaufmann (2005)

\bibitem{merz01}

Merz, P., Freisleben, B.: Memetic algorithms for the traveling salesman

  problem. Complex Systems {\bfseries 13} (2001) 297--346

\bibitem{sels11}

Sels, V., Vanhoucke, M.: A hybrid dual-population genetic algorithm for the single machine maximum lateness problem. In: Proceedings of the 11th European conference on Evolutionary computation in combinatorial optimization (2011) 14--25

\end{thebibliography}

\end{document}