{"id":85,"date":"2020-01-17T12:11:11","date_gmt":"2020-01-17T01:41:11","guid":{"rendered":"http:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/?page_id=85"},"modified":"2020-01-17T12:19:41","modified_gmt":"2020-01-17T01:49:41","slug":"cross-entropy-optimisation-hybrid-approach","status":"publish","type":"page","link":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/cross-entropy-optimisation-hybrid-approach\/","title":{"rendered":"Cross-entropy\/optimisation hybrid approach"},"content":{"rendered":"<div class=\"wpb-content-wrapper\"><p>[vc_row][vc_column][vc_empty_space][vc_column_text]<\/p>\n<h1>Cross-entropy\/optimisation hybrid approach<\/h1>\n<p align=\"left\">The Cross-Entropy method when applied to the Travelling salesman problem relies on generating random samples of tours and then constructing a sequence of transition probability matrices whose entries will, ultimately, be concentrated on the edges of an optimal tour. Of course, the Hamiltonian cycle problem can be regarded as a special case of the Travelling salesman problem and is thus, in principle, solvable by this method. On the other hand, the various MDP-based methods (see\u00a0<a href=\"http:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/variance-of-first-hitting-times\/\">Variance of first hitting times<\/a> and\u00a0<a title=\"branch-and-fix-method\" href=\"http:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/branch-and-fix-approach\/\">Branch-and-fix method<\/a>) also search for a probability transition matrix, entries of which are concentrated on the edges of a Hamiltonian cycle; however, they do so by solving a global optimisation problem, for instance, in the associated subspace of discounted occupational measures.<\/p>\n<p align=\"left\">The cross-entropy\/optimisation hybrid approach was first proposed by Eshragh et al [2] and consists of two parts:<\/p>\n<ul>\n<li>\n<div align=\"left\"><b><i>MDP-part<\/i><\/b>\u00a0&#8211; a static optimisation problem derived from the above mentioned embedding of a graph in a Markov decision process,<\/div>\n<\/li>\n<li>\n<div align=\"left\"><b><i>CE-part<\/i><\/b>\u00a0&#8211; extracting information from a random sample in a manner consistent with the Cross-Entropy method. This part may be used either separately from or in conjunction with an appropriate optimisation algorithm.<\/div>\n<\/li>\n<\/ul>\n<p align=\"left\">The CE-part is slightly modified from the standard cross-entropy implementation, in that we seek to generate reverse Hamiltonian cycles in addition to standard Hamiltonian cycles. Used alone, the CE-part should be enough to converge to an optimal solution (ie a Hamiltonian cycle), however, for moderately large graphs, the numerical performance suffers. This is the movitation for adding the MDP-part. While it does not influence the CE-part, it uses the information gained from the CE-part at each iteration to execute a heuristic aimed at finding a Hamiltonian cycle. Then, a Hamiltonian cycle may be found either by the CE-part or the MDP-part, and either allows the algorithm to terminate.<\/p>\n<p align=\"left\">In Eshragh et al [2] experimental results are given that demonstrate which part of the algorithm is ultimately successful in finding Hamiltonian cycles in progressively larger graphs, and although the CE-part is usually successful in small graphs, for larger graphs the MDP-part allows the early termination of the algorithm. The algorithm is demonstrated to be capable of solving problems with hundreds of vertices.<\/p>\n<p align=\"left\">The cross-entropy\/optimisation hybrid algorithm is discussed in greater detail in Eshragh [1].<\/p>\n<h3>PUBLICATIONS<\/h3>\n<p>[1] Eshragh, A. &#8220;Hamiltonian cycles and the space of discounted occupational measures.&#8221; PhD Thesis, University of South Australia, 2011. <a href=\"http:\/\/trove.nla.gov.au\/work\/157668907?q=Hamiltonian+cycles+and+the+space+of+discounted+occupational+measures++Ali+Eshragh+Jahromi&amp;c=book\" target=\"_blank\" rel=\"noopener noreferrer\">Trove<\/a><\/p>\n<p>[2] Eshragh, A., Filar, J.A. and\u00a0Haythorpe, M. &#8220;A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem.&#8221; <i>Annals of\u00a0Operations Research<\/i>, 189(1):103-125, 2011.\u00a0<a href=\"http:\/\/www.springerlink.com\/content\/q774uu148g525356\/\" target=\"_blank\" rel=\"noopener noreferrer\">SpringerLink<\/a>[\/vc_column_text][vc_empty_space][\/vc_column][\/vc_row]<\/p>\n<\/div>","protected":false},"excerpt":{"rendered":"<p>[vc_row][vc_column][vc_empty_space][vc_column_text] Cross-entropy\/optimisation hybrid approach The Cross-Entropy method when applied to the Travelling salesman problem relies on generating random samples of tours and then constructing a sequence of transition probability matrices whose entries will, ultimately, be concentrated on the edges of an optimal tour. Of course, the Hamiltonian cycle problem can be regarded as a special [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":63,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-85","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages\/85","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/comments?post=85"}],"version-history":[{"count":0,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages\/85\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages\/63"}],"wp:attachment":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/media?parent=85"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}