{"id":452,"date":"2011-03-05T17:37:44","date_gmt":"2011-03-05T17:37:44","guid":{"rendered":"http:\/\/www.lukas-kalinowski.com\/Homepage\/?page_id=452"},"modified":"2021-01-19T14:03:01","modified_gmt":"2021-01-19T14:03:01","slug":"machine-learning-ws1011","status":"publish","type":"page","link":"http:\/\/www.lukas-kalinowski.com\/Homepage\/machine-learning-ws1011\/","title":{"rendered":"Machine Learning WS10\/11"},"content":{"rendered":"<p><script type=\"text\/javascript\" src=\"swfobject.js\">\n            swfobject.registerObject(\"csSWF\", \"9.0.115\", \"expressInstall.swf\");\n<\/script><\/p>\n<style type=\"text\/css\">\n            #media\n            {\n                margin-top: 40px;\n            }\n            #noUpdate\n            {\n                margin: 0 auto;\n                font-family:Arial, Helvetica, sans-serif;\n                font-size: x-small;\n                color: #cccccc;\n                text-align: left;\n                width: 210px; \n                height: 200px;\t\n                padding: 40px;\n            }\n<\/style>\n<h2><span style=\"color: #3282cd;\">Travelling Salesman Problem (TSP)<\/span><\/h2>\n<h3><span style=\"color: #3282cd;\">Bearbeiter<\/span><\/h3>\n<ul>\n<li>Michael Gebhardt<\/li>\n<li>Lukas Kalinowski<\/li>\n<\/ul>\n<h3><span style=\"color: #3282cd;\">Beschreibung<\/span><\/h3>\n<p style=\"text-align: justify;\">Im Rahmen der \u00dcbung aus der Vorlesung Machine Learning wurde das Optimierungsproblem TSP mit genetischen Algorithmen gel\u00f6st. Dabei existiert eine Anzahl an St\u00e4dten, die bereist werden sollen. Es wird bei einer Stadt begonnen und eine Tour durch alle St\u00e4dte durchgef\u00fchrt, bis der Ausgangspunkt wieder erreicht wird. Dabei soll die Gesamtl\u00e4nge der Tour minimal sein. Die Entwicklung erfolgte in der Programmiersprache java.<\/p>\n<h3><span style=\"color: #3282cd;\">Vorgehen<\/span><\/h3>\n<ol  style=\"text-align: justify;\">\n<li>Eine geeignete Repr\u00e4sentation des Problems w\u00e4hlen:<br \/>\nEine Klasse &#8222;City&#8220; (Gen), bestehend aus einer x- und y-Position und Berechnung der Distanz zwischen zwei St\u00e4dten.<br \/>\nEine &#8222;Tour&#8220; Klasse (Individuum), zum W\u00e4hlen welche St\u00e4dte wann durchlaufen werden.<\/li>\n<li>Eine Population mit k Individuen erstellen, deren Parameters\u00e4tze zuf\u00e4llig generiert werden:<br \/>\nEine &#8222;Tour&#8220; Klasse, die eine Liste an St\u00e4dten (Gene) erh\u00e4lt und zun\u00e4chst zuf\u00e4llig \u00fcber alle zu durchlaufenden St\u00e4dte generiert wird. Es werden k Touren entwickelt (Population)<\/li>\n<li>Anhand der individuellen Fitness werden je zwei Individuen zur Reproduktion ausgew\u00e4hlt:<br \/>\nDie Fitness einer Tour berechnet sich aus der Gesamtdistanz beim Durchlaufen aller St\u00e4dte. Es wurden drei Verfahren zur Selektion einer Tour (Population) entwickelt: <a href=\"http:\/\/www.obitko.com\/tutorials\/genetic-algorithms\/selection.php\" target=\"_blank\">Roulettewheel-, Rank- und Tournament-Selektion.<\/a><\/li>\n<li>F\u00fcr jedes Elternpaar werden die folgenden Schritte durchgef\u00fchrt:\n<ul>\n<li>Es wird ein Nachkommen durch Rekombination der Gene generiert.<\/li>\n<li>Es werden zuf\u00e4llige Mutationen beim Nachkommen durchgef\u00fchrt.<\/li>\n<\/ul>\n<p>\nF\u00fcr die Rekombination wurden drei Verfahren implementiert: <a href=\"http:\/\/www.obitko.com\/tutorials\/genetic-algorithms\/crossover-mutation.php\" target=\"_blank\">Single-Point, Two-Point und Uniform<\/a><br \/>\nWobei bei der Entwicklung der Verfahren stets gew\u00e4hrleistet werden musste, dass bei einem Nachkommen keine Stadt zweimal durch die Tour besucht wird.<\/li>\n<li>Entspricht das fitteste Individuum als Hypothese der Problemstellung nicht hinreichend genau, gehe zu Schritt 3:<br \/>\nAls Problemstellung wird die Gesamtl\u00e4nge der Tour sowie die Anzahl an Kreuzungen beim Rundlauf der St\u00e4dte aufgefasst. Es kann mehrere optimale L\u00f6sungen geben, daher kann in der Anwendung die Anzahl an Generationen (Iterationen von Schritt 5 zu 3), die durchlaufen werden sollen \u00fcber einen Parameter festgelegt werden.<\/li>\n<\/ol>\n<h3><span style=\"color: #3282cd;\">Demonstration<\/span><\/h3>\n<div id=\"media\">\n     <iframe loading=\"lazy\" width=\"922\" height=\"721\" src=\"https:\/\/www.youtube.com\/embed\/EfSGjpoNwyE\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n        <\/div>\n<p>\n<a href=\"http:\/\/www.lukas-kalinowski.com\/Homepage\/?page_id=23\" target=\"_self\">zur\u00fcck<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Travelling Salesman Problem (TSP) Bearbeiter Michael Gebhardt Lukas Kalinowski Beschreibung Im Rahmen der \u00dcbung aus der Vorlesung Machine Learning wurde das Optimierungsproblem TSP mit genetischen Algorithmen gel\u00f6st. Dabei existiert eine Anzahl an St\u00e4dten, die bereist werden sollen. Es wird bei &hellip; <a href=\"http:\/\/www.lukas-kalinowski.com\/Homepage\/machine-learning-ws1011\/\">Weiterlesen <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"onecolumn-page.php","meta":{"ngg_post_thumbnail":0,"footnotes":""},"class_list":["post-452","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"http:\/\/www.lukas-kalinowski.com\/Homepage\/wp-json\/wp\/v2\/pages\/452","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.lukas-kalinowski.com\/Homepage\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/www.lukas-kalinowski.com\/Homepage\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/www.lukas-kalinowski.com\/Homepage\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.lukas-kalinowski.com\/Homepage\/wp-json\/wp\/v2\/comments?post=452"}],"version-history":[{"count":18,"href":"http:\/\/www.lukas-kalinowski.com\/Homepage\/wp-json\/wp\/v2\/pages\/452\/revisions"}],"predecessor-version":[{"id":2391,"href":"http:\/\/www.lukas-kalinowski.com\/Homepage\/wp-json\/wp\/v2\/pages\/452\/revisions\/2391"}],"wp:attachment":[{"href":"http:\/\/www.lukas-kalinowski.com\/Homepage\/wp-json\/wp\/v2\/media?parent=452"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}