\documentclass[11pt,twoside]{article}\makeatletter

\IfFileExists{xcolor.sty}%
  {\RequirePackage{xcolor}}%
  {\RequirePackage{color}}
\usepackage{colortbl}
\usepackage{wrapfig}
\usepackage{ifxetex}
\ifxetex
  \usepackage{fontspec}
  \usepackage{xunicode}
  \catcode`⃥=\active \def⃥{\textbackslash}
  \catcode`❴=\active \def❴{\{}
  \catcode`❵=\active \def❵{\}}
  \def\textJapanese{\fontspec{Noto Sans CJK JP}}
  \def\textChinese{\fontspec{Noto Sans CJK SC}}
  \def\textKorean{\fontspec{Noto Sans CJK KR}}
  \setmonofont{DejaVu Sans Mono}
  
\else
  \IfFileExists{utf8x.def}%
   {\usepackage[utf8x]{inputenc}
      \PrerenderUnicode{–}
    }%
   {\usepackage[utf8]{inputenc}}
  \usepackage[english]{babel}
  \usepackage[T1]{fontenc}
  \usepackage{float}
  \usepackage[]{ucs}
  \uc@dclc{8421}{default}{\textbackslash }
  \uc@dclc{10100}{default}{\{}
  \uc@dclc{10101}{default}{\}}
  \uc@dclc{8491}{default}{\AA{}}
  \uc@dclc{8239}{default}{\,}
  \uc@dclc{20154}{default}{ }
  \uc@dclc{10148}{default}{>}
  \def\textschwa{\rotatebox{-90}{e}}
  \def\textJapanese{}
  \def\textChinese{}
  \IfFileExists{tipa.sty}{\usepackage{tipa}}{}
\fi
\def\exampleFont{\ttfamily\small}
\DeclareTextSymbol{\textpi}{OML}{25}
\usepackage{relsize}
\RequirePackage{array}
\def\@testpach{\@chclass
 \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else
  \ifnum \@lastchclass=7 5 \else
   \ifnum \@lastchclass=8 \tw@ \else
    \ifnum \@lastchclass=9 \thr@@
   \else \z@
   \ifnum \@lastchclass = 10 \else
   \edef\@nextchar{\expandafter\string\@nextchar}%
   \@chnum
   \if \@nextchar c\z@ \else
    \if \@nextchar l\@ne \else
     \if \@nextchar r\tw@ \else
   \z@ \@chclass
   \if\@nextchar |\@ne \else
    \if \@nextchar !6 \else
     \if \@nextchar @7 \else
      \if \@nextchar (8 \else
       \if \@nextchar )9 \else
  10
  \@chnum
  \if \@nextchar m\thr@@\else
   \if \@nextchar p4 \else
    \if \@nextchar b5 \else
   \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi
   \fi \fi  \fi  \fi  \fi  \fi  \fi \fi \fi \fi \fi \fi}
\gdef\arraybackslash{\let\\=\@arraycr}
\def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}}
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\def\abbr{}
\def\corr{}
\def\expan{}
\def\gap{}
\def\orig{}
\def\reg{}
\def\ref{}
\def\sic{}
\def\persName{}\def\name{}
\def\placeName{}
\def\orgName{}
\def\textcal#1{{\fontspec{Lucida Calligraphy}#1}}
\def\textgothic#1{{\fontspec{Lucida Blackletter}#1}}
\def\textlarge#1{{\large #1}}
\def\textoverbar#1{\ensuremath{\overline{#1}}}
\def\textquoted#1{‘#1’}
\def\textsmall#1{{\small #1}}
\def\textsubscript#1{\@textsubscript{\selectfont#1}}
\def\textxi{\ensuremath{\xi}}
\def\titlem{\itshape}
\newenvironment{biblfree}{}{\ifvmode\par\fi }
\newenvironment{bibl}{}{}
\newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par }
\newenvironment{citbibl}{}{\ifvmode\par\fi }
\newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi }
\newenvironment{docDate}{}{\ifvmode\par\fi }
\newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi }
\newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par }
\newenvironment{msHead}{\vskip 6pt}{\par}
\newenvironment{msItem}{\vskip 6pt}{\par}
\newenvironment{rubric}{}{}
\newenvironment{titlePart}{}{\par }

\newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}}
\newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}}
\newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}}
\newcolumntype{P}[1]{){\arraybackslash}p{#1}}
\newcolumntype{B}[1]{){\arraybackslash}b{#1}}
\newcolumntype{M}[1]{){\arraybackslash}m{#1}}
\definecolor{label}{gray}{0.75}
\def\unusedattribute#1{\sout{\textcolor{label}{#1}}}
\DeclareRobustCommand*{\xref}{\hyper@normalise\xref@}
\def\xref@#1#2{\hyper@linkurl{#2}{#1}}
\begingroup
\catcode`\_=\active
\gdef_#1{\ensuremath{\sb{\mathrm{#1}}}}
\endgroup
\mathcode`\_=\string"8000
\catcode`\_=12\relax

\usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry}
\usepackage{framed}

\definecolor{shadecolor}{gray}{0.95}
\usepackage{longtable}
\usepackage[normalem]{ulem}
\usepackage{fancyvrb}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{marginnote}

