{"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\" id=\"wpb-content-root\"><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=\"https:\/\/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=\"https:\/\/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"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v28.8 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Cross-entropy\/optimisation hybrid approach - Flinders Hamiltonian Cycle Project<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/cross-entropy-optimisation-hybrid-approach\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Cross-entropy\/optimisation hybrid approach - Flinders Hamiltonian Cycle Project\" \/>\n<meta property=\"og:description\" content=\"[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;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/cross-entropy-optimisation-hybrid-approach\/\" \/>\n<meta property=\"og:site_name\" content=\"Flinders Hamiltonian Cycle Project\" \/>\n<meta property=\"article:modified_time\" content=\"2020-01-17T01:49:41+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/hcp-approaches\\\/cross-entropy-optimisation-hybrid-approach\\\/\",\"url\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/hcp-approaches\\\/cross-entropy-optimisation-hybrid-approach\\\/\",\"name\":\"Cross-entropy\\\/optimisation hybrid approach - Flinders Hamiltonian Cycle Project\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/#website\"},\"datePublished\":\"2020-01-17T01:41:11+00:00\",\"dateModified\":\"2020-01-17T01:49:41+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/hcp-approaches\\\/cross-entropy-optimisation-hybrid-approach\\\/#breadcrumb\"},\"inLanguage\":\"en-AU\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/hcp-approaches\\\/cross-entropy-optimisation-hybrid-approach\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/hcp-approaches\\\/cross-entropy-optimisation-hybrid-approach\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"HCP APPROACHES\",\"item\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/hcp-approaches\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Cross-entropy\\\/optimisation hybrid approach\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/#website\",\"url\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/\",\"name\":\"Flinders Hamiltonian Cycle Project\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-AU\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Cross-entropy\/optimisation hybrid approach - Flinders Hamiltonian Cycle Project","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/cross-entropy-optimisation-hybrid-approach\/","og_locale":"en_US","og_type":"article","og_title":"Cross-entropy\/optimisation hybrid approach - Flinders Hamiltonian Cycle Project","og_description":"[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;]","og_url":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/cross-entropy-optimisation-hybrid-approach\/","og_site_name":"Flinders Hamiltonian Cycle Project","article_modified_time":"2020-01-17T01:49:41+00:00","twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/cross-entropy-optimisation-hybrid-approach\/","url":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/cross-entropy-optimisation-hybrid-approach\/","name":"Cross-entropy\/optimisation hybrid approach - Flinders Hamiltonian Cycle Project","isPartOf":{"@id":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/#website"},"datePublished":"2020-01-17T01:41:11+00:00","dateModified":"2020-01-17T01:49:41+00:00","breadcrumb":{"@id":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/cross-entropy-optimisation-hybrid-approach\/#breadcrumb"},"inLanguage":"en-AU","potentialAction":[{"@type":"ReadAction","target":["https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/cross-entropy-optimisation-hybrid-approach\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/cross-entropy-optimisation-hybrid-approach\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/"},{"@type":"ListItem","position":2,"name":"HCP APPROACHES","item":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/"},{"@type":"ListItem","position":3,"name":"Cross-entropy\/optimisation hybrid approach"}]},{"@type":"WebSite","@id":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/#website","url":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/","name":"Flinders Hamiltonian Cycle Project","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-AU"}]}},"_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}]}}