{"id":2336,"date":"2014-01-28T17:03:15","date_gmt":"2014-01-28T17:03:15","guid":{"rendered":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp\/?post_type=portfolio&#038;p=2336"},"modified":"2016-08-25T16:41:13","modified_gmt":"2016-08-25T14:41:13","slug":"knapsack_genetic","status":"publish","type":"portfolio","link":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/gfx\/knapsack_genetic\/","title":{"rendered":"<strong>A fast genetic algorithm for the 0-1 knapsack problem<\/strong> <br\/> In less than 150 effective lines of C++ code"},"content":{"rendered":"<div  class='avia-slideshow av-av_slideshow-2bc7dc1e14d92062282adc74e7f5acff avia-slideshow-no scaling av_slideshow avia-slide-slider  avia-builder-el-0  el_before_av_heading  avia-builder-el-first  av-slideshow-ui av-control-default av-slideshow-manual av-loop-once av-loop-manual-endless av-default-height-applied avia-slideshow-1' data-slideshow-options=\"{&quot;animation&quot;:&quot;slide&quot;,&quot;autoplay&quot;:false,&quot;loop_autoplay&quot;:&quot;once&quot;,&quot;interval&quot;:5,&quot;loop_manual&quot;:&quot;manual-endless&quot;,&quot;autoplay_stopper&quot;:false,&quot;noNavigation&quot;:false,&quot;bg_slider&quot;:false,&quot;keep_padding&quot;:false,&quot;hoverpause&quot;:false,&quot;show_slide_delay&quot;:0}\"  itemprop=\"image\" itemscope=\"itemscope\" itemtype=\"https:\/\/schema.org\/ImageObject\" ><ul class='avia-slideshow-inner ' style='padding-bottom: 66.068222621185%;'><li  class='avia-slideshow-slide av-av_slideshow-2bc7dc1e14d92062282adc74e7f5acff__0  av-single-slide slide-1 slide-odd'><div data-rel='slideshow-1' class='avia-slide-wrap '   ><img decoding=\"async\" fetchpriority=\"high\" class=\"wp-image-2652 avia-img-lazy-loading-not-2652\"  src=\"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp\/wp-content\/uploads\/2014\/01\/genetic.png\" width=\"557\" height=\"368\" title='genetic' alt='Genetic Algorithm'  itemprop=\"thumbnailUrl\" srcset=\"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp\/wp-content\/uploads\/2014\/01\/genetic.png 557w, https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp\/wp-content\/uploads\/2014\/01\/genetic-300x198.png 300w, https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp\/wp-content\/uploads\/2014\/01\/genetic-450x297.png 450w\" sizes=\"(max-width: 557px) 100vw, 557px\" \/><\/div><\/li><\/ul><\/div>\n\n<style type=\"text\/css\" data-created_by=\"avia_inline_auto\" id=\"style-css-av-av_heading-120b94b502af4b26431c028068a5cfbd\">\n#top .av-special-heading.av-av_heading-120b94b502af4b26431c028068a5cfbd{\npadding-bottom:10px;\n}\nbody .av-special-heading.av-av_heading-120b94b502af4b26431c028068a5cfbd .av-special-heading-tag .heading-char{\nfont-size:25px;\n}\n.av-special-heading.av-av_heading-120b94b502af4b26431c028068a5cfbd .av-subheading{\nfont-size:15px;\n}\n<\/style>\n<div  class='av-special-heading av-av_heading-120b94b502af4b26431c028068a5cfbd av-special-heading-h3 meta-heading  avia-builder-el-1  el_after_av_slideshow  el_before_av_textblock '><h3 class='av-special-heading-tag '  itemprop=\"headline\"  >Challenge<\/h3><div class=\"special-heading-border\"><div class=\"special-heading-inner-border\"><\/div><\/div><\/div>\n<section  class='av_textblock_section av-av_textblock-0366cc7376be6c9e82a3e9cc8987b64f '   itemscope=\"itemscope\" itemtype=\"https:\/\/schema.org\/CreativeWork\" ><div class='avia_textblock'  itemprop=\"text\" ><p style=\"text-align: justify;\"><span class='av_dropcap2 av-av_dropcap2-9748a9e7bfa4060cd3cfa8398f0a06a5'>S<\/span>olve the\u00a0<a href=\"http:\/\/en.wikipedia.org\/wiki\/Knapsack_problem\">knapsack problem<\/a>\u00a0with 1,000 items and with a weight limit of 50,\u00a0<strong>in less than a second<\/strong>, with weights and values given between 1 and 30. Only the\u00a0<strong>optimal solution<\/strong>\u00a0is acceptable!<\/p>\n<\/div><\/section>\n<div  class='hr av-av_hr-d3021aff4e2c88ff75459fd6b3a45a12 hr-default  avia-builder-el-3  el_after_av_textblock  el_before_av_heading '><span class='hr-inner '><span class=\"hr-inner-style\"><\/span><\/span><\/div>\n\n<style type=\"text\/css\" data-created_by=\"avia_inline_auto\" id=\"style-css-av-av_heading-18a6f6eb235b29c0bbae26f59862f61b\">\n#top .av-special-heading.av-av_heading-18a6f6eb235b29c0bbae26f59862f61b{\npadding-bottom:10px;\n}\nbody .av-special-heading.av-av_heading-18a6f6eb235b29c0bbae26f59862f61b .av-special-heading-tag .heading-char{\nfont-size:25px;\n}\n.av-special-heading.av-av_heading-18a6f6eb235b29c0bbae26f59862f61b .av-subheading{\nfont-size:15px;\n}\n<\/style>\n<div  class='av-special-heading av-av_heading-18a6f6eb235b29c0bbae26f59862f61b av-special-heading-h3 meta-heading  avia-builder-el-4  el_after_av_hr  el_before_av_textblock '><h3 class='av-special-heading-tag '  itemprop=\"headline\"  >Features<\/h3><div class=\"special-heading-border\"><div class=\"special-heading-inner-border\"><\/div><\/div><\/div>\n<section  class='av_textblock_section av-av_textblock-0366cc7376be6c9e82a3e9cc8987b64f '   itemscope=\"itemscope\" itemtype=\"https:\/\/schema.org\/CreativeWork\" ><div class='avia_textblock'  itemprop=\"text\" ><div>\n<ul>\n<li>an\u00a0<em>evolutionary approach\u00a0<\/em>to solve an NP-hard\/NP-complete problem,<\/li>\n<li>chromosome initialization via a greedy algorithm,<\/li>\n<li>elitist selection strategy,<\/li>\n<li>three different crossover strategies,<\/li>\n<li>extremely low memory usage,<\/li>\n<li>multithreaded computation,<\/li>\n<li>a lot of performance tweaks here and there,<\/li>\n<li><em><strong>&#8230; in less than 200 lines of c++!<\/strong><\/em><\/li>\n<\/ul>\n<p style=\"text-align: justify;\">The algorithm uses ~1,1MB of memory for the 1,000 item, and still less than 3,5MB for the 10,000 item problem sets &#8211; compare it to the memory consumption of the dynamic programming approach of the problem. The average time needed to compute the optimum with\u00a0<em>1,000<\/em>\u00a0items and a limit of<em>50<\/em>\u00a0is\u00a00.05s\u00a0&#8211; that&#8217;s\u00a01\/20th\u00a0of a second.<\/p>\n<\/div>\n<\/div><\/section>\n\n<style type=\"text\/css\" data-created_by=\"avia_inline_auto\" id=\"style-css-av-av_heading-d8734b0351f56e5ec86b7b64cdc70dcb\">\n#top .av-special-heading.av-av_heading-d8734b0351f56e5ec86b7b64cdc70dcb{\npadding-bottom:10px;\n}\nbody .av-special-heading.av-av_heading-d8734b0351f56e5ec86b7b64cdc70dcb .av-special-heading-tag .heading-char{\nfont-size:25px;\n}\n.av-special-heading.av-av_heading-d8734b0351f56e5ec86b7b64cdc70dcb .av-subheading{\nfont-size:15px;\n}\n<\/style>\n<div  class='av-special-heading av-av_heading-d8734b0351f56e5ec86b7b64cdc70dcb av-special-heading-h3  avia-builder-el-6  el_after_av_textblock  el_before_av_one_fourth '><h3 class='av-special-heading-tag '  itemprop=\"headline\"  >Download<\/h3><div class=\"special-heading-border\"><div class=\"special-heading-inner-border\"><\/div><\/div><\/div>\n<div  class='flex_column av-av_one_fourth-2a9015ff38129c418a3f2eafba3e9512 av_one_fourth  avia-builder-el-7  el_after_av_heading  el_before_av_textblock  first flex_column_div  '     ><style type=\"text\/css\" data-created_by=\"avia_inline_auto\" id=\"style-css-av-av_image-8b55740232b34215c9b1a77bea09c6a1\">\n.avia-image-container.av-av_image-8b55740232b34215c9b1a77bea09c6a1 img.avia_image{\nbox-shadow:none;\n}\n.avia-image-container.av-av_image-8b55740232b34215c9b1a77bea09c6a1 .av-image-caption-overlay-center{\ncolor:#ffffff;\n}\n<\/style>\n<div  class='avia-image-container av-av_image-8b55740232b34215c9b1a77bea09c6a1 av-styling- av-img-linked avia_animated_image av-animated-when-visible-95 left-to-right avia-align-center  avia-builder-el-8  el_before_av_textblock  avia-builder-el-first '   itemprop=\"image\" itemscope=\"itemscope\" itemtype=\"https:\/\/schema.org\/ImageObject\" ><div class=\"avia-image-container-inner\"><div class=\"avia-image-overlay-wrap\"><a href=\"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp\/wp-content\/uploads\/2014\/02\/genetic.zip\" class='avia_image '  target=\"_blank\"  rel=\"noopener noreferrer\" aria-label='code-icon'><img decoding=\"async\" width=\"180\" height=\"180\" fetchpriority=\"high\" class='wp-image-2653 avia-img-lazy-loading-not-2653 avia_image ' src=\"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp\/wp-content\/uploads\/2014\/02\/code-icon-180x180.png\" alt='' title='code-icon'   itemprop=\"thumbnailUrl\" srcset=\"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp\/wp-content\/uploads\/2014\/02\/code-icon-180x180.png 180w, https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp\/wp-content\/uploads\/2014\/02\/code-icon-80x80.png 80w, https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp\/wp-content\/uploads\/2014\/02\/code-icon-36x36.png 36w, https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp\/wp-content\/uploads\/2014\/02\/code-icon-120x120.png 120w, https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp\/wp-content\/uploads\/2014\/02\/code-icon-450x450.png 450w\" sizes=\"(max-width: 180px) 100vw, 180px\" \/><\/a><\/div><\/div><\/div>\n<section  class='av_textblock_section av-av_textblock-a7bac4a6e49c8eb47262a43fda825da8 '   itemscope=\"itemscope\" itemtype=\"https:\/\/schema.org\/CreativeWork\" ><div class='avia_textblock'  itemprop=\"text\" ><p style=\"text-align: center;\"><strong>Code<\/strong><\/p>\n<\/div><\/section><\/div>\n<section  class='av_textblock_section av-av_textblock-0366cc7376be6c9e82a3e9cc8987b64f '   itemscope=\"itemscope\" itemtype=\"https:\/\/schema.org\/CreativeWork\" ><div class='avia_textblock'  itemprop=\"text\" ><p align=\"justify\"><span style=\"line-height: 1.5em;\">Feel free to fiddle around with the parameters to achieve better results at different, possibly harder problem sets!<\/span><\/p>\n<\/div><\/section>\n\n<style type=\"text\/css\" data-created_by=\"avia_inline_auto\" id=\"style-css-av-av_heading-fe95decfca858f59f8b1ccab29b9e46b\">\n#top .av-special-heading.av-av_heading-fe95decfca858f59f8b1ccab29b9e46b{\npadding-bottom:10px;\n}\nbody .av-special-heading.av-av_heading-fe95decfca858f59f8b1ccab29b9e46b .av-special-heading-tag .heading-char{\nfont-size:25px;\n}\n.av-special-heading.av-av_heading-fe95decfca858f59f8b1ccab29b9e46b .av-subheading{\nfont-size:15px;\n}\n<\/style>\n<div  class='av-special-heading av-av_heading-fe95decfca858f59f8b1ccab29b9e46b av-special-heading-h3  avia-builder-el-11  el_after_av_textblock  el_before_av_video '><h3 class='av-special-heading-tag '  itemprop=\"headline\"  >How does it work?<\/h3><div class=\"special-heading-border\"><div class=\"special-heading-inner-border\"><\/div><\/div><\/div>\n<div  class='avia-video av-av_video-13a4c64e638cdc55127eeb0c63b75292 avia-video-16-9 av-no-preview-image avia-video-load-always av-lazyload-immediate av-lazyload-video-embed'  itemprop=\"video\" itemtype=\"https:\/\/schema.org\/VideoObject\"  data-original_url='https:\/\/www.youtube.com\/watch?v=ziMHaGQJuSI'><script type='text\/html' class='av-video-tmpl'><div class='avia-iframe-wrap'><iframe loading=\"lazy\" width=\"1500\" height=\"844\" src=\"https:\/\/www.youtube.com\/embed\/ziMHaGQJuSI?feature=oembed&autoplay=0&loop=0&controls=1&mute=0\" frameborder=\"0\" allowfullscreen><\/iframe><\/div><\/script><div class='av-click-to-play-overlay'><div class=\"avia_playpause_icon\"><\/div><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":2335,"template":"","meta":{"jetpack_post_was_ever_published":false,"footnotes":""},"tags":[186,48,49,44],"portfolio_category":[],"portfolio_tag":[45,37],"portfolio_entries":[],"class_list":["post-2336","portfolio","type-portfolio","status-publish","has-post-thumbnail","hentry","tag-education","tag-genetic-algorithm","tag-knapsack-problem","tag-teaching","portfolio_tag-education","portfolio_tag-global-illumination"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp-json\/wp\/v2\/portfolio\/2336","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp-json\/wp\/v2\/portfolio"}],"about":[{"href":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp-json\/wp\/v2\/types\/portfolio"}],"author":[{"embeddable":true,"href":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp-json\/wp\/v2\/users\/1"}],"version-history":[{"count":21,"href":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp-json\/wp\/v2\/portfolio\/2336\/revisions"}],"predecessor-version":[{"id":4046,"href":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp-json\/wp\/v2\/portfolio\/2336\/revisions\/4046"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp-json\/wp\/v2\/media\/2335"}],"wp:attachment":[{"href":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp-json\/wp\/v2\/media?parent=2336"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp-json\/wp\/v2\/tags?post=2336"},{"taxonomy":"portfolio_category","embeddable":true,"href":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp-json\/wp\/v2\/portfolio_category?post=2336"},{"taxonomy":"portfolio_tag","embeddable":true,"href":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp-json\/wp\/v2\/portfolio_tag?post=2336"},{"taxonomy":"portfolio_entries","embeddable":true,"href":"https:\/\/users.cg.tuwien.ac.at\/zsolnai\/wp-json\/wp\/v2\/portfolio_entries?post=2336"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}