\renewcommand{\@cite}[1]{#1}


\renewcommand*{\marginfont}{\itshape\footnotesize}

\def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif}

  \pagestyle{fancy}

\usepackage[pdftitle={Study of Mathematical Model and Ant Colony Optimization (ACO)},
 pdfauthor={}]{hyperref}
\hyperbaseurl{}

	 \paperwidth210mm
	 \paperheight297mm
              
\def\@pnumwidth{1.55em}
\def\@tocrmarg {2.55em}
\def\@dotsep{4.5}
\setcounter{tocdepth}{3}
\clubpenalty=8000
\emergencystretch 3em
\hbadness=4000
\hyphenpenalty=400
\pretolerance=750
\tolerance=2000
\vbadness=4000
\widowpenalty=10000

\renewcommand\section{\@startsection {section}{1}{\z@}%
     {-1.75ex \@plus -0.5ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
     {-1.75ex\@plus -0.5ex \@minus- .2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
     {-1.5ex\@plus -0.35ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\large}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
     {-1ex \@plus-0.35ex \@minus -0.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\normalsize}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
     {1.5ex \@plus1ex \@minus .2ex}%
     {-1em}%
     {\reset@font\normalsize\bfseries}}


\def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt}
 \@tempdima 1.5em \begingroup
 \parindent \z@ \rightskip \@pnumwidth 
 \parfillskip -\@pnumwidth 
 \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par
 \endgroup}
\def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}}
\def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}}
\def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}}
\def\l@subparagraph{\@dottedtocline{5}{10em}{5em}}
\@ifundefined{c@section}{\newcounter{section}}{}
\@ifundefined{c@chapter}{\newcounter{chapter}}{}
\newif\if@mainmatter 
\@mainmattertrue
\def\chaptername{Chapter}
\def\frontmatter{%
  \pagenumbering{roman}
  \def\thechapter{\@roman\c@chapter}
  \def\theHchapter{\roman{chapter}}
  \def\thesection{\@roman\c@section}
  \def\theHsection{\roman{section}}
  \def\@chapapp{}%
}
\def\mainmatter{%
  \cleardoublepage
  \def\thechapter{\@arabic\c@chapter}
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \pagenumbering{arabic}
  \setcounter{secnumdepth}{6}
  \def\@chapapp{\chaptername}%
  \def\theHchapter{\arabic{chapter}}
  \def\thesection{\@arabic\c@section}
  \def\theHsection{\arabic{section}}
}
\def\backmatter{%
  \cleardoublepage
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \setcounter{secnumdepth}{2}
  \def\@chapapp{\appendixname}%
  \def\thechapter{\@Alph\c@chapter}
  \def\theHchapter{\Alph{chapter}}
  \appendix
}
\newenvironment{bibitemlist}[1]{%
   \list{\@biblabel{\@arabic\c@enumiv}}%
       {\settowidth\labelwidth{\@biblabel{#1}}%
        \leftmargin\labelwidth
        \advance\leftmargin\labelsep
        \@openbib@code
        \usecounter{enumiv}%
        \let\p@enumiv\@empty
        \renewcommand\theenumiv{\@arabic\c@enumiv}%
	}%
  \sloppy
  \clubpenalty4000
  \@clubpenalty \clubpenalty
  \widowpenalty4000%
  \sfcode`\.\@m}%
  {\def\@noitemerr
    {\@latex@warning{Empty `bibitemlist' environment}}%
    \endlist}

\def\tableofcontents{\section*{\contentsname}\@starttoc{toc}}
\parskip0pt
\parindent1em
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\newenvironment{reflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemsep}{0pt}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\itshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{sansreflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\itemsep}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\upshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{specHead}[2]%
 {\vspace{20pt}\hrule\vspace{10pt}%
  \phantomsection\label{#1}\markright{#2}%

  \pdfbookmark[2]{#2}{#1}%
  \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}%
  }{}
      \def\TheFullDate{2012-01-15 (revised: 15 January 2012)}
\def\TheID{\makeatother }
\def\TheDate{2012-01-15}
\title{Study of Mathematical Model and Ant Colony Optimization (ACO)}
\author{}\makeatletter 
\makeatletter
\newcommand*{\cleartoleftpage}{%
  \clearpage
    \if@twoside
    \ifodd\c@page
      \hbox{}\newpage
      \if@twocolumn
        \hbox{}\newpage
      \fi
    \fi
  \fi
}
\makeatother
\makeatletter
\thispagestyle{empty}
\markright{\@title}\markboth{\@title}{\@author}
\renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus2\p@
\belowdisplayshortskip 4\p@ plus2\p@ minus2\p@
\def\@listi{\leftmargin\leftmargini
               \topsep 2\p@ plus1\p@ minus1\p@
               \parsep 2\p@ plus\p@ minus\p@
               \itemsep 1pt}
}
\makeatother
\fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm}
\fancyhf{} 
\setlength{\headheight}{14pt}
\fancyhead[LE]{\bfseries\leftmark} 
\fancyhead[RO]{\bfseries\rightmark} 
\fancyfoot[RO]{}
\fancyfoot[CO]{\thepage}
\fancyfoot[LO]{\TheID}
\fancyfoot[LE]{}
\fancyfoot[CE]{\thepage}
\fancyfoot[RE]{\TheID}
\hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true}
\fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}}

\date{}
\usepackage{authblk}

\providecommand{\keywords}[1]
{
\footnotesize
  \textbf{\textit{Index terms---}} #1
}

\usepackage{graphicx,xcolor}
\definecolor{GJBlue}{HTML}{273B81}
\definecolor{GJLightBlue}{HTML}{0A9DD9}
\definecolor{GJMediumGrey}{HTML}{6D6E70}
\definecolor{GJLightGrey}{HTML}{929497} 

\renewenvironment{abstract}{%
   \setlength{\parindent}{0pt}\raggedright
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
   \textcolor{GJBlue}{\large\bfseries\abstractname\space}
}{%   
   \vskip8pt
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
}

\usepackage[absolute,overlay]{textpos}

\makeatother 
      \usepackage{lineno}
      \linenumbers
      
\begin{document}

             \author[1]{Dr. Pawandeep  Chahal}

             \affil[1]{  }

\renewcommand\Authands{ and }

\date{\small \em Received: 12 December 2011 Accepted: 31 December 2011 Published: 15 January 2012}

\maketitle


\begin{abstract}
        


In this paper we define those mathematical notions and terms that are useful about ACO and the relationships between ACO and other frameworks for optimization and control. This chapter defines and discusses the characteristics of: (i) the combinatorial optimization problems addressed by ACO, (ii) construction heuristics for combinatorial problems, (iii) the equivalence between solution construction and sequential decision process (iv) the graphical tools (state graph and construction graph) that can be used to represent and reason on the structure and dynamics of construction processes.

\end{abstract}


\keywords{optimization and control, combinatorial}

\begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) 
\textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark}
\end{textblock*}

\begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) 
\textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}}
\end{textblock*}


\let\tabcellsep& 	 	 		 
\section[{I. Combinatorial Optimization Problems}]{I. Combinatorial Optimization Problems}\par
ACO is a metaheuristic for the solution of problems of combinatorial optimization.\par
Instance of a combinatorial optimization problema : An instance of a combinatorial optimization problem is a pair (S, J), where S is a finite set of feasible solutions and J is a function that associates a real cost to each feasible solution, J: S ? R. The problem consists in finding the element s*? S which minimizes the function J:s * = arg min ????? ??(??)\textbf{(1)}\par
Hereafter only sets S with finite cardinality will be considered, even if the above definition could be extended to countable sets of infinite cardinality. Given the finiteness of the set S, the minimum of J on S indeed exists. If such minimum is attained for more than one element of S, it is a matter of indifference which one is considered.\par
Combinatorial optimization problema : A combinatorial optimization problem is a set of instances of an optimization problem. The set of instances defining an optimization problem are usually all sharing some core properties or are all generated in a similar way. Therefore, an optimization problem defines a classification over sets of instances. This classification can be made according to several criteria that are usually based on both mathematical and practical considerations.\par
Static and dynamic optimization problems : Static combinatorial optimization problems are such that the value of the mapping J does not change during the execution of the solving algorithm. In dynamically changing problems the mapping J changes during the execution of the algorithm, that is, J depends on a time parameter t: J ? J (s, t).\par
If the statistical processes according to which the costs change over time are known in advance, then the optimization problem can be stated again as a static problem in which J is either a function of the time or has a value drawn according to some probability distribution. In these cases the minimization in Equation \hyperref[formula_0]{1}has to be done according to the J's characteristics (e.g., minimization of the J's mean value, if J's values are drawn from a unimodal parametric distribution). On the other hand, when only incomplete information is available about the dynamics of cost changes, the problem has to be tackled online using an adaptive approach.\par
The set of problems here labeled as "static" are actually most of the problems usually considered in combinatorial optimization textbooks (e.g., the traveling salesman problem, the quadratic assignment problem, the graph coloring problem, etc.). They can be solved offline, adopting either a centralized or a parallel/distributed approach according to the available computing resources. Dynamic problems are somehow real-world versions of these problems. Routing in communication networks is a notable example of dynamic problem: the characteristics of both the input traffic and the topology of the network can change over time according to dynamics for which is usually hard to make robust prediction models. Moreover, in general routing requires a distributed problem solving approach.\par
In general terms, while for static problems using a centralized or a distributed algorithm is a matter of choice, dynamic problems usually impose more severe requirements, such that the nature (either centralized or distributed) of the problem has to be matched by the characteristics of the algorithm. In this sense, ACO's design, relying on the use of a set of autonomous agents, appears as rather effective, since it can be in principle used in both centralized and distributed contexts with little adaptation.\par
Primitive, environment, and constraints sets : An optimization problem can be formally identified in terms of a primitive set K, an environment set E, a solution set S, and a cost criterion J defined on S. The primitive set defines the basic elements of the problem. The environment set E is derived from the primitive set K as a subset of its power set, E ? P (K), and the solution set S is in turn derived from the environment set in terms of a family of subsets of E defined by a set of mathematical relations ? among the K's elements, S ? P (E) ? ?. The set of relations ?, which puts specific limitations on the way the elements in E can be selected in order to identify elements in S, is usually termed the constraints set.\par
The choices for sets K, E and ? are not unique. Given an abstract definition of a problem, the same problem can be expressed in different ways according to different choices for these sets. One choice can be preferred over another just because it puts some more emphasis on aspects that are seen as more important in the considered context. In general, these facts raise the issue of the representation adopted to model the abstract problem under consideration in the perspective of attacking it with a specific class of algorithms. This issue is discussed more in depth in the following of this section. But before that, it is useful to make the above notions of primitive and environment sets more concrete through a few examples, and to introduce the notion of solution components which will play a central role throughout the thesis.\par
In order to explain in what a problem definition in terms of the sets K, E and ? precisely consists of, let us consider the concrete case of two wide and quite general classes of combinatorial problems: matching problems and set problems [70], to which we will refer often throughout the thesis: Matching problems : A matching in a graph is a set of edges, no two of which share a node. Goals in matching problems consist in finding either matching with maximal edge sets or, given that costs are associated to the edges/nodes, matching with minimal associated cost (weighted matching problems).\par
Matching problems in terms of primitive and environment sets : Let K = \{1, 2, . . . , N\} be a generic set of elements of interest, and let K be the primitive set. The environment and solution sets are derived as follows:E = P (K) S = \{? ? E | problem constraints ? (K ) are satisfied\} (2)\par
The expressions 3.2 mean that the solution set is directly defined in terms of subsets of K's power set. In the class of matching problems, of particular practical interest, as well as easier to solve, are those problems for which the underlying graph is a complete bipartite graph with two sets of nodes that are equal in size. Bipartite weighted matching of this type are also known as assignment problems, which are for instance the problems of assigning tasks to agents knowing the cost of making agent i deal with task j, and include important combinatorial problems like the TSP, the QAP and the VRP. Network flow problems can be also expressed in terms of generic bipartite matching. The following example shows in practice how K, E and S can be defined in the case of a TSP. 
\section[{Example 1 :}]{Example 1 :}\par
Given an N cities TSP, K = \{c 1 , c 2 , . . . , c N \} = \{1, 2, . . . , N\} coincides with the set of the cities to be visited, E=P(K ) is the set of all their possible combinations, and S results from the application of ? as the subset of elements in E which are cyclic permutations of size N. An alternative definition of K, E and ? could consist in K being the set of pairs (p i , c j ), p i , c j ? \{1, 2, . . . , N\}, that is, the set of elements telling that city c j is in position p i in the solution sequence (notice that being the TSP's solutions cyclic permutations, the notion of position requires setting an arbitrary start city). In this case E is still the power set of K, but the syntax of the ? relations is slightly different from before, S is in fact defined as?? = ?? ?? ? ??, ?? ?? = \{(?? 1 ?? , ?? 1 ?? ), ? , (?? ?? ?? , ?? ?? ?? )\} | ? ?? ?? ?? ?? = \{1, ? , ??\} ? ? ?? ?? ?? ?? = \{1, ? , ??\}\par
That is, the set of pairs must correspond to a permutation over \{1, ?, N\}.\par
Set problems : In assignment problems solutions can be usually expressed in terms of ordered subsets of primitive elements, while in the case of set problems there is no explicit notion of ordering. Moreover, in most of the assignment problems the solution has a predefined size, while this is never the case for set problems. Set problems are also in general characterized by an additional level of complexity with respect to the assignment ones in the sense that is well expressed by the structure of the environment and solution sets:\par
Set problems in terms of primitive and environment sets :\par
In set problems, which can be further classified in set covering, set packing and set partitioning problems, the corresponding of expression 3.2 takes the following form:E= \{? ? P (K ) | instance constraints ? I are satisfied\} S= \{?' ? P (K ) | instance constraints ? I are satisfied\} (3)\par
These expressions point out the fact that the solution set is defined in a more complex way than in the matching case. Solutions are in this case sets of subsets of elements of the environment set, which, in turn, are subsets of elements of K. The ? I constraints that have been called a bit improperly "instance constraints" are defined by the actual characteristics of the instance at hand. Instance of a combinatorial problem using a compact representation : Let C be a finite set of variables such that a solution in S can be expressed in terms of subsets of C?s elements. In particular, called X? = P(C), S is identified by the subset of elements of X? for which the relations in ? are satisfied: S ? X? ? ?(C). Therefore, given the sets S, C and ?(C), together with a real-valued cost function J (S), a problem of combinatorial optimization consists in finding the element s* such that:?? * = ?????? ?????? ???\{?? ? ? ? (??)\} ??(??)\textbf{(5)}\par
Following this representation, an instance of a combinatorial optimization problem can be also compactly represented by the triple<C, ?, J >\textbf{(6)}\par
The elements of C, which represent the object of the decisions of the optimization process, are called hereafter solution components. 
\section[{a) Solution components}]{a) Solution components}\par
From above definition it is apparent that solution components always have a precise relationship with the primitive and environment sets.\par
In particular, for assignment problems C coincides with K, while for set problems C coincides with E. However, here we prefer to speak in terms of solution components rather than primitive and environment sets, because of their more intuitive and general meaning of parts of which a solution is composed of: Solution components : The solution components set C is operatively defined as the set from which a step-bystep decision process would select elements one-at-atime and add them to a set x until a feasible solution is built, that is, until x ? S.\par
According to this characterization, the notion of solution components plays a central role in this thesis, since combinatorial optimization is here framed in the domain of decision processes, and the components of a solution are precisely the step-by-step objects considered by the decisions processes. More specifically, ACO's target will consists in the learning of good decisions in the terms of pairs of components to be included in the building solutions.\par
Above definition implicitly implies that for each set C of solution components must exist a bijective mapping:f C : X ? P(C) ? S,\textbf{(7)}\par
such that each s i ? S has a finite subset \{?? ?? 1 , ?? ?? 2 , ? , ?? ?? ?? \} ? X of solution components as preimage in X, and this preimage is unique. That is, after a finite number of decision steps, where at each step t a new component c t is included in the set x t , the elements in x t ? X are expected to map through f C onto an element s ? S. The characteristics of the mapping f C define the level of correspondence between the problem under solution and the way solutions are represented. In particular, if f C is not anymore surjective, not all the feasible solutions are going to have a preimage in terms of a single set of components. Such a choice could rule out the same possibility of addressing the optimal solution. On the other hand, if f C is not anymore injective, the same solution in S can be addressed by one or more distinct elements in X. Such a choice would result in a sort of blurred image of the solution set as seen from the component set, since several solutions could be seen as the same solution, making potentially difficult for an algorithm to act optimally. In general, when the mapping f C is not anymore bijective the representation will undergo some loss of necessary information. That is, additional information must be added to a subset x ? X of C's elements in order to map it onto a solution.\par
It is clear that once a mapping f C has been defined, solution components can be seen in more general terms as decision variables. At each solution construction step a decision variable c t representing any convenient value is assigned. The only strict requirement consists in the fact that sets of decision variables can be eventually mapped bijectively onto a feasible solution. Since in some sense it is natural to explicitly associate decision variables to parts of a solution, in the following we will preferably use the term "solution components" instead of "decision variables".\par
Even if this latter would likely make clearer the intrinsic meaning of ACO's pheromone variables, which are precisely associated to pairs (c i , c j ) of decision variables: decision c j is taken, conditionally to the fact that decision c i has been already issued, according to a probability value which depends on the value of the pheromone variable ?? ?? ?? ?? ?? associated to the pair of decisions. The way ACO is discussed in this thesis in terms of sequential decision processes, as well as the recent work of Chang et al. \hyperref[b13]{[13]}, where ACO, departing from the usual application to "classical" combinatorial optimization problems, is applied to the solution of generic MDPs (therefore, dealing with stochastic transitions after the issuing of a decision), strongly confirm this interchangeable view of pheromone variables as pairs of decision variables or solution components. 
\section[{II.}]{II.} 
\section[{Construction Methods}]{Construction Methods}\par
ACO's ant-like agents independently generate solutions according to an incremental construction process. Therefore, the notion of construction algorithm is at the core of ACO. A generic construction algorithm is defined here as follows: The generic iteration (also termed hereafter transition) of a construction process can be described as:\par
x j =\{c 1 , c 2 , . . . , c j \} ? x j+1 = \{c 1 , c 2 , . . . , c j , c j+1 \}, c i ? C, ?i ? \{1, 2, . . . , | C |\},  {\ref (3.10)} where x j ? X? = P(C) is a partial solution of cardinality (length) j, j ? |C | < ?.\par
The partial solutions, that is, the set of all the possible configurations of solution components that can be encountered during the steps of the construction algorithm, coincides with elements of the environment set X?. As it has been previously noticed, the majority of these elements are such that, in general, they are not subsets of some feasible solution set. That is, without a careful step-by-step checking, the construction process is likely to end up in a partial solution that cannot be further completed into a feasible solution.\par
The algorithmic skeleton of a generic construction strategy is reported in the pseudo-code of the Algorithm 3. It is the duty of the construction algorithm to guarantee that a sequence of feasible partial solutions, defined as it follows, is generated during the process: Feasible partial solution : A partial solution x j ? X? is called feasible if it can be completed into a feasible solution s ? S, that is, if at least one feasible solution s ? S exists, of which x j is the initial sub tuple of length j in the case of sequences, or, of which x j is a subset in the case of sets. The set of the feasible partial solutions is indicated with X ? X?.\par
It is understood that a process generating a sequence of feasible partial solutions necessarily ends up into a feasible solution. The set X of all feasible sets x j is finite since both the set S and the cardinality of the set associated to each feasible solution s i are finite. Moreover, S ? X, since all the solutions s i is composed by a finite number of components, all belonging to C. Each feasible partial solution x j has associated a set of possible feasible expansions: Set of feasible expansions : For each feasible partial solution x j , the set C(x j )? C is the set of all the possible new components c j ? C that can be added to x j giving in turn a new feasible (partial) solution x j+1 :????? ?? ? = ??? ?? ?? ?? ?? +1 : ?? ?? +1 ? ?? ? ?? ?? +1 = ?? ?? ? ?? ?? \} (10)\par
Where the operator ? represents the strategy adopted by the construction algorithm to include a new component into the building solution. In general, the characteristics of the sets C strongly depend on the precise form of the operator ?.\par
The very possibility of speaking in terms of feasible partial solutions and feasible expansion sets is related to the possibility of checking step-by-step the feasibility of the partial solution in order to take a sequence of decisions that can finally take to a feasible solution. For reasons that will be more clear in the following, we make a distinction between the components of the algorithm managing the aspects of feasibility from those specifically addressed at optimize the quality of the solution(s) that will be built. In order to check step-by-step the feasibility of the building solution, we assume that a logical device can be made available to the construction agent: Feasibility-checking device : By feasibility-checking device we intend any algorithm which, on the basis of the knowledge of the set S and/or of the constraint set ?, is able to provide in polynomial time an answer concerning the feasibility of a complete solution and the potential feasibility of a partial solution.\par
From a theoretical point of view it is always possible to find such a polynomial algorithm in the case of NP-hard problems and in all the subclasses of the NP-hard one. However, even in the case of NPhardness, which is the most common and interesting case, to allow a practical use of the device the polynomial order should be small. Generally speaking, the computations associated to the device should be light. When this is not the case, it can result more convenient to incur the risk of building a solution which is not feasible, that can be either repaired or discarded. For the class of problems considered in this thesis it is often possible to have at hand a computationally-light feasibility-checking device. In fact, it is usually easy to check step-by-step the feasibility of a constructing solution for assignment problems like the TSP or the QAP. However, for some scheduling or covering problems, this same task can result both more difficult and computationally expensive to accomplish. Moreover, in the case of max constraint satisfaction problems this is precisely the problem. However, the point is that here we will not focus on the design of strategies for smart or optimized ways of dealing with feasibility issues. Surely this will be an important part of the specific implementations, but we assume that in some sense this is not the most important part of the story, which is, on the contrary, the optimization of the quality of the final solution output by the algorithm.\par
Figure  {\ref 3}.1 shows in a graphical way the generic step of a construction process, pointing out all the important aspects and their reciprocal relationships in very general terms. The feasibility checking device which defines the set C (x t ) of feasible expansions for the current partial solution x t is indicate with the ? box, to stress the role of either the constraints set ? and/or the explicit knowledge of the solution set to accomplish this sub-task. The specific strategy of selection and inclusion of the new component ct is indicated by the decision block ?. The dashe d contour lines show the actual subsets of components defining respectively the partial solution x t and the set of feasible expansions C (x t ). The chosen component ct belongs to this last. The diagram shows the case in which a feasible solution x s ? S is eventually constructed. The decision strategy ? is generically assumed as making use of at least the information contained in the partial solution in addition to C (x t ). A similar diagram will be shown for the specific case of the ACO's ant agents, in order to show the peculiarities of the ACO's design with respect to this generic one.\par
This issue of the feasibility of the final solution has put in evidence the fact that during a construction process the single decisions cannot be seen as independent. On the contrary, they are tightly related, since all the decisions issued in the past will constrain those that can be issued in the future. On the other hand, feasibility is only one aspect of the entire problem of building a solution. The equally, if not more, important aspect concerns the quality of the solution. It is evident that the same considerations on the dependence among the decisions apply also when quality is considered. In general, to optimize the final quality, each specific decision should be taken in the light of all previous decisions, that is, according to the status of the current partial solution. This can be seen at the same time as a constraint and an advantage: building a solution in a sequential way allows to reason on each single choice on the basis of an incremental amount of information coming from the past and also possibly looking into the future through some form of look ahead. These are the basic key concepts to understand the rationale behind a large part of the con-tents of this chapter, which discusses construction and decision processes. In fact, in rather general terms, two construction strategies are going to be seen as different according to the different way of using and discarding the information contained in the partial solutions. In particular, it will be shown that an exact approach, like dynamic programming \hyperref[b2]{[3]}, makes use of the full information, while a heuristic approach, like ACO, drops off everything but the last included component. 
\section[{III.}]{III.} 
\section[{Conclusion}]{Conclusion}\par
In this paper we have defined the formal tools and the basic scientific background. That is, we have defined the terms and notions that will allow us to show important connections between ACO and other related frameworks and that will allow us to adopt a formal and insightful language to describe ACO.\par
More specifically the chapter has introduced the class of combinatorial optimization problems addressed by ACO and discussed the role and characteristics of different abstract representations of the same combinatorial optimization problem at hand. The chapter has also provided a formal definition and an analysis of construction methods for combinatorial optimization, made explicit and discussed the relationship between construction methods and sequential decision processes and, in turn, optimal control and defined the notion of construction graph as a graphical tool, derived from the state graph through the application of a generating function, which is useful to visualize and reason on sequential decision processes using a compact representation.\begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-2.png}
\caption{\label{fig_0}}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-3.png}
\caption{\label{fig_1}}\end{figure}
   			\footnote{© 2012 Global Journals Inc. (US)} 		 		\backmatter  			  				\begin{bibitemlist}{1}
\bibitem[Cheng et al. ()]{b14}\label{b14} 	 		‘A loop-free extended bellman-ford routing protocol without bouncing effect’.  		 			C Cheng 		,  		 			R Riley 		,  		 			S P Kumar 		,  		 			J J Garcia-Luna-Aceves 		.  	 	 		\textit{ACM Computer Communication Review (SIGCOMM '89)},  				1989. 18 p. .  	 
\bibitem[Dijkstra ()]{b25}\label{b25} 	 		‘A note on two problems in connection with graphs’.  		 			E W Dijkstra 		.  	 	 		\textit{Numerical Mathematics}  		1959. 1 p. .  	 
\bibitem[Garcia-Luna-Aceves and Murthy (1997)]{b27}\label{b27} 	 		‘A pathfinding algorithm for loop-free routing’.  		 			J J Garcia-Luna-Aceves 		,  		 			S Murthy 		.  	 	 		\textit{IEEE/ACM Transactions on Networking}  		February 1997.  	 
\bibitem[Broch et al. ()]{b11}\label{b11} 	 		‘A performance comparison of multi-hop wireless ad hoc network routing protocols’.  		 			J Broch 		,  		 			D A Maltz 		,  		 			D B Johnson 		,  		 			Y C Hu 		,  		 			J Jetcheva 		.  	 	 		\textit{Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom98)},  				 (the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom98))  		1998.  	 
\bibitem[Chang et al. (2003)]{b13}\label{b13} 	 		\textit{An Ant System approach to Markov Decision Processes},  		 			H S Chang 		,  		 			W Gutjahr 		,  		 			J Yang 		,  		 			S Park 		.  		 2003-10.  		September 2003. Vienna, Austria.  		 			Department of Statistics and Decision Support Systems, University of Vienna 		 	 	 (Technical Report) 
\bibitem[Cidon et al. ()]{b17}\label{b17} 	 		‘Analysis of multipath routing’.  		 			I Cidon 		,  		 			R Rom 		,  		 			Y Shavitt 		.  	 	 		\textit{IEEE/ACM Transactions on Networking}  		1999. 7  (6)  p. .  	 
\bibitem[Dorigo et al. ()]{b26}\label{b26} 	 		‘Ant algorithms for discrete optimization’.  		 			M Dorigo 		,  		 			G Di Caro 		,  		 			L M Gambardella 		.  	 	 		\textit{Artificial Life}  		1999. 5  (2)  p. .  	 
\bibitem[Colorni et al. ()]{b18}\label{b18} 	 		‘Ant system for job-shop scheduling’.  		 			A Colorni 		,  		 			M Dorigo 		,  		 			V Maniezzo 		,  		 			M Trubian 		.  	 	 		\textit{Statistics and Computer Science (JORBEL)}  		1994. 34 p. .  	 	 (Belgian Journal of Operations Research) 
\bibitem[Caro et al. (2005)]{b24}\label{b24} 	 		‘AntHocNet: an adaptive nature-inspired algorithm for routing in mobile ad hoc networks’.  		 			G Di Caro 		,  		 			F Ducatelle 		,  		 			L M Gambardella 		.  	 	 		\textit{European Transactions on Telecommunications}  		October 2005. 16  (5) .  	 
\bibitem[Caro et al. ()]{b23}\label{b23} 	 		‘AntHocNet: an ant-based hybrid routing algorithm for mobile ad hoc networks’.  		 			G Di Caro 		,  		 			F Ducatelle 		,  		 			L M Gambardella 		.  	 	 		\textit{Proceedings of Parallel Problem Solving from Nature (PPSN) VIII},  		Lecture Notes in Computer Science  		 (Parallel Problem Solving from Nature (PPSN) VIII)  		2004. Springer-Verlag. 3242 p. .  	 
\bibitem[Caro and Dorigo (1997)]{b22}\label{b22} 	 		\textit{AntNet: A mobile agents approach to adaptive routing},  		 			G 		,  		 			Di Caro 		,  		 			M Dorigo 		.  		 97- 12.  		June 1997. Belgium.  		 			IRIDIA, University of Brussels 		 	 	 (Technical Report) 
\bibitem[Abe et al. ()]{b0}\label{b0} 	 		\textit{Biodiversity: an ecological perspective},  		 			T Abe 		,  		 			S A Levin 		,  		 			M Higashi 		.  		1997. New York, USA: Springer-Verlag.  	 
\bibitem[Bellman ()]{b2}\label{b2} 	 		\textit{Dynamic Programming},  		 			R Bellman 		.  		1957. Princeton University Press.  	 
\bibitem[Cottarelli and Gobbi ()]{b19}\label{b19} 	 		‘Estensioni dell'algoritmo formiche per il problema del commesso via ggiatore’.  		 			M Cottarelli 		,  		 			A Gobbi 		.  	 	 		\textit{Politecnico di Milano}  		1997.  	 	 (Master's thesis, Dipartimento di Elettronica e Informazione) 
\bibitem[Owen ()]{b31}\label{b31} 	 		\textit{Game Theory},  		 			G Owen 		.  		1995. Academic Press.  	 	 (third edition) 
\bibitem[Camara and Loureiro ()]{b12}\label{b12} 	 		\textit{Gps/ant-like routing in ad hoc networks. Telecommunication Systems},  		 			D Camara 		,  		 			A F Loureiro 		.  		2001. 18 p. .  	 
\bibitem[Bland ()]{b7}\label{b7} 	 		\textit{Layout of facilities using an Ant System approach. Engineering optimization},  		 			J A Bland 		.  		1999. 32.  	 
\bibitem[Puterman ()]{b32}\label{b32} 	 		\textit{Markov Decision Problems},  		 			M L Puterman 		.  		1994. John Wiley \& Sons.  	 
\bibitem[Cidon et al. ()]{b16}\label{b16} 	 		‘Multi-path routing combined with resource reservation’.  		 			I Cidon 		,  		 			R Rom 		,  		 			Y Shavitt 		.  	 	 		\textit{IEEE INFOCOM'97},  				1997. p. .  	 
\bibitem[Bellman ()]{b3}\label{b3} 	 		‘On a routing problem’.  		 			R Bellman 		.  	 	 		\textit{Quarterly of Applied Mathematics}  		1958. 16  (1)  p. .  	 
\bibitem[Bland ()]{b6}\label{b6} 	 		\textit{Optimal structural design by Ant Colony Optimization. Engineering optimization},  		 			J A Bland 		.  		2001. 33 p. .  	 
\bibitem[Moy ()]{b30}\label{b30} 	 		\textit{OSPF Anatomy of an Internet Routing Protocol},  		 			J Moy 		.  		1998. Addison-Wesley.  	 
\bibitem[Moy ()]{b29}\label{b29} 	 		\textit{OSPF version 2. Request For Comments (RFC) 1583},  		 			J Moy 		.  		1994.  		 			Network Working Group 		 	 
\bibitem[Chrisman ()]{b15}\label{b15} 	 		‘Reinforcement learning with perceptual aliasing: The perceptual distinctions approach’.  		 			L Chrisman 		.  	 	 		\textit{Proceedings of the Tenth National Conference on Artificial Intelligence},  				 (the Tenth National Conference on Artificial Intelligence)  		1992. p. .  	 
\bibitem[Bertsekas et al. ()]{b4}\label{b4} 	 		‘Rollout algorithms for combinatorial optimization’.  		 			D Bertsekas 		,  		 			J N Tsitsiklis 		,  		 			Cynara Wu 		.  	 	 		\textit{Journal of Heuristics}  		1997. 3  (3)  p. .  	 
\bibitem[Bland ()]{b8}\label{b8} 	 		‘Space-planning by Ant Colony Optimization’.  		 			J A Bland 		.  	 	 		\textit{International Journal of Computer Applications in Technology}  		1999. 12.  	 
\bibitem[Beckmann et al. ()]{b1}\label{b1} 	 		\textit{Studies in the Economices of Transportation},  		 			M Beckmann 		,  		 			C B Mcguire 		,  		 			C B Winstein 		.  		1956. Yale University Press.  	 
\bibitem[Bonabeau et al. ()]{b10}\label{b10} 	 		\textit{Swarm Intelligence: From Natural to Artificial Systems},  		 			E Bonabeau 		,  		 			M Dorigo 		,  		 			G Theraulaz 		.  		1999. Oxford University Press.  	 
\bibitem[Glover ()]{b28}\label{b28} 	 		‘Tabu search, part I’.  		 			F Glover 		.  	 	 		\textit{ORSA Journal on Computing}  		1989. 1 p. .  	 
\bibitem[Bolding et al. ()]{b9}\label{b9} 	 		\textit{The case for chaotic adaptive routing},  		 			K Bolding 		,  		 			M L Fulgham 		,  		 			L Snyder 		.  		 CSE- 94-02-04.  		1994. Seattle.  		 			Department of Computer Science, University of Washington 		 	 	 (Technical Report) 
\bibitem[Rome and Mattern (2004)]{b33}\label{b33} 	 		\textit{The design space of wireless sensor networks},  		 			Kay Rome 		,  		 			Friedemann Mattern 		.  		December 2004. IEEE Wireless Communications. 11 p. .  	 
\bibitem[Deneubourg et al. ()]{b21}\label{b21} 	 		‘The dynamics of collective sorting: robot-like ants and ant-like robots’.  		 			J L Deneubourg 		,  		 			S Goss 		,  		 			N Franks 		,  		 			A Sendova-Franks 		,  		 			C Detrain 		,  		 			L Chretien 		.  	 	 		\textit{Proceedings of the First International Conference on Simulation of Adaptive Behaviors: From Animals to Animats},  				 			S Wilson 		 (ed.)  		 (the First International Conference on Simulation of Adaptive Behaviors: From Animals to AnimatsCambridge, MA, USA)  		1991. MIT Press. p. .  	 
\bibitem[Deneubourg et al. ()]{b20}\label{b20} 	 		‘The self-organizing exploratory pattern of the argentine ant’.  		 			J.-L Deneubourg 		,  		 			S Aron 		,  		 			S Goss 		,  		 			J.-M Pasteels 		.  	 	 		\textit{Journal of Insect Behavior}  		1990. 3 p. .  	 
\bibitem[Birattari et al. ()]{b5}\label{b5} 	 		‘Towards the formal foundation of ant programming’.  		 			M Birattari 		,  		 			G Di Caro 		,  		 			M Dorigo 		.  	 	 		\textit{Ants Algorithms -Proceedings of ANTS 2002, Third International Workshop on Ant Algorithms},  		Lecture Notes in Computer Science  		 			M Dorigo,  			G Di Caro,  			M Sampels 		 (ed.)  		 (Brussels, Belgium)  		September 12-14, 2002. 2002. Springer-Verlag. 2463 p. .  	 
\end{bibitemlist}
 			 		 	 
\end{document}
